【文章內(nèi)容簡(jiǎn)介】 的自組織性。自 組織性 增強(qiáng)了算法的魯棒性。 4)正反饋 從自然界中真實(shí)蟻群的覓食行為機(jī)制可以發(fā)現(xiàn) ，螞蟻之所以能夠 找到最優(yōu) 路徑，主要是由于 信息素不斷地在 較優(yōu) 路徑上 的 累積，而信息素的累 積 過(guò)程 就 是一個(gè)正反饋 過(guò)程。 基本 蟻群算法 的 反饋機(jī)制 是在較優(yōu) 路徑 上留下更多的信息素， 而 更多的信息素又 吸引 來(lái) 了更多的螞蟻，這個(gè)過(guò)程 引導(dǎo) 著 整個(gè)系統(tǒng)不斷向 最優(yōu)解的方向進(jìn)化。 以上從系統(tǒng)學(xué)方面分析了蟻群算法的機(jī)理，可見蟻群算法體現(xiàn)了 不同于常規(guī)算法的 許多 新思想，這也正是基本蟻群算法在系統(tǒng)學(xué)上 研究 的意義所在。 基本蟻群算法的具體實(shí)現(xiàn) 基本蟻群 算法的實(shí)現(xiàn)步驟 基本 蟻群 算法 的 具體實(shí)現(xiàn)步驟如下： （１ ） 令初始時(shí)刻 循環(huán)次數(shù) 0?Nc ，設(shè) 最大 循環(huán) 次數(shù) 為 Ncmax，將ｍ個(gè) 15 螞蟻 隨機(jī) 放在 ｎ個(gè)元素 節(jié)點(diǎn) 上 ，設(shè) 每 條路徑 （ｉ，ｊ）的初始化信息量?? Wtij ?? （ Ｗ為常數(shù) ） ，初始時(shí)刻 設(shè)置每條路徑上的信息素增量 ? ? 00 ???ij 。 （２）循環(huán)次數(shù) 1??NN cc 。 （３） 設(shè)初始時(shí)刻 螞蟻的禁忌表索引號(hào) k ＝１。 （４） 螞蟻數(shù)目 1??kk 。 （５）螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式（１） 選擇 下一個(gè) 元素ｊ， 然后 繼續(xù)往前 搜索 移動(dòng)， 此時(shí) ? ?ktabuCj ?? 。 （６） 選擇好下一個(gè)元素ｊ之后， 再 將螞蟻移動(dòng)到新的元素 節(jié)點(diǎn) ，并把該元素 轉(zhuǎn)移 到該螞蟻個(gè)體的禁忌表中，此時(shí) ， 1?? kk tabutabu 。 （７）如果 集合 C 中元素 還沒有 遍歷完，即ｋ＜ｍ，則跳轉(zhuǎn)到第（４）步，否則執(zhí)行 第（８）步。 （８）根據(jù)路徑上信息量更新公式（２）和 信息量變化公式（３）更新每條路徑（ｉ，ｊ）上的信息量。 （９）如果滿足結(jié)束條件，即 循環(huán)次數(shù) NN cc max?，則 本次 循環(huán)結(jié)束，輸出程序計(jì)算的最佳結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第（２）步。 基本蟻群算法的程序結(jié)構(gòu)流程 圖 基本蟻群算法的程序結(jié)構(gòu)流程 圖 如圖 。 16 開始 初始化 迭代次數(shù) Nc =Nc +1 螞蟻 k=1 螞蟻 k=k+1 按照狀態(tài)轉(zhuǎn)移概率公式（ 1）選擇下一個(gè)元素 修改禁忌表 ktabu = ktabu +1 k≥螞蟻總數(shù) m？ 按照公式（ 2）和公式（ 3）進(jìn)行信息素更新 滿足結(jié)束條件？ 輸出程序計(jì)算結(jié)果 結(jié)束 N N Y Y 圖 基 本蟻群算法的程序結(jié)構(gòu)流程圖 17 第三章 基于正交離散過(guò)程的蟻群算法 正交 試驗(yàn) 設(shè)計(jì) 正交試驗(yàn) 設(shè)計(jì)的基本概念 在 正交試驗(yàn)要解決的 實(shí)際 問(wèn)題 中，要明確 評(píng)價(jià) 試驗(yàn)效果的影響 指標(biāo)，影響試驗(yàn) 評(píng)價(jià) 指標(biāo)者稱為因素，因素在試驗(yàn)中變化的狀態(tài)稱為水平。對(duì)于單因 素或者兩因素試驗(yàn)，其因素?cái)?shù) 較少，試驗(yàn)的設(shè)計(jì)、安排 都比較簡(jiǎn)單 。 但 在 實(shí)際 生產(chǎn) 過(guò)程 中 要研究 許多 因素 多水平 對(duì)產(chǎn)品指標(biāo)的影響 。例如 因素?cái)?shù) 為 a, 因素的水平數(shù) 為 b, 則多因素全面 試驗(yàn)方案的次數(shù) m 為abm? 次 ,從試驗(yàn)次 數(shù)的公 式 可知 , 因素?cái)?shù) 和 水平 數(shù) 增多 , 試驗(yàn)次數(shù)將會(huì)大大增加 。例如有 5個(gè)因素，每個(gè)因 素有 4個(gè)水平，若 全面試驗(yàn)就要進(jìn)行102445 ? 次，這樣試驗(yàn) 規(guī)模 就會(huì)大大增加， 給研究 工作 帶來(lái)了繁重 的任務(wù) , 而且也 會(huì)消耗 大量 時(shí)間 、 原材料 和 財(cái)力 。 正交 試驗(yàn)設(shè)計(jì) 就是利用正交表來(lái)安排、 分析多因素 多水平 試驗(yàn)的一種設(shè)計(jì)方法。它是從 全面 試驗(yàn)的全部水平組合中，挑選 出 一 部分 代表性很強(qiáng) 的水平組合進(jìn)行試驗(yàn)，通過(guò) 分析 這部分 有 代表性 水平組合 的 試驗(yàn)結(jié)果 ，來(lái) 了解全面試驗(yàn)的情況， 減少試驗(yàn)次數(shù)， 從而找出最優(yōu) 水平組合。 正交試驗(yàn)設(shè)計(jì)的基本原理 在試驗(yàn)安排中， 當(dāng)因素水平數(shù)不多時(shí)，適合 進(jìn)行全面試驗(yàn)， 例 如，一個(gè)三因素三水平試驗(yàn)， 各因素 各 水平之間的全部 水平 組合就有 33=27種?？梢杂靡粋€(gè)立方體來(lái)表示 多 因素 試驗(yàn)的選優(yōu)區(qū)域 ， 對(duì)于 3因素 3水平 試驗(yàn) ， 18 就可以 選擇 有 27個(gè) 網(wǎng) 格點(diǎn) 的 立方體 作為選優(yōu)區(qū) ， 如果 這 27個(gè) 格點(diǎn)都 進(jìn)行試驗(yàn)，就是全面試驗(yàn)。全面試驗(yàn)的數(shù)據(jù) 試驗(yàn) 點(diǎn)分布如圖 — 1所示。 圖 — 1 全面試驗(yàn)的數(shù)據(jù) 試驗(yàn) 點(diǎn)分布 由圖可見： 全面試驗(yàn) 數(shù)據(jù)均勻分布 ， 各個(gè)因素水平全面搭配 ， 缺點(diǎn)就是試驗(yàn)次數(shù)太 多，如果是 5因素 4水平試驗(yàn)，全面試驗(yàn)的話就要進(jìn)行102445 ? 次試驗(yàn)，這會(huì)因?qū)嶒?yàn)條件 的 實(shí)際 限制而難于實(shí)施， 因此全面試驗(yàn)適用于因素水平數(shù)不多的情況下。 正交試驗(yàn)設(shè)計(jì)就是從全面試驗(yàn)點(diǎn)中挑選一 部分 具 有代表性的試驗(yàn)點(diǎn)來(lái)進(jìn)行試驗(yàn)。 對(duì)于 3因素 3水平而言，設(shè)有 A,B,C三個(gè)因素， A因素有 321 , AAA三個(gè)試驗(yàn)水平， B因素有 321 , BBB 三個(gè)試驗(yàn)水平， C因素有 321 , CCC 三個(gè)試驗(yàn)水平，利用正交表 ? ?493L 從 27個(gè)試驗(yàn)點(diǎn)中挑選出 9個(gè)試驗(yàn)點(diǎn)，這 9個(gè)試驗(yàn)點(diǎn)為： （ 1） 111 CBA ； （ 2） 221 CBA ； （ 3） 331 CBA 。（ 4） 212 CBA 。（ 5） 322 CBA 。（ 6） 132 CBA 。（ 7） 313 CBA 。（ 8） 123 CBA 。（ 9） 233 CBA 。這種 選擇保證了 A因素的 3個(gè)水平與 B、 C因素的 3個(gè)水平在試驗(yàn)過(guò)程中各搭配一次 ，對(duì)于 A、B、 C這 3個(gè)因素來(lái)說(shuō)，正交試驗(yàn)次數(shù) 僅 是全面試驗(yàn)次數(shù)的三分之一， 這樣就 大大減少了試驗(yàn) 次數(shù)。正交試驗(yàn)設(shè)計(jì)的數(shù)據(jù) 試驗(yàn) 點(diǎn)在立方體選優(yōu)區(qū)中 19 的分布如圖 — 2所示 : 圖 — 2 正交試驗(yàn)設(shè)計(jì)的數(shù)據(jù) 試驗(yàn) 點(diǎn)分布 從圖 — 2中可以看到， 9個(gè)試驗(yàn) 數(shù)據(jù)點(diǎn)在選優(yōu)區(qū)中 均衡 分布 ，在立方體的每個(gè)平面上 恰好只有 3個(gè)試驗(yàn)點(diǎn)， 在立方體的每條線上 恰 好只 有1個(gè)試驗(yàn)點(diǎn)。 所選的這 9個(gè)試驗(yàn)點(diǎn) 在整個(gè)立方體內(nèi)均衡分布， 代表性 很強(qiáng)，能夠全面 反映 整個(gè) 立方體 選優(yōu)區(qū)內(nèi)的基本情況。 因此它們能很 好地 代表27次全面試驗(yàn)的情況， 這就是正交 試驗(yàn) 設(shè)計(jì)的優(yōu)點(diǎn) 】【 4 。 正交表及其基本性質(zhì) 正交表是正交試驗(yàn)設(shè)計(jì)的基本工具，正交試驗(yàn)設(shè)計(jì)安排以及 分析試驗(yàn) 結(jié)果都要用到正交表 ， 合理選用 正交表 是 正 交設(shè)計(jì)的基礎(chǔ)。常用的正交表已經(jīng) 規(guī)范標(biāo)準(zhǔn)化，我們 根據(jù)試驗(yàn)需要從 參考書中選取合適的正交表。 正交表的記號(hào)為 ? ?bL am ，其中 L代表正交表， m 是試驗(yàn) 次數(shù) 即 正交表的行數(shù)， b表示 水平數(shù)， a 表示因素 數(shù) 即列數(shù) 。正交表的基本性質(zhì) 如下： 1）正交性 ：在正交表中任意一列中，某因素的所有水平都 出現(xiàn)，且出現(xiàn)的次 數(shù)是相等的，在任意兩列之間，兩因素的各種不同水平組合都出現(xiàn)，并且出現(xiàn)的次數(shù)也相等。 20 2） 均衡分布 性：在正交表中的各因素水平組合在選優(yōu)區(qū)中 均衡分布 。例如圖 — 2所示，在立方體中，每 一平面內(nèi)只 有 3個(gè) 數(shù)據(jù)試驗(yàn)點(diǎn)，每一條直線上只 包含 1個(gè) 試驗(yàn)點(diǎn)，正交 試驗(yàn) 點(diǎn)均衡 分布在全面試驗(yàn)點(diǎn)中 。 3）獨(dú)立性：正交表中沒有完全重 復(fù)的水平組合，從全面試驗(yàn)組合中挑出 的這一部分試驗(yàn)組合沒有 重復(fù)試驗(yàn) 的情況 ，在討論某一因素時(shí)，不用 考慮 其他因素的影響 ， 正交表中的試驗(yàn)方案能夠綜合處理大量 的 信息 。 4）整齊可比 性 ： 整齊可比是指各個(gè) 因素的各 個(gè) 水平 之 間具有可比性。正交表中某一因素的各個(gè)水平都均勻 搭配 著其他 因素的各個(gè)水平 。如在 3因素 3 水平試驗(yàn)中的 A、 B、 C3 個(gè)因素 ， A 因素的 3 個(gè)水平 A A A3各搭配 B、 C兩因素 的 3 個(gè)不同水平，即 ：（ 1） 111 CBA ；（ 2） 221 CBA ；（ 3） 331 CBA 。（ 4） 212 CBA 。（ 5） 322 CBA 。（ 6） 132 CBA 。（ 7） 313 CBA 。（ 8） 123 CBA 。（ 9）233 CBA 。 在這 9 個(gè)水平組合中， A因素 下的 3 個(gè)水平 分別 組合 了 B、 C兩因素的 3 個(gè)水平， 且任意兩個(gè)水平組合 不會(huì)有 重復(fù) 的情況 。 A因素 3 水平之 間具有 整齊 可比性。 同理 B、 C 兩 因素 的 3水平間也 具有整齊 可比性。 基于正交離散過(guò)程的蟻群算法 正交離散 過(guò)程 蟻群算法的基本原理 傳統(tǒng)基本 蟻群算法在實(shí)際應(yīng)用中主要是解決離散域的組合優(yōu)化問(wèn)題， 而難于解決連續(xù)域 變量 的函數(shù)優(yōu)化問(wèn)題，在原料配方設(shè)計(jì)等連續(xù)變量領(lǐng)域中 應(yīng) 用困難 。 然 而正交試驗(yàn)設(shè)計(jì) 可以綜合處理大量信息，有效 地解決連續(xù)域 變量 問(wèn)題。正交離散主要是將基本蟻群算法與正交 試驗(yàn) 設(shè)計(jì)相結(jié)合 ，通過(guò)正交設(shè)計(jì)形成正交離散點(diǎn)，使連續(xù)域問(wèn)題離散化， 讓螞蟻 21 在正交試驗(yàn)得出的幾條優(yōu)化路徑中尋找最優(yōu)解， 改進(jìn) 了初始階段蟻群算法信息素隨機(jī)分布、路徑雜亂無(wú)章的缺點(diǎn) ， 最終可以取得滿意的結(jié)果 。 以原料配 方設(shè)計(jì)為例 進(jìn)一步說(shuō)明正交離散過(guò)程的蟻群算法。設(shè)原料品種（ nRR~1 ）為橫坐標(biāo)，原料用量為 ? ?100~1?iXi ，原料品種所占的 比例 iX 從 0～ 100％ 連續(xù)均勻 變化，屬于典型的連續(xù)域變量問(wèn)題。 由于從 0～100％之間有無(wú)窮多個(gè)節(jié)點(diǎn)，若用基本蟻群算法， 那么 螞蟻將會(huì)從 start點(diǎn) 開始訪問(wèn)無(wú)窮多個(gè)節(jié)點(diǎn)，這樣必然會(huì)造成龐大的計(jì)算量而無(wú)限延長(zhǎng)計(jì)算時(shí)間，所求的結(jié)果也會(huì)比較分散，所以應(yīng)把問(wèn)題離散化。 在正交試驗(yàn)優(yōu)化中，以品種數(shù) 作為因素?cái)?shù)，每個(gè) 原料品種在 所占比例 范圍內(nèi)選定水平數(shù)。例如： 有四個(gè)原料品種，也就是有四個(gè)因素，每個(gè)品種有三個(gè)水平 ，也就是 4 因素 3 水平正交試驗(yàn)，則選用正交試驗(yàn)表? ?493L ，產(chǎn)生 12 個(gè)正交離散節(jié)點(diǎn)，組成 9 個(gè)初始配方組合，讓初始螞蟻在這 9個(gè)初始路徑 中釋放一定的 信息素，然后運(yùn)行螞蟻 更加趨向于 從 這 9個(gè)配方組合 中尋找適應(yīng) 解配方，最終確定最優(yōu)解，這樣就實(shí)現(xiàn)了把連續(xù)性問(wèn)題離散化處理了。 原料成分離散化及配方搜索圖如圖 ： 0 100％ 1R 2R 3R 4R nR 2A 各原料所占的質(zhì)量分?jǐn)?shù) 3B 1C 2D 1A 3A 1B 2B 2C 3C 1D 3D ? ?21,ar ? ?32,br ? ?13,cr ? ?24,dr 圖 原料正交離散及配方搜索圖 Start end 品種因素 iX 22 為了能夠有效運(yùn)用正交離散的蟻 群算法，要 把研究對(duì)象離散化成如圖 ， 這樣就大大縮小了搜索范圍，在很大程度上改善了尋優(yōu)性能，極大縮短了計(jì)算時(shí)間。首 先挑 選 四個(gè)原料品種作為四個(gè)因素，即品種 41 ~RR ，每個(gè)因素再選擇三個(gè)水平， 即因素 1R 有 321 , AAA 三個(gè)水平、因素 2R 有 321 , BBB 三個(gè)水平、因素 3R 有 321 , CCC 三