蚁群算法及其应用研究

社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得简单、盲目的蚂蚁组成蚁群以后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受这种现象启发，意大利学者M.Dorigo，V.Maniezzo和A.Colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群算法。该算法的出现引起了学者们的巨大关注，在过去的短短十余年时间内，蚁群算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果。 本论文围绕蚁群算法的原理、理论及其应用，就如何改进基本蚁群算法、蚁群算法的并行实现，蚁群算法在组合优化、函数优化以及电厂主蒸汽温度控制系统等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括： 1．提出了一种回溯蚂蚁系统。该算法使用了一种新的类型的回溯蚂蚁(BA)来发现新的路径，类似于NP算法中在周围区域中的抽样。除了对信息素的轨迹量限制一个最大和最小值以防止停滞以外，该算法让蚂蚁随机的选择最好解的那一条边，并且迫使蚂蚁避免这条边，然后用周游的方法更新信息素矩阵，而不是发现的最好解。仿真实验结果证明：该算法在无论是求解对称还是非对称TSP问题都可以和MMAS算法相媲美，体现了很高的性能。 2．提出了一种多重蚁群算法。该算法是受并行遗传算法的概念所启发，在求解TSP问题时使用不同种群搜索解空间以避免局部最优从而获得全局最优。对几个TSP基准问题的仿真实验结果证实了该算法的有效性和可行性，其性能高于ACS算法。 3．针对大规模的TSP问题，提出了一种并行蚁群算法——并行蚁群系统。同以往的并行策略不同的是，该算法把并行处理的概念用之于蚁群系统。该算法把人工蚂蚁分成几个群，然后把蚁群系统应用于每一个群体，群体之间可以进行通讯，即按照邻居群所发现的最好路径来更新自己每条路径上的信息素水平。该算法不仅减少了计算时间，而且具有极高的搜索较好解的能力。仿真实验结果表明了该算法的有效性，而且其性能也远远超过了ACS算法和AS算法。 4．提出了求解函数优化问题的GAAA算法。该算法是基于遗传算法和蚂蚁算法的混合算法。其基本思路是算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布。算法后过程采用蚂蚁算法，在有一定初始信息素分布的情况下，充分利用蚂蚁算法的并行性、正反馈机制以及求解效率高等特性，提高求解效率。实验结果表明，该算法是一种时间效率和求解效率都比较好的求解函数优化问题的有效算法。 5．提出了一种求解电厂主蒸汽温度串级PID控制系统参数优化的蚁群算法。该算法针对PID参数优化的特点，把控制系统的绝对误差的矩的积分作为评价的性能指标来对控制系统进行优化；而后在蚂蚁的搜索过程中，嵌入了邻近搜索机制以搜索更优的解。实验结果证明，蚁群算法应用于主蒸汽温度PID控制器参数的优化是可行和有效的，而且比传统的方法和遗传算法具有更高的性能。 最后，对全文的研究工作进行了总结，并对蚁群算法的未来研究方向作了展望。