混合整数非线性规划问题的改进差分进化算法

基于改进蝙蝠算法的混合整数规划问题
赵乃刚;李勇
【期刊名称】《微电子学与计算机》
【年(卷),期】2017(34)6
【摘要】针对非线性混合整数规划问题,提出了一种改进的蝙蝠算法.构造出一种自适应调整的局部搜索步长,同时对整数变量采用单位步长搜索,以此逐步提高蝙蝠算法的局部开发能力;引入自然选择原理,平衡改进蝙蝠算法的全局搜索能力;初始一个可行解,保证算法的正确搜索方向.通过13个常见的测试函数测试结果表明,改进的蝙蝠算法对求解非线性混合整数规划问题,在成功率和精度方面都不亚于改进的粒子群算法.
【总页数】5页(P94-98)
【关键词】蝙蝠算法;非线性混合整数规划;自适应搜索步长;自然选择
【作者】赵乃刚;李勇
【作者单位】山西大同大学数学与计算机科学学院
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于改进果蝇算法求解混合整数非线性规划问题 [J], 朱志同;赵阳;李炜;郭星
2.混合整数非线性规划问题的改进差分进化算法 [J], 邓长寿;任红卫;彭虎
3.*1非线性混合整数规划问题的改进量子粒子群算法 [J], 张甲江;高岳林;高晨阳
4.求解一般整数规划问题的改进蝙蝠算法 [J], 马祥丽;张惠珍;马良
5.双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法 [J], 管超;张则强;朱立夏;毛丽丽
因版权原因，仅展示原文概要，查看原文内容请购买。

差分进化算法的改进研究作者：何佳欢王向东来源：《科技视界》2016年第01期【摘要】本文提出了一种改进的差分进化算法，算法采用一种新的突变方式，同时在选择操作之前引入扰动机制以增强算法的全局搜索能力。

之后对改进算法进行了Benchmark函数实验，得到的仿真结果证明了算法的有效性。

【关键词】差分进化算法；Benchmark函数；扰动【Abstract】The paper proposes a new modified Differential Evolution Algorithm， a new mutation operation is introduced in this algorithm， besides， a random disturbance mechanism is used before selection operation in order to enhance the global search ability. The modified algorithm is used to solve Benchmark functions， the effectiveness of the algorithm is demonstrated via the simulation results.【Key words】Differential Evolution Algorithm； Benchmark Function； Disturbance0 引言差分进化算法是1995年由Storn和Price提出来的一种基于种群的随机性搜索算法，差分进化算法在求解各式样的优化问题中表现出了良好的全局寻优能力[1]，同时其结构简单、操作容易，具有很多优点，但不可避免的是其容易陷入局部最优导致无法快速准确的收敛到全局最优值。

不同学者也提出了很多对差分进化算法的改进，主要有对控制参数的改进以及对突异策略的改进等[2-4]。

第29卷第1期2020年1月Vol.29No.lJan.2020湖南城市学院学报(自然科学版)Journal of Hunan City University(Natural Science)解决高维INLP和MINLP问题的混沌差分进化算法谭跃，赵政春，杨冰，肖湘(湖南城市学院信息与电子工程学院，湖南益阳413000)摘要：为改进差分进化(Differential Evolution,DE)算法的搜索能力，提出一种新的混沌差分进化算法(CGLSDE).首先，该算法利用混沌序列替换DE参数并采用混沌全局搜索算法来改进DE的全局搜索能力；其次，CGLSDE算法还采用了单维和多维的混沌局部搜索来改进DE的局部搜索能力.仿真结果表明：CGLSDE 算法在解决高维整数非线性规划(INLP)问题和高维混合整数非线性(MINLP)问题上，其性能要好于其它3种混沌差分进化算法.关键词：整数非线性规划(INLP);混合整数非线性规划(MINLP)；差分进化(DE)；混沌局部搜索；混沌全局搜索中图分类号：TP18文献标识码：A doi:10.3969/j.issn.1672-7304.2020.01.0011文章编号：1672-7304(2020)01-0053-07Chaotic Differential Evolution Algorithm for High-dimensional INLP andMINLP ProblemsTAN Yue,ZHAO Zhengchun,YANG Bing,XIAO Xiang(College of Information and Electronic Engineering,Hunan City University,Yiyang,Hunan413000,China)Abstract:To improve the search ability of differential evolution(DE),a new chaotic differential evolution algorithm(called CGLSDE)is proposed in this paper.Firstly,two methods(one is replacement of one of the parameters of DE using chaotic sequences,the other is chaotic global search)are used to improve the global search ability of DE.Secondly,in the CGLSDE,the single-dimensional and multi-dimensional chaotic local search ways are employed to enhance the local search capability of DE.The simulation results show that the CGLSDE is better than the other three chaotic differential evolution algor让hms in solving high-dimensional integer nonlinear programming(INLP)and mixed integer nonlinear programming(MINLP) problems.Key words:integer non-linear programming(INLP);mixed integer non-linear programming(MINLP); differential evolution(DE);chaotic local search;chaotic global search差分进化(Differential Evolution,DE)最初是由Storn和Price提出的，它是一种基于种群的随机搜索算法卩目前，有许多方法被提出并用于改进其搜索能力，在这些方法中，混沌差分进化算法是一类非常有效的优化算法.根据混沌的用途，常见混沌差分进化算法可分为2类.第1类是混沌全局搜索算法，它是用混沌序列来替换DE算法中的一个或多个参数以增强DE的全局搜索能力网.之所以被称为混沌全局搜索算法，是因为DE本身是一种全局搜索算法，用混沌序列替换参数没有改变它搜索的性质.第2类是混沌局部捜索算法，它是在每一代的进化过程中，对当前种群的最优解叠加一个混沌序列来产生一组新解.由于这类算法都是基于最优解来搜索新解，因而它被认为是一种局部搜索算法.根据每次搜索过程中最优解向量维数改变的情况，混沌局部搜索算法又可分为单维的混沌局部搜索旳°】和多维的混沌局部搜索[11-13],本文提出一种用于解决高维的整数非线性规划(INLP)问题和混合整数非线性(MINLP)规划问题的混沌差分进化算法，它是将上述2类混沌差分进化算法融合在一起，再采用一种混沌全局搜索而构成的混合算法.INLP和MINLP这2类问题的目标函数以及收稿日期：2019-10-12基金项目：湖南省自然科学基金资助项目(2016JJ4014)；湖南省教育厅科研项目(14B033,16C0301)第一作者简介：谭跃(1974-),男，湖南益阳人，教授，博士，主要从事进化计算研究.E-mail:tanyue7409@54湖南城市学院学报(自然科学版)2020年第1期相应的约束条件通常都是由一些非线性的函数组成.INLP问题决策变量的每一维都是整数，而MINLP问题决策变量的有些维数为整数，其它的维数则为实数.与INLP问题相比，MINLP问题更难求解.一个MINLP问题可以表示为min or max f(x,y),s.t.gj(x,y)<0,2,.知(x,刃=0,j e{1,2,...,7},<x k<x^:实数，k=\,2,...,n,y,<y,<y/:整数，/=1,2,...,/,X=[X|,X2，...,X”]T=[”，”,...,儿]丁_(1)其中，max or min表示最大最优化或最小最优化问题；x和y分别是”维的实数变量和m维的整数变量；/(x,y)为目标函数；&(x,y)和％(x,刃分别是不等式和等式约束条件；x；和y：分别是第k 维实数变量的下界和第/维整数变量的下界，球和孑是其对应的上界.求解INLP和MINLP问题可以分为确定性算法和启发式算法.确定性算法又包括分支定界算法网、扩展切平面算法问和外逼近算法问等.启发式算法，特别是那些基于种群的元启发式算法如差分进化□、粒子群优化算法[冈和遗传算法【切等深受很多学者的青睐.1一种新的混沌差分进化算法大多数学者只用了第1类或第2类混沌差分进化算法来求解某个或某类具体的优化问题.实际上，第1类混沌差分进化算法能较好地提高DE 的全局搜索能力，因为DE是一种随机的全局搜索算法；第2类混沌差分进化算法则能较好地提高DE的局部搜索能力，因为每次捜索时只基于当前种群的最优解在一个小的搜索范围内产生一个新解.根据上述2类混沌差分进化算法的特点可知,一个好的混沌差分进化算法应能同时提高DE 的全局和局部搜索能力.1.1混沌序列替换DE的参数差分进化算法包含变异、交叉和选择这3种操作，变异操作⑴表示为其中，球、瑁和瑁是种群的第G代3个不同的个体；M为种群的大小；参数F是缩放因子或变异因子，它通常为一个(0,1)的实常数.当DE求解高维的INLP和MINLP问题时，让缩放因子F保持固定不变的常数能导致种群的多样性不足，因而降低DE的全局搜索能力.为解决这一问题，可用一个变化的参数来替换缩放因子，所以采用混沌序列来实现这一目的.尽管有许多动态系统具有混沌行为，但是Logistic映射是应用最广的一种混沌系统，它被定义为z*+i=“z*(l-zQ.(3)其中，E为迭代次数；“是控制参数.当“=4,z(l)e(0,1)且z(l)H{0.25,0.5,0.75}时，式⑶表现出混沌行为.将式(3)z如替换式(2)的F时，则变异操作为讶(4)交叉操作是在新产生的变异个体评和当前种群中的个体巧之间进行的，具体为r卜；,if(rand(j)<CR)or j=rnb(j)u..=<.(5)兀;，if(rand(J)>CR)or j$rnb^j)其中，交叉因子CR可以在(0,1)的范围内变化；{1,2,...,0}中D是求解问题的维数；rand(j)是在(0,1)范围产生的一个均匀分布随机数；mb(j)是[1,D]的一个随机整数.DE根据式(6)规则在交叉操作之后产生的“：和个体疋之间执行选择操作.G+1，if/(M,C)is better than f(x：);X i=<(6)x°,otherwise.其中，/为目标函数；x严为第GH代的第j个个体.1.2混沌局部搜索在元启发式算法中通常是当前种群的最优解用于局部搜索.根据每次搜索时最优解向量维数改变的情况，混沌局部搜索可以进一步分为单维和多维的混沌局部搜索.单维混沌局部搜索每次搜索时只有最优解向量的某一维被改变，这种搜索方式实际上是一种精细搜索；多维混沌局部搜索在每次搜索时最优解向量的每一维都会发生改变，与单维混沌局部搜索相比，它能执行范围更大的局部搜索.一个同时具有单维和多维搜索能力的混沌局部搜索算法可以描述为BeginZ]=randFor z=l to M lz,+=“z,(l-zjIf rand<0.5%执行多维混沌局部搜索For j=l to D第29卷谭跃，等：解决高维INLP和MINLP问题的混沌差分进化算法55Pu=bSj+az M.(7) End ForElse If%执行单维混沌局部搜索Pi=bsr=rand int(l,£>)Pi.r=bS r+-⑻End IfEnd Fora=max(/(p,.)),i=l,2,-M L.(9) If a >f(bs)bs=p b.(10) End IfEnd其中，是一个(0,1)范围的随机数，且rand*{0.25,0.5,0.75};M L为总的混沌局部搜索次数；D表示求解问题的维数.式(7)中表示第i次多维混沌局部搜索产生的解向量的第丿维；臨为当前种群最优解向量加的第丿维；a是一个控制多维混沌局部搜索步长的参数；而rand int(l,Q)表示在［1,D］产生的一个随机整数D.式(8)中表示第i次单维混沌局部搜索产生的解向量的第『维；参数0用于控制单维混沌局部搜索的步长.式(9)中/是目标函数；。

用粒子群优化改进算法求解混合整数非线性规划问题
刘钊;康立山;蒋良孝;杨林权
【期刊名称】《小型微型计算机系统》
【年(卷),期】2005(26)6
【摘要】针对混合整数非线性规划(MINLP)问题,改进了粒子群优化算法(PSO),提出了一种粒子迁移策略,改进了粒子速度更新策略,使之成为一种解决MINLP问题的新算法.实验表明,新算法精确度好、收敛快.
【总页数】4页(P991-994)
【作者】刘钊;康立山;蒋良孝;杨林权
【作者单位】武汉科技大学,计算机科学与技术学院,湖北,武汉,430081;中国地质大学,计算机科学与技术系,湖北,武汉,430074;中国地质大学,计算机科学与技术系,湖北,武汉,430074;中国地质大学,信息工程学院,湖北,武汉,430074
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于改进果蝇算法求解混合整数非线性规划问题 [J], 朱志同;赵阳;李炜;郭星
2.求解混合整数非线性规划问题的改进差分进化算法 [J], 吴亮红;王耀南;陈正龙
3.一种求解混合整数非线性规划问题的演化算法——搜索空间自动收缩法 [J], 曾三友;康立山;丁立新
4.一种求解混合整数非线性规划问题的模拟退火算法 [J], 杨若黎;吴沧浦
5.求解带有等式约束的混合整数非线性规划问题的粒子群算法 [J], 罗祎青;袁希钢
因版权原因，仅展示原文概要，查看原文内容请购买。

一种改进的差分进化算法丁晓阳;李嵩华【摘要】针对基本差分进化算法收敛速度较慢的问题,将粒子群优化算法中的社会学习部分引入到差分进化算法中,提出一种改进的差分进化算法.该算法通过小概率随机变异操作增加种群的多样性和全局搜索能力;变异向量和个体向群体最优个体学习的结果进行交叉操作,利用最优个体指导进化过程,加快了算法的收敛速度,提高了优化精度.仿真实验结果表明,该算法具有更好的优化性能.【期刊名称】《陕西师范大学学报（自然科学版）》【年(卷),期】2016(044)001【总页数】6页(P1-6)【关键词】群体智能;差分进化算法;粒子群优化算法;随机变异;学习因子;多样性【作者】丁晓阳;李嵩华【作者单位】兰州财经大学信息工程学院,甘肃兰州730020;兰州财经大学信息工程学院,甘肃兰州730020【正文语种】中文【中图分类】TP181差分进化算法(differential evolution，DE)是由Rainer Storn和Kenneth Price 在1995年共同提出的一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法[1]。

DE原理简单，受控参数少，实施随机、并行、直接的全局搜索，易于理解和实现。

近年来，在约束优化计算、模糊控制器优化设计、神经网络优化、滤波器设计等方面得到了广泛的应用。

但是,与其他随机优化算法类似，DE仍存在着搜索停滞和早熟收敛等缺陷，因此，很多学者通过改进变异策略[2-10]、优化交叉策略[11-13]及引入其他算法的先进进化方式[14-17]对基本差分进化算法进行改进。

例如，文献[2]提出一种用于求解0-1规划问题的二进制差分进化算法，该算法在进化过程中无需变异率，即可根据个体间的差异直接在离散域内进行变异。

文献[3]设计了一个基于符号函数的多策略变异算子，用正负随机数代替原有的变异率，实现了两个方向上的随机搜索。

文献[4]改进了差分进化算法的变异操作，采用随机选择的方式进行变异和扰动操作。

混合差分进化算法
混合差分进化算法（HDE）是一种优化算法，它将差分进化算法和其他元启发式算法相结合，用于解决各种优化问题。

该算法使用差分进化算法的核心思想，即使用种群中的个体进行交叉和变异来生成新的解决方案，并通过选择策略来更新种群。

同时，该算法还引入了其他元启发式算法的特点，如局部搜索和全局搜索，以提高算法的收敛性和搜索效率。

HDE算法的基本步骤包括初始化种群、差分进化操作、局部搜索和全局搜索。

在初始化种群阶段，算法随机生成一组初始解，并将其作为种群的初始个体。

接下来，算法使用差分进化操作来生成新的解决方案。

该操作包括选择三个随机个体，然后将它们进行差分和加权操作，以生成新的解决方案。

然后，算法使用局部搜索来改善新的解决方案，并使用全局搜索来跳出局部最优解。

HDE算法的优点是它可以有效地克服传统优化算法的局限性，并提高搜索效率和收敛性。

此外，该算法还具有较好的适应性，可以针对不同的问题进行调整和优化。

因此，HDE算法已成为一种广泛应用的优化算法，在许多领域都有着实际应用。

- 1 -。

0-1非线性规划问题的改进差分进化算法ComputerEngineeringandApplications计算机工程与应用2010,46(15)430-1非线性规划问题的改进差分进化算法刘俊梅,高岳林1,李会荣1,2LIUJun-mei,GAOYue-lin',LIHui-rong,1.北方民族大学信息与系统科学研究所,银川7500212.商洛学院数学与计算科学系,陕西商洛7260001.ResearchInstituteofInformation&amp;SystemScience,NorthNationalUniversity,Yinc huan750021,China2.MathematicsandComputerScienceDepartment,ShangluoAcademy,Shangluo,Shaanxi 726000,ChinaE-mail:***********************LIUJun-mei.GAOYue-lin.LIHui-rong.Improveddifferentialevolutionalgorithmof0-1no nlinearprogrammingprob-puterEngineeringandApplications.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中图分类号:TP181引言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)s.t.()--&lt;0,i=1,2,…,m(1)()=0√=1,2,…,1基金项日:国家自然科学基金(theNationalNaturalScienceFoundationofChinaunderGrantNo.60962006);宁夏自然科学基金项目资助(NnNzO848).作者简介:刘俊梅(1980一),女,硕士,研究方向:最优化理论及应用,智能计算及应用;高岳林(1963一),男,教授,博士,研究生导师,研究方向:最优化理论方法及应用,智能计算及应用,金融数学与金融工程.收稿日期:2008—12—04修回日期:2009—02—18442010,46(15)ComputerEngineeringandApplwations计算机工程与应用xi=Oor1,i=1,2,…,D式(1)中:(…,),岛()为不等式约束条件,hi(x)为等式约束条件.这些约束条件通常都是非线性的,因而O-1NLP问题一般难以求解.对约束条件的处理,一般采用简单有效的惩罚函数法『l11,将带约束条件的原0-INLP问题转化为无约束问题来求解.经惩罚函数转化后的无约束问题可定义为:f,))十∑()十∑()&gt;:(2)j=l/=1式(2)中和为大于零的惩罚因子.&lt;gi&gt;+=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)&lt;:)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≥2s.t.2x1+23≤6l,2,3∈{0,1}例211考虑如下的O-1线性规划问题:min()__】帆2—5x3+3X4--4X5s.t.3xl一2x2+7x3—5x4+缸5≤6l2+3一4+5≤01,2,3,4,5∈{0,1}例3lll考虑如下的0-1线性规划问题:min()一6xl+5:l;s.t.l慨2—2x3≤53xl+5x2—7x3≤一5l,2,3∈{0,1}例4求0-1二次规划minf4():Ox,{0,1},其中15—4-4—1712Ol2110221l-25—8l一83O一51—5-20实验中种群规模Ⅳ取变量维数的10倍,F=0.5,:0.5,CR…=O.9,最大迭代次数都为T--30,惩罚因子,:10;控制误差s=10,罚因子的放大系数c=10,为减小随机干扰,每一问题都重复10次实验.下面为文献『1】中的最速下降法(Steep—estDescentMethod,SDM0)以及提到的改进差匕算法(Mod—ifiedDE,MDA)两种算法对4个问题所求的最优解,最优值,达优率,运行的平均时间,迭代次数的比较统计表.从表1中可以看出新算法对于低维(3-5维)很快找到了最优解,同时也不需要初始点.与文献[1]中相比特别是例2,文献[1]中利用最速下降法迭代9次时才得到局部最优解=(1,1,0,1,1),最优值为厂()=一2,而利用提到的MDE算法迭代1次就能得到最优解=(0,0,1,1,1),得到的全局最优值f(x)一6,从而显示了新算法的有效性.表1MDE算法与文献【1]巾的SDM算法结果比较表例5考虑如下的0-1非线性规划问题min()=1T十Ⅱ"I's.t?21一.1'2,…,肘,∈{0,1}i=1,2,…,的随机数,j=l,2,…,n,m=l,2,…,.例6考虑如下的0-1非线性规划问题:minf6()…20exp[0.2∑cos(2)]-exp('jD——)+20+es?t?1Z2T≤tm~ln=1,2,…,∈{0,1}1,2,…,H例7考虑如下的0-1非线性规划问题:Jminf7():∑一10c.s(2)+101l仁l【n『s-t.}≤,m=1,2,…,J—JlI∈{0,1}=1,2,…,n例8考虑如下的O-1非线性规划问题:mi0一cos()+ls.1.1∑,,m:1,2,…,J=1∈{0,1J=1,2,…,对例5,例6,例7,例8每次实验运行的最大迭代次数为5O,蹦因子u=10,控制误差g=10,罚因子的放大系数c=10,上面三个例子中…d,t的取值和例5中的取法一样.测试问题的规模(n,)从(10,5)到(300,80)变化,每组实验对同一次产生的随机变量(即同一非线性规划问题)运行l0次,分别从所求问题最优近似值,平均最优近似值,以及标准差,CPU运行的平均时间进行比较,结果如表2～表5.表2例5的测试结果表3例6的测试结果从表2～表5可以看出,随着问题规模的增大,约束条件的增多,对随机产生的同一非线性规划问题算法都经过一次搜索就基本上找到了最优解,而且能在很短时问内达到,显示了改进差分进化算法对0一l非线性规划的适应性,有效性.用随机产生的例子来测试算法的计算可行性,其中(Q)吣讥,(),()一中的元素分别是卜1,0】,[一3,一21;~I111,5】中的随机6结论产生的随机数,和t分别为f0,10],[400,500】中的随机产生对DE算法的变异矢量用四舍五入方法进行取整运算,使∑D,V462010,46(15)ComputerEngineeringandApplications计算机工程与应用表4仞7的测试结果改进的DE算法适应于求解0—1线性规划和0-1非线性规划问题.为保证种群的多样性和提高算法的收敛速度,采用指数递增交叉概率因子的方法.对8个典型0—1线性规划和0-1非线性规划问题.测试结果表明,改进的DE算法收敛速度快,精度高,全局搜索鲁棒性好,是一种求解0—1线性规划和0—1非线性规划问题的有效方法,可广泛应用于各种实际问题中.参考文献:【1】AnjidaniM,EffatiS.Steepestdescentmethodforsolvingzero-one nonlinearpmgranamingproblems[J1.AppliedMathematicsandCom——putation,2007,193:197—202.【2】陈国华,廖小莲.0—1非线性混合整数规划的罚函数解法叨.应用数学与计算数学,2007,21(1):1l1-115.f3】隋允康,贾志超,杜家政.非线性O一1规划问题的连续化及其遗传算法解法【Jj_北京工业大学,2008,34(8):785—791.【4】PriceKV.Differentialevolution:Afastandsimplenumericalopti—mizer[C]//Proceedingsofthe1996BiennialConferenceoftheNorth AmericanFuzzyInformationProcessingSociety,1996.[5]StornR,PriceK.Differentialevolution—asimpleandefficientadap—tireschemefor0baloptimizati0novercontinuousspaces[R].Teeh—nicalReportInternationalComputerScienceInstitute,Berkley,1995.[6]刘军民,高岳林.基于混沌搜索的差分进化算法fJ】计算机工程与应用,2008,44(12):66—68.【7】李珂,郑金华.一种改进的基于差分进化多目标进化算法[J].计算机工程与应用,2008,44(29):51—56.[8]陈文霞,龚文引,蔡之华.正交差分演化算法在工程优化设计中的应用叨.计算机工程与应用,2008,44(18):230—235.【9]LinYung-Chien,HwangKao-Shing,WangFeng-Shen昏Amixed--cod—ingschemeofevolutionaryalgorithmstosolvemixed-integernon-linearprogrammingproblems[J】.ComputersMathApplie,2004,47(8-9):1295—1307.【l0]吴亮红,王耀南,陈正龙.求解混合整数非线性规划问题的改进差分进化算法们小型微型计算机系统,2007,19(4):92—95.[11]袁亚湘,孙文瑜撮优化理论与方法[M】.北京:科学出版社,1997. [12】徐宗本.计算智能——模拟进化计算【M].北京:高等教育出版社, 2O05.(上接42页)有—个合理的上限.但是对于内存受限不便于进行预计算,或者是日(n)本身就特意选择很小的情况,窗口宽度为W的NA(n)计算并不能显着提高运算速度.在该文的算法中,并没有采用投影坐标,因为采用投影坐标并不能提高计算速度,只要在最后一步一次进行一次求逆运算就可以了.参考文献:[1】ShamirA.Identity—basedcryptosytemsandsignatureschemes[C AdvacesinCryptologyCrypto'84.IS.1.]:Springer-V erlag,1984:47-53. 【2】BonehD,FranklinM.Identity—basedencryptionfromtheweilpar—ing[C]//KilianJ.AdvancesinCryptology--Crypto2001.Berlin,Hei—delberg:Springer—V erlag,2001:213—229.[3】MenezesA.Anintroductiontopairing-basedcryptography[EB/OL]. http://www.cacr.math.uwaterloo.ea/-ajmeneze/publications/pairlngs.pdf. f4】DuttaR,BaruaR,SarkarP.Pairing—basedcryptographicprotocols:A survey,Report2004/064[R/0L].CryptologyePrintArchive,2004.http:// /2004/064.pdf.【5】PatersonKG,PriceG.Acomparisonbetweentraditionalpublickey infrastructuresandidentity-basedcryptography[J].InformationSeeuri- tyTechnicalReport,2003,8(3):57—72.[6】BlakeIF,SeuoussiG,SmartNP.Advancesinellipticcurvecryp- tography[M].NewY ork:CambridgeUniversityPress,2005.【7】SilvermanJH.Thearithmeticofellipticcurves[M].Beijing:Beijing WorldPublishingCorporation,1999,[8】LipmaaH,MaoWenbo,JakobssonM.Cryptographicprotocols:Techniques forsecureprotocoldesign[M].【s.1.]:Prentice-Hall,2006:114—147.[9]9MaasM.Pairing-basedcryptography[D].TechniseheUnivemiteitEind—hoven,2004.【lO]ScottM.Implementingcryptographicpairings[EB/OL].fro://ftp.tom—puting.dcu.ie/pub/resources/crypto/pairings.pdf.[11]GalbraithSD,HarrisonK,SolderaD.Implementingthetatepair—int~EB/OL]./techreports/2002/HPL-2002-23.pdf. 【12]HwuJing—Shyang,ChenRong-Jaye,LinYi—Bing.Anefficientiden- tity—basedcryptosystemforend—to-endmobilesecurity[11.IEEE TransactionsonWirelessCommunications,2o06,5(9):2586—2593.【13]BarretoPSLM,KimHY,LynnB,eta1.Efficientalgorithmsforpairing-basedcryptosystems,Report2002/O08[R/OL~CryptologyePrlnt Archive,2002.http://eprint.iacr.or~2002/008.pdf.[14】BlakeI,MurtyK,XuG.RefinementsofMiller'salgorithmforcom—putingWeil/Tatepairing,Repoa2004/065[R/OL].CryptologyePrint Archive,2004./2004/065.pdf.[15】HankersonD,MenezesA,Vanstones.椭圆曲线密码学导论[M].北京:电子工业出版社,2005:90—97.。