遗传算法实例详解：从编码到收敛性分析
遗传算法实例详解：从编码到收敛性分析
遗传算法作为一种启发式搜索算法，在优化问题中有着广泛的应用。本文通过一个具体的优化问题实例，详细介绍了遗传算法的各个关键步骤，包括编码、适应函数定义、选择、交叉、变异等，帮助读者深入理解遗传算法的工作原理和实现细节。
序言
上篇《优化算法：遗传算法》主要讲述了遗传算法基本原理、相关概念和具体步骤。
本篇通过一个简单的示例更好的理解遗传算法。
1.例题与算法流程
设
，求
。
遗传算法的整个过程如下：
2.具体流程
1）编码和产生初始群体
第一步要确定编码的策略，也就是说如何把-1~2这个区间内的数用计算机语言表示出来。
编码就是表现型的基因型的映射，编码时要注意以下三个原则。
完备性:问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色体位串)的表现型(简单讲就是编码方案能够表示问题解空间中的所有可能解)。
健全型:GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解(简单讲就是编码方案中的每个编码都对应问题解空间中的一个合法解)。
非冗余性:染色色体和潜在解必须一一对应。
这里通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0,1}二进制串。当然，串长取决于求解的精度。如果要设定求解精度到六位小数，由于区间长度为2-(-1)=3，则必须将闭区间[-1,2]分为
等分。因为
，所以编码的二进制串至少需要 22 位。
将一个二进制串
转化为区间[-1,2]对应的实数值很简单,只需采取以下两步
(1)将一个二进制串
代表的二进制数化为10进制数，即
(2)
对应的区间[-1,2]的实数为
例如，一个二进制串 a=<1000101110110101000111>表示实数 0.637197。
二进制串<0000000000000000000000>，<111111111111111111111>，分别表示区同的两个端点值-1和2。
利用这种方法就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则。
随机产生一个个体数为4个的初始群体:
pop(1)={
<1101011101001100011110>， %a1
<1000011001010001000010>，%a2
<0001100111010110000000>， %a3
<0110101001101110010101>,} %a4
化成十进制的分数分别为
pop(1)={1.523032.0.574022,-0.697235,0.247238}
接下来解决每个染色体个体的适应值问题
2)定义适应函数和适应值
由于给定的目标函数
在[-1,2]的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应适应值增大的方向，也为以后计算各个体的入选概率打下基础。
定义适应函数
，采用下述方法，即
式中：
即可以是特定的输入值，也可以是当前所有代或最近K代中
的最小值，这里为了方便计算，将采用一个特定的输入值。
取
，
当
时适应函数
；
当
时适应函数
。
根据初始群体pop(1)，先计算目标函数值：
f[pop(1)]={1.226437,1.318543,-1.380607.0.933350}
再根据定义的适应函数计算适应值：
g[pop(1)]={2.226437,2.318543,0,1.933350}
3)确定选择标准
用适应值的比例作为选择的标准，得到的每个个体的适应值比例叫做入选概率。其
计算公式如下。
对于给定的规模为n的群体
，个体
的适应值为
,则其入选的概率为：
由上述给出的群体，可以计算出各个个体的入选概率。
首先可得
，然后分别用四个个体的适应值除以
，得
P(a1)=2226437/6.478330=0.343675 % a1
P(a2)=2.318543/6.478330=0.357892 %a2
P(a3)=0/6.478330=0 %a3
P(a4)=1.933350/6.478330=0.298433 %a4
4)产生种群
计算完入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群,得到与原群体大小同样的种群。(精英产生精英法)
将个体适应度大小映射为概率进行复制:适应度高的个体有更大概率复制，且复制的份数越多。(轮盘赌法)
这里按精英产生精英法由初始群体的入选概率淘汰掉a3，再加入a2，补足成与群体同样大小的种群，得到newpop(1)如下:
newpop(1 )={
<1101011101001100011110>% a1
<1000011001010001000010>% a2
<1000011001010001000010>%a3
<0110101001101110010101>}%a4
5)交叉
交叉是一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组组成新的群体。
把之前得到的 newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉(可以在｣協辜任一位进行交叉)。
<110101110 1001100011110> <1101011101010001000010>
交叉得
<100001100 1010001000010> <1000011001001100011110>
<10000110010100 01000010> <1000011001010010010101>
交叉得
<01101010011011 10010101> <0110101001101101000010>
通过交叉又得到四个新个体，得到新的群体jchpop(1)如下：
jchpop(1 )={
<1101011101010001000010>
<1000011001001100011110>
<1000011001010010010101>.
<0110101001101101000010 >
这里简单采用单点交叉，还有多点交叉的方法。
6)变异
变异是通过一个小概率改变染色体位串上的某个基因
现把刚得到的 jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到的新群体pop(2)如下:
pop(2)={
<1101011101010001000010>.
<1000011001001100011110>.
<1000011011010010010101>
<0110101001101101000010 >}
然后重复上述的选择、交叉、变异直到满足终止条件为止。
7)终止条件
遗传算法的终止条件有两类常见条件。
采用设定最大(遗传)代数的方法，一般可设定为50代，此时就可能得出最优解。此种方法简单易行，但可能不是很精确。
根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来就控制。
3.遗传算法的收敛性
遗传算法作为一种搜索算法，通过对这些操作的适度设计和运行，可以实现兼顾全局搜索和局部搜索的所谓的均衡搜索，具体实现如下图：
应该指出的是，遗传算法虽然可以实现均衡搜索，但该算法的全局优化收敛性的理论分析尚待解决。这里直接给出几点定律：
若变异概率
，交叉概率
，则基本 遗传算法不收敛到全局最优解。如果改进基本遗传算法按交叉、变异、种群选取之后更新当前最优染色体(解)的进化循环过程，则收敛于全局最优。
如果改进基本遗传算法按交叉、变异、种群选取之前更新当前最优染色体(解)的进化循环过程，则收敛于全局最优。
注：本篇内容均为对《MATLAB建模与仿真》(周品 赵新芬 编著，国防工业出版社)摘录与个人归纳总结，如需要更加详细了解，可阅读原书“第16章 部分智能优化算法”部分。