字典序进化算法用于组合优化问题
肖赤心1
蔡自兴2
王勇2
1.中南大学信息科学与工程学院,湖南长沙410083;湘潭大学信息工程学院,湖南湘潭4111052.中南大学信息科学与工程学院,湖南长沙,410083
摘要：为了寻求快速、高效的算法在合理的计算时间内解决大规模组合优化问题以克服目前许多算法的不足,本文提出了一种新的编码方法,将离散的组合空间一一映射到连续的整数区间,结合进化策略的成熟搜索机制提高新算法的性能.整数编码与问题的组合向量一一对应,所有编码均为可行方案,有效避免了以往算法中的冗余运算,进一步缩小了问题的搜索窄间.其次,进化策略中加入了一个精英队列,并且建立了相应的精英学习策略.在整个群体进化的同时,精英个体也按照相应的策略不断优化,从而有效吸收以往算法在组合优化问题上的成功经验,有利于保留好的基因段.最后证明了新算法以概率1收敛到全局最优.基于旅行商问题测试库的仿真实验结果表明了算法的有效性.
关键词：字典序组合问题进化策略旅行商问题
分类号：TP301(计算技术、计算机技术)
资助基金：国家自然科学基金(90820302)国家自然科学基金(60805027)高等学校博士学科点专项科研基金(200805330005)
论文发表日期：2010-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：8( 473-480 )
英文信息