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