智能優化算法及其應用

摘要:該文對兩種主要智能控制方法作了總結和比較，分別闡述了遺傳算法和蟻群算法的基本原理、算法模型及流程。

關鍵詞:智能控制方法; 遺傳算法; 蟻群算法

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)14-3764-02

The Application of Intelligent Optimum Algorithms

MENG Xiao-chun

(Jinzhong University， Jinzhong 030600， China)

Abstract: In this article Genetic Algorithms， ant colony algorithm were summarized and compared. The elements， models and processes of two intelligent algorithms were introduced.

Key words: intelligent algorithms; Genetic Algorithms; ant colony algorithm

隨著人類生產發展需求的增加和人類的技術水平和知識水平的提高，控制科學也逐漸產生并發展起來，它從經典控制理論，現代控制理論發展到智能控制理論。智能控制的概念和原理主要是針對被控對象、環境、控制目標或任務的復雜性而提出的。

一般來說智能控制有以下特點:多輸入多輸出，被控對象非線性嚴重，沒有確定的數學模型，系統工作點變化劇烈，控制過程可以由微分/差分以及離散狀態序列來描述，復雜對象，復雜環境，復雜任務，被控對象與控制器不明顯分離[1]。

智能控制方法是從“仿人”的概念出發的，是一門跨學科、需要多學科提供基礎支持的技術科學。

1 遺傳算法

遺傳算法( Genetic Algorithms GA)是一類借鑒生物界自然選擇和自然遺傳機制的隨機的搜索算法，是由Holland 教授于1975 年提出。它簡單、通用、魯棒性強、適用于并行處理，對于以往難于解決的函數優化問題、復雜的多目標規劃問題、工農業生產中的配管、配線問題、以及機器學習、圖象識別、人工神經網絡控制和網絡構造、系統辨識、模糊控制、系統故障診、行走機器人路徑規劃等問題，尤其是自動控制，GA 為最有效的方法之一。

1.1 基本思想

遺傳算法的基本思想來源于達爾文(Darum)的進化論和門德爾(Mendel)的遺傳學說。達爾文的進化論認為:每一物種在不斷的發展過程中都是越來越適應環境;物種的每個個體的基本特征被后代所繼承，但后代又不完全同于自己的父代;在個體的生存與發展中那些更能適應環境的個體特征則能被保留下來，體現了適者生存的原理。與此相應，門德爾的遺傳學則認為:遺傳是作為一種指令遺傳碼封裝在每個細胞中，并以基因的形式包含在染色體中;每個基因有特殊的位置并控制某個特殊的性質，而由每個基因產生的個體對環境有一定的適應性;通過基因雜交和基因突變可能產生對環境適應性強的后代，并通過優勝劣汰的自然選擇，適應值高的基因結構則被保存下來。Holland 等人正是綜合了上述兩種學說的基本思想，創立了遺傳算法。該算法借助于計算機編程，一般是將待求問題表示成串(或染色體)，即為二進制碼或數碼串，從而構成一群串，并將它們置于問題的求解環境中，根據適者生存的原則，從中選擇出適應環境的串進行復制(reproduction) ，且通過交換(crossover)、變異(mutation) 兩種基因操作產生新的一代更適應環境的串群，經這樣一代代地不斷變化，最后收斂到一個最適應環境的串上，而求得問題的最優解。

1.2實現方法

GA 的求解為下列六步(流程見圖1)

1) 選擇編碼方式和編碼:GA在執行求解之前，首先要選擇合適的編碼方式，將待求解問題的所有參量編碼成一個定長的字符串，設串長為L。目前，常使用的編碼方式主要是二進制碼。

2) 產生初始種群:而經典遺傳算法是按隨機方法產生一組原始解，表示為N個初始字符串，每個字符串稱為一個個體，這N個個體就構成了一個群體。GA以這N個字符串作為初始點開始迭代計算，但這樣就可能導致初始種群在解空間分布的不均勻，從而影響算法的性能。要得到一個好的初始種群，可以將一些實驗設計方法，如均勻設計或正交設計與遺傳算法相結合，吳斌[2]指出初始種群的各個個體之間應保持一定的距離，并定義相同長度的以某一常數為基的兩個字符串中對應位不同的數量為兩者的廣義海明距離。要求入選種群的所有個體之間的廣義海明距離必須大于等于某個設定值。初始種解采取這種方式就能保證隨機產生的各個體間有較明顯的差別，使它們能較均勻的分布在解空間上保證初始種群含有較為豐富的模式，從而增加搜索收斂于全局最優解的可能。

3) 計算適應度函數值:適應度函數反映了個體對環境適應能力的強弱， 用來區分群體中個體好壞的標準，是自然選擇的唯一標準，選擇的好壞直接影響算法的優劣，引入適應值調節和資源共享策略可以加快收斂速度和跳出局部最優點。對適應值進行調節就是通過變換改變原適應值的比例關系，常用的比例關系有線性變換，乘冪變換和指數變換等。根據對它的計算值，可以很好地控制個體生存的機會，以體現適者生存的自然法則。一般來說，對于不同的問題，適應度函數的定義方式也不盡相同。

4) 選擇:選擇也稱復制或繁殖，是從舊種群中選擇優質個體，淘汰部分個體，產生新種群的過程。選擇不產生新的個體優質個體得到復制，使種群的平均適應度f得到提高。可見它模擬了生物界的“優勝劣汰”。選擇的方法有多種，無論哪種，都與適應度有關，且選擇的主要思想是個體的選擇概率正比于其適應度。常用的選擇方法有:輪盤賭法、期待值法、兩兩競爭法、保留最優個體法。

5) 交叉:交叉是將選擇后的種群個體放入交配池(mating pool)隨機地配對，稱之為父代。按照選定的交叉方式及確定的交叉概率，把成對個體的基因部分地交換，形成一對子代。可見交叉后，生成新的個體。交叉方法包括一點交叉、多點交叉、均勻交叉。

6) 變異:首先在群體中隨機地選擇一個個體，對于選中的個體以一定的概率隨機地改變字符串中某位上的字符的值。當采用二進制碼串時就是將選中位上的1 變為0 或0 變為1 。因變異發生的概率很低，故單靠其并不能使問題求解取得明顯進展，但它能確保產生能繼續進化的單一群體，因為新的個體產生提供機會。遺傳算法經歷上述6 個步驟并執行6至3 步的循環操作，求出問題的最優解。

總之，遺傳算法理論與技術研究主要是從遺傳操作、群體大小、參數控制、適應度評價以及并行實現技術等方面來提高遺傳算法的性能，而應用研究相對較薄弱，故今后開發遺傳算法的商業軟件、開拓更廣泛的遺傳算法應用領域是應用研究的主要任務。

2 蟻群算法

蟻群算法(ant colony algorithm， ACA)是一種通用仿生并行算法，是20世紀90年代由意大利學者M. Dorigo[4]等人首先提出來的一種新型模擬進化算法，可用來求解傳統方法難以解決的非凸、非線性非連續的優化問題。它通過模擬螞蟻群的行為來求解問題，本質上是一種基于群體的多代理算法。蟻群算法與其他模擬進化算法一樣，通過候選解組成的群體的進化過程來尋求最優解，包含兩個基本階段:適應階段和協作階段。在適應階段，各候選解根據積累的信息不斷調整自身結構;在協作階段，候選解之間通過信息交流，以期望產生性能更好的解。

2.1 蟻群算法的基本原理

螞蟻在走過的路上會釋放一種特殊的分泌物——信息激素(pheromone)，它能被一定范圍內其它螞蟻覺察到并影響他們的行為，當一條路上的信息激素逐漸增多時，后來的螞蟻選擇這條路徑的概率也逐漸增大，從而又增加了該路徑的信息激素強度，這種選擇過程是一種正反饋機制，螞蟻系統也稱為增強型學習系統。

如圖2所示，螞蟻從蟻穴出來覓食時由于障礙物的存在，到達A點后只能沿A-B-C或A-D-C走。假設在t=0時刻有16只螞蟻從蟻穴出發外出尋食(設螞蟻在單位時間走過單位長度)，在t=1時到達A點，因為此時A-B和A-D都沒有信息激素，所以螞蟻按等概率選擇，8只選擇A-B，8只選擇A-D，在t=4時，從A-B走的8只到達食物處，并開始返回。在t=5時，返回的螞蟻到達C，這時BC和CD上的信息素濃度都為8，螞蟻還等概率選擇，4只從B-C，4只從C-D，在t=8時，沿B-C走的4只螞蟻返回蟻穴重新外出，t=9時，又來到A，此時A-B的信息激素的濃度是16，而D-A的是12，所以將有較多的螞蟻選擇沿A-B走，如此循環，最后所有的螞蟻都會選擇A-B-C路線。

由此可見，蟻群算法主要有三種機制[3]。第一，選擇機制:信息素越多的路徑，被選中的概率越大;第二，信息素更新機制:路徑越短，信息素增加越快;第三，協作機制:個體之間通過信息素進行交流。

2.2 蟻群算法模型與流程

蟻群搜索食物的過程與旅行商問題(TSP)非常相似，人們用它也成功地解決了TSP問題。這里以TSP為例來說明蟻群算法的基本流程。

假設有n個城市，m個螞蟻，任兩城市r，s之間的距離為d(r，s)，用τ(r，s)來表示兩個城市間信息素的濃度，△τ(r，s)k表示第k只螞蟻經過支路(r，s)后釋放的信息濃度，Pk(r，s)表示第k個螞蟻的轉移概率:

(1)

其中，集合allowed 表示螞蟻k下一步應該選擇的城市，即以前未訪問過的城市。η(r，s)=1/d(r，s)，為邊弧(r，s)的能見度，α為信息素濃度的重要程度，β為能見度的相對重要程度(α≥0，β≥0)，信息素濃度按照下式更新:

其中，ρ表示殘留信息的持久程度，稱為信息量揮發系數。

Q為常數，Lk表示第k只螞蟻在本次循環中所走過的路徑的長度。這種模型是M.Dorigo[5]提出的三種模型之一，為ant cycle system，另外兩種是ant quantity system 和 ant density system，他們的區別在于螞蟻在經過的路徑上留的信息量的表達式不同。ant cycle system比其他兩種方式在求解TSP時性能好。

算法流程如下:

1) 初始化，設迭代次數為NC，初始化NC=0，τ(r，s)=A，△τ(r，s)=0，將m個螞蟻置于n個頂點上;

2) 將各個螞蟻初始位置至于當前的解集allowed中，然后對每個螞蟻k(k=1，2，…，m) 按照概率Pk轉移到下一個城市S，將S置于當前解集中，如此循環，直到所有的螞蟻訪問完所有的城市;

3) 計算每個螞蟻行走的總路徑Lk，并保存最優解;

4) 按信息濃度更新公式，更新各邊的信息濃度;

5) 各邊的△τ(r，s)初始化，NC=NC+1;

6) 如果NC小于預定值且沒有穩定解，則轉第(2)步，否則輸出最優解。

蟻群算法是近10年才提出的新型進化算法，在解決很多組合問題上都取得比較理想的效果。在靜態組合優化問題中的應用主要有TSP(旅行商問題)[6-7]、QAP(二次分配問題)、JSP(工作調度問題)[8]、GCP(圖著色問題)等 。它在動態組合優化問題中的應用主要是通信網絡路由問題[9]。在機器人智能規劃等領域中的應用研究已經相當廣泛，充分展示了其算法的優越性，實用性以及通用性[10]。在水資源的優化調度研究中，蟻群算法也得到了很好的應用，在水庫優化調度中，已由單庫優化調度擴展到了兩庫[11]。在大規模集成電路綜合布線問題的應用中，蟻群算法也取得了較好的效果，主要也是利用了蟻群算法的并行性。

蟻群算法的主要優點正反饋性、較強的魯棒性、并行性以及易與其他方法結合的特性使得他有很好的應用前景，但是作為一種新型的模擬進化優化算法，還未發展完善，存在如下一些問題。

1) 蟻群算法求解連續優化問題相對較弱。實際工程應用中存在著許多此類問題，如將蟻群算法應用于求解連續優化問題，將會擴展蟻群算法在其他研究領域的應用。

2) 由于蟻群算法起步較晚，同GA，SA等算法相比，還沒有系統的分析方法和堅實的數學基礎，具有完備的數學理論基礎將會使蟻群算法得到更廣泛的應用，同時也能為算法本身的改進與完善提供理論支持。

3) 基本蟻群算法易出現停滯現象，存在搜索時間長，全局搜索能力弱等缺點，所以針對算法本身的改進與完善仍將是以后蟻群算法在應用中的重要研究方向。

參考文獻:

[1] 孫施良. 模糊控制系統的Matlab仿真過程[J]. 機械與電子， 2005，01(12).

[2] 吳斌， 涂序彥. 快速遺傳算法研究[J]. 電子科技大學學報，1999，(1):49-53.

[3] 楊強， 吳中福. 一種新型支持向量機[J]. 重慶大學學報(自然科學版)，2005，10(2).

[4] M Dorigo， V Maniezzo， A Colorni. The ant system:optimization by acolony of cooperating agents[J]. IEEE Transactions on System，Man and Cybernetics Part B，1996，26(1):29-42.

[5] M Dorigo， L M Gambardella. A study of some properties of Ant-Q[A]. Proceedings of PPSN IV Fourth International Conference on Parallel Problem Solving From Nature[C] . Springer， Berlin，1996， 656-665.

[6] 張磊. 基于支持向量機的相關反饋圖像檢索算法[J]. 清華大學學報自然科版，2002 42(1):80-83.

[7] 吳高巍. 基于后驗概率的支持向量機[J]. 計算機研究與發展， 2005，08(02).

[8] 劉學軍， 陳松燦， 彭宏京.基于支持向量機的計算機鍵盤用戶身份驗真[J].計算機研究與發展，2002，39(9):1082-1086.

[9] 鹿衛國， 戴亞平. 適用于加權樣本集處理的加權支持向量機方法[J]. 北京理工大學學報， 2005，09(03).

[10] 張國宣. 基于核聚類方法的多層次支持向量機分類樹[J]. 計算機工程， 2005，05(10).

[11] 唐發明. 一種新的二叉樹多類支持向量機算法[J]. 計算機工程與應用， 2005，06(07).