应用遗传算法提高蚁群算法性能的研究

《应用遗传算法提高蚁群算法性能的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、太原理工大学硕士研究生学位论文应用遗传算法提高蚁群算法性能的研究摘要蚁群算法(antcolonyalgorithm简称ACA)是最近几年才提出来的一种新型的模拟进化算法，它来源于对真实蚂蚁群体寻找从巢穴到食物源最短路径方法的模拟，体现了真实蚁群的协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上释放信息素，借助选择策略、信息素更新等操作来提高解的质量，进而达到优化的目的。可见，它是一种随机搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具有高度的本质并行性、正反馈性、鲁棒性及协同性等优点，在解决复杂优化问题上显示出了良好的适应性，具有许多优良品质和实际应用

2、价值，是一种很有前景的方法。因此，蚁群算法的研究无论从理论上还是实用上都具有较高的价值。作为一种近年提出的新算法，蚁群算法还没有像遗传算法、模拟退火算法等那样形成系统的分析方法和坚实的数学基础，算法中各个参数的选择也没有理论上的指导；算法初期信息素匮乏，导致搜索时间较长；算法运行过程中容易出现收敛过早或停滞现象；不能扩大解的搜索范围；不能很好的利用当前解所带的信息等。本文以基本蚁群算法的性能分析为背景，通过实验分析了基本蚁群算法中五个参数：启发因子口，期望因子∥，信息素挥发度P，蚂蚁数量m以及总信息量Q各自对算法性能的影响。实验结果表明口，∥，P这三个参数对算法的

3、影响较大，并且他们的作用是紧密耦合的。目前对于这些参数的选择T太原理工大学硕士研究生学位论文大多以经验或试验来确定，造成试验工作量大且难以得到最佳的参数配合，影响了算法的使用。本文利用遗传算法来优化这三个参数，并将其应用在TSP问题的仿真实验中。实验表明，该方法能够快速的找到一组较优解，可使蚁群算法获得较优的运行性能，说明了该方法的可行性和有效性。本文在查阅大量国内外参考文献的基础上，针对前面基本蚁群算法初始信息素匮乏的缺陷，给出一个可行的解决方案：将蚁群算法与遗传算法相结合形成混合算法(GA—ACA)。其基本思路是：算法一开始充分利用遗传算法快速性、随机性、全局

4、收敛性的特点，搜索出待求解问题的初始信息素分布；然后在此初始信息素分布的情况下，充分利用蚁群算法并行性、正反馈性、求精解效率高等特点来求解。此外，GA．ACA混合算法相对于基本蚁群算法在以下几个方面进行了改进：①引入确定性与随机性相结合的选择策略，减少算法陷入局部解的概率；②对局部信息素与全局信息素采用自适应的信息素更新策略动态调整，更好的利用当前解；③引入2-opt局部搜索算法来扩大解的搜索空间。将混合算法在经典的组合优化问题旅行商问题(TSP)和二次指派问题(QAP)上进行了仿真验证。实验结果表明，该混合算法不但加速了蚁群算法的收敛速度，而且提高了所得优化解的

5、质量。关键词：蚁群算法，信息素，组合优化，混合算法，遗传算法Ⅱ太原理工大学硕士研究生学位论文RESEARCH0NIMPROVEDPERFORMANCEOFANTCOLONYALGORITHMBYGENETICALGORITHMABSTRACTAntcolonyalgorithm(ACA)hasemergedrecentlyasanewmeta·heuristicwhichbelongtotheclassofproblem-solvingstrategiesderivedfromnature．Itisbasedontheresearchontheantfinding

6、theshortestroadfromthenesttothedestination．Itsimulatethecooperatingprocesswhichantcolonysearchroutefromnesttofood．Itisakindofstochasticexplorativealgorithms．Ititeratestothebestansweraccordingtoselectivestrategyandinformationelement，whichisgeneratedbyeachant．Thecharacteristicofparallel

7、，positivefeedbackandrobustisstronglyshowedintherunningofACA．Ithasshowedagreatdealofsalientcharacterandperformedgreatvalueinitsapplicationspecialforsolvingthecombination—optimizequestions．SotheresearchoftheoryandutilityofACAhasgreatmerit．Asanewalgorithm，ACAhasnosystematicanalyzingmetho

8、dands