求解约束优化问题的动态目标迁移差分进化算法＊

刘俊梅 马永刚 高岳林

（中国矿业大学银川学院基础部数学教研室1） 银川 750011）（北方民族大学信息与系统科学研究所2） 银川 750021）

0 引 言

考虑以下约束优化问题（constrained optimization problems，COPs）：

式中：gi（x），hj（x），i＝1，2，…，m；j＝1，2，…，n是Rn上有的连续实函数.设Ω＝｛x：≤xd≤，d＝1，2，…，n｝，F是问题（1）的可行域.

约束优化问题广泛存在于许多领域，如货物分配、股票分析等.然而处理约束条件是求解约束优化问题的关键，目前，处理约束优化问题的主要方法是罚函数方法，惩罚函数不足之处，是很难找到适当的惩罚因子.为了克服此缺点，K.Deb等人［1－2］利用遗传算法竞争选择策略，引入了不需要惩罚因子而直接比较个体优劣的方法，但是该方法搜索能力不强，Liu Bo［3］提出的协同进化差分进化算法（CODE）.

近年来，除了罚函数法，一些新颖的技术也被融入到进化算法中用来处理约束，Runarsson和Yao［4］提出了一种随机排序法来处理约束技术（SR），M.M.Efren［5］等提出的简单可行基规则差分进化（CHDE），Lu和Chen［6］提出了自适应速度改进的粒子群优化算法求解约束优化问题，采用动态多目标方法处理约束.

以上这些方法均提出了可行解优于不可行解的规则，它没有充分考虑到约束边界周围的个体，对于这类问题，位于最优解附近的不可行解对于寻找最优解是很有帮助的.

针对形如式（1）的非线性约束优化问题，提出了一种改进的差分进化算法.该算法在初始化中加入迁移操作，采用动态双目标的约束处理方法，将其转化为无约束双目标优化问题，当个体的违反约束度在容忍度以外时，通过违反约束度函数更新个体，当个体的违反约束度在容忍度以内时，通过原目标函数更新个体，在每次迭代中保留一部分性能较优的不可行个体，扩大了个体的搜索范围，增强了算法寻优效果.

1 迁移初始化及基本差分进化算法的改进

1.1 迁移初始化

在基本差分进化算法［7］中，初始化过程是随机的，随机过程大多可以保证初始种群分布均匀，但对个体的质量不能保证，种群中有一部分个体远离可行域.如果初始种群较好，将有助于提高算法的效率和求解质量.

本文采取初始化迁移操作，对随机产生的个体按照一定的约束违反度进行选择，将远离可行域的个体向可行域方向迁移，以此提高个体的质量.

定义约束违反度函数

显然，φ（x）是所有违反约束的和，φ（x）≥0，并且φ（x）＝0当且仅当x∈F.

根据式（2）计算初始种群P0中每个个体的约束违反度，将约束违反度小于等于δ1的个体放入种群P1，否则，将个体放入种群P2，然后将种群P2中的个体进行迁移操作，迁移操作公式如下

式中：α为常数，本文取α＝0.6；R为随机选择的种群P1中的个体；S为种群P2中的个体，用新产生的个体X替换个体S。按照式（4）将种群P2中每个个体进行替换，然后将种群P1和P2合并为一个种群，这样就可以提高种群中个体的质量，根据需要可以连续进行L次以上的种群迁移操作，本文取L＝5，每进行一次种群迁移操作，违反约束容忍度变为原来的0.1倍.

1.2 基本差分进化算法的改进

1.2.1 变异操作 DE最基本的变异成分是父代的差分矢量，种群中每个矢量对父代两个不同的个体根据式（5）产生变异个体，变异操作的方程为

1.2.2 交叉操作 DE利用交叉操作以保持种群的多样性.将个体与xm进行交叉操作，产生试验个体vi.为保证个体的进化，首先通过随机选择，使得vi至少有一位由xm贡献，而对于其他位，可利用交叉概率因子CR，决定vi中那位由xm贡献，那位由贡献.交叉操作的方程为

式中：rand（）为［0，1］之间的均匀分布的随机数；交叉概率因子CR∈［0，1］.

针对基本DE算法中参数取固定值容易陷入局部极值的问题，本文采用随迭代次数线性递增的交叉概率因子，更新公式为

式中：t为当前迭代次数；Tmax为最大迭代次数；参数CRmin，CRmax表示交叉概率因子的下界和上界，该交叉概率能良好的平衡全局搜索能力和局部搜索能力.

1.2.3 选择操作 基本DE算法采用“贪婪”的搜索策略，经过变异与交叉操作后生成的试验个体vi与进行竞争，只有当vi的适应度值较更优时才被选作子代，否则，直接将作为子代.这种选择策略也是一种精英保留策略，考虑到约束优化问题的非线性约束条件，算法将对这种选择策略进行修正.

对于vi和的竞争，种群最优个体xbest的进化，本文依据违反约束度函数和原目标函数进行选择操作，当个体的违反约束度在容忍度以外时，通过违反约束度函数更新个体，当个体的违反约束度在容忍度以内时，通过原目标函数更新个体，具体操作见算法1.

2 求解约束优化问题的动态目标迁移差分进化算法

2.1 约束处理技术

本文采取动态目标的处理方法，它的主要思想是将约束违反度函数作为优化的第一个目标，将目标函数作为第二个目标进行优化.

因此求解约束优化问题（COPs）就可以转化为无约束双目标优化问题

本文设置一个阀值δ2≥0，使得φ（x）≤δ2时，就开始优化f（x）.如果个体x在可行域的外面，（即φ（x）＞δ2），则个体以φ（x）为其优化目标，否则，个体以目标函数f（x）进行优化.更新个体xi和全局最优个体xbest的具体流程（记为算法1）如下.

式中：Tmax为最大迭代次数；δ2的初始值取为10－5.

2.2 违反简单边界约束的处理技术

在某些情况下，xi新产生的试验向量vi会逃离简单边界约束，就会给算法带来不必要的计算.为此，如果某个试验向量逃离简单边界用旧个体xi和边界）的平均值来取代试验向量［8］.

2.3 改进差分进化算法（DOMDE）

步骤1 （初始化设置）确定种群的大小N，搜索空间的维数n，收缩因子F，交叉概率R的上下界，初始化约束违反容忍度δ1，初始化阀值δ2，最大迭代次数Tmax，迁移初始化总代数L，设置当前迭代代数t＝1.

步骤2 迁移初始化

1）按照式（3）随机产生N个n维向量.

2）由式（2）计算粒子群的约束违反度，如果φ（xi）≤δ1，将第i个个体加入到种群P1，否则，加

步骤3 若A＝ ｛x｜φ（x）≤δ2｝≠Φ，取初始全局最优位置xbest＝arg，否则xbest＝入到种群P2，然后对P2中的每个个体按照式（4）进行迁移操作，最后将种群P1和种群P2合并为种群P，直到进行L次种群迁移操作为止.

步骤4 根据式（5）、（6）、（7）产生试验向量，如果试验向量的某一分量xid（t）（d＝1，2，…，n）越出边界，则按式（10）对其分量重新赋值.

步骤5 根据算法1（见3.1）更新每个个体和全局最优个体.

步骤6 让t＝t＋1，返回到步骤3，直到达到设定的最大迭代次数停止.

3 数值实验及分析

为了验证本文算法（DOMDE）的有效性，选取6个测试函数［9］进行试验，将试验的结果与已有的结果进行比较.这些测试函数被认为是用进化算法很难优化的复杂函数，这些测试函数的主要特性如表1所列.在表1中，ρ＝｜F｜／｜S｜是估计可行域占整个搜索空间的比率，｜F｜表示可行解的个数，｜S｜表示整个搜索空间随机产生解的个数，在实验中｜S｜＝1000 000.其中LI，NI，LE，NE分别表示约束优化问题约束条件中线性不等式、非线性不等式、线性等式、非线性等式的个数.

表1 6个测试函数的主要性质

数值实验在Matlab7.8中进行，在计算中，群体规模 N＝10n，F＝0.6，CRmin＝0.1，CRmax＝0.9，初始化的约束违反度容忍度δ1在问题g04，g09中取为1，在g03中取为5，在g06中取为4 000，在g08中取为8，初始阀值δ2均取为10－5，最大迭代次数Tmax＝1 000，根据试验问题g01中没有进行迁移初始化操作，其余5个问题中迁移初始化进化代数L取为5.每个测试函数在相同的条件下独立运行20次，函数的最优值（记为Opt）以及20次实验的最好结果（记为Best）、中间值（记为Median）、最优值平均值（记为Mean）、最差结果（记为Worst）以及标准差（记为Std）见表2.

表2 测试函数运行结果的比较表

问题g03是极大化问题，利用－f（x）将其转化为极小化问题.由表2可见，DOMDE算法对于大多数优化问题基本上都找到了最优解，并且标准差也比较小.问题g01有2个局部极小－13.000和－12.453 125，20次独立实验算法都跳出这两个局部极小点.对于6个测试函数，DOMDE算法也基本上达到了较为满意的结果，新算法（DOMDE）与HM结果的比较见表3.

表3 新算法（DOMDE）与HM［9］结果的比较表

由表3可见，DOMDE算法不仅从20次运行的最好值，平均最好值，还是最差值，都比HM算法的寻优性能好，并且对于复杂的、利用进化算法难优化的g06问题，HM算法没有好的计算结果，而新算法DOMDE也基本上达到了最优解.

4 结束语

本文给出了一种求解约束优化问题的动态目标迁移差分进化算法（DOMDE）.针对随机初始化种群个体的质量不高，有许多个体可能远离可行域，采用迁移初始化提高初始种群的质量.将基本差分进化算法的选择操作进行修正，采用动态目标的处理约束方法来更新种群个体和全局个体，当个体的违反约束度在容忍度以外时，通过违反约束度函数更新个体，当个体的违反约束度在容忍度以内时，通过原目标函数更新个体.给出一种特殊的违反简单边界约束的处理技术，提高算法的寻优能力.将DOMDE算法的测试数值与目前已知的最优数值以及HM随机性方法得到的数值结果进行对比，显示出DOMDE算法的有效性，通用性和稳健性，是一种有潜力的全局优化算法.

［1］沈文胜，熊方方.混合型非线性规划的 MATLAB实现方法［J］.武汉理工大学：交通科学与工程版，2011，35（2）：413－416.

［2］DEB K，AGRAWAL S.A niched－penalty approach for constraint handling in genetic algorithm［C］／／Proc of the Icennga－99，Portorz，1999：234－239.

［3］LIU Bo，HAN Nan，ZHANG Xuejun.A co－evolutionary differential algorithm for constrained optimization［C］／／3th International Conference on Natural Computation（ICNC 2007），China，Haikou，2007：51－57.

［4］RUNARSSON T P，YAO X.Stochastic ranking for constrained evolutionary optimization［J］.IEEE Trans Evol Comput，2000，4（3）：284－294.

［5］EFREN M M，CARLOS A，COELLO C，et al.Simple feasibility rules and differential evolution for constrained optimization［C］／／3th Mexican International Conference on Artificial Intelligence（MICAI 2004），Mexico City，MX，2004：707－716.

［6］LU Haiyan，CHEN Weiqi.Self－adaptive velocity particle swarm optimization for solving constrained optimization problems［J］.Journal of Global Optimization，2008，41（3）：427－445.

［7］STORN R，PRICE K.Differential evolution－a simple and efficient adaptive scheme for global optimization over continuous spaces［R］.Berkley：Technical Report International Computer Science Institute，1995.

［8］KARIN Z，RAINER L.Constrained single－objective optimization using differential evolution［C］／／Proceedings of the Congress on Evolutionary Computation 2006（CEC′2006）.Vancouver，Canada，2006：927－934.

［9］KOZIEL S，MICHALEWICZ Z.Evolutionary algorithms，homomorphous mapping，and constrained parameter optimization［J］.Evolutionary Computation，1999，7（1）：19－44.