【作者】 陈星宇；

【导师】 全惠云；

【作者基本信息】 湖南师范大学 ， 计算机软件与理论， 2008， 硕士

【摘要】 蚁群算法是一种新型求解复杂优化问题的启发式算法。该方法通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。由于蚁群具有稳健性、全局性、普遍性、分布式计算等优点,理论研究不断深入,应用领域不断扩大。理论方面主要研究算法的模型,分析其收敛性和收敛速度以及控制参数对算法性能的影响等。而应用研究也分为两类:解决组合优化问题以及用于具体应用领域。相对于理论部分,对蚁群算法的应用部分的研究则开辟了相当广阔的领域,也取得了很大的成功。本文在理论上对蚁群算法本身的理论部分进行研究,提出了几点有效的改进策略,对蚁群算法加以改进。在应用方面选取TSP问题作为典型的组合优化问题,用改进的蚁群算法求解之。最后,将算法运用于实际的物流管理中的配送路径优化问题。仿真结果表明,本改进算法在理论和实际中都是非常有效的。论文的主要工作和创新如下:在混合算法-最大最小蚂蚁算法和3-opt局部搜索算法的基础上,提出了一种改进的混合蚂蚁算法。在集中讨论了蚁群算法的数学模型基础上,并对蚁群算法提出了几点改进策略,使得本算法能比其他改进蚁群算法具有更多优越性。算法前期使用局部搜索的解初始化信息素矩阵,加快收敛速度,后期依Metropolis接受准则概率接受局部优化解,有效地避免陷入局部最优,自适应的信息素调节机制使算法更加灵活,而K近邻候选集则使之适应大规模问题求解。将改进算法应用于经典的组合优化问题TSP(TravelingSalesman Problem)问题。TSP问题是一个是一类典型的NP难问题,经常被用来验证算法的效率。在交通运输、网络等方面有着广泛的应用背景。由于TSP问题与最短路径有很多相似之处,它也是路径优化问题的研究基础。理论分析和TSPLIB中部分实例仿真结果表明,此算法求解TSP问题能比其他改进蚁群算法具有更多优越性。将改进算法应用于物流运输管理中,设计了物流配送路径优化问题的数学模型和用于优化物流配送路径的混合蚁群算法,并用实验证明了该算法对于合理生成物流配送路径有着很好的作用,通常都能够找到最优的路径。更多还原

【Abstract】 Ant Colony Algorithm is a novel heuristic algorithm to solve complicated optimization problems. It gets inspiration from nature behavior of ants in finding food. Because of its properties of robustness, global optimization, universality and distributed computation, the theoretical research is involved increasingly deep and the application becomes increasingly large. The theory part of ACO focuses on establishing the computation model of ACO, analyzing the convergence of ACO, etc. The application part of ACO generally deals with two aspects: to solve a kind of combinational optimization problem and to solve some specific real industry management problem. Compared with the theory aspect of ACO, the application aspect of ACO extends to rather wide fields and makes great success.This thesis studies the ACO algorithms theory and introduces two aspects of its applications. One is to a typical combination problem, Traveling Salesman Problem. The other aspect is an exercise in application field, Problem for Logistic Distribution. The main contributions of this thesis are:We devise IHAS, an improved hybrid algorithm combines max-min ant system (MMAS) with a local search strategy. We present the computation model of ACO and design several effective strategies. IHAS also uses adaptive pheromone trail information, neighborhood candidate list and Metropolis rulers to instruct solutions, which can speed up convergence, avoid local optimization and solve scalable instances.Introduce the IHAS to classical combinational problem TSP (Traveling Salesman Problem). TSP is a typical kind of NP hard problem to testify the efficiency of the improved algorithm. It had wide application background in transportation, network and so on. It is also the research foundation for logistic routing problem since there are some commons between TSP and the shortest path problem. Theory analysis and experimental result shows that IHAS outperforms other hybrid ant colony algorithms due to its ability to find the satisfactory results effectively when applied to the Traveling Salesman Problem.We put the improved algorithm into logistic transportation management. Design the computation model of logistic distribution routing problem and present IHAS to solve this problem. Satisfied computational result on given problems are reported, which shows that the improved ACS is useful and effective, the best path usually can be found.更多还原