遗传算法及其改进措施

优化算法大作业

一、题目

本文利用遗传算法，依次完成下面三个目标函数的寻优：

1Generalized Rosen brock’s valley Function

048.2048.2)1()(100)(max112221iniiiixxxxxf

2 Generalized Rastrigin's Function

12.512.5)10)2cos(10()(min112iniiixxxxf

3 Schaffer’s Function

44))(001.01(5.0)(sin5.0),(min222212222121ixxxxxxxf

二、本文思路

遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法，本文利用遗传算法分别对上述三种函数进行全局寻优，具体思路如下：

1. 编码与解码

1) 编码：假设某一参数的取值范围是[umin , umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l 种不同的编码，编码的长度越长，对应的精度越高。

 第一题变量的取值范围是[-2.048,2.048]，本文采取十位数的编码，那么精度为：

3minmax110004.412luu

 第二题变量的取值范围是[-5.12,5.12]，本文采取的是十二位数的编码，那么精度为：

3minmax210501.212luu

 第三题变量的取值范围是[-4,4]，本文采取的是十三位数的编码，那么精度为：

3minmax310442.212luu 2) 解码：假设某一个个体的编码是1221bbbbbLiii，那么对应的解码公式为：

)2(11miniliibux

2. 个体适应度评价

1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设 定个体的适应度F(X)就等于相应的目标函数值f(X)，即：

𝐹(𝑥)={𝑓(𝑥)−𝐶𝑚𝑖𝑛 𝑓(𝑥)>𝐶𝑚𝑖𝑛0 𝑓(𝑥)≤𝐶𝑚𝑖𝑛

其中minC是函数最小值估计。

2) 对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即

F(𝑥)={𝐶𝑚𝑎𝑥−𝑓(𝑥) 𝑓(𝑥)<𝐶𝑚𝑎𝑥0 𝑓(𝑥)≥𝐶𝑚𝑎𝑥

其中maxC是函数的最大值估计。

3. 复制、交叉、变异

1) 比例算子：个体被选中并遗传到下一代的概率与个体的适应度成正比，本文采取的的赌轮盘选择法选，该方法较容易实现，易于编程。

2) 交叉算子：交叉是遗传算法产生新个体的主要手段，通过交叉子代的基因值不同于父代，从而可以出现适应度更高的个体，本文采用的是单点交叉算子。

3) 变异算子：变异也是产生新个体的一种方法，对于遗传算法中二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将基因值变为1，反之，若原有的基因值为1，则变异操作将其变为0。

三、程序流程

对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：

第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；

第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；

第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；

第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；

第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；

第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。

第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。

具体程序流程图见下图所示：

图1遗传算法流程图

四、优化过程

1. 第一题

图2 Rosen brock函数图像

图3 遗传算法迭代寻优过程

程序运行结果如下：最优点函数取值9.3905)2,1(,048.22,048.21xxfxx

2. 第二题 -3-2-10123-4-20201000200030004000X: 2.048Y: -2.048Z: 38980204060801001201401601802005001000150020002500300035004000迭代次数函数值

最优解种群平均适应度种群最大适应度

图4：Rastrigin函数图像

图5：遗传算法迭代寻优过程

程序运行结果如下：最优点函数取值5731.0)2,1(,0346.020413.01xxfxx， -10-50510-10-505100204060801000204060801001201401601802004550556065707580迭代次数适应度

种群平均适应度种群最大适应度

3. 第三题

图6 Schaffer函数图像

-4-2024-4-202400.20.40.60.810204060801001201401601802000.20.30.40.50.60.70.80.91迭代次数函数值

种群平均适应度种群最大适应度图7 遗传算法迭代寻优过程

程序运行结果如下：最优点函数取值9902.0)2,1(,1210.320181.01xxfxx，

由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。

五、问题的发现与改进

1. 问题一：局部最优解

从第三题的函数图像中可以看出，该函数有无限多个局部极大值点，只有一个全局最优点1)0,0(f,此函数最导致峰周围有一圈脊，上面的取值均为0.990283。从上面的优化过程可以看出，当随机选定初始种群后，随着迭代次数的增加，种群最终都集中在了这一圈脊上，也就是寻优过程陷入了局部最优点，并没有找到函数的的最优点。对于遗传算法中的上述问题，我们采用的解决方案如下。

解决方法1：等值线法

初始种群的选取对函数能不能找到最优点有着重要的影响，本文通过分析函数的等值线缩小初始种群的随机产生范围，从而让种群朝着全局最优点进化。在Matlab下画出函数的等值线如下图：

图8 目标函数的等值线图

从图中可以看出，以中心最优点为圆心，围绕着中心点分布着多条等值线，从中心的红色区域向外到蓝色区域，目标函数值先减小再增加最后又减小，所以本文以中间红色区域到蓝色区域中选取合适的等值线截面，并在该面上随机产生初始种群，这样可以有效防止迭代陷入局部最优解。改进后的寻优结果：

-4-3-2-101234-4-3-2-101234

图9 改进后的遗传算法寻优过程

图6中的最终种群进化到了函数一圈“脊”上，但是这只是函数的局部最优点，而从图9可以清楚地看到，种群进化到最后都集中在了中心凸起点的附近，这也是函数的最大值点，可见改进后的遗传算法有效的解决了局部最优点的问题，顺利找到了函数的全局最优解。

解决方法2：模拟退火算法

模拟退火算法是模仿了自然界退火现象，利用了物理中固体物质的退火过程与一般问题的相似性，从某一初始温度开始，伴随着温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解，它能有效的克服寻优陷入局部最小值的优化方法。其具体算法原理本文不详述，只给出采用模拟退火算法的实现过程如下图所示： -4-2024-4-202400.20.40.60.81

图10 模拟推过算法实现过程

相关参数选择为：

初始温度Temperature=30

步长因子StepFactor=0.002

容差Tolerance=1e-7

马可夫链长度MarkovLength=1000

衰减参数DecayScale=0.95

程序运行结果为（程序见附录）：

最优点函数取值0000.1)2,1(,04-1.0610e205-7.2448e 1xxfxx，

寻优过程如下：

图11 模拟退火算法的寻优过程

从上面的寻优结果可以看出，模拟退火算法解决了本例中遗传算法寻优陷入局部最优解的问题，最终找到了Schaffer Function函数的全局唯一最优解1)0,0(f。

问题二：寻优速度

基本的遗传算法中产生优良个体的主要手段是同过交叉重组，但这样并不能保证产生新个体的速度，即迭代寻优的速度很慢，考虑到为了保证较高的精度，本文的基因编码分别是十位、十二位与十三位，那么对于二元函数，染色体的长度就是二十、二十四与二十六，因此可以在交叉重组时，将较长的染色体分为若干段，并对每一小段进行两两配对交叉重组，这样相当于每个染色体在一次的迭代过程中参与了几次交叉重组，大大加快了新个体的产生速度。本文即将染色体分为了两段，进行交叉重组（程序见附录），加快了寻优速度。

六 程序附录

1 遗传算法主程序

%%%%%遗传算法主程序%%%%%

clear %清除普通变量，不清除全局变量

clf

popsize=80; %种群大小

chromlength=26; %字符串长度（个体染色体长度）

pc=0.6; 05010015020025000.10.20.30.40.50.60.70.80.91模拟退火寻优过程迭代次数寻优过程pm=0.001;

% global Numv=2;

pop=initpop(popsize,chromlength)

for i=1:200 %200为迭代次数

objvalue=calobjvalue(pop); %计算函数值

fitvalue=calfitvalue(objvalue); %计算个体适应度

avefitvalue(i)=sum(fitvalue)/popsize;

newpop=selection(pop,fitvalue);% 选择

newpop=crossover_multiv(newpop,pc);

newpop=mutation(newpop,pm);

[bestindividual,bestfit]=best(pop,fitvalue);

z(i)=max(bestfit) %个体适应度的最大值

n(i)=i;

x(i)=decodechrom(bestindividual,1,chromlength/2)*8/8191-4 %将二进制的数转换为十进制数然后归一化到0-10之间

y(i)=decodechrom(bestindividual,(chromlength/2+1),chromlength/2)*8/8191-4

pop=newpop;

end

figure(1);

i=1:1:200;