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

□文/楊磊

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

一、遺傳算法簡(jiǎn)介

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

解決一個(gè)實(shí)際問(wèn)題的遺傳算法通常包括下列兩個(gè)決策步驟：（1）將求解問(wèn)題模型化為符合遺傳算法的框架?？尚薪饪臻g的定義，適應(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)和工作過(guò)程方面的特點(diǎn)見(jiàn)表1。（表1）

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

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

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

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

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

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

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

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

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

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

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

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

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

這類(lèi)問(wèn)題擴(kuò)展到基于二維的矩陣代表的逼近問(wèn)題，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èn)題、指派問(wèn)題、分割問(wèn)題及網(wǎng)絡(luò)計(jì)劃優(yōu)化問(wèn)題等方面都獲得了非常成功的應(yīng)用，這些問(wèn)題被認(rèn)為是NP類(lèi)問(wèn)題，其規(guī)模隨變量的增加呈指數(shù)增長(zhǎng)，遺傳算法在這些問(wèn)題的求解中，充分體現(xiàn)了其操作性能方面的優(yōu)勢(shì)。

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

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

（一）傳播方式的障礙。遺傳算法最初的工作是以密執(zhí)根大學(xué)嚴(yán)謹(jǐn)?shù)难芯啃〗M作為研究項(xiàng)目和學(xué)術(shù)討論中心，當(dāng)研究成員擴(kuò)大時(shí)，這類(lèi)討論會(huì)演變?yōu)闄C(jī)構(gòu)的學(xué)術(shù)會(huì)議（美國(guó)現(xiàn)有5個(gè)，歐洲有3個(gè)，我國(guó)目前還沒(méi)有），許多研究者聚于此而遠(yuǎn)離問(wèn)題導(dǎo)向，有關(guān)的會(huì)議論文公開(kāi)出版數(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)致了兩方面的問(wèn)題：一是許多關(guān)于遺傳算法的論文不能與從其他方法得到的結(jié)論進(jìn)行質(zhì)量的比較，二是削弱了許多遺傳算法多的潛在使用者用遺傳算法與其他方法競(jìng)爭(zhēng)的信心。

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

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

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

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

[1]陳國(guó)良等.遺傳算法及其應(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.