ComputerEngineeringandApplications计算机工程与应用2010,46(15)43
0-1非线性规划问题的改进差分进化算法
刘俊梅，高岳林1，李会荣1,2直流固态继电器
LIUJun-mei,GAOYue-lin',LIHui-rong,
1.北方民族大学信息与系统科学研究所，银川750021
河南天价过路费案
限额领料2.商洛学院数学与计算科学系，陕西商洛726000
1.ResearchInstituteofInformation&SystemScience,NorthNationalUniversity,Yinc huan750021,China
2.MathematicsandComputerScienceDepartment,ShangluoAcademy,Shangluo,Shaanxi 726000,China
南通东方中学E-mail:***********************
LIUJun-mei.GAOYue-lin.LIHui-rong.Improveddifferentialevolutionalgorithmof0-1no nlinearprogrammingprob-
lems.ComputerEngineeringandApplications.2010.46(15):43-46.
Abstract:For0-1nonlinearprogrammingproblem,animproveddifferentialevolutionalgori thmisproposed.Inthealgorithmpenalty functionmethodisusedtoprocesstheconstraintsandthecrossoverprobabilityisanexponenti ncreasedfunctiononiterationto raiseglobaloptimizationabilityandconvergentspeedand0-1integeroperationisusedinmut ationoperatortoproduce0-1in—
tegerpoints.Itisshownforeightexamplesthatthealgorithmisgoodinconvergence,precision androbust.
Keywords:0-1nonlinearprogramming;differentialevolutionalgorithm;penaltyfunction method;exponentincreasedcrossoverprobability
摘要：针对0-1非线性规划问题的特点，提出了一种适合于求解0—1非线性规划问题的改进差分进化算法.这个算法把差分进化
算法和罚函数方法有机结合起来，在变异操作中加入0-1取整运算，在交叉操作中使用了指数递增交叉概率因子以提高算法的全
局搜索能力和收敛速率.用8个例子进行了实验研究，结果表明这个改进的差分进化算法在收敛性，精 度，鲁棒性强方面都比较好.
关键词:0—1非线性规划；差分进化算法；罚函数方法；指数递增交叉概率因子DOI.10.3778/j.issn.1002—8331.2010.15.014文章编号:1002—8331(2010)15—0043—04文献标识码:A中图分类号:TP18
1引言
0-1非线性规划问题(0一INLP)是每个决策变量仅仅取0
和1的非线性规划问题，有时被称为二进制整数规划(BIP)问
题，他广泛存在于许多实际工程和管理等领域，如资本预算问
题，背包问题，旅行商问题等.求解0—1NLP的传统方法有分支
定界法，广义Benders分解法(GBD)，外近似法等.这些方法随w980i
着变量维数的增加，计算量会急剧增大，从而使这些算法不可
能用于实时控制，存在很大的局限性.近年来，有些学者利用罚
函数法将0-1NLP转化为无约束优化问题，然后利用古典优化
的方法求解，例如用最速下降法(SDM)Ill，文献[2】将0—1非线性
混合整数规划转化为无约束非线性规划问题，可通过求解一个
无约束非线性规划问题得到原问题的s近似极小解，所得近似
解有时很难达到最优，存在一定的局限性，也有些学者把0—1
非线性规划问题通过连续化处理，然后利用进化算法求解，如
文献『3】.差分进化算法H(DE)是RainerStorn和KennethPrice
于1995年共同提出的一种采用浮点矢量编码，在连续空间中进
行启发式随机搜索的优化算法[51.近年来，差分进化算法作为一
种性能卓越的优化算法正受到13益关注，许多学者对差分进化
算法进行改进并广泛应用于各个领域.如文献[6]提出一种基于
混沌搜索的差分进化算法，文献【7】用改进的差分进化算法去求
解多目标优化问题，文献[8】把正交的差分进化算法应用于工程
优化设计中，为了将DE用于求解混合整数非线性规划(MINP)
问题，文献【9]用混合整数编码方案的差分进化算法去求解混合
整数非线性规划问题，文献[i01对DE的变异操作进行了改进,
提出了对变异矢量采用四舍五入方法进行取整，使之适合于0一
l整数规划和整数只包括{0,1/的优化问题.取得了好的效果.
在进行初始化时对0—1变量，先在{0,1}实数空间随机取值，然
后采用四舍五入法进行取整运算，得到对应的0—1变量，在变
异操作时，对变异矢量同样采取四舍五入的方法进行取整，该
方法扩大了寻优空间，有利于提高算法搜索到最优解的鲁棒性.
用多个例子对改进的算法进行测试，实验结果表明了所提出的
改进DE(MDE)算法用于求解0-1NLP问题的有效性.
20-1非线性规划问题的描述
论文研究以下形式的0-1非线性规划问题:
min)
<()--<0,i=1,2,…,m(1)
()=0√=1,2,…,1
基金项日：国家自然科学基金(theNationalNaturalScienceFoundationofChinaunderGrantNo.60962006)；宁夏自然科学基金项目资助(NnNzO848).
作者简介：刘俊梅(1980一)，女，硕士，研究方向：最优化理论及应用，智能计算及应用；高岳林(1963一)，男，教授，博士，研究生导师，研究方向：最优
化理论方法及应用，智能计算及应用，金融数学与金融工程.
收稿日期:2008—12—04修回日期:2009—02—18
442010,46(15)ComputerEngineeringandApplwations计算机工程与应用
xi=Oor1,i=1,2,…,D
式(1)中:(…,)，岛()为不等式约束条件,hi(x)为等式
约束条件.这些约束条件通常都是非线性的，因而O-1NLP问
题一般难以求解.对约束条件的处理，一般采用简单有效的惩
罚函数法『l11，将带约束条件的原0-INLP问题转化为无约束问
题来求解.经惩罚函数转化后的无约束问题可定义为:
f,
))十∑()十∑()>:(2)j=l/=1
式(2)中和为大于零的惩罚因子.
<gi>+=max(0，慝)
3改进的差分进化算法
差分进化算法采用浮点数编码，在连续空问进行优化计
算，是一种求解实数变量优化问题的有效方法.要将DE用于
求解0-1规划或0-1非线性规划问题，必须对DE进行改进. DE的基本操作包括变异，交叉和选择操作，与其他进化算法一样也是依据适应值大小进行操作.根据DE算法的特点，只要
对变异操作进行改进就可以将DE用于0—1规划和0-1非线性规划.对于0-1变量，文中对变异后的矢量进行取整运算(采取四舍五入法)，这样使得变异操作在{0,l}实数空间进行，从
而扩大了寻优空间，有利于提高算法的寻优能力.一般而言，进行取整运算时要么是向下取整，要么是向上取整，只作一种选择，缩小了寻优空间，该文算法在取整运算时采用四舍五入法.
3.1变量描述与初始化
DE由Ⅳ个参数矢量:(i=1,2,…,Ⅳ，其中t表示第￡代)
构成种，在搜索空间进行并行直接的寻优.设0—1变量的维数为D，可表示为(，一,%)初始化时，根据式(3)对0—1
变量进行初始化.对于0-1变量，先在i0,1}实数空间进行随
机取值，然后进行取整运算，得到对应的0一l变量.式中rand() 为f0,1】之间的均匀随机数.和分别为相应决策变量的下
界和上界.
'
+[rand()}(')1(3)
3.2变异操作
0-1变量变异操作:
DE最基本的变异成分是父代的差分矢量，每个矢量对包括
父代两个不同的个体(:.,X')根据变异个体的生成方法不同,r2
形成了多种不同的差分进化算法方梨目.其中用四舍五入的方法进行取整，对0—1变量进行变异操作的方程为:
=
d+(,l—)】(4)
式(4)中Xt，为互不相同的随机个体,Ff0,2】，为缩放因
子.变异矢量其实就是的一个噪音版本.
3.3交叉操作
DE利用交叉操作以保持种的多样性.对于体中第i
个个体:，将与进行交叉操作，产生试验个体.为保证个
体：的进化，首先通过随机选择，使得至少有一位由贡
工业品外观设计
献，而对于其他位，可利用一个交叉概率因子CR，决定中哪
位由贡献，哪位由：贡献.交叉操作的方程为:
,2,...,Ⅳ(5).thers,2, (Ⅳ)
式(5)中rand()为『0,1]之间的均匀分布的随机数,CR∈[0,l】. 由式(6)可知，女H果CR越大，则对的贡献越多，当CR=I
时,m==有利于局部搜索和加速收敛速率；如果CR越小，则
：对9CT的贡献越多，当CR=0时,：对，有利于保持种的多
样性和全局搜索.由此可见，在保持种多样性与收敛速率之间是矛盾的.良好的搜索策略应该是在搜索的初始阶段保持种多样性，进行全局搜索，尽可能得到多个可能全局最优的种子，而在搜索的后期应加强局部搜索能力，以提高算法的精度. 基于这种思想，采用指数递增交叉概率因子CR的方法，即CR 随迭代次数的增加而由小变大，初始阶段t对XT贡献多，提高全局搜索能力，而在后期则对贡献多，提高局部搜索能力.
设cR为最小交叉概率，一为最大交叉概率,t为当前迭代
次数，为最大迭代次数，则CR由方程(6)确定:
一
f1一tit,'
CR=CR+(一CR)e～(6)
