智能優(yōu)化算法及其應(yīng)用

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

關(guān)鍵詞:智能控制方法; 遺傳算法; 蟻群算法

中圖分類號:TP301文獻標(biāo)識碼: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

隨著人類生產(chǎn)發(fā)展需求的增加和人類的技術(shù)水平和知識水平的提高，控制科學(xué)也逐漸產(chǎn)生并發(fā)展起來，它從經(jīng)典控制理論，現(xiàn)代控制理論發(fā)展到智能控制理論。智能控制的概念和原理主要是針對被控對象、環(huán)境、控制目標(biāo)或任務(wù)的復(fù)雜性而提出的。

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

智能控制方法是從“仿人”的概念出發(fā)的，是一門跨學(xué)科、需要多學(xué)科提供基礎(chǔ)支持的技術(shù)科學(xué)。

1 遺傳算法

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

1.1 基本思想

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

1.2實現(xiàn)方法

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

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

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

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

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

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

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

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

2 蟻群算法

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

2.1 蟻群算法的基本原理

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

如圖2所示，螞蟻從蟻穴出來覓食時由于障礙物的存在，到達A點后只能沿A-B-C或A-D-C走。假設(shè)在t=0時刻有16只螞蟻從蟻穴出發(fā)外出尋食(設(shè)螞蟻在單位時間走過單位長度)，在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走，如此循環(huán)，最后所有的螞蟻都會選擇A-B-C路線。

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

2.2 蟻群算法模型與流程

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

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

(1)

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

其中，ρ表示殘留信息的持久程度，稱為信息量揮發(fā)系數(shù)。

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

算法流程如下:

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

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

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

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

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

6) 如果NC小于預(yù)定值且沒有穩(wěn)定解，則轉(zhuǎn)第(2)步，否則輸出最優(yōu)解。

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

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

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

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

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

參考文獻:

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

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

[3] 楊強， 吳中福. 一種新型支持向量機[J]. 重慶大學(xué)學(xué)報(自然科學(xué)版)，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] 張磊. 基于支持向量機的相關(guān)反饋圖像檢索算法[J]. 清華大學(xué)學(xué)報自然科版，2002 42(1):80-83.

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

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

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

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

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