元胞蚂蚁算法及其应用研究

【作者】 朱刚；

【导师】 马良；

【作者基本信息】 上海理工大学 ， 管理科学与工程， 2007， 博士

【摘要】 旅行商问题、度约束最小树问题、二次分配问题、图着色问题等是迄今为止仍悬而未决的NP-难题,具有极大的挑战性。这些问题在实际生活中有着广泛的应用,寻找有效的算法就显得更为重要。近年来,一系列来自自然界的演化型算法,典型的有:遗传算法、模拟退火算法、禁忌搜索法、蚂蚁算法、粒子群算法、免疫算法等,为解决这些问题提供了一种手段。蚂蚁算法于1991年首次提出的,1996年起正式发表在国际学术期刊上。蚂蚁算法以TSP为测试基准,与其它一些常用启发式方法作了一系列的比较,实验结果体现了其强大的寻优搜索能力,并已在一系列困难的组合优化问题求解中取得了成效。元胞自动机是冯诺伊曼最早提出的“用于模拟生命系统所具有的自复制功能”,沃尔夫勒姆等人将动力系统方法和计算理论及形式语言方法用于元胞自动机的研究中,促进其广泛应用,尤其是其大规模的仿真计算能力为研究复杂系统的行为提供了有效的虚拟实验室。本文将立足于蚂蚁算法(Ant Algorithm),并结合元胞自动机(Celluar Automata)原理,针对一般连续和离散优化问题,提出一种全新的元胞蚂蚁算法。从理论上探索了算法的收敛性,并从实验角度验证算法的有效性,同时对多目标问题进行了探索。本文为系统科学、人工智能、优化理论以及复杂性科学等一系列跨学科领域的发展提供了新的思想方法,同时为工程技术、社会经济(如城市交通、物流配送)等范畴内的相关问题提供有效的基本解决工具和手段,具有广泛的经济和社会效益。本文的具体内容包括:第一章给出了论文的研究背景和内容;第二章概述了计算复杂性和演化类算法的几种主流思想及其研究现状;第三章介绍了蚂蚁算法和元胞自动机的原理;第四章介绍元胞蚂蚁算法,首先给出连续元胞蚂蚁算法的数学描述和实例测试,然后给出离散元胞蚂蚁算法的描述,并对TSP库的数据进行实例验证,最后讨论若干扩展TSP的求解方法;第五章介绍随机泛函分析基础,给出连续和离散元胞蚂蚁算法的收敛性的论证;第六章主要讨论多目标的元胞蚂蚁算法;第七章对论文进行总结,并对进一步的研究方向进行展望。总之,本文的研究从理论上提出了求解组合优化难题的新算法并给出算法收敛性的数学论证,在应用上为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。更多还原

【Abstract】 This area of research contains many unsolved famous problems that have great challenges, such as those so called NP-hard problems like the traveling salesman problem, degree-constrained minimum spanning tree problem, quadratic assignment problem, graph coloring problem etc. Since these problems have many applications in real situations, it is quite important to find some applicable algorithms. In recent years, there appeared several evolutionary algorithms for solving the NP-hard problems from nature in this field, typically like simulated annealing, genetic algorithm, tabu search, ant algorithm, etc.Ant colony algorithm was first proposed in 1991 and published at international magazine in 1996. Compared with other bionical algorithms for TSP, the ant algorithms have some good properties as a searching optimization approach in some test experiments and solving different discrete systems optimization problems successfully. The concept of cellular automata were first proposed by Von Neumann in simulating system of living with reproducing. Wolfram et al took the method of dynamic system, computational theory and the method of form language for studying the cellular automata. Cellular automata were applied in many fields and have provided effective virtual laboratory in the field of large-scale simulation computing for studying the behavior of systems.This dissertation proposes a new algorithm -- cellular ant algorithm-- for function and discrete systems optimization based on ant algorithm and cellular automata.The dissertation gives convergence analysis for cellular ant algorithm and numerical simulation that show the algorithm is robust and efficient, and extends the application area to the multi-objective optimization.The dissertation provides a new method for systems science, artificial intelligence, optimization theory and complexity science, and provides effective and basic tools and methods for many fields of engineering technology and social economy with wide effects.The contents of the dissertation includes:Chapter 1 gives the background and the contents of the whole dissertation.Chapter 2 generally introduces computational complexity and surveys some main ideas of evolutionary algorithms and their development. Chapter 3 describes the basic principles of ant algorithm and Cellular Automata.Chapter 4 proposes a new optimization algorithm—cellular ant algorithm. Firstly the function optimization, then discusses the discrete systems optimization, like classical TSP, lastly discusses the resolution of some extended TSP. These problems include bottleneck TSP, minimum ratio TSP, time-constrained TSP. Large number of tests and comparisons show the effectiveness of the searching strategy.Chapter 5 gives convergence analysis for cellular ant algorithm of function and discrete systems based on the theory of random fixed point, and makes the relevant theoretical foundation of the convergence property of the algorithm.In Chapter 6, a cellular ant algorithm for solving multi-objective function optimization is presented. The algorithm can be used for solving the multi-objective function and discrete systems optimization. The simulation results show that the algorithm can efficiently reach the true Pareto frontier.In short, the research results of the dissertation theoretically provides a new kind algorithm for NP-hard problems and gives convergence proof of the algorithm. Practically, the dissertation develops a series of strategies for solving different systems optimization problems.更多还原