□文/楊磊

（東北財經大學津橋商學院遼寧·大連）

一、遺傳算法簡介

遺傳算法（GAS）是由美國密執(zhí)根大學的Holland等人創(chuàng)立的。與其他啟發(fā)式方法順序搜索解空間的工作方式不同，遺傳算法采用解的種群作為工作單元，使用模仿生物進化的適者生存原則指導搜索并改進目標。種群由代表個體的定長字符串組成，每個個體表示解空間的一個點，每個解的質量，通過依賴于問題目標函數的適應值函數來進行評估。搜索過程通過進化來進行，每代中的個體以正比于它的適應值的概率遺傳到下一代。它使用3個基本算子：選擇、交叉和變異。選擇是指個體以其適應值比例復制到交配池中；交叉是交配池中的兩個個體進行交配，組合形成一個（或幾個）新個體，復制和交叉將好的特性進行遺傳；變異則是發(fā)生在少數字符串某基因位上的基因的突變，它使搜索過程能夠有機會從搜索到的局部最優(yōu)解逃出。

解決一個實際問題的遺傳算法通常包括下列兩個決策步驟：（1）將求解問題模型化為符合遺傳算法的框架?？尚薪饪臻g的定義，適應值函數的表現形式，解的字符串表達式方式；（2）遺傳算法參數的設計。種群規(guī)模，復制、交叉、變異的概率選擇，進化最大代數，終止準則設定等。

二、遺傳算法的基本特點

（一）結構特點。遺傳算法是以適應值提供的啟發(fā)式信息進行搜索的，與其他啟發(fā)式（模擬退火、爬山法、神經網絡等）方法相比，在結構和工作過程方面的特點見表1。（表1）

（二）實驗性能方面的特點

1、高效性。遺傳算法具有大范圍全局搜索的特點，與問題領域無關，前期工作量比較少。

2、健壯性。遺傳算法的搜索是用種群作為基本單元，采用三個不同作用的基本算子進行搜索的，解的結果隨時間增加而趨于穩(wěn)定，不受初始解的影響，而且不因實例的不同而蛻變。

3、通用性和靈活性。遺傳算法可用于多種優(yōu)化搜索問題，解題程序可以通用，針對不同的實例，適當調整算子參數，就可以使算法執(zhí)行獲得最佳的解結果和占用CPU機時的關系。

表1 遺傳算法的結構特點

表2 作業(yè)調度問題的研究

三、遺傳算法在解決經典運籌問題中的應用

（一）旅行商問題（TSP）。旅行商問題自誕生以來，頗受數學家推崇，今天的旅行商問題已遠遠超過其本身的含義，成為一種衡量算法優(yōu)劣的標準。旅行商問題是采用非標準編碼遺傳算法求解最成功的一例，基因編碼用推銷員順序經歷的城市名表示，求最佳路線即是改變編碼次序而求最低適應值的問題。對類似字符串使用標準交叉，產生的后代可能有重復或丟失的元素，因而成為非可行解。為克服這種困難，人們提出許多非標準的交叉和變異方法：交叉主要采用重排序方法——部分匹配重排序，順序交叉和循環(huán)交叉等；變異主要采用位點、反轉、對換、插入等方法，使旅行商問題得以有效地解決。值得一提的是，清華大學張雷博士提出的自適應多點交叉算子，能夠保證多點交叉后路徑的可行性，加快了搜索速度。

（二）作業(yè)調度問題。作業(yè)調度問題同樣是自然變更次序的問題，可以用基于變更次序的遺傳算法進行處理。（表2）

（三）背包問題。一維、二維和三維背包問題在商業(yè)和工業(yè)領域有著廣泛的應用，基于遺傳算法的求解方法很多。傳統(tǒng)求解采用啟發(fā)式規(guī)則，決定下一步該裝哪一塊和裝在哪里，此時變更次序的編碼與啟發(fā)式安置策略是利用遺傳算法解決這類問題的最為出色的方法，Lin使用一系列的懲罰項指導其搜索策略，測定單個個體的適應值。

Bortfeldt使用一個層次背包問題，個體用它們的層次代表，當兩個親代被選擇交叉時，它們的層次混在一起，從中選擇最好的作為子代的第一層，再從余下的組件中選擇最好的作為第二層，以此類推，直至產生所有的層次。

陳國良等設計了一種“與/或”交叉方法，使子代繼承雙親的同型基因，對雜型基因采用不同支配方式，這種策略為遺傳算法的硬件實現創(chuàng)造了良好的條件。

（四）時刻表排定問題。Corne對Edinburgh大學7日內的28個時間期間安排40門課的考試問題作了處理，尋找一個可行的時間排定表，使每個學生參加的考試在時間上能夠錯開，時刻表用字符串代表，字符串每個位置代表一門課，該位置的值代表考試的時間，用均勻交叉和標準變異操作求解。

這類問題擴展到基于二維的矩陣代表的逼近問題，Colorini使用行代表教師列代表可用的小時數的矩陣，每個單元的值為教師在此時承擔的任務，包括教室和其他一些資源配置，教師的任務是事先給定的，故行都是可行的，列代表的時間安排可能會發(fā)生沖突，將此沖突用懲罰函數表示在適應值函數中，而且采用修復算子在評價之前盡量將結論調整回可行區(qū)域內，該算法用Milan學校的實際數據進行了檢驗。

除此之外，遺傳算法在運輸問題、指派問題、分割問題及網絡計劃優(yōu)化問題等方面都獲得了非常成功的應用，這些問題被認為是NP類問題，其規(guī)模隨變量的增加呈指數增長，遺傳算法在這些問題的求解中，充分體現了其操作性能方面的優(yōu)勢。

四、應用和推廣中存在的問題

在上述問題中，遺傳算法求解展示了優(yōu)良的性能，但遺傳算法并未像其他啟發(fā)式方法那樣容易地被OR學者廣泛接受而用于大量的實際問題中，究其原因，主要有以下幾點：

（一）傳播方式的障礙。遺傳算法最初的工作是以密執(zhí)根大學嚴謹的研究小組作為研究項目和學術討論中心，當研究成員擴大時，這類討論會演變?yōu)闄C構的學術會議（美國現有5個，歐洲有3個，我國目前還沒有），許多研究者聚于此而遠離問題導向，有關的會議論文公開出版數量很少，而且，由于歷史原因，研究者常常將他們的研究結果選擇在有關人工智能的雜志上發(fā)表，導致了應用遺傳算法的信息很緩慢地擴散到其他不同技術應用領域的工作者中，這與模擬退火等其他啟發(fā)式方法快速在運籌學會議及雜志上發(fā)表相反。由于缺乏交流導致了兩方面的問題：一是許多關于遺傳算法的論文不能與從其他方法得到的結論進行質量的比較，二是削弱了許多遺傳算法多的潛在使用者用遺傳算法與其他方法競爭的信心。

（二）術語的隔膜。初始跨入遺傳算法領域的使用者常常感到起步非常艱難，遺傳算法依賴于遺傳學的術語也像模擬退火的術語來自于統(tǒng)計熱力學一樣。然而，溫度、冷卻等可能很快賦予新的意義，但遺傳算法中的基因位、染色體、遺傳型卻難以很快被人理解和接受；另外，許多發(fā)表的研究偏重于用某些專門函數檢驗他們的新思路或新設想，這對于全面理解該技術固然是一件好事，但對于一個面對如此豐富復雜材料的初用者會發(fā)現，他將不知從何做起。即使一個非常愿意使用遺傳算法的人，也要有足夠的決心去克服上述障礙。

（三）方法的局限性。對于具有強約束的優(yōu)化問題，采用懲罰函數逼近常常達不到預想的結果。Radcliffe評論說：“約束通常被認為是遺傳算法面臨的最大問題”因為懲罰因子選擇不當時，會招致錯誤結論。目前，求解帶約束優(yōu)化問題的啟發(fā)式遺傳方法已經有了一些，但是，它們多數與問題領域相關，在這方面還缺少普遍適用的方法的系統(tǒng)研究。

（四）編碼的困難。不是所有問題解空間中的點都能明顯地用編碼表示，作為OR研究者，常常從問題結構取得利益，用矩陣、樹、網絡或其他更適用的方法建立表達式；串表達中的建筑塊假說建議適用較少的字符，導致人們對二進制編碼的偏愛，但二進制編碼具有一定的映射誤差（實際計算時，我們是把問題作為整數規(guī)劃），特別是它不能直接反映出所求問題本身結構特征，因此很難滿足生成有意義的積木塊編碼原則；再者，二進制字符的長度隨問題發(fā)生明顯變化，當問題復雜時會因為編碼太長而無法進行正常工作。

以上的種種阻力，在一定程度上減緩了遺傳算法在運籌學實際問題中的推廣和應用。

[1]陳國良等.遺傳算法及其應用.北京：人民郵電出版社，1996.6.

[2]胡運權.運籌學.北京：清華大學出版社，2007.4.

[3]Michale wicz Z.Evolutionary computation techniques for non-linear programming problems.Trans.Opl.Res.1994.2.