社会演化算法及其在TSP问题中的应用

《社会演化算法及其在TSP问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、社会演化算法及其在TSP问题中的应用摘要组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题属于NP完全问题。当问题规模逐渐扩大时，其解空间呈组合爆炸特征，无法用常规的方法求解。此类问题目前只能用启发式算法进行求解。旅行商问题(TSP)就是一个经典的组合优化问题。本文给出了一种基于社会演化算法求解TSP问题的方法，该算法用认知主体取代了传统遗传算法的基于编码的可行解生成方式；用基于“范式学习与更新"的进化寻优机制取代了传统遗传算法中基于模仿基因的遗传和变异的进化寻优机制，使其计算效率更优。在本文的应

2、用研究中，将社会演化算法和蚁群算法相结合，以蚁群算法作为认知主体的推理过程，得到认知主体进行学习的初步范式，再以社会演化算法中基于“范式的学习和更新”方式获得最优解。通过具体算例实验仿真与TSP已知最优解进行对比分析，结果表明，社会演化算法在种群规模较小，迭代次数较少的情况下也可获得TSP最优解。在求解TSP问题的基础上，对社会演化算法的各种参数的取值及其对解的影响进行讨论，寻找一些可供人们参考的经验规律，对同类问题进行简化处理。最后，对全文的研究工作进行了总结，并对社会演化算法今后的发展方向作了展望。关键词：社会演化算法，蚁群算法，旅行商问题(TSP)，

3、认知主体SOCIALEVOLUTIONARYPROGRAMMINGALGoRITHMANDITSAPPLICATIONINTSPABSTRACTCombinatorialOptimizationProblemisoneofthemostimportantembranchmentofoperationalresearch．Themathematicalmethodscanbeusedtosearchoptimizationarrange，grouping，sequenceorriddingofthediscreteevents．Theseproblemsbe

4、longtotheNon—polynomial—complete(NPC)questions．Withtheenlargementofthescaleofquestion，thesolutionspacemakesthecharacteristicofexplodingup，isunlikelysolvedwithgeneralmethods．Thesequestionscanonlybesolvedbymeta—heuristicstogettheapproximatesolution．TSPisaclassicalcombinatorialoptimi

5、zationproblem．AmethodbasedonsocialevolutionaryalgorithmisgiveninthispapertosolveTSRTheproposedmethodreplacesindividualsinthetraditionalGeneticAlgorithmwithCognitiveAgents．Italsoreplacesthemechanismofcrossoverandmutationwiththemechanismof“paradigmstudyandupdate”．Thereforethepropose

6、dalgorithmhasanadvantageinthecomputationalefficiency．Inthispaper,socialevolutionaryalgorithmiscombinedwithAntColonyOptimization．FirstlyAntColonyOptimizationisusedascognitiveagents’cognitivelearning，andthentheglobaloptimumisobtainedbyparadigm’Slearningandshift．Finallysomeresultsare

7、comparedwiththeoptimumthatwereknown，theresultindicatethatSocialEvolutionaryProgrammingwithlIfeweragentsandlessiterativetimescanalsoconvergetheoptimum．OnthebasicofsolutiontoTSP,differentparametersinsocialevolutionaryalgorithmandtheirimpacttotheresultareanalyzed，tryingtofindsomeexpe

8、riencelawstosimplifiedthesameprob