هوش مصنوعی, علوم کامپیوتر

الگوریتم گرگ خاکستری (Grey Wolf Optimizer) و کاربردهای آن در بهینه‌سازی هوشمند

1.21k بازدید   بروزرسانی: ۱۷ دی ۱۴۰۳   زمان مطالعه: 9 دقیقه   دانلود PDF مقاله  
تصویری از الگوریتم گرگ خاکستری

الگوریتم گرگ خاکستری Grey Wolf Optimizer که به الگوریتم GWO معروف است یک الگوریتم بهینه سازی مبتنی بر جمعیت است که از رفتار گرگ های خاکستری در زندگی کردن و روش شکار آن‌‌ها الهام گرفته شده است. در این مقاله از مجله پی استور، الگوریتم گرگ خاکستری را تشریح خواهیم کرد و در ادامه کدهای پیاده سازی این الگوریتم در متلب و پایتون را بیان می کنیم.

فهرست مطالب این نوشته پنهان
مقدمه‌ای بر الگوریتم‌های بهینه‌سازی هوشمند
تاریخچه الگوریتم‌های بهینه‌سازی هوشمند
دسته‌بندی الگوریتم‌های بهینه‌سازی هوشمند
الگوریتم گرگ خاکستری (Grey Wolf Optimizer – GWO)
رفتار اجتماعی گرگ‌های خاکستری
فرمولاسیون ریاضی GWO
الگوریتم کلی GWO
شبه کد الگوریتم گرگ خاکستری
فلوچارت الگوریتم گرگ خاکستری
کد الگوریتم گرگ خاکستری در متلب
کد الگوریتم گرگ خاکستری در پایتون
کاربردهای الگوریتم گرگ خاکستری
مقایسه GWO با سایر الگوریتم‌های بهینه‌سازی
نتیجه‌گیری
بنر

مقدمه‌ای بر الگوریتم‌های بهینه‌سازی هوشمند

الگوریتم‌های بهینه‌سازی «Optimization Algorithms» به عنوان یکی از شاخه‌های اصلی در علم محاسبات تکاملی و الهام‌گرفته از طبیعت «Nature-inspired» در دهه‌های اخیر معرفی و گسترش یافته‌اند. این الگوریتم‌ها، با الهام از پدیده‌های طبیعی، رفتار موجودات زنده و پدیده‌های اجتماعی، به دنبال حل مسائل پیچیده‌ی بهینه‌سازی هستند که با روش‌های متعارف حل نمی‌شوند.

یکی از مسائل اساسی در علوم مهندسی، ریاضی و علوم داده، مسئله بهینه‌سازی «Optimization Problem» است که در آن هدف یافتن بهترین جواب از بین تمامی جواب‌های ممکن است. این مسائل معمولاً به دو دسته مسائل بهینه‌سازی تک‌هدفه (Single-objective Optimization) و چندهدفه (Multi-objective Optimization) تقسیم می‌شوند. الگوریتم‌های سنتی بهینه‌سازی از جمله روش‌های گرادیان (Gradient-based Methods) و برنامه‌ریزی خطی (Linear Programming) در مسائل پیچیده با تعداد زیاد متغیرها و قیود ناکارآمد هستند از اینرو الگوریتم‌های بهینه‌سازی هوشمند ایده‌ای جدید برای حل مسائل هستند.

تاریخچه الگوریتم‌های بهینه‌سازی هوشمند

ایده الگوریتم‌های بهینه‌سازی الهام گرفته از طبیعت به دهه ۱۹۶۰ بازمی‌گردد. اولین الگوریتم تکاملی «Evolutionary Algorithm» به عنوان الگوریتم ژنتیک «Genetic Algorithm» معرفی شد. سپس الگوریتم‌هایی مانند الگوریتم کلونی مورچگان «Ant Colony Optimization – ACO»، الگوریتم پرندگان یا ازدحام ذرات «Particle Swarm Optimization – PSO» و الگوریتم گرگ خاکستری «Grey Wolf Optimizer – GWO» معرفی شدند که هرکدام ویژگی‌ها و مزایای خاص خود را دارند.

دسته‌بندی الگوریتم‌های بهینه‌سازی هوشمند

الگوریتم‌های بهینه‌سازی هوشمند به دو دسته اصلی تقسیم می‌شوند:

  1. الگوریتم‌های مبتنی بر جمعیت (Population-based Algorithms): در این دسته، مجموعه‌ای از جواب‌های ممکن یا «جمعیت» (Population) تولید شده و سپس با تکرار فرآیندهای جهش، تقاطع و انتخاب، به سمت جواب بهینه حرکت می‌کنند. الگوریتم ژنتیک (Genetic Algorithm) و الگوریتم‌های ازدحامی مانند PSO و GWO در این دسته قرار می‌گیرند.
  2. الگوریتم‌های جستجوی تکراری (Iterative Search Algorithms): این الگوریتم‌ها با استفاده از تکرار یک جستجوی محلی یا روش‌های دیگر به دنبال بهبود جواب فعلی هستند. الگوریتم‌های مشتق‌پذیر (Derivative-based Algorithms) و الگوریتم تبرید تدریجی (Simulated Annealing – SA) از این دسته‌اند.
تصویری الگوریتم های بهینه سازی هوشمند
پاورپوینت آماده و تخصصی پی استور ویژه الگوریتم های بهینه سازی هوشمند
کلیک کنید

الگوریتم گرگ خاکستری (Grey Wolf Optimizer – GWO)

الگوریتم گرگ خاکستری (GWO) یکی از الگوریتم‌های الهام گرفته از طبیعت است که در سال ۲۰۱۴ توسط سید علی میرجلیلی و همکاران (Mirjalili et al) ارائه شد. این الگوریتم با الهام از رفتار اجتماعی و شکار گرگ‌های خاکستری طراحی شده است. گرگ‌های خاکستری به عنوان شکارچیان برتر در طبیعت، رفتارهای پیچیده‌ای در هماهنگی و رهبری گروهی دارند که می‌تواند به عنوان مدلی برای جستجوی فضای بهینه‌سازی استفاده شود.

رفتار اجتماعی گرگ‌های خاکستری

گرگ‌های خاکستری در طبیعت به صورت گروهی زندگی می‌کنند و هر گروه دارای سلسله مراتبی مشخص است. اعضای گروه به چهار دسته تقسیم می‌شوند:

تصویری از سلسله مراتب گرهای خاکستری

  1. آلفا (Alpha): رهبر گروه که تصمیمات اصلی مانند زمان شکار، مکان استراحت و دیگر رفتارهای گروه را تعیین می‌کند. گرگ‌های دیگر از دستورات او پیروی می‌کنند.
  2. بتا (Beta): دومین مقام در گروه که به آلفا در اجرای دستورات کمک کرده و در غیاب او نقش رهبری را به عهده می‌گیرد.
  3. گاما (Gamma): این دسته شامل گرگ‌های پایین‌تر در سلسله مراتب است که وظیفه نگهبانی و جستجوی شکار را دارند.
  4. اُمگا (Omega): پایین‌ترین رتبه در گروه که به عنوان تسلیم‌ترین عضو عمل می‌کند و از دستورات تمامی گرگ‌ها پیروی می‌کند.

این سلسله مراتب رفتاری در الگوریتم GWO برای یافتن جواب بهینه مورد استفاده قرار می‌گیرد. آلفا به عنوان بهترین جواب فعلی (Best Solution) و بتا و گاما به عنوان جواب‌های دوم و سوم انتخاب می‌شوند. اُمگا به عنوان جمعیت باقی‌مانده عمل کرده و به پیروی از سه جواب برتر عمل می‌کند.

فرمولاسیون ریاضی GWO

الگوریتم گرگ خاکستری از سه مرحله اصلی در جستجوی بهینه‌سازی استفاده می‌کند: ردگیری (Tracking)، محاصره (Encircling)، و حمله (Attacking) به شکار. این مراحل به صورت ریاضیاتی مدل‌سازی می‌شوند.

فرمولاسیون ریاضی GWO

محاصره (Encircling)

در الگوریتم GWO، فرآیند محاصره شکار با استفاده از معادلات زیر مدل‌سازی می‌شود:

$${\bf{D}} = \mid {\bf{C}} \cdot {{\bf{X}}_{\bf{p}}}(t) – {\bf{X}}(t)\mid $$

$${\bf{X}}(t + 1) = {{\bf{X}}_{\bf{p}}}(t) – {\bf{A}} \cdot {\bf{D}}$$

  • \({{\bf{X}}_{\bf{p}}}(t) \): موقعیت شکار در زمان
  • \(X(t)\): موقعیت گرگ خاکستری
  • \(A\) و \(C\) ضرایب کنترلی که در مراحل مختلف جستجو به روز رسانی می شوند.

ضرایب A و C به صورت زیر تعریف می‌شوند:

$$A = 2a \cdot {r_1} – a$$

$${\bf{C}} = 2 \cdot {{\bf{r}}_{\bf{2}}}$$

  • \(a\) مقداری است که از ۲ به ۰ کاهش می‌یابد (در طول تکرارها).
  • \({{\bf{r}}_{\bf{1}}}\) و \({{\bf{r}}_{\bf{2}}}\) اعداد تصادفی در بازه \(\left[ {0,1} \right]\)

حمله (Attacking)

حمله به شکار زمانی اتفاق می‌افتد که گرگ‌ها به شکار نزدیک شده باشند. این مرحله با کاهش مقدار a کنترل می‌شود. زمانی که A در بازه [-۱,۱] قرار بگیرد، گرگ‌ها به شکار نزدیک شده و حمله می‌کنند.

جستجو (Searching)

زمانی که مقدار  بزرگ‌تر از ۱ یا کوچک‌تر از -۱ باشد، گرگ‌ها به جای تمرکز روی شکار فعلی، شروع به جستجوی شکار جدید می‌کنند. این مرحله مشابه اکتشاف (Exploration) است.

الگوریتم کلی GWO

مراحل الگوریتم GWO به صورت زیر خلاصه می‌شود:

  1. ابتدا جمعیت گرگ‌ها (Population) به صورت تصادفی در فضای جستجو مقداردهی اولیه می‌شود.
  2. گرگ‌ها به سه گروه آلفا، بتا و گاما تقسیم می‌شوند که بهترین، دومین و سومین جواب‌ها را به ترتیب نشان می‌دهند.
  3. هر گرگ به‌روزرسانی می‌شود تا به شکار نزدیک شود.
  4. الگوریتم تا زمان رسیدن به معیار توقف (Stop Criterion) ادامه می‌یابد.

شبه کد الگوریتم گرگ خاکستری

Step1: Randomly initialize the population of grey wolves Xi  (i=1,2,…,n)
Step2: Initialize the value of a=2, A and C  ( using eq.3)
Step3: Calculate the fitness of each member of the population
Xα=member with the best fitness value
Xβ=second best member ( in terms of fitness value)
Xδ=third best member (in terms of fitness value)
Step4: FOR t = 1 to Max_number_of_iterations:
Update the position of all the omega wolves by eq. 4, 5 and 6
Update a, A, C (using eq. 3)
a = 2(1-t/T)
Calculate Fitness of all search agents
Update Xα, Xβ, Xδ.
            END FOR
Step5: return Xα

فلوچارت الگوریتم گرگ خاکستری

فلوچارت الگوریتم گرگ خاکستری

کد الگوریتم گرگ خاکستری در متلب

در ادامه کد پایه الگوریتم گرگ خاکستری (GWO) به زبان متلب ارائه می‌شود:

% تابع هدف
function obj = Sphere(x)
    obj = sum(x.^2);
end

% الگوریتم گرگ خاکستری
function GWO
    % پارامترهای اولیه
    SearchAgents_no = 30;  % تعداد گرگ‌ها
    Max_iter = 500;        % تعداد تکرارها
    dim = 5;               % تعداد ابعاد
    lb = -10;              % کران پایین
    ub = 10;               % کران بالا
    
    % مقداردهی اولیه موقعیت گرگ‌ها
    Positions = rand(SearchAgents_no, dim) .* (ub - lb) + lb;
    
    % مقادیر اولیه آلفا، بتا و دلتا
    Alpha_pos = zeros(1, dim);
    Alpha_score = inf;
    
    Beta_pos = zeros(1, dim);
    Beta_score = inf;
    
    Delta_pos = zeros(1, dim);
    Delta_score = inf;
    
    % حلقه اصلی الگوریتم
    for iter = 1:Max_iter
        for i = 1:SearchAgents_no
            % محدود کردن موقعیت گرگ‌ها به فضای جستجو
            Positions(i, : ) = max(min(Positions(i, : ), ub), lb);
            
            % ارزیابی تابع هدف برای هر گرگ
            fitness = Sphere(Positions(i, :));
            
            % به‌روزرسانی آلفا، بتا و دلتا
            if fitness < Alpha_score
                Alpha_score = fitness;
                Alpha_pos = Positions(i, :);
            elseif fitness < Beta_score
                Beta_score = fitness;
                Beta_pos = Positions(i, :);
            elseif fitness < Delta_score
                Delta_score = fitness;
                Delta_pos = Positions(i, :);
            end
        end
        
        % پارامترهای a، A و C
        a = 2 - iter * (2 / Max_iter);  % کاهش خطی پارامتر a
        A1 = 2 * a * rand() - a;
        A2 = 2 * a * rand() - a;
        A3 = 2 * a * rand() - a;
        C1 = 2 * rand();
        C2 = 2 * rand();
        C3 = 2 * rand();
        
        % به‌روزرسانی موقعیت گرگ‌ها
        for i = 1:SearchAgents_no
            D_alpha = abs(C1 * Alpha_pos - Positions(i, :));
            X1 = Alpha_pos - A1 * D_alpha;
            
            D_beta = abs(C2 * Beta_pos - Positions(i, :));
            X2 = Beta_pos - A2 * D_beta;
            
            D_delta = abs(C3 * Delta_pos - Positions(i, :));
            X3 = Delta_pos - A3 * D_delta;
            
            Positions(i, : ) = (X1 + X2 + X3) / 3;
        end
        
        % نمایش نتایج
        disp(['Iteration ' num2str(iter) ': Best score = ' num2str(Alpha_score)]);
    end
end

% اجرای الگوریتم
GWO
  1. تابع هدف: در اینجا از تابع Sphere به عنوان یک مثال استفاده شده است که تابع هدف برای بهینه‌سازی است. شما می‌توانید تابع هدف دیگری را جایگزین کنید.
  2. پارامترها:
    • SearchAgents_no: تعداد گرگ‌ها یا همان عامل‌های جستجو.
    • Max_iter: تعداد تکرارهای الگوریتم.
    • dim: تعداد ابعاد مسئله.
    • lb و ub: کران‌های بالا و پایین برای فضای جستجو.
  3. موقعیت‌ها: گرگ‌ها موقعیت‌های تصادفی اولیه در فضای جستجو دریافت می‌کنند.
  4. به‌روزرسانی موقعیت گرگ‌ها: موقعیت گرگ‌ها بر اساس موقعیت گرگ‌های آلفا، بتا و دلتا و با استفاده از فرمول‌های الگوریتم GWO به‌روزرسانی می‌شود.
  5. نمایش نتایج: در هر تکرار بهترین مقدار بهینه‌سازی نمایش داده می‌شود.

این کد می‌تواند به راحتی برای حل مسائل مختلف بهینه‌سازی استفاده شود و قابل تنظیم با تغییر تابع هدف و پارامترهای جستجو است.

الگوریتم گرگ خاکستری GWO در متلب
دوره آموزش کامل الگوریتم گرگ خاکستری GWO در متلب — تئوری و عملی
کلیک کنید

کد الگوریتم گرگ خاکستری در پایتون

الگوریتم بهینه‌سازی گرگ خاکستری (Gray Wolf Optimizer) را می‌توان به راحتی در پایتون پیاده‌سازی کرد. در ادامه کد پایه این الگوریتم به زبان پایتون آورده شده است:

import numpy as np

# تابع هدف (در اینجا تابع Sphere)
def sphere_function(x):
    return np.sum(x ** 2)

# الگوریتم گرگ خاکستری
class GWO:
    def __init__(self, obj_function, dim, n_agents, max_iter, lb, ub):
        self.obj_function = obj_function  # تابع هدف
        self.dim = dim  # تعداد ابعاد
        self.n_agents = n_agents  # تعداد گرگ‌ها
        self.max_iter = max_iter  # تعداد تکرارها
        self.lb = lb  # کران پایین
        self.ub = ub  # کران بالا

        # مقداردهی اولیه گرگ‌ها (موقعیت تصادفی در فضای جستجو)
        self.positions = np.random.uniform(self.lb, self.ub, (self.n_agents, self.dim))
        
        # بهترین گرگ‌ها: آلفا، بتا و دلتا
        self.alpha_pos = np.zeros(self.dim)
        self.alpha_score = float("inf")
        
        self.beta_pos = np.zeros(self.dim)
        self.beta_score = float("inf")
        
        self.delta_pos = np.zeros(self.dim)
        self.delta_score = float("inf")

    # حلقه اصلی الگوریتم
    def optimize(self):
        for iter in range(self.max_iter):
            for i in range(self.n_agents):
                # محدود کردن موقعیت گرگ‌ها به محدوده مشخص‌شده
                self.positions[i, :] = np.clip(self.positions[i, :], self.lb, self.ub)
                
                # محاسبه تابع هدف
                fitness = self.obj_function(self.positions[i, :])
                
                # به‌روزرسانی آلفا، بتا و دلتا
                if fitness < self.alpha_score:
                    self.alpha_score = fitness
                    self.alpha_pos = self.positions[i, :].copy()
                elif fitness < self.beta_score:
                    self.beta_score = fitness
                    self.beta_pos = self.positions[i, :].copy()
                elif fitness < self.delta_score:
                    self.delta_score = fitness
                    self.delta_pos = self.positions[i, :].copy()

            # به‌روزرسانی پارامترها
            a = 2 - iter * (2 / self.max_iter)  # کاهش خطی پارامتر a
            
            for i in range(self.n_agents):
                A1 = 2 * a * np.random.random(self.dim) - a
                C1 = 2 * np.random.random(self.dim)
                
                A2 = 2 * a * np.random.random(self.dim) - a
                C2 = 2 * np.random.random(self.dim)
                
                A3 = 2 * a * np.random.random(self.dim) - a
                C3 = 2 * np.random.random(self.dim)

                # موقعیت آلفا
                D_alpha = abs(C1 * self.alpha_pos - self.positions[i, :])
                X1 = self.alpha_pos - A1 * D_alpha
                
                # موقعیت بتا
                D_beta = abs(C2 * self.beta_pos - self.positions[i, :])
                X2 = self.beta_pos - A2 * D_beta
                
                # موقعیت دلتا
                D_delta = abs(C3 * self.delta_pos - self.positions[i, :])
                X3 = self.delta_pos - A3 * D_delta
                
                # به‌روزرسانی موقعیت گرگ‌ها
                self.positions[i, :] = (X1 + X2 + X3) / 3

            # نمایش بهترین نتیجه در هر تکرار
            print(f"Iteration {iter + 1}, Best score: {self.alpha_score}")
        
        # نتیجه نهایی
        return self.alpha_pos, self.alpha_score


# تنظیمات الگوریتم
dim = 5  # تعداد ابعاد
n_agents = 30  # تعداد گرگ‌ها
max_iter = 500  # تعداد تکرارها
lb = -10  # کران پایین
ub = 10  # کران بالا

# اجرای الگوریتم
gwo = GWO(sphere_function, dim, n_agents, max_iter, lb, ub)
best_position, best_score = gwo.optimize()

print("Best position:", best_position)
print("Best score:", best_score)
  1. تابع هدف: تابع sphere_function برای محاسبه مقدار تابع هدف استفاده می‌شود. این تابع به راحتی قابل تغییر است.
  2. کلاس GWO:
    • این کلاس شامل تمامی مراحل الگوریتم گرگ خاکستری است، از جمله مقداردهی اولیه، به‌روزرسانی موقعیت‌ها و بهینه‌سازی.
    • موقعیت گرگ‌های آلفا، بتا و دلتا در طول فرآیند به‌روزرسانی می‌شود.
  3. تابع optimize: این تابع حلقه اصلی الگوریتم را شامل می‌شود و موقعیت گرگ‌ها را در هر تکرار به‌روزرسانی می‌کند.
  4. پارامترها:
    • dim: تعداد ابعاد مسئله.
    • n_agents: تعداد گرگ‌ها یا عامل‌های جستجو.
    • max_iter: تعداد تکرارهای الگوریتم.
    • lb و ub: کران‌های پایین و بالای فضای جستجو.

این کد به راحتی قابل تغییر و تنظیم برای مسائل مختلف بهینه‌سازی است. کافی است تابع هدف و پارامترهای مسئله خود را به‌روزرسانی کنید.

الگوریتم گرگ خاکستری در پایتون
دوره جامع الگوریتم گرگ خاکستری در پایتون — تئوری و عملی
کلیک کنید

کاربردهای الگوریتم گرگ خاکستری

الگوریتم گرگ خاکستری در حوزه‌های مختلفی از جمله مهندسی، داده‌کاوی، بهینه‌سازی مسائل ترکیبی و مسائل بهینه‌سازی پیوسته استفاده شده است. برخی از کاربردهای مهم این الگوریتم عبارتند از:

  1. بهینه‌سازی توابع غیرخطی (Nonlinear Function Optimization): GWO برای بهینه‌سازی توابع پیچیده و غیرخطی با تعداد متغیرهای زیاد به کار می‌رود.
  2. بهینه‌سازی مسائل مهندسی (Engineering Optimization): الگوریتم GWO برای طراحی بهینه سازه‌ها، مدارهای الکتریکی و سیستم‌های مکانیکی استفاده می‌شود.
  3. انتخاب ویژگی (Feature Selection) در داده‌کاوی: این الگوریتم در انتخاب بهترین زیرمجموعه از ویژگی‌ها برای کاهش ابعاد داده و افزایش دقت مدل‌های یادگیری ماشین کاربرد دارد.

مقایسه GWO با سایر الگوریتم‌های بهینه‌سازی

الگوریتم GWO در مقایسه با الگوریتم‌های دیگر مانند الگوریتم ژنتیک (GA) و PSO مزایای زیر را دارد:

  • سادگی در پیاده‌سازی: GWO دارای ساختار ساده‌ای است و به راحتی می‌توان آن را برای مسائل مختلف بهینه‌سازی پیاده‌سازی کرد.
  • توازن بین اکتشاف و استخراج (Exploration and Exploitation): این الگوریتم به دلیل استفاده از ضرایب کنترلی A و C به طور پویا بین جستجو و بهبود جواب تعادل برقرار می‌کند.
  • پایداری و دقت بالا: GWO معمولاً در حل مسائل بهینه‌سازی پیچیده نتایج پایدارتری نسبت به برخی از الگوریتم‌های دیگر ارائه می‌دهد.

نتیجه‌گیری

الگوریتم گرگ خاکستری (GWO) یکی از الگوریتم‌های قدرتمند و انعطاف‌پذیر در حوزه بهینه‌سازی هوشمند است که با الهام از رفتار اجتماعی گرگ‌های خاکستری، توانسته است در حل مسائل بهینه‌سازی پیچیده به کار گرفته شود. این الگوریتم به دلیل ساختار ساده، توانایی بالا در جستجوی بهینه و کاربرد در مسائل مختلف، به عنوان یکی از ابزارهای اصلی در بهینه‌سازی‌های مدرن شناخته می‌شود.

اگر این مطلب برای شما مفید بوده است، مباحث زیر نیز به شما پیشنهاد می‌شوند:
میزان رضایتمندی
لطفاً میزان رضایت خودتان را از این مطلب با دادن امتیاز اعلام کنید.
[ امتیاز میانگین 5 از 1 نفر ]
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع و مراجع:
sciencedirect geeksforgeeks

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


برچسب‌ها:
الگوریتم بهینه سازی الگوریتم فرا ابتکاری الگوریتم مبتنی بر جمعیت متاهیوریستیک

مقالات مرتبط

پیمایش به بالا