基于PARETO的改進遺傳在多目標模型的研究

林虹虹

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

關鍵詞：多目標優化 遺傳算法 PARETO

中圖分類號：TP301.6 文獻標識碼：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

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

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

1 多目標優化現狀

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

2 遺傳多目標概念

一般的多目標優化問題可以定義如下[1-2]：

MinT

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

其中T。

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

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

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

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

3 遺傳的多目標改進研究

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

3.1 編碼

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

3.2 初始化群體

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

3.3 適應度值計算

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

x1+x2<=100

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

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

[subjected_value]=Subject_fitness（x） （3）

[fitness_value]=fitness（subjected_value） （4）

3.4 混合策略分析

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

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

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

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

3.5 遺傳交叉、變異自適應策略

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

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

（6）

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

自適應變公式隨著遺傳代數指數的改變而發生改變，其變異公式為：

（7）

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

3.6 精英保留

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

4 實例分析

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

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

（8）

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

St. ；，

（9）

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

5 結語

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

參考文獻

[1] 馬振華，劉坤林，陸漩，等.現代應用數學手冊（運籌學與最優化理論卷）[M].北京：清華大學出版社，2001.

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