燕樂(lè)緯，陳洋洋，周 云

(1.廣州大學(xué)土木工程學(xué)院,廣東 廣州 510006；2.廣州大學(xué)工程抗震研究中心,廣東 廣州 510006)

標(biāo)準(zhǔn)遺傳算法(Standard Genetic Algorithm，SGA)在工程應(yīng)用中有兩個(gè)瓶頸問(wèn)題[1-2]，一是控制參數(shù)過(guò)多，包括種群規(guī)模、位串長(zhǎng)度、選擇壓力、交叉概率、變異概率等。這些控制參數(shù)對(duì)遺傳算法的優(yōu)化效果意義重大，但它們的設(shè)定需要對(duì)遺傳算法和優(yōu)化問(wèn)題本身都有相當(dāng)水平的專業(yè)知識(shí)。二是與基于梯度的尋優(yōu)策略相比，作為一類隨機(jī)優(yōu)化方法，遺傳算法的收斂速度相對(duì)較慢[3-4]。究其原因，是因?yàn)檫z傳算法在遺傳進(jìn)化過(guò)程中僅使用了目標(biāo)函數(shù)值而未使用包含有更多優(yōu)化信息的連續(xù)、梯度等條件。基于以上兩個(gè)事實(shí)，SGA的應(yīng)用大多局限于設(shè)計(jì)空間非凸、離散、不連續(xù)，目標(biāo)函數(shù)與設(shè)計(jì)變量之間的關(guān)系不明確、多峰、不可導(dǎo)等傳統(tǒng)優(yōu)化方法難以求解的復(fù)雜問(wèn)題，且計(jì)算量十分龐大。

為提高遺傳算法的優(yōu)化效率，眾多研究者從宏觀策略和微觀策略的不同角度提出了很多改進(jìn)方法[5-7]。1989年，Krishnakumar[8]在SGA的基礎(chǔ)上提出了微種群遺傳算法(micro Genetic Algorithm，mGA)[9]。mGA的基本思想是盡可能地縮小遺傳算法的種群規(guī)模N，以提高遺傳算法的優(yōu)化效率。由于幾乎所有遺傳操作都與種群規(guī)模N有著直接的關(guān)系，減小種群規(guī)模顯然可以減少遺傳算法在編碼、選擇、交叉、計(jì)算個(gè)體的適應(yīng)度等遺傳操作中的計(jì)算開(kāi)銷。對(duì)于主要計(jì)算量集中在目標(biāo)函數(shù)值計(jì)算過(guò)程的復(fù)雜工程優(yōu)化問(wèn)題來(lái)說(shuō)，mGA減小種群規(guī)模的做法意義非同凡響。

由于mGA的種群規(guī)模極小，種群多樣性較差，很容易出現(xiàn)早熟收斂。mGA采用重啟動(dòng)策略來(lái)解決早熟收斂的問(wèn)題。此外，基于SGA中變異算子僅僅是以極小概率發(fā)生的輔助算子的思想，Krishnakumar在mGA中摒棄了變異算子。種群規(guī)模極小且不含變異算子，這是mGA區(qū)別于其他遺傳算法的兩個(gè)重要特征。

但是，這一mGA存在著一定的缺陷[10]。首先，mGA的每一次重啟動(dòng)，都僅僅保留了一個(gè)最優(yōu)個(gè)體而拋棄了遺傳優(yōu)化過(guò)程得到的模式識(shí)別和分析信息，這一做法顯然與遺傳算法的基本思想背道而馳。其次，從適應(yīng)度函數(shù)的一般特征來(lái)看，最優(yōu)個(gè)體的鄰域是需要重點(diǎn)搜索的區(qū)域。mGA取消了變異算子，實(shí)際上是剝奪了遺傳算法的局部搜索能力。

本文將在以往工作的基礎(chǔ)上[11-13]，對(duì)mGA進(jìn)行改進(jìn)?；镜乃悸肥菧p少重啟動(dòng)次數(shù)，增強(qiáng)兩次重啟動(dòng)之間遺傳優(yōu)化過(guò)程的全局和局部搜索能力，使算法在盡可能保有模式識(shí)別信息的前提下進(jìn)行智能搜索；加入自適應(yīng)變異算子，使之參與mGA的全局搜索和局部搜索，充分發(fā)揮算法的廣度和深度搜索能力。

1 宏觀策略

1.1 實(shí)數(shù)編碼

實(shí)數(shù)編碼的批評(píng)者認(rèn)為，實(shí)數(shù)編碼不具備基因的外在表現(xiàn)形式，在交叉和變異過(guò)程中未能體現(xiàn)基因交換和基因突變的細(xì)節(jié)特征，與遺傳算法建立在生物進(jìn)化論思想上這一基礎(chǔ)相背離。實(shí)數(shù)編碼的支持者對(duì)這這一點(diǎn)的解釋是：生物進(jìn)化論只是遺傳算法的思想基礎(chǔ)而非必須遵守的準(zhǔn)則；工程優(yōu)化問(wèn)題考慮的是優(yōu)化問(wèn)題本身，只要優(yōu)化問(wèn)題能夠得到求解，遺傳算法在形式上與生物進(jìn)化論有所背離是可以接受的[14]。

mGA種群中的個(gè)體只有5～10個(gè)，從生物學(xué)的角度來(lái)看，如此小的種群無(wú)法維持種群生存的基本要求。在進(jìn)行交叉運(yùn)算時(shí)，這一微小種群中所含的模式數(shù)目過(guò)少，模式識(shí)別和組合能力有限。因而在基因的重組和進(jìn)化方面，二進(jìn)制編碼并不比實(shí)數(shù)編碼更具優(yōu)勢(shì)。此外，Krishnakumar提出mGA的根本目的就在于提高遺傳算法的計(jì)算效率，避免過(guò)多的計(jì)算開(kāi)銷。二進(jìn)制編碼的頻繁編碼和解碼過(guò)程顯然與這一目的相悖?；谝陨蟽蓚€(gè)事實(shí)，可知mGA比SGA更有理由采用實(shí)數(shù)編碼。

1.2 漸進(jìn)階段和驟變階段

將進(jìn)化過(guò)程分為漸進(jìn)和突變兩個(gè)不同的階段，并采用自適應(yīng)的交叉算子和變異算子實(shí)現(xiàn)從突變階段到漸進(jìn)階段的逐漸轉(zhuǎn)化，是遺傳算法提高搜索效率的有效手段。

對(duì)于mGA來(lái)說(shuō)，由于采用了重啟動(dòng)策略，漸進(jìn)階段和驟變階段的含義與以往有所不同。從mGA的全局進(jìn)化過(guò)程來(lái)看，由于每一次重啟動(dòng)都只保留了一個(gè)最優(yōu)個(gè)體而拋棄了其余的所有進(jìn)化信息，進(jìn)化階段的劃分沒(méi)有實(shí)際意義。而兩次重啟動(dòng)之間則是一個(gè)完整進(jìn)化過(guò)程，本文提出的改進(jìn)mGA的漸進(jìn)階段和驟變階段，就是針對(duì)這一進(jìn)化過(guò)程而言的。

1.3 種群隔離機(jī)制

算法采用了被大量實(shí)踐證明能夠有效提高收斂速度、抑制早熟收斂的種群隔離機(jī)制。種群隔離機(jī)制實(shí)際上是一種人為干預(yù)遺傳優(yōu)化過(guò)程，增強(qiáng)遺傳算法的并行性的方法。對(duì)于種群規(guī)模極小的mGA來(lái)說(shuō)，種群隔離機(jī)制提高種群多樣性、防止早熟收斂的意義更加明顯。

2 微觀策略

2.1 相同個(gè)體的處理

由于mGA的種群規(guī)模很小，即使種群中只有一對(duì)相同個(gè)體，也會(huì)大大削弱種群的多樣性，所以絕對(duì)不允許出現(xiàn)相同個(gè)體。mGA的所有遺傳算子都帶有摒棄相同個(gè)體的設(shè)置，在進(jìn)行每一次遺傳操作時(shí)，都要根據(jù)新產(chǎn)生的個(gè)體與現(xiàn)有種群中個(gè)體的距離大小考慮是可以保留還是需要重新生成。這是mGA必不可少的步驟之一。

2.2 選擇算子

采用允許父代和子代相競(jìng)爭(zhēng)，聯(lián)賽規(guī)模為2的不放回錦標(biāo)賽選擇算子，選擇過(guò)程持續(xù)到種群內(nèi)的所有個(gè)體全部被選中或者淘汰為止。在這樣的選擇策略下，最優(yōu)個(gè)體總是能夠存活下來(lái)，從實(shí)際效果上實(shí)現(xiàn)了杰出者選擇策略。

2.3 交叉算子

(1)

式中τ1和τ2是在[-1,1]上均勻分布的隨機(jī)數(shù)。

2.4 變異算子

囿于SGA中變異算子是以很小概率發(fā)生的輔助算子這一思想，Krishnakumar提出的mGA中摒棄了變異算子。實(shí)際上，mGA的種群規(guī)模小，搜索能力有限，加入變異算子能夠在不增加循環(huán)次數(shù)的前提下，增加利用現(xiàn)有種群已經(jīng)獲得的遺傳信息進(jìn)行有效搜索的次數(shù)。此外，交叉算子全局搜索能力較強(qiáng)而局部搜索能力較弱，變異算子是交叉算子的有益補(bǔ)充。在本文所提出的改進(jìn)mGA中，將采用自適應(yīng)隨機(jī)變異算子，并令變異概率為100％，即所有個(gè)體全部執(zhí)行變異操作。

······

(2)

τb

(3)

(4)

式中T是當(dāng)前繁殖代數(shù)，bl和bu分別是取值半徑b的下界和上界。qm是這一非均勻變異算子引入的一個(gè)用于調(diào)整變異半徑b的收縮速度的參數(shù)，其取值范圍在1.1～2.0之間。

(4)式使這一變異算子具備了自適應(yīng)變焦的能力。隨著循環(huán)次數(shù)的增長(zhǎng)，變異半徑逐漸收縮。在優(yōu)化的漸進(jìn)階段，變異范圍較大，變異算子參與全局搜索，目的是快速鎖定最優(yōu)解所在區(qū)域；在優(yōu)化的驟變階段，變異范圍縮小，變異算子用于執(zhí)行局部精細(xì)搜索，目的是準(zhǔn)確地確定最優(yōu)解。式中設(shè)定變異下界bl的目的是防止驟變階段變異算子因變異范圍縮得太小而失去意義。

非均勻變異算子和算術(shù)交叉算子的自適應(yīng)特性使得遺傳進(jìn)化過(guò)程從漸進(jìn)階段逐漸轉(zhuǎn)換到了驟變階段，實(shí)現(xiàn)了遺傳算法全局搜索和局部搜索的協(xié)調(diào)與配合。

2.5 異種機(jī)制

異種機(jī)制是指在遺傳優(yōu)化過(guò)程中，以較小的概率在當(dāng)前種群的搜索范圍之外繼續(xù)選擇種子進(jìn)入循環(huán)進(jìn)程，增加種群多樣性的方法。異種機(jī)制模擬的是人工干預(yù)物種進(jìn)化，獲取最優(yōu)物種的過(guò)程。遺傳算法的過(guò)程性使這一干預(yù)得以實(shí)現(xiàn)。

異種機(jī)制的作用機(jī)理是：

1)對(duì)優(yōu)化過(guò)程進(jìn)行監(jiān)測(cè)，如果發(fā)現(xiàn)當(dāng)前種群發(fā)生了近親繁殖，則啟動(dòng)異種機(jī)制；

2)在當(dāng)前種群的搜索范圍之外選擇數(shù)個(gè)異種，用以代替現(xiàn)有種群中適應(yīng)度較低的個(gè)體；

3)用帶有異種的種群生成子代，進(jìn)入下一次循環(huán)。

由于mGA的種群規(guī)模較小，發(fā)生近親繁殖造成的后果更加嚴(yán)重，有必要嚴(yán)格控制相似個(gè)體的出現(xiàn)。在本文提出的改進(jìn)mGA中，近親繁殖判別式直接考慮任意兩個(gè)個(gè)體之間距離是否小于預(yù)先設(shè)定的臨界值dr，即

,

(5)

(5)式即本文提出的改進(jìn)mGA的近親繁殖判別式。其中臨界值dr按下式自適應(yīng)變焦：

(6)

式中Tr是從最近一次重啟動(dòng)開(kāi)始計(jì)數(shù)的繁殖代數(shù)。對(duì)于改進(jìn)的mGA來(lái)說(shuō)，兩次重啟動(dòng)之間是一個(gè)完整的遺傳算法循環(huán)，臨界值dr只有隨著Tr的變化自適應(yīng)變焦才有意義。

此外，在確定dr的上界dru和下界drl時(shí)，需要計(jì)算個(gè)體之間的“需要距離”dt。在本文提出的改進(jìn)mGA中，由于種群規(guī)模過(guò)小，采用計(jì)算初始種群個(gè)體之間平均距離的方法計(jì)算“需要距離”dt會(huì)產(chǎn)生較大的誤差。因此，需要在優(yōu)化開(kāi)始前先運(yùn)行一個(gè)專門(mén)計(jì)算dt的子程序。具體做法是在搜索空間中生產(chǎn)足夠多的個(gè)體，然后在其中隨機(jī)選擇N(種群規(guī)模)個(gè)個(gè)體計(jì)算平均距離，重復(fù)多次求其平均值，將這一平均值記做dt，再取dru=(1/4)dt即可。根據(jù)設(shè)計(jì)空間的大小和優(yōu)化問(wèn)題求解精度δL的不同，dr的下界drl的取值可以擴(kuò)大到20～30倍的δL，這樣就可以使種群在驟變階段加速收斂時(shí)還能保證一定的多樣性。

基于同樣的原因，本文提出的改進(jìn)mGA在選擇異種時(shí)僅采用隨機(jī)選取異種的方法。異種機(jī)制的最大取值半徑bh也是Tr的函數(shù)

(7)

實(shí)際應(yīng)用中，可以取bh的上界bhu=4dt，下界bhl為50～100倍的δL。

2.6 算法流程

在本章的最后，給出改進(jìn)的mGΑ流程如下：

1)用實(shí)數(shù)編碼對(duì)設(shè)計(jì)空間中的可行解編碼；

2)隨機(jī)生成8個(gè)個(gè)體的值作為初始種群；

3)分別計(jì)算這8個(gè)個(gè)體的適應(yīng)度，用不放回錦標(biāo)賽選擇選出4個(gè)適應(yīng)度較高的個(gè)體；

4)將這4個(gè)個(gè)體作為父代個(gè)體隨機(jī)配對(duì)，實(shí)施算術(shù)交叉，生成4個(gè)子代個(gè)體；

5)將算術(shù)交叉得到的4個(gè)子代個(gè)體和原有的4個(gè)父代個(gè)體合并，形成中間種群；

6)用不放回錦標(biāo)賽選擇在中間種群中選出4個(gè)適應(yīng)度較高的個(gè)體；

7)對(duì)這4個(gè)個(gè)體分別進(jìn)行變異操作，生成4個(gè)變異個(gè)體；

8)將這8個(gè)個(gè)體合并得到新一代種群；

9)判斷種群是否發(fā)生了近親繁殖，若是，則啟動(dòng)異種機(jī)制；

10)判斷是否滿足終止條件，若是，進(jìn)入第13)步，否則進(jìn)入第11)步；

11)判斷當(dāng)前種群是否基因型收斂，若是，進(jìn)入下一步，若否，轉(zhuǎn)3)；

12)啟動(dòng)重啟動(dòng)策略，采用不放回錦標(biāo)賽選擇在中間種群中選出4個(gè)適應(yīng)度較高的個(gè)體，再隨機(jī)產(chǎn)生4個(gè)個(gè)體，組成新的種群，并轉(zhuǎn)至3)；

13)將當(dāng)前種群中適應(yīng)度最大的個(gè)體作為改進(jìn)mGΑ得到的最優(yōu)解輸出，結(jié)束算法的循環(huán)過(guò)程。

3 性能測(cè)試

為驗(yàn)證本文所提出算法的有效性，采用標(biāo)準(zhǔn)測(cè)試函數(shù)Schaffer1 function(F6函數(shù))、Rana’s function(F9函數(shù))和Himmelbau’s function(F14函數(shù))進(jìn)行測(cè)試，并與帶有杰出者保留策略的SGA進(jìn)行了對(duì)比。所用SGA的種群規(guī)模N=100，交叉概率pc=0.8，變異概率pm=0.05，終止代數(shù)T=300。

Schaffer1 function(F6函數(shù))：

Rana’s function(F9函數(shù))：

Himmelbau’s function(F14函數(shù))

分別用SGA和本文所提改進(jìn)后的mGA對(duì)以上三個(gè)測(cè)試函數(shù)進(jìn)行了尋優(yōu)計(jì)算。運(yùn)行50次的對(duì)比測(cè)試結(jié)果如表1所示。表中“最優(yōu)值”是50次運(yùn)算得到的最優(yōu)結(jié)果；“平均值”是指50次優(yōu)化結(jié)果的平均；“運(yùn)算次數(shù)”算法收斂所需的平均適應(yīng)值計(jì)算次數(shù)。

從表中可以看出，改進(jìn)后的mGA可以用遠(yuǎn)低于SGA的運(yùn)算次數(shù)獲得比SGA更佳的優(yōu)化結(jié)果。對(duì)于工程優(yōu)化問(wèn)題來(lái)說(shuō)，主要的運(yùn)算開(kāi)銷集中于適應(yīng)值的計(jì)算上，因而減少適應(yīng)值的計(jì)算次數(shù)，往往意味著優(yōu)化時(shí)間的縮減和計(jì)算效率的提高。

表1 SGA和改進(jìn)后的mGA測(cè)試結(jié)果對(duì)比

需要指出的是，計(jì)算結(jié)果顯示，相比于SGA，改進(jìn)后的mGA對(duì)初始種群的平均適應(yīng)度較為敏感。以F6函數(shù)的優(yōu)化過(guò)程為例，mGA收斂時(shí)適應(yīng)值函數(shù)運(yùn)算次數(shù)的最小值僅為260次，最大值則達(dá)到30 122次，平均值為4 702.76。而SGA對(duì)應(yīng)的這3個(gè)值分別是5 900、29 900和18 576。這顯然是因?yàn)镾GA的種群規(guī)模大，并行性和魯棒性都較好造成的結(jié)果?？紤]到最終種群適應(yīng)值的改善和平均計(jì)算次數(shù)的顯著減小，總體而言，本文提出的改進(jìn)mGA仍然是值得采用的方法。

4 結(jié) 論

本文采用種群隔離機(jī)制、算術(shù)交叉、杰出者保留策略等對(duì)mGA進(jìn)行了改進(jìn)。減少了重啟動(dòng)次數(shù)，增強(qiáng)了兩次重啟動(dòng)之間遺傳優(yōu)化過(guò)程的全局和局部搜索能力，使算法在盡可能保有模式識(shí)別信息的前提下進(jìn)行智能搜索。加入了自適應(yīng)變異算子，使之參與mGA的全局搜索和局部搜索，充分發(fā)揮算法的廣度和深度搜索能力。引入了異種機(jī)制，加快了遺傳算法的收斂效率，提高了遺傳算法收斂于全局最優(yōu)解的概率。標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試結(jié)果表明，這一改進(jìn)的mGA能夠用遠(yuǎn)低于SGA的適應(yīng)值計(jì)算代價(jià)獲得更佳的優(yōu)化結(jié)果，具備較好的工程實(shí)用意義。

參考文獻(xiàn)：

[1]HOLLAND J H.Adaptation in naturaland artificial systems[M].Ann Arbor,Michigan: University of Michigan Press,1975.

[2]HOLLAND J H.Induction: processes of inference,learning,and discovery[M].Cambridge:MIT Press,1987.

[3]GOLDBERG D.E.Genetic algorithm in search,optimization and machine learning [M].MA:Addison-Wesley Publishing Company,1989.

[4]MARINSKIS Y,MARINSKIS,M.A hybrid genetic-particle swarm optimization algorithm for the vehicle routing problem [J].Expert Systems with Applications,2010,37(2): 1446-1455.

[5]AMIN J,MOHAMMAD A S,REZA T M.A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem [J].International Journal of Advanced Manufacturing Technology,2010,9:1-14.

[6]VAGELIS P,MANOLIS P.A hybrid particle swarm-gradient algorithm for global structural optimization [J].Computer-Aided Civil and Infrastructure Engineering,2011,26(1): 48-68.

[7]MOHAMED J A H,SIVAKUMAR R.A survey: hybrid evolutionary algorithms for cluster analysis[C].Artificial Intelligence Review,2011: 1-26.

[8]KRISHNAKUMAR K.Micro-genetic algorithm for stationary and non-stationary function optimization [M].SPIE Proceedings: Intelligent Control and Adaptive Systems,1989: 289-296.

[9]HAMZEH A,RAHMANI A.Approximating arbitrary reinforcement signal by learning classifier systems using micro genetic algorithm [J].Fundamenta Informaticae,2008,86(1/2): 93-111.

[10]ROY S,GHOSH S,SHIVPURI R.A new approach to optimal design of multi-stage metal forming processes with micro genetic algorithms [J].International Journal of Machine Tools and Manufacture,1997,37(1): 29-44.

[11]燕樂(lè)緯，陳樹(shù)輝.基于改進(jìn)遺傳算法的非線性方程組求解 [J].中山大學(xué)學(xué)報(bào):自然科學(xué)版，2011，50(1)：9-13.

[12]SU R K L,YAN L W.Provision of reinforcement in concrete solids using the generalized genetic algorithm [J].Journal of Computing in Civil Engineering,ASCE,2011，25(3)：211-217.

[13]燕樂(lè)緯，陳樹(shù)輝.一種改進(jìn)的廣義遺傳算法及其在結(jié)構(gòu)動(dòng)力優(yōu)化問(wèn)題中的應(yīng)用 [J].工程力學(xué)，2010，27(5)：21-26.

[14]王正志，薄濤.進(jìn)化計(jì)算 [M].長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2000.