文章地址：RM-MEDA: A Regularity Model Based Multiobjective Estimation of Distribution Algorithm

在溫和的條件下，可以從Karush-Kuhn-Tucker條件誘導(dǎo)出連續(xù)多目標(biāo)優(yōu)化問題的Pareto集是(m-1)-D區(qū)段連續(xù)，其中m是目標(biāo)數(shù)。根據(jù)這個規(guī)則屬性，我們提出一種基于規(guī)則模型的分布式算法多目標(biāo)估計（RM-MEDA）,用于連續(xù)多目標(biāo)優(yōu)化問題with variable linkages。在每一代中，所提出的算法通過其質(zhì)心為（M-1）-D分段連續(xù)流行的概率分布在決策空間中建模有前景的區(qū)域。采用局部主成分分析算法來建立該模型。從模型中采樣新的試用解。然后采用非支配排序來選擇解進入下一代。

引言

多目標(biāo)優(yōu)化在許多工業(yè)領(lǐng)域備受關(guān)注。一般，MOP中的目標(biāo)是相互沖突的，沒有單個解能夠同時優(yōu)化所有目標(biāo)。Pareto集/面是決策/目標(biāo)空間的一組最優(yōu)折中解。當(dāng)決策者的偏好無法獲取或難以在數(shù)學(xué)上表示時，決策者通常需要近似Pareto集或Pareto面來給予他們最終的選擇。這種近似可以是Pareto最優(yōu)解的有限集合或Pareto集/面的數(shù)學(xué)近似模型。

當(dāng)Schaffer‘s開創(chuàng)性成果發(fā)表后，發(fā)展了一系列進化算法（EA）來求解多目標(biāo)優(yōu)化問題。多目標(biāo)優(yōu)化算法（MOEA）的主要優(yōu)勢是它們是基于種群的算法，能夠在單次運行中提供一組Pareto最優(yōu)解來近似Pareto面/Pareto集。當(dāng)前的MOEA研究主要集中在以下問題。

適應(yīng)度分配和分布性維持：與標(biāo)量優(yōu)化的方法一樣，大多數(shù)MOEAs使用選擇算子將其搜索引導(dǎo)到?jīng)Q策空間中的有前景的區(qū)域。當(dāng)Pareto支配不能完成排序時，單目標(biāo)優(yōu)化中的傳統(tǒng)的選擇算子不能直接應(yīng)用到多目標(biāo)優(yōu)化中。此外，大多數(shù)MOEAs的任務(wù)是產(chǎn)生一組盡量均勻分布在Pareto面上的解。因此，MOEAs的選擇算子不能只考慮種群的收斂性。因此，為每個解分配相對適應(yīng)度值以反映其在MOEAs中的選擇效用是非常重要的工作。適應(yīng)度分配成為了過去20年的主要研究。一些技術(shù)，例如適應(yīng)度共享、聚集距離，在適應(yīng)度分配中頻繁使用來保證搜索的分布性。最近，提出了一種基于分解的適應(yīng)度分配和多樣性維持方法。

額外種群：使用當(dāng)個on-line種群很難平衡收斂和分布。因為數(shù)量有限，on-line種群不能存儲在搜索期間找到的一些代表性的解。為了克服該缺陷，MOEA采用額外的種群（歸檔集）來記錄搜索過程中找到的非支配解。

MOEA和局部搜索的結(jié)合：memetic algorithm結(jié)合EA和啟發(fā)式局部搜索法在各種單目標(biāo)優(yōu)化問題中優(yōu)于傳統(tǒng)的進化算法。一些多目標(biāo)memtic algorithms（MOMA）在過去十年里獲得發(fā)展。MOMA需要考慮如何為局部搜索算子評價解的質(zhì)量。在多目標(biāo)遺傳局部搜索（MOGLS）中，隨機權(quán)重的標(biāo)量函數(shù)在局部搜索和選擇中用作其評估函數(shù)。Memetic Pareto archived evolution strategy（M-PAES）通過使用支配排序來評價解。MOEA/D提供了多目標(biāo)優(yōu)化中標(biāo)量優(yōu)化的一般方法。

然而，在如何生成新的解集方面還沒有多少工作。當(dāng)前大多數(shù)MOEAs直接采用的是遺傳重組算子，例如：交叉和變異。在生成新解的過程中，MOPs的特征沒有被很好地利用。最近，Deb等比較了幾個重組算子在一些測試問題with variable linkages上的性能。實驗結(jié)果表明，variable linkages導(dǎo)致MOEA的難度增加，重組算子對MOEA的性能至關(guān)重要。

據(jù)觀察，在溫和條件下，連續(xù)MOP的Pareto集（決策空間）是分段連續(xù)（m-1）維流形，其中m是目標(biāo)的數(shù)量。該觀察已經(jīng)在數(shù)學(xué)規(guī)劃方法中用來近似Pareto面和Pareto集。然而，這種規(guī)律并沒有應(yīng)用到MOEAs中，除了那些隱含利用規(guī)律性的局部搜索，例如動態(tài)加權(quán)聚合方法。本文的工作將表明，基于這種規(guī)律性的新試驗解的繁殖可以有效地應(yīng)對連續(xù)MOP中的variable linkages。

分布性算法的估計（EDA）是進化計算中一種新計算模式。另外，他們明確地從所選擇的解中提取全局統(tǒng)計信息，并基于提取的信息構(gòu)建有前景的解的后驗概率分布模型。從構(gòu)建的模型中采用新的解，并全部或部分取代久的種群。幾種EDA方法已經(jīng)提出來求解連續(xù)MOP問題。然而，這些EDA在建立概率模型時沒有考慮規(guī)律性。由于規(guī)律性概率建模技術(shù)已經(jīng)在統(tǒng)計學(xué)領(lǐng)域得到了廣泛的研究，因此非常適合利用EDA設(shè)計中的規(guī)律性來實現(xiàn)連續(xù)MOP。

作為首次在決策空間中捕獲和利用Pareto集的規(guī)律性，我們最近提出使用局部主成分分析來從先前的搜索中歐提取Pareto集的規(guī)律性模式。我們研究了兩種混合MOEAs。其中一些試驗解由傳統(tǒng)遺傳算子生成，其他的從基于規(guī)律模式構(gòu)建的概率模型中抽樣生成。

主要創(chuàng)新：基于連續(xù)MOPs的規(guī)律性屬性，提出一種分布性算法的估計求解連續(xù)MOPs。該算法沒有采用交叉和變異算子產(chǎn)生新的解。另外，本文還建立了更具有統(tǒng)計意義且簡單的模型的參數(shù)估計。

算法

基本思想

EDAs構(gòu)建概率模型，用于基于從先前搜索中提取的統(tǒng)計信息來表征搜索空間中的有前景的解，然后從該模型中采樣新的試驗解。一個非常重要的問題是應(yīng)該使用什么樣的模型來完成這樣的任務(wù)。一個好的模型應(yīng)該易于構(gòu)建和采樣，并且能夠描述具有良好保真度的有前景的區(qū)域。

我們希望決策空間中的種群能夠近似PS，且隨著搜索的推移均勻地散布在整個PS上。因此，我們可以設(shè)想種群中的點作為以PS為質(zhì)心的隨機向量 $\xi \in R^n$ 的獨立觀測。而PS是一個分段連續(xù)（m-1）維流形， $\xi$ 有如下描述：

(2)

其中， $\zeta$ 均勻分布在分段連續(xù)（m-1）維流形上。 $\varepsilon$ 為n維均值為0的噪聲向量。

圖1給出了我們的基本思想。

算法框架

在每一代中沒，算法需要保留大小為N的種群：

算法如下所述：

建模

將模型（2）擬合到種群 $Pop(t)$ 中的點與主曲線或曲面分析高度相關(guān)，旨在找到 $R^n$ 中一組點的中心曲線或曲面。然而，由于其模型的內(nèi)在復(fù)雜性，用于主曲線或曲面分析的大多數(shù)算法相當(dāng)昂貴。由于在RM-MEDA每一代中需要進行建模，因此在RM-MEDA中無法承受太過復(fù)雜的模型。另一方面，當(dāng)種群 $Pop(t)$ 中的點的實際分布很難通過公式（2）準(zhǔn)確描述時，也沒必要采用復(fù)雜的模型。

為了簡單起見，在我們實現(xiàn)中，假設(shè) $\xi$ 的質(zhì)信是由K個流形組成 $\Psi^1,\cdots , \Psi^K$ ，（例如，(2)中的 $\zeta$ 在這些流形上均勻分布。），每個 $\Psi^j$ 是一個(m-1)維超矩形。特別地：

在二目標(biāo)情況下（m=2），每個 $\Psi^j$ 在 $R^n$ 中是一個線段。

在三目標(biāo)情況下（m=3），每個 $\Psi^j$ 在 $\Psi^j$ 中是一個矩形。

假設(shè) $A^j$ 表示 $\zeta$ 是來自 $\Psi^j$ 的事件。那么

在事件 $A^j$ 發(fā)生的條件下，我們做出如下假設(shè)：

$\zeta$ 是在 $\Psi^j$ 上均勻生成的。

$\varepsilon \thicksim N(0,\sigma_jI)$ ，其中 $I$ 是 $n\times n$ 單位矩陣， $\sigma_j > 0$ 。

在以上假設(shè)的情況下，建模問題視為估計 $\Psi^j, \sigma_j$ 和 $Prob(A^j)$ $(j=1,2,\cdots,K)$ 。為了解決該問題，我們首先劃分 $Pop(t)$ 為K分離簇 $S^1,\cdots,S^K$ ，在 $S^j$ 中的點視為在A^j條件下的樣本。然后，我們能夠估計參數(shù)。