【文章內(nèi)容簡(jiǎn)介】 之間的路徑上殘留的信息量。來(lái)模擬實(shí)際螞蟻的信息素濃度。 在初始化的時(shí)候， m 個(gè)螞蟻被放置在不同的城市上，賦予每條邊上的信息量為 ij? （ 0） 。每個(gè)螞蟻 k 的 ktabu 的第一個(gè)元素賦值為它所在的城市。 用 )(tpkij 表示在￡時(shí)刻螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j 的概率，則 )(tpkij =?o th e r w is ea llo w e djtttt ka llo w e dr ijijijijk ,0,)()( )()( ??????????? （ 1） 其中 kallowed 表示螞蟻 k 下一步允許走過(guò)的城市的集合，它隨螞蟻 k 的行進(jìn)過(guò)程而動(dòng)態(tài)改變；信息量 )(tij?? 隨時(shí)間的推移會(huì)逐步衰減，用 1? 表示 ??, 分別 表示螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息量及 啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用 , )(tij? 為由城市 i 轉(zhuǎn)移到城市 j 的期望程度 可根據(jù)某種啟發(fā)算法而定。 經(jīng)過(guò) n 個(gè)時(shí)刻。螞蟻 k 走完所有的城市，完成一次循環(huán)。此時(shí)，要根據(jù)下式對(duì)各路徑上的信息量作更新： ijijij tnt ???? ???? )(.)( （ 2） 6 其中： ij?? =???mkkij1 ? （ 3） kij?? 表示螞蟻 k 在本次循環(huán)中在城市 i 和城市 j 之間留下的信息量，其計(jì)算方法根據(jù)計(jì)算模型而定，在最常用的 ant cycle system 模型中 ； kij?? =?????o t h e r w i s ejkLQ k,0i, 和城市在本次循環(huán)中經(jīng)過(guò)城市若螞蟻 (4) 其中 Q 為常數(shù) , kL 為螞 k 在本次循環(huán)中所走路徑的長(zhǎng)度 。 粒子群算法 粒子群算法，也稱(chēng) 粒子群優(yōu)化算法 （ Particle Swarm Optimization），縮寫(xiě)為 PSO， 是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法（ Evolu2tionary Algorithm EA）。 PSO 算法屬于進(jìn)化算法的一種，和 遺傳算法 相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的 “交叉 ”(Crossover) 和 “變異 ”(Mutation) 操作，它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。 設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知 道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周?chē)鷧^(qū)域。 PSO 從這種 模型 中得到啟示并用于解決優(yōu)化問(wèn)題。 PSO 中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)。我們稱(chēng)之為“粒子”。所有的例子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值 (fitnessvalue)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。 PSO 初始化為一群隨機(jī)粒子 (隨機(jī)解 )。然后通疊代找到最優(yōu)解。在每一次疊代中，粒子通過(guò)跟蹤兩個(gè) 極值 來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值 。這個(gè)極值是全局極值 gBest。另外也可以不用整個(gè)種群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。在找到這兩個(gè)最優(yōu)值時(shí) ,粒子 7 根據(jù)如下的公式來(lái)更新自己的速度和新的 位置 v[]=w*v[] 1c *rand()*(pbest[]present[]) 2c *rand()*(gbest[]present[]) (a) present[]=persent[] v[] (b) v[]是粒子的速度 ,w是慣性權(quán)重 ,persent[]是當(dāng)前粒子的位置 .pbest[] 和 gbest[]如前定義 rand()是介于（ 0， 1）之間的隨機(jī)數(shù) . 1c , 2c 是學(xué)習(xí)因子 。 通常 1c = 2c =2，大多數(shù)情況 0≤ 1c = 2c ≤ 4 在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度 maxV ，如果某一維更新后的速度超過(guò)用戶(hù)設(shè)定的 maxV ，那么這一維的速度就被限定為maxV . 幾種智能算法特點(diǎn) 遺傳算法發(fā)展歷史長(zhǎng)，理論基礎(chǔ)完備，已經(jīng)在組合優(yōu)化領(lǐng)域取得巨大成功。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。具有自組織、自適應(yīng)和自學(xué)習(xí)性。但是，由于遺傳算法是基 于個(gè)體競(jìng)爭(zhēng)這樣一種機(jī)制，使得算法后期多樣性匾乏，降低算法效率。 蟻群算法魯棒性強(qiáng)，具有優(yōu)越的正反饋機(jī)制， 每個(gè)個(gè)體只能感知局部的信息，一不直接使用全局信息 。個(gè)體可改變環(huán)境、并通過(guò)環(huán)境來(lái)進(jìn)行間接通訊 。是一類(lèi)概率型的全局搜索方法，這種非確定性使算法能夠有更多的機(jī)會(huì)求得全局最優(yōu)解 。其優(yōu)化過(guò)程不依賴(lài)于優(yōu)化問(wèn)題本身的嚴(yán)格數(shù)學(xué)性質(zhì)，如連續(xù)性，可導(dǎo)性及目標(biāo)函數(shù)和約束函數(shù)的精確數(shù)學(xué)描述 。是一類(lèi)基于多主體的智能算法，各主體之間通過(guò)相互協(xié)作來(lái)更好地適應(yīng)環(huán)境 。具有潛在的并行性，其搜索過(guò)程不是從一點(diǎn)出發(fā)，而是從多個(gè)點(diǎn)同時(shí)過(guò)行，這種分布式多智能體的協(xié)作是異步并發(fā)進(jìn)行的，分布并行的模式將大大提高整個(gè)算法的運(yùn)行效率和快速反應(yīng)的能力。蟻群算法 在構(gòu)造解的過(guò)程中，隨機(jī)選擇策略增加了生成解的隨機(jī)性，接收了解在一定程度上的退化，使得搜索范圍在一段時(shí)間內(nèi)保持足夠大這樣影響了算法的收斂速度。 粒子群算法的基本思想是通過(guò)群體中個(gè)體之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解，它具有概念簡(jiǎn)單容易實(shí)現(xiàn)，搜索速度快，搜索范圍大的突出優(yōu)點(diǎn)，粒子群算法參數(shù)少，原理簡(jiǎn)單，易于編程實(shí)現(xiàn)最初是用來(lái)解決連續(xù)優(yōu)化問(wèn)題，一般采用實(shí) 8 數(shù)編碼。由于粒子群算法粒子間快速的信息交換，使得粒子群算法早期收斂速度較快，但是這種信息交換方式是建立在粒子都向最優(yōu)方向移動(dòng)機(jī)制的基礎(chǔ)上，使得粒子趨向同一化，所以到 尋優(yōu)后期算法容易陷入局部最優(yōu)。 小結(jié) 本章主要介紹了遺傳算法，蟻群算法幾種智能算法的基本理論和求解組合優(yōu)化問(wèn)題的的基本步驟和方法，總結(jié)了這幾種智能算法的優(yōu)缺點(diǎn)，為本課題在研究人工魚(yú)群算法求解組合優(yōu)化問(wèn)題提供參考。 3 基本人工魚(yú)群算法 人工魚(yú)群算法 (Artificial Fishschool Algofithm)是一種基于模擬魚(yú)群行為的優(yōu)化算法，在基本 AFSA 中，主要是利用了魚(yú)群的覓食、聚群和追尾行為，從構(gòu)造一條魚(yú)的底層行為做起，通過(guò)魚(yú)群中各個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來(lái)的目的。該算法 具有良好的克服局部極值、取得全局極值的能力。并且算法中只使用目標(biāo)函數(shù)的函數(shù)值，無(wú)需目標(biāo)函數(shù)的梯度值等特殊信息，對(duì)搜索空間具有一定的自適應(yīng)能力 .算法對(duì)初值無(wú)要求，對(duì)各參數(shù)的選擇也不很敏感。 動(dòng)物在進(jìn)化過(guò)程中，經(jīng)過(guò)漫長(zhǎng)的自然界的優(yōu)勝劣汰，形成了形形色色的覓食和生存方式，這些方式為人類(lèi)解決問(wèn)題的思路帶來(lái)了不少啟發(fā)和鼓舞。動(dòng)物一般不具備人類(lèi)所具有的復(fù)雜邏輯推理能力和綜合判斷能力的高級(jí)智能，它們的目的是在個(gè)體的簡(jiǎn)單行為或通過(guò)群體的簡(jiǎn)單行為而達(dá)到或突現(xiàn)出來(lái)的。 人工魚(yú)群算法模型 人工魚(yú)群算法是一種基于行為的人工智 能思想 ,通過(guò)魚(yú)在水里的行為方式模擬構(gòu)建了一種魚(yú)群模式 ,用來(lái)解決尋優(yōu)問(wèn)題 ,從而產(chǎn)生了一種新型的智能算法。 在一片水域中，魚(yú)生存的數(shù)目最