4 MATLAB与智能优化算法
写在最前
本栏参考《智能优化算法及其MATLAB实例（第二版）》包子阳 余继周 杨彬 编著
4.1 遗传算法
4.1.1遗传算法的基本概念
简单而言，遗传算法使用群体搜索技术，将种群代表一组解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代种群。并逐步使种群进化到包含近似最优解的状态。
遗传算法中的术语有一般如下：
群体和个体-----群体是生物进化过程中的一个集团，表示可行解集。个体是组成群体的单个生物体，表示可行解。
染色体和基因-----染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。基因是控制生物体某种性状(即遗传信息)的基本单位，表示可行解编码的分量。
遗传编码-----遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码，十进制编码等等。
适应度-----即生物群体中个体适应生存环境的能力。在遗传算法中，用来评价个体优劣的数学函数，称为个体的适应度函数。遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义城可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有：目标函数映射成适应度函数，基于序的适应度函数等。
4.1.2 遗传算法的操作和流程
遗传算法中最优解的搜索过程也模仿生物的遗传进化的过程，使用所谓的遗传算子来实现，即选择算子、交叉算子和变异算子。
（1）选择算子：根据个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些代良的个体遗传到作代群体P(1+t)中。
其中“轮盘赌”选择法是遗传算法中最早提出的种选择方法。它是一种基于比例的选择，利用各个个体适应度所占比例的大小来决定其子孙保留的可能性。若某个个体i的适应度为fi，种群大小为NP,则它被选取的概率表示为pi=fi/(f1+f2+f3+…+fNP)。个体适应度越大，则其被选择的机会也越大，反之亦然。
（2）交叉算子：将群体P(t)中选中的各个个体随机搭配，对每一对个体。以某一概率(交叉概率Pc)交换它们之间的部分染色体。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉操作一般分为以下几个步骤：首先，从交配池中随机取出要交配的一对个体；然后，根据位串长度L，对要交配的一对个体，随机选取[1,L-1]中的一个或多个整数k作为交叉位置；最后，根据交叉概率Pc实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。
(3)变异算子：对群体中的每个个体，以某一 概率(交异概率Pm)将某一个或某些基因座上的基因值改变为其他的等位基因值。根据个体编码方式的不同，变异方式有:实值变异、二进制交异。对于二进制的变异，对相应的基因值取反；对于实值的变异，对相应的基因值用取值范围内的其他随机值整代。变异操作的一般步骤为：首先，对种群中所有个体按事先设定的变异概率判断是否进行变异；然后，对进行变异的个体随机选择变异位置进行变异。
遗传算法的运算流程 如图所示。具体步骤如下:
(1)初始化。设置进化代数计数器g=0，设置最大进化代数G，随机生成NP个个体作为初始群体P(0)。
(2)个体评价。计算群体P(t)中各个个体的适应度。
(3)选择运算。将选择算子作用于群体，根据个体的适应度，按照一定的规则或方法，选择一些优良个体遗传到下一代群体。
(4)交叉运算。将交叉算子作用于群体，对选中的成对个体，以某概率交换它们之间的部分染色体，产生新的个体
。
(5)变异运算。将变异算子作用于群体，对选中的个体，以某概率改变某一个或某些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)，计算适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。
(6)终止条件判断：如g≤G则g=g+1转到步骤(2)，若g>G则进化过程中所得到的具有最大适应度的个体作为最优解输出，中止计算。
4.1.3遗传算法实例
例如求解y=x+10sin(5x)+7cos(4x)在X=[0,10]上的极大值。
clear; %清除所有变量
close all; %清图
clc; %清屏
NP=50; %种群数量
L=20; %二进制数串长度
Pc=0.8; %交叉率
Pm=0.1; %变异率
G=100; %最大遗传代数
Xs=10; %上限
Xx=0; %下限
f=randi([0,1],NP,L); %随机获得初始种群
for k=1:G
%%%%%%%%%%%%将二进制解码为定义域范围内十进制%%%%%%%%%%%%%%
for i=1:NP
U=f(i,:);
m=0;
for j=1:L
m=U(j)*2^(j-1)+m;
end
x(i)=Xx+m*(Xs-Xx)/(2^L-1);
Fit(i)= x(i)+10*sin(5*x(i))+7*cos(4*x(i));
end
maxFit=max(Fit); %最大值
minFit=min(Fit); %最小值
rr=find(Fit==maxFit);
fBest=f(rr(1,1),:); %历代最优个体
xBest=x(rr(1,1));
Fit=(Fit-minFit)/(maxFit-minFit); %归一化适应度值
%%%%%%%%%%%%%%%%%%基于轮盘赌的复制操作%%%%%%%%%%%%%%%%%%%
sum_Fit=sum(Fit);
fitvalue=Fit./sum_Fit;
fitvalue=cumsum(fitvalue);
ms=sort(rand(NP,1));
fiti=1;
newi=1;
while newi<=NP
if (ms(newi))<fitvalue(fiti)
nf(newi,:)=f(fiti,:);
newi=newi+1;
else
fiti=fiti+1;
end
end
%%%%%%%%%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%%%%%%%
for i=1:2:NP
p=rand;
if p<Pc
q=randi([0,1],L,1);
for j=1:L
if q(j)==1;
temp=nf(i+1,j);
nf(i+1,j)=nf(i,j);
nf(i,j)=temp;
end
end
end
end
%%%%%%%%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%%%%%%%%%%%
i=1;
while i<=round(NP*Pm)
h=randi([1,NP],1,1); %随机选取一个需要变异的染色体
for j=1:round(L*Pm)
g=randi([1,L],1,1); %随机需要变异的基因数
nf(h,g)=~nf(h,g);
end
i=i+1;
end
f=nf;
f(1,:)=fBest; %保留最优个体在新种群中
trace(k)=maxFit; %历代最优适应度
end
xBest; %最优个体
figure
plot(trace)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')
其中函数曲线和遗传算法迭代曲线为：