蚁群算法是20世纪90年代初期提出的一种新型模拟进化算法,其思想吸收了真实蚂蚁的行为特性,通过模拟真实蚁群搜索食物的过程来完成对问题的求解。它采用有记忆的人工蚂蚁,通过个体间的信息交流与相互协作找到从蚁穴到食物源的最短路径。这种方法是由意大利学者Dorigo M等人首先提出的,他们称之为蚁群系统(Ant Colony System, ACS)。根据蚁群算法的特点用该算法求解旅行商问题(Traveling Salesman Problem, TSP)、指派问题(Assignment Problem)、Job-Shop调度问题等等一系列经典问题,经证明取得了一系列较好的实验结果,蚁群算法现已广泛应用到很多领域。多态蚁群算法是在针对蚁群算法收敛速度慢、容易陷入局部最优等缺点的基础之上,通过对蚁群社会的仔细研究发现,真实蚁群社会中的所有蚂蚁不仅各司其职,而且相互依赖、相互协作,相互之间形成一个有机的整体。在执行某项任务时,个体之间会通过各自分泌的信息素相互联系、相互协作。这里的“多态性”是指蚁群社会所具有多种状态的蚂蚁群体及信息素。根据分工的不同将蚂蚁分为:侦察蚁、搜索蚁和工蚁,各种蚂蚁各司其职。其中,侦察蚁群负责局部侦察,搜索蚁群负责全局搜索。这种改进大大提高了蚂蚁群体之间的合作效果,增强了算法的有效性。模拟退火算法是1982年由S.Kirkpatrick等人提出的一种模拟金属退火机理而建立的随机优化方法。它是源于对固体退火过程的直接简单模拟而建立的一种通用随机搜索技术,具有较强的局部搜索能力,并能避免陷入局部最优解。正是由于这种优势的存在,人们成功地将该思想引入组合优化理论,近年来该算法引起了大规模优化设计、数值分析、复杂布局等领域广泛的重视。本文对蚁群算法尤其是多态蚁群算法进行了较为系统地分析和研究,提出了三种改进的算法,并将改进的多态蚁群算法应用到复杂迷宫的路径求解中,主要包括以下一些内容:(1)蚁群算法的概述。介绍了蚁群算法的研究背景及其意义、算法的功能、思想来源、国内外研究现状以及典型应用等等。(2)蚁群算法的研究。介绍了蚁群算法的三种基本模型,蚁群算法最早应用到旅行商问题当中,简要介绍了旅行商问题,及蚁群算法基于旅行商问题的实现步骤以及算法复杂度分析。(3)多态蚁群算法的模型与实现。介绍了多态蚁群算法提出的背景,多态蚁群算法的模型,多态蚁群算法存在的不足。(4)基本蚁群算法及多态蚁群算法的改进。基于基本蚁群算法和多态蚁群算法存在的不足,提出了三种改进的蚁群算法:自适应调整挥发系数的逆向蚁群算法、基于模拟退火算法的多道逆向蚁群算法和基于信息素扩散的多态蚁群算法。试验结果证明改进的算法提高了收敛速度和寻找到最优解的能力。(5)结合蚁群算法在寻找最优路径上的优势,将改进后的多态蚁群算法运用到复杂迷宫的求解最优路径当中。理论分析和试验结果证明该算法能较好的找到最优路径。