2.5 遗传算法的应用实例

例2-1 利用标准遗传算法求解函数最大值问题。已知 x ∈[0，10]，试求一元连续函数 f （ x ）=2 x +9sin 4 x +5cos3 x 的最大值。

解： 利用下面的MATLAB程序，绘制 f （ x ）的图形，如图2-7所示。由图可见，该函数有多个极大值，且存在唯一的最大值。

函数的自变量采用二进制编码方式，编码长度为20。为了保证目标函数均为正值，采用目标函数值加上20作为个体评价的适应度函数值。种群更新采用新种群个体与原种群个体“一对一”方式的贪婪竞争选择。利用标准遗传算法的求解过程如下。

（1）初始化算法参数：初始化染色体的种群数量为NP=50，染色体的编码长度为 N =20，自变量取值上限为 X _max =10，取值下限为 X _min =0，交叉概率为 P _c =0.8，变异概率为 P _m =0.2，最大进化代数为 G =200。

（2）随机初始化种群的位置：采用随机产生“0”和“1”的方法，生成NP个长度为 N 的二进制编码个体作为种群的初始位置。将二进制编码转换为实数，计算所有个体的适应度函数值。

（3）判断是否达到了最大进化代数：若是，则结束搜索过程，转到步骤（10）；若否，则继续进行下面的步骤。

（4）基于“轮盘赌”的复制操作：利用个体的适应度函数值构建选择概率，采用“轮盘赌”的方法从种群中选取NP个个体作为父辈个体。

（5）基于概率的交叉操作：将父辈个体按照顺序两个一组进行配对，产生rand ₁ ∈[0，1]内的均匀分布随机数，如果rand ₁ ＜ P _c ，则该组两个父辈个体进行交叉操作。交叉方法为对每个基因位的二进制编码，产生rand ₂ ∈[0，1]内的均匀分布随机数，如果rand ₂ ＜0.3，则两个父辈个体同一基因位的编码互换。

（6）基于概率的变异操作：对交叉操作后的每一个个体，产生rand ₃ ∈[0，1]内的均匀分布随机数，如果rand ₃ ＜ P _m ，则将该个体进行变异操作。变异方法为对每个基因位的二进制编码，产生rand ₄ ∈[0，1]内的均匀分布随机数，如果rand ₄ ＜0.3，则对该基因位的编码进行逻辑非操作。

（7）计算所有新个体的适应度函数值：将遗传操作得到新个体的二进制编码转换为实数，计算所有新个体的适应度函数值。

（8）利用贪婪竞争选择更新种群：新个体与原个体进行“一对一”方式的贪婪竞争选择，如果新个体的适应度函数值大于原个体的适应度函数值，则用新个体的位置及其适应度函数值替代原个体的适应度函数值；否则，保持原个体的位置及其适应度函数值不变。

（9）记录最优个体的位置及其目标函数值：找到种群中适应度函数值最大的个体，将其适应度函数值转换为目标函数值，记录最优个体的位置及其目标函数值。转到步骤（3）。

（10）输出优化结果：输出函数取得最大值的位置、函数的最大值和最优个体的目标函数值进化曲线。

程序每次运行结果会有差异。某次优化结果为：在 x =8.2886处，函数取得最大值为 f （ x ）=30.2739，相应最优个体的目标函数值进化曲线如图2-8所示。

MATLAB参考源程序如下：

例2-2 利用遗传算法求解函数最小值问题。已知 N =10， x _n ∈[-20，20]，试求多元函数 的最小值。

解： 该函数在 X =[0，0，…，0]处，存在唯一的最小值 f （ X ）=0。函数的自变量采用实数编码方式，编码长度与问题维数相同。由于求解问题为最小值优化问题，且函数的最大值为4000，因此用于个体评价的适应度函数值采用4000减去目标函数值来表示，将求解问题转换为最大值优化问题。选择操作采用按照适应度函数值由大到小对种群个体进行排序，用序号为偶数的个体与君主个体（最优个体）配对的方法构建父辈个体。交叉操作采用依据概率进行基因位互换的方式。变异操作采用依据概率个体基因位值在个体向量中负的绝对值最大分量值到正的绝对值最大分量值范围内产生的随机数替代的方式，而不采用在搜索范围内取随机数替代的方式，这种变异操作具有一定的自适应性，对个体向量的破坏作用小，能够大大提高求解精度。种群更新采用新群体与原种群混合群体竞争选择方式。利用遗传算法的求解过程如下。

（1）初始化算法参数：初始化染色体的种群数量为NP=100，染色体的编码长度为 N =10，自变量取值上限为 X _max =20，自变量取值下限为 X _min =-20，交叉概率为 P _c =0.8，变异概率为 P _m =0.1，最大进化代数为 G =100。

（2）随机初始化种群的位置：采用在搜索范围内产生随机数的方法，生成NP个 N 维实数编码个体作为种群的初始位置，计算所有个体的适应度函数值，按照适应度函数值从大到小对种群个体进行排序，记录君主个体。

（3）判断是否达到了最大进化代数：若是，则结束搜索过程，转到步骤（10）；若否，则继续进行下面的步骤。

（4）父辈个体配对方法：建立一个新种群，将序号为奇数的个体设置为上一代种群中的君主个体，序号为偶数的个体设置为上一代种群排序后序号为偶数的个体。

（5）基于概率的交叉操作：将父辈个体按照顺序两个一组进行配对，产生rand ₁ ∈[0，1]内的均匀分布随机数，如果rand ₁ ＜ P _c ，则对该组两个父辈个体进行交叉操作。交叉方法为对每个基因位的实数值，产生rand ₂ ∈[0，1]内的均匀分布随机数，如果rand ₂ ＜0.5，则对两个父辈个体同一基因位的实数值互换。

（6）基于概率的变异操作：对交叉操作后的每一个个体，找到自身向量中绝对值最大的分量值，产生rand ₃ ∈[0，1]内的均匀分布随机数，如果rand ₃ ＜ P _m ，则对该个体进行变异操作。变异方法为对每个基因位的实数值，产生rand ₄ ∈[0，1]内的均匀分布随机数，如果rand ₄ ＜0.5，则在负的绝对值最大分量值到正的绝对值最大分量值范围内产生随机数，替代该基因位的实数值。

（7）计算所有新个体的适应度函数值。

（8）利用群体竞争选择更新种群：将所有新个体与原种群个体混合，按照适应度函数值由大到小进行排序，选取前NP个个体作为下一代种群，保持种群数量不变。

（9）记录最优个体的位置及其目标函数值：找到种群中适应度函数值最大的个体，将其适应度函数值转换为目标函数值，记录最优个体的位置及其目标函数值。转到步骤（3）。

（10）输出优化结果：输出函数取得最小值的位置、函数的最小值和最优个体的目标函数值进化曲线。

程序每次运行结果会有差异。某次优化结果为：在 X =[-2.1119×10 ^-7 ，-1.1547×10 ^-9 ，1.9475×10 ^-7 ，1.4652×10 ^-7 ，-3.7710×10 ^-8 ，-5.7991×10 ^-9 ，4.2631×10 ^-8 ，8.2554×10 ^-8 ，1.4169×10 ^-7 ，2.1604×10 ^-7 ]处，函数取得的最小值为 f （ X ）=0，相应最优个体的目标函数值进化曲线如图2-9所示。

MATLAB参考源程序如下：

例2-3 利用遗传算法求解0-1背包问题。有 N =20件物品和一个容量为 C =878的背包，每件物品的体积和价值如表2-2所示。选取一些物品装入背包，要求背包内物品的总体积不超过背包的容量，且物品的总价值最大，求解最佳装包方案，需要确定将哪些物品装入背包。

解： 问题的自变量采用二进制编码方式，编码长度和物品件数相同，每个染色体编码的位置和物品的序号相对应，“1”表示将该物品放入背包，“0”表示不将该物品放入背包。采用带有惩罚性质的目标函数构建用于个体评价的适应度函数，具体形式为

式中，fit（ X _i ）为个体 X _i 的适应度函数； f （ X _i ）为选择物品的总价值； g （ X _i ）为选择物品的总体积； f _p （ X _i ）为惩罚价值，其定义为

式中， F 为惩罚系数。

利用遗传算法的求解过程如下。

（1）初始化算法参数：初始化染色体的种群数量为NP=100，染色体的编码长度为 N =20，背包容量为 C =878，交叉概率为 P _c =0.8，变异概率为 P _m =0.2，惩罚系数为 F =3，最大进化代数为 G =500。

（2）随机初始化种群的位置：采用随机产生“0”和“1”的方法，生成NP个长度为 N 的二进制编码个体作为种群初始位置，计算所有个体的适应度函数值。记录最优个体的位置及其适应度函数值。

（3）判断是否达到了最大进化代数：若是，则结束搜索过程，转到步骤（10）；若否，则继续进行下面的步骤。

（4）基于“轮盘赌”的复制操作：利用个体的适应度函数值构建选择概率，采用“轮盘赌”的方法从种群中选取NP个个体作为父辈个体。

（5）基于概率的交叉操作：将父辈个体按照顺序两个一组进行配对，产生rand ₁ ∈[0，1]内的均匀分布随机数，如果rand ₁ ＜ P _c ，则对该组两个父辈个体进行交叉操作。交叉方法为随机产生两个不相同的位置 p ， q ∈[1， N ]，且 p ≤ q ，互换两个交叉个体位置[ p ， q ]部分编码。

（6）基于概率的变异操作：对交叉操作后的每一个个体，产生rand ₂ ∈[0，1]内的均匀分布随机数，如果rand ₂ ＜ P _m ，则对该个体进行变异操作。变异方法为对每个基因位的二进制编码，产生rand ₃ ∈[0，1]内的均匀分布随机数，如果rand ₃ ＜0.1，则对该基因位的编码进行逻辑非操作。

（7）计算所有新个体的适应度函数值。

（8）更新种群的位置及其适应度函数值：用新个体的位置及其适应度函数值直接替代原种群个体的位置及其适应度函数值。

（9）更新最优个体的位置及其目标函数值：找到种群中适应度函数值最大的个体，如果其适应度函数值大于最优个体的适应度函数值，则用来替代最优个体的位置及其适应度函数值；否则，保持最优个体的位置及其适应度函数值不变。转到步骤（3）。

（10）输出优化结果：输出最优装包方案、包内物品总体积、包内物品总价值和最优个体的目标函数值进化曲线。

程序运行的输出结果非常稳定。某次优化结果为：[1，0，1，1，1，1，1，1，0，1，0，1，1，1，1，1，1，1，0，1]。因此，装入背包内物品的序号为[1，3，4，5，6，7，8，10，12，13，14，15，16，17，18，20]，总体积为878cm ³ ，总价值为1042元，相应最优个体的目标函数进化曲线如图2-10所示。

MATLAB参考源程序如下：

例2-4 利用改进的遗传算法求解TSP问题。假设有一个旅行商要到全国31个省会城市（不包含港澳台地区，各城市位置的平面坐标如表2-3所示）推销商品，从某个城市出发，途经其余各城市且仅经过一次，然后回到出发城市，试求其最短行程。假设该TSP问题为对称型旅行商问题，任意两个城市之间的距离可由城市位置平面坐标之间的欧氏距离公式求得。

解： 路径采用城市序号顺序编码方式，编码长度与城市数量相同。由于求解问题为最小值优化问题，因此用于个体评价的适应度函数采用目标函数（路径长度）的倒数来表示，将求解问题转换为最大值优化问题。这里需要对遗传算法中的交叉操作和变异操作进行改进。

（1）交叉操作采用两条路径的启发式交叉方式，交叉概率转变为交叉对象选择概率，产生rand ₁ ∈[0，1]内的均匀分布随机数，如果rand ₁ ＜ P _c ，则当前个体与从种群中随机选择的一个其他个体进行启发式交叉操作；否则，当前个体与随机路径进行启发式交叉操作。

（2）变异操作采用路径两点间或两端倒序变异方式，种群更新采用交叉变异产生的新路径与原种群混合群体竞争选择方式。

利用改进的遗传算法的求解过程如下。

（1）初始化算法参数：初始化染色体的种群数量为NP=100，染色体的编码长度为 N =31，交叉对象选择概率为 P _c =0.7，倒序变异概率为 P _m =0.2，最大进化代数为 G =300，利用给定的城市位置平面坐标计算得到任意两个城市之间的距离矩阵。

（2）随机初始化种群的路径：采用在[1， N ]内产生不重复随机整数的方法生成NP条随机路径作为种群的初始路径，计算所有个体的适应度函数值。

（3）判断是否达到了最大进化代数：若是，则结束搜索过程，转到步骤（9）；若否，则继续进行下面的步骤。

（4）依据选择概率选择交叉对象进行启发式交叉操作：对种群中的所有个体，产生rand ₁ ∈[0，1]内的均匀分布随机数，如果rand ₁ ＜ P _c ，则当前个体与从种群中随机选择的一个其他个体进行启发式交叉操作；否则，当前个体与随机路径进行启发式交叉操作。

（5）依据概率进行倒序变异操作：对交叉操作后的每一个个体，产生rand ₂ ∈[0，1]内的均匀分布随机数，如果rand ₂ ＜ P _m ，则对该个体进行倒序变异操作。

（6）计算所有新个体的适应度函数值。

（7）利用群体竞争选择更新种群：将所有新个体群与原种群个体混合，按照适应度函数值由大到小进行排序，选取前NP个个体作为下一代种群，保持种群数量不变。

（8）记录最优个体的路径及其目标函数值：找到种群中适应度函数值最大的个体，将其适应度函数值转换为目标函数值，记录最优个体的路径及其目标函数值。转到步骤（3）。

（9）输出优化结果：输出最优路径、最优路径的长度和最优个体的目标函数值进化曲线。

程序每次运行结果会有差异。某次优化路径为：17→18→19→20→28→23→22→4→21→27→31→26→25→30→24→16→5→6→29→1→9→8→7→2→15→12→10→3→11→13→14（见图2-11），路径长度为：18468.7781km，相应最优个体的目标函数值进化曲线如图2-12所示。

MATLAB参考源程序如下： mlFW+y0ovoKMd0xFdF1tzF7TBVM7rB1taizTafCodnRPX4AQEXt8vx1f6PSLPJ63