遺傳算法的改進(jìn)與應(yīng)用

摘要：遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它與傳統(tǒng)的算法不同。大多數(shù)古典的優(yōu)化算法是基于一個單一的度量函數(shù)(評估函數(shù))的梯度或較高次統(tǒng)計，以產(chǎn)生一個確定性的試驗解序列；遺傳算法不依賴于梯度信息，而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解。該文針對傳統(tǒng)遺傳算法的缺陷，提出了一些新的改進(jìn)思路，即從搜索技術(shù)和遺傳算子等的角度來改進(jìn)遺傳算法。

關(guān)鍵詞：遺傳算法；自然遺傳機(jī)制；搜索；遺傳算子；改進(jìn)

中圖分類號：TP301.6文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2008)33-1461-02

Genetic Algorithm and Application

MA Si-hong

(Radio and TV University in Wuxi ，Wuxi 214011，China)

Abstract: The genetic algorithm is a kind of natural selection from biological and natural genetic mechanisms of random search algorithm， it is different from the traditional method. Most of the classical algorithm is based on a single measurement function (evaluation function) or the gradient times higher statistics， in order to produce a definitive solution test sequence; genetic algorithm does not rely on gradient information， but through the simulation of natural evolution To search for optimal solutions. In this paper， the shortcomings of traditional genetic algorithm， put forward some new ideas to improve， that is， from the search technology and genetic operators such as the point of view to improve the genetic algorithm.

Key words: genetic algorithms; natural genetic mechanisms; search; genetic operator; improve

遺傳算法(Genetic Algorithms，GA)是二十世紀(jì)七十年代開始興起的以自然選擇和遺傳理論為基礎(chǔ)，將是模擬生物進(jìn)化過程中，“適者生存，優(yōu)勝劣汰”規(guī)律而無需函數(shù)梯度信息的自適應(yīng)全局搜索算法，在模式識別、神經(jīng)網(wǎng)絡(luò)，控制系統(tǒng)優(yōu)化等方面得到了廣泛應(yīng)用。遺傳算法倍受各行設(shè)計者青睞之原因在于：這類隨機(jī)算法能夠同時處理N個設(shè)計變量，有利于實現(xiàn)并行操作，提高多變量優(yōu)化問題的計算效率。但是很多研究表明如果優(yōu)化參數(shù)配置不當(dāng)，遺傳算法可能會出現(xiàn)不收斂的情況。為使遺傳算法運(yùn)用于工程結(jié)構(gòu)優(yōu)化領(lǐng)域，諸多學(xué)者對遺傳算法做出不少改進(jìn) 。

1 遺傳算法的原理與一般流程

1.1 遺傳算法的原理

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它與傳統(tǒng)的算法不同。大多數(shù)

古典的優(yōu)化算法是基于一個單一的度量函數(shù)(評估函數(shù))的梯度或較高次統(tǒng)計，以產(chǎn)生一個確定性的試驗解序列；遺傳算法不依賴于梯度信息，而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解。遺傳算法一般包含三個基本操作，即選擇、交叉和變異，選擇體現(xiàn)了適者生存的自然法則，是通過把適應(yīng)值高的個體復(fù)制到下一代來改善群體的平均適應(yīng)值，它的目的是從群體中選出繁殖后代的雙親，避免基因缺失，提高全局收斂性和計算效率。交叉操作對于保證遺傳算法的尋優(yōu)過程能收斂到全局最優(yōu)點，以及提高對優(yōu)化過程的收斂速度起著重要的作用，常見的交叉操作主要有：單點交叉、多點交又 、均勻交叉等。變異操作是將個體染色體編碼串中的某些基因座上的基因值用該基因的其它等位基因來替換，形成一個新的個體，從遺傳運(yùn)算過程中產(chǎn)生新個體的能力方面來說，交叉運(yùn)算是產(chǎn)生新個體的主要方法，它決定了GA 的全局搜索能力，而變異運(yùn)算是產(chǎn)生新個體的輔助方法，但它也是必不可少的一個運(yùn)算步驟，決定了GA 的局部搜索能力，交叉算子與變異算子的相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使得CA 能夠以良好的搜索性能完或最優(yōu)化問題的尋優(yōu)過程。

1.2 遺傳算法的一般流程

對于基本的遺傳算法GA，可以定義成為一個8元組：

GA=(C，F(xiàn)，Po，M，Ps，Pc，Pm，T )

式中，C-個體的編碼方法，

F-個體的適應(yīng)度函數(shù)，

Po-初始種群，

M-群體大小，

Ps-選擇算子，

Pc-交叉算子，

Pm- 變異算子，

T-算法終止條件，一般終止進(jìn)化代數(shù)為100—500。

其中影響遺傳算法精度以及收斂速度的有選擇算子，交叉算子以及變異算子。由于遺傳算法的搜索基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，因此，適應(yīng)度函數(shù)的選擇對算法的實現(xiàn)至關(guān)重要。

遺傳算法的具體可以分為以下幾個步驟：1)隨機(jī)產(chǎn)生初始種群，個體數(shù)目一定，每個個體表示為染色體的基因編碼；2)計算個體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個體及其代表的最優(yōu)解，并結(jié)束計算；否則轉(zhuǎn)向第三步；3)依據(jù)適應(yīng)度選擇再生個體，適應(yīng)度高的個體被選中的概率高，適應(yīng)度低的個體可能被淘汰；4)按照一定的交叉概率和交叉方法，生成新的個體；5)按照一定的變異概率和變異方法，生成新的個體；6)有交叉和變異產(chǎn)生的新一代的種群，返回到第二步。

2 遺傳算法的改進(jìn)

目前對遺傳算法主要應(yīng)從以下三個方面著手改進(jìn)：① 控制參數(shù)的調(diào)整；② 遺傳算子的改進(jìn)；③ 與其它啟發(fā)式搜索技術(shù)結(jié)合構(gòu)成的基本遺傳算法的混合搜索算法。對控制參數(shù)調(diào)整的研究，筆者在以前論文中已經(jīng)述及，本文主要從后兩個角度的改進(jìn)這個角度來探討如何改進(jìn)遺傳算法。

2.1 搜索技術(shù)的改進(jìn)

眾所周知，遺傳算法是基于自然選擇和基因遺傳學(xué)原理的一種群體尋優(yōu)的搜索算法，它只要求被優(yōu)化的函數(shù)是可計算的，因而具有很強(qiáng)的全局搜索能力，可有效地防止搜索過程收斂于局部最優(yōu)解。但是GA的不足在于它的局部搜索能力弱，如果解空間很小的話，GA很難搜索到精確的最優(yōu)值。為了提高算法的搜索效率，有必要引入新的算法思想，其中復(fù)合形法就是一種很好的改進(jìn)措施。復(fù)合形法的基本思想與遺傳算法類似，也是同時從參數(shù)空間中隨機(jī)地取幾個點構(gòu)成復(fù)合形，并從這個復(fù)合形出發(fā)進(jìn)行搜索。具體地說，就是對空間中這些點計算出各自性能指標(biāo)值，去掉最壞的個體，并通過計算其它個體的中心點，以此對最壞點做一個映射，得到一個新的較好的個體。如此反復(fù)迭代，使復(fù)合形逐步向最優(yōu)點收縮，復(fù)合形法也存在收斂速度慢的問題，且若初始隨機(jī)數(shù)取得不好，使復(fù)合形的形狀不好時，還可能導(dǎo)致復(fù)合形不收斂。但是在一般情況下，復(fù)合形有相對確定的搜索方向，而這正是遺傳算法所欠缺的。基于以上想法，可以在遺傳算法中增加一個操作收縮，即把種群中各個體作為一個復(fù)合形的頂點，并根據(jù)各點的指標(biāo)函數(shù)值，產(chǎn)生新的較好點以取代最壞點，把整個種群向最優(yōu)解的方向收縮一次。有研究表明，改進(jìn)后的算法保持了原有的遺傳算法的優(yōu)點，同時引入了復(fù)合形法的搜索方向，使進(jìn)一步提高遺傳算法的收斂速度成為可能。

2.2 遺傳算子的改進(jìn)

在GA中引入一種成長算子，它不要求目標(biāo)函數(shù)連續(xù)、可導(dǎo)，能有效防止算法陷入偽極值點，加速GA的收斂，簡稱這種改進(jìn)的GA為GGA。其特點是：描述該點的部分或全部參數(shù)的二進(jìn)制編碼的最后幾位全是1或0，比如**1000000或**011111。以**100000為例，這時如最優(yōu)點為**011110，且待尋優(yōu)函數(shù)值關(guān)于最優(yōu)點對稱，那么，只有區(qū)間(**011111，**011101)中的個體優(yōu)于**100000，這些個體與**100000的歐幾里德距離最大為3，而它們與**100000的距離最小也為5，而變異概率為1/4，僅依靠基本的交叉，變異操作，要花很長時間尋到更優(yōu)個體。若將成長算子引入二進(jìn)制編碼GA中，能避免算法陷入偽極值點，同時能加強(qiáng)算法的方向性，加快算法的收斂。成長算子加在適應(yīng)度值計算之后及復(fù)制算子之前，該算子對每一代中適應(yīng)度值最大的前m個個體進(jìn)行成長操作。若每一代種群中有N個個體Bi(i=1，2，… ，N )，它們的適應(yīng)度值為fi(i=1，2，… ，N)，個體Bj由n個待尋優(yōu)參數(shù)的二進(jìn)制編碼6j(j=1，2，…，N)組成，成長操作的具體步驟如下：

1) i=1；

2) 取出種群中的適應(yīng)度值第i大的個體Bi；

3) j=1；

4) B=Bi(B為中間變量，其中相應(yīng)的幾個參數(shù)編碼為6

5) Bj=Bj+1，未溢出則判斷B的適應(yīng)度值f比fi大否，大則8)，否則6)；

6) B=Bi；

7) Bj=Bj-1，未溢出則判斷B的適應(yīng)度值f比fi大否，大則8)，否則9)；

8) Bi=B；

9) j=j+1，若j≤ n則4)，j> n則10)；

10) 將B放回種群中，i= i+1，若i≤ m則2)，i> m則11)；

11) 成長操作結(jié)束。

從上面步驟可看出，該成長算子可以實現(xiàn)歐幾里德距離較小而海明距離較大的兩點之間的跨越，使當(dāng)

前最優(yōu)個體向其所在單極值區(qū)域的極值點收斂一步，彌補(bǔ)了二進(jìn)制編碼GA的不足。

2.3 其他

上面所列出的各種改進(jìn)措施均是在標(biāo)準(zhǔn)GA的各步驟中進(jìn)行的。更進(jìn)一步地人們在遺傳算法中又添加了附加的算法和一些輔助功能，GA的理論得到了更進(jìn)一步的發(fā)展。同時還有更多的研究在進(jìn)行進(jìn)一步的探討。其中有研究在普通GA中加入了漂移算子，即以當(dāng)前最優(yōu)個體為研究對象，將染色體基因片段的后二分之一的基因分別按一定的概率做±1的隨機(jī)漂移，排位靠后的基因的漂移概率較大，排位靠前的基因漂移概率較小，由此產(chǎn)生一定數(shù)量的新個體，這種改變?nèi)旧w申的低位基因的取值的方法可以起到擴(kuò)大局部搜索能力的作用。有研究針對機(jī)組啟停問題的特點，設(shè)計了“可行性檢查”、“冗余檢查”、“邊界搜索”等附加功能，減少了GA求解過程中的無效操作，有效地提高了GA 的效率。還有人提出了多層遺傳算法的概念，即除了群體內(nèi)部各個體之間進(jìn)行遺傳操作外，在各個群體闊也進(jìn)行類似的遺傳操作(即群體的復(fù)制、交叉、變異)，以加強(qiáng)群體間的信息交換，改善尋優(yōu)能力。此外，遺傳算法本身是以激勵機(jī)制-適應(yīng)度函數(shù)為基礎(chǔ)，故對適應(yīng)度函數(shù)的改進(jìn)應(yīng)該是最基本的、最有效的改進(jìn)方式。

總之，通過計算機(jī)模擬來再現(xiàn)生命現(xiàn)象是正在興起的一個新的課題，人工生命研究的重要內(nèi)容之一就是進(jìn)化現(xiàn)象，而遺傳算法則是研究進(jìn)化現(xiàn)象的重要方法。各種算法對遺傳算法的改進(jìn)能夠有效地避免一般遺傳算法在計算過程中存在的問題，同時相對于一般遺傳算法，其收斂速度和效率都有了很大的提高。

參考文獻(xiàn)：

[1] 周明，孫樹棟．遺傳算法原理與應(yīng)用[M]．北京：國防工業(yè)出版社，1999：33-65．

[2] 劉利民，柴躍廷．分布式庫存系統(tǒng)優(yōu)化控制的一種改進(jìn)遺傳算法[J]．計算機(jī)集成制造系統(tǒng)-CIMS，2002，8(5)：399-403

[3] 李海民，吳成柯．基于BP網(wǎng)絡(luò)的遺傳算法[J]．模式識別與人工智能，1999，12(2)：223-228．

[4] 唐文艷，顧元憲．遺傳算法在結(jié)構(gòu)優(yōu)化中的研究進(jìn)展[J]．力學(xué)進(jìn)展，2002，32(1)：26-40．

[5] 張延年，劉斌，董錦坤，等．改進(jìn)遺傳算法在建筑結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J]．東北大學(xué)學(xué)報(自然科學(xué)版)，2004，25(7)：692-694．

[6] 謝楠．遺傳算法的改進(jìn)策略及其在橋梁抗震優(yōu)化設(shè)計中的應(yīng)用效果[J]．工程力學(xué)，2000，(3)：98-100.

[7] 高山．遺傳算法在機(jī)組啟停中的應(yīng)用及改進(jìn)[J]．東南大學(xué)學(xué)報，2000，(3)：21-22.

[8] 吳超仲．一種多層遺傳算法的提出及實現(xiàn)[J]．武漢交通科技大學(xué)學(xué)報，2000，(4)：354.