一種初始種群算法的應用研究

姜彬峰

（吉林鐵道職業技術學院 計算機科學技術系，吉林 132001）

0 引言

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

遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結構對象的優化過程中顯示出明顯的優勢。與傳統的搜索方法相比，遺傳算法具有如下特點：

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

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

l）產生初始群體，隨機產生m個個體，每個個體看作是一個染色體，m個染色體組成一個群體；

2）對群體中每個個體計算相應的適應度值；

3）通過選擇和復制操作從群體中選出滿足條件的個體，并放入到交配緩沖池中；

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

5）計算每個新個體的適應度值；

6）如果滿足結束條件，則停止；否則轉到第3步。

圖1 標準遺傳算法流程圖

由圖1可見，初始群體是遺傳算法的第一步，初始種群的分布狀態不僅直接關系到遺傳算法的全局收斂性，還影響算法的搜索效率，所以對初始種群進行科學合理設定是應用遺傳算法進行尋優計算的一個重要問題。

1 需求解的實際模型

在鐵路客運領域，鐵路企業為實現客運總收益最大化，在基于旅客需求預測的前提下可以建立以下一種多區間多票價的座位控制模型。

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

ck為第k個區間的列車的容量，C為全部ck組成的K維列向量；

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

Rt為第t個FODF的收益。

該模型是一個隨機規劃模型，對于這種約束優化問題，可以使用遺傳算法進行求解。

2 初始種群算法

對于該模型，如果使用產生隨機數的方法來得到足夠數量的初始種群，將大大增加算法的運算時間，而且由于傳統GA的初始種群是隨機選取的，初始種群的覆蓋空間具有很大的不確定性，如果初始種群空間不包含全局最優解的信息，而遺傳算子又不能在有限的進化代數內將覆蓋空間擴延到全局最優解所在的區域，那么過早收斂就不可避免的[6]。本文采用以下方法得到初始種群。

定義1：隨機產生一個個體，若該個體滿足約束條件，則該個體稱為可行個體，若該個體不滿足約束條件，則稱該個體為非可行個體[1]；

定義2：最初的可行個體的全體稱為初始種群，個體的數量稱為種群規模[1]；

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

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

若令rip為與第i個初始個體第p個分量相對應的在[0, 1]區間內服從均勻分布的隨機數，X1為一個已知初始可行個體，它滿足規劃模型中的約束條件。

初始種群規模為m，于是可按下式隨機產生一個初始個體X2：

其中：檢驗新生成的X2是否滿足約束條件，若滿足則生成新的初始個體X3，若不滿足則重復執行式（2）直至X2成為可行個體。

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

設x1p為X1的第p個分量，x2p為X2的第p個分量，其中p＝1, 2, ,n，為X2的第p個分量經過式（2）第k次迭代（即重復執行式（2）k次）后的值，則有

又因為

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

設

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

由數學歸納法可知對于k＝1, 2, ，式（7）恒成立。

因為0≤ ＜1，當x2p≠x1p時，下述兩式成立。

式（8）說明，當式（2）重復執行時，將使X2中的各分量的值不斷地向X1中對應的各分量的值靠近。

式（9）說明，當式（2）重復執行時，將使X2中的各分量的值不斷地向X1中對應的各分量的值無限地靠近。在一定的精度要求下，當與x1p的差距在精度要求的范圍內時，可以令＝x1p。

若x2p＝x1p，當式（2）重復執行時，由式（7）可知，將始終等于x1p。

綜上所述，若新生成的X2仍不滿足約束條件，則對其重復執行式（2），使X2中的各分量的值不斷地向X1中對應的各分量的值靠近。在一定精度要求下，可以經過有限次迭代，最終使X2中的各分量的值等于X1中對應的各分量的值。

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

事實上，如果取 ＝0.5，我們可以認為用式（2）進行一次迭代后的新X2是X1與原X2連線的中點，如圖2所示。

X2產生后，再產生X3，采用與X2同樣的方法進行處理，最終能夠產生m個初始可行個體。

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

圖2 X1與原X2和新X2之間的關系

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

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

3 算例

以2區間5種票價結構為例，初始種群規模設定為300。所有決策變量取值均在[0,1020]區間內。按隨機產生初始種群的方法和本文所用的方法分別進行計算，得到表1所示的結果。

表1 兩種方法的運行時間

4 結束語

實踐證明，采用該初始種群算法可以有效地縮短求解該模型的時間。同時，該算法也可以應用到其他類似問題的求解中。

[1] 王福林,吳昌友,楊輝.用遺傳算法求解約束優化問題時初始種群產生方法的探討[J].東北農業大學學報.2004, (5).

[2] 田延碩.遺傳算法的研究與應用[J].電子科技大學.2004.

[3] 張秀敏.我國鐵路客票折扣銷售研究[J].西南交通大學.2005[4] 高強, 朱金福, 陳可嘉.航空收益管理中多航段艙位控制模型[J].交通運輸工程學報.2005, (4).

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

[6] 何大闊, 王福利, 賈明興.遺傳算法初始種群與操作參數的均勻設計[J].東北大學學報(自然科學版).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.