徐 梅，文士發(fā)，王福林，官 林

（東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱 150030）

遺傳算法求解約束優(yōu)化問(wèn)題時(shí)產(chǎn)生初始種群的改進(jìn)方法

徐 梅，文士發(fā)，王福林，官 林

（東北農(nóng)業(yè)大學(xué)工程學(xué)院，哈爾濱 150030）

研究提出初始內(nèi)點(diǎn)產(chǎn)生新方法，該方法根據(jù)約束優(yōu)化問(wèn)題的特點(diǎn)，構(gòu)造由約束條件構(gòu)成目標(biāo)函數(shù)，將求初始內(nèi)點(diǎn)問(wèn)題轉(zhuǎn)化為求解一系列無(wú)約束優(yōu)化問(wèn)題，通過(guò)求解這些無(wú)約束優(yōu)化問(wèn)題，實(shí)現(xiàn)初始內(nèi)點(diǎn)求解；研究初始種群其余個(gè)體產(chǎn)生的一種方法。結(jié)果表明，初始種群產(chǎn)生關(guān)鍵在于求得一個(gè)初始內(nèi)點(diǎn)，求得初始內(nèi)點(diǎn)后，其他個(gè)體的產(chǎn)生將占據(jù)較少時(shí)間。試驗(yàn)驗(yàn)證文章給出的初始種群產(chǎn)生方法快速可靠，可以克服有些約束優(yōu)化問(wèn)題初始種群難以產(chǎn)生問(wèn)題。

遺傳算法；初始內(nèi)點(diǎn)；初始種群；約束優(yōu)化問(wèn)題

遺傳算法（Genetic algorithms，GA），是由美國(guó)密歇根大學(xué)Holland創(chuàng)立[1]，思想基礎(chǔ)來(lái)源于群體遺傳學(xué)和生物進(jìn)化論，是基于基因遺傳學(xué)和自然選擇原理的一種群本尋優(yōu)算法。特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜非線性約束優(yōu)化問(wèn)題，被廣泛用于機(jī)器學(xué)習(xí)、組合優(yōu)化、系統(tǒng)工程、自適應(yīng)控制、人工智能、規(guī)劃設(shè)計(jì)、智能制造系統(tǒng)、智能機(jī)器系統(tǒng)、人工生命等領(lǐng)域[2-4]。與其他尋優(yōu)算法相比，遺傳算法具有以下特點(diǎn)：①遺傳算法是群體尋優(yōu)算法，搜索從許多點(diǎn)開(kāi)始，可防止搜索過(guò)程收斂于局部最優(yōu)解，提高求得全局最優(yōu)解的可能性；②遺傳算法通過(guò)適應(yīng)度函數(shù)實(shí)現(xiàn)優(yōu)秀種群選擇，避免其他推導(dǎo)和附屬信息，求解具有較好的魯棒性；③對(duì)尋優(yōu)函數(shù)無(wú)限制，既不要求函數(shù)連續(xù)，也不要求函數(shù)可微；可以是顯函數(shù)，也可以是隱函數(shù)（映射矩陣、神經(jīng)網(wǎng)絡(luò)），因而應(yīng)用廣泛；④遺傳算法是一種啟發(fā)式搜索法，既不是窮舉法，也不是完全隨機(jī)搜索，只要基因位置選擇恰當(dāng)，遺傳操作合理，搜索效率往往較高，僅需有限次計(jì)算，便可得到理想最優(yōu)解；⑤具有并行計(jì)算優(yōu)點(diǎn)，可用大規(guī)模并行計(jì)算大幅提高運(yùn)算速度；⑥特別適用于復(fù)雜大系統(tǒng)的優(yōu)化求解。

遺傳算法雖然具有諸多優(yōu)點(diǎn)，但在用于求解約束優(yōu)化問(wèn)題時(shí)，用產(chǎn)生隨機(jī)數(shù)方法得到足夠數(shù)量初始種群，有時(shí)相當(dāng)困難，需要幾十個(gè)小時(shí)甚至更長(zhǎng)時(shí)間才能產(chǎn)生。本文對(duì)此問(wèn)題進(jìn)行研究，提出初始種群產(chǎn)生的一種新方法。

1 用遺傳算法求解約束優(yōu)化問(wèn)題的方法概述

約束優(yōu)化問(wèn)題是一類廣泛存在于科學(xué)研究和工程應(yīng)用中的優(yōu)化問(wèn)題，一般約束優(yōu)化問(wèn)題可描述為：

式中，X=(x1,x2,…,xn)T是n維歐式空間En中的點(diǎn)(向量)，目標(biāo)函數(shù)f(X)和約束條件gj(X)，hk(X)均為X的實(shí)函數(shù)[5]。

求解約束優(yōu)化問(wèn)題主要的挑戰(zhàn)是如何有效平衡約束優(yōu)化可行解區(qū)域和不可行解區(qū)域之間的搜索，即設(shè)計(jì)一個(gè)有效的約束處理方法定位全局最佳的可行區(qū)域。針對(duì)處理不可行解這一問(wèn)題，在最近幾十年的進(jìn)化算法研究中，許多新思路被提出，如修復(fù)、懲罰函數(shù)等。其中修復(fù)是將不滿足約束條件的解進(jìn)行修復(fù)，使其成為滿足約束條件的解。

將遺傳算法應(yīng)用于求解約束優(yōu)化問(wèn)題時(shí)，需運(yùn)用變量替換等方法把等式約束替換，采用遺傳算法求解約束優(yōu)化問(wèn)題的數(shù)學(xué)模型可表示為：

目前，遺傳算法處理約束優(yōu)化問(wèn)題時(shí)，一般采用懲罰函數(shù)法、解碼器法、算子修正法和可行解搜索法[6]。懲罰函數(shù)法是約束優(yōu)化問(wèn)題中比較常用的方法，通過(guò)在適應(yīng)值函數(shù)上添加一個(gè)懲罰項(xiàng)，將原問(wèn)題變成一個(gè)無(wú)約束性質(zhì)問(wèn)題。懲罰函數(shù)法簡(jiǎn)單易行，但在實(shí)際操作中，懲罰因子較難。解碼器法不同于懲罰函數(shù)法，是通過(guò)特殊編碼方式避免產(chǎn)生不可行個(gè)體，此方法效率較高，并非所有約束問(wèn)題都能使用這種方法進(jìn)行求解。算子修正法通過(guò)設(shè)計(jì)專門的算子，以保證可行個(gè)體產(chǎn)生的個(gè)體仍是可行個(gè)體，這些遺傳算子對(duì)可行解空間封閉，算子修正法只能用于線性約束問(wèn)題，而不能用于非線性約束問(wèn)題。可行解搜索法對(duì)算子修正法進(jìn)一步改進(jìn)，適用于線性和非線性的約束優(yōu)化問(wèn)題。

在求解約束優(yōu)化問(wèn)題時(shí)，遺傳算法起始于一組隨機(jī)選擇的初始個(gè)體，對(duì)其進(jìn)行進(jìn)化操作，包括選擇、交叉、變異等。該算法的進(jìn)行主要依賴目標(biāo)函數(shù)（適應(yīng)度函數(shù)），優(yōu)秀個(gè)體將具有較高適應(yīng)度函數(shù)值，較差的個(gè)體將具有較低適應(yīng)度函數(shù)值。求解過(guò)程中需要評(píng)價(jià)的目標(biāo)函數(shù)和約束條件，而不需要其他更復(fù)雜信息。遺傳算法具有隨機(jī)性特點(diǎn)，使其能避免陷入局部最優(yōu)的優(yōu)勢(shì)。遺傳算法第一步是產(chǎn)生一組可行的解，將其作為初始種群。算法收斂速度、算法的性能受初始種群影響極大，因此初始種群確定尤為重要。

2 初始內(nèi)點(diǎn)的一種新求法

定義1：對(duì)于種群中的任意一個(gè)個(gè)體，若該個(gè)體滿足（2）式中的所有條件，則該個(gè)體稱為可行個(gè)體，若該個(gè)體不滿足所有約束條件，則該個(gè)體為非可行個(gè)體；

定義2：最初可行個(gè)體的全體稱為初始種群，初始種群中個(gè)體的數(shù)量稱為種群規(guī)模；

定義3：對(duì)于種群中的任意一個(gè)個(gè)體，若該個(gè)體滿足（3）式中的所有條件，則該個(gè)體稱為內(nèi)點(diǎn)。

初始種群方法是在內(nèi)點(diǎn)基礎(chǔ)上，采用對(duì)內(nèi)修正方法實(shí)現(xiàn)。初始種群的產(chǎn)生可分為兩種情況。第一種情況是可人為給出1個(gè)初始內(nèi)點(diǎn)；第2種情況是無(wú)法人為給出1個(gè)初始內(nèi)點(diǎn)。針對(duì)第2種情況，只要運(yùn)用合適的搜索方法，產(chǎn)生出1個(gè)內(nèi)點(diǎn)，則等同于第1種情況。因此整個(gè)過(guò)程的關(guān)鍵是初始內(nèi)點(diǎn)產(chǎn)生，具體步驟如下。先任取一點(diǎn)，如果其以嚴(yán)格不等式滿足所有約束，則就是要求初始內(nèi)點(diǎn)。若該點(diǎn)以嚴(yán)格不等式滿足一部分約束，而不能以嚴(yán)格不等式滿足另外約束，則以不能嚴(yán)格滿足的這些約束函數(shù)為假擬目標(biāo)函數(shù)，而以嚴(yán)格滿足那些約束函數(shù)形成障礙項(xiàng)，構(gòu)造1個(gè)無(wú)約束性質(zhì)的函數(shù)。求出上述函數(shù)在點(diǎn)的單位負(fù)梯度向量，在此方向上進(jìn)行搜索，得出函數(shù)值小于點(diǎn)的新點(diǎn)若仍不為內(nèi)點(diǎn)，就如上述方法，減小障礙因子，構(gòu)造出新的目標(biāo)函數(shù)繼續(xù)進(jìn)行搜索，直至求出的點(diǎn)嚴(yán)格滿足所有約束，成為初始內(nèi)點(diǎn)為止。

求初始內(nèi)點(diǎn)的迭代步驟如下：

②確定指標(biāo)集Tk和Tˉk

③檢查Tˉk是否為空集，若為空集，則取X(k)為初始內(nèi)點(diǎn)，迭代停止；否則，轉(zhuǎn)下步。

④構(gòu)造如下目標(biāo)函數(shù)

⑤求函數(shù)P(X,rk)在)處的單位負(fù)梯度方向

式中，λk為搜索步長(zhǎng)。

按上述步驟求得的點(diǎn)就是要求的初始內(nèi)點(diǎn)。

3 初始種群其余個(gè)體的產(chǎn)生方法

式中，ai是變量xi的下限，bi是變量xi的上限，ri為0～1的隨機(jī)數(shù)。

若X2滿足（10）式

則產(chǎn)生下一個(gè)個(gè)體X3，若不滿足，則

式中，α為收縮系數(shù)（0≤α＜1）。

當(dāng)α取值為0.5時(shí)，實(shí)際上就是取X1與X2的中點(diǎn)，如圖1所示。

圖1 X1與原X2和新X2之間的關(guān)系Fig.1 Relationship of X1,primary X2and new X2

若按（11）式收縮1次，X2還不是可行個(gè)體，則按（12）式將α減半，

再按（11）式繼續(xù)向X1收縮靠攏，直至使X2成為可行個(gè)體為止。

X2產(chǎn)生以后，再產(chǎn)生個(gè)體X3，采用與X2同樣處理方法，可使X3成為可行個(gè)體。仿照同樣方法，直至產(chǎn)生所有可行個(gè)體為止。

4 示例計(jì)算

為評(píng)價(jià)本文提出的初始種群產(chǎn)生方法的性能，選取兩個(gè)相當(dāng)復(fù)雜的測(cè)試函數(shù)進(jìn)行測(cè)試。電腦配置為i5內(nèi)核、1 GB內(nèi)存，以Matlab 7.1為編程平臺(tái)。用產(chǎn)生所有滿足約束條件的初始種群耗時(shí)多少作為評(píng)價(jià)標(biāo)準(zhǔn)，將本文提出方法的測(cè)試結(jié)果與常用隨機(jī)產(chǎn)生方法的測(cè)試結(jié)果進(jìn)行對(duì)比，測(cè)試函數(shù)及結(jié)果見(jiàn)下文。

在示例1中，變量x1～x8的上下限在模型中已經(jīng)給定，按照隨機(jī)產(chǎn)生的方法和本文提供的方法，在不同種群規(guī)模下，分別統(tǒng)計(jì)100次運(yùn)行的結(jié)果。當(dāng)產(chǎn)生滿足要求的初始種群時(shí)，隨機(jī)產(chǎn)生方法和本文提供的方法所用時(shí)間的平均值見(jiàn)表1。

表1 示例1中不同種群規(guī)模下初始種群產(chǎn)生時(shí)間比較Table 1 Comparison of creation time in different size of population in example 1

在示例2中，變量x1～x12下限為0，x10,x11,x12取值上限已確定。x1～x9取值上限定為800，按隨機(jī)產(chǎn)生方法和本文提供方法，在不同種群規(guī)模下，分別統(tǒng)計(jì)100次運(yùn)行結(jié)果（由于隨機(jī)方式比較慢，只統(tǒng)計(jì)5次）。當(dāng)產(chǎn)生滿足要求的初始種群時(shí)，隨機(jī)產(chǎn)生方法和本文提供的方法所用時(shí)間平均值見(jiàn)表2。

表2 示例2中不同種群規(guī)模下初始種群產(chǎn)生時(shí)間比較Table 2 Comparison of creation time in different size of population in example 2

從表1和2可以看出，本文給出的方法能夠加快初始種群的產(chǎn)生速度，并且隨著種群規(guī)模的增大，優(yōu)勢(shì)更加明顯。從示例2可以看出，對(duì)于約束比較復(fù)雜的問(wèn)題，用隨機(jī)的方法產(chǎn)生初始種群需要幾小時(shí)、十幾小時(shí)甚至更長(zhǎng)時(shí)間，嚴(yán)重影響遺傳算法效率，而采用本文方法則可提高遺傳算法求解復(fù)雜約束優(yōu)化問(wèn)題效率。

5 討論與結(jié)論

約束優(yōu)化問(wèn)題是工程領(lǐng)域最常見(jiàn)問(wèn)題，由于問(wèn)題復(fù)雜性，至今尚無(wú)確定性搜索算法求解。遺傳算法已成功求解約束優(yōu)化問(wèn)題。Bean等提出基于罰函數(shù)求解方法[9]，Man等提出基于修改算子求解方法[10]，劉大蓮等提出內(nèi)外交叉遺傳算法[11]，何家莉等用遺傳算法解決含有等式約束優(yōu)化問(wèn)題[12]。遺傳算法在求解約束優(yōu)化問(wèn)題時(shí)，關(guān)鍵是初始種群產(chǎn)生，為能在可行域內(nèi)產(chǎn)生初始種群，傳統(tǒng)遺傳算法采用隨機(jī)加篩選產(chǎn)生方法，使初始種群產(chǎn)生速度被限制，降低算法性能。王福林等提出隨機(jī)加修復(fù)產(chǎn)生方法[8]，使初始種群產(chǎn)生速度得到提高。但在求解約束條件較苛刻優(yōu)化問(wèn)題時(shí)，由于該方法第1個(gè)可行域內(nèi)點(diǎn)仍是采用隨機(jī)方式產(chǎn)生，導(dǎo)致初始種群產(chǎn)生時(shí)間偏長(zhǎng)。本文針對(duì)這一缺陷，提出改進(jìn)方法，將基于罰函數(shù)梯度下降法應(yīng)用到初始種群產(chǎn)生中，以約束條件構(gòu)造目標(biāo)函數(shù)為搜索對(duì)象，尋找第1個(gè)可行域內(nèi)點(diǎn)，保證第1個(gè)初始可行域內(nèi)點(diǎn)快速產(chǎn)生，加快初始種群產(chǎn)生速度，提高遺傳算法求解復(fù)雜約束優(yōu)化問(wèn)題效率。

[1]Holland J H.Adaptation in natural and artificial systems[M].USA: The University of Michigan Press,1975.

[2]朱劍英.智能系統(tǒng)非經(jīng)典數(shù)學(xué)方法[M].武漢:華中科技大學(xué)出版社,2001.

[3] 邵克勇,李鑫,邱躍峰,等.模仿二倍體繁殖的改進(jìn)遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2012,24(4):816-820.

[4]李菲,王福林,吳昌友.基于遺傳神經(jīng)網(wǎng)絡(luò)的農(nóng)村用電量需求預(yù)測(cè)[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2009,40(2):106-110.

[5]胡運(yùn)權(quán),郭耀煌.運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社, 2007:152-153.

[6]余文,李文厚.遺傳算法對(duì)約束優(yōu)化問(wèn)題的研究綜述[J].計(jì)算機(jī)科學(xué),2002(6):98-101.

[7]紀(jì)震,廖惠連,吳青華.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社,2009:105.

[8]王福林,吳昌友,楊輝.用遺傳算法求解約束優(yōu)化問(wèn)題時(shí)初始種群產(chǎn)生方法的探討[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2004,35(5): 608-611.

[9]Bean J C,Hadj-Alouane A.A dual genetic algorithm for bound?ed integer programs[J].Ann Arbor,1992,1001:48109-2117.

[10]Man K F,Tang K S,Kwong S.Genetie algorithms:Concepts and designs aves disquette[M].New York:Springer,1999.

[11]劉大蓮,徐尚文.求解約束優(yōu)化問(wèn)題的內(nèi)外交叉遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2012,32(1):190-195.

[12]何家莉,宣士斌.含有等式約束優(yōu)化問(wèn)題的遺傳算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(5):1253-1255.

Improved method on generation of initial population by using GA for solving constrained optimization problems

XU Mei,WEN Shifa,WANG Fulin, GUAN Lin(School of Engineering,NortheastAgricultural University,Harbin 150030,China)

Through the research we present a new method about initial interior point's generation, firstly constructed a constraint posed by the objective function,which is based on the characteristics of constrained optimization problems,and translate the problem of evaluating the initial interior point into solving the problem of solving a series of unconstrained optimization,by solving the unconstrained optimization problem,we achieve the solution of the initial interior point;Based on this,the research has given a method on the generation of the rest initial population individuals.The results showed that the key to generate the initial population was to obtain an initial point,the production of other individuals would take less time after the initial internal point was obtained.We verified by examples that the initial population generation method given by the paper was a fast and reliable method,and thus overcame the problem,which initial population was difficult to be produced in some constrained optimization problems.

genetic algorithms;initial interior point;initial population;constrained optimization problem

TP301.6

A

1005-9369（2014）07-0104-04

時(shí)間2014-7-4 17:18:39 [URL]http://www.cnki.net/kcms/detail/23.1391.S.20140707.0843.008.html

徐梅,文士發(fā),王福林,等.遺傳算法求解約束優(yōu)化問(wèn)題時(shí)產(chǎn)生初始種群的改進(jìn)方法[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2014,45(7):104-107.

Xu Mei,Wen Shifa,Wang Fulin,et al.Improved method on generation of initial population by using GA for solving constrained optimization problems[J].Journal of Northeast Agricultural University,2014,45(7):104-107.(in Chinese with English abstract)

2013-09-27

國(guó)家自然科學(xué)基金項(xiàng)目（31071331，1151z004）

徐梅（1957-），女，教授，碩士，博士生導(dǎo)師，研究方向?yàn)檗r(nóng)業(yè)系統(tǒng)工程。E-mail:xumei2009@163.com