一种基于模拟退火的参数自适应差分演化算法及其应用

李亚楠 ，郭海湘 ，黎金玲，刘晓

（中国地质大学1a.经济管理学院；1b.数字化商务管理研究中心；1c.中国矿产资源战略与政策研究中心，武汉 430074；2.武汉工程科技学院，武汉 430200）

差分演化算法[1]（Differential Evolution，DE）是Price等为求解切比学夫多项式问题于1995 年提出的一种演化算法，是基于群体的随机搜索算法。算法最新颖的特点是它的变异操作，其操作是通过对当前个体加上2个随机选定个体的带权差来进行变异。因此，在算法迭代初期因种群个体差异较大，使得算法具有较强的全局搜索能力，但到了算法趋于收敛的迭代后期，种群个体差异较小，使得算法具有较强的局部搜索能力。这种新颖的变异操作也使得差分演化算法在求解优化问题上具有其他进化算法不可比拟的优点。主要总结为：收敛速度快、不易陷入局部最优及通用性强。而其包含的控制参数主要是种群大小、个体维度、变异因子以及交叉概率，待定参数较少。因其收敛速度快、不易陷入局部最优、通用性强、待定参数少等优点，差分演化算法被广泛应用于全局优化、运筹管理和工程设计等领域[2-4]。

标准的差分演化算法在高维数、多峰值复杂函数的应用上容易出现“早熟”现象，即容易陷入局部最小；后期收敛速度较慢，表现不够稳健；对控制参数设置及差分策略的选择比较敏感，会影响差分演化算法的通用性。为此，许多学者对标准的差分演化算法进行了改进。Brest等[5]提出了一种改进的差分演化算法（jDE），算法对缩放因子和交叉概率进行了自适应的调整；Wang等[6]提出了一种策略和控制参数的混合式差分演化算法（CoDE），其中缩放因子和交叉概率选自已有研究中表现较好的值；Qin等[7]提出了一种自适应策略的差分演化算法（SaDE），使得算法能够根据具体情况进行差分策略的选择；Zhang等[8-9]提出了一种带有存储机制的自适应差分演化算法（JADE），在算法中给出了一种改进的DE/current-to-best/l差分策略；Mallipeddi等[10]提出了一种控制参数和差分策略整体自适应的差分演化算法（EPSDE），对控制参数和差分策略进行了匹配；Ghosh等[11]提出了一种基于适应度值的控制参数自适应方法的差分演化算法（FiADE），其中缩放因子和交叉概率根据目标的适应度值进行自适应调整；Pan等[12]提出了一种自适应的差分演化算法，其中每个个体对应一对单独的缩放因子和交叉概率；Zou等[13]提出了一种改进的差分演化算法（MDE），其中交叉概率分别使用高斯分布和均匀分布生成，旨在提高种群多样性；郑建国等[14]提出了一种改进的差分演化算法，设计了一种新颖的DEB 准则[15]用于选择操作。虽然在提高差分演化算法的搜索能力和收敛速度方面已经做了很多工作，但是自适应策略变得越来越复杂，而且已有研究文献的仿真结果表明，差分演化算法的性能方面还有很大的改进空间。

本文提出了一种基于模拟退火的参数自适应差分演化算法（Enhanced Self-adaptive Differential Evolution，ESADE），在算法中先对种群进行初始化，生成2个相同的种群。同时，初始化一组控制参数，接着对这组控制参数进行简单的差分计算，即对其进行差分演化算法中的变异操作，生成一组新的控制参数，这两组控制参数分别和2个种群相对应。然后，2个种群在两组不同的控制参数下进行变异、交叉操作，生成两组试验向量。在选择操作中，通过对两组试验向量的比较后选出适应度表现最优的试验向量作为下一代的目标向量。为了提高算法的全局搜索能力，本算法将模拟退火的思想应用在选择操作上，并将表现较好的控制参数作为下一代初始化的控制参数。在这个进化过程中，每个目标向量对应的控制参数都能在学习前代优良经验的基础上逐步地进行自适应，解决了传统差分演化算法对控制参数设置比较敏感这一问题。为了测试ESADE算法的性能，本文将ESADE 算法与jDE、JADE、SaDE、EPSDE及CoDE算法进行了比较，比较结果表明，ESADE算法的性能在整体上优于其他5 种算法。同时，为了测试ESADE 算法解决实际问题的能力，本文将ESADE 算法应用于TSP 问题，结果表明，ESADE算法能够有效解决TSP问题。

1 传统的差分演化算法及其变形

差分演化算法的主要思想是通过变异操作产生变异个体，然后进行交叉操作得到试验个体。最后，通过选择操作使得较好的个体进入下一代群体。由于差分演化算法涉及参数少，容错性好，有全局优化的功能并且易于编码实现，故此后被广泛应用于各种科学领域。但差分演化算法也存在缺点，例如对控制参数设置及策略的选择比较敏感，这些问题影响了差分演化算法的通用性，为了解决这些问题，很多改进的差分演化算法被提出。

1.1 传统的差分演化算法

差分演化算法包括初始化种群、变异、交叉和选择4个基本操作[16]，基本执行过程如图1所示。

图1 差分演化算法的基本流程

在图1的基础上，对差分演化算法的4个基本操作做进一步阐述。

（1）编码。差分演化算法是一种基于种群的全局优化算法，种群中的个体均采用实数编码。

（2）个体结构。用NP表示种群大小，种群中第i个个体在第G代记为

其中，D为个体所包含的维度。

（3）初始化种群。种群初始化采用公式

其中：xj，i，0为第G=0代，种群中第i个个体第j个维度的值；randi，j（0，1）∈[0，1]并且随机生成；

为搜索空间第j个维度的下界；

为搜索空间第j个维度的上界；Xmin和Xmax分别为搜索空间的下界和上界的向量表达形式。

（4）变异。差分演化算法的差分就是体现在变异操作上，变异的一般过程为

式中：Xk，G为当前种群中待变异的第k个体；Xm，G、Xi，G、Xj，G为当前种群中随机挑选的个体，并且k≠m≠i≠j；Vk，G为变异后的个体；F∈[0，1]为缩放因子。通常用DE/x/y/z表示不同的变异模式，DE表示差分演化算法；x为差分项前面的基础项，通常有rand（基础项是随机从种群中选择的个体）、best（基础项是种群中最优个体）、rand-to-best和current-to-best等；y为差分项个数，通常取1或2。z为交叉模式，通常为指数模式和二项式模式。

（5）交叉。交叉概率Cr∈[0，1]。交叉有两种形式：①指数模式为

式中，jrand∈[1，2，…，D]为随机选择的值。

（6）选择。交叉后得到的个体Ui，G和目标个体Xi，G分别代入目标函数进行比较，因为差分演化算法求的是目标函数极小，所以其选择过程为

1.2 5种改进的差分演化算法

1.2.1 jDE算法 在jDE算法[5]中，控制参数F和Cr在进化过程中是自适应的，在编码时，控制参数F和Cr被编码在个体中，它们的调整是通过2个新的调整变量τ1和τ2。新一代的控 制参数Fi，G+1和Cri，G+1在变异操作之前就产生了，因此，jDE的这种自适应控制参数机制能够影响到变异操作、交叉操作以及选择操作生成的新个体向量。

1.2.2 JADE算法 在JADE 算法[8-9]中引入了一种新颖的变异策略（即DE/current-to-pbest 策略）和一个用于存档次优解的存档向量来引导算法进化的方向。这种DE/current-to-pbest 策略利用多个最佳解决方案既满足了变异策略的贪婪性又保留了种群的多样性，同样地，这种存档向量用来存储除最优解外的较优解，能够保留种群的多样性。

1.2.3 SaDE算法 在SaDE算法[7]中，每一代的差分策略是从策略侯选池（DE/rand/1，DE/rand/2，DE/rand-to-best/2，DE/current-to-rand/1）中，根据每个差分策略概率的大小进行选择，这个概率是通过对每个差分策略在一定数量的代数上的表现进行计算的，其中这个一定数量的进化代数称为学习期（Learning Period，LP）。

1.2.4 EPSDE算法 在EPSDE 算法[10]中引入了差分策略池和控制参数池，其中控制参数池包括缩放因子值池和交叉概率值池。

在EPSDE算法中，初始化种群中每个个体随机地从差分策略池中选择一种差分策略，并相应地从缩放因子值池和交叉概率值池中分别随机选取一个值作为其缩放因子和交叉概率。在选择操作中，当试验向量的适应度值比目标向量的适应度值好时，生成试验向量对应的差分策略、缩放因子和交叉概率的组合将被保存在一个成功组合池里，并进入下一代的进化；当试验向量的适应度值比目标向量的适应度值差时，目标向量对应的差分策略、缩放因子和交叉概率将被随机重新初始化，该初始化过程是以相同的概率直接从成功组合池中随机选择，或从差分策略、缩放因子和交叉概率各自对应的池中随机选择。

1.2.5 CoDE 算法 类似地，Wang等[6]提出了一种结合不同差分策略的系统框架，称为复合式差分演化算法（Composite DE，CoDE）。其中差分策略和控制参数是通过研究后选取表现较好的策略和参数值。

在CoDE算法中，对应3种差分策略，每个目标向量进行差分演化计算后生成3个试验向量。将3个试验向量中适应度值表现最好的一个与目标向量的适应度值进行比较，如果其适应度值表现比目标向量的适应度值好，则该试验向量将进入下一代进化。

2 基于模拟退火的参数自适应差分演化算法

针对传统差分演化算法对控制参数设置和差分策略选择比较敏感，以及局部搜索能力较差导致的演化后期收敛速度变慢等问题，已经有很多学者对传统差分演化算法提出了改进策略，虽然在提高差分演化算法的搜索能力和收敛速度方面已经做了很多工作，但是自适应策略变得越来越复杂，而且已有研究文献的仿真结果表明，差分演化算法的性能方面还有很大的改进空间。基于这种情况，本文提出了一种基于模拟退火的参数自适应差分演化算法（ESADE），其步骤如下：

（1）个体编码。编码个体包括三部分：候选解向量、控制参数和适应度值。编码个体结构如图2所示。

图2 个体的编码

（2）初始化。初始化包括控制参数初始化和种群初始化两部分。其中，控制参数初始化包括种群大小NP，模拟退火中初始温度参数t0，每个个体对应的缩放因子oFi，G和每个个体对应的交叉概率oCri，G。其中，oFi，G和oCri，G的动态更新如下：

式中，oFi，G、oCri，G分别是以μF和μCr为均值通过柯西和正态分布生成的。μF、μCr初始值设置为0.5，每一代的更新过程分别为：

式中：SF是用来存储成功进化缩放因子的数组，即用来存储能够进入下一代的试验向量对应的缩放因子值的数组；SCr是用来存放成功进化交叉因子的数组，即用来存储能够进入下一代的试验向量对应的交叉因子值的数组。

种群初始化是在相应范围内均匀分布，

并且

则在G=0代时，第i个个体第j个属性的初始化为

（3）参数变异。通过对控制参数oF和oCr进行变异操作，得到一组新的控制参数mF和mCr，其变异过程为：

式中，r1、r2的取值是在1，2，…，NP中随机抽取不同的整数。

生成2个相同的种群：①标记为populationo，与控制参数oFi，G、oCri，G对应进行差分演化计算；②标记为populationm，与控制参数mFi，G、mCri，G对应进行差分演化计算。

（4）种群变异操作。种群populationo的差分策略是DE/current-to-pbest/1，其变异操作过程为

种群populationm的差分策略是DE/current-topbest/1，其变异操作过程为

（5）种群交叉操作。种群populationo的交叉操作是二项交叉，其操作过程为

种群populationm的交叉操作是二项交叉，其操

作过程为

（5）种群选择操作。种群选择操作的过程是通过比较目标向量Xi，G、种群poplutiono生成的试验向量oUi，G以及种群poplutionm生成的试验向量mUi，G选择出适应度值最优的进化到下一代。在该过程中，模拟退火的思想被加入到选择操作中用来增强算法的全局搜索能力，t0为模拟退火中的初始化温度参数，tG为第G代温度参数，其中，tG更新与选择操作过程为：

式中：G为进化的第G代；f（oUi，G）为oUi，G的适应度值；f（mUi，G）为mUi，G的适应度值；f（Xi，G）为Xi，G的适应度值。

（7）记录优良的控制参数。当试验向量能够成功进化到下一代时，说明其对应的控制参数表现较好，这些表现较优良的控制参数将分别被存入成功进化缩放因子数组SF和成功进化交叉因子数组SCr中。其过程为：

若Xi，G+1=oUi，G，则oFi，G→SF，oCri，G→SCr；若Xi，G+1=mUi，G，则mFi，G→SF，mCri，G→SCr。

当数组SF、SCr内存储的控制参数数量超过一个上限值时，数组SF、SCr将被清空。

（8）更新控制参数。如果SF不是空集，则根据（7）、（5）对控制参数oF进行更新，更新过程：

如果SCr不是空集，则根据（8）、（6）对控制参数oCr进行更新，更新过程：

3 ESADE 算法与差分演化算法的其他变形的比较

3.1 实验设置

3.1.1 基准函数 影响差分演化算法计算效果的因素主要包含实验环境、测试函数和控制参数的设置以及差分策略的选择。为了测试ESADE 算法的性能，本文将ESADE算法与其他改进差分演化算法在相同条件下进行测试。因为改进的差分演化算法大多是针对变异因子、交叉概率以及差分策略进行的改进，因此，本文设置的相同条件主要包括相同的实验环境（电脑型号Dell-XPS8500和软件型号Matlab-R2010a）、相同的测试函数以及相同的基本参数（种群大小、个体维度、算法进化的代数以及独立运行次数）。本文使用17（f1～f17）个全局最小值的基准函数作为测试函数，这些函数都是从参考文献[15]中选择的国际通用的测试函数，其维度均可以自由变化。其中，f1～f5是单峰函数，f6～f9是基本多峰函数，f10是扩展多峰函数，f11～f17是混合组成函数。这些函数的最优值f（x*）、最优取值时x*的取值和x的初始范围如表1所示，函数的详细表达形式见附录A。

表1 基准函数的基本介绍

3.1.2 参数设置 为了比较ESADE 算法和其他改进差分演化算法的性能，本文设置统一参数：进行基准函数测试的维度大小D=30；种群大小NP=50；每个函数的最大进化代数为10 000；每个函数独立运行次数为25。另外，本文提出的算法所涉及模拟退火中的初始化温度参数t0=1 000。

3.2 ESADE算法和其他改进差分演化算法性能的比较

ESADE算法性能的评估是通过和其他改进差分演化算法的性能进行比较而得出的，这些改进差分演化算法是上文所介绍的jDE、JADE、SaDE、EPSDE和CoDE等5种算法。

为了避免一次运算导致的结果偏差较大这一现象，本文设置的独立运行次数为25，即每个函数进行25次独立进化，对进化的最优值求平均作为算法求得的平均最优值。表2给出了17个基准函数在维度取值为30、独立运行次数为25 时的平均值。为了进一步分析算法的性能，本文采用威尔科克森秩和检验分别对ESADE算法和jDE、JADE、SaDE、EPSDE及CoDE算法进行了比较，其中威尔科克森秩和检验的置信区间为0.05，其比较结果如表3所示。

表2 ESADE算法和jDE、JADE、SaDE、EPSDE及CoDE算法在17个测试函数上进行25次进化的测试结果

表3 威尔科克森秩和检验的比较结果

表4给出了ESADE 算法和其他改进差分演化算法之间的比较结果。表4清楚地表明，本文提出的ESADE算法整体上比其他5种算法的性能都要好。如ESADE 算法在13 个测试函数上性能比jDE算法好，在3个测试函数上性能和jDE相似；在10个测试函数上性能比JADE 算法好，在4个测试函数上性能和JADE相似；在14个测试函数上性能比SaDE算法好，在3 个测试函数上性能和SaDE相似；在9个测试函数上性能比EPSDE 算法好，在2个测试函数上性能和EPSDE相似；在9个测试函数上性能比CoDE 算法好，在5个测试函数上性能和CoDE相似。

表4 ESADE算法和CoDE、JADE、j DE、EPSDE算法及SaDE在威尔科克森秩和检验下的比较结果

为了进一步阐明ESADE 算法和其他改进差分演化算法性能之间的关系，本文在图3中给出6个测试函数在几种不同算法上的进化收敛图。由图3可见，ESADE算法的整体收敛速度比其他5 种算法都要快，而且没有出现陷入局部最优的情况。图3中所选取的6个测试函数都是有代表性的函数。从ESADE 算法和其他改进差分演化算法的比较表明，ESADE算法的性能在整体上优于其他5 种算法，与其他5种算法相比，ESADE 算法的优势很明显。这是因为本文提出的ESADE 算法能够自适应地调整控制参数以便满足不同问题需求，而且在选择操作中加入了模拟退火的思想，能够提高全局搜索能力。

图3 ESADE、jDE、JADE、SaDE、EPSDE和CoDE算法在6个函数上的进化收敛图

3.3 模拟退火中初始温度参数对ESADE 算法性能的影响

模拟退火中初始温度参数的设置可能会影响ESADE算法的性能，为了使ESADE算法的性能达到最优，本文对模拟退火中初始温度参数t0的取值进行了测试。在t0=10，100，1 000，10 000时，分别测试了ESADE算法的结果并给出了ESADE 算法在6个函数上的收敛图，如图4所示。图中表明，当t0=10 000 时，ESADE 的性能较差；但是当t0=10，100，1 000时，并无明显区别。为了进一步说明t0取值对ESADE 算法性能的影响，本文使用威尔科克森秩和检验分别对取不同t0值的ESADE算法和jDE、JADE、SaDE、EPSDE 及CoDE 算法进行了比较，其中威尔科克森秩和检验的置信区间为0.05，其比较结果如表5 所示。表中说明，当t0=1 000时，ESADE算法的性能最好。故将初始温度参数设置为t0=1 000。

表5 t0取不同值时，ESADE 算法和CoDE、JADE、jDE、EPSDE 及SaDE算法的比较结果

图4 t0取不同值时，ESADE算法在6个函数上的收敛图

3.4 ESADE算法在解决TSP问题上的应用

为了测试ESADE算法在解决现实问题上的性能，本文将ESADE 算法用于解决TSP 问题，并将结果与CoDE、JADE、jDE、EPSDE 及SaDE 算法进行比较。

3.4.1 TSP问题描述 TSP（Traveling Saleman Problem）即旅行商问题，简称为TSP 问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本[16]。在算法中，通过目标函数来评价新解的优劣，从而保证产生新解的质量，有利于算法的快速收敛。本文使用的目标向量为

式中：n为城市个数；dij为城市i、j之间的距离；xij为决策变量，其表达式为

3.4.2 实验设置 所有算法的最大进化代数统一设置为10 000，种群大小为100，独立运行次数为25次，城市个数分别为10和14（城市的具体坐标见附录B）。

3.4.3 实验结果与分析 表6给出了当ESADE、CoDE、JADE、jDE、EPSDE 及SaDE 算法用于TSP问题的结果以及时间消耗。结果表明，当城市个数为10 和14 时，ESADE 算 法 能 够 得 到 与jDE、JADE、SADE 及CoDE 算法相同的平均值和中值，并且这一均值是目前已有研究中的最小值；同时，因为ESADE 算法中采取的双种群策略以及加入模拟退火机制的选择策略，相对于jDE 和JADE 算法，ESADE时间耗费会翻倍，但比SaDE、EPSDE 和CoDE 算法的时间耗费，ESADE 算法更高效。表7给出了在0.05置信区间内，本文采用威尔科克森秩和检验分别对ESADE 算法和jDE、JADE、SaDE、EPSDE及CoDE算法应用于TSP问题上的结果进行了比较，比较结果表明，ESADE算法在TSP问题上的表现优于EPSDE 算法，类似于jDE、JADE、SADE及CoDE算法。以上结果表明，ESADE算法能够有效解决TSP问题。

表6 ESADE、CoDE、JADE、jDE、EPSDE及SaDE算法应用于TSP问题的结果

表7 ESADE算法和CoDE、JADE、j DE、EPSDE及SaDE算法在TSP问题上的比较结果

4 结语

差分演化算法作为一种高效的优化算法，被广泛应用于科学与工程领域。在差分演化算法中，进化策略和控制参数会对算法的性能有重要影响。但是因为不同问题甚至是相同问题的不同进化阶段需要的最优设置都是不同的，使得选择合适的进化策略和相关参数成为一个较困难的问题。为了解决该问题，本文提出了一种ESADE算法。ESADE算法生成一组控制参数oF和oCr，再通过对这组控制参数进行变异操作生成一组新的控制参数mF和mCr，然后根据这两组控制参数分别对2个相同的种群进行变异和交叉操作，生成两组试验向量，最后进行选择操作。为了增强算法的全局搜索能力，ESADE算法中的选择操作加入了模拟退火的思想。为了对ESADE 算法的性能进行测试，本文从CEC2005中选择了17个函数作为测试函数，并将ESADE算法的测试结果与其他改进差分演化算法的测试结果进行了比较。比较结果显示，ESADE算法有很强的全局搜索能力，并且性能在整体上优于其他算法。同时，本文还测试了模拟退火中初始温度参数对ESADE 算法性能的影响，结果表明，当初始温度参数为1 000时，ESADE算法的性能较好。最后，将ESADE算法应用于TSP问题，结果表明，ESADE 算法能够取得与jDE、JADE、SADE及CoDE算法相同的最小值，并且这一最小值是目前已知最小值，这说明，ESADE算法能够有效解决TSP问题。

本研究未来的工作主要集中于两点：①将小生境算法的思想加入到变异操作中，改变个体的选择方式，使得个体的选取更加具有代表性；② 将ESADE算法应用于解决更多的实际问题，例如，将ESADE算法用于解决多目标优化问题；将ESADE算法用于解决油层识别问题，包括特征选择和规则提取等。

附录A

基准函数的详细表达形式。

f1：Shifted sphere function，其公式为，z=x-o，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。

f2：Shifted schwefel's problem 1.2，其公式为，z=x-o，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。

f3：Shifted rotated high conditioned elliptic function，其公式为，z=（x-o）M，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0，M为正交变换矩阵。

f4：Shifted schwefel's problem 1.2 with noise in fitness，其公式为

其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。

f5：Schwefel's problem 2.6 with global optimum on bounds，其公式为，其中，-100≤x（i）≤100，A为D×D的矩阵，aij是取值范围在[-500，500]的随机整数，det（A）≠0，Ai是矩阵A的第i行，Bi=Ai˙o，o是D×1的向量，oi是取值范围在[-100，100]的随机整数，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。

f6：Shifted rosenbrock's function，其公式为

其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。

f7：Shifted rotated griewank's function without bounds，其公式为

其中，0≤x（i）≤600，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0，M为正交变换矩阵。

f8：Shifted rotated ackley's function with global optimum on bounds，其公式为

其中，-32≤x（i）≤32，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0，M为正交变换矩阵。

f9：Shifted rastrigin's function，其公式为，z=x-o，其中，-5 ≤x（i）≤5，o=（o（1），o（2），…，o（n））为转移全局最优取值，即全局最优值在x*=o时取得，全局最优值f（x*）=0。f10：Shifted expanded griewank's plus rosenbrock's function，其公式为

其中，-3 ≤x（i）≤1，o=（o（1），o（2），…，o（n））为转移全局最优取 值，即全局最优值在x*=o时取 得，全 局最优值f（x*）=0。

f11～f17：函数f11～f17分别由10个基本函数组合而成，详细描述请参考文献[15]。

附录B

城市坐标

表1 10点TSP问题

表2 14点TSP问题