无约束优化问题的差分进化算法求解

洪云飞 （长江大学期刊社；信息与数学学院，湖北 荆州434023）

陈 忠 （长江大学信息与数学学院，湖北 荆州434023）

差分进化算法 （Differential Evolution，DE）是一种基于群体差异的启发式随机搜索算法［1］。差分进化算法具有全局优化性能好，结构简单和易于实现的特点，在函数优化［2－3］、多目标优化［4］、背包问题［5－6］、系统辨识［7－8］等方面得到广泛应用。下面，笔者利用差分进化算法求解无约束优化问题。

1 约束优化问题的数学描述

不失一般性，以最小化问题为例，无约束优化问题可描述为：

其中，S＝ ｛x∈Rn｜li≤xi≤ui，i＝1，2，…，n｝为问题的可行域。

2 差分进化算法的构成要素

1）编码方法 使用差分进化算法求解一个问题之前，需要选择一种编码方法。编码就是将实际问题的解用一种便于算法操作的形式来描述。根据问题的具体情况，可以灵活选择编码方式。如对于排序问题可采取顺序编码，对于背包问题可以采取0－1编码。对于实优化问题，一般可以直接使用实数编码，编码的每一位就是解的相应维的取值。笔者选择实数编码作为算法实现的编码方式。

2）适应度函数的构造 类似于遗传算法，差分进化算法的适应度函数也是用来对搜索状态进行评价的。一般情况下，将目标函数作为适应度函数是最直接也是最容易理解的做法。当然，对目标函数的任何变形都可以作为适应度函数，只要这个变形是严格单调的。笔者直接把目标函数作为适应度函数。

3）种群规模 种群规模NP是一个整型参数。当NP很小的时候，由于无法保证种群的多样性，算法容易陷入局部最优解。然而，种群规模过大将导致计算时间大幅增加，降低算法的执行效率。并且当种群规模增长到一定水平时，继续增加种群规模将不再有显著作用。因此，针对不同的具体问题，需要设置合适的种群规模算法才能达到较好的搜索性能。

4）初始解的获得 差分进化算法可以随机给出初始解，也可以事先使用其他算法给出一个较好的初始解。由于差分进化算法主要是基于个体之间的差异推动群体进化，因此初始解的好坏对算法的搜索性能有较大影响。尤其是一些带有复杂约束的优化问题，随机给出的初始解很可能是不可行的，甚至通过多步搜索也很难找到一个可行解，这个时候应该针对特定的复杂约束，采用启发式方法或其他方法找到可行解作为初始解。笔者以标准测试函数检测算法性能时采用随机方式生成初始解。

5）进化操作 差分进化算法的基本进化操作包括变异、交叉和选择。算法在优化迭代过程中，采用规模为NP的D维向量（i＝1，2，…，NP）作为第g代的种群，在搜索空间中进行寻优，其中NP为种群规模，D为解空间维数。

式中，CR为交叉概率，范围在0～1之间；rand（）为0～1范围内生成的随机数；jrand为1～D之间随机选取的整数随机量。

式中，f（·）为适应度函数。

6）停止准则 一般使用最大迭代次数或可以接受的满意解作为停止准则。笔者选择最大迭代次数作为算法停止的控制参数。

3 差分进化算法步骤和流程

差分进化算法执行的步骤如下：

Step1 初始化。根据具体问题初始化种群。

Step2 判断是否满足停止条件。如果满足，输出结果，算法停止；否则继续一下步骤。

Step3 执行变异操作。从父代群体中随机选取3个个体，按照式 （2）执行变异操作，得到变异个体；

Step4 执行交叉操作。对变异个体按式 （3）执行交叉操作，得到交叉个体；

Step5 执行选择操作。计算交叉个体的适应值，并与原个体进行比较，依据贪婪选择原则执行选择操作，返回Step2；

差分进化算法的执行流程如图1所示。

图1 差分进化算法流程

4 数值试验

通过标准测试函数来分析差分进化算法在求解数值优化问题时的寻优性能。笔者选取的标准测试函数如下：

对于待求解问题本身来说，问题维度是影响计算规模的关键因素。对于求解算法而言，控制参数是影响算法性能的关键因素。在差分进化算法中，有3个主要控制参数：种群规模NP、变异操作中差分向量的缩放因子F以及交叉操作中的交叉因子CR。因此，笔者首先通过上述标准测试函数对差分进化算法的计算性能进行初步检验，同时分析不同控制参数对差分进化算法计算性能的影响，从而获取比较合适的控制参数设置范围，并以此为基础展开后续并行差分进化算法的研究和测试工作。

较大的种群规模，一方面可以容纳更多的不同个体，为种群多样性提供了可能；另一方面增加了需要进行评价计算的个体数量，也就意味着算法寻优的时间必然要增加。因此，不能简单地说种群规模的变化对算法求解性能影响的利弊，而需要进行大量模拟计算，把种群规模控制在一个合理的范围内，既保证差分进化算法有足够的特征各异的进化个体，又兼顾算法的求解耗时。

将问题维度固定为30，迭代次数为1000，缩放因子F固定为0.6，交叉因子CR固定为0.8，在不同种群规模情况下以差分进化算法对上述5个标准测试函数进行模拟计算，模拟计算结果如表1所示。

表1 不同种群规模下测试函数的模拟计算结果

由表1可见，当问题维度为30时，随着种群规模的增加，差分进化算法寻优得到的结果逐渐向全局最优点靠近，但是当种群规模超过200左右时，算法的寻优结果并没有继续呈现较强的向全局最优点逼近的趋势，反而呈现出一种震荡或回退的趋势，如图2所示。该现象说明，在问题维度一定的情况下，种群规模超过某个阈值后，继续增加种群规模未必能够带来寻优性能的增加。但是可以预见的是，其计算耗时必然会随着种群规模的扩大而迅速增加。

图2 适应值与种群规模的关系

［1］Storn R，Price K.Differential evolution－A simple heuristic for global optimization over continuous spaces ［J］.Journal of Global Optimization，1997，11 （4）：341－359.

［2］Ali M M.Differential evolution with preferential crossover ［J］.European Journal of Operations Research，2007，181 （3）：1137－1147.

［3］Noman N，Iba H.Accelerating differential evolution using an adaptive local search ［J］.IEEE Trans on Evolutionary Computation，2008，12 （1）：107－125.

［4］Iorio A W，Li X D.Solving rotated multi－objective optimization problems using differential evolution ［A］.Proceeding of the 17th Australian joint conference on advances in artificial intelligence ［C］.Cairns，Australia，2004：861－872.

［5］Chen Peng，Li Jian，Liu Zhiming.Solving 0－1knapsack problems by a discrete binary version of differential Evolution ［A］.Proceeding of the 2nd International Symposium on Intelligent Information Technology Application ［C］.Shanghai，China，2008，II：513－516.

［5］Wang Ling，Fu Xiping，Mao Yunfei，et al.A novel modified binary differential evolution algorithm and its applications ［J］.Neuron computing，2012，98 （5）：55－75.

［7］Peng Bo，Liu Bo，Zhang Fuyi，et al.differential evolution algorithm based parameter estimation for chaotic systems［J］.Chaos，Solutions and Fractals，2009，39 （5）：2110－2118.

［8］Zhang Rui，Song Shiji，Wu Cheng.A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion ［J］.Applied Soft Computing，2013，13 （3）：1448－1458.