林虹虹

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)致該研究進(jìn)展緩慢，而且多目標(biāo)與單目標(biāo)優(yōu)化問題也存在較多不同，其中單目標(biāo)問題只需優(yōu)化一個(gè)目標(biāo)或一個(gè)最優(yōu)解；但是多目標(biāo)的目標(biāo)值卻經(jīng)常形成互相沖突，即當(dāng)目標(biāo)是達(dá)到最優(yōu)時(shí)，其化目標(biāo)不一定是最優(yōu)，甚至有可能是最差的，形成多目標(biāo)化問題（Multi-objective Optimization Problem，MOP）。

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

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

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

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)仿真過程較費(fèi)時(shí)，使得整個(gè)優(yōu)化過程都會(huì)變得很慢。

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

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

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

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

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

3.1 編碼

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

3.2 初始化群體

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

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

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

x1+x2<=100

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

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

[subjected_value]=Subject_fitness（x） （3）

[fitness_value]=fitness（subjected_value） （4）

3.4 混合策略分析

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

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

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

（3）若完成上述計(jì)算后，個(gè)體期望小于0，則選擇項(xiàng)中不包含該個(gè)體。

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

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

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

（6）

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

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

（7）

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

3.6 精英保留

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

4 實(shí)例分析

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

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

（8）

上述公式中，x1，x2分別表述作業(yè)決策的變量，但是依照作業(yè)時(shí)間以及實(shí)際作業(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)的交叉、變異更新機(jī)制和精英混合策略的全局搜索機(jī)制研究，進(jìn)而解決了遺傳算法在局部解搜索的不足，提高IAGAMO混合算法的運(yùn)算效率及收斂速度。并且在實(shí)際生產(chǎn)模型應(yīng)用中，比較IAGAMO模型與傳統(tǒng)的單目標(biāo)數(shù)學(xué)模型實(shí)例，得出本文所提出的觀點(diǎn)：基于PARETO的IAGAMO算法模型在多目標(biāo)問題研究中，不僅能較好地提高多目標(biāo)問題優(yōu)化解集的搜索效率，而且具有廣泛的生產(chǎn)推廣價(jià)值。

參考文獻(xiàn)

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

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