3.5 差分进化算法的应用实例

例3-1 利用自适应差分进化算法求解函数最小值问题。已知 N =10， x _n ∈[-20，20]，试求函数 的最小值。

解： 该函数在 X =[0，0，…，0]处，存在唯一的最小值 f （ X ）=0。函数的自变量采用实数编码方式，编码长度与问题维数相同。由于求解问题为最小值优化问题，且函数的最大值为4000，因此用于个体评价的适应度函数值采用4000减去目标函数值来表示，将求解问题转换为最大值优化问题。为了提高求解精度，引入动态变异因子，利用自适应差分进化算法的求解过程如下。

（1）初始化算法参数：初始化种群数量为NP=50，编码长度为 N =10，自变量取值上限为 X _max =20，取值下限为 X _min =-20，初始变异因子为 F ₀ =0.4，交叉概率为 P _c =0.1，最大进化代数为 G =200。

（2）随机初始化种群的位置：采用在搜索范围内产生随机数的方法，生成NP个 N 维实数编码个体作为种群的初始位置，计算所有个体的适应度函数值。

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

（4）更新自适应变异因子：按照式（3-13）计算当代自适应变异因子的取值。

（5）变异操作：对每一个当前个体，从种群中随机选择互不相同，且与当前个体也不相同的三个个体进行自适应变异操作，得到所有的中间个体。

（6）交叉操作：依据交叉概率，对每个合成向量与相应当前个体的目标向量进行基于概率的交叉操作，得到所有的候选个体。

（7）计算所有候选个体的适应度函数值：对每个候选个体的试验向量进行边界条件处理，如果分量取值超出了搜索范围，则在搜索范围内随机生成一个实数予以替代，然后计算其适应度函数值。

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

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

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

程序每次运行结果会有差异。某次优化结果为：在 X =[0.00029626，0.00061289，-0.00043382，-0.00049861，-0.00040296，-0.00025183，-0.00040292，0.00077804，-0.00054527，-0.00075725]处，函数取得最小值为 f （ X ）=2.7644×10 ^-6 ，相应最优个体的目标函数值进化曲线如图3-5所示。

MATLAB参考源程序如下：

例3-2 利用基本差分进化算法求解函数最大值问题。已知 x ∈[-6，6]， y ∈[-6，6]，试求函数 的最大值。

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

函数的自变量采用实数编码方式，编码长度与问题维数相同。由于求解问题本身就是最大值优化问题，因此直接采用目标函数作为个体评价的适应度函数。利用基本差分进化算法（DE/rand/1/bin）的求解过程如下。

（1）初始化算法参数：初始化种群数量为NP=50，编码长度为 N =2，自变量取值上限为 X _max =6，取值下限为 X _min =-6，变异因子为 F =0.5，交叉概率为 P _c =0.1，最大进化代数为 G =200。

（2）随机初始化种群的位置：采用在搜索范围内产生随机数的方法，生成NP个 N 维实数编码个体作为种群的初始位置，计算所有个体的目标函数值。

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

（4）变异操作：对每个当前个体，从种群中随机选择互不相同，且与当前个体也不相同的三个个体进行变异操作，得到所有的中间个体。

（5）交叉操作：依据交叉概率，对每个合成向量与相应当前个体的目标向量进行基于概率的交叉操作，得到所有的候选个体。

（6）计算所有候选个体的目标函数值：对每个候选个体的试验向量进行边界处理，如果分量大于取值上限，则直接取取值上限；如果分量小于取值下限，则直接取取值下限，然后计算其目标函数值。

（7）选择操作：每个候选个体与对应的当前个体进行“一对一”方式的贪婪竞争选择，如果候选个体的目标函数值大于当前个体的目标函数值，则用候选个体的位置及其目标函数值替换当前个体的位置及其目标函数值；否则，保持当前个体的位置及其目标函数值不变。

（8）记录最优个体的位置及其目标函数值：找到种群中目标函数值最大的个体，记录最优个体的位置及其目标函数值。转到步骤（3）。

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

程序每次运行结果会有差异。某次优化结果为：在 x =-2.2333×10 ^-9 ， y =-2.9786×10 ^-7 处，函数取得最大值为 f （ x ， y ）=3，相应最优个体的目标函数值进化曲线如图3-7所示。

MATLAB参考源程序如下：

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

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

（1）变异操作改为：对于个体路径 X _i ，从种群中随机选择三个父辈个体路径 、 、 ，根据 中每个城市在路径 和 中的位置序号进行差分，得到城市位置的位移向量 S ，然后将路径 中各城市的位置与 S 对应相加，得到一个新的位置向量 M ，将 依据 M 调整顺序得到中间个体 V _i 。例如，由10个城市构成的路径 ， ， ，按照 路径中城市的顺序，用同一个城市在 中的位置序号减去在 中的位置序号，得到位移向量 S =[4，7，5，-1，2，4，-3，-6，-8，-4]，如图3-8所示。

对于个体 中各城市的位置向量 J 加上位移向量 S ，得到一个新的位置向量 M =[5，9，8，3，7，10，4，2，1，6]，然后依次把 中各城市序号放置到 M 对应指定的位置上，得到中间个体 V _i ，如图3-9所示。

（2）交叉操作改为：采用中间个体路径与当前个体路径启发式交叉操作和依据概率进行倒序变异操作得到候选个体路径。

（3）选择操作改为：为了避免候选个体与当前个体“一对一”方式的贪婪竞争选择把一些好的个体过早淘汰掉，采用群体竞争选择方式。将候选个体种群和当前种群混合，从中选取NP个优质个体进入下一代种群，保持种群数量不变。

利用改进的差分进化算法的求解过程如下。

（1）初始化算法参数：初始化种群数量为NP=100，编码长度为 N =31，倒序变异概率为 P _m =0.4，最大进化代数为 G =1000。利用给定的城市位置平面坐标计算任意两个城市之间的距离矩阵。

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

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

（4）判断所有个体是否完成了当代变异操作和交叉操作：若是，则转到步骤（8）；若否，则继续进行下面的步骤。

（5）变异操作：从种群中随机选择互不相同，且与当前个体路径也不相同的3条个体路径进行变异操作，得到中间个体路径。

（6）交叉操作：将中间个体路径与当前个体路径进行启发式交叉操作和依据概率进行倒序变异操作，得到候选个体路径并进行记录。

（7）计算候选个体的适应度函数值并进行记录。转到步骤（4）。

（8）群体竞争选择操作：将由候选个体组成的候选种群与当前种群混合，按照适应度函数值从大到小排序，选取较好的前NP个个体作为下一代种群，保持种群数量不变。

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

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

程序每次运行结果会有差异。某次优化路径为：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（见图3-10），路径长度为：18468.7781km，相应最优个体的目标函数值进化曲线如图3-11所示。

MATLAB参考源程序如下： +sz79T3H5oFDIE9tb5ChgfSHcOsoz7nNWXJK5UJAHzcoBJRCWhlh0rvMjbR3d4cx