高林娥

(運(yùn)城師范高等?？茖W(xué)校，山西 運(yùn)城 044000)

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

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

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

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

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

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

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

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

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

2.1 遺傳算法的概述

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

2.2 遺傳算法的運(yùn)行流程

圖1 遺傳算法的運(yùn)行流程

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

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

示例:

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

s1=13(01101)

s2=24(11000)

s3=8(01000)

s4=19(10011)

第二步:計(jì)算適應(yīng)度

假定適應(yīng)度為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

第三步:選擇

染色體的選擇概率為:

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

r1=0.450126，r2=0.110347

r3=0.572496，r4=0.98503

染色體 適應(yīng)度 選擇概率 積累概率 選中次數(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)中交叉算子采用單點(diǎn)交叉算子。

單點(diǎn)交叉運(yùn)算

注:表中/為交叉點(diǎn)

第五步:變異

注:表中0、1為變異點(diǎn)。

第六步:至下一代，適應(yīng)度計(jì)算——選擇——變異，直至滿足條件為止。

4 結(jié)論

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

［1］黃孔亮.多目標(biāo)遺傳算法研究與應(yīng)用［D］.深圳:深圳大學(xué)，2005.

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

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

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

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