0-1非线性规划问题的改进差分进化算法

0-1非线性规划问题的改进差分进化算法

2023年10月28日发(作者：暑假班招生简章)

赞美活到老学到老的唯美句子-

0-1非线性规划问题的改进差分进化算法

ComputerEngineeringandApplications计算机工程与应用2010,46(15)43

0-1非线性规划问题的改进差分进化算法

刘俊梅,高岳林1,李会荣1,2

LIUJun-mei,GAOYue-lin',LIHui-rong,

1.北方民族大学信息与系统科学研究所,银川750021

2.商洛学院数学与计算科学系,陕西商洛726000

chInstituteofInformation&SystemScience,NorthNationalUniversity,Yinchuan750021,China

aticsandComputerScienceDepartment,ShangluoAcademy,Shangluo,Shaanxi726000,China

E-mail:***********************eddifferentialevolutionalgorithmof0-1nonlinearprogrammingprob-

erEngineeringandApplications.2010.46(15):43-46.

Abstract:For0-1nonlinearprogrammingproblem,lgorithmpenalty

functionmethodisusedtoprocesstheconstraintsandthecrossoverprobabilityisanexponentincreasedfunctiononiterationto

raiseglobaloptimizationabilityandconvergentspeedand0-1integeroperationisusedinmutationoperatortoproduce0-1in—

ownforeightexamplesthatthealgorithmisgoodinconvergence,precisionandrobust.

Keywords:0-1nonlinearprogramming;differentialevolutionalgorithm;penaltyfunctionmethod;exponentincreasedcrossoverprobability

摘要:针对0-1非线性规划问题的特点,提出了一种适合于求解0—1非线性规划问题的改进差分进化算法.这个算法把差分进化 算法和罚函数方法有机结合起来,在变异操作中加入0-1取整运算,在交叉操作中使用了指数递增交叉概率因子以提高算法的全

局搜索能力和收敛速率.用8个例子进行了实验研究,结果表明这个改进的差分进化算法在收敛性,精度,鲁棒性强方面都比较好.

关键词:0—1非线性规划;差分进化算法;罚函数方法;指数递增交叉概率因子

DOI.10.3778/.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),外近似法等.这些方法随

着变量维数的增加,计算量会急剧增大,从而使这些算法不可

能用于实时控制,存在很大的局限性.近年来,有些学者利用罚

函数法将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√=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) 其中参数a=30,b=3.

3.4选择操作

DE采用"贪婪"的搜索策略,经过变异与交叉操作后生成

的实验个体XT与:进行竞争,只有当的适应度值较更优时

才被选作子代,否则,直接将:作为子代.选择操作切的方程为:

F(xr)<:)

others

(7)

4算法流程

综合以上对DE的改进,提出的求解0-1一NLP的改进DE

算法的流程如下:

步骤1初始化种规模^,收缩因子F,交叉概率

和～.在{0,1}实数空间内按式(3)随机初始化每一个个体.

确定惩罚因子和,罚因子放大系数c,控制误差,设置罚

函数法当前迭代计数器k=0,设置差分进化算法最大迭代次数

7,置当前迭代计数器t=0.

步骤2计算每个个体每个约束条件的惩罚量.

步骤3按式(2)计算每个个体的适应值,求出最优适应值

及最优个体.

步骤4判断是否达到罚函数法的终止条件,若是则退出,

输出最优值.否则运用差分进化算法开始迭代,执行下一步.

步骤5对:(i=1,2,…,Ⅳ)执行(6)一(8)步,生成第t+l?代

种.

步骤6在种中随机选择3个与:不同的个体,按式(4)

进行变异操作,生成变异个体.

步骤7按式(5)和(6)进行交叉操作,生成试验个体.

步骤8按式(7)进行选择操作,生成￡+1代个体.

步骤9t=t+l,返回步骤2.

5数值例子 为验证算法求解0-1非线性规划的有效性,用如下6个例

子进行实验.

例llll考虑如下的0-1线性规划问题:

min()=20xl一10x2+3

刘俊梅,高岳林,李会荣:0-l非线性规划问题的改进差分进化算法2010,46(15)45

l

+23≥2

l,2,3∈{0,1}

例211考虑如下的O-1线性规划问题:

min()__】帆2—5x3+3X4--4X5

l2

+3一4+5≤0

1,2,3,4,5∈{0,1}

例3lll考虑如下的0-1线性规划问题:

min()一6xl+5:l;