遺傳,模擬退火,蟻群三個(gè)算法求解tsp的對(duì)比

1、-. z.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院智能計(jì)算及應(yīng)用課程設(shè)計(jì)設(shè)計(jì)題目：智能計(jì)算解決旅行商問題摘要本文以遺傳算法、模擬退火、蟻群算法三個(gè)算法解決旅行商問題，將三個(gè)算法進(jìn)展比擬分析。目前這三個(gè)算法廣泛應(yīng)用于各個(gè)領(lǐng)域中，本文以31個(gè)城市為例，運(yùn)用遺傳算法、模擬退火、蟻群算法分別進(jìn)展了計(jì)算，將他們的計(jì)算結(jié)果進(jìn)展了比擬分析。關(guān)鍵詞: 遺傳算法 模擬退火 蟻群算法旅行商問題背景：遺傳算法：20世紀(jì)60年代初，美國Michigan大學(xué)的John Holland教授開場(chǎng)研究自然和人工系統(tǒng)的自適應(yīng)行為，在從事如何建立能學(xué)習(xí)的機(jī)器的研究過程中，受達(dá)爾文進(jìn)化論的啟發(fā)，逐漸意識(shí)到為獲得一個(gè)好的算法僅靠單個(gè)策略建立和改良是不夠的，還

2、要依賴于一個(gè)包含許多候選策略的群體的繁殖，從而提出了遺傳算法的根本思想。 20世紀(jì)60年代中期，基于語言智能和邏輯數(shù)學(xué)智能的傳統(tǒng)人工智能十分興盛，而基于自然進(jìn)化思想的模擬進(jìn)化算法則遭到疑心與反對(duì)，但Holland及其指導(dǎo)的博士仍堅(jiān)持這一領(lǐng)域的研究。Bagley發(fā)表了第一篇有關(guān)遺傳算法應(yīng)用的論文，并首先提出“遺傳算法這一術(shù)語，在其博士論文中采用雙倍體編碼，開展了復(fù)制、穿插、變異、顯性、倒位等基因操作算子，并敏銳地發(fā)覺到防止早熟的機(jī)理，開展了自組織遺傳算法的概念。與此同時(shí)，Rosenberg在其博士論文中進(jìn)展了單細(xì)胞生物群體的計(jì)算機(jī)仿真研究，對(duì)以后函數(shù)優(yōu)化頗有啟發(fā)，并開展了自適應(yīng)交換策略，在遺傳操

3、作方面提出了許多獨(dú)特的設(shè)想。Hollistien在其1971年發(fā)表的計(jì)算機(jī)控制系統(tǒng)的人工遺傳自適應(yīng)方法論文中首次將遺傳算法應(yīng)用于函數(shù)優(yōu)化，并對(duì)優(yōu)勢(shì)基因控制、穿插、變異以及編碼技術(shù)進(jìn)展了深入的研究。人們經(jīng)過長(zhǎng)期的研究，在20世紀(jì)o年代初形成了遺傳算法的根本框架。1975年Holland出版了經(jīng)典著作“Adaptation in Nature and Artificial System,該書詳細(xì)闡述了遺傳算法的根本理論和方法，提出了著名的模式理論，為遺傳算法奠定了數(shù)學(xué)根底。同年，DeJong發(fā)表了重要論文“An Analysis of the Behav-nor of a Class of Gen

4、etie Adaptive System，在論文中，他將Holland的模式理論與計(jì)算實(shí)驗(yàn)結(jié)合起來，并通過函數(shù)優(yōu)化的應(yīng)用深人研究，將選擇、穿插、變異操作進(jìn)一步完善和系統(tǒng)化，并提出了代溝等新的操作技術(shù)，所得出的許多結(jié)論至今仍具有普遍的指導(dǎo)意義。進(jìn)入20世紀(jì)80年代末期，隨著計(jì)算機(jī)技術(shù)的開展，遺傳算法的研究再次興起。遺傳算法以其較強(qiáng)的解決問題的能力和廣泛的適應(yīng)性，深受眾多領(lǐng)域研究人員的重視，遺傳算法的理論研究和應(yīng)用研究已成為十分熱門的課題。自1985年起，遺傳算法及其應(yīng)用的國際會(huì)議每?jī)赡暾匍_一次，并且在相關(guān)的人工智能會(huì)議和刊物上大多設(shè)有遺傳算法的專題。模擬退火：模擬退火算法來源于固體退火原理，是一

5、種基于概率的算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)平衡態(tài)，最后在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小。模擬退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis1等人于1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從*一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在

6、解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性，從而可有效防止陷入局部極小并最終趨于全局最優(yōu)的串行構(gòu)造的優(yōu)化算法。蟻群算法：蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在

7、尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究說明該算法具有許多優(yōu)良的性質(zhì)。針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)展了比擬，數(shù)值仿真結(jié)果說明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。算法原理：遺傳算法：遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對(duì)群體的個(gè)體按照它們對(duì)環(huán)境適應(yīng)度(適應(yīng)度評(píng)估)施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題遺傳過程的解，一代又一代地優(yōu)化，并逼近最優(yōu)解。遺傳操作包括以下三個(gè)根本遺傳算子(genetic oper

8、ator):選擇(selection)；穿插(crossover)；變異(mutation)。這三個(gè)遺傳算子有如下特點(diǎn)：個(gè)體遺傳算子的操作都是在隨機(jī)擾動(dòng)情況下進(jìn)展的。因此，群體中個(gè)體向最優(yōu)解遷移的規(guī)則是隨機(jī)的。需要強(qiáng)調(diào)的是，這種隨機(jī)化操作和傳統(tǒng)的隨機(jī)搜索方法是有區(qū)別的。遺傳操作進(jìn)展的高效有向的搜索而不是如一般隨機(jī)搜索方法所進(jìn)展的無向搜索。遺傳操作的效果和上述三個(gè)遺傳算子所取的操作概率，編碼方法，群體大小，初始群體以及適應(yīng)度函數(shù)的設(shè)定密切相關(guān)。從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫選擇。選擇算子有時(shí)又稱為再生算子(reproduction operator)。選擇的目的是把優(yōu)化的個(gè)體(或解

9、)直接遺傳到下一代或通過配對(duì)穿插產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估根底上的，目前常用的選擇算子有以下幾種：適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。其中輪盤賭選擇法 roulette wheel selection是最簡(jiǎn)單也是最常用的選擇方法。在該方法中，各個(gè)個(gè)體的選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為n，其中個(gè)體i的適應(yīng)度為，則i 被選擇的概率，為遺傳算法顯然，概率反映了個(gè)體i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。個(gè)體適應(yīng)度越大。其被選擇的概率就越高、反之亦然。計(jì)算出群體中各個(gè)個(gè)體的選擇概率后，為了選擇交配個(gè)體，需要進(jìn)展多輪選擇。每一輪產(chǎn)生一個(gè)0

10、，1之間均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來確定被選個(gè)體。個(gè)體被選后，可隨機(jī)地組成交配對(duì)，以供后面的穿插操作。在自然界生物進(jìn)化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的穿插算子。所謂穿插是指把兩個(gè)父代個(gè)體的局部構(gòu)造加以替換重組而生成新個(gè)體的操作。通過穿插，遺傳算法的搜索能力得以飛躍提高。穿插算子根據(jù)穿插率將種群中的兩個(gè)個(gè)體隨機(jī)地交換*些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法：實(shí)值重組離散重組,中間重組,線性重組,擴(kuò)展線性重組。二進(jìn)制穿插單點(diǎn)穿插,多點(diǎn)穿插,均勻穿插,洗牌穿插,縮小代理穿插。

11、最常用的穿插算子為單點(diǎn)穿插。具體操作是:在個(gè)體串中隨機(jī)設(shè)定一個(gè)穿插點(diǎn)，實(shí)行穿插時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的局部構(gòu)造進(jìn)展互換，并生成兩個(gè)新個(gè)體。下面給出了單點(diǎn)穿插的一個(gè)例子：個(gè)體A：1 0 0 1 1 1 1 1 0 0 1 0 0 0 新個(gè)體個(gè)體B：0 0 1 1 0 0 0 0 0 1 1 1 1 1 新個(gè)體變異算子的根本內(nèi)容是對(duì)群體中的個(gè)體串的*些基因座上的基因值作變動(dòng)。依據(jù)個(gè)體編碼表示方法的不同，可以有以下的算法：a)實(shí)值變異b)二進(jìn)制變異。一般來說，變異算子操作的根本步驟如下：a)對(duì)群中所有個(gè)體以事先設(shè)定的變異概率判斷是否進(jìn)展變異b)對(duì)進(jìn)展變異的個(gè)體隨機(jī)選擇變異位進(jìn)展變異。遺傳算法引入變

12、異的目的有兩個(gè):一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過穿插算子已接近最優(yōu)解鄰域時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應(yīng)取較小值，否則接近最優(yōu)解的積木塊會(huì)因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時(shí)收斂概率應(yīng)取較大值。遺傳算法中，穿插算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過穿插和變異這對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當(dāng)群體在進(jìn)化中陷于搜索空間中*個(gè)超平面而僅靠穿插不能擺脫時(shí)，通過變異操作可有助于這種擺

13、脫。所謂相互競(jìng)爭(zhēng)，是指當(dāng)通過穿插已形成所期望的積木塊時(shí)，變異操作有可能破壞這些積木塊。如何有效地配合使用穿插和變異操作，是目前遺傳算法的一個(gè)重要研究?jī)?nèi)容。模擬退火：模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)平衡態(tài)，最后在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e(-E/(kT)，其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解

14、組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開場(chǎng)，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差承受或舍棄的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子t、每個(gè)t值時(shí)的迭代次數(shù)L和停頓條件S。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三局部。模擬退火的根本思想:(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L(2) 對(duì)k=1，L做第(3)至第6步：(3) 產(chǎn)生新解S(4) 計(jì)算增量t=C

15、(S)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)，(5) 假設(shè)t0，然后轉(zhuǎn)第2步。模擬退火算法新解的產(chǎn)生和承受可分為如下四個(gè)步驟：第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和承受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或局部元素進(jìn)展置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域構(gòu)造，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換局部產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)說明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被承受,判斷的依

16、據(jù)是一個(gè)承受準(zhǔn)則，最常用的承受準(zhǔn)則是Metropolis準(zhǔn)則: 假設(shè)t0則承受S作為新的當(dāng)前解S，否則以概率e*p(-t/T)承受S作為新的當(dāng)前解S。第四步是當(dāng)新解被確定承受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換局部予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代。可在此根底上開場(chǎng)下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的根底上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。蟻群算法：蟻群優(yōu)化

17、算法是模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法。螞蟻在覓食過程中能夠在其經(jīng)過的路徑上留下一種稱之為信息素的物質(zhì)，并在覓食過程中能夠感知這種物質(zhì)的強(qiáng)度，并指導(dǎo)自己行動(dòng)方向，它們總是朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對(duì)信息素的正反應(yīng)現(xiàn)象。*一條路徑越短，路徑上經(jīng)過的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構(gòu)成的正反應(yīng)過程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。螞蟻在覓食過程時(shí)，是以信息素作為媒介而間接進(jìn)展信息交流，當(dāng)螞蟻從食物源走到蟻穴，或者從蟻穴走到食物源時(shí)，都會(huì)在經(jīng)過的路徑上釋放信息素，從而形成了一條含有信

18、息素的路徑，螞蟻可以感覺出路徑上信息素濃度的大小，并且以較高的概率選擇信息素濃度較高的路徑蟻群系統(tǒng)ACS12是由Dorigo等人提出來的改良的蟻群算法，它與AS的不同之處主要表達(dá)在三個(gè)方面：1采用不同的路徑選擇規(guī)則，能更好地利用螞蟻所積累的搜索經(jīng)歷。2信息素?fù)]發(fā)和信息素釋放動(dòng)作只在至今最優(yōu)路徑的邊上執(zhí)行，即每次迭代之后只有至今最優(yōu)螞蟻被允許釋放信息素；3除了全局信息素更新規(guī)則外，還采用了局部信息素更新規(guī)則。在ACS中，位于城市i的螞蟻k，根據(jù)偽隨機(jī)比例規(guī)則選擇城市j作為下一個(gè)訪問的城市。設(shè)C=c1, c2, , 是n個(gè)城市的集合，L=lij|ci, cj C是集合C中的元素城市兩兩連接的集合，

19、dij(i, j=1,1,n)是lij的Euclidean距離，即G=(C, L)是一個(gè)有向圖，TSP的目的是從有向圖G中尋出長(zhǎng)度最短的Hamilton圈，即一條對(duì)C=c1, c2, ,中n個(gè)元素城市訪問且只訪問一次的最短封閉曲線n城市規(guī)模的TSP，存在(n-1)!/2條不同閉合路徑設(shè)bi(t)表示t時(shí)刻位于元素i的螞蟻數(shù)目，ij (t)為t時(shí)刻路徑(i, j)上的信息量，n表示TSP規(guī)模，m為蟻群中螞蟻總數(shù)，則是t時(shí)刻集合C中元素城市兩兩連接lij上殘留信息量的集合，在初始時(shí)刻各條路徑上的信息量相等，并設(shè)ij(0)=const, 根本蟻群算法的尋優(yōu)是通過有向圖g=(C, L, )實(shí)現(xiàn)的。螞蟻

20、k(k=1,2,m)在運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。這里用禁忌表tabuk來記錄螞蟻k當(dāng)前所走過的城市，集合隨著tabuk進(jìn)化過程做動(dòng)態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。在t時(shí)刻螞蟻k由元素城市i轉(zhuǎn)移到元素城市j的狀態(tài)轉(zhuǎn)移概率：其中allowedk=C-tabuk表示螞蟻k下一步允許選擇的城市；為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)；為期望啟發(fā)式因子，表示能見度的相對(duì)重要性，反映螞蟻在運(yùn)動(dòng)過程中啟發(fā)信

21、息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；ij(t)為啟發(fā)函數(shù)，ij(t) =1/dij式中dij表示相鄰兩個(gè)城市之間的距離。對(duì)螞蟻k而言，dij越小，則ij(t)越大，pijk也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從元素城市i轉(zhuǎn)移到元素城市j的期望程度。為了防止殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷(也即一個(gè)循環(huán)完畢)后，要對(duì)殘留信息進(jìn)展更新處理。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時(shí)，存儲(chǔ)在大腦中的舊信息隨著時(shí)間的推移逐漸淡化，甚至忘記。由此，t+n時(shí)刻在路徑(i, j)上的信息量可

22、按如下規(guī)則進(jìn)展調(diào)整式中，表示信息素?fù)]發(fā)系數(shù)，則1-表示信息素殘留因子，為了防止信息的無限積累，的取值*圍為0，1), ij(t)表示本次循環(huán)中路徑(i, j)上的信息素增量，初始時(shí)刻ij(t) =0, ijk(t)表示第k只螞蟻在本次循環(huán)中留在路徑(i, j)上的信息量。根據(jù)信息素更新策略的不同，Dorigo M提出了三種不同的根本蟻群算法模型，分別稱之為Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差異在于ijk(t)求法的不同。程序遺傳算法：clearclcclose all% 加載數(shù)據(jù)%load data*=1304 2312;3639 1315;4

23、177 2244;3721 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;D=Distanse(*);

24、 %生成距離矩陣N=size(D,1); %城市個(gè)數(shù)% 遺傳參數(shù)NIND=100; %種群大小MA*GEN=200; %最大遺傳代數(shù)Pc=0.9; %穿插概率Pm=0.05; %變異概率GGAP=0.9; %代溝% 初始化種群Chrom=InitPop(NIND,N);% 畫出隨機(jī)解的路徑圖DrawPath(Chrom(1,:),*)pause(0.0001)% 輸出隨機(jī)解的路徑和總距離disp(初始種群中的一個(gè)隨機(jī)值:)OutputPath(Chrom(1,:);Rlength=PathLength(D,Chrom(1,:);disp(總距離：,num2str(Rlength);disp()

25、% 優(yōu)化gen=0;figure;hold on;bo* on*lim(0,MA*GEN)title(優(yōu)化過程)*label(代數(shù))ylabel(最優(yōu)值)ObjV=PathLength(D,Chrom); %計(jì)算路徑長(zhǎng)度preObjV=min(ObjV);while gen=rand R=randperm(L); SelCh(i,R(1:2)=SelCh(i,R(2:-1:1); endend OutputPat.m% 輸出路徑函數(shù)%輸入：R 路徑function p=OutputPath(R)R=R,R(1);N=length(R);p=num2str(R(1);for i=2:N p=p,

26、num2str(R(i);enddisp(p)PathLength.m% 計(jì)算各個(gè)體的路徑長(zhǎng)度% 輸入：% D 兩兩城市之間的距離% Chrom 個(gè)體的軌跡function len=PathLength(D,Chrom)row,col=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NIND p=Chrom(i,:) Chrom(i,1); i1=p(1:end-1); i2=p(2:end); len(i,1)=sum(D(i1-1)*col+i2);endRebin.m% 穿插操作% 輸入%SelCh 被選擇的個(gè)體%Pc 穿插概率%

27、輸出：% SelCh 穿插后的個(gè)體function SelCh=Rebin(SelCh,Pc)NSel=size(SelCh,1);for i=1:2:NSel-mod(NSel,2) if Pc=rand %穿插概率Pc SelCh(i,:),SelCh(i+1,:)=intercross(SelCh(i,:),SelCh(i+1,:); endend%輸入：%a和b為兩個(gè)待穿插的個(gè)體%輸出：%a和b為穿插后得到的兩個(gè)個(gè)體function a,b=intercross(a,b)L=length(a);r1=randsrc(1,1,1:L);r2=randsrc(1,1,1:L);if r1=

28、r2 a0=a;b0=b; s=min(r1,r2); e=ma*(r1,r2); for i=s:e a1=a;b1=b; a(i)=b0(i); b(i)=a0(i); *=find(a=a(i); y=find(b=b(i); i1=*(*=i); i2=y(y=i); if isempty(i1) a(i1)=a1(i); end if isempty(i2) b(i2)=b1(i); end endendReins.m% 重插入子代的新種群 %Chrom 父代的種群 %SelCh 子代種群 %ObjV 父代適應(yīng)度 % Chrom 組合父代與子代后得到的新種群function Chro

29、m=Reins(Chrom,SelCh,ObjV)NIND=size(Chrom,1);NSel=size(SelCh,1);TobjV,inde*=sort(ObjV);Chrom=Chrom(inde*(1:NIND-NSel),:);SelCh;Reverse.m% 進(jìn)化逆轉(zhuǎn)函數(shù)%SelCh 被選擇的個(gè)體%D 城市的距離矩陣%輸出%SelCh 進(jìn)化逆轉(zhuǎn)后的個(gè)體function SelCh=Reverse(SelCh,D)row,col=size(SelCh);ObjV=PathLength(D,SelCh); %計(jì)算路徑長(zhǎng)度SelCh1=SelCh;for i=1:row r1=rand

30、src(1,1,1:col); r2=randsrc(1,1,1:col); mininverse=min(r1 r2); ma*inverse=ma*(r1 r2); SelCh1(i,mininverse:ma*inverse)=SelCh1(i,ma*inverse:-1:mininverse);endObjV1=PathLength(D,SelCh1); %計(jì)算路徑長(zhǎng)度inde*=ObjV1ObjV;SelCh(inde*,:)=SelCh1(inde*,:);Select.mfunction SelCh=Select(Chrom,FitnV,GGAP) % 選擇操作NIND=size

31、(Chrom,1); % Chrom 種群NSel=ma*(floor(NIND*GGAP+.5),2); % %GGAP：代溝ChrI*=Sus(FitnV,NSel); %FitnV 適應(yīng)度值SelCh=Chrom(ChrI*,:); %SelCh 被選擇的個(gè)體Sus.m%Nsel 被選擇個(gè)體的數(shù)目%NewChrI* 被選擇個(gè)體的索引號(hào)function NewChrI* = Sus(FitnV,Nsel) %FitnV 個(gè)體的適應(yīng)度值Nind,ans = size(FitnV);cumfit = cumsum(FitnV);trials = cumfit(Nind) / Nsel * (r

32、and + (0:Nsel-1);Mf = cumfit(:, ones(1, Nsel);Mt = trials(:, ones(1, Nind);NewChrI*, ans = find(Mt Mf & zeros(1, Nsel); Mf(1:Nind-1, :) =tffor r=1:Markov_length% Markov鏈長(zhǎng)度% 產(chǎn)生隨機(jī)擾動(dòng)if (rand 0.5)% 隨機(jī)決定是進(jìn)展兩交換還是三交換% 兩交換ind1 = 0; ind2 = 0;while (ind1 = ind2)ind1 = ceil(rand.*amount);ind2 = ceil(rand.*amou

33、nt);endtmp1 = sol_new(ind1);sol_new(ind1) = sol_new(ind2);sol_new(ind2) = tmp1;else% 三交換ind1 = 0; ind2 = 0; ind3 = 0;while (ind1 = ind2) | (ind1 = ind3) .| (ind2 = ind3) | (abs(ind1-ind2) = 1)ind1 = ceil(rand.*amount);ind2 = ceil(rand.*amount);ind3 = ceil(rand.*amount);endtmp1 = ind1;tmp2 = ind2;tmp

34、3 = ind3;% 確保ind1 ind2 ind3if (ind1 ind2) & (ind2 ind3);elseif (ind1 ind3) & (ind3 ind2)ind2 = tmp3;ind3 = tmp2;elseif (ind2 ind1) & (ind1 ind3)ind1 = tmp2;ind2 = tmp1;elseif (ind2 ind3) & (ind3 ind1)ind1 = tmp2;ind2 = tmp3; ind3 = tmp1;elseif (ind3 ind1) & (ind1 ind2)ind1 = tmp3;ind2 = tmp1; ind3 =

35、 tmp2;elseif (ind3 ind2) & (ind2 ind1)ind1 = tmp3;ind2 = tmp2; ind3 = tmp1;endtmplist1 = sol_new(ind1+1):(ind2-1);sol_new(ind1+1):(ind1+ind3-ind2+1) = .sol_new(ind2):(ind3);sol_new(ind1+ind3-ind2+2):ind3) = .tmplist1;end%檢查是否滿足約束% 計(jì)算目標(biāo)函數(shù)值即內(nèi)能E_new = 0;for i = 1 : (amount-1)E_new = E_new + .dist_matri

36、*(sol_new(i),sol_new(i+1);end% 再算上從最后一個(gè)城市到第一個(gè)城市的距離E_new = E_new + .dist_matri*(sol_new(amount),sol_new(1);if E_new E_currentE_current = E_new;sol_current = sol_new;if E_new E_best% 把冷卻過程中最好的解保存下來E_best = E_new;sol_best = sol_new;endelse% 假設(shè)新解的目標(biāo)函數(shù)值小于當(dāng)前解的，% 則僅以一定概率承受新解if rand e*p(-(E_new-E_current)./

37、t)E_current = E_new;sol_current = sol_new;elsesol_new = sol_current;endendendt=t.*a;% 控制參數(shù)t溫度減少為原來的a倍enddisp(最優(yōu)解為：)disp(sol_best)disp(最短距離：)disp(E_best)程序運(yùn)行結(jié)果為:蟻群算法:clear allclc% 導(dǎo)入數(shù)據(jù)citys=1304 2312;3639 1315;4177 2244;3721 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;256

38、2 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;% 計(jì)算城市間相互距離n = size(citys,1);D = zeros(n,n);for i = 1:n for j = 1:n if i = j D(i,j) = sqrt(sum(citys(i,:

39、) - citys(j,:).2); else D(i,j) = 1e-4; end end end% 初始化參數(shù)m = 50; % 螞蟻數(shù)量alpha = 1; % 信息素重要程度因子beta = 5; % 啟發(fā)函數(shù)重要程度因子rho = 0.1; % 信息素?fù)]發(fā)因子Q = 1; % 常系數(shù)Eta = 1./D; % 啟發(fā)函數(shù)Tau = ones(n,n); % 信息素矩陣Table = zeros(m,n); % 路徑記錄表iter = 1; % 迭代次數(shù)初值iter_ma* = 200; % 最大迭代次數(shù) Route_best = zeros(iter_ma*,n); % 各代最正確路徑

40、 Length_best = zeros(iter_ma*,1); % 各代最正確路徑的長(zhǎng)度 Length_ave = zeros(iter_ma*,1); % 各代路徑的平均長(zhǎng)度 % 迭代尋找最正確路徑while iter = rand); target = allow(target_inde*(1); Table(i,j) = target; end end % 計(jì)算各個(gè)螞蟻的路徑距離 Length = zeros(m,1); for i = 1:m Route = Table(i,:); for j = 1:(n - 1) Length(i) = Length(i) + D(Route(

41、j),Route(j + 1); end Length(i) = Length(i) + D(Route(n),Route(1); end % 計(jì)算最短路徑距離及平均距離 if iter = 1 min_Length,min_inde* = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_inde*,:); else min_Length,min_inde* = min(Length); Length_best(iter) =

42、 min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) = min_Length Route_best(iter,:) = Table(min_inde*,:); else Route_best(iter,:) = Route_best(iter-1),:); end end % 更新信息素 Delta_Tau = zeros(n,n); % 逐個(gè)螞蟻計(jì)算 for i = 1:m % 逐個(gè)城市計(jì)算 for j = 1:(n - 1) Delta_Tau(Table(i,j),Table(i,j+1) = Delta_Tau(Table(i,j),Table(i,j+1) + Q/Length(i); end Delta_Tau(Table(i,n),Table(i,1) = Delta_Tau(Table(i,n),Table(i,1) + Q/Length(i); end Tau = (1-rho)