最大团问题的蚁群算法研究

最大团问题的蚁群算法研究I目 录摘 要 .IIIABSTRACT.IV引言 .1第一章 绪论.21.1 研究背景 .21.2 蚁群算法的研究历史和现状 .31.3 论文研究目的及主要内容.5第二章 蚁群算法 .72.1 概述 .72.2 蚁群算法基本原理 .72.3 蚁群算法框架.92.4 本章小结 .14第三章 最大团问题的新型蚁群算法 .153.1 最大团问题 .15最大团问题的蚁群算法研究II3.2 新型蚁群算法基本思想简介 .153.3 最大团问题的新型蚁群算法 .193.4 实验结果及结论 .243.5 本章小结 .25第四章 蚁群算法的参数研究 .264.1 ACO 算法中参数的研究 .264.2 蚁群算法参数最优组合的“三步走”方法 27.314.3 本章小结 .32结论 .32致谢.34参考文献 .35最大团问题的蚁群算法研究III摘 要组合优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点问题。对于NP-完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一种新的启发式算法，它具有正反馈、自组织、分布式计算以及结构性的贪心启发等特点。其中正反馈使得它能很快搜索到比较好的解；分布计算避免了算法陷入局部收敛而不能继续优化；而贪心启发机制使它能在寻优的早期阶段就搜索到可接受的解。因而蚁群算法能够成功地应用于解决许多NP-完全的组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算法应用于求解图的最大团这个经典的NP-完全组合优化问题，在本文中我主要做了以下工作：1、 在了解蚂蚁的社会形态、群体行为等生物学特征的基础上，认真研究了蚁群算法的思想起源、发展现状、以及其应用情况。2、 从深层意义上分析蚁群算法机制的原理，研究其基本的数学模型和具体实现步骤。3、 根据最大团问题的特点，给出了求解最大团问题的蚁群算法解决方案，编写程序，用DIMACS benchmarks中的部分实例进行了仿真验证。4、 根据大量实验结果对蚁群算法的参数选择进行了研究。关键词：蚁群算法 组合优化 最大团 启发式算法最大团问题的蚁群算法研究IVAbstractMany combinatorial optimization problems, which are fundamental and important in science and engineering calculation, are NP-complete problems. The solution of these problems has been the key problems in the study of algorithm theory. For NP-complete combination optimization problems, there is no efficient algorithm to the solution of the problems now. Consequently, heuristic algorithms may be used to solve such type of problems. As a new heuristic algorithm, Ant Colony Optimization (ACO) algorithm whose main characteristics are positive feedback, distributed computation and constructive greedy heuristic can solve many NP-complete combination optimization problems successfully. For the positive feedback makes it be able to very quickly search the better solution;Distribute computation avoided the calculate way sink into the part refrain from rash action and cant continue the optimization;And the constructive greedy heuristic makes it able to search the acceptable solution in the earlier period stage. This thesis introduces the principles of ACO in detail and describes our deep research work in the application of combination optimization problems. We apply ACO to Maximum Clique Problems, which are typical NP-complete combination optimization problems. The main contribution of this thesis is as follows:1.Based on the understanding of the biology characters of ants, I studied the origins of the ACO algorithm,the present condition of its development,and the applied circumstance.2.I analysed the principle of the ACO algorithm mechanism deeply,and studied its basic mathematics model and the step to carry it out.3.According to the characteristics of Maximum Clique Problem,I gave the solution way of it, using some examples simulated and verified it.4. According to the experiment results,I studied the way of its parameter choice.Key Words: Ant Colony Optimization algorithm Combinatorial OptimizationMaximum Clique Problem Heuristic algorith最大团问题的蚁群算法研究1引言蚁群优化 1（ACO）属于智能仿生算法蚂蚁算法（AA）的范畴，后者是从蚂蚁觅食时的路径选择机制中得到启发的：个体蚂蚁的能力有限，但是多个蚂蚁组成的群体却能相互配合，在食物源和巢穴之间确定最小的路径。有关研究发现，蚂蚁之间是凭借信息素轨迹（pheromone trails）进行信息交流并据以决定搜索方向的。当蚂蚁移动时，它会在经过的路线上留下这种信息素，从而引导其他蚂蚁以更大的概率去选择相同的路线。当某条路径上经过的蚂蚁越来越多时，其所积累的信息素就会越来越多（同时也有一定的挥发），那么它被其他蚂蚁选择的机会就越大。上述这种群体之间相互配合的机制被称为自催化行为（autocatalytic behavior），该过程具有正反馈的特性（positive feedback），是一种增强型的学习系统。ACO 的主要特征是正反馈、分布计算以及结构性的贪心启发。正反馈使得它能很快搜索到比较好的解；分布计算避免了算法陷入局部收敛而不能继续优化；而贪心启发机制使它能在寻优的早期阶段就搜索到可接受的解。目前国外ACO 领域的研究热点集中在寻优原理与数学基础的研究、收敛性研究、并行ACO 算法研究以及利用ACO 解决各类优化问题等等。从上个世纪九十年代后期起国内逐渐兴起了“蚂蚁热”，利用ACO 解决组合优化问题以及通信网络路由问题的论文很多，但对算法本身进行创新的则很少看见。可以预见，作为一种新兴的智能仿生算法，ACO 具有非常重要的研究前景和应用价值。最大团问题的蚁群算法研究2第一章 绪论1.1 研究背景随着计算机科学的飞速发展，针对离散变量的优化问题被逐渐重视，从而形成了有别于数学规划的另一类模型， 即组合优化（Combinatorial Optimization ）。越来越多的人开始研究组合优化问题，提出许多新的方法和思路，使得组合优化问题内容更加丰富。组合优化问题的求解一直是近年来研究的热点领域之一。组合优化就是离散优化，它是通过数学方法寻找离散事件的最优编排、分组、次序或筛选等。组合优化问题 2，3 通常可描述为：令=s 1，s 2，s n为所有状态构成的解空间， C( st) 为状态 st 对应的目标函数值，要求寻求最优解 s* ，使得对于任意的s t , C( s*)= min C( st) 。对组合优化问题的研究，特别是求解复杂组合优化问题方法的探索已成为众多学科关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，也在于它们在现实生活中的很多方面有着广泛的应用。典型的组合优化问题有旅行商问题（traveling salesman problem ）、加工调度问题（scheduling problem）、0-1 背包问题（0-1 knapsack problem）、装箱问题（bin packing problem）、图着色问题（graph coloring problem）、聚类问题（clustering problem）以及最大团问题（maximum clique problem）和最大割问题（MaxCut problem ）等。这些问题数学描述非常简单，理论上说每一个组合优化问题都可以通过枚举的方法求得最优解，但枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接受，即所谓的“组合爆炸”。对于这些NP-完全2，3，9，10 的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。近些年来，随着计算机技术的发展，一些新的启发式智能化方法愈来愈引起了众多学者的关注和兴趣。诸如神经网络（neural network）、模拟退火（simulated annealing）、禁忌搜索（tabu search）、进化算法（ evolutionary algorithms）、蚁群算法（ant colony optimization algorithm）、DNA 计算（ DNA computation）等，它们毫无争议地成为解决组合爆炸及NP 类问题的锐利工具。然而，面对各种问题的特殊性和复杂性，每一种算法都表现出其自身的优势和缺陷，都会面临时间性能和优化性能的双重挑战 27。最大团问题的蚁群算法研究3蚁群算法（Ant Colony Optimization algorithm ，ACO）是由意大利学者M.Dorigo1 等人在20 世纪90 年代初通过模拟自然界中蚂蚁集体觅食的行为而提出的一种基于种群的启发式仿生类算法。它是继模拟退火算法、遗传算法、禁忌搜索算法、神经网络算法等启发式搜索算法 27以后的又一种应用于组合优化问题的启发式搜索算法。虽然与已经发展完备的一些启发式算法比较起来，蚁群算法的计算量比较大、搜索时间长、有时候效果并不理想，但是它的成功运用还是激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。众多的研究结果已经证明，蚁群算法具有很强的发现较好解的能力，该算法不仅利用了正反馈原理加快进化过程，而且是一种本质并行的算法，不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好解。由于鲁棒性强，使得蚁群算法易于解决各种不同的优化问题。但该算法的研究毕竟刚刚开始，还未形成系统的分析方法和坚实的数学基础，许多问题还有待于进一步研究。1.2 蚁群算法的研究历史和现状最先提出的蚁群算法被称为AS 4，7 （Ant System），它是M.Dorigo、A.Colorni、V.Maniezzo 在意大利的米兰理工学院研究组合优化问题的计算机智能解决方法时的研究成果。AS 算法首先应用于解决旅行商问题（TSP），随后V.Maniezzo、A.Colorni 把AS 算法用于解决二次分配问题（QAP）。最初的AS 算法的效果并不理想，但是后续的研究将蚁群算法和局部搜索以及其它的一些优化方法相结合获得的许多令人振奋的成果。1995 年L.M.Gambardella 和M.Dorigo 提出了Ant-Q 算法 8，9 。该算法建立了AS 与Q-学习机制（Q-learning） 10的联系。它在 AS 算法的随机比例规则基础上，在解构造过程中提出了伪随机比例状态迁移规则（pseudo-random-proportional state transition rule）从而能够实现解构造过程中知识探索（exploration）和知识利用（exploitation）的平衡，并引入信息素局部更新过程，信息素局部更新规则使用了Q-学习机制。此外，在信息素的全局更新中采用了精英策略。 Ant-Q 是一个非常有效的算法。此后，M.Dorigo 和L.M.Gambardella 在Ant-Q 算法基础上提出了ACS 11，12（Ant Colony System）； T.Sttzle 和H.Hoos 提出了MMAS 13（MAX-MIN Ant system）。这两种扩展的蚂蚁算法都被用于解决对称旅行商问题（ TSP）以及非对最大团问题的蚁群算法研究4称旅行商问题（ATSP），并取得了比较满意的结果。MMAS 算法采用了用当前找到的最好解来更新信息素指引蚂蚁向更高质量的解空间搜索的贪婪策略，并对信息素设立上下限来避免算法的早熟。1999 年，M.Dorigo、G.DiCaro 和L.M.Gambardella 把此前各种基于AS 演化而得的算法归结到一个统一的框架中，并提供了抽象而规范的算法描述，称为ACO 元启发式算法 14（Ant Colony Optimization meta-heuristic），简称为ACO 算法。ACO 算法的优点在于：利用了正反馈原理加快进化过程；是一种本质并行的算法；不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好的解；由于鲁棒性强，故易于解决各种不同的优化问题。但是，蚁群算法的计算量比较大、搜索时间长、有时候效果并不理想，国内外的研究人员针对蚁群算法的这些问题，做了许多研究工作，有的将蚁群算法与其它算法相结合，有的给蚁群系统加入变异特征，取得了许多研究和应用成果。B.Bullnheimer 等提出了一种基于蚂蚁等级的ASrenk 算法。W.J.Gutjahr提出了基于图的蚂蚁算法GBAS（Graph-based Ant System）,并证明了算法将以概率1-收敛于最优解。其中， 可以通过选择足够大的蚂蚁数量或足够小的信息素挥发系数来获得任意小的值。C.Blum针对可转换为0-1 整数规划问题的组合优化问题，提出了一种HC-ACO 算法。该算法利用一些策略来避免算法陷入局部最优解。吴庆洪 15等人提出了具有变异特征的蚁群算法,有机地结合了2-opt方法,提高了算法的搜索速度。吴斌、史忠植 16在蚁群算法的基础上提出了相遇算法，其基本思想是在求解TSP问题中，用两只蚂蚁共同完成对一条路径的搜索，并将相遇算法与采用并行策略的分段算法相结合提出一种基于蚁群算法的TSP问题分段求解算法，提高搜索速度。陈崚、沈洁、秦玲 17等针对蚁群算法加速收敛和早熟停滞现象的矛盾，提出了一种基于分布均匀度的自适应蚁群算法。该算法根据优化过程中解的分布均匀度，自适应地调整路径选择概率策略和信息素更新策略，以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。朱庆保、杨志军 18针对蚁群算法在进行大规模优化时收敛时间过长，提出了基于变异和动态信息素更新的蚁群优化算法。该算法以最近的邻居节点选择和动态信息素更新策略来加速全局收敛，以一种独特的变异策略来加快局部寻优，使收敛速度大幅度地提高。最大团问题的蚁群算法研究5I.Watanabe 和S.Matsui 27通过自适应的控制候选集合，改善ACO 算法性能；P.Koroes 和J.ilc用多级的ACO 算法解决了网络划分问题（Mesh Partitioning problem）；C.Solnon研究了蚁群算法搜索的多样性和快速收敛性之间的矛盾，通过对算法参数的研究提出了在算法初期增加预处理步骤，希望在不影响搜索多样性的前提下，提高收敛速度，通过对约束满足问题（Constrain Satisfaction Problem）的仿真试验表明了算法确实能提高速度。目前大量的研究工作注重于ACO 的实际应用，然而，近几年的研究发现：ACO 用于解决组合优化问题时，也会遇到类似进化算法中的deception 和bias 现象。例如：C.Blum 和M.Sampels 研究ACO 用于作业调度问题（shop scheduling problems）时发现：一段时间之后ACO 的性能会由于信息素模式和处理的问题实例而下降，这种现象称为：second-order deception或者search bias，它意味着随着时间的推移找到更好解的可能性越来越小。J.Montgomery 等试图找出导致算法search bias的原因；C.Blum和M.Dorigo 1针对蚁群算法求解组合优化是遇到的second order deception 问题，做了大量的研究工作。然而