【正文】 碼公式為： 2021/6/15 75 第五步：確定個(gè)體評(píng)價(jià)方法。 第六步：設(shè)計(jì)遺傳算子。 可知， Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即有： F(X)=f(x1， x2) 選擇運(yùn)算使用比例選擇算子； 交叉運(yùn)算使用單點(diǎn)交叉算子； 變異運(yùn)算使用基本位變異算子。 2021/6/15 76 第七步：確定遺傳算法的運(yùn)行參數(shù)。 對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下： 群體大?。?M＝ 80 終止代數(shù)： T＝ 200 交叉概率： pc＝ 變異概率： pm＝ 通過(guò)上述七個(gè)步驟就可構(gòu)成用于 Rosenbrock函數(shù)優(yōu)化計(jì)算的基本遺傳算法。 2021/6/15 77 自適應(yīng)變異 如果雙親的基因非常相近 ， 所產(chǎn)生的后代相對(duì)于雙親也必然比較接近 。 這樣所期待的性能改善也必然較小 。 類似于 “ 近親繁殖 ” 。 所以基因模式的單一性不僅減慢進(jìn)化歷程 ， 而且可能導(dǎo)致進(jìn)化停滯 ， 過(guò)早地收斂于局部的極值解 。 Darrel Wnitly提出了一種如下的自適應(yīng)變異的方法：在交叉前 ，以海明 (Hamming)距離測(cè)定雙親基因碼的差異 ， 根據(jù)測(cè)定值決定后代的變異概率 pm。 若雙親的差異較小 ， 則選取較大的變異概率 。 當(dāng)群體中的個(gè)體過(guò)于趨于一致時(shí) ， 通過(guò)變異的增加來(lái)提高群體的多樣性 ， 即增強(qiáng)了算法維持全局搜索的能力；反之 ， 當(dāng)群體已具備較強(qiáng)的多樣性時(shí) ， 減小變異率 ， 從而不破壞優(yōu)良的個(gè)體 。 五、遺傳算法的改進(jìn) 2021/6/15 78 部分替代法 設(shè) PG為上一代進(jìn)化到下一代時(shí)被替換的個(gè)體的比例，則按此比例，部分個(gè)體被新的個(gè)體所取代，而其他部分的個(gè)體則直接進(jìn)入下一代。 PG越大，進(jìn)化得越快，但算法的穩(wěn)定性和收斂性將受到影響；而 PG越小，算法的穩(wěn)定性越好，但進(jìn)化速度將變慢?？梢?，應(yīng)該尋求運(yùn)行速度與穩(wěn)定性、收斂性之間的諧調(diào)平衡。 2021/6/15 79 優(yōu)秀個(gè)體保護(hù)法 這種方法對(duì)于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。 這樣可以防止優(yōu)秀個(gè)體由于復(fù)制、交叉或變異中的偶然因素而被破壞掉。 這是增強(qiáng)算法穩(wěn)定性和收斂性的有效方法。 但同時(shí)也可能使遺傳算法陷入局部的極值范圍。 2021/6/15 80 分布式遺傳算法 該方法將一個(gè)總的群體分為若干個(gè)子群，各子群將具有略微不同的基因模式，它們各自的遺傳過(guò)程具有相對(duì)的獨(dú)立性和封閉性，因而進(jìn)化的方向也略有差異，從而保證了搜索的充分性及收斂結(jié)果的全局最優(yōu)性。 另一方面，在各子群之間又以一定的比例定期地進(jìn)行優(yōu)良個(gè)體的遷移，即每個(gè)子群將其中最優(yōu)的幾個(gè)個(gè)體輪流送到其他子群中。 這樣做的目的是期望使各子群能共享優(yōu)良的基因模式以防止某些子群向局部最優(yōu)方向收斂。 分布式遺傳算法模擬了生物進(jìn)化過(guò)程中的基因隔離和基因遷移，即各子群之間有相關(guān)的封閉性，又有必要的交流和溝通。 研究表明，在總的種群個(gè)數(shù)相同的情況下，分布式遺傳算法可以得到比單一種群遺傳算法更好的效果。 2021/6/15 81 運(yùn)用基于 Matlab的遺傳算法工具箱非常方便 ， 遺傳算法工具箱里包括了我們需要的各種函數(shù)庫(kù) 。 目前 ， 基于 Matlab的遺傳算法工具箱也很多 ， 比較流行的有英國(guó)設(shè)菲爾德大學(xué)開發(fā)的遺傳算法工具箱 GATBX、 GAOT以及 Math Works公司推出的 GADS。 GADS 這個(gè)是 ， 全名叫 Geic Algorithm and Direct Search Toolbox。 在 Help里面有對(duì)這個(gè)工具箱的詳細(xì)介紹 ， 還有很多例子作演示 。 另一方面它還提供了一個(gè)圖形用戶界面的工具 ， 名為 gatool， 有了這個(gè)工具就可以不必輸入繁瑣的命令行參數(shù) ， 能方便而且直觀的觀察算法的運(yùn)行過(guò)程 。 MATLAB下遺傳算法工具箱 2021/6/15 82 蟻群算法 2021/6/15 83 蟻群算法是最近幾年才提出的一種新型的模擬進(jìn)化算法，由意大利學(xué)者 Colorni A、 Dorigo M和 Maniezzo V于 1992年首先提出，用蟻群在搜索食物源的過(guò)程中所體現(xiàn)出來(lái)的尋優(yōu)能力來(lái)解決一些離散系統(tǒng)優(yōu)化中的困難問(wèn)題。 已經(jīng)用該方法解決了旅行商問(wèn)題、指派問(wèn)題、調(diào)度問(wèn)題等，取得了一系列較好的實(shí)驗(yàn)結(jié)果。 2021/6/15 84 像螞蟻這類群居昆蟲，雖然沒(méi)有視覺(jué)，卻能找到由蟻穴到食物源的最短路徑。 雖然單只螞蟻的行為極其簡(jiǎn)單，但由這樣的單個(gè)簡(jiǎn)單個(gè)體所組成的蟻群群體卻表現(xiàn)出極其復(fù)雜的行為，能夠完成復(fù)雜的任務(wù)，不僅如此，螞蟻還能適應(yīng)環(huán)境的變化，如：在螞蟻運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)， 螞蟻能夠很快重新找到最優(yōu)路徑。 人們經(jīng)過(guò)大量的研究發(fā)現(xiàn)，螞蟻個(gè)體間通過(guò)一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，從而能夠相互協(xié)作，完成復(fù)雜的任務(wù)。 螞蟻之所以表現(xiàn)出復(fù)雜有序的行為，個(gè)體之間的信息交流和相互協(xié)作起著重要的作用。 螞蟻覓食的生物學(xué)基礎(chǔ) 2021/6/15 85 螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下該物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向。螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。 因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后者選擇該路徑的概率越大。 螞蟻個(gè)體之間就是通過(guò)這種信息的交流達(dá)到搜索食物的目的。 2021/6/15 86 蟻群系統(tǒng)示意圖 食物 蟻巢 A D B C 障礙物 1 1 1 2 2 1 2021/6/15 87 假定障礙物的周圍有兩條道路可從螞蟻的巢穴到達(dá)食物源，分別具有長(zhǎng)度 4和 6。螞蟻在單位時(shí)間內(nèi)可移動(dòng)一個(gè)單位長(zhǎng)度的距離。開始時(shí)所有道路上都未留有任何信息素。 在 t=0時(shí)刻， 20只螞蟻從巢穴出發(fā)移動(dòng)到 A，它們以相同的概率選擇左側(cè)或右側(cè)道路，因此平均有 10只螞蟻?zhàn)咦髠?cè)， 10只走右側(cè)。 t=4時(shí)刻，第一組到達(dá)食物源的螞蟻將折回，此時(shí)第二組的螞蟻到達(dá) CD中點(diǎn)處。 t=5時(shí)刻，兩組螞蟻將在 D點(diǎn)相遇。此時(shí) BD上的信息素和 CD上的相同，因?yàn)楦饔?10只螞蟻選擇了相應(yīng)的道路，從而有 5只返回的螞蟻將選擇 BD，而另 5只將選擇 CD，第二組螞蟻繼續(xù)向食物方向移動(dòng)。 2021/6/15 88 t=8時(shí)刻，前 5只螞蟻將返回巢穴，此時(shí)在 AC中點(diǎn)處、 CD中點(diǎn)處以及 B點(diǎn)上各有 5只螞蟻。 t=9時(shí)刻，前 5只螞蟻又回到 A點(diǎn)，并且再次面對(duì)往左還是往右的選擇。 這時(shí)， AB上的軌跡數(shù)是 20而 AC上是 15，因此將有較為多數(shù)的螞蟻選擇往左，從而增強(qiáng)了該路線上的信息素。 隨著該過(guò)程的繼續(xù)，兩條道路上的信息素的差距將越來(lái)越大，直至絕大多數(shù)螞蟻都選擇了最短的路線。 正是由于一條道路要比另一條道路短，因此，在相同的時(shí)間區(qū)間內(nèi)，短的路線有更多的機(jī)會(huì)被選擇。 2021/6/15 89 蟻群算法是一種隨機(jī)搜索算法，與其他模型進(jìn)化算法一樣，通過(guò)候選解組成的群體的進(jìn)化來(lái)尋求最優(yōu)解。 該過(guò)程包括兩個(gè)階段：適應(yīng)階段和協(xié)作階段。 在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)； 在協(xié)作階段，候選解之間通過(guò)信息交流，以期產(chǎn)生性能更好的解。 作為與遺傳算法同屬一類的通用型隨機(jī)優(yōu)化算法，蟻群算法不需要任何先驗(yàn)知識(shí)，最初只是隨機(jī)地選擇搜索路徑，隨著對(duì)解空間的“了解”，搜索變得更有規(guī)律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。 2021/6/15 90 蟻群算法對(duì)搜索空間的“了解”機(jī)制 （ 1）、螞蟻的記憶。 一只螞蟻搜索過(guò)的路徑在下次搜索時(shí)就不會(huì)再被選擇，由此在蟻群算法中建立禁忌列表來(lái)進(jìn)行模擬。 （ 2）、螞蟻利用信息素進(jìn)行相互通信。 螞蟻在所選擇的路徑上會(huì)釋放一種叫信息素的物質(zhì)，當(dāng)同伴進(jìn)行路徑選擇時(shí)，會(huì)根據(jù)路徑上的信息素進(jìn)行選擇，這樣信息素就成為螞蟻之間通信的媒介。 2021/6/15 91 （ 3）、螞蟻的集群活動(dòng)。 通過(guò)一只螞蟻的運(yùn)動(dòng)很難到達(dá)食物源，但整個(gè)蟻群進(jìn)行搜索就完全不同。 當(dāng)某些路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，在路徑上留下的信息素?cái)?shù)量也越來(lái)越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度。而某些路徑上通過(guò)的螞蟻較少時(shí)，路徑上的信息素就會(huì)隨時(shí)間的推移而蒸發(fā)。 模擬這種現(xiàn)象即可利用群體智能建立路徑選擇機(jī)制，使蟻群算法的搜索向最優(yōu)解推進(jìn)。 蟻群算法所利用的搜索機(jī)制呈現(xiàn)出一種自催化或正反饋的特征，可將蟻群算法模型理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)。 2021/6/15 92 旅行商問(wèn)題 旅行商問(wèn)題即 TSP問(wèn)題 (Traveling Salesman Problem) 指給定 n座城市和兩兩城市之間的距離，要求確定一條經(jīng)過(guò)各個(gè)城市當(dāng)且僅當(dāng)一次的最短路線。 其圖論描述為： 給定圖 G=(V,A)，其中 V為頂點(diǎn)集， A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的連接距離，要求確定一條長(zhǎng)度最短的Hamilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短回路。 2021/6/15 93 蟻群算法應(yīng)用于旅行商問(wèn)題的基本算法 （ 1）它根據(jù)以城市距離和連接邊上的信息素軌跡強(qiáng)度的數(shù)量為變量的概率函數(shù)選擇下一個(gè)城市。 （ 2）規(guī)定螞蟻?zhàn)吆戏肪€，除非周游完成，不允許轉(zhuǎn)到已訪問(wèn)的城市，由禁忌表控制（設(shè) tabuk表示第 k只螞蟻的禁忌表， tabuk(s)表示禁忌表中的第 s個(gè)元素。） （ 3）它完成周游后，螞蟻在它每一條訪問(wèn)的邊上留下信息素。 每只螞蟻所具有的特征 2021/6/15 94 bi(t) (i=1,2,?,n)： 在 t時(shí)刻城市 i的螞蟻數(shù) ???nii tbm1)(算法中的基本符號(hào) ： 全部螞蟻數(shù) dij： 兩城市之間的距離 ?ij ： 路徑 (i， j)上的能見度，反映城市 i到城市 j的啟發(fā)程度， 一般取 =1/dij ?ij(t) ： t時(shí)刻路徑 (i,j)上的 信息素軌跡強(qiáng)度 初始時(shí)刻，各條路徑上的信息量相等，設(shè) ?ij(0)＝ C。 n： 城市數(shù)目 2021/6/15 95 螞蟻 k (k=1,2,?,m)在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上積累的 信息素軌跡強(qiáng)度 和啟發(fā)式信息決定轉(zhuǎn)移方向。 表示在 t時(shí)刻螞蟻 k由位置 i轉(zhuǎn)移到位置 j的概率，也就是其選擇策略。 )(tp kij? ?? ? ? ?? ? ? ???????????? ??o t h e r w i s ea l l o w e djtttttpka l l ow e dsisisijijkijk0????????allowedk={0,1,?,n1}tabuk： 表示螞蟻 k下一步允許選擇的城市。 2021/6/15 96 tabuk(k=1,2,?,m)：與實(shí)際蟻群不同，人工蟻群系統(tǒng)具有記憶功能，用 tabuk記錄螞蟻 k當(dāng)前所走過(guò)的城市，集合 tabuk隨著進(jìn)化過(guò)程做動(dòng)態(tài)調(diào)整。當(dāng)所有 n座城市都加入到 tabuk中時(shí)，螞蟻k便完成了一次循環(huán)，此時(shí)螞蟻 k所走過(guò)的路徑就是問(wèn)題的一個(gè)解。之后，禁忌表被清空，該螞蟻又可以自由選擇，開始下一個(gè)循環(huán)。 ?和 ? ： ?表示信息素強(qiáng)度的相對(duì)重要性， ?表示能見度的相對(duì)重要性。 分別反映了螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性： 如果 ? =0，則是傳統(tǒng)的貪心算法，如果 ? =0，則是純粹的正反饋的啟發(fā)式算法。 2021/6/15 97 經(jīng)過(guò) n個(gè)時(shí)刻 (n即為城市數(shù)目 )，螞蟻完成一次循環(huán)，各路徑上的信息量要根據(jù)以下公式做調(diào)整： 1( 1 ) ( )ij ij ijmkij ijktt? ? ? ????? ? ? ? ?? ? ??kij?? ： 第 k只螞蟻在本次循環(huán)中留在路徑 ij上的信息量 ij??： 本次循環(huán)中路徑 ij上的信息量增量 ?： 表示軌跡的持久性， (1－ ?)稱為信息的揮發(fā)系數(shù)，表示信息消逝程度，隨時(shí)間推移，以前留下的信息逐漸消失。通常設(shè)置系數(shù) 0?1來(lái)避免路徑上信息素的無(wú)限累加。 2021/6/15 98 為常數(shù)長(zhǎng)度只螞蟻環(huán)游一周的路徑表示第否則只螞蟻在本次循環(huán)經(jīng)過(guò)若第QkLijkLQkkkij???????0?信息素修改 antcycle algorithm（蟻環(huán)算法） 蟻環(huán)算法利用的是整體信息，在求解 TSP問(wèn)題時(shí)，性能較好。 該算法的特點(diǎn)是行走的路徑越短，對(duì)應(yīng)保存的信息素的值就越大。 2021/6/15 99 ????? ???否則之間經(jīng)過(guò)和只螞蟻在時(shí)刻若第01 ijttkdQijkij?antquantity algorithm（蟻量算法） ??? ???否則之間經(jīng)過(guò)和只螞蟻在時(shí)刻若第01 ijttkQ