基于PARETO的改進遺傳在多目標(biāo)模型的研究

林虹虹

摘 要：該文先介紹PARETO解及多目標(biāo)的相關(guān)概念，再通過自適應(yīng)更新機制、精英保留策略等方法來提高遺傳搜索效率，并且對多目標(biāo)函數(shù)的結(jié)構(gòu)進行改進設(shè)計，結(jié)合IAGAMO模型，以全局搜索機制作為研究基礎(chǔ)，針對遺傳算法實際應(yīng)用缺陷進行了分析，著重論述通過全局搜索機制對提高局部搜索中遺傳算法的影響，從而加速了IAGAMO混合算法的運算速度以及收斂效率。最后將PARETO的IAGAMO算法在生產(chǎn)實例進行仿真驗證，結(jié)果所獲得PARETO解的數(shù)據(jù)較符合生產(chǎn)的實際應(yīng)用。因此，PARETO以其巨大的技術(shù)優(yōu)勢，有效提升了搜索效率，在多目標(biāo)搜索以及解集的優(yōu)化中發(fā)揮了重要的作用，因此具有廣闊的發(fā)展空間。

關(guān)鍵詞：多目標(biāo)優(yōu)化 遺傳算法 PARETO

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1674-098X（2015）09（c）-0046-02

The Research on the Multi-objective Case Using Improved GA Based on PARETO

Lin Honghong

（Engineering occupation technical college of Guangdong，Guangzhou Guangdong，510630，China）

Abstract：This article first introduces the concepts of PARETO solutions and multi-target，and then through an adaptive update mechanism， elitist and other methods to improve the efficiency of genetic search， and the structure of multi-objective function to improve the design， combined with IAGAMO model， through the adaptive cross， features of the PARETO optimal solution， variability update mechanism and mixing in elite global search mechanism strategy to further address the lack of genetic algorithms to search for local solutions， and it to improve the IAGAMO hybrid convergence speed and computational efficiency. Finally， PARETO of IAGAMO algorithm simulation instance in the production， the results obtained are compared with data PARETO solution compatible with the application of production.Therefore，PARETO not only to better improve the efficiency of multi-objective optimization search solution set， but also with a wide range of produce promotional value.

Key Words：Multi-objective Optimization；Genetic Algorithm；PARETO

近年來，多目標(biāo)優(yōu)化問題求解已成為演化算法的重要研究方向。由于傳統(tǒng)優(yōu)化方法的局限性，導(dǎo)致該研究進展緩慢，而且多目標(biāo)與單目標(biāo)優(yōu)化問題也存在較多不同，其中單目標(biāo)問題只需優(yōu)化一個目標(biāo)或一個最優(yōu)解；但是多目標(biāo)的目標(biāo)值卻經(jīng)常形成互相沖突，即當(dāng)目標(biāo)是達到最優(yōu)時，其化目標(biāo)不一定是最優(yōu)，甚至有可能是最差的，形成多目標(biāo)化問題（Multi-objective Optimization Problem，MOP）。

遺傳算法可以對整個群體進行進化運算操作，著重于個體的集合，是求解軟性多目標(biāo)規(guī)劃的重要方法，運用遺傳算法對多目標(biāo)模型求解可以得到相對較好的解集，因此本文主要通過不同決策變量的研究設(shè)計、定義，再依據(jù)多目標(biāo)PARETO解的概念，進一步地改進設(shè)計的遺傳多目標(biāo)模型（IAGAMO）。

1 多目標(biāo)優(yōu)化現(xiàn)狀

現(xiàn)階段，多目標(biāo)問題優(yōu)化的應(yīng)用越來越廣，而多目標(biāo)求解中也往往存在相互競爭、相互沖突，其中一個目標(biāo)的改進可能引起其他目標(biāo)性能的降低，所以不存在解使得各個目標(biāo)函數(shù)同時達到最優(yōu)，因此我們只能尋找在多個目標(biāo)協(xié)調(diào)中相對最優(yōu)的解。而傳統(tǒng)的多目標(biāo)優(yōu)化問題解決方法主要是依靠設(shè)計人員進行排序或加權(quán)進行優(yōu)化，然后再利用傳統(tǒng)的單目標(biāo)優(yōu)化求解方法進行求解，因此存在不少缺點，例如：（1）該方法需要決策者對該問題要有充分的認(rèn)識和了解、合理的權(quán)值、敏感的參數(shù)、穩(wěn)定的可靠性。（2）決策者在做決定的時候，往往希望能有多種選擇的方案，而該方法恰恰只能提供唯一的解。

2 遺傳多目標(biāo)概念

一般的多目標(biāo)優(yōu)化問題可以定義如下[1-2]：

MinT

S.t i=1，2…，k （1）

其中T。

傳統(tǒng)多目標(biāo)問題優(yōu)化方法，一般情況下只能得到局部最優(yōu)解，加上系統(tǒng)仿真過程較費時，使得整個優(yōu)化過程都會變得很慢。

在多目標(biāo)研究中，即當(dāng)且僅當(dāng)模型只有單目標(biāo)時，可以較快尋找到最好的解。若存在多個目標(biāo)時，由于目標(biāo)之間存在無法比較和沖突現(xiàn)象，會導(dǎo)致最后解不一定是所有目標(biāo)下最優(yōu)的解。因此存在多個目標(biāo)解的時候，一般也存在一系列無法簡單進行比較的解。這種解稱作PARETO最優(yōu)解（PARETO optimal solutions） 或非支配解（Nondominated Solutions）。

對于每個PARETO最優(yōu)解都具有在不同程度上滿足各目標(biāo)的“優(yōu)越性”。因此只需在實際應(yīng)用中選擇PARETO最優(yōu)解中一個較為合適的折衷解即可。所以在求解多目標(biāo)優(yōu)化的過程中，就比須解決兩個問題：一個是如何求得PARETO最優(yōu)解；另一個是如何根據(jù)實際情況，在多個的PARETO最優(yōu)解中選擇最合適的最大的PARETO最優(yōu)解。

遺傳算法有較好的搜索性和并行性特點，因此多目標(biāo)遺傳算法可以同時求出多個PARETO解，并且對于PARETO解集中的解進行選擇、交叉、變異等遺傳操作，最終求出多目標(biāo)優(yōu)化問題的最優(yōu)解。所以只能在單次模擬運算中搜索PARETO最優(yōu)集，因此它非常適用于多目標(biāo)規(guī)劃問題。

3 遺傳的多目標(biāo)改進研究

遺傳算法具有全局搜索能力較強優(yōu)勢，故作為指導(dǎo)性搜索算法，本文則結(jié)合精英混合局部搜索能力強及遺傳算子自適應(yīng)的更新的特點，克服遺傳算法的不足，增強混合遺傳算子在全局和局部范圍的搜索能力和效率。

3.1 編碼

在編碼過程中，主要采用實數(shù)編碼，用以降低解的搜索時間過程，提高IAGMO算法收斂速度。

3.2 初始化群體

首先隨機生成S×N個樣本，然后將它們分成N個子群體，每個子群體包含Smin個（一個決策變量解）樣本。其中Smin為最小規(guī)模保護限制，引入這一概念是為了保護群體的進化能力，使之不會被過早地淘汰。

3.3 適應(yīng)度值計算

由于多目標(biāo)問題模型屬于多維模型，因此在本文將約束條件和目標(biāo)函數(shù)的以矩陣的方式設(shè)計，舉例如下，首先對約束條件的x系數(shù)和邊界作矩陣排列，如：

x1+x2<=100

30×x1+40×x2<=300 （2）

根據(jù)（2）式，決策變量x矩陣設(shè)計為：[1，1；30，40]，而約束條件的邊界矩陣為：[100；300]，至此目標(biāo)函數(shù)的迭代計算則依次計算約束條件函數(shù)及目標(biāo)函數(shù)，偽碼如下：

[subjected_value]=Subject_fitness（x） （3）

[fitness_value]=fitness（subjected_value） （4）

3.4 混合策略分析

針對選擇機制，主要采用混合選擇機制，結(jié)合輪盤賭以及期望值方法。通常選擇機制都會采用輪盤賭方法，依照實際個體數(shù)進行確定，若個體數(shù)過少，則依照隨機數(shù)進行選擇時會出現(xiàn)誤差，造成無法將個體適應(yīng)度正確反映出來。為了有效降低這種選擇誤差，通常會使用期望值方法。

（1）通過下述計算公式對每個個體進行計算，求出其在下一代生存中期望數(shù)目。 （5）

（2）若在選擇過程中，某一個體被選中參與交叉，那么在下一代生存中，其期望數(shù)目需降低0.5；若被選中個體不參與交叉，則其在下一代生存中期望數(shù)目降低1。

（3）若完成上述計算后，個體期望小于0，則選擇項中不包含該個體。

3.5 遺傳交叉、變異自適應(yīng)策略

在種群適應(yīng)度比較集中時，使交叉概率比變異概率，當(dāng)群體適應(yīng)度比較分散時，使和增大。因此Srinvivas等提出了一種自適應(yīng)遺傳算法（Adaptive GA，AGA），和能夠隨著個體的適應(yīng)度自動變化。但經(jīng)測試研究，Srinvivas提出的自適應(yīng)交叉、變異公式容易致和偏離正常選擇的概率范圍，導(dǎo)致遺傳迭代的結(jié)果易于“早熟”，即欺騙結(jié)果。

依照研究人員的研究成果，迭代初期，遺傳算法搜索能力會受到交叉概率選擇的影響，若交叉概率提升，則遺傳算法搜索能力便得到提升。而迭代后期，收斂速度會受到交叉概率的影響，降低交叉概率則收斂速度得到提升。遺傳代數(shù)雙曲線下降時，全局最優(yōu)解以及收斂速度會受到自適應(yīng)交叉概率的影響而效果最佳。公式如下：

（6）

式（6）中pc為自適應(yīng)交叉算子，pc1和pc2為固定交叉概率值，t為遺傳迭代次數(shù)，為最大遺傳代數(shù)；迭代初期選擇該種自適應(yīng)交叉概率，可以保證交換率，加速進化，防止遺傳算法遲滯。而在迭代后期選擇該種自適應(yīng)交叉概率則能夠保證降低交換率，使其逐步降低至常量，令收斂速度平滑。以此確保搜索空間連續(xù)、平穩(wěn)，從而降低全局最優(yōu)解的獲得難度。

自適應(yīng)變公式隨著遺傳代數(shù)指數(shù)的改變而發(fā)生改變，其變異公式為：

（7）

式（7）中pm為自適應(yīng)變異算子，pm1和pm2為固定交叉變異值，λ則是常數(shù)，其取值以種群分布決定，其取值一般大于5小于10。在迭代初期，這種變異概率能夠保證進行個體性能較差過程中，形成足夠的變異率，以此增加擾動，令解空間擴大。而迭代次數(shù)的提升、變異率的降低使得最終平滑收斂。

3.6 精英保留

在遺傳算法中，將基因結(jié)構(gòu)優(yōu)良、基因特性優(yōu)良的個體歸為精英個體。若新一代群體中加入了精英個體，那么為維持群體規(guī)模，則需要在新一代群體中選出適應(yīng)度值最小的個體，將其淘汰。在遺傳算法的優(yōu)化改進中，精英保留策略能夠影響全局收斂能力，并且該策略已經(jīng)從理論上得以證明，可以對全局收斂能力造成影響。

4 實例分析

以某試驗基地作為案例分析實例，對該試驗基地第一生產(chǎn)階段中的數(shù)據(jù)模型予以分析。首先依照多目標(biāo)設(shè)計要求，針對問題設(shè)計模型，要求在75天內(nèi)完成200畝工作量，且保證時間、成本的最低。

依照實際要求，多目標(biāo)模型可以表述為以下公式。

（8）

上述公式中，x1，x2分別表述作業(yè)決策的變量，但是依照作業(yè)時間以及實際作業(yè)總量，約束條件為

St. ；，

（9）

根據(jù)式（8）式（9）的多目標(biāo)的數(shù)學(xué)條件描述，在IAGAMO模型參數(shù)設(shè)置中：交叉算子pc取0.8，變異算子pm取0.2，最大迭代次數(shù)max_gen則取150。

5 結(jié)語

在PARETO求解優(yōu)化中，遺傳算法是主要研究方向。所以在文章中主要以遺傳算法作為基礎(chǔ)思想，以PARETO最優(yōu)解為前提，加上自適應(yīng)的交叉、變異更新機制和精英混合策略的全局搜索機制研究，進而解決了遺傳算法在局部解搜索的不足，提高IAGAMO混合算法的運算效率及收斂速度。并且在實際生產(chǎn)模型應(yīng)用中，比較IAGAMO模型與傳統(tǒng)的單目標(biāo)數(shù)學(xué)模型實例，得出本文所提出的觀點：基于PARETO的IAGAMO算法模型在多目標(biāo)問題研究中，不僅能較好地提高多目標(biāo)問題優(yōu)化解集的搜索效率，而且具有廣泛的生產(chǎn)推廣價值。

參考文獻

[1] 馬振華，劉坤林，陸漩，等.現(xiàn)代應(yīng)用數(shù)學(xué)手冊（運籌學(xué)與最優(yōu)化理論卷）[M].北京：清華大學(xué)出版社，2001.

[2] 朱學(xué)軍，陳形，李峻.多個體參與交叉的PARETO多目標(biāo)遺傳算法[J].電子學(xué)報，2000（1）：106-109.