【正文】 而且在Rankbased AS和精英策略 AS均優(yōu)于基本 AS的同時(shí)，前者還獲得了比精英策略 AS更好的解。 76 7/7這種 算法求解 TSP的能力與 AS、精英策略AS、遺傳算法和模擬退火算法進(jìn)行了比較。75 6/7另一種對(duì) AS改進(jìn)的算法是 Rankbased Version AS。該算法修改了 AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。73 4/7再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過的路徑再次被選擇的概率。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。 該系統(tǒng)的提出是以AntQ算法為基礎(chǔ)的。但是若選擇的精英過多則算法會(huì)由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。較早的一種改進(jìn)方法是精英策略 (Elitist Strategy)， 其思想是在算法開始后即對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為 Tgb(全局最優(yōu)行程 )，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過這些行程的螞蟻記為 “精英 ”，從而增大較好行程的選擇機(jī)會(huì)。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的 TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴(kuò)展時(shí)， AS的解題能力大幅度下降。71 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。這些 AS改進(jìn)版本的一個(gè)共同點(diǎn)就是 增強(qiáng)了螞蟻搜索過程中對(duì)最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。69第五章第五章 結(jié)束結(jié)束智能優(yōu)化方法智能優(yōu)化方法 信息系統(tǒng)與管理學(xué)院 70 蟻群優(yōu)化算法研究現(xiàn)狀 1/790年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（ Ant System, AS） 并將其應(yīng)用于解決優(yōu)化算法中經(jīng)典的旅行商問題（ TSP）。當(dāng)一只螞蟻遇到一個(gè)數(shù)據(jù)時(shí)即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時(shí)則將數(shù)據(jù)放置在該位置，繼續(xù)移動(dòng)。以分布的形式做少量的計(jì)算來刷新全局路由選擇信息。 用蟻群算法在分層圖模型的基礎(chǔ)上求解動(dòng)態(tài)RWA 問題。65 應(yīng)用 2/5 同時(shí) ,分布式的計(jì)算方式則克服了傳統(tǒng)集中式算法可擴(kuò)展性差的缺點(diǎn) ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。由于 RWA 問題是 NPC 問題 ,文獻(xiàn)中大多將 RWA 問題拆分成路由和波長(zhǎng)分配兩個(gè)子問題分別加以解決。64 應(yīng)用 1/5 光 網(wǎng)絡(luò)的智能管理 分布式 動(dòng)態(tài)選路及波長(zhǎng)分配 ( RWA , Routing and Wavelength Assignment ) 是指在實(shí)時(shí)業(yè)務(wù)情況下光通路的路由選擇和波長(zhǎng)分配的優(yōu)化問題,是實(shí)現(xiàn)自動(dòng)交換光網(wǎng)絡(luò) (ASON ,Automatically Switched Optical Network) 的關(guān)鍵技術(shù)之一。 以上 三種算法中 ，蟻周算法 效果最好，因?yàn)樗玫氖侨中畔?，而其余兩種算法用的是局部信息 。63 信息素的更改 6/6蟻 量算法 （ antquantity algorithm）的信息素 更新為 Q為常量， 表示 i到 j的距離，這樣信息濃度 會(huì)隨城市距離的減小而加大。實(shí)際上這種方式等價(jià)于蟻群離線方式中只有一只螞蟻。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進(jìn)行比較選擇最優(yōu)路徑。 Q為一個(gè)常數(shù)，該算法名為蟻周算法（ antcycle algorithm） ,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。更新公式為 第 s+1只螞蟻根據(jù) 重新計(jì)算路由表。其中， 為第 k1次循環(huán)后的的信息素的痕跡值。59 信息素的更改 2/6離線方式的信息素更新分為單螞蟻離線更新和蟻群離線更新。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。二、終止條件1 給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；2 當(dāng)前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；3 目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。 Dorigo在求解 TSP問題時(shí)，推薦參數(shù)的最佳設(shè)置為： 。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實(shí)現(xiàn)記憶功能。55 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 2/3 第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點(diǎn)。 54 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 1/3算法中需要記憶的信息有三部分。把 GBAS算法中步驟 3中的改為 ，若滿足此條件則替換當(dāng)前最好解為 ，對(duì) W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點(diǎn)。設(shè)第 s只螞蟻第 k步所走的路線為 ，表示螞蟻從 0點(diǎn)出發(fā)，順序到達(dá) 。52 解的表達(dá)形式與算法的實(shí)現(xiàn) 3/4 算法的實(shí)現(xiàn)建立有向圖 ，其中 A中共有 條弧。51 解的表達(dá)形式與算法的實(shí)現(xiàn) 2/4 算法的實(shí)現(xiàn)例： 01背包問題的解順序表達(dá)形式與算法實(shí)現(xiàn)。諸如車間作業(yè)及下料等問題，他們的共同特點(diǎn)是解以一個(gè)順序表示。而對(duì)于一般以順序作為解的優(yōu)化問題，