基于遗传算法混合蚁群算法地研究

《基于遗传算法混合蚁群算法地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要群集智能与演化计算都是模仿自然界生物进化过程而产生的一类仿生型算法，其代表算法——蚁群算法与遗传算法从产生以来至今得到了越来越多的科研人员的重视。蚁群算法(AntColonyAlgorithm,ACA)是最近几年才提出来的一种模拟由简单个体组成的群落与环境以及个体之间的互动行为的仿生算法，它来源于对真实蚂蚁群体寻找从巢穴到食物源最短路径方法的模拟，体现了真实蚁群的协作过程，具有高度的并行性、正反馈性、鲁棒性及协同性等优点，在解决复杂优化问题上显示出了良好的适应性，是一种很有应用前景的智能算法。由于蚁群算法的提出相对较晚，

2、所以至今还未形成系统的分析方法和坚实的数学基础，算法中各个参数的选择也只有通过先验知识来指导而没有理论上的指导；存在算法初期信息素匮乏，搜索时间过长，以及运行过程中容易出现收敛过早或停滞现象等缺点。遗传算法的提出相对蚁群算法较早，研究也相对较成熟，具有快速、随机、全局收敛性的特点，但同时存在信息素匮乏、求解效率低等缺陷。本论文在对蚁群算法与遗传算法进行充分比较研究后，将这两种算法进行了融合，同时对融合后的混合算法进行了改进，并通过使用该混合算法在求解复杂旅行商问题(TSP问题)上的仿真实验结果表明，该改进算法能够更快地收敛到

3、全局最优解。论文的贡献及主要创新点体现在以下几个方面：(1)提出了一种基于遗传算法的混合蚁群算法。该算法利用遗传算法在大范围内寻找一组粗略解，以这组粗略解为蚁群算法的初始路径求解出其最优解；同时为提高蚁群算法的全局搜索能力，在蚁群算法中嵌入变异、交叉等遗传操作。并通过求解复杂TSP问题的仿真数据实验验证了这种基于遗传算法的蚁群混合算法的高效性。(2)提出了一种新的自适应改变值的方法。由于蚁群算法中的值在大多数情况下只能根据经验来确定，而且对参数最佳值的选取是一极其复杂的问题，目前还没有完善的理论依据，而其对算法的性能优劣

4、起着致关重要的影响，本论文对蚁群算法的信息挥发系数进行了进一步的研究，提出了一种自适应改变值的方法，并将其应用于基于遗传算法的蚁群混合算法中。使混合算法能在保证一定的收敛速度下仍具有较优的全局搜索能力。(3)在混合算法中引进了新的路径选择策略。为了增加蚂蚁在初始阶段选择路径的多k样性，论文对蚂蚁在以概率p(t)进行路径选择过程中引进了新的选择策略，在一定程度ij上削弱了混合算法陷入局部最优的趋势。关键字：蚁群算法;遗传算法;混合算法;TSP问题IAbstractSwarmIntelligenceandEvolutiona

5、ryComputationallbelongtobionicalgorithmwhichimitatesevolvingprocessofnature.Astherepresentativealgorithm,antcolonyalgorithm(ACA)andgeneticalgorithms(GA)havebeenpaidmoreandmoreattentionbyresearchers.ACAemergerecentlyasanewmeta-heuristicwhichsimulatecommunitiesmaking

6、upofsomesimpleindividualsandits’environment.Itbasesontheresearchonantfindingtheshortestroadfromthenesttothefoodwhichreflectsthecooperatingprocessinthecourseofantcolonysearchingroute.Thecharacteristicsofparallel，positivefeedbackandrobustarestronglyshowedintherunning

7、ofACA.Itshowsagreatdealofsalientcharacterandgoodadaptabilityinitsapplication,especiallyinsolvingthecomplexcombination-optimizequestions.SoACAisapromisingapplicableintelligentalgorithm.ForACAbeingproposedcomparativelylate,ithasnosystematicanalyzingmethodandstablefou

8、ndationofmathematics,andthechoosingofparametersalsohasnopreviousknowledgeandtheorytoguide.so,attheinitialstageofalgorithm,thepheromoneisveryscarc