一種初始種群算法的應(yīng)用研究

姜彬峰

（吉林鐵道職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)系，吉林 132001）

0 引言

在日常生產(chǎn)實(shí)踐中，我們往往會(huì)遇到一些約束優(yōu)化問(wèn)題。為了更好地使用計(jì)算機(jī)求解這些問(wèn)題，人們普遍采用遺傳算法。遺傳算法（Genetic Algorithm,GA）是近幾年發(fā)展起來(lái)的一種嶄新的全局優(yōu)化算法。它是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，1962年霍蘭德(Holland)教授首次提出了GA算法的思想，1975年他發(fā)表《Adaptation in natural and artificial systems》的專(zhuān)著，如今發(fā)展成為標(biāo)準(zhǔn)形式的遺傳算法。

遺傳算法作為一種快捷、簡(jiǎn)便、容錯(cuò)性強(qiáng)的算法，在各類(lèi)結(jié)構(gòu)對(duì)象的優(yōu)化過(guò)程中顯示出明顯的優(yōu)勢(shì)。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點(diǎn)：

搜索過(guò)程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個(gè)體。此編碼操作， 使得遺傳算法可直接對(duì)結(jié)構(gòu)對(duì)象（集合、序列、矩陣、樹(shù)、圖、鏈和表）進(jìn)行操作。搜索過(guò)程是從一組解迭代到另一組解，采用同時(shí)處理群體中多個(gè)個(gè)體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。采用概率的變遷規(guī)則來(lái)指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。對(duì)搜索空間沒(méi)有任何特殊要求（如連通性、凸性等），只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其它輔助信息，適應(yīng)范圍很廣。廣泛應(yīng)用在函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問(wèn)題、自動(dòng)控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等領(lǐng)域。

遺傳算法的基本流程如圖1所示。

l）產(chǎn)生初始群體，隨機(jī)產(chǎn)生m個(gè)個(gè)體，每個(gè)個(gè)體看作是一個(gè)染色體，m個(gè)染色體組成一個(gè)群體；

2）對(duì)群體中每個(gè)個(gè)體計(jì)算相應(yīng)的適應(yīng)度值；

3）通過(guò)選擇和復(fù)制操作從群體中選出滿(mǎn)足條件的個(gè)體，并放入到交配緩沖池中；

4）對(duì)交配緩沖池中的個(gè)體使用交叉和變異算子形成下一代群體中的m個(gè)個(gè)體；

5）計(jì)算每個(gè)新個(gè)體的適應(yīng)度值；

6）如果滿(mǎn)足結(jié)束條件，則停止；否則轉(zhuǎn)到第3步。

圖1 標(biāo)準(zhǔn)遺傳算法流程圖

由圖1可見(jiàn)，初始群體是遺傳算法的第一步，初始種群的分布狀態(tài)不僅直接關(guān)系到遺傳算法的全局收斂性，還影響算法的搜索效率，所以對(duì)初始種群進(jìn)行科學(xué)合理設(shè)定是應(yīng)用遺傳算法進(jìn)行尋優(yōu)計(jì)算的一個(gè)重要問(wèn)題。

1 需求解的實(shí)際模型

在鐵路客運(yùn)領(lǐng)域，鐵路企業(yè)為實(shí)現(xiàn)客運(yùn)總收益最大化，在基于旅客需求預(yù)測(cè)的前提下可以建立以下一種多區(qū)間多票價(jià)的座位控制模型。

式中，AKT為FODF使用區(qū)間的矩陣，矩陣的列為一個(gè)FODF所包含的區(qū)間，akt為第t個(gè)FODF使用第k區(qū)間，否則akt＝0；

ck為第k個(gè)區(qū)間的列車(chē)的容量，C為全部ck組成的K維列向量；

st為第t個(gè)FODF的座位控制數(shù)，也就是決策變量，S為由全部st組成的t維列向量；

Rt為第t個(gè)FODF的收益。

該模型是一個(gè)隨機(jī)規(guī)劃模型，對(duì)于這種約束優(yōu)化問(wèn)題，可以使用遺傳算法進(jìn)行求解。

2 初始種群算法

對(duì)于該模型，如果使用產(chǎn)生隨機(jī)數(shù)的方法來(lái)得到足夠數(shù)量的初始種群，將大大增加算法的運(yùn)算時(shí)間，而且由于傳統(tǒng)GA的初始種群是隨機(jī)選取的，初始種群的覆蓋空間具有很大的不確定性，如果初始種群空間不包含全局最優(yōu)解的信息，而遺傳算子又不能在有限的進(jìn)化代數(shù)內(nèi)將覆蓋空間擴(kuò)延到全局最優(yōu)解所在的區(qū)域，那么過(guò)早收斂就不可避免的[6]。本文采用以下方法得到初始種群。

定義1：隨機(jī)產(chǎn)生一個(gè)個(gè)體，若該個(gè)體滿(mǎn)足約束條件，則該個(gè)體稱(chēng)為可行個(gè)體，若該個(gè)體不滿(mǎn)足約束條件，則稱(chēng)該個(gè)體為非可行個(gè)體[1]；

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

設(shè)ai和bi分別為決策變量xi的取值上限和下限，Xi為第i個(gè)初始個(gè)體：

式中：Xip為第i個(gè)個(gè)體第p個(gè)分量的初始值，p＝ 1, 2, ,n。

若令rip為與第i個(gè)初始個(gè)體第p個(gè)分量相對(duì)應(yīng)的在[0, 1]區(qū)間內(nèi)服從均勻分布的隨機(jī)數(shù)，X1為一個(gè)已知初始可行個(gè)體，它滿(mǎn)足規(guī)劃模型中的約束條件。

初始種群規(guī)模為m，于是可按下式隨機(jī)產(chǎn)生一個(gè)初始個(gè)體X2：

其中：檢驗(yàn)新生成的X2是否滿(mǎn)足約束條件，若滿(mǎn)足則生成新的初始個(gè)體X3，若不滿(mǎn)足則重復(fù)執(zhí)行式（2）直至X2成為可行個(gè)體。

式中 為收縮系數(shù)，0≤ ＜1，一般可取0.5。

設(shè)x1p為X1的第p個(gè)分量，x2p為X2的第p個(gè)分量，其中p＝1, 2, ,n，為X2的第p個(gè)分量經(jīng)過(guò)式（2）第k次迭代（即重復(fù)執(zhí)行式（2）k次）后的值，則有

又因?yàn)?/p>

將式（4）代入式（5）中可得

設(shè)

將式（6）代入式（3）中可得

由數(shù)學(xué)歸納法可知對(duì)于k＝1, 2, ，式（7）恒成立。

因?yàn)?≤ ＜1，當(dāng)x2p≠x1p時(shí)，下述兩式成立。

式（8）說(shuō)明，當(dāng)式（2）重復(fù)執(zhí)行時(shí)，將使X2中的各分量的值不斷地向X1中對(duì)應(yīng)的各分量的值靠近。

式（9）說(shuō)明，當(dāng)式（2）重復(fù)執(zhí)行時(shí)，將使X2中的各分量的值不斷地向X1中對(duì)應(yīng)的各分量的值無(wú)限地靠近。在一定的精度要求下，當(dāng)與x1p的差距在精度要求的范圍內(nèi)時(shí)，可以令＝x1p。

若x2p＝x1p，當(dāng)式（2）重復(fù)執(zhí)行時(shí)，由式（7）可知，將始終等于x1p。

綜上所述，若新生成的X2仍不滿(mǎn)足約束條件，則對(duì)其重復(fù)執(zhí)行式（2），使X2中的各分量的值不斷地向X1中對(duì)應(yīng)的各分量的值靠近。在一定精度要求下，可以經(jīng)過(guò)有限次迭代，最終使X2中的各分量的值等于X1中對(duì)應(yīng)的各分量的值。

通過(guò)上述算法，在X2向X1靠攏的過(guò)程中，X2有可能成為X1以外的其他可行個(gè)體，也有可能最終成為X1。當(dāng)X2成為X1時(shí)，為了保證初始種群個(gè)體的多樣性，可以按（1）再重新生成 ，再用式（2）重新迭代。

事實(shí)上，如果取 ＝0.5，我們可以認(rèn)為用式（2）進(jìn)行一次迭代后的新X2是X1與原X2連線(xiàn)的中點(diǎn)，如圖2所示。

X2產(chǎn)生后，再產(chǎn)生X3，采用與X2同樣的方法進(jìn)行處理，最終能夠產(chǎn)生m個(gè)初始可行個(gè)體。

對(duì)于本文的多區(qū)間座位控制模型，每個(gè)決策變量的取值范圍均可以設(shè)定為[0, C]，其中C是列車(chē)的容量。根據(jù)邊際期望座位收益方法分析，一般座位數(shù)量不會(huì)與需求量偏差很大，所以編碼時(shí)對(duì)于每一個(gè)決策變量St只取[0,t+ 3t]之間的值，這樣將會(huì)縮小搜索空間的范圍，減少運(yùn)算時(shí)間。

圖2 X1與原X2和新X2之間的關(guān)系

對(duì)于本文的多區(qū)間座位控制模型，我們知道零向量是一個(gè)初始可行個(gè)體，可以將X1定義為零向量。但為了提高算法的收斂速度，對(duì)于第一個(gè)初始可行個(gè)體，可以采用如下方法自動(dòng)獲得。

我們知道，對(duì)于X1中第p個(gè)分量x1p所對(duì)應(yīng)分布的p和p均為正數(shù)，其中p＝1, 2, ,T，因此若X1還不是可行個(gè)體，重復(fù)上述作法，可以使每一分量均逐漸向0靠攏，能夠保證在有限迭代次數(shù)內(nèi)使X1成為零向量，因此重復(fù)上述做法必然使X1成為可行個(gè)體。當(dāng)X1成為可行個(gè)體后，再按照上述產(chǎn)生初始種群的方法產(chǎn)生其他初始可行個(gè)體。

3 算例

以2區(qū)間5種票價(jià)結(jié)構(gòu)為例，初始種群規(guī)模設(shè)定為300。所有決策變量取值均在[0,1020]區(qū)間內(nèi)。按隨機(jī)產(chǎn)生初始種群的方法和本文所用的方法分別進(jìn)行計(jì)算，得到表1所示的結(jié)果。

表1 兩種方法的運(yùn)行時(shí)間

4 結(jié)束語(yǔ)

實(shí)踐證明，采用該初始種群算法可以有效地縮短求解該模型的時(shí)間。同時(shí)，該算法也可以應(yīng)用到其他類(lèi)似問(wèn)題的求解中。

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

[2] 田延碩.遺傳算法的研究與應(yīng)用[J].電子科技大學(xué).2004.

[3] 張秀敏.我國(guó)鐵路客票折扣銷(xiāo)售研究[J].西南交通大學(xué).2005[4] 高強(qiáng), 朱金福, 陳可嘉.航空收益管理中多航段艙位控制模型[J].交通運(yùn)輸工程學(xué)報(bào).2005, (4).

[5] 劉昌貴, 但斌.基于蒙特卡羅仿真技術(shù)的隨機(jī)型庫(kù)存決策方法[J].重慶大學(xué)學(xué)報(bào)(自然科學(xué)版).2006, (2).

[6] 何大闊, 王福利, 賈明興.遺傳算法初始種群與操作參數(shù)的均勻設(shè)計(jì)[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版).2005, (9).

[7] Chatwin R.E.Optimal Airline Overbooking.Ph.D.thesis.Department of Operations Research.Stanford Unicersity Palo Alto CA.1992.

[8] Sun X..Airline Yield Management.A Dynamic Seat Allocation Model.Master’s thesis Faculty of Commerce.University of British Columbia.1992.

[9] Shaykevich.Airline Yield Management.Dynamic Programming Approach Master’s thesis.Department of Operation Research.University of North Carolina.Chapel Hill, NC.1994.