优化算法粒子群算法遗传算法禁忌算法对比
目录
优化算法の粒子群算法、遗传算法、禁忌算法对比
0、优化算法
优化算法是一种根据概率按照固定步骤寻求问题的最优解的过程。常见的优化算法有最传统的梯度下降法(Gradient Descent)，在自然特性的基础上模拟个体种群的适应性的遗传算法（Genetic Algorithm，GA）和粒子群算法（Particle Swarm Optimization，PSO），收敛速度较快的牛顿法（Newton’s method）及其在牛顿法的基础上使用正定矩阵来近似Hessian矩阵逆的拟牛顿法（Quasi Newton method），还有以亚启发式随机搜索的禁忌算法（Tabu Search）。
1、粒子群算法
粒子群中的每一个粒子都代表一个问题的可能解，通过粒子个体的简单行为，群体内的信息交互实现问题求解的智能性。算法那中每个粒子可视为N维搜索空间中的一个搜索个体，粒子的当前位置即为对应优化问题的一个候选解，粒子的飞行过程即为该个体的搜索过程。粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整。粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向，每个粒子单独搜寻的最优解叫做个体极值，粒子群中最优的个体极值作为当前全局最优解。不断迭代，更新速度和位置。最终得到满足终止条件的最优解。
目标函数z=y sin(2 pi x)+x cos(2 pi y)
%% I. 清空环境%二元函数
%https://blog.csdn.net/weixin_44897776/article/details/113686831
clc
clear
%% II. 绘制目标函数曲线图
rand('state',3);
figure(1);
lbx=-3;ubx=3; %函数自变量x范围【-3,3】
lby=-3;uby=3; %函数自变量y范围【-3,3】
ezmesh('y*sin(2*pi*x)+x*cos(2*pi*y)',[lbx,ubx,lby,uby],100); %画出函数曲线
hold on;
%% III. 参数初始化
c1 = 1.49445;%c1和c2：是学习因子，通常c1=c2=2
c2 = 1.49445;
ws=0.9;%w惯性权重，体现粒子继承先前的速度的能力
we=0.4;%一般start=0.9 end=0.4时算法性能最好，迭代初期惯性大有利于全局搜索，迭代后期惯性小有利于局部搜索
maxgen = 50; % 进化次数
sizepop = 80; %种群规模
Vmax = 1; %速度的范围，超过则用边界值。
Vmin = -1;
popmax = 3; %个体的变化范围
popmin = -3;
%定义适应度函数
%% IV. 产生初始粒子和速度
for i = 1:sizepop
% 随机产生一个种群
pop(i,:) = 3*rands(1,2); %初始种群粒子位置
V(i,:) = rands(1,2); %初始化速度
% 计算适应度
fitness(i) = fun1(pop(i,:));
end
%% V. 个体极值和群体极值
[bestfitness,bestindex] = max(fitness);
gbest = pop(bestindex,:); %全局最佳
fitnessgbest = bestfitness; %全局最佳适应度值
pbest = pop; %个体最佳
fitnesspbest = fitness; %个体最佳适应度值
%% VI. 迭代寻优
tic
for i = 1:maxgen
% tic
w=ws-(ws-we)*(i/maxgen);
for j = 1:sizepop
% 速度更新
V(j,:) = w*V(j,:) + c1*rand*(pbest(j,:) - pop(j,:)) + c2*rand*(gbest - pop(j,:));
V(j,find(V(j,:)>Vmax)) = Vmax;
V(j,find(V(j,:)<Vmin)) = Vmin;
% 种群更新
pop(j,:) = pop(j,:) + V(j,:);
pop(j,find(pop(j,:)>popmax)) = popmax;
pop(j,find(pop(j,:)<popmin)) = popmin;
% 适应度值更新
fitness(j) = fun1(pop(j,:));
end
for j = 1:sizepop
% 个体最优更新
if fitness(j) > fitnesspbest(j)
pbest(j,:) = pop(j,:);
fitnesspbest(j) = fitness(j);
end
% 群体最优更新
if fitness(j) > fitnessgbest
gbest = pop(j,:);
fitnessgbest = fitness(j);
end
end
Q(i) = fitnessgbest;
% toc
end
toc
%% VII. 输出结果并绘图
[gbest fitnessgbest];
plot3(gbest(1),gbest(2),fitnessgbest,'r*')
fprintf(['最优解:\nX=',num2str(gbest(1)),'\nY=',num2str(gbest(2)),'\nZ=',num2str(fitnessgbest),'\n'])
figure(2)
plot(Q)
title('最优个体适应度','fontsize',12);
xlabel('迭代次数','fontsize',12);ylabel('适应度','fontsize',12);
function z = fun1(x)
z=x(2)*sin(2*pi*x(1))+x(1)*cos(2*pi*x(2));
end算法迭代曲线
2、遗传算法
遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成，每个个体实际上是染色体带有特征的实体。在初代种群产生之后，遗传算法按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。
目标函数z=y sin(2 pi x)+x cos(2 pi y)
%%二维GA matlab智能算法第二章example2
clc
clear all
close all
rand('state',2);
%% 画出函数图
figure(1);
lbx=-3;ubx=3; %函数自变量x范围【-2,2】
lby=-3;uby=3; %函数自变量y范围【-2,2】
ezmesh('y*sin(2*pi*x)+x*cos(2*pi*y)',[lbx,ubx,lby,uby],100); %画出函数曲线
hold on;
%% 定义遗传算法参数
NIND=40; %个体数目
MAXGEN=50; %最大遗传代数
PRECI=20; %变量的二进制位数
GGAP=0.95; %代沟
px=0.7; %交叉概率
pm=0.01; %变异概率
trace=zeros(3,MAXGEN); %寻优结果的初始值
FieldD=[PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1]; %区域描述器
Chrom=crtbp(NIND,PRECI*2); %初始种群
%% 优化
gen=0; %代计数器
XY=bs2rv(Chrom,FieldD); %计算初始种群的十进制转换
X=XY(:,1);Y=XY(:,2);
ObjV=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算目标函数值
tic
while gen<MAXGEN
% tic
FitnV=ranking(-ObjV); %分配适应度值
SelCh=select('sus',Chrom,FitnV,GGAP); %选择
SelCh=recombin('xovsp',SelCh,px); %重组
SelCh=mut(SelCh,pm); %变异
XY=bs2rv(SelCh,FieldD); %子代个体的十进制转换
X=XY(:,1);Y=XY(:,2);
ObjVSel=Y.*sin(2*pi*X)+X.*cos(2*pi*Y); %计算子代的目标函数值
[Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群
XY=bs2rv(Chrom,FieldD);
gen=gen+1; %代计数器增加
%获取每代的最优解及其序号，Y为最优解,I为个体的序号
[Y,I]=max(ObjV);
trace(1:2,gen)=XY(I,:); %记下每代的最优值
trace(3,gen)=Y; %记下每代的最优值
% toc
end
toc
plot3(trace(1,:),trace(2,:),trace(3,:),'bo'); %画出每代的最优点
grid on;
plot3(XY(:,1),XY(:,2),ObjV,'bo'); %画出最后一代的种群
hold off
%% 画进化图
figure(2);
plot(1:MAXGEN,trace(3,:));
grid on
xlabel('遗传代数')
ylabel('解的变化')
title('收敛过程')
bestZ=trace(3,end);
bestX=trace(1,end);
bestY=trace(2,end);
fprintf(['最优解:\nX=',num2str(bestX),'\nY=',num2str(bestY),'\nZ=',num2str(bestZ),'\n'])算法迭代曲线
3、禁忌算法
禁忌搜索算法首先确定一个初始可行解，确定初始可行解后，定义可行解的领域移动集，然后从领域移动集中挑选一个能改进当前解得移动集，再从新的解开始，反复搜索。如果领域移动中只接受比当前解好的解，搜索就可能陷入循环的危险。为了避免陷入循环和局部最优，构造一个短期循环记忆表，即禁忌表，禁忌表中存放刚刚进行过的领域移动，这些移动被称为禁忌移动。对于当前的移动，在以后的T次循环中都是禁止的，以避免回到原先的解，T次以后释放该移动。禁忌表是一个循环表，搜索过程中被循环的修改，使禁忌表始终保持这T个移动。
目标函数z=y sin(2 pi x)+x cos(2 pi y)
%%%%%%%%%%%%%%%%禁忌搜索算法求函数极值问题%%%%%%%%%%%%%%%%%%%
clear all; %清除所有变量
close all; %清图
clc; %清屏
xu=3; %上界
xl=-3; %下界
rand("state",3);
% L=randint(1,1,[5 11]); %禁忌长度取5,11之间的随机数
L=randi([5 11],1,1); %禁忌长度取5,11之间的随机数
Ca=5; %邻域解个数
Gmax=50; %禁忌算法的最大迭代次数；
w=1; %自适应权重系数
tabu=[]; %禁忌表
x0=rand(1,2)*(xu-xl)+xl; %随机产生初始解
bestsofar.key=x0; %最优解
xnow(1).key=x0; %当前解
%%%%%%%%%%%%%%%%最优解函数值，当前解函数值%%%%%%%%%%%%%%%%%
bestsofar.value=func2(bestsofar.key);
xnow(1).value=func2(xnow(1).key);
g=1;
while g<Gmax
x_near=[]; %邻域解
w=w*0.998;
for i=1:Ca
%%%%%%%%%%%%%%%%%%%%%产生邻域解%%%%%%%%%%%%%%%%%%%%
x_temp=xnow(g).key;
x1=x_temp(1);
x2=x_temp(2);
x_near(i,1)=x1+(2*rand-1)*w*(xu-xl);
%%%%%%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%边界吸收%%%%%%%%%%%%%%%%%%%%%
if x_near(i,1)<xl
x_near(i,1)=xl;
end
if x_near(i,1)>xu
x_near(i,1)=xu;
end
x_near(i,2)=x2+(2*rand-1)*w*(xu-xl);
%%%%%%%%%%%%%%%%%边界条件处理%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%边界吸收%%%%%%%%%%%%%%%%%%%%%
if x_near(i,2)<xl
x_near(i,2)=xl;
end
if x_near(i,2)>xu
x_near(i,2)=xu;
end
%%%%%%%%%%%%%%计算邻域解点的函数值%%%%%%%%%%%%%%%%%%%
fitvalue_near(i)=func2(x_near(i,:));
end
%%%%%%%%%%%%%%%%%%%%最优邻域解为候选解%%%%%%%%%%%%%%%%%%%
temp=find(fitvalue_near==max(fitvalue_near));
candidate(g).key=x_near(temp,:);
candidate(g).value=func2(candidate(g).key);
%%%%%%%%%%%%%%候选解和当前解的评价函数差%%%%%%%%%%%%%%%%%%
delta1=candidate(g).value-xnow(g).value;
%%%%%%%%%%%%%%候选解和目前最优解的评价函数差%%%%%%%%%%%%%%%
delta2=candidate(g).value-bestsofar.value;
%%%%%候选解并没有改进解，把候选解赋给下一次迭代的当前解%%%%%%
if delta1<=0
xnow(g+1).key=candidate(g).key;
xnow(g+1).value=func2(xnow(g).key);
%%%%%%%%%%%%%%%%%%%%%更新禁忌表%%%%%%%%%%%%%%%%%%%%%%%
tabu=[tabu;xnow(g+1).key];
if size(tabu,1)>L
tabu(1,:)=[];
end
g=g+1; %更新禁忌表后，迭代次数自增1
%%%%%%%如果相对于当前解有改进，则应与目前最优解比较%%%%%%%%%%
else
if delta2>0 %候选解比目前最优解优
%%%%%%%%%%把改进解赋给下一次迭代的当前解%%%%%%%%%%%%
xnow(g+1).key=candidate(g).key;
xnow(g+1).value=func2(xnow(g+1).key);
%%%%%%%%%%%%%%%%%%%%更新禁忌表%%%%%%%%%%%%%%%%%%%%%
tabu=[tabu;xnow(g+1).key];
if size(tabu,1)>L
tabu(1,:)=[];
end
%%%%%%%%把改进解赋给下一次迭代的目前最优解%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%包含藐视准则%%%%%%%%%%%%%%%%%%%%%%%
bestsofar.key=candidate(g).key;
bestsofar.value=func2(bestsofar.key);
g=g+1; %更新禁忌表后，迭代次数自增1
else
%%%%%%%%%%%%%%%判断改进解时候在禁忌表里%%%%%%%%%%%%%%%
[M,N]=size(tabu);
r=0;
for m=1:M
if candidate(g).key(1)==tabu(m,1)...
& candidate(g).key(2) == tabu(m,1)
r=1;
end
end
if r==0
%%改进解不在禁忌表里，把改进解赋给下一次迭代的当前解
xnow(g+1).key=candidate(g).key;
xnow(g+1).value=func2(xnow(g+1).key);
%%%%%%%%%%%%%%%%%%%%%更新禁忌表%%%%%%%%%%%%%%%%%%
tabu=[tabu;xnow(g).key];
if size(tabu,1)>L
tabu(1,:)=[];
end
g=g+1; %更新禁忌表后，迭代次数自增1
else
%%%如果改进解在禁忌表里，用当前解重新产生邻域解%%%%%
xnow(g).key=xnow(g).key;
xnow(g).value=func2(xnow(g).key);
end
end
end
trace(g)=func2(bestsofar.key);
end
bestsofar %最优变量及最优值
figure
plot(trace);
xlabel('迭代次数')
ylabel('目标函数值')
title('搜索过程最优值曲线')
%该脚本应命名为func2.m
function y=func2(x)
y = x(2)*sin(2*pi*x(1))+x(1)*cos(2*pi*x(2));
end迭代曲线
以上三种算法的优劣分析
以下分别对粒子群算法、遗传算法、禁忌算法的特征进行分析。
粒子群算法是一类非确定算法，其优点在于有更多的机会得到全局最优解，且粒子群算法具有自组织和进化性以及记忆功能，所有粒子都保存优解得相关信息。且粒子群算法还具备稳健性，即在不同条件和环境下都实用有效。但粒子群算法的数学理论基础还不够牢固，算法收敛性还有待斟酌。
遗传算法直接以目标函数作为搜索信息，仅仅使用适应度函数值来度量个体的优劣程度。因此遗传算法有着高度的优越性。另一方面由于遗传算法的群体搜索特性，可以避免在多峰分布搜索空间进行搜索易陷入单峰极值的问题。但遗传算法的效率通常低于其它优化算法，且容易出现过早收敛的现象。
禁忌算法主要特点是在搜索开始阶段解的质量提高很快，随着搜索过程的继续，解得质量提高速度逐渐放缓，甚至在很长的搜索阶段内解得质量没有太大的提高，适合中小规模的NP问题求解，整体效率比较均衡。