改进的遗传混合蚁群算法在TSP问题中的应用.doc

摘要: 为了提高基本蚁群算法的收敛性能和全局求解能力,对基本蚁群算法进行了改进,提出了一种改进的遗传混合蚁群算法。在每代进化中保留最优解和次优解的公共解集后引入遗传操作中的交叉算子进行运算,并采用自适应改变信息素挥发系数的方法,加快了算法收敛速度,提高了解的全局性。通过对 TSP 问题的仿真运算表明,改进的遗传混合蚁群算法在收敛速度和解的全局性上都有较大的改善。
中国论文网
关键词: 蚁群算法; 遗传算法; 交叉算子; 自适应; TSP
中图分类号:TP391 文献标志码:B 文章编号:1006-8228(2012)11-31-02
Application of improved ic hybrid ant colony algorithm in TSP
Xu Deming
(Huizhou University, Huizhou, Guangdong 516007, China)
Abstract: To improve the efficiency of convergence and the global ability of basic ACA, a novel hybrid algorithm is proposed, which is an bination of GA and ACA. Cross operator is calculated after reserving the intersection of the best solution and the second best solution in every evolution, and the adaptive change pheromone volatile coefficient is affected. Convergence speed is accelerated and the global ability of the algorithm is improved. The simulations for TSP problem show that the improved algorithm has better convergence efficiency and global ability.
Key words: ant colony algorithm(ACA); ic algorithm(GA); cross operator; the adaptive change; TSP
0 引言
旅行商问题(Traveling Salesman Problem,TSP)又称货郎担问题,是一个著名的组合优化问题,也是一个典型的、易于描述却难于处理的NP完全问题[1]。由于该问题的实际模型在路径、网络、分配、基因测序和机器人控制等方面有着广泛的应用[2],故长期以来一直吸引着许多领域的研究人员对其算法改进的关注。
蚁群算法是一种求解组合最优化问题的新型通用启发式方法,该方法具有正反馈、分布式计算和贪婪启发式搜索的特点。由于蚁群算法容易出现停滞现象,即搜索进行到一定程度后,所有个体所发现的解完全一致,不能对解空间进一步搜索,不利于发现更好的解,而且蚁群中多个个体的运动是随机的,当群体规模较大或网络结构较为复杂时,要找