求解最短路径的遗传算法中若干问题的讨论

《求解最短路径的遗传算法中若干问题的讨论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Seediscussions,stats,andauthorprofilesforthispublicationat:https://www.researchgate.net/publication/200768694Article·January2008CITATIONSREADS04282authors,including:QingzhengxuXijingUniversity29PUBLICATIONS200CITATIONSSEEPROFILEAllcontentfollowingthispagewasuploadedbyQingzhen

2、gxuon17May2014.Theuserhasrequestedenhancementofthedownloadedfile.第29卷第6期计算机工程与设计2008年3月Vol.29No.6ComputerEngineeringandDesignMar.2008求解最短路径的遗传算法中若干问题的讨论1,21徐庆征，柯熙政(1.西安理工大学自动化与信息工程学院，陕西西安710048；2.西安通信学院，陕西西安710106)摘要：针对道路交通网络中的最短路径问题，讨论了遗传算法中遗传算子的设计及运行参数的选择，提出一种新的交叉算子，提高了种群多样性。通过计算机仿真实验，比较了多种遗传

3、算子设计方案的优劣及不同运行参数对算法效果的影响，为实际应用提供了参考。采用VC语言实现该遗传算法，并应用于实际的电子地图中，结果表明了算法的有效性和实用性。关键词：最短路径;遗传算法;遗传算子;参数选择;电子地图中图法分类号：TP301.6文献标识码：A文章编号：1000-7024(2008)06-1507-03Geneticalgorithmanalysisforshortestpath1,21XUQing-zheng,KEXi-zheng(1.SchoolofAutomationandInformationEngineering,Xi'anUniversityofTechnol

4、ogy,Xi'an710048,China;2.Xi'anCommunicationInstitute,Xi'an710106,China)Abstract：Howtodesigngeneticoperatorandselectparameterusingthegeneticalgorithmisdiscussedtosolvetheshortestpathproblemintrafficnetwork,andanewcrossoveroperatorisproposedtoincreasethepopulationdiversity.Theperformancesofsomegen

5、eticope-ratorsandparametersarecomprisedbycomputersimulation.ThegeneticalgorithmisachievedbyVC++.Theapplicationresultinthepracticalelectronicmapindicatesthatthegeneticalgorithmiseffectiveandpracticality.Keywords：shortestpath;geneticalgorithm;geneticoperator;parameterselection;electronicmap码的效果较好

6、，收敛速度较为合理，寻优性能较佳。因此，本0引言文全部采用基于路径的染色体编码方案。最短路径问题是一类受到普遍重视和研究的网络优化问1.2种群初始化题，广泛应用于计算机科学、交通工程、通信工程、系统工程、对于初始化种群通常有完全随机选择和启发式选择两种运筹学等众多领域。它为研究更复杂的网络流问题提供了基方式。完全随机选择方式，使得适应度低的染色体也可能被础，是解决其它许多复杂网络优化问题的子问题之一。从目选中而加入到遗传机制当中，它适合于对问题的解没有任何前国内外研究现状[1-4]来看，基于遗传算法的最短路径问题的先验知识的情况。启发式选择尽可能选择适应度高的个体，研究比较零散，缺乏

7、比较系统和全面的研究。使得遗传算法更快的到达最优解，但同时减少了种群的多样本文讨论求解最短路径问题的遗传算法中遗传算子的设性，使得算法易于过早成熟。因此，本文全部采用完全随机方计以及参数的选择，通过仿真实验，比较多种遗传算子设计方式产生初始化种群。案的优劣以及不同运行参数对于算法效果的影响，并将遗传1.3适应度函数算法应用于西安市电子地图中。本文的适应度函数定义为1=1(1)1求解最短路径问题的遗传算法设计+1=11.1染色体编码方案式中：——第条染色体的