基于混合粒子群算法的旅行商问题研究（已处理）

基于混合粒子群算法的旅行商问题研究摘要演化计算是模拟自然界生物演化过程的一种群体导向随机搜索技术。近年来,用演化算法求解组合优化问题已经成为研究热点,旅行商问题,是一类NP完全的组合优化问题,有效地求解旅行商问题,对于组合优化问题的求解有着十分重要的意义。标准粒子群算法[6]通过追随个体极值和群体极值来完成极值寻优的,虽然操作简单,且能够快速收敛,但是随着迭代次数的不断增加,在种群收敛集中的同时,各粒子也越来越相似,可能在局部解周边无法跳出。针对该算法的缺乏,本文在标准粒子群优化算法的根底上通过引用遗传算法思想中的交叉和变异操作来改善粒子群算法,从而防止了标准粒子群优化算法可能陷入局部最优的情况,并将其应用于求解旅行商(TSP)问题。本文将改良的粒子群算法在14城市和30城市及50城市这三个实例中进行了仿真,结果说明了基于混合粒子群优化算法对于求解组合优化问题的优越性,对小规模城市坐标精确度非常高。关键词:粒子群算法;组合优化;遗传算法;TSPABSTRACTTheevolutionarycomputationsimulationnatureisakindofbiologicalevolutionprocessgrouporientedrandomsearchtechnology.Inrecentyears,withtheevolutionaryalgorithmtosolvecombinatorialoptimizationproblemhasbecomethefocusinthetravelingsalesmanproblem,isakindofNPcompletecombinatorialoptimizationproblem,effectivesolutiontravelingsalesmanproblemforcombinatorialoptimizationproblemsolvingisveryimportantmeaningThestandardparticleswarmalgorithmthroughthefollowingindividualsandgroupstocompletetheextremevalueofextremevalueoptimizationextreme,althoughtheoperationissimple,andcanbefastconvergence,but,withtheincreaseofiterationtimes,inapopulationconcentrationofconvergenceatthesametime,eachparticlealsomoreandmoresimilar,maybeinlocalsolutionforperipheralcouldnotgetout.Accordingtothedeficiencyofthealgorithm,basedonthestandardparticleswarmoptimizationalgorithmbasedongeneticalgorithmthroughreferencethoughtsofcrossoverandmutationoperatorstoimproveparticleswarmalgorithm,andavoidthestandardparticleswarmoptimizationalgorithmmayfallintothelocaloptimalsituation,andisappliedtosolvingthetravelingsalesmanproblemTSP.Thispaperwillbeimprovedparticleswarmalgorithmin14citiesand30citiesand50citythethreeexamplesofsimulation.Theresultsshowthatthehybridparticleswarmoptimizationalgorithmforsolvingthecombinatorialoptimizationproblem,theadvantageofsmallcitiestocoordinateaccuracyisveryhighKeywords:Particleswarmalgorithm;Combinatorialoptimization;Geneticalgorithm;TSP目录摘要 IABSTRACT II1.绪论 11.1选题的背景、目的和意义 11.2研究综述 11.3本文的主要工作 21.4本文的组织与结构 22.演化计算概述 32.1演化计算的历史与开展 32.2演化算法的框架 42.3演化计算的特点 52.4演化计算的分支 62.5演化计算的应用 72.6演化计算的研究与开展动态 83.基于混合粒子群算法求解旅行商问题 93.1粒子群算法概述 93.2遗传算法概述 113.3旅行商问题概述 133.4混合粒子群优化算法求解旅行商问题 143.5仿真实验 163.6结论 244.总结与展望 25致谢 26参考文献 27基于混合粒子群算法的旅行商问题研究1.绪论1.1选题的背景、目的和意义仿生优化算法特别是演化算法,已被广泛应用于各种科学技术和工程问题中。演化算法是以达尔文的进化论思想为根底,通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术,是指基于“优胜劣汰〞进化理论的寻优算法[2]。近年来,一种新型的演化算法诞生:群集智能算法SwarmIntelligenceAlgorithms,简称SIA,群智能SwarmIntelligence,SI的概念最早由Beni,Hackwood和Wang在分子自动机系统中提出。群集智能算法作为一种基于概率搜索能力的计算方法,有着比传统算法更优的优点:①群体中相互之间合作的个体是分布的;②可以通过个体之间间接的通信进行合作,从而具有良好的可扩充性;③没有中心的控制,具有鲁棒性;④单个的个体能力较简单,实现时比拟方便,具有简单性。群智能算法作为一种新兴的演化计算技术,已成为越来越多研究者的关注焦点,它与人工生命,特别是进化策略以及遗传算法有着极为特殊的联系。群智能理论研究领域主要有两种算法:蚁群算法和粒子群优化算法。蚁群算法是对蚂蚁群落食物采集过程的模拟,已成功应用于许多离散优化问题。粒子群优化算法也是起源于对简单社会系统的模拟,最初是模拟鸟群觅食的过程,但后来发现它是一种很好的优化工具。粒子群算法,也称粒子群优化算法,缩写PSO[7],是近年来开展起来的一种新的进化算法,是一种进化计算技术evolutionarycomputation,1995年由Eberhart和kennedy提出。旅行商问题(TSP)[11]是数学领域中著名问题之一,是一个经典的组合优化问题。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值,这是一个NP难题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,因此设计高效算法来求解旅行商问题具有重要的理论和实际意义,国内外学者对其进行了大量的研究,更多更有效的方法有待进一步被探讨和开掘。本文在粒子群算法的根底上引入遗传算法的交叉和变异操作,目的在于:克服标准粒子群优化算法中的局部优先问题,克服遗传算法中复杂的编码实现,使操作变得简单,实现变得容易,提高精确度;为旅行商问题寻求更优解。而本文的实际意义在于:粒子群算法作为一种新的进化算法,其开展和研究的时间并不长,旅行商问题,是一类NP完全的组合优化问题,在各领域有着广泛的应用,在粒子群算法中引入交叉和变异操作来求解旅行商问题,是一次有意义的尝试。1.2研究综述演化算法[3]是一类模拟自然界遗传进化规律的仿生学算法,经过假设干年的研究开展,已经形成一个庞大的学术家族。近年来,一种新型的演化算法诞生:群集智能算法SwarmIntelligenceAlgorithms,简称SIA,群智能SwarmIntelligence,SI的概念最早由Beni,Hackwood和Wang在分子自动机系统中提出。典型的群集智能算法有Dorigo提出的蚁群算法AntColonyAlgorithms,Kenndy与Eberthart提出的粒子群优化算法ParticleSwarmOptimization,PSO。在国外,关于演化算法的研究一直领先于国内,开展也比拟成熟,许多理论体系和研究体系已经非常完善,我国学者接触这个领域较晚,目前尚未形成声势和有规模的研究队伍,但武汉大学对演化算法的研究较深入,处于国内领先地位。自从1995年Eberhart和kennedy提出原始粒子群以后,Shi.Y和Eberhart分析了PSO算法的参数选择,并将惯性权重引入PSO,并相继提出了线性递减惯性权重LDIW、模糊惯性权重FIW和随机惯性权重RIW。Clerc对算法的参数选择和收敛性进行了初步的数学分析,引入收敛因子以保证算法的收敛;Ozcan和Mohan对原始PSO算法进行了数学分析,指出停留在离散时间状态的粒子轨迹是连续的正弦波形。PSO算法存在着收敛速度和收敛质量之间的矛盾。为了获得更好的优化性能,研究者们提出了各种改良的PSO算法。Angeline通过引入GA中的选择机制得到混合PSO,该算法提高了收敛速度,但也增加了陷入局部极值的可能;Lovbjerg和Rasmussen等提出了具有繁殖和子群的杂交PSO算法,将GA中的交叉机制引入PSO,由于后代选择并不是基于适应度值,防止了基于适应度值选择对那些多局部极值的函数优化时带来的潜在的问题。此外,很多的研究者也尝试着研究将其它的优化技术与PSO相结合、能充分发挥各个算法优点的混合算法。本次课题设计的主要目的是对混合粒子群算法求解旅行商问题的研究和讨论,在标准粒子群算法的根底上引入交叉操作和变异操作,用于旅行商问题的求解,并对结果进行比照分析。1.3本文的主要工作本文的主要工作是对混合粒子群算法进行研究,并将其用于求解旅行商问题。首先研究了演化计算的由来和理论根底,以及其特点,在此根底上又研究了粒子群优化算法和遗传算法,并将粒子群算法和遗传算法相结合,接着了解了组合优化问题,并仔细研究了旅行商问题。接着把改良的粒子群算法用于旅行商问题的求解,通过仿真实验得出结果并与当前最优路径进行比照分析。1.4本文的组织与结构论文的结构安排如下:第1章:引言,这局部主要介绍了有关本课题的选题目的和意义,并且也简单介绍了本文的主要工作。第2章:演化计算,在这个章节主要对演化计算的历史与开展、演化计算的框架结构、演化计算的特点和分支以及演化计算的应用等做了详细的介绍。第3章:基于混合粒子群算法求解旅行商问题,这个章节主要介绍了粒子群算法,遗传算法及旅行商问题,并对算法进行了仿真实验,对所得结果与当前最正确路径进行了比照分析。第4章:结论与展望,对全文做出了总结,指出了论文的缺乏之处,展望课题开展的前景。2.演化计算概述演化计算[3]是模拟自然界生物演化过程产生的一种群体导向随机搜索技术,它的根本原那么是优胜劣汰的自然选择法那么。演化计算采用简单的编码技术来表示各种复杂的结构,并通过对一组编码表示进行简单的遗传操作再生、杂交和变异和优胜劣汰的竞争机制来指导对问题空间的搜索。简而言之,演化计算不用了解问题的全部特征,就可以通过表达进化机制的演化过程完成问题的求解。2.1演化计算的历史与开展演化计算EvolutionaryComputation,简称EC是源于对生物进化的模拟的一类基于种群的概率搜索方法。它的生物学理论根底有两个:达尔文的自然选择学说和基于分子生物学的遗传理论。达尔文的自然选择学说认为,生物是有变异的,变异可能引起个体性状的差异,由于生物体的繁育潜力超过实际的繁育率,适应度高的个体将生存下来,其所带有的变异因为合理而生存下来。环境的多样性也使得生物界通过自然选择而获得了多样性。基于分子生物学的遗传理论发现,生物上下代之间传递遗传信息物质是DNA,其主要载体是染色体,染色体上具有遗传效应的DNA片段称为基因。DNA的双螺旋结构使得两个父代能有规律地将各自一半的染色体遗传给下一代,下一代的基因根本上是上一代基因的重新组合,同时在遗传过程中还会发生基因的突变,产生一些新的基因,引起新的个体性状差异。通过对自然进化过程的简单化模拟得到一种有效的计算机算法,这种思想的萌芽在二十世纪五六十年代已屡次相互独立地出现,在二十世纪七八十年代才得到开展和推广,这一过程一直是沿着三条相对独立的研究线索而开展,并导致形成了三个主流,即遗传算法GeneticAlgorithm,简称GA、演化规划EvolutionaryProgramming,简称EP和演化策略EvolutionStrategies,简称ES。遗传编程GeneticProgramming,简称GP那么是遗传算法的分支。直到1994年第一届InternationalConferenceonEvolutionaryComputation的召开,以上这些算法才被统称为演化计算。演化计算采用简单的编码技术来表示各种复杂的结构,并且通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选法那么来指导学习和确定搜索的方向。由于演化计算采用种群的方式进行搜索,这使它可以同时地搜索解空间内的多个区域。并且使用种群进行搜索的方式能使演化算法特别适合于大规模的并行计算。在赋予演化计算自组织、自适应、自学习等特性的同时,优胜劣汰的自然选择和简单的遗传操作也使演化计算具有不受它的搜索空间限制性条件如可微、连续、单峰等的约束以及也不需要其它辅助信息如导数的特点。这些新的特点使演化算法不仅能获得较高的效率而且也具有简单、易操作和通用的特性,而且这些特性正是演化计算越来越受到广阔研究人员青睐的主要原因之一。演化计算在二十世纪六七十年代未受到重视。主要原因如下:①当时这些方法本身还不够成熟;②这些方法需要较大的计算量,并且当时的计算机还不够普以及速度也跟不上要求,这样便限制了它们的应用;③当时基于符号处理的人工智能方法正处于顶峰状态,使人们难以认识到其它方法的有效性和适应性。到了二十世纪八十年代,人们越来越清楚地认识到传统人工智能方法的局限性,由于计算机速度的提高和并行计算机的普及,已使演化计算对于机器速度的要求不再是制约其开展的因素。同时也由于它的不断开展及其在一些应用领域内取得了成功,演化计算已表现出了良好的应用前景。现在,演化计算的研究内容十分广泛,例如演化计算的设计与分析、演化计算的理论根底以及在各个领域中的应用等。随着演化计算的理论研究的不断深入和应用领域的不断扩展,演化计算将会取得很大的成功,必将在当今社会占据更重要的位置。2.2演化算法的框架演化算法在求解问题的过程是从多个解开始的,然后通过一定的法那么逐步迭代来产生新的解。演化算法首先将问题的可行解进行相应的编码,这些已经编码的解被称为染色体或称为个体,记为,,,…,等。这里的t表示的是迭代数,称为演化代数。一定数量的个体组成了一个群体,记作。群体中个体的数目称作群体的大小,记作N。演化算法的搜索是始于这个群体的,最初产生的群体叫作初始群体。初始群体产生以后,算法模拟遗传学中的杂交、变异和复制等操作方式来设计出演化算子,采用优胜劣汰的自然选择法那么来指导、学习和确定搜索的方向,这个过程就叫作演化过程。在演化过程中,要选择当前解进行杂交以产生新解,这些当前解那么称为新解的父解或称作父代个体,产生的新解那么称为后代解或称为子代个体。演化算法的根本流程可以描述如下:随机初始化群体;计算中的个体的适应值;while不满足结束条件do由通过特定的演化操作来形成新的群体;计算中的个体的适应值,并;由算法的根本流程可知,演化算法对待求解的问题的本身是一无所知的,它所能做的只是对算法所产生的每一个个体进行相应的评价,并通过遗传操作来产生新一代的群体,使适应值相对较好的个体比适应值相对较差的个体有更多的繁殖后代的时机。如此一代一代地演化下去,一直到算法满足给定的终止条件为止。演化算法的根本流程图如图2.1所示。图2.1演化算法根本流程图2.3演化计算的特点演化算法采用的是简单的编码技术来表示各种复杂的体系结构,并通过对某一组编码表示进行简单的遗传操作如选择、杂交和变异和由优胜劣汰的竞争机制来指导对空间的搜索。概括地讲就是,演化算法不用了解问题的全部特征和属性,就可以通过进化机制的演化过程来完成问题的求解。演化算法,诸如演化规划EP、遗传算法GA、演化策略ES都是一种模拟生物进化的随机计算模型,通过反复屡次的迭代,使那些对环境有比拟强的适应能力的个体存活下来。这种模型不需要所求函数的其它辅助信息,而能够到达相当高的精度要求,尤其是那些适合一些非线性的和超高维的问题的优化。研究演化计算不可防止会遇到的一个现实问题就是关于演化计算的数学证明迄今为止还根本上仍是一个空白,也就是至今无法用数学的方法来证明演化计算的有效性,也即无法证明演化计算为何会具有收敛性。同样,当我们得到一个比拟好的问题的解时,无法直接证明它就是这个问题的最优解,原因在于这个解是我们搜索出来的,而每次搜索结果可能都不一样,所以无法证明这次搜索的解就一定是解决问题的最好的解。与传统的算法相比拟,演化算法具有以下的一些特点:1应用演化来计算求解问题时,在确定了编码的方案,适应值函数以及演化算子之后,算法将会利用演化过程中所获得的信息自行进行组织搜索。由于自然的选择策略为“优胜劣汰,适者生存〞,因而适应值大的个体就具有较高的生存概率。故而适应值大的个体那么有与环境更适应的基因结构。此类基因结构通过杂交与变异等遗传操作就可能产生更能适应生存环境的后代。而演化算法的这种自组织、自适应特征同时也赋予了它所具有能根据环境的变化自动的发现当前生存环境的特征和规律的能力。2演化算法采用种群的方式进行组织搜索,从而使它可以同时搜索解空间的多片区域,并且能以比拟大的概率跳出局部最优,来找出全局的最优解,因而可以有效的防止了搜索过程收敛于局部最优化解的情况。3演化算法只需要得到目标函数的取值信息,不需要其它附加信息,因而适用于任何类型的大规模、非线性的不连续函数的优化问题以及无解析表达式的目标函数的优化问题,具有非常强的通用性。4演化算法同时具有并行计算的特点。算法的操作对象一般是一组可行解,而非单个的可行解;搜索轨道也是有多条,而非单条,因而具有良好的并行性。5演化计算是利用个体的适应值来推动种群的演化的,而不管问题本身的结构特征,在利用演化算法来求解问题时,我们只需要计算相应的编码方式和演化算子,而不需要修改算法自身的组织结构。除此之外,当问题中的环境发生动态变化时,因为演化计算本身就是一个动态演化的过程,它也就能动态适应环境,演化过程就能继续演化下去而不需要重新的进行初始化。2.4演化计算的分支演化计算最初具有三大分支:即于20世纪70年代由Holland提出的遗传算法GeneticAlgorithms,简称GA,同期由Rechenberg和Schewefel等提出的进化策略EvolutionaryStrategy,简称ES以及于1960年代由Fogel、Owens和Walsh提出的进化规划EvolutionaryProgramming,简称EP。20世界90年代在遗传算法的根底上又开展了一个分支:即由J.Koza提出的遗传程序设计GeneticProgramming,简称GP。这几个分支具有一个共同点就是都是借助生物演化的思想和原理来解决实际的问题。1遗传算法。将进化论与计算机科学结合起来的尝试开始于二十世纪五十年代,但由于缺乏一种通用的编码方案,使得人们只能依赖变异而不是交配来产生新的基因结构,到二十世纪六十年代,位串编码技术出现,这种编码技术不但适于变异操作。而已同样适于交配即杂交操作。并且强调将交配作为主要的遗传操作。遗传算法的通用编码技术和简单有效的遗传操作意义重大,并为其广泛、成功的应用奠定了坚实的根底。Holland遗传算法被称为简单遗传算法SGA。2演化规划。演化规划的方法最初是由//.el等提出在1960年代。他们在研究人工智能的时候发现,智能行为就是具有感应其所处环境的状态、并按给定目标自动做出适当响应的能力。在研究中,他们将模拟环境描述成由有限字符集中的符号组成的序列。于是问题就被转化为,如何根据当前观察到的符号序列做出响应,以获得最大收益。这里,收益主要由环境中将要出现的下一个符号及预先定义好的效益目标来确定。他们将此方法应用到数据诊断、模式识别和分类及控制系统的设计等问题中,取得了较好的结果。3演化策略。1960年代初,柏林工业大学的学生I.Rechenberg和//.wefel[2]在进行风洞实验时,由于用传统的方法难以对设计中描述物体形状的参数进行优化。因而利用生物遗传和变异的思想来改变参数值,并获得了较好的效果。随后,他们对这种方法进行了深入的研究和探索。形成了演化计算的另一个分支演化策略。4遗传程序设计。自计算机出现以来,计算机科学的一个方向性目标就是让计算机自主进行程序设计,即只要告诉计算机要解决的问题,而不需要告诉它具体如何去做。遗传程序设计便是在该领域的一种尝试。它采用演化算法中遗传算法的根本思想,但使用一种更为灵活的表示方式??使用分层结构来表示解空间。这些分层结构有叶节点和中间节点,叶结点是所需解决问题的原始变量,中间结点那么是组合这些原始变量的函数。这样,每个分层结构对应问题的一个可行解。遗传程序设计就是使用一些遗传操作动态地改变这些结构,以获得解决该问题的可行的计算机程序。遗传程序设计的思想是Stanford大学的//.a在1990年代初提出的。2.5演化计算的应用从演化计算的原理来看,它适用于一些没有好的数学方法来解决的问题,或者是数学方法解决的不好的各类问题。如这里的背包问题,虽然定义非常简单,但没有可使用的常规的数学方法解决的可能,用穷举法也是无法解决这个问题的,但是演化算法却可以在一定的程度上解决这个问题。演化计算为我们提供了一种求解复杂系统优化问题的通用框架,它并不依赖于问题的具体领域,而对问题的种类有很强的鲁棒性,所以演化计算在大型优化问题的求解、自适应控制、机器学习、神经网络、人工生命、经济预测等领域中都取得了比拟大的成功,已然引起了包括数学、物理学、化学、生物学、计算机科学及工程应用等领域科学工作者们和学者们的极大兴趣。演化计算的主要应用领域如下:1生物技术和生物学。演化计算的机理来自源生物学,同时又效劳于生物学,用演化计算的方法可以用来来研究一些生物学的现象。2优化。其中包括函数优化和组合优化问题。函数优化是演化计算经典的应用领域,同时也是对演化计算进行性能评价的常用算例。人们构造出了许许多多的各种形式的测试函数,有连续函数也有离散函数,有低维函数也有高维函数,有凸函数也有凹函数,有单峰函数也有多峰函数,有确定性函数也有随机性函数等等。对于高度非线性、多目标的函数优化问题,使用演化算法可以很方便地得到它们的解,但传统的方法往往难以奏效。演化计算在函数优化中的应用成果甚丰。3图像处理和模式识别。图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中,比方扫描、特征提取、图像分割等都会不可防止地产生一些误差,这些误差肯能会影响到图像处理和识别的效果。怎样使这些误差最小是使计算机视觉到达实用化的一个重要要求。演化计算在图像处理中的优化计算方面是完全可以胜任的。4人工生命。人工生命是指以计算机为媒介模拟生命或具有生命特征的行为,包括自组织、自学习及信息的复制和传播行为。自组织和自学习能力是人工生命的两个主要特征。人工生命与演化计算存在着密切的关系,基于演化计算的模型演化是研究人工生命现象的一个重要理论根底。虽然人工生命的研究还处于启蒙阶段,但是演化计算已经在它的演化模型、学习模型和行为模型等方面显示了初步的应用能力。所以可以说,演化计算在人工生命及复杂自适应系统的模型与设计和复杂系统突现性理论研究中将会得到更为深入的开展。5机器学习。学习能力是高级自适应系统应该具备的能力之一。基于演化计算的机器学习,尤其是分类器系统,在很多领域都得到了应用。例如:演化计算被用于模糊控制规那么的学习中,利用演化算法学习隶属度函数,从而能更好地改良模糊系统的性能。基于演化计算的机器学习也可用于调整人工神经网络的连接权,同时也能用于神经网络结构的优化设计。分类器系统也在多机器人路径规划系统中得到了成功的应用。2.6演化计算的研究与开展动态在演化计算的研究中,主要有四类研究方向:1演化计算的理论研究。以前对演化计算的理论研究成果相对较少,但是近年来逐渐活泼了起来,出现了一些收敛性的研究成果,但收敛速度的研究还有待于科学家们的艰苦努力。2用演化算法作为工具解决工程领域的问题,主要是进行优化,它所关心的是能否在传统方法上一些提高。目前大多数的研究相比照拟集中于演化算法的构造,与传统的算法相比,这些算法可以非常高效的解决这些问题。从问题的领域来看,大规模的优化问题,包括单目标优化和多目标优化问题、自适应控制、机器学习、神经网络、人工生命、经济预测、网络优化及演化设计等都是演化计算施展舞台的热点。从方法的本身来看,各种演化模型层出不穷,多层演化、大规模并行演化、协同演化、岛屿模型、演化算法与传统算法的结合与渗透、演化算法与机器学习相结合等等都给演化计算注入了强大的生命力3演化软件,主要是指自动程序设计,由计算机自己来编写程序,并自动进行复杂系统的建模。4演化硬件的研究。演化硬件演化算法+可编程序逻辑器件演化硬件将是未来演化计算开展的一个重要趋势,是一个全新的开展方向。演化硬件即指能像生物一样能根据环境的变化改变自身结构来适应其生存环境的硬件,采用可编程集成电路中的结构位串作为演化算法中的染色体,再通过演化计算来完成硬件功能局部的设计。演化硬件是演化算法和可编程逻辑器件的结合,演化计算也为演化硬件提供了理论与方法的根底,并且可编程集成电路尤其是新一代现场可编程门阵列FPGA为演化硬件提供了丰富的物质根底。演化硬件现在已经在容错系统、模式识别、控制和机器人、电路设计和超大规模集成电路的设计等领域获得到了一定的应用。甚至有人预言,一旦演化硬件得到充分的实现,它将成为一个具有广泛应用前景的新兴产业。3.基于混合粒子群算法求解旅行商问题粒子群优化算法[7]是一种模仿鸟类觅食的群集智能优化算法,具有很强的全局搜索能力,已成为目前解决NP完全问题的又一种较为有效的方法之一。标准粒子群算法存在早熟现象,该算法是通过追随个体极值和群体极值来完成极值寻优的,虽然操作简单,且能够快速收敛,但是随着迭代次数的不断增加,在种群收敛集中的同时,各粒子也越来越相似,可能在局部最优解周边无法跳出。混合粒子群算法摒弃了传统粒子群算法中的通过跟踪极值来更新粒子位置的方法,而是引入了遗传算法中的交叉和变异操作,通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。3.1粒子群算法概述粒子群优化算法PSO是起源于对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现PSO是一种很好的优化工具。是Eberhart博士和kennedy博士创造的一种新的全局优化进化算法。3.1.1粒子群优化算法的根本原理PSO模拟鸟群的捕食行为。设想这样一个场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中,每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子〞。所有的粒子都有一个由被优化的函数决定的适应值fitnessvalue,每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子随机解。然后通过叠代找到最优解。在每一次叠代中,粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值,另一个极值是整个种群目前找到的最优解,这个极值是全局极值。另外也可以不用整个种群而只是用其中一局部最为粒子的邻居,那么在所有邻居中的极值就是局部极值。在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置。(3-1)(3-2)从(3-1)式和(3-2)式可以看出,粒子的移动方向由三局部决定,自己原有的速度、与自己最正确经历的距离和与群体最正确经历的距离,并分别由惯性权重w,c1、c2决定其相对重要性。PSO参数包括[16]:群体规模m,惯性权重w,加速常数c1和c2,最大V,最大代数G。w称为惯性权重,使粒子保持运动的惯性,其大小决定了粒子对当前速度继承了多少,如果没有第一局部,既w0,那么速度只取决于粒子当前的位置和它们历史最好位置,速度本身没有记忆性。假设一个粒子位于全局最好位置,他将保持静止。而其他粒子那么飞向它本身最好位置和全局最好位置的加权中心。在这种条件下,粒子群将统计的收缩到当前的全局最好位置,更像一个局部算法。再加上第一局部后,粒子有扩展搜索空间的趋势,既第一局部有全局搜索的能力。这也使得w的作用为针对不同的搜索问题,调整算法全局和局部搜索能力的平衡。c1,c2是学习因子,或称加速系数,代表将每个粒子推向个体最优位置和群体最优位置的统计加速项的权重。低的值允许微粒在被拉回来之前可以在目标区域外徘徊,而高的值导致粒子突然的冲向或者越过目标区域。如果没有后两局部,既c1c20,粒子将一直以当前的速度飞行,直到到达边界。由于它只能搜索有限的区域,将很难找到好的解。如果没有第二局部,既c10,那么粒子没有认知能力,也就是只有社会social-only〞的模型。在粒子的相互作用下,有能力到达新的搜索空间,它的收敛速度比标准版本更快,但是对复杂问题,比标准版本更容易陷入局部优值点。如果没有第三局部,既c20,那么粒子之间没有社会信息共享,也就是“只有认知cognition-only〞的模型,因为个体间没有交互,一个规模为m的群体等价于m个单个粒子的运行。因而得到解得几率非常小。适宜的c1和c2既可加快收敛又不易陷入局部最优,一般取[0,4]之间的数,一般让c1等于c2。r1和r2是介于[0,1]之间的随机数。是粒子i在第t次迭代中第d维的速度。是粒子i在第t次迭代中第d维的当前位置。在每一维粒子的速度都会被限制在一个最大速度V,如果某一维更新后的速度超过用户设定的V,那么这一维的速度就被限定为V。V决定在当前位置与最好位置之间的分辨率。如果V太高,粒子可能会飞过好解,如果V太小,粒子不能进行足够的探索,导致陷入局部最优。该限制有三个目的:防止计算溢出;实现人工学习和态度转变;决定问题空间搜索的力度。粒子数一般取20?40.其实对于大局部的问题10个粒子已经足够可以取得好的结果,不过对于比拟难的问题或者特定类别的问题,粒子数可以取到100或200。粒子的长度是由优化问题决定的,就是问题解的长度。粒子的范围由优化问题决定,每一维可设定不同的范围。3.1.2粒子群优化算法描述和流程图粒子群优化算法流程描述如下:步骤1初始化粒子群,即随机设定各粒子的的初始位置xi和初始速度vi;步骤2计算每个粒子的适应度值;步骤3对每个粒子,比拟它们的适应度值和它经历的最好位置pid的适应度值,假设更好,更新pid;步骤4对每个粒子,比拟它们的适应度值和群体经历的最好位置gid的适应度值,假设更好更新gid;步骤5根据位置和速度的更新公式调整粒子的位置和速度;3.1.3粒子群优化算法特点群体智能由大量简单个体相互交流和协作涌现出的智能行为。粒子群优化PSO算法实现容易、精度高、收敛快,粒子还有一个重要的特点,就是有记忆。PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质。但是它比遗传算法规那么更为简单,它没有遗传算法的“交叉〞Crossover和“变异〞Mutation操作。它通过追随当前搜索到的最优值来寻找全局最优。PSO的一个优势就是采用实数编码,不需要像遗传算法一样是二进制编码或者采用针对实数的遗传操作。例如对于问题fxx1^2x2^2x3^2求解,粒子可以直接编码为x1,x2,x3,而适应度函数就是fx。接着我们就可以利用前面的过程去寻优。这个寻优过程是一个叠代过程,中止条件一般为设置为到达最大循环数或者最小错误。3.2遗传算法概述对于一个求函数最大值的优化问题(求函数最小值也类同),遗传算法(GeneticAlgorithm)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。3.2.1遗传算法的根本原理遗传算法[10]是由美国的J.Holland教授1975年首先提出的,其主要特点是直接对结构对象进行操作,不存在求异和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应的调整搜索方向,不需要确定的规那么。遗传算法的这些性质,已被人们广泛的应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题求函数最小值也类同,一般可以描述为以下数学规划模型:(3-3)(3-4)(3-5)(3-3)式中为决策变量,为目标函数式,式(3-4),(3-5)为约束条件,U是根本空间,R是U的子集,满足约束条件的解X称为可行解,集合R表示所有满足约束条件的解所组成的集合,称为可行解集合。遗传算法[5]是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群那么由经过基因(gene)编码的一定数目的个体individual组成。每个个体实际上是染色体chromosome带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。3.2.2遗传算法步骤遗传算法的根本步骤如下:1初始化:设置进化代数计数器,t0,设置最大进化代数T,随机生成M个个体作为初始群体P0。2个体评价:计算群体Pt中各个个体的适应度。3选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过对交配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评价根底上的。4交叉运算:将交叉算子作用于群体。所谓交叉是指把两个父代个体的局部结构加以替换重组生成新个体的操作。遗传算法中起核心作用的就是交叉算子。5变异运算:将变异算子作用于群体。既是对群体中的个体串的某些基因座上的基因值作变动。群体Pt经过选择、交叉、变异运算之后得到下一代群体Pt.6终止条件判断:假设tT,那么以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。3.3旅行商问题概述著名的旅行商问题,是一类NP完全的组合优化问题,具有广泛的实际应用价值,例如:城市管道铺设优化、物流行业中的车辆调度优化、制造业中的切割路径优化等现实生活中的很多优化问题都可以归结为TSP模型来求解。3.3.1旅行商问题概述旅行商问题TravelingSalesmanProblem,简记TSP[11]是组合数学中一个古老而又困难的问题,它易于描述但至今尚未彻底解决,现己归入所谓的NP完全问题类,经典提法为:有一货物推销员要去假设干个城市推销货物,从城市1出发,经其余各城市一次,然后回到城市1,问选择怎样的行走路线,才能使总行程最短(各城市间距离为己知)。该问题在图论的意义下就是所谓