(完整)用遺傳算法求解TSP問題

用遺傳算法求解TSP問題遺傳算法（GeneticAlgorithmGA）,是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，它是由美國Michigan大學(xué)的J。Holland教授于1975年首先提出的。J.Holland教授和它的研究小組圍繞遺傳算法進(jìn)行研究的宗旨有兩個(gè)：抽取和解釋自然系統(tǒng)的自適應(yīng)過程以及設(shè)計(jì)具有自然系統(tǒng)機(jī)理的人工系統(tǒng)。遺傳算法的大致過程是這樣的:將每個(gè)可能的解看作是群體中的一個(gè)個(gè)體或染色體，并將每個(gè)個(gè)體編碼成字符串的形式，根據(jù)預(yù)定的目標(biāo)函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià),即給出一個(gè)適應(yīng)度值。開始時(shí),總是隨機(jī)的產(chǎn)生一些個(gè)體，根據(jù)這些個(gè)體的適應(yīng)度，利用遺傳算子選擇（Selection）、交叉（Crossover）、變異國口七2號(hào)。門）對(duì)它們重新組合，得到一群新的個(gè)體.這一群新的個(gè)體由于繼承了上一代的一些優(yōu)良特性，明顯優(yōu)于上一代，以逐步向著更優(yōu)解的方向進(jìn)化.遺傳算法主要的特點(diǎn)在于：簡(jiǎn)單、通用、魯棒性強(qiáng)。經(jīng)過二十多年的發(fā)展，遺傳算法已經(jīng)在旅行商問題、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)等領(lǐng)域得到成功的應(yīng)用。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比,主要有以下特點(diǎn)：遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象.傳統(tǒng)的優(yōu)化算法往往直接決策變量的實(shí)際植本身,而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概念，可以模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子.遺傳算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。遺傳算法使用多個(gè)點(diǎn)的搜索信息,具有隱含并行性。遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。遺傳算法是基于生物學(xué)的,理解或編程都不太難。下面是遺傳算法的一般算法步驟:1、創(chuàng)建一個(gè)隨機(jī)的初始狀態(tài)初始種群是從解中隨機(jī)選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號(hào)人工智能系統(tǒng)的情況不一樣;在那里,問題的初始狀態(tài)已經(jīng)給定了。2、評(píng)估適應(yīng)度對(duì)每一個(gè)解（染色體）指定一個(gè)適應(yīng)度的值，根據(jù)問題求解的實(shí)際接近程度來指定（以便逼近求解問題的答案）.不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案,系統(tǒng)可能需要利用的那些特性。3、繁殖（包括子代突變）帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代（后代產(chǎn)生后也將發(fā)生突變）。后代是父母的產(chǎn)物，他們由來自父母的基因結(jié)合而成,這個(gè)過程被稱為“雜交".4、下一代如果新的一代包含一個(gè)解，能產(chǎn)生一個(gè)充分接近或等于期望答案的輸出，那么問題就已經(jīng)解決了.如果情況并非如此，新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程,一代一代地演化下去，直到達(dá)到期望的解為止.5、并行計(jì)算非常容易將遺傳算法用到并行計(jì)算和群集環(huán)境中。一種方法是直接把每個(gè)節(jié)點(diǎn)當(dāng)成一個(gè)并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)。另一種方法是“農(nóng)場(chǎng)主/勞工”體系結(jié)構(gòu)，指定一個(gè)節(jié)點(diǎn)為“農(nóng)場(chǎng)主”節(jié)點(diǎn)，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評(píng)估.6、術(shù)語說明由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法,所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識(shí)，以下是我們將會(huì)涉及到的一些術(shù)語:①染色體（Chromosome）染色體又可以叫做基因型個(gè)體（individuals）,一定數(shù)量的個(gè)體組成了群體（population）,群體中個(gè)體的數(shù)量叫做群體大小.②基因（Gene）基因是串中的元素，基因用于表示個(gè)體的特征.例如有一個(gè)串S=01234，則其中的1，0，2,3這4個(gè)元素分別稱為基因。它們的值稱為等位基因（Alletes）。③基因地點(diǎn)（Locus）基因地點(diǎn)在算法中表示一個(gè)基因在串中的位置稱為基因位置（GenePosition），有時(shí)也簡(jiǎn)稱基因位?；蛭恢糜纱淖笙蛴矣?jì)算，例如在串S=12043中，0的基因位置是3。④基因特征值（GeneFeature）在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1,它的基因特征值為8.——不過本程序的基因無特征值；⑤適應(yīng)度（Fitness）各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度fitness）。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)(完整)用遺傳算法求解TSP問題問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù).這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。遺傳算法中，針對(duì)三種遺傳算子可進(jìn)行如下的遺傳操作。一、選擇算子從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫做選擇。選擇算子又叫再生算子(ReproductionOperator)。選擇的目的是把優(yōu)化的解直接遺傳到下一代或者通過配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的,目前常用的選擇算子有：.適應(yīng)度比例方法(Fitnessproportionalmodel)適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法.它也叫賭輪(roulettewheele)或蒙特卡羅(MonteCarlo)選擇。設(shè)群體大小為n，其中個(gè)體的適應(yīng)度值為了,則被i選擇的概率為P:isip=f/￡于siii可見p反映了個(gè)體i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。個(gè)體適應(yīng)度越大，被si選擇的概率就越高..最佳個(gè)體保存方法(Elitistmodel)此方法的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中。采用這種選擇方法的優(yōu)點(diǎn)是:進(jìn)化過程中某一代的最優(yōu)解可以不被交叉和變異操作所破壞。但是，這是這樣可能隱含了一種危機(jī)——導(dǎo)致早熟，即局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有可能限于局部解。也就是說,該方法的全局搜索能力不強(qiáng)，它更加適合于單峰性質(zhì)的搜索空間搜索。一般將這種方法與其它一些選擇操作配合起來使用，才能有良好的效果。另外，最佳個(gè)體保存方法還可加以推廣,即在每一代的進(jìn)化過程中保留多個(gè)最優(yōu)個(gè)體不參加交叉、變異等遺傳操作，而直接將它們復(fù)制到下一代群體中。這種選擇方法也稱為穩(wěn)態(tài)復(fù)制..排序選擇方法(Rank—based)排序選擇方法是指在計(jì)算每個(gè)個(gè)體的適應(yīng)度后,根據(jù)適應(yīng)度大小順序?qū)θ后w中個(gè)體排序，然后把事先設(shè)計(jì)好的概率表按順序分配給個(gè)體，作為各自的選擇概率。這種方法的不足之處在于選擇概率和序號(hào)的關(guān)系必須事先確定。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計(jì)誤差.此外還有一些比較常用的選擇方法如期望值方法(Expectedvaluemodel)、聯(lián)賽選擇方法(Tournamentselectionmodel)等。(完整)用遺傳算法求解(完整)用遺傳算法求解TSP問題二、交叉算子1．交叉算子的設(shè)計(jì)實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問題有關(guān)，一般包括以下一些要點(diǎn)：①任何交叉算子需要滿足交叉算子的評(píng)估準(zhǔn)則,就是說交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。②交叉設(shè)計(jì)和編碼設(shè)計(jì)是相互聯(lián)系的。也就是說，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作。這也就是所謂的編碼——交叉設(shè)計(jì)。2．基本的交叉算子①一點(diǎn)交叉(Onepointcrossover)一點(diǎn)交叉又叫做簡(jiǎn)單交叉.具體的操作是：在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉的時(shí)候，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新的個(gè)體。如下圖所示：ParentAParentBOffspring11001011+11011111=11001111圖2.1一點(diǎn)交叉二點(diǎn)交叉(Twopointcrossover)二點(diǎn)交叉與一點(diǎn)交叉類似，只是設(shè)值2個(gè)交叉點(diǎn)(隨機(jī)設(shè)定)，如下圖所示：圖2。2二點(diǎn)交叉一致交叉(Uniformcrossover)一致交叉是指通過設(shè)定屏蔽字(mask)來決定新個(gè)體的基因繼承兩個(gè)舊個(gè)體中哪個(gè)個(gè)體的對(duì)應(yīng)基因.如下圖所示：ParentAParentBOffspring11001011+11011101二11011111

圖2.3一致交叉算術(shù)交叉(ArithmeticCrossover)算術(shù)交叉是指由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。為了能夠進(jìn)行線性組合運(yùn)算，算術(shù)交叉的操作對(duì)象一般是由浮點(diǎn)數(shù)編碼所表示的個(gè)體。假設(shè)在兩個(gè)個(gè)體X，，X，之間進(jìn)行算術(shù)交叉，則交叉運(yùn)算后所產(chǎn)生出的兩個(gè)新個(gè)體是：ABXt+1=aXt+(1—a)Xt<ABAX，+1=aX，+(1—a)X，BAB其中，a是一參數(shù)，它可以是一個(gè)常數(shù)，此時(shí)所進(jìn)行的交叉運(yùn)算稱為均勻算術(shù)交叉；它可以是一個(gè)由進(jìn)化代數(shù)所決定的變量,此時(shí)所進(jìn)行的交叉運(yùn)算稱為非均勻算術(shù)交叉。3．交叉算子與遺傳算法的收斂型遺傳算法的收斂性不僅取決于編碼，初始化群體,適應(yīng)度函數(shù)，選擇算子的設(shè)計(jì)，而且還取決于交叉算子和下面要提到的變異算子.但是，遺傳算法的收斂性主要決定于作為其核心操作的交叉算子。交叉算子收斂性是遺傳算法研究中最重要的課題之一.需要指出的是，交叉算子并未提供收斂性保證.三、變異算子變異操作的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng).例如，基于字符集｛0，1｝的二值碼串,變異操作就是把1變成0或者把0變成1。變異操作的步驟為：在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)的確定基因座,然后以事先設(shè)定的變異概率對(duì)這些基因座的基因值進(jìn)行變異。如下圖所示：AftercrossoverAftermutation11001001=>10001001圖2。4簡(jiǎn)單位變異遺傳算法引入變異的目的有兩個(gè):一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解臨近值時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會(huì)因?yàn)樽儺惗獾狡茐摹６鞘惯z傳算法可以維持群體多樣性，以防止出現(xiàn)早熟現(xiàn)象。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。遺傳算法通過交叉和變異這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局1291761291763491212322261879827813216127975191122024417866160161235118629227755155275(完整)用遺傳算法求解TSP問題和局部的均衡搜索能力。遺傳算法在組合優(yōu)化中有著許多重要而且成功的應(yīng)用實(shí)例，這里只涉及到了最典型的旅行商問題(TSP問題)。旅行商問題，即TSP問題(TravelingSalesmanProblem)是數(shù)學(xué)領(lǐng)域中的著名問題之一.假設(shè)有一個(gè)旅行商人要拜訪門個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。。即尋找一條最短的遍歷門個(gè)城市的路徑，或者說搜索整數(shù)子集X二｛1,2,…，n｝的一個(gè)排列，使得T=Ed(v,v)+d(v,v)取最小值。其中d(v,v)表示城dii+1inii+1市i至|1v的距離。iTi+1TSP問題是一個(gè)組合優(yōu)化問題。該問題可以被證明具有NPC計(jì)算復(fù)雜性。因此，任何能使該問題的求解得以簡(jiǎn)化的方法,都將受到高度的評(píng)價(jià)和關(guān)注。遺傳算法求解可以得到問題的最優(yōu)解,且算法簡(jiǎn)單,對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題,用其它優(yōu)化方法較難求解,而遺傳算法可以方便的得到較好的結(jié)果。我將用遺傳算法來求解一個(gè)簡(jiǎn)單的TSP問題，其中基因是n個(gè)城市的排列順序，適應(yīng)度應(yīng)該是城市之間的距離總和,將距離作為權(quán)值.算法求解的問題就是對(duì)總距離最小的訪問城市的路徑排序。得到最短訪問路徑適應(yīng)函數(shù)的最優(yōu)排序。本例中,首先以十進(jìn)制方式對(duì)遍歷29個(gè)城市的次序排列進(jìn)行編碼,例如碼串12345678表示從城市1開始,依次經(jīng)過城市2,3,4,5,6,7,8,最后返回城市1的遍歷路徑,這是一種針對(duì)TSP問題的最自然的編碼方式.其邊權(quán)值如下所示：/*01072411901248031676152157283133113297228129348276188150653411846722116910845167TOC\o"1-5"\h\z1070148137881273361831349525418010123417517626519918267422782711462511051911397924114803741712595093172172324913122803914123494223563552041824354172924241163372737719013737402022342221922484211728779107381211528668701371512391351372421652282051248817120206139220246160319112163322240232314287238155653663001753075722012197801272592346103861417216735155157331272226362296232164853752491473011181886018531633650922239238602334382542024392352542101873132661542823212981682499543719031443576183317192202141233021318827219313130223398344289177216141346108571902454381243152134217248467243821302063658920936828627836033328420111141232122135372266132111157952324216016725418820601592205714980132193127100289519324113116920016118916328325449111731935120227236515904041761067916116514195187254103279215117359216308322133180312287112554391938922040402103843252794153492852171384283102003541692411122381131012807916315723513120957176210018611775231165818592230184741502081041582062972343911073223312543023681491063841860691915935125167255443092451693272463352882281754123824027221023328680793251176901221225656108175113240176125280177266243（完整）用遺傳算法求解TSP問題TOC\o"1-5"\h\z34826542215231436231334436019316541523159122244066178198286773622872283582993803192761993568628729626628933312714134916535561786601121322207929623218129223331425318818235568238232154177284100952858112556661781120128167169179120692831212132811506720470155164282216201281872178516710816019813212808821126915919717218918213565421821376585321141111952541389225517516128622016788029922910423611014997108341278435151366375298346412193103428230441132357779169211299035328921337129037933218427141723930024916810832124127931018430924011836229617926922935301211623458018934267146292135175147249572211312152007424517662287232120159104289121015422041932182212514241373073019519035316911735415016912592228181691972362131621540352147247350169105116242571184372457220035916920832728027735829228317211037134522035202651783910819133716522018819043266161216241104246177552992331211891492908041147265012426345139273228121603148113218930811215833526615538031421318297379189932471781240199167797720597185435243111163322238206288243275319253281135108332342218350392631990＊/對(duì)此29個(gè)城市的訪問，要求每個(gè)城市都只能訪問一次，并且最后要回到原來出發(fā)的城市。將以上29個(gè)城市之間的代號(hào)和距離權(quán)值用一個(gè)的數(shù)組matrix[maxstring][maxstring]進(jìn)行存儲(chǔ)和初始化。接著在此基礎(chǔ)上定義適應(yīng)度函數(shù)。適應(yīng)度函數(shù)通常取路徑長度T的倒數(shù)，即f=1/T.如果結(jié)dd合TSP的約束條件（比如每個(gè)城市經(jīng)過且只經(jīng)過一次）,則適應(yīng)度函數(shù)可表示成為f=1/（T+a?N）。其中N是對(duì)TSP路徑不合法的度量（比如取N為未遍歷的城市的個(gè)數(shù)），a為dttt懲罰系數(shù)，可以是距離的倍數(shù)。然后進(jìn)行遺傳算子的設(shè)計(jì)：以門個(gè)城市的遍歷次序作為遺傳算法的編碼，因?yàn)樵诟鞣N遺傳操作中都隱含了丁5「問題的合法性約束條件（例如，每個(gè)城市經(jīng)過且經(jīng)過一次），所以適應(yīng)度函數(shù)取哈密而頓長度的倒數(shù).采用賭輪選擇機(jī)制。一開始用隨機(jī)方法產(chǎn)生初始群體。隨著遺傳算法的執(zhí)行，則保留M個(gè)教優(yōu)的個(gè)體作為群體.在每一代運(yùn)算過程中，個(gè)體被選中的概率與其在群體中的相對(duì)適應(yīng)度成正比。交叉方法采用改進(jìn)的OX方法，這種方法的好處是，在兩個(gè)父代串相同的情況下仍能產(chǎn)生一定程度的變異效果，這對(duì)維持群體內(nèi)一定的多樣化特性有一定的作用.變異方法采用“逆轉(zhuǎn)"與下山方法相結(jié)合的操作，稱為“進(jìn)化逆轉(zhuǎn)"，主要目的是改善遺傳算法的局部搜索能力。在基本遺傳算法操作中,交叉操作在可行解空間中動(dòng)作范圍較寬，步伐較大，導(dǎo)致變異操作受“選擇”壓力的作用，難以發(fā)揮局部搜索的功效。因此，在遺傳算法框架中加入適當(dāng)?shù)?、基于鄰域的局部搜索機(jī)制，構(gòu)成一種全局搜索和局部搜索相結(jié)合的優(yōu)化搜索算法。下山方法就是一種很好的局部搜索方法。這里，定義一次“逆轉(zhuǎn)”為進(jìn)入一個(gè)解的鄰居，則進(jìn)化逆轉(zhuǎn)就是一個(gè)單方向的（朝著改進(jìn)方向的深度下山）和連續(xù)的“逆轉(zhuǎn)”操作。若“逆轉(zhuǎn)”使可行解的（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題適應(yīng)度提高，則繼續(xù)執(zhí)行逆轉(zhuǎn)，如此反復(fù)直到適應(yīng)度不再提高（這就是典型的下山過程）。這一操作可以得到較好的效果。將此算法編程實(shí)現(xiàn),可得到如下的算法描述和流程框圖：TSPSTART數(shù)據(jù)初始化與內(nèi)存空間分配;gen=0；初始化路徑群體；適應(yīng)度統(tǒng)計(jì)；顯示初始路徑；do{gen=gen+1；選擇操作；交叉操作;變異操作;適應(yīng)度統(tǒng)計(jì);顯示中間結(jié)果;}while（不滿足停止條件）將計(jì)算結(jié)果寫入文件；內(nèi)存空間釋放；END實(shí)驗(yàn)分析此問題即一個(gè)TSP問題，其中事件間相當(dāng)于一個(gè)偏序集，解方法可以用遞歸和回溯法，時(shí)間復(fù)雜度比較復(fù)雜.用遺傳算法求解時(shí)，問題是要得到基因的一個(gè)序列與前面的不同，所以要在基因進(jìn)行交叉和變異之后要進(jìn)行基因序列的休整，使得整個(gè)基因序列保持完整，休整方法就是對(duì)重復(fù)基因進(jìn)行更換.用遺傳算法求解問題時(shí)，很容易將問題限于局部憂化.本程序代碼在C—Free3.5下編譯通過，謝謝老師審閱！附錄：代碼/＊＊＊＊**＊*＊＊*＊＊＊******＊＊＊**＊＊*＊*＊＊*＊*＊＊*＊＊//＊*＊**＊＊＊＊TSPwritebyLJ***＊*＊**＊***＊＊＊*＊*//***＊****＊**＊*＊＊＊*＊**＊*****＊＊＊*＊＊＊＊＊*＊*＊*/#include<stdio。h〉#include<stdlib。h〉＃include〈math.h〉#include〈windows.h>＃include〈time.h>＃definemaxpop100＃definemaxstring29（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題297234297234391107322331254302368149106384186069191593512516725544309245169327246335288structindividual{unsignedintchrom[maxstring]；floatx,fitness；intparent[2];intxsite；}；/*當(dāng)前代種群＊//*新一代種群*//*當(dāng)前代種群＊//*新一代種群*/structindividual*newpop；structindividual＊temp，*p1；unsignedintco_min,jrand；unsignedintnmutation,ncross，jcross,maxpp,minpp,maxxy；floatsumfitness,avg，max,min，seed，maxold,oldrand[maxstring]；unsignedcharx[maxstring]，y[maxstring]；float*dd,ff,maxdd，refpd,fm[201]；//以下為29個(gè)城市的邊權(quán)值/＊01072411901248031676152157283133113297228129348276188150653411846722116910845167TOC\o"1-5"\h\z107014813788127336183134952541801012341751762651991826742278271146251105191139792411480374171259509317217232491312280391412349422356355204182435417292424116337273771901373740202234222192248421172877910738121152866870137151239135137242165228205124881712020613922024616031911216332224023231428723815565366300175307572201219780127259234610386141721673515515733127222636229623216485375249147301118188601853163365092223923860233438254202439235254210187313266154282321298168249954371903144357618331719220214123302131882721931313022339834428917721614134610857190245438124315213421724846724382130206365892093682862783603332842011114123212213537226613211115795232421601672541882060159220571498013219312710028951932411311692001611891632832544911173193512022723651590404176106791611651419518725410327921511735921630832213318031228711255439193892204040210384325279415349285217138428310200354169241112238113101280791631572351312095717621001861177523116581859223018474150208104158206voidinit()；voidinit()；（完整）用遺傳算法求解TSP問題TOC\o"1-5"\h\z2281754123824027221023328680793251176901221225656108175113240176125280177266243129176349121232226187982781321612797519112202441786616016123511862922775515527534826542215231436231334436019316541523159122244066178198286773622872283582993803192761993568628729626628933312714134916535561786601121322207929623218129223331425318818235568238232154177284100952858112556661781120128167169179120692831212132811506720470155164282216201281872178516710816019813212808821126915919717218918213565421821376585321141111952541389225517516128622016788029922910423611014997108341278435151366375298346412193103428230441132357779169211299035328921337129037933218427141723930024916810832124127931018430924011836229617926922935301211623458018934267146292135175147249572211312152007424517662287232120159104289121015422041932182212514241373073019519035316911735415016912592228181691972362131621540352147247350169105116242571184372457220035916920832728027735829228317211037134522035202651783910819133716522018819043266161216241104246177552992331211891492908041147265012426345139273228121603148113218930811215833526615538031421318297379189932471781240199167797720597185435243111163322238206288243275319253281135108332342218350392631990＊/staticintmatrix[maxstring][maxstring]={{0，107，241，190,124，80,316，76，152，157，283,133,113，297，228，129，348,276,188，150，65,341，184,67,221，169,108，45,167}，{107,0，148，137，88，127,336,183,134,95，254,180，101，234,175，176，265，199,182，67，42，278，271，146，251，105，191,139,79}，{241,148,0,374，171，259,509，317，217，232,491，312，280,391,412,349,422，356,355，204,182,435,417,292,424，116，337，273,77},{190,137,374,0,202,234,222,192,248,42,117,287,79,107,38,121,152,86,68,70,137,151,239,135,137,242,165,228,205},{124,88,171,202,0,61,392,202,46,160,319,112,163,322,240,232,314,287,238,155,65,366,300,175,307,57,220,121,97},{80,127,259,234,61,0,386,141,72,167,351,55,157,331,272,226,362,296,232,164,85,375,249,147,301,118,188,60,185},{316,336,509,222,392,386,0,233,438,254,202,439,235,254,210,187,313,266,154,282,321,298,168,249,95,437,190,314,435},{76,183,317,192,202,141,233,0,213,188,272,193,131,302,233,98,344,289,177,216,141,346,108,57,190,245,43,81,243},{152,134,217,248,46,72,438,213,0,206,365,89,209,368,286,278,360,333,284,201,111,412,321,221,353,72,266,132,111},{157,95,232,42,160,167,254,188,206,0,159,220,57,149,80,132,193,127,100,28,95,193,241,131,169,200,161,189,163},{283,254,491,117,319,351,202,272,365,159,0,404,176,106,79,161,165,141,95,187,254,103,279,215,117,359,216,308,322},{133,180,312,287,112,55,439,193,89,220,404,0,210,384,325,279,415,349,285,217,138,428,310,200,354,169,241,112,238},{113,101,280,79,163,157,235,131,209,57,176,210,0,186,117,75,231,165,81,85,92,230,184,74,150,208,104,158,206},{297,234,391,107,322,331,254,302,368,149,106,384,186,0,69,191,59,35,125,167,255,44,309,245,169,327,246,335,288},{228,175,412,38,240,272,210,233,286,80,79,325,117,69,0,122,122,56,56,108,175,113,240,176,125,280,177,266,243},{129,176,349,121,232,226,187,98,278,132,161,279,75,191,122,0,244,178,66,160,161,235,118,62,92,277,55,155,275}(完整)用遺傳算法求解TSP問題,{348,265,422,152,314,362,313,344,360,193,165,415,231,59,122,244,0,66,178,198,286,77,362,287,228,358,299,380,319}，{276，199，356，86,287,296,266,289,333，127，141，349,165,35,56,178,66,0,112，132,220,79，296，232,181,292，233，314，253},{188,182,355,68,238,232,154,177,284,100,95,285,81,125,56,66,178,112,0,128,167,169,179,120,69,283,121,213,281},{150,67,204,70,155,164,282,216,201,28,187,217,85,167,108,160,198,132,128,0,88,211,269,159,197,172,189,182,135},{65,42,182,137,65,85,321,141,111,95,254,138,92,255,175,161,286,220,167,88,0,299,229,104,236,110,149,97,108},{341,278,435,151,366,375,298,346,412,193,103,428,230,44,113,235,77,79,169,211,299,0,353,289,213,371,290,379,332},{184,271,417,239,300,249,168,108,321,241,279,310,184,309,240,118,362,296,179,269,229,353,0,121,162,345,80,189,342},{67,146,292,135,175,147,249,57,221,131,215,200,74,245,176,62,287,232,120,159,104,289,121,0,154,220,41,93,218},{221,251,424,137,307,301,95,190,353,169,117,354,150,169,125,92,228,181,69,197,236,213,162,154,0,352,147,247,350},{169,105,116,242,57,118,437,245,72,200,359,169,208,327,280,277,358,292,283,172,110,371,345,220,352,0,265,178,39},{108,191,337,165,220,188,190,43,266,161,216,241,104,246,177,55,299,233,121,189,149,290,80,41,147,265,0,124,263},{45,139,273,228,121,60,314,81,132,189,308,112,158,335,266,155,380,314,213,182,97,379,189,93,247,178,124,0,199},{167,79,77,205,97,185,435,243,111,163,322,238,206,288,243,275,319,253,281,135,108,332,342,218,350,39,263,199,0}};floatpcross；/＊交叉概率*/floatpmutation；/＊變異概率＊/intpopsize;/*種群大?。?intlchrom;/*染色體長度＊/intgen;/*當(dāng)前世代數(shù)*/intmaxgen;/*最大世代數(shù)＊/intvar_num;/＊變量數(shù)目＊/intfunc_num;/*函數(shù)數(shù)目＊/structindividual＊spop;intcompare_count;FILE*outfp,＊outfp1,*outfp2；{{(完整)用遺傳算法求解TSP問題voidinitmalloc();voidinitpop();voidinitparameters();voidinversion(unsignedint,unsignedint,unsignedint*)；floatdecode(unsignedint＊)；floatobjfunc(float);voidgeneration();intselect()；voidstatistics(structindividual*);intcrossover(unsignedint[],unsignedint[],unsignedint[],unsignedint[])；voidmutation(unsignedint[],float)；voidreport(int,structindividual*)；voidmain(){doublestart=clock()，end,time；init()；statistics(oldpop)；gen=1；outfp=fopen(”output.txt","a");outfp1=fopen("evaluate.txt”,"a”);outfp2=fopen("compare_count°txt","a")；for(gen=1；gen<=maxgen；gen++)（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題{{printf("gen=%dcompare_count=%d\n",gen,compare_count);generation()；statistics(oldpop)；report(gen，oldpop)；}fprintf(outfp2，"———-——-—--—-———————--—---———-———-\n");end=clock()；time=(end—start)/CLOCKS_PER_SEC；fprintf(outfp1，”%f\n”,time);}voidclimb(unsignedinta[]){inti1,i2，j,k，j2；j2=rand()％(2＊lchrom/3)；floatx,y;for(j=j2；j〈j2+lchrom/3-1;j++)for(k=0；k〈lchrom；k++){if(k==j)continue；if(k〉j){i2=k；i1=j；}else{i1=k；i2=j；}x=decode(a);inversion(i1，i2,a)；//i1,i2inversion(i1，i2,a)；//i1,i2為前后的兩個(gè)逆轉(zhuǎn)點(diǎn)y=decode(a)；if(y〉x)inversion(i1,i2，a)；//如果逆轉(zhuǎn)后路經(jīng)長度增長，則再次逆轉(zhuǎn)//一次恢復(fù)到以前的狀態(tài)。}}voidinit(){initparameters()；initmalloc()；initpop();}voidinitparameters(){maxgen=200;popsize=100；lchrom=maxstring；pcross=0.9;pmutation=1.0/(lchrom);nmutation=0；ncross=0;}voidinitmalloc()（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題oldpop=newindividual[popsize]；newpop=newindividual[popsize]；temp=newindividual[popsize]；}voidinitpop（）{srand（（unsigned）time（NULL））;//初始化隨機(jī)數(shù)unsignedinttemp;unsignedintj，i,k，j2，j3，j4；unsignedintp5[maxstring]；//臨時(shí)待排列數(shù)組floatf1，f2；j=0；for（k=0；k<lchrom；k++）oldpop[j].chrom[k]=k;for（k=0;k〈lchrom;k++）p5[k]=oldpop[j]。chrom[k]；for（；j<popsize；j++）{j2=rand（）%lchrom;〃重新排列p5口for（k=0;k〈j2+20;k++）j3=rand（）%lchrom；j4=rand()％lchrom;temp=p5[j3]；p5[j3]=p5[j4];p5[j4]=temp；}for(k=0;k<lchrom;k++)oldpop[j].chrom[k]=p5[k];}for(j=0；j<popsize；j++){oldpop[j]ox=decode(oldpop[j].chrom);oldpop[j]。fitness=objfunc(oldpop[j].x);oldpop[j]oparent[0]=0;oldpop[j]oparent[1]=0;oldpop[j].xsite=0;}printf(”\n")；}voidinversion(unsignedintk,unsignedintj，unsignedint*ss){unsignedinti,l1;unsignedinttt;l1=(j-k)/2;for(i=0；i〈=l1；i++)tt=ss[k+i]；ss[k+i]=ss[j—i]；ss[j-i]=tt；}}//函數(shù)decode計(jì)算一個(gè)城市排列的路徑長度floatdecode(unsignedint*pp){intj；floattt；tt=matrix[pp[0]][pp[lchrom—1]];for(j=0;j<lchrom—1；j++)tt=tt+matrix[pp[j]][pp[j+1]]；returntt；}voidgeneration(){intsite；unsignedintk,mate1,mate2;for(inti=0;i〈popsize-1;i=i+2)mate1=select()；do{mate2=select()；}while(mate1二二mate2)；site=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[i]。chrom,newpop[i+1].chrom)；mutation(newpop[i].chrom,pmutation)；//局部爬山到最優(yōu)點(diǎn)climb(newpop[i].chrom)；newpop[i].x=decode(newpop[i]。chrom)；newpop[i]。fitness=objfunc(newpop[i]。x);newpop[i].parent[0]=mate1；newpop[i].parent[1]=mate2；newpop[i]。xsite=site;mutation(newpop[i+1].chrom，pmutation)；climb(newpop[i+1]。chrom);//局部爬山到最優(yōu)點(diǎn)newpop[i+1].x=decode(newpop[i+1].chrom)；newpop[i+1].fitness=objfunc(newpop[i+1]。x);newpop[i+1]。parent[0]=mate1;newpop[i+l]。parent[1]=mate2；newpop[i+1].xsite=site;//群體更新方式采用最佳個(gè)體保留方式，每次以一個(gè)最佳個(gè)體替代一個(gè)最差個(gè)體if(newpop[i].fitness〉max)（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題{{for（k=0；k〈lchrom；k++）oldpop[minpp].chrom[k]=newpop[i]。chrom[k];oldpop[minpp].x=newpop[i].x;oldpop[minpp].fitness=newpop[i].fitness;return；}if（newpop[i+1].fitness〉max）{for（k=0;k<lchrom；k++）oldpop[minpp]。chrom[k]=newpop[i+1].chrom[k];oldpop[minpp].x=newpop[i+1]。x;oldpop[minpp].fitness=newpop[i+1].fitness；return;}}}floatobjfunc（floatx1）{return1/x1;}intselect（）//輪盤賭選擇函數(shù)（完整）用遺傳算法求解（完整）用遺傳算法求解TSP問題doublesum，pick;unsignedinti,random;random=rand()%10000；pick=(double)random/10000.0；sum=0；if(sumfitness！=0){for(i=0；(sum〈pick)&&(i<popsize);i++)sum+=oldpop[i]。fitness/sumfitness；}elsei=(rand()%popsize)+1；〃即i=rnd(1,popsize