引用本文:肖赤心,蔡自兴,王勇.字典序进化算法用于组合优化问题[J].控制理论与应用,2010,27(4):473~480.[点击复制]
XIAO Chi-xin,CAI Zi-xing,WANG Yong.Evolutionary strategy of lexicographic order for combinational problem[J].Control Theory and Technology,2010,27(4):473~480.[点击复制]
字典序进化算法用于组合优化问题
Evolutionary strategy of lexicographic order for combinational problem
摘要点击 2123  全文点击 1380  投稿时间：2008-09-25  修订日期：2010-04-30
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  
  2010,27(4):473-480
中文关键词  字典序  组合问题  进化策略  旅行商问题
英文关键词  lexicographic order  combinational problem  evolutionary strategy  traveling salesman problem
基金项目  国家自科基金重大专项(90820302); 国家自科基金(青年)项目(60805027); 国家博士点基金项目(200805330005).
作者单位E-mail
肖赤心* 中南大学 信息科学与工程学院
湘潭大学 信息工程学院 		chixinxiao@hotmail.com 
蔡自兴 中南大学 信息科学与工程学院  
王勇 中南大学 信息科学与工程学院  
中文摘要
      为了寻求快速、高效的算法在合理的计算时间内解决大规模组合优化问题以克服目前许多算法的不足, 本文提出了一种新的编码方法, 将离散的组合空间一一映射到连续的整数区间, 结合进化策略的成熟搜索机制提高新算法的性能. 整数编码与问题的组合向量一一对应,所有编码均为可行方案, 有效避免了以往算法中的冗余运算, 进一步缩小了问题的搜索空间. 其次, 进化策略中加入了一个精英队列, 并且建立了相应的精英学习策略.在整个群体进化的同时, 精英个体也按照相应的策略不断优化, 从而有效吸收以往算法在组合优化问题上的成功经验, 有利于保留好的基因段. 最后证明了新算法以概率1收敛到全局最优. 基于旅行商问题测试库的仿真实验结果表明了算法的有效性.
英文摘要
      In order to construct a fast and effective algorithm to solve large-scale combinational problems in desirable computational time rather than be trapped in weakness as some existing algorithms, a novel encoding approach is proposed in this paper which applies an one to one mapping from a discrete space to a continuous integer section. Assembled with successful exploration and exploitation mechanism of evolutionary strategy, the performances of the algorithm are largely promoted. Since the one to one mapping between codes and combinational vectors, the new scheme only provides feasible solutions, which can help to avoid redundant computation existing in some algorithms effectively and the search space is further reduced. Secondly, a queue of elites is added in evolutionary mechanism combined with some particular learning strategy. The queue is refreshed frequently in evolution. This can help the algorithm to maintain better gene blocks. Finally, its convergence to global optimal solution with probability one is proved. The numerical experiments based on the Benchmarks of traveling salesman problem library(TSPLIB) show the effectiveness of algorithm proposed.