遺傳算法在多目標(biāo)優(yōu)化的應(yīng)用：公式,討論,概述總括

遺傳算法在多目標(biāo)優(yōu)化的應(yīng)用：公式，討論，概述/總括概述本文主要以適合度函數(shù)為基礎(chǔ)的分配方法來闡述多目標(biāo)遺傳算法。傳統(tǒng)的群落形成方法(nicheformationmethod)在此也有適當(dāng)?shù)难由欤⑻峁┝巳郝浯笮〗缍ǖ睦碚摳鶕?jù)。適合度分配方法可將外部決策者直接納入問題研究范圍，最終通過多目標(biāo)遺傳算法進行進一步總結(jié)：遺傳算法在多目標(biāo)優(yōu)化圈中為是最優(yōu)的解決方法，而且它還將決策者納入在問題討論范圍內(nèi)。適合度分配方法通過遺傳算法和外部決策者的相互作用以找到問題最優(yōu)的解決方案，并且詳細解釋遺傳算法和外部決策者如何通過相互作用以得出最終結(jié)果。簡介求非劣解集是多目標(biāo)決策的基本手段。已有成熟的非劣解生成技術(shù)本質(zhì)上都是以標(biāo)量優(yōu)化的手段通過多次計算得到非劣解集。目前遺傳算法在多目標(biāo)問題中的應(yīng)用方法多數(shù)是根據(jù)決策偏好信息，先將多目標(biāo)問題標(biāo)量化處理為單目標(biāo)問題后再以遺傳算法求解，仍然沒有脫離傳統(tǒng)的多目標(biāo)問題分步解決的方式。在沒有偏好信息條件下直接使用遺傳算法推求多目標(biāo)非劣解的解集的研究尚不多見。本文根據(jù)遺傳算法每代均產(chǎn)生大量可行解和隱含的并行性這一特點，設(shè)計了一種基于排序的表現(xiàn)矩陣測度可行解對所有目標(biāo)總體表現(xiàn)好壞的向量比較方法，并通過在個體適應(yīng)度定標(biāo)中引入該方法，控制優(yōu)解替換和保持種群多樣性，采用自適應(yīng)變化的方式確定交叉和變異概率，設(shè)計了多目標(biāo)遺傳算法(MultiObjectiveGeneticAlgorithm,MOGA)。該算法通過一次計算就可以得到問題的非劣解集，簡化了多目標(biāo)問題的優(yōu)化求解步驟。多目標(biāo)問題中在沒有給出決策偏好信息的前提下，難以直接衡量解的優(yōu)劣，這是遺傳算法應(yīng)用到多目標(biāo)問題中的最大困難。根據(jù)遺傳算法中每一代都有大量的可行解產(chǎn)生這一特點，我們考慮通過可行解之間相互比較淘汰劣解的辦法來達到最后對非劣解集的逼近?？紤]一個n維的多目標(biāo)規(guī)劃問題，且均為目標(biāo)函數(shù)最大化，其劣解可以定義為：f(x*)^f(x)i=1，2，，niit且式(1)至少對一個i取“V”。即至少劣于一個可行解的x必為劣解。對于遺傳算法中產(chǎn)生大量的可行解，我們考慮對同一代中的個體基于目標(biāo)函數(shù)相互比較，淘汰掉確定的劣解，并以生成的新解予以替換。經(jīng)過數(shù)量足夠大的種群一定次數(shù)的進化計算，可以得到一個接近非劣解集前沿面的解集，在一定精度要求下，可以近似的將其作為非劣解集。個體的適應(yīng)度計算方法確定后，為保證能得到非劣解集，算法設(shè)計中必須處理好以下問題：(1)保持種群的多樣性及進化方向的控制。算法需要求出的是一組不同的非劣解，所以計算中要防止種群收斂到某一個解。與一般遺傳算法進化到后期時種群接近收斂不同，多目標(biāo)遺傳算法中要求都要保持解的多樣性以適應(yīng)對已得到的優(yōu)解(也就是最后非劣解集的備選集)能再進行更新。(2)優(yōu)解的選擇替換。算法必須能選出表現(xiàn)更好的解，并避免由于優(yōu)解的替換不當(dāng)使得解集收斂于同一個方向，并使得解集的分布具有一定程度的均勻性。從上述思路出發(fā)，本文在多目標(biāo)遺傳算法中使用了針對多目標(biāo)的個體適應(yīng)度確定方法，對交叉和變異概率依據(jù)種群和進化代數(shù)進行自適應(yīng)調(diào)整，并控制種群個體并行向非劣解集前沿面逼近。二向量評估基因算法Schaffer在1984年提出一種向量評價的遺傳算法。它通過以目標(biāo)向量的各個分量作為適應(yīng)度來選擇出幾個等規(guī)模的子群體，交叉和變異的操作則在由子。群體組成的整個群體內(nèi)進行。即在每一代，基于個目標(biāo)函數(shù)適應(yīng)度的計算，產(chǎn)生一定數(shù)目的子種群，子種群的大小為N/q,q為目標(biāo)函數(shù)的個數(shù)，然后將產(chǎn)生q個子種群的后代混合起來成為新的種群N繼續(xù)雜交。雜交采用離散重組，變異采用均勻變異。然而1989年理查德提出：將所得的全部新個體都劃分到同一個種群內(nèi)，相當(dāng)于將全部適合度符合的向量點集，線性劃歸到同一適合度函數(shù)曲線上。因此當(dāng)下的效率權(quán)衡就取決于當(dāng)下新組成的群體。實質(zhì)上它是一種權(quán)重取于當(dāng)前世代的適應(yīng)度函數(shù)線性求和的將多目標(biāo)合成單一目標(biāo)的優(yōu)化方法。在最優(yōu)集的基礎(chǔ)上，提出一種將各個目標(biāo)值直接映射到適應(yīng)度函數(shù)中的基于秩的適應(yīng)度函數(shù)。因此下一章我們提出：提出了用于對整個種群的個體進行排序的結(jié)合目標(biāo)值及其優(yōu)先級偏好信息的關(guān)系算子。三以等級分三類的方式體現(xiàn)適應(yīng)度分配方法在多目標(biāo)優(yōu)化遺傳算法中的應(yīng)用將Xi視為t子代中的一個個體，該個體符合適應(yīng)度函數(shù)Pi(t)，假設(shè)其余全部個體都在現(xiàn)存種群中，則Xi在該種群中的位置，可用以下函數(shù)表明：p(')函數(shù)(Xi,t)=1+i其余所有不完全符合Pi(t)的個體則被分配到等級1(rankl)的函數(shù)曲線上，見圖1.(見原稿figureImultiobjectiveranking)，這和Fourman1985年提出的分類篩選的方法有所不同，該等級分類的方式明確表明處于等級3的個體劣于處于等級2的個體，原因在于后者(等級3)函數(shù)曲線對現(xiàn)存?zhèn)€體的描述較為粗略。但1989年Goldberg,提出的方法則忽略了這兩的等級存在的些微差異。關(guān)于適應(yīng)度分配方法我們應(yīng)認識到：不需要將某代該種群中的各個等級都呈現(xiàn)出來，例如圖1中等級4的缺失即為一很好的例證。傳統(tǒng)的適應(yīng)度按等級的分配方法在此有了一定延伸：按等級找種群將全部個體按適應(yīng)度從最優(yōu)（等級1）排到最劣（等級^其中n小于等于N）,從某方面看，該曲線一般為線性關(guān)系，但也不盡然。按適合度將每個個體都分配到同一等級，則這些個體被選中繼續(xù)作為下一代親本的幾率是相同的。值得注意的是該方法使得全球各種群的適應(yīng)度具有連續(xù)性，并維持了適當(dāng)?shù)暮Y選淘汰的壓力。上述所指的適應(yīng)度分配方法僅為傳統(tǒng)/標(biāo)準(zhǔn)方法的一個延伸，適用于單目標(biāo)優(yōu)化或無相互競爭的多目標(biāo)優(yōu)化。四基于小生境技術(shù)遺傳算法適應(yīng)度分享法可以有效地在復(fù)雜多峰函數(shù)優(yōu)化問題中避免基因個體的堆積，保持群體的多樣性。這里引進的另一個遺傳算法的矢量^血戲需要特別注意。現(xiàn)存的理論把^血戲的價值設(shè)定為解集有優(yōu)先知道的有限個峰和均勻小生境組成。在收斂上，適應(yīng)度高的個體將取代原有的結(jié)構(gòu)相似的個體。另一方面，在多目標(biāo)優(yōu)化問題中的全體解的個體適應(yīng)度是均勻單調(diào)的，而且無法預(yù)知解集的大小。函數(shù)的運用已經(jīng)強制性使搜索集中在在全體最優(yōu)解中。通過在目標(biāo)價值范圍內(nèi)應(yīng)用使用度分享比在多種解決范圍內(nèi)要好。，并且只有在總體操作空間的兩兩間非支配個體間才能進化出均勻分配表現(xiàn)。適應(yīng)度共享函數(shù)的直接目的時將搜索空間的多個不同峰值在地理上區(qū)分開來，每一個峰值處接受一定比例數(shù)目的個體，比例大小與峰值高度有關(guān)。為了實現(xiàn)這樣的分布，共享法將個體的目標(biāo)適應(yīng)度降低得到個體鄰集密集程度的估計。適應(yīng)度函數(shù)共享法多少獨立于現(xiàn)在使用的選擇方法。4.1對^share的選擇^sha的建立意義是較好峰值之間個體的最小距離，其建立基礎(chǔ)是分享法將個體目標(biāo)適應(yīng)度降低。通過以上部分，我們無法知道在不同解決范圍內(nèi)多目標(biāo)優(yōu)化問題解集的大小，由于它依賴于目標(biāo)函數(shù)圖像。然而，在目標(biāo)價值范圍內(nèi)和由于非支配個體定義，一個更高的限制對于解集的大小可以被計算通過最小值和最大值評價各個目標(biāo)假設(shè)在那個解集內(nèi)。另S為不同解決方法范圍內(nèi)的解集。f（S）為目標(biāo)范圍內(nèi)的解集，''’I,...'q）,,同時令m=(min']...,min')=(m,m)yyM=(maxy,...maxy)=(MM)yy設(shè)A是各個不同(M「m?邊界連積的和A=fI!（M-m）TOC\o"1-5"\h\zFjT77!（M-m+b）一！（M-m）bqt-、——;=0sharebsharebh>0share五在選擇算法中混合HIGHER-LEVER的解決方式當(dāng)遇到既定函數(shù)做選擇的情況下，決策者需要決定哪個無支配個體作為解。首先，非劣最優(yōu)目標(biāo)區(qū)域根據(jù)特定的問題設(shè)定協(xié)議，然后用一個清晰地可用的圖，這個協(xié)議知道找到解終止?？偠灾m應(yīng)度較高的解保留較多而樣本，適應(yīng)度較低的解保留較少的樣本甚至被淘汰。進化過程最后一代的最優(yōu)解就是遺傳算法的最終結(jié)果。減少解決法案的種類被稱為Higher-lever的結(jié)決方案。這個方法并沒有縮小尋找的范圍，而是減少了非劣最優(yōu)目標(biāo)區(qū)域?qū)ふ易顑?yōu)解的空間。這種適應(yīng)度解決方式更早前被描述為了接受達成目標(biāo)的信息，近似的被應(yīng)用為傳統(tǒng)的目標(biāo)達成方式(Gembicki1974)5.1目標(biāo)規(guī)劃法目標(biāo)規(guī)劃法解決多目標(biāo)多約束問題的定義如下minf(x)xeQ設(shè)X為變量，Q為可行域，f為目標(biāo)函數(shù)，代入一下公式可得min人XxeQ同理fTW"g這里gi是f的目標(biāo)偏好值。Wi為權(quán)重。對人求極限，Wi"是目標(biāo)偏差的最小值5.2調(diào)整多目標(biāo)優(yōu)化方案概括目標(biāo)信息

多目標(biāo)優(yōu)化函數(shù)程序最早描述的是對通過改變個體與個體比較的方法調(diào)整目標(biāo)信息。這使得一個個體優(yōu)于另一個個體成為可能，即使兩個都是無支配個體。這個算法將變得不同并演進了操作面得相關(guān)區(qū)域。1q。同時考慮'1q。同時考慮'g滿足y=（'…'）疽=（'…'g=（g…g）gg1gq，且bb1bq，且曰標(biāo)向量一個值，q~k，中一個特殊目標(biāo)。除了一般性的誤差，可寫成3k—1，，q—1;X/1—1，...k，Vj—k+1,...,q,('>g)a('<'假設(shè)一組可用的目標(biāo)序列值。甚至，g不滿足任意一個目標(biāo)，i,e.(B)Vi—1,...，q,（'>g）或者全部目標(biāo)，我們可寫成(C)(B)在公式（A）中，'g滿足目標(biāo)k+1,…，q并且，因此將優(yōu)先于'b，如果他支配'b遵循第一個k構(gòu)成的'g等同于由k構(gòu)成的'b。'g將仍在種群中優(yōu)于'b如果他支配'b遵循剩余的組成個體，或者剩余的種群個體全都不滿足目標(biāo)。通常，'g將優(yōu)先于'b當(dāng)且僅當(dāng)('p<')v{g(1,...b)b(1,...,b)('g(1...,b)-'b(1.,b))八f'p<')v~('<g)-g(b+1...q)b(b+1...q)b(b+1,...,q)(b+1,...，q))在公式（B）中，'g不滿足任何一個目標(biāo)。然后'g優(yōu)先于'b，當(dāng)且僅當(dāng)它支配'b，i,e,（'<'N?（'<g）這種關(guān)系的應(yīng)用優(yōu)于僅對其進行描述。設(shè)所有的目標(biāo)趨近無窮大將使得算法演進為整個非劣性域的表述。這種表述或許不夠精確，受目標(biāo)規(guī)劃的影響，在多目標(biāo)優(yōu)化問題中比較容易得到偏好信息不同的目標(biāo)給定相同的優(yōu)先級，可以避免使用目標(biāo)函數(shù)的距離測度，而距離測度不可避免的依賴于具體問題中給定的目標(biāo)值大小。這種方法依賴于決策者提供的目標(biāo)值及其優(yōu)先級偏好信息，在某種程度上仍取決于決策者對問題的把握程度，需要決策者來決定。六通過多目標(biāo)優(yōu)化遺傳算法提高偏好值精確值多目標(biāo)優(yōu)化遺傳算法可以進一步被推廣。決策者的行為可看成一些非絕對意義上的效用函數(shù)的連續(xù)價值體現(xiàn)。效用函數(shù)表達了一種決策者結(jié)合目標(biāo)函數(shù)對其中一個目標(biāo)值的偏好大于另一目標(biāo)值，最后，是這個函數(shù)建立了遺傳算法優(yōu)化種群的基礎(chǔ)。建立線性規(guī)劃模型進行個體比較，同時對當(dāng)前種群的個體進行排序，另一方面，達成決策者兩個不同態(tài)度的一致。首先，假設(shè)決策者準(zhǔn)確的指導(dǎo)優(yōu)化的對象，比如財政支出。第二，決策者只使得優(yōu)化個體使用多目標(biāo)優(yōu)化優(yōu)越性最廣泛的定義。提供目標(biāo)信息，或使用分享技術(shù)，通常意味著決策者更詳盡的態(tài)度，更少直接的效用函數(shù)，一個可能甚至不同于遺傳算法的過程，但仍是另一個效用函數(shù)。一個多目標(biāo)的基因優(yōu)化在一般意義上是，由體現(xiàn)決策者對每代種群序列解的評估的標(biāo)準(zhǔn)的基因算法構(gòu)成。決策者通過對非劣性最優(yōu)解和可用的優(yōu)先信息的應(yīng)用來表達其偏好，同時通過選擇和繁殖產(chǎn)生下一代種群，重復(fù)上述選擇和繁殖，指導(dǎo)結(jié)束條件得到滿足。進化過陳過最后一代中的最優(yōu)解就是用遺傳算法最優(yōu)化問題所得到的最終結(jié)果。多目標(biāo)優(yōu)化問題中的多個目標(biāo)之間通過決策相互制約，對其中一個目標(biāo)的優(yōu)化必須以犧牲其他目標(biāo)為代價，一次通常無法找到一個解同時最優(yōu)化所有目標(biāo)，而是找到多個解，這些解間很難客觀評價他們的優(yōu)劣性。即多目標(biāo)優(yōu)化問題的解不是唯一的而是存在一個最優(yōu)解集合。七最初的結(jié)果多目標(biāo)優(yōu)化遺傳算法最直接的應(yīng)用是Pegasus氣體渦輪機的優(yōu)化一個完整的發(fā)動機非線性模型(Hancock,1992)，被應(yīng)用于SIMULINK(MATHWORKs,1992b)被用來模仿這個系統(tǒng)，給予初始條件數(shù)量和操控者參量集。遺傳算法被應(yīng)用在MATLAB(MATHWORKs,1992a;Fleming,1993),意味著所有的編碼精確地計算環(huán)境中運行。每一個算法的控制者參量都是Gray編碼，14個字節(jié)一行，串成70個字節(jié)長度的染色體。一個自由的初始容量為80和標(biāo)準(zhǔn)兩點簡化代理交叉算子以及二進制變化的應(yīng)用。初始目標(biāo)價值是設(shè)定發(fā)動機根據(jù)一些執(zhí)行要求。有四個目標(biāo)被應(yīng)用。tT最終輸出變化達到70%的時間目標(biāo)：tT^0.59s16最終輸出變化解決在±10%的時間目標(biāo)’6V1.08s05超越目標(biāo)，測量最終輸出變化相關(guān)的值，目標(biāo)。6<10%8rr在這一步驟后測量輸出錯誤4秒，最終輸出變化相關(guān)。目標(biāo)：err<10%在遺傳算法的運行過程中，決策者儲存了所有的非支配個體進化到現(xiàn)在的一代。該算法運用一定的選擇策略從當(dāng)前種群中選取兩父本，由該父本交叉遺傳產(chǎn)生的新個體替換種群中最差的個體，不斷重復(fù)直到終止條件滿足。ml7mlQf.理<'CDena口nsCJGt-LNormaliiedoDjectivevaluesDi二iDDi=itngLDObjectivefunctions一個典型的操作圖，在40代后達到初始目標(biāo)，在圖形6中體現(xiàn)。在這一階段為輸出誤差設(shè)置更高的目標(biāo)在圖7中表現(xiàn)，包含了圖六中解集的子集。繼續(xù)運行遺傳算法，更多的定義將被達到在這邊區(qū)域中。見圖八。圖九表現(xiàn)了解決方法的可選擇觀點。在上面舉例說明。八結(jié)束語遺傳算法通過搜集個體種群適合于多目標(biāo)優(yōu)化。它能夠找到總體最優(yōu)條件同時能夠處理不連續(xù)嘈雜的函數(shù)。多目標(biāo)優(yōu)化遺傳算法的進步表達了人們希望在細節(jié)上決定發(fā)動機的設(shè)計。從簡單的Pareto基礎(chǔ)適應(yīng)任務(wù)方法所引出的重要問題是基于非群體小生境多目標(biāo)優(yōu)化遺傳算法，應(yīng)用遺傳算法解決多目標(biāo)優(yōu)化問題時，個