一、麻雀算法简介
麻雀搜索算法(Sparrow Search Algorithm, SSA)是于2020年提出的。SSA 主要是受麻雀的觅食行为和反捕食行为的启发而提出的。该算法比较新颖,具有寻优能力强,收敛速度快的优点。
1 算法原理
建立麻雀搜索算法的数学模型,主要规则如下所述:
(1)发现者通常拥有较高的能源储备并且在整个种群中负责搜索到具有丰富食物的区域,为所有的加入者提供觅食的区域和方向。在模型建立中能量储备的高低取决于麻雀个体所对应的适应度值(Fitness Value)的好坏。
(2)一旦麻雀发现了捕食者,个体开始发出鸣叫作为报警信号。当报警值大于安全值时,发现者会将加入者带到其它安全区域进行觅食。
(3)发现者和加入者的身份是动态变化的。只要能够寻找到更好的食物来源,每只麻雀都可以成为发现者,但是发现者和加入者所占整个种群数量的比重是不变的。也就是说,有一只麻雀变成发现者必然有另一只麻雀变成加入者。
(4)加入者的能量越低,它们在整个种群中所处的觅食位置就越差。一些饥肠辘辘的加入者更有可能飞往其它地方觅食,以获得更多的能量。
(5)在觅食过程中,加入者总是能够搜索到提供最好食物的发现者,然后从最好的食物中获取食物或者在该发现者周围觅食。与此同时,一些加入者为了增加自己的捕食率可能会不断地监控发现者进而去争夺食物资源。
(6)当意识到危险时,群体边缘的麻雀会迅速向安全区域移动,以获得更好的位置,位于种群中间的麻雀则会随机走动,以靠近其它麻雀。
在模拟实验中,我们需要使用虚拟麻雀进行食物的寻找,由n只麻雀组成的种群可表示为如下形式:
其中,d表示待优化问题变量的维数,n则是麻雀的数量。那么,所有麻雀的适应度值可以表示为如下形式:
其中,f表示适应度值。
在SSA中, 具有较好适应度值的发现者在搜索过程中会优先获取食物。此外, 因为发现者负责为整个麻雀种群寻找食物并为所有加入者提供觅食的方向。因此,发现者可以获得比加入者更大的觅食搜索范围。根据规则(1)和规则(2),在每次迭代的过程中,发现者的位置更新描述如下:
其中, t代表当前迭代数, j=1, 2, 3, ..., d.item maz是一个常数,表示最大的迭代次数。Xy表示第i个麻雀在第j维中的位置信息。xE(0,1]是一个随机数。R2(R2E[0,1])和ST(STe[0.5, 1] ) 分别表示预警值和安全值。Q是服从正态分布的随机数.L表示一个1×d的矩阵, 其中该矩阵内每个元素全部为
1.
当R2<ST时,这意味着此时的觅食环境周围没有捕食者,发现者可以执行广泛的搜索操作。如果R2≥ST,这表示种群中的一些麻雀已经发现了捕食者,井向种群中其它麻雀发出了警报,此时所有麻雀都需要迅速飞到其它安全的地方进行觅食。对于加入者,它们需要执行规则(3)和规则(4)。如前面所描述,在觅食过程中,一些加入者会时刻监视着发现者。一旦它们察觉到发现者已经找到了更好的食物,它们会立即离开现在的位置去争夺食物。如果它们赢了,它们可以立即获得该发现者的食物,否则需要继续执行规则(4)。加入者的位置更新描述如下:
其中, X, 是目前发现者所占据的最优位置, X worst则表示当前全局最差的位置。A表示一个1×d的矩阵, 其中每个元素随机赋值为1或-1,并且A+=A(AA)-.当i>n/2时,这表明,适应度值较低的第i个加入者没有获得食物,处于十分饥饿的状态,此时需要飞往其它地方觅食,以获得更多的能量。在模拟实验中,我们假设这些意识到危险的麻雀占总数量的10%到20%。这些麻雀的初始位置是在种群中随机产生的。根据规则(5),其数学表达式可以表示为如下形式:
其中, 其中X best是当前的全局最优位置。β作为步长控制参数, 是服从均值为0, 方差为1的正态分布的随机数。KE[-1, 1] 是一个随机数,则是当前麻雀个体的适应度值。f,和fw分别是当前全局最佳和最差的适应度值。e的常数,以避免分母出现零。
为简单起见, 当f:>f, 表示此时的麻雀正处于种群的边缘, 极其容易受到捕食者的攻击。X best表示这个位置的麻雀是种群中最好的位置也是十分安全的。f;=f,时,这表明处于种群中间的麻雀意识到了危险,需要靠近其它的麻雀以此尽量减少它们被捕食的风险。K表示麻雀移动的方向同时也是步长控制参数。
2 算法流程
Step1: 初始化种群,迭代次数,初始化捕食者和加入者比列。
Step2:计算适应度值,并排序。
Step3:利用式(3)更新捕食者位置。
Step4:利用式(4)更新加入者位置。
Step5:利用式(5)更新警戒者位置。
Step6:计算适应度值并更新麻雀位置。
Step7:是否满足停止条件,满足则退出,输出结果,否则,重复执行Step2-6;
二、源代码
% -----------------------------------------------------------------------------------------------------------
% Sparrow Search algorithm (SSA) (demo)
clear all
clc
SearchAgents_no=100; % 代数
Function_name=‘F1‘; % Name of the test function that can be from F1 to F23 (Table 1,2,3 in the paper)
Max_iteration=1000; % Maximum numbef of iterations
% Load details of the selected benchmark function
[lb,ub,dim,fobj]=Get_Functions_details(Function_name);
[fMin,bestX,SSA_curve]=SSA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj);
%Draw objective space
semilogy(SSA_curve,‘Color‘,‘g‘)
axis ([0 1000 0 1 ])
title(‘Objective space‘)
xlabel(‘Iteration‘);
ylabel(‘Best score obtained so far‘);
%axis tight
grid on
box on
legend(‘SSA‘)
display([‘The best solution obtained by SSA is : ‘, num2str(bestX)]);
display([‘The best optimal value of the objective funciton found by SSA is : ‘, num2str(fMin)]);
%pop是种群,M是迭代次数,fobj是用来计算适应度的函数
%pNum是生产者
%r1==a
% r2:预警值
% fit:适应度
function [fMin , bestX,Convergence_curve ] = SSA(pop, M,c,d,dim,fobj )
P_percent = 0.2; % The population size of producers accounts for "P_percent" percent of the total population size
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
pNum = round( pop * P_percent ); % The population size of the producers
lb= c.*ones( 1,dim ); % Lower limit/bounds/ a vector
ub= d.*ones( 1,dim ); % Upper limit/bounds/ a vector
%Initialization
for i = 1 : pop
x( i, : ) = lb + (ub - lb) .* rand( 1, dim );
fit( i ) = fobj( x( i, : ) ) ;
end
pFit = fit;
pX = x; % The individual‘s best position corresponding to the pFit
[ fMin, bestI ] = min( fit ); % fMin denotes the global optimum fitness value
bestX = x( bestI, : ); % bestX denotes the global optimum position corresponding to fMin
% Start updating the solutions.
%
for t = 1 : M
[ ans, sortIndex ] = sort( pFit );% Sort.
[fmax,B]=max( pFit );
worse= x(B,:);
r2=rand(1);
%%%%%%%%%%%%%5%%%%%%这一部位为发现者(探索者)的位置更新%%%%%%%%%%%%%%%%%%%%%%%%%
if(r2<0.8)%预警值较小,说明没有捕食者出现
for i = 1 : pNum %r2小于0.8的发现者的改变(1-20) % Equation (3)
r1=rand(1);
x( sortIndex( i ), : ) = pX( sortIndex( i ), : )*exp(-(i)/(r1*M));%对自变量做一个随机变换
x( sortIndex( i ), : ) = Bounds( x( sortIndex( i ), : ), lb, ub );%对超过边界的变量进行去除
fit( sortIndex( i ) ) = fobj( x( sortIndex( i ), : ) ); %就算新的适应度值
end
else %预警值较大,说明有捕食者出现威胁到了种群的安全,需要去其它地方觅食
for i = 1 : pNum %r2大于0.8的发现者的改变
x( sortIndex( i ), : ) = pX( sortIndex( i ), : )+randn(1)*ones(1,dim);
x( sortIndex( i ), : ) = Bounds( x( sortIndex( i ), : ), lb, ub );
fit( sortIndex( i ) ) = fobj( x( sortIndex( i ), : ) );
end
end
%%%%%%%%%%%%%5%%%%%%这一部位为加入者(追随者)的位置更新%%%%%%%%%%%%%%%%%%%%%%%%%
for i = ( pNum + 1 ) : pop %剩下20-100的个体的变换 % Equation (4)
A=floor(rand(1,dim)*2)*2-1;
if( i>(pop/2))%这个代表这部分麻雀处于十分饥饿的状态(因为它们的能量很低,也是是适应度值很差),需要到其它地方觅食
x( sortIndex(i ), : )=randn(1)*exp((worse-pX( sortIndex( i ), : ))/(i)^2);
else%这一部分追随者是围绕最好的发现者周围进行觅食,其间也有可能发生食物的争夺,使其自己变成生产者
x( sortIndex( i ), : )=bestXX+(abs(( pX( sortIndex( i ), : )-bestXX)))*(A‘*(A*A‘)^(-1))*ones(1,dim);
end
x( sortIndex( i ), : ) = Bounds( x( sortIndex( i ), : ), lb, ub );%判断边界是否超出
fit( sortIndex( i ) ) = fobj( x( sortIndex( i ), : ) );%计算适应度值
end
%%%%%%%%%%%%%5%%%%%%这一部位为意识到危险(注意这里只是意识到了危险,不代表出现了真正的捕食者)的麻雀的位置更新%%%%%%%%%%%%%%%%%%%%%%%%%
c=randperm(numel(sortIndex));%%%%%%%%%这个的作用是在种群中随机产生其位置(也就是这部分的麻雀位置一开始是随机的,意识到危险了要进行位置移动,
%处于种群外围的麻雀向安全区域靠拢,处在种群中心的麻雀则随机行走以靠近别的麻雀)
x( sortIndex( b(j) ), : )=bestX+(randn(1,dim)).*(abs(( pX( sortIndex( b(j) ), : ) -bestX)));
else %处于种群中心的麻雀的位置改变
x( sortIndex( b(j) ), : ) =pX( sortIndex( b(j) ), : )+(2*rand(1)-1)*(abs(pX( sortIndex( b(j) ), : )-worse))/ ( pFit( sortIndex( b(j) ) )-fmax+1e-50);
end
x( sortIndex(b(j) ), : ) = Bounds( x( sortIndex(b(j) ), : ), lb, ub );
fit( sortIndex( b(j) ) ) = fobj( x( sortIndex( b(j) ), : ) );
end
for i = 1 : pop
if ( fit( i ) < pFit( i ) )
pFit( i ) = fit( i );
pX( i, : ) = x( i, : );
end
end
end
Convergence_curve(t)=fMin;
end
% Application of simple limits/bounds
function s = Bounds( s, Lb, Ub)
% Apply the lower bound vector
% Apply the upper bound vector
J = temp > Ub;
temp(J) = Ub(J);
% Update this new move
s = temp;
%---------------------------------------------------------------------------------------------------------------------------
三、运行结果
四、matlab版本及参考文献
1 matlab版本
2014a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例(第2版)[M].电子工业出版社,2016.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社,2017.
[3]周品.MATLAB 神经网络设计与应用[M].清华大学出版社,2013.
[4]陈明.MATLAB神经网络原理与实例精解[M].清华大学出版社,2013.
[5]方清城.MATLAB R2016a神经网络设计与应用28个案例分析[M].清华大学出版社,2018.