【硕士论文】基于遗传算法的旅行商问题仿真研究.pdf

《【硕士论文】基于遗传算法的旅行商问题仿真研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西北工业大学硕士学位论文基于遗传算法的旅行商问题仿真研究姓名：华灵群申请学位级别：硕士专业：系统工程指导教师：周德云20060401摘要旅行商是组合优化中最为著名的问题，它综合了一大类组合优化问题的典型特征，并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、x一射线结晶学、机器人控制等高科技领域。运用遗传算法和混合遗传算法对TSP问题进行了研究。将免疫算法融入到遗传算法当中，构成一种改进的遗传算法，与利用简单遗传算法的计算过程进行了仿真和对比。应用结果表明，该算法简单、高效、稳定性好，能较好克服传统方法和现有遗传算法的不足，性能得到了显著的提高，获得了满意的效果。提出了一种混合分布式

2、并行遗传算法，应用于求解旅行商(TSP)I'o]题。这种混合算法主要由动态种群并行模型和20pt算法组成。程序由C编制，运行环境是并行虚拟机(PVM)。在这种混合并行遗传算法中，20pt算法取代变异操作，它逆转TSP个体的基因片段，改善TSP个体的旅行距离。动态种群模型是一种由全局并行模型和粗粒度并行模型结合而成的并行遗传算法模型，但它并没有迁移操作，因为在进化过程中种群仅仅被当作是个体的集合。它的主要思想是通过动态分离种群为子群从而减少最差个体的等待时间，使得子群的演化不被拖延。在处理速度方面，它提供更高的效能，此外动态种群模型还具有完全的可扩展性。最后在一组PC机集群构成的网络环境下运用

3、该混合算法求解TSP问题，实验的数值结果证明了该算法的有效性和可行性。关键词：旅行商问题，遗传算法，免疫遗传算法，MPI并行算法AbstractTravelingSalesmanProblem(TSP)isthewell—knowncombinationoptimizingproblem，itcolligatestheclassicaltypicalityofatypeofcombinationoptimizingproblem，andexists．inVLSIchipmanufacture，printingcircuitdesign，X—raycrystallography,robotco

4、ntrolandmanyotherhigh—techfields．AccordingtoNP-completedtheory,TSPbelongstoNPH，itcan'tbesolvedbyroutinesearchmethods，anddifferenttypesofsolutionsmustbeemployed．Geneticalgorithm(GA)isshowingitspotentialinsolvinglargecombinationoptimizingproblemmoreandmore．ConsideringexistedproblemsTSP,dispatchproble

5、msofstaticstateforPTVarestudiedanddiscussedwithgeneticalgorithms(GA)andHybridGA．MakingfulluseofintelligentcharacteristicsofGA．staticdispatchofPTVisimprovedeffectively．BasedonGAandthestudyoftheimmuneprincipleofcreature，immunealgorithmismissedintoGA，andtheybecomeanimprovedGA．Thisadvancedalgorithm--Im

6、muneGA(IGA)isappliedtosolvesomeoptimizationproblems．ThecomputingprogramsapplyingGAandIGAaresimulatedandcompared．TheresultsshowthatIGAissimple，efficientandrobust．AhybridalgorithmusingdistributedPGAbasedontheDDsmodelandheuristicmethod(20pt)forrapidsolutionofTravellingSalespersonProblem(TSP)ispresente

7、d．AcprogrambasedonthisalgorithminParallelVirtualMachine(PVM)environmentisdeveloped．Inthishybridmethod，themutationisprovidedbythe20ptmethodwhichisoneofthemostwell-knownlocalsearchesalgorithmsamongTSPsolvinga