搜索
最大团问题的蚁群算法研究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.1ACO算法中参数的研究..............................................................................................................264.2蚁群算法参数最优组合的“三步走”方法[27]..................................................................314.3本章小结.........................................................................................................................................32结论............................................................................................................................................................33致谢.............................................................................................................................................................34参考文献.................................................................................................................................................35最大团问题的蚁群算法研究III摘要组合优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点问题。对于NP-完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一种新的启发式算法，它具有正反馈、自组织、分布式计算以及结构性的贪心启发等特点。其中正反馈使得它能很快搜索到比较好的解；分布计算避免了算法陷入局部收敛而不能继续优化；而贪心启发机制使它能在寻优的早期阶段就搜索到可接受的解。因而蚁群算法能够成功地应用于解决许多NP-完全的组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算法应用于求解图的最大团这个经典的NP-完全组合优化问题，在本文中我主要做了以下工作：1、在了解蚂蚁的社会形态、群体行为等生物学特征的基础上，认真研究了蚁群算法的思想起源、发展现状、以及其应用情况。2、从深层意义上分析蚁群算法机制的原理，研究其基本的数学模型和具体实现步骤。3、根据最大团问题的特点，给出了求解最大团问题的蚁群算法解决方案，编写程序，用DIMACSbenchmarks中的部分实例进行了仿真验证。4、根据大量实验结果对蚁群算法的参数选择进行了研究。关键词：蚁群算法组合优化最大团启发式算法最大团问题的蚁群算法研究IVAbstractManycombinatorialoptimizationproblems,whicharefundamentalandimportantinscienceandengineeringcalculation,areNP-completeproblems.Thesolutionoftheseproblemshasbeenthekeyproblemsinthestudyofalgorithmtheory.ForNP-completecombinationoptimizationproblems,thereisnoefficientalgorithmtothesolutionoftheproblemsnow.Consequently,heuristicalgorithmsmaybeusedtosolvesuchtypeofproblems.Asanewheuristicalgorithm,AntColonyOptimization(ACO)algorithmwhosemaincharacteristicsarepositivefeedback,distributedcomputationandconstructivegreedyheuristiccansolvemanyNP-completecombinationoptimizationproblemssuccessfully.Forthepositivefeedbackmakesitbeabletoveryquicklysearchthebettersolution;Distributecomputationavoidedthecalculatewaysinkintothepartrefrainfromrashactionandcan'tcontinuetheoptimization;Andtheconstructivegreedyheuristicmakesitabletosearchtheacceptablesolutionintheearlierperiodstage.ThisthesisintroducestheprinciplesofACOindetailanddescribesourdeepresearchworkintheapplicationofcombinationoptimizationproblems.Wea