文章地址：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ū)域。采用局部主成分分析算法來建立該模型。從模型中采樣新的試用解奴紧。然后采用非支配排序來選擇解進(jìn)入下一代。
引言
多目標(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ā)展了一系列進(jìn)化算法（EA）來求解多目標(biāo)優(yōu)化問題叔遂。多目標(biāo)優(yōu)化算法（MOEA）的主要優(yōu)勢是它們是基于種群的算法，能夠在單次運(yùn)行中提供一組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種群很難平衡收斂和分布俏脊。因?yàn)閿?shù)量有限，on-line種群不能存儲在搜索期間找到的一些代表性的解肤晓。為了克服該缺陷爷贫，MOEA采用額外的種群（歸檔集）來記錄搜索過程中找到的非支配解认然。
MOEA和局部搜索的結(jié)合：memetic algorithm結(jié)合EA和啟發(fā)式局部搜索法在各種單目標(biāo)優(yōu)化問題中優(yōu)于傳統(tǒng)的進(jìn)化算法。一些多目標(biāo)memtic algorithms（MOMA）在過去十年里獲得發(fā)展漫萄。MOMA需要考慮如何為局部搜索算子評價解的質(zhì)量卷员。在多目標(biāo)遺傳局部搜索（MOGLS）中，隨機(jī)權(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上的性能握爷。實(shí)驗(yàn)結(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àn)解的繁殖可以有效地應(yīng)對連續(xù)MOP中的variable linkages景用。
分布性算法的估計（EDA）是進(jìn)化計算中一種新計算模式涵叮。另外，他們明確地從所選擇的解中提取全局統(tǒng)計信息伞插，并基于提取的信息構(gòu)建有前景的解的后驗(yàn)概率分布模型割粮。從構(gòu)建的模型中采用新的解，并全部或部分取代久的種群媚污。幾種EDA方法已經(jīng)提出來求解連續(xù)MOP問題舀瓢。然而，這些EDA在建立概率模型時沒有考慮規(guī)律性耗美。由于規(guī)律性概率建模技術(shù)已經(jīng)在統(tǒng)計學(xué)領(lǐng)域得到了廣泛的研究京髓，因此非常適合利用EDA設(shè)計中的規(guī)律性來實(shí)現(xiàn)連續(xù)MOP航缀。
作為首次在決策空間中捕獲和利用Pareto集的規(guī)律性，我們最近提出使用局部主成分分析來從先前的搜索中歐提取Pareto集的規(guī)律性模式堰怨。我們研究了兩種混合MOEAs芥玉。其中一些試驗(yàn)解由傳統(tǒng)遺傳算子生成，其他的從基于規(guī)律模式構(gòu)建的概率模型中抽樣生成备图。
主要創(chuàng)新：基于連續(xù)MOPs的規(guī)律性屬性灿巧，提出一種分布性算法的估計求解連續(xù)MOPs。該算法沒有采用交叉和變異算子產(chǎn)生新的解揽涮。另外抠藕，本文還建立了更具有統(tǒng)計意義且簡單的模型的參數(shù)估計。
算法
基本思想
EDAs構(gòu)建概率模型绞吁，用于基于從先前搜索中提取的統(tǒng)計信息來表征搜索空間中的有前景的解幢痘，然后從該模型中采樣新的試驗(yàn)解唬格。一個非常重要的問題是應(yīng)該使用什么樣的模型來完成這樣的任務(wù)家破。一個好的模型應(yīng)該易于構(gòu)建和采樣，并且能夠描述具有良好保真度的有前景的區(qū)域购岗。
我們希望決策空間中的種群能夠近似PS汰聋，且隨著搜索的推移均勻地散布在整個PS上。因此喊积，我們可以設(shè)想種群中的點(diǎn)作為以PS為質(zhì)心的隨機(jī)向量的獨(dú)立觀測烹困。而PS是一個分段連續(xù)（m-1）維流形，
有如下描述：
其中乾吻，均勻分布在分段連續(xù)（m-1）維流形上髓梅。
為n維均值為0的噪聲向量。
圖1給出了我們的基本思想绎签。
算法框架
在每一代中沒枯饿，算法需要保留大小為N的種群：
算法如下所述：
建模
將模型（2）擬合到種群中的點(diǎn)與主曲線或曲面分析高度相關(guān)，旨在找到
中一組點(diǎn)的中心曲線或曲面诡必。然而奢方，由于其模型的內(nèi)在復(fù)雜性，用于主曲線或曲面分析的大多數(shù)算法相當(dāng)昂貴爸舒。由于在RM-MEDA每一代中需要進(jìn)行建模蟋字，因此在RM-MEDA中無法承受太過復(fù)雜的模型。另一方面扭勉，當(dāng)種群
中的點(diǎn)的實(shí)際分布很難通過公式（2）準(zhǔn)確描述時鹊奖，也沒必要采用復(fù)雜的模型。
為了簡單起見涂炎，在我們實(shí)現(xiàn)中忠聚，假設(shè)的質(zhì)信是由K個流形組成
焰盗，（例如，(2)中的
在這些流形上均勻分布咒林。）熬拒，每個
是一個(m-1)維超矩形。特別地：
在二目標(biāo)情況下（m=2）垫竞，每個在
中是一個線段澎粟。
在三目標(biāo)情況下（m=3），每個在
中是一個矩形欢瞪。
假設(shè)表示
是來自
的事件活烙。那么
在事件發(fā)生的條件下，我們做出如下假設(shè)：
是在
上均勻生成的遣鼓。
啸盏，其中
是
單位矩陣，
骑祟。
在以上假設(shè)的情況下回懦，建模問題視為估計和
。為了解決該問題次企，我們首先劃分
為K分離簇
怯晕，在
中的點(diǎn)視為在A^j條件下的樣本。然后缸棵，我們能夠估計參數(shù)舟茶。
在本文中，我們使用(m-1)維局部豬成分分析（(m-1)-D Local PCA）算法為劃分的種群堵第。假設(shè)
為
的有限子集吧凉，
的樣本均值是：
其中是
的基數(shù)。
中點(diǎn)的協(xié)方差矩陣為：
第i個主分量是矩陣Cov的第i個最大特征值相關(guān)聯(lián)的單位特征向量踏志。然后將S中各點(diǎn)的仿射(m-1)維主子空間定義為：
通過(m-1)局部PCA算法最小化以下誤差函數(shù)獲得分區(qū)阀捅。
其中是
中點(diǎn)的仿射(m-1)維主要j子空間，
是從x到其在
中的投影的歐幾里德距離狰贯。
(m-1)局部PCA通過以下迭代將種群分割到
：
局部PCA算法比K-means聚類方法（聚類質(zhì)心為一點(diǎn)）更適合于分割來構(gòu)建模型(2)也搓。因?yàn)槲覀兗僭O(shè)每個質(zhì)心cluster應(yīng)該是一個(m-1)-D超矩形而不是一個點(diǎn)。
大致上涵紊，RM-MEDA的建模工作如下所示：
討論：
繁殖
需要考慮的問題是在每個中生成多少個新的試驗(yàn)解傍妒。在最終解均勻分配在PS的理想情況下，我們假設(shè)
其中摸柄，為
的(m-1)-D體積颤练。因此，圍繞
生成的新解與
成比例驱负。生成解的過程如下：
選擇
選擇的過程如下：
