基于混合粒子群算法的旅行商問題研究（已處理）

基于混合粒子群算法的旅行商問題研究摘要演化計(jì)算是模擬自然界生物演化過程的一種群體導(dǎo)向隨機(jī)搜索技術(shù)。近年來,用演化算法求解組合優(yōu)化問題已經(jīng)成為研究熱點(diǎn),旅行商問題,是一類NP完全的組合優(yōu)化問題,有效地求解旅行商問題,對(duì)于組合優(yōu)化問題的求解有著十分重要的意義。標(biāo)準(zhǔn)粒子群算法[6]通過追隨個(gè)體極值和群體極值來完成極值尋優(yōu)的,雖然操作簡(jiǎn)單,且能夠快速收斂,但是隨著迭代次數(shù)的不斷增加,在種群收斂集中的同時(shí),各粒子也越來越相似,可能在局部解周邊無法跳出。針對(duì)該算法的缺乏,本文在標(biāo)準(zhǔn)粒子群優(yōu)化算法的根底上通過引用遺傳算法思想中的交叉和變異操作來改善粒子群算法,從而防止了標(biāo)準(zhǔn)粒子群優(yōu)化算法可能陷入局部最優(yōu)的情況,并將其應(yīng)用于求解旅行商(TSP)問題。本文將改良的粒子群算法在14城市和30城市及50城市這三個(gè)實(shí)例中進(jìn)行了仿真,結(jié)果說明了基于混合粒子群優(yōu)化算法對(duì)于求解組合優(yōu)化問題的優(yōu)越性,對(duì)小規(guī)模城市坐標(biāo)精確度非常高。關(guān)鍵詞:粒子群算法;組合優(yōu)化;遺傳算法;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本文的組織與結(jié)構(gòu) 22.演化計(jì)算概述 32.1演化計(jì)算的歷史與開展 32.2演化算法的框架 42.3演化計(jì)算的特點(diǎn) 52.4演化計(jì)算的分支 62.5演化計(jì)算的應(yīng)用 72.6演化計(jì)算的研究與開展動(dòng)態(tài) 83.基于混合粒子群算法求解旅行商問題 93.1粒子群算法概述 93.2遺傳算法概述 113.3旅行商問題概述 133.4混合粒子群優(yōu)化算法求解旅行商問題 143.5仿真實(shí)驗(yàn) 163.6結(jié)論 244.總結(jié)與展望 25致謝 26參考文獻(xiàn) 27基于混合粒子群算法的旅行商問題研究1.緒論1.1選題的背景、目的和意義仿生優(yōu)化算法特別是演化算法,已被廣泛應(yīng)用于各種科學(xué)技術(shù)和工程問題中。演化算法是以達(dá)爾文的進(jìn)化論思想為根底,通過模擬生物進(jìn)化過程與機(jī)制的求解問題的自組織、自適應(yīng)的人工智能技術(shù),是指基于“優(yōu)勝劣汰〞進(jìn)化理論的尋優(yōu)算法[2]。近年來,一種新型的演化算法誕生:群集智能算法SwarmIntelligenceAlgorithms,簡(jiǎn)稱SIA,群智能SwarmIntelligence,SI的概念最早由Beni,Hackwood和Wang在分子自動(dòng)機(jī)系統(tǒng)中提出。群集智能算法作為一種基于概率搜索能力的計(jì)算方法,有著比傳統(tǒng)算法更優(yōu)的優(yōu)點(diǎn):①群體中相互之間合作的個(gè)體是分布的;②可以通過個(gè)體之間間接的通信進(jìn)行合作,從而具有良好的可擴(kuò)充性;③沒有中心的控制,具有魯棒性;④單個(gè)的個(gè)體能力較簡(jiǎn)單,實(shí)現(xiàn)時(shí)比擬方便,具有簡(jiǎn)單性。群智能算法作為一種新興的演化計(jì)算技術(shù),已成為越來越多研究者的關(guān)注焦點(diǎn),它與人工生命,特別是進(jìn)化策略以及遺傳算法有著極為特殊的聯(lián)系。群智能理論研究領(lǐng)域主要有兩種算法:蟻群算法和粒子群優(yōu)化算法。蟻群算法是對(duì)螞蟻群落食物采集過程的模擬,已成功應(yīng)用于許多離散優(yōu)化問題。粒子群優(yōu)化算法也是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬,最初是模擬鳥群覓食的過程,但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。粒子群算法,也稱粒子群優(yōu)化算法,縮寫PSO[7],是近年來開展起來的一種新的進(jìn)化算法,是一種進(jìn)化計(jì)算技術(shù)evolutionarycomputation,1995年由Eberhart和kennedy提出。旅行商問題(TSP)[11]是數(shù)學(xué)領(lǐng)域中著名問題之一,是一個(gè)經(jīng)典的組合優(yōu)化問題。假設(shè)有一個(gè)旅行商人要拜訪N個(gè)城市,他必須選擇所要走的路徑,路徑的限制是每個(gè)城市只能拜訪一次,而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值,這是一個(gè)NP難題。由于其在交通運(yùn)輸、電路板線路設(shè)計(jì)以及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用,因此設(shè)計(jì)高效算法來求解旅行商問題具有重要的理論和實(shí)際意義,國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究,更多更有效的方法有待進(jìn)一步被探討和開掘。本文在粒子群算法的根底上引入遺傳算法的交叉和變異操作,目的在于:克服標(biāo)準(zhǔn)粒子群優(yōu)化算法中的局部?jī)?yōu)先問題,克服遺傳算法中復(fù)雜的編碼實(shí)現(xiàn),使操作變得簡(jiǎn)單,實(shí)現(xiàn)變得容易,提高精確度;為旅行商問題尋求更優(yōu)解。而本文的實(shí)際意義在于:粒子群算法作為一種新的進(jìn)化算法,其開展和研究的時(shí)間并不長(zhǎng),旅行商問題,是一類NP完全的組合優(yōu)化問題,在各領(lǐng)域有著廣泛的應(yīng)用,在粒子群算法中引入交叉和變異操作來求解旅行商問題,是一次有意義的嘗試。1.2研究綜述演化算法[3]是一類模擬自然界遺傳進(jìn)化規(guī)律的仿生學(xué)算法,經(jīng)過假設(shè)干年的研究開展,已經(jīng)形成一個(gè)龐大的學(xué)術(shù)家族。近年來,一種新型的演化算法誕生:群集智能算法SwarmIntelligenceAlgorithms,簡(jiǎn)稱SIA,群智能SwarmIntelligence,SI的概念最早由Beni,Hackwood和Wang在分子自動(dòng)機(jī)系統(tǒng)中提出。典型的群集智能算法有Dorigo提出的蟻群算法AntColonyAlgorithms,Kenndy與Eberthart提出的粒子群優(yōu)化算法ParticleSwarmOptimization,PSO。在國(guó)外,關(guān)于演化算法的研究一直領(lǐng)先于國(guó)內(nèi),開展也比擬成熟,許多理論體系和研究體系已經(jīng)非常完善,我國(guó)學(xué)者接觸這個(gè)領(lǐng)域較晚,目前尚未形成聲勢(shì)和有規(guī)模的研究隊(duì)伍,但武漢大學(xué)對(duì)演化算法的研究較深入,處于國(guó)內(nèi)領(lǐng)先地位。自從1995年Eberhart和kennedy提出原始粒子群以后,Shi.Y和Eberhart分析了PSO算法的參數(shù)選擇,并將慣性權(quán)重引入PSO,并相繼提出了線性遞減慣性權(quán)重LDIW、模糊慣性權(quán)重FIW和隨機(jī)慣性權(quán)重RIW。Clerc對(duì)算法的參數(shù)選擇和收斂性進(jìn)行了初步的數(shù)學(xué)分析,引入收斂因子以保證算法的收斂;Ozcan和Mohan對(duì)原始PSO算法進(jìn)行了數(shù)學(xué)分析,指出停留在離散時(shí)間狀態(tài)的粒子軌跡是連續(xù)的正弦波形。PSO算法存在著收斂速度和收斂質(zhì)量之間的矛盾。為了獲得更好的優(yōu)化性能,研究者們提出了各種改良的PSO算法。Angeline通過引入GA中的選擇機(jī)制得到混合PSO,該算法提高了收斂速度,但也增加了陷入局部極值的可能;Lovbjerg和Rasmussen等提出了具有繁殖和子群的雜交PSO算法,將GA中的交叉機(jī)制引入PSO,由于后代選擇并不是基于適應(yīng)度值,防止了基于適應(yīng)度值選擇對(duì)那些多局部極值的函數(shù)優(yōu)化時(shí)帶來的潛在的問題。此外,很多的研究者也嘗試著研究將其它的優(yōu)化技術(shù)與PSO相結(jié)合、能充分發(fā)揮各個(gè)算法優(yōu)點(diǎn)的混合算法。本次課題設(shè)計(jì)的主要目的是對(duì)混合粒子群算法求解旅行商問題的研究和討論,在標(biāo)準(zhǔn)粒子群算法的根底上引入交叉操作和變異操作,用于旅行商問題的求解,并對(duì)結(jié)果進(jìn)行比照分析。1.3本文的主要工作本文的主要工作是對(duì)混合粒子群算法進(jìn)行研究,并將其用于求解旅行商問題。首先研究了演化計(jì)算的由來和理論根底,以及其特點(diǎn),在此根底上又研究了粒子群優(yōu)化算法和遺傳算法,并將粒子群算法和遺傳算法相結(jié)合,接著了解了組合優(yōu)化問題,并仔細(xì)研究了旅行商問題。接著把改良的粒子群算法用于旅行商問題的求解,通過仿真實(shí)驗(yàn)得出結(jié)果并與當(dāng)前最優(yōu)路徑進(jìn)行比照分析。1.4本文的組織與結(jié)構(gòu)論文的結(jié)構(gòu)安排如下:第1章:引言,這局部主要介紹了有關(guān)本課題的選題目的和意義,并且也簡(jiǎn)單介紹了本文的主要工作。第2章:演化計(jì)算,在這個(gè)章節(jié)主要對(duì)演化計(jì)算的歷史與開展、演化計(jì)算的框架結(jié)構(gòu)、演化計(jì)算的特點(diǎn)和分支以及演化計(jì)算的應(yīng)用等做了詳細(xì)的介紹。第3章:基于混合粒子群算法求解旅行商問題,這個(gè)章節(jié)主要介紹了粒子群算法,遺傳算法及旅行商問題,并對(duì)算法進(jìn)行了仿真實(shí)驗(yàn),對(duì)所得結(jié)果與當(dāng)前最正確路徑進(jìn)行了比照分析。第4章:結(jié)論與展望,對(duì)全文做出了總結(jié),指出了論文的缺乏之處,展望課題開展的前景。2.演化計(jì)算概述演化計(jì)算[3]是模擬自然界生物演化過程產(chǎn)生的一種群體導(dǎo)向隨機(jī)搜索技術(shù),它的根本原那么是優(yōu)勝劣汰的自然選擇法那么。演化計(jì)算采用簡(jiǎn)單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu),并通過對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作再生、雜交和變異和優(yōu)勝劣汰的競(jìng)爭(zhēng)機(jī)制來指導(dǎo)對(duì)問題空間的搜索。簡(jiǎn)而言之,演化計(jì)算不用了解問題的全部特征,就可以通過表達(dá)進(jìn)化機(jī)制的演化過程完成問題的求解。2.1演化計(jì)算的歷史與開展演化計(jì)算EvolutionaryComputation,簡(jiǎn)稱EC是源于對(duì)生物進(jìn)化的模擬的一類基于種群的概率搜索方法。它的生物學(xué)理論根底有兩個(gè):達(dá)爾文的自然選擇學(xué)說和基于分子生物學(xué)的遺傳理論。達(dá)爾文的自然選擇學(xué)說認(rèn)為,生物是有變異的,變異可能引起個(gè)體性狀的差異,由于生物體的繁育潛力超過實(shí)際的繁育率,適應(yīng)度高的個(gè)體將生存下來,其所帶有的變異因?yàn)楹侠矶嫦聛?。環(huán)境的多樣性也使得生物界通過自然選擇而獲得了多樣性?；诜肿由飳W(xué)的遺傳理論發(fā)現(xiàn),生物上下代之間傳遞遺傳信息物質(zhì)是DNA,其主要載體是染色體,染色體上具有遺傳效應(yīng)的DNA片段稱為基因。DNA的雙螺旋結(jié)構(gòu)使得兩個(gè)父代能有規(guī)律地將各自一半的染色體遺傳給下一代,下一代的基因根本上是上一代基因的重新組合,同時(shí)在遺傳過程中還會(huì)發(fā)生基因的突變,產(chǎn)生一些新的基因,引起新的個(gè)體性狀差異。通過對(duì)自然進(jìn)化過程的簡(jiǎn)單化模擬得到一種有效的計(jì)算機(jī)算法,這種思想的萌芽在二十世紀(jì)五六十年代已屢次相互獨(dú)立地出現(xiàn),在二十世紀(jì)七八十年代才得到開展和推廣,這一過程一直是沿著三條相對(duì)獨(dú)立的研究線索而開展,并導(dǎo)致形成了三個(gè)主流,即遺傳算法GeneticAlgorithm,簡(jiǎn)稱GA、演化規(guī)劃EvolutionaryProgramming,簡(jiǎn)稱EP和演化策略EvolutionStrategies,簡(jiǎn)稱ES。遺傳編程GeneticProgramming,簡(jiǎn)稱GP那么是遺傳算法的分支。直到1994年第一屆InternationalConferenceonEvolutionaryComputation的召開,以上這些算法才被統(tǒng)稱為演化計(jì)算。演化計(jì)算采用簡(jiǎn)單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu),并且通過對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選法那么來指導(dǎo)學(xué)習(xí)和確定搜索的方向。由于演化計(jì)算采用種群的方式進(jìn)行搜索,這使它可以同時(shí)地搜索解空間內(nèi)的多個(gè)區(qū)域。并且使用種群進(jìn)行搜索的方式能使演化算法特別適合于大規(guī)模的并行計(jì)算。在賦予演化計(jì)算自組織、自適應(yīng)、自學(xué)習(xí)等特性的同時(shí),優(yōu)勝劣汰的自然選擇和簡(jiǎn)單的遺傳操作也使演化計(jì)算具有不受它的搜索空間限制性條件如可微、連續(xù)、單峰等的約束以及也不需要其它輔助信息如導(dǎo)數(shù)的特點(diǎn)。這些新的特點(diǎn)使演化算法不僅能獲得較高的效率而且也具有簡(jiǎn)單、易操作和通用的特性,而且這些特性正是演化計(jì)算越來越受到廣闊研究人員青睞的主要原因之一。演化計(jì)算在二十世紀(jì)六七十年代未受到重視。主要原因如下:①當(dāng)時(shí)這些方法本身還不夠成熟;②這些方法需要較大的計(jì)算量,并且當(dāng)時(shí)的計(jì)算機(jī)還不夠普以及速度也跟不上要求,這樣便限制了它們的應(yīng)用;③當(dāng)時(shí)基于符號(hào)處理的人工智能方法正處于頂峰狀態(tài),使人們難以認(rèn)識(shí)到其它方法的有效性和適應(yīng)性。到了二十世紀(jì)八十年代,人們?cè)絹碓角宄卣J(rèn)識(shí)到傳統(tǒng)人工智能方法的局限性,由于計(jì)算機(jī)速度的提高和并行計(jì)算機(jī)的普及,已使演化計(jì)算對(duì)于機(jī)器速度的要求不再是制約其開展的因素。同時(shí)也由于它的不斷開展及其在一些應(yīng)用領(lǐng)域內(nèi)取得了成功,演化計(jì)算已表現(xiàn)出了良好的應(yīng)用前景。現(xiàn)在,演化計(jì)算的研究?jī)?nèi)容十分廣泛,例如演化計(jì)算的設(shè)計(jì)與分析、演化計(jì)算的理論根底以及在各個(gè)領(lǐng)域中的應(yīng)用等。隨著演化計(jì)算的理論研究的不斷深入和應(yīng)用領(lǐng)域的不斷擴(kuò)展,演化計(jì)算將會(huì)取得很大的成功,必將在當(dāng)今社會(huì)占據(jù)更重要的位置。2.2演化算法的框架演化算法在求解問題的過程是從多個(gè)解開始的,然后通過一定的法那么逐步迭代來產(chǎn)生新的解。演化算法首先將問題的可行解進(jìn)行相應(yīng)的編碼,這些已經(jīng)編碼的解被稱為染色體或稱為個(gè)體,記為,,,…,等。這里的t表示的是迭代數(shù),稱為演化代數(shù)。一定數(shù)量的個(gè)體組成了一個(gè)群體,記作。群體中個(gè)體的數(shù)目稱作群體的大小,記作N。演化算法的搜索是始于這個(gè)群體的,最初產(chǎn)生的群體叫作初始群體。初始群體產(chǎn)生以后,算法模擬遺傳學(xué)中的雜交、變異和復(fù)制等操作方式來設(shè)計(jì)出演化算子,采用優(yōu)勝劣汰的自然選擇法那么來指導(dǎo)、學(xué)習(xí)和確定搜索的方向,這個(gè)過程就叫作演化過程。在演化過程中,要選擇當(dāng)前解進(jìn)行雜交以產(chǎn)生新解,這些當(dāng)前解那么稱為新解的父解或稱作父代個(gè)體,產(chǎn)生的新解那么稱為后代解或稱為子代個(gè)體。演化算法的根本流程可以描述如下:隨機(jī)初始化群體;計(jì)算中的個(gè)體的適應(yīng)值;while不滿足結(jié)束條件do由通過特定的演化操作來形成新的群體;計(jì)算中的個(gè)體的適應(yīng)值,并;由算法的根本流程可知,演化算法對(duì)待求解的問題的本身是一無所知的,它所能做的只是對(duì)算法所產(chǎn)生的每一個(gè)個(gè)體進(jìn)行相應(yīng)的評(píng)價(jià),并通過遺傳操作來產(chǎn)生新一代的群體,使適應(yīng)值相對(duì)較好的個(gè)體比適應(yīng)值相對(duì)較差的個(gè)體有更多的繁殖后代的時(shí)機(jī)。如此一代一代地演化下去,一直到算法滿足給定的終止條件為止。演化算法的根本流程圖如圖2.1所示。圖2.1演化算法根本流程圖2.3演化計(jì)算的特點(diǎn)演化算法采用的是簡(jiǎn)單的編碼技術(shù)來表示各種復(fù)雜的體系結(jié)構(gòu),并通過對(duì)某一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作如選擇、雜交和變異和由優(yōu)勝劣汰的競(jìng)爭(zhēng)機(jī)制來指導(dǎo)對(duì)空間的搜索。概括地講就是,演化算法不用了解問題的全部特征和屬性,就可以通過進(jìn)化機(jī)制的演化過程來完成問題的求解。演化算法,諸如演化規(guī)劃EP、遺傳算法GA、演化策略ES都是一種模擬生物進(jìn)化的隨機(jī)計(jì)算模型,通過反復(fù)屢次的迭代,使那些對(duì)環(huán)境有比擬強(qiáng)的適應(yīng)能力的個(gè)體存活下來。這種模型不需要所求函數(shù)的其它輔助信息,而能夠到達(dá)相當(dāng)高的精度要求,尤其是那些適合一些非線性的和超高維的問題的優(yōu)化。研究演化計(jì)算不可防止會(huì)遇到的一個(gè)現(xiàn)實(shí)問題就是關(guān)于演化計(jì)算的數(shù)學(xué)證明迄今為止還根本上仍是一個(gè)空白,也就是至今無法用數(shù)學(xué)的方法來證明演化計(jì)算的有效性,也即無法證明演化計(jì)算為何會(huì)具有收斂性。同樣,當(dāng)我們得到一個(gè)比擬好的問題的解時(shí),無法直接證明它就是這個(gè)問題的最優(yōu)解,原因在于這個(gè)解是我們搜索出來的,而每次搜索結(jié)果可能都不一樣,所以無法證明這次搜索的解就一定是解決問題的最好的解。與傳統(tǒng)的算法相比擬,演化算法具有以下的一些特點(diǎn):1應(yīng)用演化來計(jì)算求解問題時(shí),在確定了編碼的方案,適應(yīng)值函數(shù)以及演化算子之后,算法將會(huì)利用演化過程中所獲得的信息自行進(jìn)行組織搜索。由于自然的選擇策略為“優(yōu)勝劣汰,適者生存〞,因而適應(yīng)值大的個(gè)體就具有較高的生存概率。故而適應(yīng)值大的個(gè)體那么有與環(huán)境更適應(yīng)的基因結(jié)構(gòu)。此類基因結(jié)構(gòu)通過雜交與變異等遺傳操作就可能產(chǎn)生更能適應(yīng)生存環(huán)境的后代。而演化算法的這種自組織、自適應(yīng)特征同時(shí)也賦予了它所具有能根據(jù)環(huán)境的變化自動(dòng)的發(fā)現(xiàn)當(dāng)前生存環(huán)境的特征和規(guī)律的能力。2演化算法采用種群的方式進(jìn)行組織搜索,從而使它可以同時(shí)搜索解空間的多片區(qū)域,并且能以比擬大的概率跳出局部最優(yōu),來找出全局的最優(yōu)解,因而可以有效的防止了搜索過程收斂于局部最優(yōu)化解的情況。3演化算法只需要得到目標(biāo)函數(shù)的取值信息,不需要其它附加信息,因而適用于任何類型的大規(guī)模、非線性的不連續(xù)函數(shù)的優(yōu)化問題以及無解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化問題,具有非常強(qiáng)的通用性。4演化算法同時(shí)具有并行計(jì)算的特點(diǎn)。算法的操作對(duì)象一般是一組可行解,而非單個(gè)的可行解;搜索軌道也是有多條,而非單條,因而具有良好的并行性。5演化計(jì)算是利用個(gè)體的適應(yīng)值來推動(dòng)種群的演化的,而不管問題本身的結(jié)構(gòu)特征,在利用演化算法來求解問題時(shí),我們只需要計(jì)算相應(yīng)的編碼方式和演化算子,而不需要修改算法自身的組織結(jié)構(gòu)。除此之外,當(dāng)問題中的環(huán)境發(fā)生動(dòng)態(tài)變化時(shí),因?yàn)檠莼?jì)算本身就是一個(gè)動(dòng)態(tài)演化的過程,它也就能動(dòng)態(tài)適應(yīng)環(huán)境,演化過程就能繼續(xù)演化下去而不需要重新的進(jìn)行初始化。2.4演化計(jì)算的分支演化計(jì)算最初具有三大分支:即于20世紀(jì)70年代由Holland提出的遺傳算法GeneticAlgorithms,簡(jiǎn)稱GA,同期由Rechenberg和Schewefel等提出的進(jìn)化策略EvolutionaryStrategy,簡(jiǎn)稱ES以及于1960年代由Fogel、Owens和Walsh提出的進(jìn)化規(guī)劃EvolutionaryProgramming,簡(jiǎn)稱EP。20世界90年代在遺傳算法的根底上又開展了一個(gè)分支:即由J.Koza提出的遺傳程序設(shè)計(jì)GeneticProgramming,簡(jiǎn)稱GP。這幾個(gè)分支具有一個(gè)共同點(diǎn)就是都是借助生物演化的思想和原理來解決實(shí)際的問題。1遺傳算法。將進(jìn)化論與計(jì)算機(jī)科學(xué)結(jié)合起來的嘗試開始于二十世紀(jì)五十年代,但由于缺乏一種通用的編碼方案,使得人們只能依賴變異而不是交配來產(chǎn)生新的基因結(jié)構(gòu),到二十世紀(jì)六十年代,位串編碼技術(shù)出現(xiàn),這種編碼技術(shù)不但適于變異操作。而已同樣適于交配即雜交操作。并且強(qiáng)調(diào)將交配作為主要的遺傳操作。遺傳算法的通用編碼技術(shù)和簡(jiǎn)單有效的遺傳操作意義重大,并為其廣泛、成功的應(yīng)用奠定了堅(jiān)實(shí)的根底。Holland遺傳算法被稱為簡(jiǎn)單遺傳算法SGA。2演化規(guī)劃。演化規(guī)劃的方法最初是由//.el等提出在1960年代。他們?cè)谘芯咳斯ぶ悄艿臅r(shí)候發(fā)現(xiàn),智能行為就是具有感應(yīng)其所處環(huán)境的狀態(tài)、并按給定目標(biāo)自動(dòng)做出適當(dāng)響應(yīng)的能力。在研究中,他們將模擬環(huán)境描述成由有限字符集中的符號(hào)組成的序列。于是問題就被轉(zhuǎn)化為,如何根據(jù)當(dāng)前觀察到的符號(hào)序列做出響應(yīng),以獲得最大收益。這里,收益主要由環(huán)境中將要出現(xiàn)的下一個(gè)符號(hào)及預(yù)先定義好的效益目標(biāo)來確定。他們將此方法應(yīng)用到數(shù)據(jù)診斷、模式識(shí)別和分類及控制系統(tǒng)的設(shè)計(jì)等問題中,取得了較好的結(jié)果。3演化策略。1960年代初,柏林工業(yè)大學(xué)的學(xué)生I.Rechenberg和//.wefel[2]在進(jìn)行風(fēng)洞實(shí)驗(yàn)時(shí),由于用傳統(tǒng)的方法難以對(duì)設(shè)計(jì)中描述物體形狀的參數(shù)進(jìn)行優(yōu)化。因而利用生物遺傳和變異的思想來改變參數(shù)值,并獲得了較好的效果。隨后,他們對(duì)這種方法進(jìn)行了深入的研究和探索。形成了演化計(jì)算的另一個(gè)分支演化策略。4遺傳程序設(shè)計(jì)。自計(jì)算機(jī)出現(xiàn)以來,計(jì)算機(jī)科學(xué)的一個(gè)方向性目標(biāo)就是讓計(jì)算機(jī)自主進(jìn)行程序設(shè)計(jì),即只要告訴計(jì)算機(jī)要解決的問題,而不需要告訴它具體如何去做。遺傳程序設(shè)計(jì)便是在該領(lǐng)域的一種嘗試。它采用演化算法中遺傳算法的根本思想,但使用一種更為靈活的表示方式??使用分層結(jié)構(gòu)來表示解空間。這些分層結(jié)構(gòu)有葉節(jié)點(diǎn)和中間節(jié)點(diǎn),葉結(jié)點(diǎn)是所需解決問題的原始變量,中間結(jié)點(diǎn)那么是組合這些原始變量的函數(shù)。這樣,每個(gè)分層結(jié)構(gòu)對(duì)應(yīng)問題的一個(gè)可行解。遺傳程序設(shè)計(jì)就是使用一些遺傳操作動(dòng)態(tài)地改變這些結(jié)構(gòu),以獲得解決該問題的可行的計(jì)算機(jī)程序。遺傳程序設(shè)計(jì)的思想是Stanford大學(xué)的//.a在1990年代初提出的。2.5演化計(jì)算的應(yīng)用從演化計(jì)算的原理來看,它適用于一些沒有好的數(shù)學(xué)方法來解決的問題,或者是數(shù)學(xué)方法解決的不好的各類問題。如這里的背包問題,雖然定義非常簡(jiǎn)單,但沒有可使用的常規(guī)的數(shù)學(xué)方法解決的可能,用窮舉法也是無法解決這個(gè)問題的,但是演化算法卻可以在一定的程度上解決這個(gè)問題。演化計(jì)算為我們提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架,它并不依賴于問題的具體領(lǐng)域,而對(duì)問題的種類有很強(qiáng)的魯棒性,所以演化計(jì)算在大型優(yōu)化問題的求解、自適應(yīng)控制、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、人工生命、經(jīng)濟(jì)預(yù)測(cè)等領(lǐng)域中都取得了比擬大的成功,已然引起了包括數(shù)學(xué)、物理學(xué)、化學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)及工程應(yīng)用等領(lǐng)域科學(xué)工作者們和學(xué)者們的極大興趣。演化計(jì)算的主要應(yīng)用領(lǐng)域如下:1生物技術(shù)和生物學(xué)。演化計(jì)算的機(jī)理來自源生物學(xué),同時(shí)又效勞于生物學(xué),用演化計(jì)算的方法可以用來來研究一些生物學(xué)的現(xiàn)象。2優(yōu)化。其中包括函數(shù)優(yōu)化和組合優(yōu)化問題。函數(shù)優(yōu)化是演化計(jì)算經(jīng)典的應(yīng)用領(lǐng)域,同時(shí)也是對(duì)演化計(jì)算進(jìn)行性能評(píng)價(jià)的常用算例。人們構(gòu)造出了許許多多的各種形式的測(cè)試函數(shù),有連續(xù)函數(shù)也有離散函數(shù),有低維函數(shù)也有高維函數(shù),有凸函數(shù)也有凹函數(shù),有單峰函數(shù)也有多峰函數(shù),有確定性函數(shù)也有隨機(jī)性函數(shù)等等。對(duì)于高度非線性、多目標(biāo)的函數(shù)優(yōu)化問題,使用演化算法可以很方便地得到它們的解,但傳統(tǒng)的方法往往難以奏效。演化計(jì)算在函數(shù)優(yōu)化中的應(yīng)用成果甚豐。3圖像處理和模式識(shí)別。圖像處理和模式識(shí)別是計(jì)算機(jī)視覺中的一個(gè)重要研究領(lǐng)域。在圖像處理過程中,比方掃描、特征提取、圖像分割等都會(huì)不可防止地產(chǎn)生一些誤差,這些誤差肯能會(huì)影響到圖像處理和識(shí)別的效果。怎樣使這些誤差最小是使計(jì)算機(jī)視覺到達(dá)實(shí)用化的一個(gè)重要要求。演化計(jì)算在圖像處理中的優(yōu)化計(jì)算方面是完全可以勝任的。4人工生命。人工生命是指以計(jì)算機(jī)為媒介模擬生命或具有生命特征的行為,包括自組織、自學(xué)習(xí)及信息的復(fù)制和傳播行為。自組織和自學(xué)習(xí)能力是人工生命的兩個(gè)主要特征。人工生命與演化計(jì)算存在著密切的關(guān)系,基于演化計(jì)算的模型演化是研究人工生命現(xiàn)象的一個(gè)重要理論根底。雖然人工生命的研究還處于啟蒙階段,但是演化計(jì)算已經(jīng)在它的演化模型、學(xué)習(xí)模型和行為模型等方面顯示了初步的應(yīng)用能力。所以可以說,演化計(jì)算在人工生命及復(fù)雜自適應(yīng)系統(tǒng)的模型與設(shè)計(jì)和復(fù)雜系統(tǒng)突現(xiàn)性理論研究中將會(huì)得到更為深入的開展。5機(jī)器學(xué)習(xí)。學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)應(yīng)該具備的能力之一。基于演化計(jì)算的機(jī)器學(xué)習(xí),尤其是分類器系統(tǒng),在很多領(lǐng)域都得到了應(yīng)用。例如:演化計(jì)算被用于模糊控制規(guī)那么的學(xué)習(xí)中,利用演化算法學(xué)習(xí)隸屬度函數(shù),從而能更好地改良模糊系統(tǒng)的性能?；谘莼?jì)算的機(jī)器學(xué)習(xí)也可用于調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán),同時(shí)也能用于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化設(shè)計(jì)。分類器系統(tǒng)也在多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。2.6演化計(jì)算的研究與開展動(dòng)態(tài)在演化計(jì)算的研究中,主要有四類研究方向:1演化計(jì)算的理論研究。以前對(duì)演化計(jì)算的理論研究成果相對(duì)較少,但是近年來逐漸活潑了起來,出現(xiàn)了一些收斂性的研究成果,但收斂速度的研究還有待于科學(xué)家們的艱苦努力。2用演化算法作為工具解決工程領(lǐng)域的問題,主要是進(jìn)行優(yōu)化,它所關(guān)心的是能否在傳統(tǒng)方法上一些提高。目前大多數(shù)的研究相比照擬集中于演化算法的構(gòu)造,與傳統(tǒng)的算法相比,這些算法可以非常高效的解決這些問題。從問題的領(lǐng)域來看,大規(guī)模的優(yōu)化問題,包括單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題、自適應(yīng)控制、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、人工生命、經(jīng)濟(jì)預(yù)測(cè)、網(wǎng)絡(luò)優(yōu)化及演化設(shè)計(jì)等都是演化計(jì)算施展舞臺(tái)的熱點(diǎn)。從方法的本身來看,各種演化模型層出不窮,多層演化、大規(guī)模并行演化、協(xié)同演化、島嶼模型、演化算法與傳統(tǒng)算法的結(jié)合與滲透、演化算法與機(jī)器學(xué)習(xí)相結(jié)合等等都給演化計(jì)算注入了強(qiáng)大的生命力3演化軟件,主要是指自動(dòng)程序設(shè)計(jì),由計(jì)算機(jī)自己來編寫程序,并自動(dòng)進(jìn)行復(fù)雜系統(tǒng)的建模。4演化硬件的研究。演化硬件演化算法+可編程序邏輯器件演化硬件將是未來演化計(jì)算開展的一個(gè)重要趨勢(shì),是一個(gè)全新的開展方向。演化硬件即指能像生物一樣能根據(jù)環(huán)境的變化改變自身結(jié)構(gòu)來適應(yīng)其生存環(huán)境的硬件,采用可編程集成電路中的結(jié)構(gòu)位串作為演化算法中的染色體,再通過演化計(jì)算來完成硬件功能局部的設(shè)計(jì)。演化硬件是演化算法和可編程邏輯器件的結(jié)合,演化計(jì)算也為演化硬件提供了理論與方法的根底,并且可編程集成電路尤其是新一代現(xiàn)場(chǎng)可編程門陣列FPGA為演化硬件提供了豐富的物質(zhì)根底。演化硬件現(xiàn)在已經(jīng)在容錯(cuò)系統(tǒng)、模式識(shí)別、控制和機(jī)器人、電路設(shè)計(jì)和超大規(guī)模集成電路的設(shè)計(jì)等領(lǐng)域獲得到了一定的應(yīng)用。甚至有人預(yù)言,一旦演化硬件得到充分的實(shí)現(xiàn),它將成為一個(gè)具有廣泛應(yīng)用前景的新興產(chǎn)業(yè)。3.基于混合粒子群算法求解旅行商問題粒子群優(yōu)化算法[7]是一種模仿鳥類覓食的群集智能優(yōu)化算法,具有很強(qiáng)的全局搜索能力,已成為目前解決NP完全問題的又一種較為有效的方法之一。標(biāo)準(zhǔn)粒子群算法存在早熟現(xiàn)象,該算法是通過追隨個(gè)體極值和群體極值來完成極值尋優(yōu)的,雖然操作簡(jiǎn)單,且能夠快速收斂,但是隨著迭代次數(shù)的不斷增加,在種群收斂集中的同時(shí),各粒子也越來越相似,可能在局部最優(yōu)解周邊無法跳出?；旌狭Ｗ尤核惴ㄞ饤壛藗鹘y(tǒng)粒子群算法中的通過跟蹤極值來更新粒子位置的方法,而是引入了遺傳算法中的交叉和變異操作,通過粒子同個(gè)體極值和群體極值的交叉以及粒子自身變異的方式來搜索最優(yōu)解。3.1粒子群算法概述粒子群優(yōu)化算法PSO是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。最初設(shè)想是模擬鳥群覓食的過程。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。是Eberhart博士和kennedy博士創(chuàng)造的一種新的全局優(yōu)化進(jìn)化算法。3.1.1粒子群優(yōu)化算法的根本原理PSO模擬鳥群的捕食行為。設(shè)想這樣一個(gè)場(chǎng)景:一群鳥在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中,每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子〞。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值fitnessvalue,每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機(jī)粒子隨機(jī)解。然后通過疊代找到最優(yōu)解。在每一次疊代中,粒子通過跟蹤兩個(gè)"極值"來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值,另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解,這個(gè)極值是全局極值。另外也可以不用整個(gè)種群而只是用其中一局部最為粒子的鄰居,那么在所有鄰居中的極值就是局部極值。在找到這兩個(gè)最優(yōu)值時(shí),粒子根據(jù)如下的公式來更新自己的速度和新的位置。(3-1)(3-2)從(3-1)式和(3-2)式可以看出,粒子的移動(dòng)方向由三局部決定,自己原有的速度、與自己最正確經(jīng)歷的距離和與群體最正確經(jīng)歷的距離,并分別由慣性權(quán)重w,c1、c2決定其相對(duì)重要性。PSO參數(shù)包括[16]:群體規(guī)模m,慣性權(quán)重w,加速常數(shù)c1和c2,最大V,最大代數(shù)G。w稱為慣性權(quán)重,使粒子保持運(yùn)動(dòng)的慣性,其大小決定了粒子對(duì)當(dāng)前速度繼承了多少,如果沒有第一局部,既w0,那么速度只取決于粒子當(dāng)前的位置和它們歷史最好位置,速度本身沒有記憶性。假設(shè)一個(gè)粒子位于全局最好位置,他將保持靜止。而其他粒子那么飛向它本身最好位置和全局最好位置的加權(quán)中心。在這種條件下,粒子群將統(tǒng)計(jì)的收縮到當(dāng)前的全局最好位置,更像一個(gè)局部算法。再加上第一局部后,粒子有擴(kuò)展搜索空間的趨勢(shì),既第一局部有全局搜索的能力。這也使得w的作用為針對(duì)不同的搜索問題,調(diào)整算法全局和局部搜索能力的平衡。c1,c2是學(xué)習(xí)因子,或稱加速系數(shù),代表將每個(gè)粒子推向個(gè)體最優(yōu)位置和群體最優(yōu)位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)重。低的值允許微粒在被拉回來之前可以在目標(biāo)區(qū)域外徘徊,而高的值導(dǎo)致粒子突然的沖向或者越過目標(biāo)區(qū)域。如果沒有后兩局部,既c1c20,粒子將一直以當(dāng)前的速度飛行,直到到達(dá)邊界。由于它只能搜索有限的區(qū)域,將很難找到好的解。如果沒有第二局部,既c10,那么粒子沒有認(rèn)知能力,也就是只有社會(huì)social-only〞的模型。在粒子的相互作用下,有能力到達(dá)新的搜索空間,它的收斂速度比標(biāo)準(zhǔn)版本更快,但是對(duì)復(fù)雜問題,比標(biāo)準(zhǔn)版本更容易陷入局部?jī)?yōu)值點(diǎn)。如果沒有第三局部,既c20,那么粒子之間沒有社會(huì)信息共享,也就是“只有認(rèn)知cognition-only〞的模型,因?yàn)閭€(gè)體間沒有交互,一個(gè)規(guī)模為m的群體等價(jià)于m個(gè)單個(gè)粒子的運(yùn)行。因而得到解得幾率非常小。適宜的c1和c2既可加快收斂又不易陷入局部最優(yōu),一般取[0,4]之間的數(shù),一般讓c1等于c2。r1和r2是介于[0,1]之間的隨機(jī)數(shù)。是粒子i在第t次迭代中第d維的速度。是粒子i在第t次迭代中第d維的當(dāng)前位置。在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度V,如果某一維更新后的速度超過用戶設(shè)定的V,那么這一維的速度就被限定為V。V決定在當(dāng)前位置與最好位置之間的分辨率。如果V太高,粒子可能會(huì)飛過好解,如果V太小,粒子不能進(jìn)行足夠的探索,導(dǎo)致陷入局部最優(yōu)。該限制有三個(gè)目的:防止計(jì)算溢出;實(shí)現(xiàn)人工學(xué)習(xí)和態(tài)度轉(zhuǎn)變;決定問題空間搜索的力度。粒子數(shù)一般取20?40.其實(shí)對(duì)于大局部的問題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果,不過對(duì)于比擬難的問題或者特定類別的問題,粒子數(shù)可以取到100或200。粒子的長(zhǎng)度是由優(yōu)化問題決定的,就是問題解的長(zhǎng)度。粒子的范圍由優(yōu)化問題決定,每一維可設(shè)定不同的范圍。3.1.2粒子群優(yōu)化算法描述和流程圖粒子群優(yōu)化算法流程描述如下:步驟1初始化粒子群,即隨機(jī)設(shè)定各粒子的的初始位置xi和初始速度vi;步驟2計(jì)算每個(gè)粒子的適應(yīng)度值;步驟3對(duì)每個(gè)粒子,比擬它們的適應(yīng)度值和它經(jīng)歷的最好位置pid的適應(yīng)度值,假設(shè)更好,更新pid;步驟4對(duì)每個(gè)粒子,比擬它們的適應(yīng)度值和群體經(jīng)歷的最好位置gid的適應(yīng)度值,假設(shè)更好更新gid;步驟5根據(jù)位置和速度的更新公式調(diào)整粒子的位置和速度;3.1.3粒子群優(yōu)化算法特點(diǎn)群體智能由大量簡(jiǎn)單個(gè)體相互交流和協(xié)作涌現(xiàn)出的智能行為。粒子群優(yōu)化PSO算法實(shí)現(xiàn)容易、精度高、收斂快,粒子還有一個(gè)重要的特點(diǎn),就是有記憶。PSO算法屬于進(jìn)化算法的一種,和遺傳算法相似,它也是從隨機(jī)解出發(fā),通過迭代尋找最優(yōu)解,它也是通過適應(yīng)度來評(píng)價(jià)解的品質(zhì)。但是它比遺傳算法規(guī)那么更為簡(jiǎn)單,它沒有遺傳算法的“交叉〞Crossover和“變異〞Mutation操作。它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。PSO的一個(gè)優(yōu)勢(shì)就是采用實(shí)數(shù)編碼,不需要像遺傳算法一樣是二進(jìn)制編碼或者采用針對(duì)實(shí)數(shù)的遺傳操作。例如對(duì)于問題fxx1^2x2^2x3^2求解,粒子可以直接編碼為x1,x2,x3,而適應(yīng)度函數(shù)就是fx。接著我們就可以利用前面的過程去尋優(yōu)。這個(gè)尋優(yōu)過程是一個(gè)疊代過程,中止條件一般為設(shè)置為到達(dá)最大循環(huán)數(shù)或者最小錯(cuò)誤。3.2遺傳算法概述對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同),遺傳算法(GeneticAlgorithm)是一類借鑒生物界的進(jìn)化規(guī)律(適者生存,優(yōu)勝劣汰遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。3.2.1遺傳算法的根本原理遺傳算法[10]是由美國(guó)的J.Holland教授1975年首先提出的,其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,不存在求異和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法,能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間,自適應(yīng)的調(diào)整搜索方向,不需要確定的規(guī)那么。遺傳算法的這些性質(zhì),已被人們廣泛的應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問題求函數(shù)最小值也類同,一般可以描述為以下數(shù)學(xué)規(guī)劃模型:(3-3)(3-4)(3-5)(3-3)式中為決策變量,為目標(biāo)函數(shù)式,式(3-4),(3-5)為約束條件,U是根本空間,R是U的子集,滿足約束條件的解X稱為可行解,集合R表示所有滿足約束條件的解所組成的集合,稱為可行解集合。遺傳算法[5]是從代表問題可能潛在的解集的一個(gè)種群(population)開始的,而一個(gè)種群那么由經(jīng)過基因(gene)編碼的一定數(shù)目的個(gè)體individual組成。每個(gè)個(gè)體實(shí)際上是染色體chromosome帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體,即多個(gè)基因的集合,其內(nèi)部表現(xiàn)(即基因型)是某種基因組合,它決定了個(gè)體的形狀的外部表現(xiàn),如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此,在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜,我們往往進(jìn)行簡(jiǎn)化,如二進(jìn)制編碼,初代種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代(generation)演化產(chǎn)生出越來越好的近似解,在每一代,根據(jù)問題域中個(gè)體的適應(yīng)度(fitness)大小選擇(selection)個(gè)體,并借助于自然遺傳學(xué)的遺傳算子(geneticoperators)進(jìn)行組合交叉(crossover)和變異(mutation),產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境,末代種群中的最優(yōu)個(gè)體經(jīng)過解碼(decoding),可以作為問題近似最優(yōu)解。3.2.2遺傳算法步驟遺傳算法的根本步驟如下:1初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器,t0,設(shè)置最大進(jìn)化代數(shù)T,隨機(jī)生成M個(gè)個(gè)體作為初始群體P0。2個(gè)體評(píng)價(jià):計(jì)算群體Pt中各個(gè)個(gè)體的適應(yīng)度。3選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過對(duì)交配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)價(jià)根底上的。4交叉運(yùn)算:將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的局部結(jié)構(gòu)加以替換重組生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。5變異運(yùn)算:將變異算子作用于群體。既是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體Pt經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體Pt.6終止條件判斷:假設(shè)tT,那么以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出,終止計(jì)算。3.3旅行商問題概述著名的旅行商問題,是一類NP完全的組合優(yōu)化問題,具有廣泛的實(shí)際應(yīng)用價(jià)值,例如:城市管道鋪設(shè)優(yōu)化、物流行業(yè)中的車輛調(diào)度優(yōu)化、制造業(yè)中的切割路徑優(yōu)化等現(xiàn)實(shí)生活中的很多優(yōu)化問題都可以歸結(jié)為TSP模型來求解。3.3.1旅行商問題概述旅行商問題TravelingSalesmanProblem,簡(jiǎn)記TSP[11]是組合數(shù)學(xué)中一個(gè)古老而又困難的問題,它易于描述但至今尚未徹底解決,現(xiàn)己歸入所謂的NP完全問題類,經(jīng)典提法為:有一貨物推銷員要去假設(shè)干個(gè)城市推銷貨物,從城市1出發(fā),經(jīng)其余各城市一次,然后回到城市1,問選擇怎樣的行走路線,才能使總行程最短(各城市間距離為己知)。該問題在圖論的意義下就是所謂