遺傳算法在解決經(jīng)典運(yùn)籌問題中的應(yīng)用

□文/楊磊

（東北財(cái)經(jīng)大學(xué)津橋商學(xué)院遼寧·大連）

一、遺傳算法簡介

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

解決一個(gè)實(shí)際問題的遺傳算法通常包括下列兩個(gè)決策步驟：（1）將求解問題模型化為符合遺傳算法的框架。可行解空間的定義，適應(yīng)值函數(shù)的表現(xiàn)形式，解的字符串表達(dá)式方式；（2）遺傳算法參數(shù)的設(shè)計(jì)。種群規(guī)模，復(fù)制、交叉、變異的概率選擇，進(jìn)化最大代數(shù)，終止準(zhǔn)則設(shè)定等。

二、遺傳算法的基本特點(diǎn)

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

（二）實(shí)驗(yàn)性能方面的特點(diǎn)

1、高效性。遺傳算法具有大范圍全局搜索的特點(diǎn)，與問題領(lǐng)域無關(guān)，前期工作量比較少。

2、健壯性。遺傳算法的搜索是用種群作為基本單元，采用三個(gè)不同作用的基本算子進(jìn)行搜索的，解的結(jié)果隨時(shí)間增加而趨于穩(wěn)定，不受初始解的影響，而且不因?qū)嵗牟煌懽儭?/p>

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

表1 遺傳算法的結(jié)構(gòu)特點(diǎn)

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

三、遺傳算法在解決經(jīng)典運(yùn)籌問題中的應(yīng)用

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

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

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

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

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

（四）時(shí)刻表排定問題。Corne對(duì)Edinburgh大學(xué)7日內(nèi)的28個(gè)時(shí)間期間安排40門課的考試問題作了處理，尋找一個(gè)可行的時(shí)間排定表，使每個(gè)學(xué)生參加的考試在時(shí)間上能夠錯(cuò)開，時(shí)刻表用字符串代表，字符串每個(gè)位置代表一門課，該位置的值代表考試的時(shí)間，用均勻交叉和標(biāo)準(zhǔn)變異操作求解。

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

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

四、應(yīng)用和推廣中存在的問題

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

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

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

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

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

以上的種種阻力，在一定程度上減緩了遺傳算法在運(yùn)籌學(xué)實(shí)際問題中的推廣和應(yīng)用。

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

[2]胡運(yùn)權(quán).運(yùn)籌學(xué).北京：清華大學(xué)出版社，2007.4.

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