开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 灰狼优化算法（GWO） -> 正文阅读

[人工智能]灰狼优化算法（GWO）

算法背景

灰狼优化算法(GWO)，由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能优化算法。灵感来自于灰狼群体捕食行为。

优点：较强的收敛性能，结构简单、需要调节的参数少，容易实现，存在能够自适应调整的收敛因子以及信息反馈机制，能够在局部寻优与全局搜索之间实现平衡，因此在对问题的求解精度和收敛速度方面都有良好的性能。

应用：车间调度、参数优化、图像分类

算法思想

灰狼群体中有严格的等级制度，一小部分拥有绝对话语权的灰狼带领一群灰狼向猎物前进。灰狼群一般分为4个等级：? $\alpha \beta \delta \omega$ ?（权利从大到小）模拟领导阶层。

集体狩猎是灰狼的一种社会行为，社会等级在集体狩猎过程中发挥着重要的作用，捕食的过程在α的带领下完成。主要包括三个步骤：

跟踪和接近猎物
骚扰、追捕和包围猎物，直到它停止移动
攻击猎物

社会等级分层

构建灰狼社会等级层次模型，对灰狼的社会等级进行数学建模。

考虑一个搜索空间，现实中狼群由眼睛嗅觉等等知道猎物的位置，然而计算机中模拟无法做到这点，但是我们可以假设，猎物位置是由我们在搜索空间中发现的最佳解决方案提供，我们可以使用该解决方案去找到更好的解决方案，不断迭代优化，此最优解决方案会非常接近最好的解决方案。

将? $\alpha$ ?作为最优解（个体的适应度最优），次优解?? $\beta$ ?，最佳解决方案? $\delta$ ?，剩下的候选解命名为? $\omega$ ，?狩猎过程由? $\alpha \beta \delta$ ?引导， $\omega$ ?跟随这三只狼。即我们总是去找到三个最佳解决方案，然后围绕该区域进行搜索，目的是找到更好的解决方案然后更新 $\alpha \beta \delta$ ?。

包围猎物

在狩猎过程中，将灰狼围捕猎物的行为定义如下：

个体与猎间的距离公式：

$D=|C\cdot X_{p}(t)-X(t)|$ ? ? ? ? （1）

灰狼位置更新公式：

$X(t+1)=X_{p}(t)-A\cdot D$ ? ? ? ? （2）

系数向量：

$A=2a\cdot r1-a$ ? ? ? ? （3）

$C=2\cdot r2$ ? ? ? ? （4）

其中：t 为迭代次数，D 是个体与猎间的距离向量， ‘ $\cdot$ ’?不是点积，是乘法， $X_{p}$ ?是猎物位置向量，X 为灰狼位置向量， $a$ ? 是收敛因子（随迭代次数从 2 线性减小到 0 ），r1 和 r2 是随机向量，模取【0-1】之间的随机数。

从公式可以看出，经过移动后灰狼群向? $\alpha$ ?移动，移动方向由自身位置和随机向量 C 决定，移动步长由隔离距离灰狼距离和系数向量 A 决定，即? $a$ ?线性减小意味着随机性和运动步长幅度，步长随迭代次数而减小越来越接近最优解。

狩猎

灰狼能够识别猎物的位置并包围它们。当灰狼识别出猎物的位置后,??在? $\alpha \beta \delta$ ?的带领下指导狼群包围猎物。灰狼个体跟踪猎物位置的数学模型描述如下：

$D_{\alpha }=|C_{1}\cdot X_{\alpha}-X|$ ????????????????????????

$D_{\beta }=|C_{2}\cdot X_{\beta }-X|$ ? ? ????????? ? （5）

$D_{\delta}=|C_{3}\cdot X_{\delta }-X|$ ????????????????????????

其中,? $D_{\alpha }$ ?， $D_{\beta }$ ?和? $D_{\delta }$ ?分别表示? $\alpha$ ??和?? $\beta$ , $\delta$ 与其他个体间的距离； $X_{\alpha } X_{\beta }X_{\delta }$ ?分别代表? $\alpha$ ??和?? $\beta$ , $\delta$ 当前的位置； $C_{1}C_{2}C_{3}$ ?是随机向量,? X 是当前灰狼的位置。

$X_{1}=X_{\alpha }-A_{1}\cdot (D_{\alpha })$ ????????????????????????

$X_{2}=X_{\beta }-A_{2}\cdot (D_{\beta })$ ? ? ? ? ? ? ? ? （6）

$X_{3}=X_{\delta }-A_{3}\cdot (D_{\delta })$ ????????????????????????

? $X_{t+1}=\frac{X_{1}+X_{2}+X_{3}}{3}$ ? ? ? ? ? ? ? ? （7）

式（6）分别定义了狼群中? $\omega$ ?个体朝向?? $\alpha$ ??和?? $\beta$ , $\delta$ ??前进的步长和方向，式 (7) 定义了ω的最终位置。

攻击猎物

当猎物停止移动时,灰狼通过攻击来完成狩猎过程.为了模拟逼近猎物,? $a$ ?的值被逐渐减小，因此? A的波动范围也随之减小。换句话说，在迭代过程中,当? $a$ ?的值从２线性下降到０时，其对应的 A 的值也在区间 [?- $a$ ,? $a$ ]?内变化。

如图所示，当? A 的值位于区间内时,灰狼的下一位置可以位于其当前位置和猎物位置之间的任意位置（由于随机），当 -1<A<1 时，狼群向猎物发起攻击(陷入局部最优)。当 A>1 或 A<-1 时，灰狼远离猎物，探索其他区域（为了找到全局最优解）。

GWO 另一个有利于全局探索的组件 C（随机权重），C?是[0,2]之间的随机向量。表示狼所在的位置对猎物影响的随机权重，C>1表示影响权重大，反之，表示影响权重小。在算法陷入了局部最优并且不易跳出时，?C?的随机性在避免局部最优方面发挥了非常重要的作用。

算法流程

伪代码

Initialize the grey wolf population Xi (i=1,2,,,,n)
Initialize a,A,C,t=0

Calculate the fitness of each search agent
X(alpha) = the best search agent
X(bete) = the second best search agent
X(delta) = the third best search agent

while (t< Max number of iterations)
    for each search agent
        Update the position of the current search agent
    end for

    Update a,A,and C
    Calculate the fitness of all search agents
    Update X(alpha),X(bete),and X(delta)
    t=t+1
end while

return X(alpha)

算法测试

求函数最大值（一元）

% 灰狼优化算法（求函数极值）
clc;
clear;
close all;
%% 目标函数
f= @(x) - (x - 10) .^ 2 + x .* sin(x) .* cos(2 * x) - 5 * x .* sin(3 * x) ; % 适应度函数表达式(求这个函数的最大值)  
figure(1);
fplot(f, [0 20], 'b-');                 % 画出初始图像 
title('初始图像');
hold on;
%% 初始化参数
N=30;       % 灰狼个数
dim=1;      % 维度
Iter=50;   % 最大迭代次数
a=2;        % 收敛因子
ub=20;      % 最大值限制
lb=0;       % 最小值限制

% 初始化alpha,beta,delta
Alpha_pos=zeros(1,dim);    
Alpha_score=-inf; %求最大值改为inf
Beta_pos=zeros(1,dim);
Beta_score=-inf; 
Delta_pos=zeros(1,dim);
Delta_score=-inf;

Positions=rand(N,dim).*(ub-lb)+lb;      % 初始化个体位置
Convergence_curve=zeros(1,Iter);        % 收敛曲线
l=0;        %循环次数记录

%% 迭代求解
while l<Iter
    for i=1:size(Positions,1)  
        
       % 超出边界处理
        Flag4ub=Positions(i,:)>ub;
        Flag4lb=Positions(i,:)<lb;
        Positions(i,:)=(Positions(i,:).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb;               
        
        % 计算个体适应度函数
        fitness=f(Positions(i,:));
        
        % 更新 Alpha, Beta, and Delta
        if fitness>Alpha_score 
            Alpha_score=fitness; 
            Alpha_pos=Positions(i,:);
        end    
        if fitness<Alpha_score && fitness>Beta_score 
            Beta_score=fitness; 
            Beta_pos=Positions(i,:);
        end     
        if fitness<Alpha_score && fitness<Beta_score && fitness>Delta_score 
            Delta_score=fitness; 
            Delta_pos=Positions(i,:);
        end
    end
       
    a=2-l*((2)/Iter); % 收敛因子从2线性递减到0
    
    % 更新灰狼个体的位置
    for i=1:size(Positions,1)
        for j=1:size(Positions,2)     
            
            r1=rand(); % r1 is a random number in [0,1]
            r2=rand(); % r2 is a random number in [0,1]   
            A1=2*a*r1-a;
            C1=2*r2;
            D_alpha=abs(C1*Alpha_pos(j)-Positions(i,j)); 
            X1=Alpha_pos(j)-A1*D_alpha;
                       
            r1=rand();
            r2=rand();          
            A2=2*a*r1-a;
            C2=2*r2;       
            D_beta=abs(C2*Beta_pos(j)-Positions(i,j));
            X2=Beta_pos(j)-A2*D_beta;
            
            r1=rand();
            r2=rand();          
            A3=2*a*r1-a; 
            C3=2*r2;          
            D_delta=abs(C3*Delta_pos(j)-Positions(i,j));
            X3=Delta_pos(j)-A3*D_delta;
            
            Positions(i,j)=(X1+X2+X3)/3;% Equation (3.7)         
        end
    end
    l=l+1;    
    Convergence_curve(l)=Alpha_score;
end
plot(Alpha_pos, f(Alpha_pos), '*r');

figure(2);
plot(Convergence_curve);
title('收敛过程'); 

display(['The best solution obtained by GWO is : ', num2str(Alpha_pos)]);
display(['The best optimal value of the objective funciton found by GWO is : ', num2str(Alpha_score)]);

二元函数求最大值

% 灰狼优化算法（求函数极值）
clc;
clear;
close all;
%% 目标函数
[ZuoBiao_x, ZuoBiao_y] = meshgrid(-10:0.1:10,-5:0.1:5);   % 产生二维坐标
ZuoBiao_z = f_xy(ZuoBiao_x, ZuoBiao_y);
figure(1);
s = mesh(ZuoBiao_x, ZuoBiao_y, ZuoBiao_z);                % 画出初始图像 
title('初始图像');
%% 初始化参数
N=30;       % 灰狼个数
dim=2;      % 维度
Iter=200;   % 最大迭代次数
a=2;        % 收敛因子
ub=[10 5];      % 最大值限制
lb=[-10 -5];       % 最小值限制

% 初始化alpha,beta,delta
Alpha_pos=zeros(1,dim);    
Alpha_score=-inf; %求最大值改为inf
Beta_pos=zeros(1,dim);
Beta_score=-inf; 
Delta_pos=zeros(1,dim);
Delta_score=-inf;

Positions=rand(N,dim).*(ub-lb)+lb;      % 初始化个体位置
Convergence_curve=zeros(1,Iter);        % 收敛曲线
l=0;        %循环次数记录

%% 迭代求解
while l<Iter
    for i=1:size(Positions,1)  
        
       % 超出边界处理
        Flag4ub=Positions(i,:)>ub;
        Flag4lb=Positions(i,:)<lb;
        Positions(i,:)=(Positions(i,:).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb;               
        
        % 计算个体适应度函数
        fitness=f_xy(Positions(i,1), Positions(i,2));
        
        % 更新 Alpha, Beta, and Delta
        if fitness>Alpha_score 
            Alpha_score=fitness; 
            Alpha_pos=Positions(i,:);
        end    
        if fitness<Alpha_score && fitness>Beta_score 
            Beta_score=fitness; 
            Beta_pos=Positions(i,:);
        end     
        if fitness<Alpha_score && fitness<Beta_score && fitness>Delta_score 
            Delta_score=fitness; 
            Delta_pos=Positions(i,:);
        end
    end
       
    a=2-l*((2)/Iter); % 收敛因子从2线性递减到0
    
    % 更新灰狼个体的位置
    for i=1:size(Positions,1)
        for j=1:size(Positions,2)     
            
            r1=rand(); % r1 is a random number in [0,1]
            r2=rand(); % r2 is a random number in [0,1]   
            A1=2*a*r1-a;
            C1=2*r2;
            D_alpha=abs(C1*Alpha_pos(j)-Positions(i,j)); 
            X1=Alpha_pos(j)-A1*D_alpha;
                       
            r1=rand();
            r2=rand();          
            A2=2*a*r1-a;
            C2=2*r2;       
            D_beta=abs(C2*Beta_pos(j)-Positions(i,j));
            X2=Beta_pos(j)-A2*D_beta;
            
            r1=rand();
            r2=rand();          
            A3=2*a*r1-a; 
            C3=2*r2;          
            D_delta=abs(C3*Delta_pos(j)-Positions(i,j));
            X3=Delta_pos(j)-A3*D_delta;
            
            Positions(i,j)=(X1+X2+X3)/3;% Equation (3.7)         
        end
    end
    l=l+1;    
    Convergence_curve(l)=Alpha_score;
end

figure(2);
plot(Convergence_curve);
title('收敛过程'); 

display(['The best solution obtained by GWO is : ', num2str(Alpha_pos)]);
display(['The best optimal value of the objective funciton found by GWO is : ', num2str(Alpha_score)]);

多元函书求最小值

链接：https://pan.baidu.com/s/1sQxYMXhwF1xhRqhXB1kJpQ?
提取码：1234?

GWO解TSP问题

待补充。。。。。。
?

[1] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey Wolf Optimizer," Advances in Engineering Software, vol. 69, pp. 46-61, 2014.