【作者】 何雪海；

【导师】 胡小兵；

【作者基本信息】 重庆大学 ， 计算数学， 2011， 硕士

【摘要】 组合优化问题的解决在理论和实际应用领域都有非常重要的地位。随着问题规模的扩大,因为计算复杂度的问题,如果使用确定性算法很多组合问题的最优解是无法实现的。蚁群优化元启发式算法是一种专门针对难解的离散优化问题的理想方法,它能在合理的时间得到能够接受的解。蚁群优化算法具有正反馈、分布式、鲁棒性强、易于与其它算法结合的优点。理论上讲,经过适当转化,蚁群优化算法可以解决任何组合优化问题。从最初的蚂蚁系统发展到现在众多的改进蚁群算法,蚁群算法在性能上已经取得了很大的进步。其应用已经涵盖了组合优化、连续函数优化、网络路由、机器学习、图像处理等众多学科。本文主要围绕蚁群优化的原理、基本蚁群算法的改进、蚁群优化理论。就如何改进蚁群算法性能,如何改进算法的全局搜索能力进行了深入的研究。此外还总结了蚁群优化应用规则和使用蚁群优化求解问题的一般步骤,最后给出了一些典型的应用实例。主要研究成果如下:提出一种改进蚁群算法,在转移概率公式中引入一个新的自适应因子以避免算法陷入局部最优解。随着迭代次数的增加,该因子有利于蚂蚁探索较弱信息素浓度的边而避免信息素浓度过度积累。这一特性使蚂蚁在迭代后期仍能以较高概率搜索到更好的解。仿真实验显示,改进后算法对解决旅行商问题有更优的全局搜索能力。更多还原

【Abstract】 Discrete optimization plays a great role both in thoery and application. It’s almost impossible to retain the optimal solution with deterministic algorithm especially when the scale of the problem is very large. Ant colony optimization(ACO) belongs to meta-heristic algorithms and it can help us to obtain a reasonable optimal solution. ACO has such features as positive feedback, parallel computing,robustness and so on.Any discrete optimization can be settled by ACO if modified properly. Great breakthrough has been made in performance of ACO since the appearance of ant system. Its application includes discrete optimization, net routing, machine learning, image processing and so on.This paper concentrates on the principle of ACO, improved versions of ant system,the theory, as well as stategies to improve the performance of the algorithm. The discipline and the main steps to apply ACO are also discussed in the paper. Besides, some instances are given to illustrate the great performance of ACO. The main contribution comes as follows:An improved Ant Colony System (IACS), which employed a new factor in transition rule to overcome the premature behavior in (ACO) is proposed. The factor can help the ants to obtain a better result by exploring the arc with low pheromone trail accumulated so far as time elapses. Besides, it can avoid the over-concentration of pheromone trail to enlarge the searching range. Simulation results shows that the IACS has better performance in solving the Traveling Salesman Problems (TSP) and more outstanding global optimization properties.更多还原