基因遺傳算法的多目標優(yōu)化問題的研究與應用

高林娥

(運城師范高等?？茖W校，山西 運城 044000)

就現(xiàn)實而言，我們生存的世界存在許多問題，而在解決這些問題時，會遇到兩種類型的困難，一是多個相互沖突的目標。二是高維復雜的搜索空間。就第一點而言，單目標優(yōu)化不能解決的問題，多個相互競爭目標的優(yōu)化結果是可以得到一組可行解，一般被稱作Pareto最優(yōu)解集［1］。經(jīng)濟的發(fā)展是迅速的，而人的潛能是巨大的。人類為了更好的生活，在改造自然的方案規(guī)劃和設計的過程都體現(xiàn)了效益最大化和成本最小化的這一基本優(yōu)化原則。在現(xiàn)實生活中幾乎每個重要的決策問題都要在考慮約束條件的同時對若干個相互沖突的目標進行有效的處理，但是這又往往涉及到多個目標的優(yōu)化問題，這些目標不是單獨存在的，而是聯(lián)合在一起的相互競爭的目標［2］。所以，效益最大化和成本最小化在本質上是一個多目標優(yōu)化問題。將遺傳算法合理地應用到多目標優(yōu)化的問題上，可以有效地解決問題。而這種將遺傳算法應用到多目標優(yōu)化問題上的算法通常稱為多目標優(yōu)化進化算法或者多目標優(yōu)化遺傳算法。由于多目標問題的廣泛存在性和求解的困難性，所以研究者們一直對其有很大的興趣和挑戰(zhàn)性。它最早是由Franklin在1772年提出了如何有效協(xié)調多個目標矛盾的問題，但是目前國際上絕對多數(shù)的專家學者都普遍認為多目標優(yōu)化的問題是由法國的經(jīng)濟學家V.Pareto在1896年最早提出來的，V.Pareto從政治經(jīng)濟學的角度出發(fā)，將許多難以進行比較的問題統(tǒng)一歸納為多目標的最優(yōu)化問題。

1 多目標優(yōu)化的綜述

1.1 多目標優(yōu)化的基本概念

在大多數(shù)情況下，單目標優(yōu)化存在多個最優(yōu)解，這種情況在多目標優(yōu)化問題中是不存在的，多目標優(yōu)化問題的最優(yōu)解只存在Pareto最優(yōu)解。若一個多項目優(yōu)化問題存在所謂的最優(yōu)解，則該最優(yōu)解一定是Pareto最優(yōu)解，并且Pareto最優(yōu)解也只有這些最優(yōu)解組成，不再包含其它解。因此Pareto最優(yōu)解是多目標優(yōu)化問題的合理的解集合。而通常多目標優(yōu)化問題的Pareto最優(yōu)解是一個合集。所以，在求解多目標優(yōu)化問題的首要步驟和關鍵是求出盡可能多的Pareto最優(yōu)解［3］。

1.2 目前常用的多目標優(yōu)化方法

約束法:在MOP問題中，從k個目標函數(shù)f1(x)，f2(x)，…，fk(x)中，若能夠確定一個主要的目標，例如f1(x)，而對其它的目標函數(shù)只要滿足一定的條件即可，這樣我們就可以把其它目標當作約束來處理。此外，還有加權法、距離函數(shù)法、分層序列法等。

1.3 傳統(tǒng)優(yōu)化方法應用時的注意問題

傳統(tǒng)的多目標優(yōu)化方法在解決問題的過程中通常會存在著一定的局限性，其具體表現(xiàn)主要有以下幾點:①在運用加權法等一系列古典方法進行多目標優(yōu)化問題的求解時，對Pareto最優(yōu)前端的形狀很敏感，但是卻無法有效地處理前端的凹部。②通常情況下只能得到一個解，但是在實際決策中的決策者往往需要多種行之有效的方案來進行選擇。③傳統(tǒng)方法在運用的過程中都會共同存在著一個目標，那就是如何獲得Pareto的最優(yōu)集。而在獲得這個Pareto的過程中，最優(yōu)集需要多次進行優(yōu)化，但是由于每一次的優(yōu)化過程都是相互獨立的事件，得出的結果也很難得到統(tǒng)一，使得決策者很難進行有效的決策，而且這種方法費時又費力。④多個目標函數(shù)之間的量綱不同，難以統(tǒng)一。⑤由于目標函數(shù)的各個權值是由人為規(guī)定的，因此加權值的分配有著很強的主觀性。

2 遺傳算法的基本原理和方法

2.1 遺傳算法的概述

遺傳算法是模擬生物界中自然選擇和群體遺傳機制，采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。

2.2 遺傳算法的運行流程

圖1 遺傳算法的運行流程

第一，編碼。解空間的解數(shù)據(jù)x作為遺傳算法中的一種表現(xiàn)形式，通常會將從表現(xiàn)型到基因型的映射稱為編碼［4］。遺傳算法在搜索之前應當先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結構數(shù)據(jù)，這樣一來。這些串結構中不同組合的數(shù)據(jù)就構成了各個不一樣的點。第二，初始群體的生成。初始群體主要是由隨機生成的N個串結構數(shù)據(jù)，這些串結構數(shù)據(jù)又會構成N個個體，N個個體再會構成一個群體。遺傳算法在此時便會以這N個串結構作為迭代的初始點。第三，適應度值評價檢測。適應度函數(shù)通常代表著個體或解的優(yōu)越性。在處理不同的問題時，適應度函數(shù)定義的方法式也不盡。第四，選擇合適的算子，并將此算子作用于群體，在確定個體時應當緊密依據(jù)適應度函數(shù)值的變化來進行確定，以便下一步操作的順利進行。第五，交叉。把交叉算子運用到群體之中，并以交叉的概率P進行交叉操作，之后再隨機對群體中的選取的個體在隨機生成的位置進行交叉。第六，變異。通過將變異算子在群體中進行作用，在進行變異操作時，應當以變異的概率對個體進行變異，從而得到新個體。

3 多目標優(yōu)化問題遺傳算法應用示例

示例:

第一步:產(chǎn)生初始種群

s1=13(01101)

s2=24(11000)

s3=8(01000)

s4=19(10011)

第二步:計算適應度

假定適應度為f(s)=s2，則

f(s1)=f(13)=132=169

f(s2)=f(24)=242=576

f(s3)=f(8)=82=64

f(s4)=f(19)=192=361

第三步:選擇

染色體的選擇概率為:

例如設從區(qū)間［0，1］中產(chǎn)生4個隨機數(shù):

r1=0.450126，r2=0.110347

r3=0.572496，r4=0.98503

染色體 適應度 選擇概率 積累概率 選中次數(shù)S1=01101169 0.14 0.14 1 S2=11000 576 0.49 0.063 2 S3=01000 64 0.06 0.69 0 S4=10011361 0.31 1.00 1

第四步:交叉

基本遺傳算法(SGA)中交叉算子采用單點交叉算子。

單點交叉運算

注:表中/為交叉點

第五步:變異

注:表中0、1為變異點。

第六步:至下一代，適應度計算——選擇——變異，直至滿足條件為止。

4 結論

基因遺傳算法的多目標優(yōu)化問題的關鍵在于群體適應度的分配和進化過程中群體多樣性的保持。多目標優(yōu)化問題的解不是唯一的，而是存在一個最有解集合，對于解決現(xiàn)實生活中的復雜問題是可行的。但是，目前求解的多目標優(yōu)化問題的遺產(chǎn)算法缺乏收斂性理論，沒有描述出多目標遺傳算法代與代之間的動態(tài)［5］。多目標優(yōu)化領域取得成果是矚目的，但進一步的研究也將作為發(fā)展的趨勢。

［1］黃孔亮.多目標遺傳算法研究與應用［D］.深圳:深圳大學，2005.

［2］藍盛芳.試論達爾文進化論與協(xié)同進化論［J］.生態(tài)科學，1995，(2).

［3］楊唐勝，陳文清，朱瑞賡.一種與遺傳算法類似的人工免疫算法［J］.武漢理工大學學報，2005，(10).

［4］鄧麗君.基于遺傳算法的多目標優(yōu)化與決策方法研究［D］.長沙:國防科學技術大學，2003.

［5］關志華.面向多目標優(yōu)化問題的遺傳算法的理論及應用研究［D］.天津:天津大學，2002.