一种具有混合编码的二进制差分演化算法

被引：80

作者：

贺毅朝 ^{[1
]}

王熙照 ^{[2
]}

寇应展 ^{[3
]}

机构：

[1] 石家庄经济学院信息工程学院

[2] 河北大学数学与计算机学院

[3] 军械工程学院计算机工程系

来源：

计算机研究与发展 | 2007年 / 09期

关键词：

差分演化; 个体混合编码; 辅助搜索空间; 3-SAT问题; 背包问题;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入"差异算子"等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入"辅助搜索空间"和"个体混合编码"等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的.HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.

引用

页码：1476 / 1484

页数：9

共 11 条

[1]

蚁群算法在移动Agent迁移中的应用研究 [J].

杜荣华 ;

姚刚 ;

吴泉源 .

计算机研究与发展, 2007, (02) :282-287

[2]

基于极大极小距离密度的多目标微分进化算法 [J].

张利彪 ;

周春光 ;

马铭 ;

孙彩堂 .

计算机研究与发展, 2007, (01) :177-184

[3]

基于改进的微粒群优化算法的0-1背包问题求解 [J].

沈显君 ;

王伟武 ;

郑波尽 ;

李元香 .

计算机工程, 2006, (18) :23-24+38

[4]

特殊一维背包问题的降维替换算法研究 [J].

高天 ;

王梦光 ;

唐立新 ;

宋建海 .

系统工程理论方法应用, 2002, (02) :125-130

[5]

求解SAT问题的拟人退火算法 [J].

张德富 ;

黄文奇 ;

汪厚祥 .

计算机学报, 2002, (02) :148-152

[6]

佳点集遗传算法 [J].

张铃 ;

张钹 .

计算机学报, 2001, (09) :917-922

[7]

Evolutionary Operators in Global Optimization with Dynamic Search Trajectories.[J] E.C. Laskari;K.E. Parsopoulos;M.N. Vrahatis Numerical Algorithms 2003,

[8]

Estimation of heat transfer parameters in a trickle-bed reactor using differential evolution and orthogonal collocation[J] B.V Babu;K.K.N Sastry Computers and Chemical Engineering 1999,

[9]

Differential Evolution - A Simple and Efficient Heuristic for global Optimization over Continuous Spaces.[J] Rainer Storn;Kenneth Price Journal of Global Optimization 1997,

[10]

遗传算法的基本理论与应用[M] 李敏强等著; 科学出版社 2002,

← 1 2 →