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

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