基因表達(dá)式編程教學(xué)課件5

先進(jìn)計(jì)算模型（5）自然計(jì)算模型系列之蟻群算法四川大學(xué)計(jì)算機(jī)學(xué)院2008-2009博士生課程（遺傳算法，基因表達(dá)式編程，粒子群算法(PSO)，蟻群算法，魚群算法，….)唐常杰

四川大學(xué)計(jì)算機(jī)學(xué)院2023/9/281目錄，大致計(jì)劃第一次自然計(jì)算模型系列1：概述篇自然計(jì)算模型系列2粒子群（

魚群/鳥群）算法自然計(jì)算模型系列3基因表達(dá)式編程第二次自然計(jì)算模型系列4：模擬退火算法自然計(jì)算模型系列5：蟻群算法自然計(jì)算模型系列6：免疫計(jì)算模型（思路和比喻）下載URL:校園網(wǎng)和學(xué)院網(wǎng)

/~chjtang/teach/tang_teaching.htm7/~tangchangjie/teach/tang_teaching.htm2023/9/282下一次自然計(jì)算模型（NatureComputing)概述GEP基因表達(dá)式編程PSO

粒子群算法魚群鳥群算法今天蟻群算法模擬退火算法人工免疫思想（比喻）

……

歡迎同學(xué)發(fā)言（5-30分鐘均可）提綱2023/9/283資料出處和致謝參考資料：本PPT僅作和同學(xué)們?cè)谟懻摪鎯?nèi)交流之用參考了若干教科書，文獻(xiàn)和論文和報(bào)告。在末尾列出50多篇，但參考的文獻(xiàn)不只這些,主要是遺傳算法、基因表達(dá)式編程、粒子群算法的相關(guān)作者等等，包括國內(nèi)外，校內(nèi)外專家和本實(shí)驗(yàn)室成員的工作對(duì)未列出的文獻(xiàn)作者也在此一并致謝。參考文獻(xiàn)可能有遺漏，歡迎未列出的文獻(xiàn)作者及時(shí)指出，，以便即時(shí)在參考文獻(xiàn)中補(bǔ)充。作PPT類似于把小說改編為劇本，有重新創(chuàng)作的成分，也希望其它引用本PPT材料的標(biāo)注本PPT2023/9/284歡迎指正我們?cè)谶@方面方面的工作不多，難免疏漏：我們?cè)谶@方面方面的工作不多，難免疏漏：論文參見…..2023/9/285課程計(jì)劃和特點(diǎn)有多位（7-8位）博士生導(dǎo)師作專題講座，每個(gè)老師講課8小時(shí)（大約需要準(zhǔn)備40—60小時(shí)）特點(diǎn)廣---N位導(dǎo)師，N=8~9,N+

個(gè)領(lǐng)域，M個(gè)課題，(M>N).“N家講座”，不敢比百家…新

---要求報(bào)告新技術(shù)前沿淺

–因?yàn)闀r(shí)間短，主要將思想，方法，介紹成果。不可能深入到公式和算法細(xì)節(jié)實(shí)---結(jié)合實(shí)際，結(jié)合博士生可能的選題2023/9/286學(xué)習(xí)方法學(xué)思想，學(xué)觀點(diǎn)，學(xué)方法，聯(lián)系自己的科研選題。1先觀其大略。（諸葛亮法，討論班和聽學(xué)術(shù)報(bào)告適用）

王粲的《英雄記鈔》，諸葛亮與徐庶、石廣元、孟公威一道游學(xué)，“三人務(wù)于精熟，而亮獨(dú)觀其大略”。多快好省地?cái)U(kuò)展知識(shí)面，學(xué)思想、方法。

宋代理學(xué)家陸象山：“讀書且平平讀，未曉處且放過，不必太滯?！?，聽課時(shí)不懂的，暫時(shí)放過，最后根據(jù)緩急，去理解。今天的GEP兩小時(shí)觀其大略，然后用一學(xué)期鉆研它。2再一個(gè)小課題寫課程論文（考核），從一點(diǎn)深入。交相關(guān)老師評(píng)閱。博士生選題。（先寬度優(yōu)先，試選，選定后，就深度優(yōu)先，深入下去）2023/9/287

這里根據(jù)情況，可插入自然計(jì)算模型PPT2023/9/288蟻群優(yōu)化算法計(jì)算機(jī)科學(xué)家向大自然學(xué)習(xí)的又一個(gè)成果

2023/9/289

基于直觀或經(jīng)驗(yàn)，摸著石頭過河，石頭--啟發(fā)性知識(shí)可接受的花費(fèi)（時(shí)間、空間）下，給出一個(gè)可行解，可行解與最優(yōu)解偏差事先不一定可算.特點(diǎn)（與傳統(tǒng)優(yōu)化方法不同）：直觀經(jīng)驗(yàn)求解，不考慮所得解與最優(yōu)解的偏離程度.啟發(fā)性規(guī)則：不保證成功，且可能矛盾。三思而行（哪三個(gè)？危、變、退）當(dāng)斷不斷反受其亂如森林中下山沿小溪，可能下到天池去了，沒出山.(解釋“以概率P執(zhí)行啟發(fā)規(guī)則”）啟發(fā)式算法（heuristicalgorithm）2023/9/2810參考書作者：李士勇等出版社：哈爾濱工業(yè)大學(xué)出版社出版日期：2004-0916開頁數(shù)：245英文書較多2023/9/2811對(duì)螞蟻的觀察1單只螞蟻無所作為蟻群復(fù)雜的社會(huì)行為：筑巢、覓食、遷徙、清掃蟻巢小孩最容易觀察到的是螞蟻搬家，“皇絲瑪瑪….”美國阿爾伯塔大學(xué)：設(shè)計(jì)出多個(gè)機(jī)器人共推物體算法2023/9/2812對(duì)螞蟻的觀察2分工行為（蟻皇生育、工蟻干活、兵蟻保衛(wèi)）美國西北大學(xué)：螞蟻算法卡車油漆工人分組，某組任務(wù)特緊，另一組幫助。提高了整體的生產(chǎn)率?！爸病毙袨橐粋€(gè)螞蟻--神經(jīng)元，螞蟻間信息交流，隨機(jī)連接神經(jīng)網(wǎng)絡(luò)群體智能2023/9/2813對(duì)螞蟻的觀察3（不是一般小孩們的觀察）單只螞蟻無所作為蟻群復(fù)雜的社會(huì)行為：筑巢、覓食、遷徙、清掃蟻巢覓食行為兩個(gè)成語:雁過留聲，聞風(fēng)而動(dòng)，改為兩個(gè)（本行內(nèi)用）新成語：

蟻過留素（信息素，pheromone）,聞素而跟（其他螞蟻）良性循環(huán)：路好（有食且近）

蟻多

-信息素多

蟻多--…..（隨時(shí)會(huì)蒸發(fā)掉一部分），開始：信息素濃度路短素濃。（下頁）2023/9/2814為什么蟻路趨短？良性循環(huán)是怎樣開始的？符號(hào)和假定：路徑上的信息素濃度函數(shù)

記為Ph(pheromone

)螞蟻在路程上均勻釋放信息素，d(Ph)/ds=常數(shù)

等邊三角形ABC

螞蟻M1:AC,M2:ABC

找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A點(diǎn)時(shí)，M2才到C點(diǎn)。AC上蟻氣：兩次信息素疊加（去-回），AB路只有去一次信息素，

B

AC信息素濃度Ph(AC)>Ph(ABC)

后面螞蟻聞素而跟，AC

進(jìn)入良性循環(huán),信息素越來越多

上帝（如果有的話）造化神奇。嘆服。2023/9/2815為什么蟻路趨短？良性循環(huán)是怎樣開始的？符號(hào)和假定：路徑上的信息素濃度函數(shù)

記為Ph(pheromone

)螞蟻在路程上均勻釋放信息素，d(Ph)/ds=常數(shù)

等邊三角形ABC

螞蟻M1:AC,M2:ABC

找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A點(diǎn)時(shí)，M2才到C點(diǎn)。AC上蟻氣：兩次信息素疊加（去-回），AB路只有去一次信息素，

B

AC信息素濃度Ph(AC)>Ph(ABC)

后面螞蟻聞素而跟，AC

進(jìn)入良性循環(huán),信息素越來越多

上帝（如果有的話）造化神奇。嘆服。2023/9/2816為什么是螞蟻？要點(diǎn)？螞蟻群居群動(dòng)，很少有獨(dú)行俠，選擇信息素濃的路徑，喜歡熱鬧，追求蟻氣（人氣）人也類似。

兩家飯店，一家熱熱火火，一家門可羅雀，你選哪家？選登山旅游線，一般人選人氣多的（信息素濃的）信息素啟發(fā)性知識(shí)：人氣高的自有其優(yōu)點(diǎn)飯店請(qǐng)名人寫詩歌作畫、寫對(duì)聯(lián)留下信息素商業(yè)”托”,假造信息素優(yōu)勢(shì)：并行+分布+信息素2023/9/2817要點(diǎn)螞蟻群居群動(dòng)，很少有獨(dú)行俠，趨向信息素濃度強(qiáng)點(diǎn)，習(xí)熱鬧，人氣（蟻氣）人也類似。

兩家飯店相鄰，一家熱熱火火，一家門可羅雀，你選哪家？選登山旅游線，一般人選人氣多的（信息素濃的）這里有啟發(fā)性知識(shí)：人氣高的，自有其優(yōu)點(diǎn)飯店請(qǐng)名人寫詩歌作畫、寫對(duì)聯(lián)留下信息素商業(yè)”托兒”,假造信息素優(yōu)勢(shì)：并行+分布+信息素70%選紅火的，不一定每人是這樣按概率.0.7選紅火的2023/9/2818要點(diǎn)螞蟻群居群動(dòng)，很少有獨(dú)行俠，趨向信息素濃度強(qiáng)點(diǎn)，習(xí)熱鬧，人氣（蟻氣）人也類似。

兩家飯店，一家熱熱火火，一家門可羅雀，你選哪家？選登山旅游線，一般人選人氣多的（信息素濃的）信息素啟發(fā)性知識(shí)：人氣高的自有其優(yōu)點(diǎn)飯店請(qǐng)名人寫詩歌作畫、寫對(duì)聯(lián)留下信息素商業(yè)”托兒”,假造信息素優(yōu)勢(shì)：并行+分布+信息素2023/9/2819觀察后收獲（不是小孩，而是科學(xué)家的收獲）意大利學(xué)者M(jìn)Dorigo，Vmaniezzo和AColorni20世紀(jì)90年代：螞蟻系統(tǒng)（antsystem，AS）求解旅行商問題（TravelingSalesmanProblem，簡(jiǎn)稱TSP）90年代中期，用于廣泛領(lǐng)域，取得成果MDorigo發(fā)展為用的優(yōu)化技術(shù)-蟻群優(yōu)化（AntColonyOptimization，簡(jiǎn)稱ACO）WJGutjahr：ACO的收斂性用于合優(yōu)化，函數(shù)優(yōu)化、系統(tǒng)辨識(shí)、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘、網(wǎng)絡(luò)路由2023/9/2820ACO國際研討會(huì)四屆ACO國際研討會(huì)1998、2000年、2002年、2004年，比利時(shí)布魯塞爾大學(xué)如果這是美國人發(fā)明的，估計(jì)還要紅火一些2023/9/2821蟻群算法源革生物啟發(fā)計(jì)算大潮中的一朵小浪花時(shí)間：20世紀(jì)90年代地點(diǎn)：意大利人物：意大利M．Dorigo，V．Maniezzo，A．Colorni目的：模擬自然界螞蟻搜索路徑的行為，結(jié)果：群體智能理論應(yīng)用：求解NP問題（TSP問題、分配問題、job-shop調(diào)度問題），解復(fù)雜優(yōu)化問題（離散優(yōu)化問題）有優(yōu)勢(shì)2023/9/2822應(yīng)用領(lǐng)域解決大多數(shù)優(yōu)化問題或轉(zhuǎn)化為優(yōu)化求解的問題。分類、聚類、模式識(shí)別、多目標(biāo)優(yōu)化、QoS、流程規(guī)劃信號(hào)處理機(jī)器人控制、決策支持2023/9/2823背景群體智能理論包括：

微粒群算法，ParticleSwarmOptimization,PSO

魚群鳥群追尾（見賢思齊）已講過。

蟻群算法(AntColonyOptimization,ACO)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，2023/9/2824蟻群優(yōu)化算法研究背景與傳統(tǒng)進(jìn)化算法-梯度算法的差異：，

概率搜索(不一定每人都喜歡熱鬧的餐廳）1并行+分布，無中控，個(gè)別螞蟻死亡無關(guān)大局2因而程序堅(jiān)固。3非直接信息交流，（廣播）4可處理離散對(duì)象5實(shí)現(xiàn)簡(jiǎn)單

2023/9/2825一個(gè)在本PPT中講兩次的實(shí)例旅行商問題

（第一次了解大致思想）N城有向圖G=（N，A），城市間距離目標(biāo)函數(shù)為，

為城市1,2，…n的一個(gè)排列是一個(gè)候選解，追求總長(zhǎng)最小的解?；【€城-城距離矩陣后面還有另一個(gè)信息素矩陣2023/9/2826一個(gè)在本PPT中講兩次的實(shí)例

（第一次了解大致思想）四個(gè)城市的非對(duì)稱TSP問題，距離矩陣和城市圖示如下：城-城距離矩陣后面還有另一個(gè)信息素矩陣2023/9/2827解的存在性解一定存在N!個(gè)排列，N!個(gè)長(zhǎng)度，其中必由最小數(shù)但是N！比指數(shù)增長(zhǎng)快1*2*3*….*10=(1*10)*(2*9)*…*(5*5)>105=N(N/2)窮舉法計(jì)算時(shí)間太長(zhǎng)20!=2.4X1018每秒評(píng)估100萬條路徑，需要7萬年2023/9/2828解的存在性解一定存在N!個(gè)排列，N!個(gè)長(zhǎng)度，其中必由最小數(shù)但是N！比指數(shù)增長(zhǎng)快1*2*3*….*10=(1*10)*(2*9)*…*(5*5)>105=N(N/2)窮舉法計(jì)算時(shí)間太長(zhǎng)20!=2.4X1018每秒評(píng)估100萬條路徑，需要7萬年2023/9/2829一個(gè)在本PPT中講兩次的實(shí)例

（第一次了解大致思想）共4只螞蟻，都從城A出發(fā)，揮發(fā)因子（日取其半，萬世不竭）有向圖矩陣共有12條弧，初始信息素記憶矩陣為：弧的蟻氣競(jìng)爭(zhēng)：總數(shù)為衡量1,是“0和博弈”，此消彼長(zhǎng)信息素矩陣不同于城-城距離矩陣2023/9/2830實(shí)例假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為W2，這個(gè)解是截止到當(dāng)前的最優(yōu)解，(碰巧是實(shí)際最優(yōu)解)路長(zhǎng)代價(jià)下一輪的信息素將獎(jiǎng)優(yōu)罰劣這條好路上的弧線將得到獎(jiǎng)勵(lì)，所有都按比例揮發(fā)一半2023/9/2831信息素更新

獎(jiǎng)優(yōu)罰劣信息素更新規(guī)則，得到更新矩陣（有揮發(fā)，有獎(jiǎng)勵(lì)）。有增有減信息素總量仍為為1四個(gè)1/6，下頁解釋所有都按比例揮發(fā)一半，（公平）2023/9/2832實(shí)例信息素更新信息素更新規(guī)則，得到更新矩陣（有揮發(fā)，有獎(jiǎng)勵(lì)）。四個(gè)1/6的來源：12條弧先揮發(fā)（收遺產(chǎn)稅）一半，每條上s收1/24，收稅共得12/24，分給4個(gè)獲獎(jiǎng)弧，每個(gè)得到3/24的獎(jiǎng)勵(lì)。優(yōu)弧上總計(jì)為1/6.以稅作獎(jiǎng)

總的蟻氣還是1揮發(fā)作稅：所有都按比例揮發(fā)一半，一共揮發(fā)12/24(遺產(chǎn)稅）,用來下一步作獎(jiǎng)勵(lì)用2023/9/2833實(shí)例信息素更新信息素更新規(guī)則，得到更新矩陣（有揮發(fā)，有獎(jiǎng)勵(lì)）。1表示第一次外循環(huán)結(jié)束的狀態(tài)四個(gè)1/6，是揮發(fā)一半，又得到了3/24的獎(jiǎng)勵(lì)好路徑：ACDBA所有都按比例揮發(fā)一半，BACDDBAC2023/9/2834重復(fù)外循環(huán)，再揮發(fā)--獎(jiǎng)勵(lì)一次上次W2已是全局最優(yōu)，W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素?fù)]發(fā)。這次之后，信息素量分布為好的路徑不變，表示收斂了2023/9/2835重復(fù)外循環(huán)，再揮發(fā)--獎(jiǎng)勵(lì)一次得到全局最優(yōu)解，信息素更新不再依賴于以群的行走路線，“富人越富強(qiáng)人越窮”，而且富者剝削窮者第三次外循環(huán)后信息素矩陣為：注意每次收遺產(chǎn)稅一半，但日取其半，萬世不竭?！?好的路徑不變，表示收斂了2023/9/2836為什么實(shí)現(xiàn)簡(jiǎn)單？

算法中僅涉及各種基本的數(shù)學(xué)操作，對(duì)CPU和內(nèi)存的要求不高。只輸出：目標(biāo)函數(shù)值，無需梯度信息。（導(dǎo)數(shù)，微分）2023/9/2837蟻群算法（AS）研究進(jìn)展

三個(gè)小分支：更新信息素的方法不同Ant-density、Ant-quantity

Ant-cycle。

信息素表達(dá)為路徑質(zhì)量的增函數(shù)。效率：不大于75城市的TSP中，可以用

個(gè)別螞蟻一動(dòng)一更新,個(gè)人英雄主義，急功近利所有螞蟻完成行程才更新后面例子用此法

集體英雄主義2023/9/2838蟻群算法（AS）研究進(jìn)展

性能改進(jìn)。精英策略(ElitistStrategy)，獎(jiǎng)勵(lì)先進(jìn)（錦上添花）：

1給身份。好路徑后續(xù)行程作全局最優(yōu)行程，記為Tgb，

2給優(yōu)惠。信息素更新時(shí)，給政策優(yōu)惠（加權(quán)），經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機(jī)會(huì)。

過分獎(jiǎng)勵(lì)的缺點(diǎn)：若精英過多，會(huì)早熟。（較早收斂于局部次優(yōu)解）2023/9/2839一種獎(jiǎng)勵(lì)和懲罰方法（有多種不同處理方法）總的思路。（在后面實(shí)例中采用的一種做法）

1信息素是上一輪的遺產(chǎn)。

2所有弧線按比例揮發(fā)信息素（坐吃都會(huì)山空，公平）（比喻：收遺產(chǎn)稅或揮發(fā)）3以稅資獎(jiǎng)，全部稅款作為對(duì)好路徑上弧線的蟻氣獎(jiǎng)勵(lì)維持信息素總量為衡量14各條弧線競(jìng)爭(zhēng)是1和博弈，多次迭代后，”富弧越富，窮弧越窮”，2023/9/2840螞蟻系統(tǒng)也收稅不鼓勵(lì)坐吃山空每條路信息素自然揮發(fā)，（收遺產(chǎn)稅）：獎(jiǎng)勵(lì)先進(jìn)多種策略：

1只獎(jiǎng)勵(lì)最優(yōu)路徑上弧計(jì)算簡(jiǎn)單，后面實(shí)例用此法

2按先進(jìn)程度加權(quán)地給多種等級(jí)的獎(jiǎng)（精細(xì)，復(fù)雜）作用：減小已訪問的路徑再次被選擇的概率。2023/9/2841Rank-basedVersionAS

按先進(jìn)程度加權(quán)地給多種等級(jí)的獎(jiǎng)

錦上添花

獎(jiǎng)勵(lì)好路徑的一種方法好路徑多加信息素，其行程長(zhǎng)度排序，螞蟻放置信息素的強(qiáng)度公式：，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。揮發(fā)后剩余遺產(chǎn)r越小，排序越前，路越短，W-r越大，獎(jiǎng)勵(lì)信息素越多2023/9/2842錦上添花發(fā)的效率問題：大型TSP問題中（最多包含132座城市）優(yōu)于GA和SA優(yōu)于基本AS（模擬退火），2023/9/2843應(yīng)用旅行商問題組合優(yōu)化問題網(wǎng)絡(luò)路由優(yōu)化武器攻擊目標(biāo)分配和優(yōu)化車輛運(yùn)行路徑規(guī)劃區(qū)域性無線電頻率自動(dòng)分配、2023/9/2844應(yīng)用：信路由優(yōu)化HP公司和英國電信公司蟻群路由算法（AntColonyRouting,ACR）。思想：螞蟻分布并行地檢查經(jīng)過堵塞的路由，延遲，對(duì)表做較大的增強(qiáng)信息素?fù)]發(fā)

拋棄過期的路由信息當(dāng)前最優(yōu)路由擁堵，迅速搜尋另一條替代路徑2023/9/2845應(yīng)用：分類Lumer和Faieta螞蟻搬運(yùn)蟻卵問題：各種螞蟻（形、色）隨機(jī)散布二維平面，分類之Begin//大致思路初始化：隨機(jī)地散布虛擬螞蟻While(notfinish)

foreach螞蟻

{if(螞蟻空閑)隨機(jī)移動(dòng)一步;if(螞蟻空閑且碰見蟻卵）then背起來；隨機(jī)移動(dòng)一步;

if(碰見）和背上相似的蟻卵卸貨

}finish=達(dá)到分類目的或超時(shí);End類似實(shí)例：學(xué)生協(xié)助老師把試卷按分?jǐn)?shù)線分類可用多進(jìn)程OOP實(shí)現(xiàn)2023/9/2846一個(gè)較完整的實(shí)例旅行商問題TSP

（本頁到結(jié)束）TSP,（TravelingSsalesmanProblem）1960管梅谷教授提出，中國郵遞員問題。問題描述：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短（注意，與一筆畫問題不同）。一個(gè)較完整的實(shí)例:從本頁一直PPT到結(jié)束2023/9/2847較完整實(shí)例TSP問題的數(shù)學(xué)描述(之一種）約束條件目標(biāo)選走路段表示方法2023/9/2848計(jì)算復(fù)雜性城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325year隨城市增多，計(jì)算時(shí)間增加很快。到31個(gè)城市時(shí)，要計(jì)算325年。2023/9/2849較完整實(shí)例注意數(shù)據(jù)結(jié)構(gòu)要用一定的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)蟻群的記憶能力，記憶訪問過的節(jié)點(diǎn)。等等保存弧上信息素的結(jié)構(gòu)。

2023/9/2850較完整實(shí)例TSP

圖論的N城有向圖G=（N，A），城市間距離目標(biāo)函數(shù)為，其中為城市1,2，…n的一個(gè)排列，。2023/9/2851較完整實(shí)例：若干簡(jiǎn)化和假定設(shè)m只螞蟻，在圖的相鄰節(jié)點(diǎn)間移動(dòng)，求解方式：協(xié)作+異步：多個(gè)螞蟻可是多線程，可并發(fā)、可異步工作—評(píng)價(jià)—在工作—再評(píng)價(jià)螞蟻下一步轉(zhuǎn)向何方由弧上兩參數(shù)決定：1信息素（蟻氣、痕跡）。2可見度（那些城市可以去）。

信息素更新方式

揮發(fā)，按比率減少，（收遺產(chǎn)稅）

增強(qiáng)，錦上添花，好邊獎(jiǎng)勵(lì)信息素。2023/9/2852較完整實(shí)例：螞蟻一步運(yùn)動(dòng)

問題螞蟻有多個(gè)城市可見時(shí)，首選哪一個(gè)城市訪問？

方法：按蟻氣份額隨機(jī)（弧上信息素在總息素中份額）（實(shí)現(xiàn)，輪盤賭用份額扇形，（0-360度）執(zhí)骰子，radom(360)落在哪一個(gè)扇形中，選中（下頁解釋）

隨時(shí)或階段性地總結(jié)

優(yōu)化程度：表達(dá)為信息素保存2023/9/2853較完整實(shí)例：螞蟻一步運(yùn)動(dòng)隨機(jī)+概率（城市信息素在總息素中占的的份額）（實(shí)現(xiàn)，用輪盤上用份額和扇形，（0-360）執(zhí)骰子，radom(360)落在那個(gè)扇形中，選那個(gè)）下頁解釋實(shí)現(xiàn)方式按概率選擇有什么好處？不一定每個(gè)螞蟻每次都去信息素大的城市，這擴(kuò)大了搜索范圍，避免早熟，容易全局優(yōu)化。但多次操作，總的來看，是趨向于去信息素大的城市2023/9/2854較完整實(shí)例：螞蟻的一步運(yùn)動(dòng)隨機(jī)+概率（城市信息素在總息素中占的的份額）（實(shí)現(xiàn)，用輪盤上用份額和扇形，（0-360）執(zhí)骰子，radom(360)落在那個(gè)扇形中，選那個(gè)）下頁解釋實(shí)現(xiàn)方式按概率選擇有什么好處？不一定每個(gè)螞蟻每次都去信息素大的城市，這擴(kuò)大了搜索范圍，避免早熟，容易全局優(yōu)化。但多次操作，總的來看，是趨向于去信息素大的城市2023/9/2855輪盤賭，轉(zhuǎn)糖餅，按適應(yīng)度大小分配份額GEP中多個(gè)物種按適應(yīng)度比較繁殖機(jī)會(huì)這里，按蟻氣在多個(gè)城市中選當(dāng)前首訪城市。小餅龍虎政策向”優(yōu)良”

品種傾斜適應(yīng)度大的，站的份額多2023/9/2856輪盤賭算法用上頁的例子1按龍、虎、./小糖餅的份額（適應(yīng)度）設(shè)計(jì)分割數(shù)組，分辨率1度如【0—180】標(biāo)記為糖餅占用180/360=50%【90-100】標(biāo)記為龍占100/360=1/36…..【340-360】標(biāo)記為虎占20/360=2/36

用多個(gè)if語句或不等式比較，可從角度得到對(duì)應(yīng)的標(biāo)記

IntGet-Label（Alpha)

{容易實(shí)現(xiàn)，略去代碼}LabelType={糖餅,龍,….,虎}算法LabelTypeDiece()//返回首選城市{Radomize()；

Alpha=Radom(360);//0-360之間隨機(jī)數(shù)Return(Get-Label（Alpha))}調(diào)用這個(gè)函數(shù)份額可能是動(dòng)態(tài)的，每輪更新份額2023/9/2857螞蟻一步目標(biāo)按概率選擇隨機(jī)+

按城市信息素在總息素中占的的份額（實(shí)現(xiàn)，用輪盤上用份額和扇形，（0-360）執(zhí)骰子，radom(360)落在份額扇形中，（上頁解釋）

走完一步，作階段性總結(jié)表達(dá)為信息素保存到未訪城市的概率為城市在信息素中占的的份額已訪城市不再去，份額為0不一定每次都最大的，但大多數(shù)是選最大的用此作份額扇形的輪盤賭2023/9/28585初始化n城的TSP問題，所有城市集合N={1,2,3,…,n}城間距離矩陣，弧（I,j)上信息素初值，m只螞蟻從同一城市出發(fā)。初始解：按編號(hào)走（這是一種走法，但不一定最好） |A|：弧的總數(shù)使得所有信息素和為12023/9/2859主程序三大部分Dowhile（1）{Init:{……第s個(gè)螞蟻s,從起點(diǎn)i0出發(fā)，

….//L(s)----螞蟻s已訪城市集

L(s)=空集……//初始化}If(Satisfy)return(currentresult);

for（each螞蟻）走一步盡量好；//內(nèi)循環(huán)，下頁解釋

揮發(fā)和獎(jiǎng)勵(lì)（）；//總結(jié)評(píng)比，獎(jiǎng)勵(lì)懲罰，再循環(huán)}2023/9/2860內(nèi)循環(huán)對(duì)螞蟻編號(hào)s循環(huán),1<=s<=m

每個(gè)螞蟻?zhàn)咭徊?，要盡量好{螞蟻s當(dāng)前城市記為i，if 第s只螞蟻找到一個(gè)解，s暫休息。否則，若則以概率 ， 到達(dá)j， if則到達(dá) }

第s個(gè)螞蟻訪完N個(gè)城市，得到一個(gè)解它可暫時(shí)休息。城市走遍了2023/9/2861內(nèi)循環(huán)對(duì)第s個(gè)螞蟻循環(huán)

螞蟻s在城市i，若 完成第s只螞蟻的計(jì)算。否則，if則以概率 ，或 到達(dá)j， if則到達(dá)

第s個(gè)螞蟻還沒完成任務(wù)還有城市未訪問到未訪城市的概率，即城市信息素所占份額已訪城市不再去2023/9/2862內(nèi)循環(huán)對(duì)第s個(gè)螞蟻循環(huán)

螞蟻s在城市i，若 完成第s只螞蟻的計(jì)算。否則，若則以概率 ， 到達(dá)j