采用不可行解驱动的DE进化算法求解难约束优化问题

邓长寿¹，赵秉岩²

(1. 九江学院 信息科学与技术学院，江西 九江，332005；2. 九江学院 商学院, 江西 九江，332005)

摘要：针对一类难约束优化问题，提出一种不可行解驱动的差分进化算法求解方法。该算法利用2个不同变异算子的时变线性组合，定义一种自适应组合变异算子，有效平衡算法的全局搜索能力与局部搜索能力；基于一种概率选择准则定义一种新选择算子，有效选择可行解与不可行解，使得种群自适应地保留适当比例的不可行解进行寻优。该算法可求解难约束优化Bump问题，得出新最优解，与其他算法可求解结果比较后显示了其高效性。

关键词：难约束优化；自适应组合变异算子；概率选择准则；选择算子

中图分类号：TP18          文献标志码：A         文章编号：1672-7207(2011)S1-0620-05

Infeasible solutions driven DE for

 hard constrained optimization problem

DENG Chang-shou¹, ZHAO Bing-yan²

(1. School of Information Science and Technology, Jiujiang University, Jiujiang 332005, China;

2. School of Business, Jiujiang University, Jiujiang 332005, China)

Abstract: In order to solve the hard constrained optimization problems, an infeasible solutions driven differential volution algorithm was proposed. A self-adaptive combination mutation operator, which can balance the exploration capability and the exploitive capability, was defined using the two traditional mutation operators. Based on a selection rule, a new selection operator was constructed which can decide the one to exist between a feasible solution and an infeasible solution. The new optimum of the bump function found by the new algorithm shows that it is effective in solving the hard optimization problem.

Key words: hard constrained optimization problem; self-adaptive combination mutation operator; probability selection rule; selection operator

约束优化问题是一类广泛存在于科学研究和工程实际中的难解数学规划问题，其一般形式如式(1)所示，对其研究具有十分重要的理论和实际意义。

minimize f(x)

           (1)

式中：f(x)是目标函数，g_i(x)和h_i(x)分别为不等式约束条件和等式约束条件；l为不等式约束的个数；p 为所

有约数的个数；

目前求解非线性规划问题的方法分为两类：确定性算法和随机算法^[1]。确定性方法存在的主要问题是合适的初始解选取困难，而且需要函数的梯度信息。因此，确定性方法对于目标函数不可导、不连通的可行解域、甚至目标函数未知的问题将无法求得全局最优解。进化算法是一种基于群体的随机算法，具有   鲁棒性强、搜索效率高、不易陷入局部最优等特点，在约束优化问题中获得了广泛的应用。李敏强等^[2]基于遗传算法提出一种求解约束优化问题的方法，获得较好的结果。李炳宇等^[3]提出基于粒子群的算法求解约束优化问题的方法。最近贺毅朝等^[4]利用改进差异演化算法(MDE)求解约束优化问题，获得较好的求解结果。Becerra等^[5]利用文化差异演化算法(CDE)尝试求解约束优化问题。Zhang等^[6]利用修改差分进化算法和动态随机选择方法(DSS-MDE)求解约束优化问题。尽管这些方法取得了较好的结果，但是对于最优解位于可行域边界这类难约束优化问题，比如Bump问题，文献中报道的这些方法效果均不理想，主要表现在求解的精度和稳定性有待改善。

对于最优解位于可行域边界这类难约束优化问题，进化算法的整体搜索效率和如何充分利用不可行解搜索位于可行域边界的最优解是关键，而常见的惩罚函数方法存在惩罚因子选择困难问题^[4]。针对此类难约束优化问题，本文作者提出一种不可行解驱动的差分进化算法(Infeasible solutions driven differential evolution, ISDDE)求解难约束优化问题。ISDDE算法利用概率准则定义了一种包含处理约束条件的新选择算子，直接处理约束条件，自适应保留适当的不可行解，不仅可以有效避免惩罚函数因子选择困难问题，而且可以利用不可行解驱动最优解的寻找。此外，ISDDE算法还定义了一种自适应组合变异算子，有效平衡算法的全局搜索能力与局部搜索能力。

1  DE算法

DE算法首先在问题的解空间中随机产生初始种群，然后对当前种群进行变异和交叉操作，产生一个过渡种群；随后基于贪婪的思想，对当前种群和过渡种群中的对应个体进行一对一的选择，产生新一代群体。DE算法根据变异和交叉操作的不同，形成了不同的模式。常见的是DE/rand/1/bin和DE/best/1/bin^[7]。

设DE 算法种群规模为N, 每个个体是n维向量，则第G代中的个体可表示为DE算法的主要操作包括：产生初始种群、变异算子、交叉算子和选择算子。

产生初始种群比较简单，即在n维空间中，随机产生均匀分布的满足上下界约束的N个个体的种群。如式(2)所示。

        (2)

式中：，，和分别表示第j个变量的上界和下界。

DE 算法的变异算子利用随机2个个体间的偏差扰动产生新个体。变异算子得到中间个体记为。DE/rand/1/bin模式的变异算子表示如下：

     (3)

DE/best/1/bin模式的变异算子表示如下：

     (4)

交叉算子将当前所得到的中间个体与个体进行杂交，如式(5)所示。交叉操作得到当前个体的候选个体。

  (5)

式中，是一个均匀分布的随机数，之间的随机整数，为交叉概率。采用这种交叉策略，可以确保下一代个体中至少有一个染色体来源于中间个体。

选择算子根据候选个体的函数适应值，按照公式(6)选择相应的个体进入下一代种群。

   (6)

DE算法的控制参数有3个N，F和C。种群规模NP取值一般为变量维数的2~20倍，且至少应大于4。，。

2  难约束优化问题的ISDDE算法

2.1  自适应组合变异算子

综上所述，DE/rand/1/bin模式的变异算子中的基变量是一个随机量；而DE/best/1/bin模式的变异算子中的基变量是当前种群中的最好向量。因此，DE/rand/1/bin模式变异算子具有较好的全局搜索能力；而DE/best/1/bin模式的变异算子具有较强的局部搜索能力^[6]。为了充分发挥这2种变异算子的优势，ISDDE算法在演化迭代求解过程中，将这种两种不同的算子的变异结果进行时变线性组合。ISDDE算法在迭代的初期，DE/rand/1/bin模式的变异算子的结果占较大的比例，以获得较强的全局搜索能力。在迭代的后期，DE/best/1/bin模式的变异算子占较大的比例，以获得较强的局部搜索能力。ISDDE算法中组合变异算子定义如下：

       (7)

其中，变量λ控制2种不同变异模式所占的比例。λ随着迭代次数自适应调整，如式(8)所示。

       (8)

其中，是当前的迭代次数，是最大迭代次数。变量λ随着迭代次数自适应地变化。

图1所示为最大迭代次数为10 000代时，2种不同变异模式所占比例的变化情况。

图1  2种不同变异算子的概率曲线

Fig.1 Probability curves of two traditional mutation operators

从图1可以得知，ISDDE算法使用DE/rand/1/bin模式变异算子的比例从1逐渐减少为0；使用DE/best/1/bin模式的变异算子的比例从0逐渐增加为1。因此，ISDDE算法在演化迭代求解过程，自适应地实现全局搜索能力的逐渐缩小，局部寻优能力的逐渐增强。

2.2  带约束条件处理的新选择算子

利用进化算法求解难约束优化问题时，对于约束条件的处理是其关键。本文作者在文献[7]处理约束条件的Deb准则的基础上，提出一种概率Deb准则。基于概率Deb准则，重新定义一种选择算子。该选择算子在目标函数适应值与违反约束条件的程度之间进行平衡，选择优秀个体进入下一代种群。

Deb准则如下：

(1) 当2个比较的个体中，一个个体为可行解，另外一个个体为不可行解时，选择可行解；

(2) 当2个比较的个体均为可行解时，选择目标函数值小的个体；

(3) 当2个比较的个体均为不可行解时，选择违反约束条件程度小的个体。

Deb准则的主要缺陷是难以发挥不可行解的作用，特别是当群体中的绝大部分个体均为可行解或者是最优解处于搜索区域的边界时，不可行解将很难进入群体。针对此问题，本文对Deb准则的第一条进行修改，提出一种概率Deb准则。概率Deb准则将Deb准则的如下：(1) 当2个比较的个体中，一个个体为可行解，另外一个个体为不可行解时，以较大的概率选择可行解，以较小的概率选择不可行解，而且选择不可行解的概率逐渐变为0。

为了定义新选择算子，首先给出个体违反约束的程度定义。对于式(1)所示的约束优化问题，违反约束程度的函数：

     (9)

对于式(1)所示的最小约束优化问题，设X和Y为参与竞争的2个不同个体。定义函数如下：

     (10)

式中，ε为较小的实数，下文的实验中，为当前的迭代次数。若，则个体X优于个体Y；若，则个体Y优于个体X。从式(10)可以看出，随着迭代次数的增加，不可行解进入下一代的概率逐渐趋小，最后渐趋于0。保证最后的最优解为可行解。

综上所述，新选择算子定义如式(11)所示：

   (11)

本文作者新定义的选择算子包含了对约束条件的处理，避免了常见的罚函数方法选择惩罚因子难以确定的问题。

2.3  ISDDE算法流程图

综上所述，难约束优化问题的新型差异演化算法流程如图2所示。

图2   ISDDE算法流程图

Fig.2  Schematic diagram of flowchart of ISDDE

3  数值实验

为了检验ISDDE算法的性能，本文作者利用ISDDE算法求解著名的难约束优化问题Bump问题^[4]。

Bump问题如式(12)所示：

          (12)

Bump问题具有“三超”特性(超非线性、超多峰和超高维)的典型难约束优化问题，而且其最优解位于可行解域的边界，现有方法求解效果均不理想。其二维图形如图3所示。

图3  二维Bump问题

Fig.3 Bump problem with two dimension

Bump问题的全局最优解目前未知。当时，文献[4]求出的最新最优解为0.803 619 104 06。本文实验时ISDDE的种群数目，，，最大迭代次数为10 000。独立运行10次，10次都可以求出新的最优解0.803 619 104 125 59。ISDDE算法求出的新最优解如表1所列。

表2给出ISDDE算法与PSODE^[3]、改进差异演化算法MDE^[4]以及文化差异演化算法CDE^[5]、DSS-MDE^[6]等方法求解Bump问题的结果比较，其他方法的求解结果直接引自相关的文献。

表1  ISDDE求出的新最优解

Table 1 Best solution found by ISSDE

表2 不同算法求解结果的对比

Table 2  Compared results of different algorithms

针对20维的难约束优化Bump问题，由表2可知：在5种不同的方法中，本文作者提出的ISDDE算法求出的最优解是最优的，而且ISDDE算法计算结果的方差也是最小的，几乎接近0，显示出其良好的稳定性。

4  结束语

对于最优解位于搜索空间可行域边界的难约束优化问题，进化计算求解的关键是进化算法的搜索能力以及如何充分利用部分不可行解引导个体寻找最优解。该ISDDE算法利用组自适应组合变异算子有效平衡其全局搜索和局部搜索能力，提高了算法整体搜索能力。此外，ISDDE算法基于一种新概率Deb准则，提出一个包含约束条件处理能力的新选择算子。新选择算子不仅能够自适应地利用不可行解进行寻优，而且能够避免罚函数法中因子选择困难问题。难约束优化Bump问题的求解结果对比表明，ISDDE算法不仅仅求解新的最优解，而且算法的稳定性也最高。ISDDE算法的组合变异算子和选择算子的构造机制对于其他演化算法也有借鉴意义。

参考文献：

[1] 王勇, 蔡自兴, 周育人, 等. 约束优化进化算法[J]. 软件学报, 2009, 20(1): 11-27.
WANG Yong, CAI Zi-xing; ZHOU Yu-ren, et al. Constrained optimization evolutionary algorithms [J]. Journal of Software, 2009, 20(1): 11-27.

[2] 李敏强, 寇纪松, 林丹, 等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2003: 82-94.
LI Ming-qiang, KOU Ji-song, LIN Dan, et al. Theory and application of genetic algorithm [M]. BEIJING: Science Press, 2003: 82-94.

[3] 李炳宇, 萧蕴诗, 吴启迪. 一种基于粒子群算法求解约束优化问题的混合算法[J]. 控制与决策, 2004, 19(7): 804-807, 812.
LI Bing-yu, XIAO Yun-shi, WU Qi-di. Hybrid algorithm based on particle swarm optimization for solving constrained optimization problems [J]. Control and Decision, 2004, 19(7): 804-807, 812.

[4] 贺毅朝, 王熙照. 基于改进DE算法的难约束优化问题的求解[J]. 计算机工程, 2008, 34(13): 193-194, 217.
HE Yi-chao, WANG Xi-zhao. Solution of hard constrained optimization problem based on modified differential evolution algorithm [J]. Computer Engineering, 2008, 34(13): 193-194, 217.

[5] Becerra R L, Coello C A. Cultured differential evolution for constrained optimization [J]. Computation Methods in Applied Mechanics and Engineering, 2006, 195(33/36): 4303-4322.

[6] Zhang Min, Luo Wen-jian, Wang Xu-fa. Differential evolution with dynamic stochastic selection for constrained optimization [J]. Information Science, 2008, 178: 3043-3074.

[7] Storn R, Price K. Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization, 1997, 11(4): 341-359.

[8] Deb K. An efficient constraint handling method for genetic algorithms [J]. Computation Methods in Applied Mechanics and Engineering, 2000, 86(2/4): 311-338.

(编辑 龙怀中)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：江西省教育厅科技项目(GJJ10616,GJJ11616)

通信作者：邓长寿(1972－)，安徽合肥人，博士, 教授, 从事计算智能、数据挖掘研究；电话：0792-8313661; E-mail: dengtju@yahoo.com.cn