摘要
提出一种求解旅行商(TSP)问题的新型分散搜索算法.将蚁群算法(ACO)的构解方法引入分散搜索(SS)算法,在搜索过程中既考虑解的质量,又考虑解的分散性.采用一种将蚁群算法的信息素更新技术与分散搜索的组合机制相结合的新型子集组合成新解的构解机制,同时采用动态更新参考集与临界准则策略来加快收敛速度.实验结果表明,该算法优于其他现有的方法,获得了较好的结果.
A scatter search algorithm is presented. The solution construction mechanism of ant colony optimization （ACO） is introduced into scatter search （SS）. Both solution quality and diversification are considered. A new mechanism of the subset combination method is applied simultaneity, which hybridizes the mechanism of the pheromone trail updating with the combination mechanism of scatter search to generate new solutions. The dynamic updating strategy and the criterion of threshold are adopted to accelerate the convergence. The experimental results show that the method is more efficient and competitive compared with the existing methods in terms of solution quality.
出处
《控制与决策》
EI
CSCD
北大核心
2008年第7期762-766,共5页
Control and Decision
基金
国家自然科学基金项目(60674084)
国家杰出青年科学基金项目(70425003)
国家863计划项目(2006AA04Z174)
关键词
旅行商
蚁群算法
分散搜索
Traveling salesman problem
Ant colony optimization
Scatter search
