字典序进化算法用于组合优化问题

Evolutionary strategy of lexicographic order for combinational problem

中文关键词  字典序  组合问题  进化策略  旅行商问题

英文关键词  lexicographic order  combinational problem  evolutionary strategy  traveling salesman problem

中文摘要

      为了寻求快速、高效的算法在合理的计算时间内解决大规模组合优化问题以克服目前许多算法的不足, 本文提出了一种新的编码方法, 将离散的组合空间一一映射到连续的整数区间, 结合进化策略的成熟搜索机制提高新算法的性能. 整数编码与问题的组合向量一一对应,所有编码均为可行方案, 有效避免了以往算法中的冗余运算, 进一步缩小了问题的搜索空间. 其次, 进化策略中加入了一个精英队列, 并且建立了相应的精英学习策略.在整个群体进化的同时, 精英个体也按照相应的策略不断优化, 从而有效吸收以往算法在组合优化问题上的成功经验, 有利于保留好的基因段. 最后证明了新算法以概率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.