基于分布估計(jì)算法的多目標(biāo)優(yōu)化

高 尚，劉 勇

（1. 江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003；2. 人工智能四川省高校重點(diǎn)實(shí)驗(yàn)室，自貢 643000）

基于分布估計(jì)算法的多目標(biāo)優(yōu)化

高 尚1，劉 勇2

（1. 江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003；2. 人工智能四川省高校重點(diǎn)實(shí)驗(yàn)室，自貢 643000）

論述解決多目標(biāo)優(yōu)化問題的若干解法，為了提高多目標(biāo)優(yōu)化算法的收斂性和求解精度，提出了一種分布估計(jì)的多目標(biāo)優(yōu)化算法。給出了3個(gè)典型的測試函數(shù)的pateto解集。通過4個(gè)測試函數(shù)測試，并與非劣排序多目標(biāo)遺傳算法(NSGA-Ⅱ)和規(guī)則模型分布估計(jì)算法（RM-MEDA）兩個(gè)算法進(jìn)行了比較。測試結(jié)果表明，該算法具有良好的收斂性和分布性，并且效果穩(wěn)定。

多目標(biāo)優(yōu)化；分布估計(jì)算法；收斂性

0 引言

在科學(xué)研究、工程實(shí)踐和社會生活中多目標(biāo)優(yōu)化問題(multi-Objective optimization problems，簡稱MOPs)很常見。多目標(biāo)優(yōu)化問題的各個(gè)子目標(biāo)之間是相互矛盾的，一個(gè)子目標(biāo)的目標(biāo)函數(shù)提高有可能會引起另一個(gè)或者另幾個(gè)子目標(biāo)的目標(biāo)函數(shù)性能下降，也就是說要同時(shí)使多個(gè)子目標(biāo)目標(biāo)函數(shù)同時(shí)達(dá)到最優(yōu)值是不可能的，因此求解多目標(biāo)優(yōu)化問題存在一定的難度。對于多目標(biāo)優(yōu)化問題，一個(gè)解對于某些目標(biāo)來說可能是較好的，而對于其他目標(biāo)來說可能是較差的，因此只能在它們中間進(jìn)行折中權(quán)衡和協(xié)調(diào)，使各個(gè)子目標(biāo)都盡可能地達(dá)到最優(yōu)化。存在一個(gè)折衷解的集合稱為帕累托最優(yōu)解集(Paretooptimal set)或非支配解集(nondominated set)。對于多目標(biāo)優(yōu)化問題來說，目前一般通過加權(quán)等方式轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，然后用數(shù)學(xué)優(yōu)化方法來求解，但每次只能得到一種權(quán)重情況下的最優(yōu)解，無法得到最優(yōu)解集。而且多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)和約束函數(shù)可能是非線性、不連續(xù)的或不可微，傳統(tǒng)的數(shù)學(xué)優(yōu)化方法往往效率低下，甚至失效。本文試圖采用分布估計(jì)算法來改善其性能，得到Pareto最優(yōu)解集。

1 多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型及解法

多目標(biāo)優(yōu)化問題含有n個(gè)決策變量，m個(gè)目標(biāo)變量，多目標(biāo)優(yōu)化問題可表示為

求解多目標(biāo)優(yōu)化問題的算法研究目前很熱門。目前解多目標(biāo)優(yōu)化問題的算法分為兩大類：傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法。傳統(tǒng)優(yōu)化算法有加權(quán)法、層次優(yōu)化法、約束法和目標(biāo)規(guī)劃法等。傳統(tǒng)優(yōu)化算法實(shí)質(zhì)上就是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，通過采用單目標(biāo)優(yōu)化的方法達(dá)到對多目標(biāo)函數(shù)的求解，這些算法往往只能得到一個(gè)解而非Pareto最優(yōu)解集。這樣得到的解往往與想要得到的最優(yōu)解集相去甚遠(yuǎn)，遠(yuǎn)遠(yuǎn)滿足不了現(xiàn)代工程實(shí)踐的應(yīng)用要求。智能優(yōu)化算法通過對自然現(xiàn)象的仿真模擬，建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機(jī)搜索算法。智能優(yōu)化算法具有自組織、自適應(yīng)、自學(xué)習(xí)性等特征，為解決復(fù)雜的工程問題提供了重要的技術(shù)方法。智能優(yōu)化算法還具有較高的并行性，一次運(yùn)行可以求得多個(gè)Pareto最優(yōu)解，具有傳統(tǒng)算法不可比擬的優(yōu)勢。因此隨著信息技術(shù)的進(jìn)步尤其是智能化技術(shù)的進(jìn)步，各種智能算法的出現(xiàn)，使得利用更加科學(xué)合理的智能優(yōu)化算法成為發(fā)展趨勢。解多目標(biāo)問題的智能優(yōu)化算法目前有進(jìn)化算法（Evolutionary Algorithm, EA）、遺傳算法（Genetic Algorithm，GA）、人工模擬退火算法（Simulated Annealing，SA）、蟻群優(yōu)化算法（Ant Colony Optimization, ACO）、粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）、人工免疫系統(tǒng)（Artificial Immune System, AIS）[1]和分布估計(jì)算法（Estimation of Distribution Algorithm，EDA）[2]等。

2 分布估計(jì)算法的多目標(biāo)優(yōu)化

2.1 基本分布估計(jì)算法

分布估計(jì)算法[3-6]的概念最初由Muhliebe H, Paass G在1996年提出的，分布估計(jì)算法在傳統(tǒng)的遺傳算法基礎(chǔ)上發(fā)展起來的一種全新的隨機(jī)優(yōu)化算法。在傳統(tǒng)的遺傳算法中，用若干個(gè)種群（編碼）表示優(yōu)化問題的一組候選解，種群中的每個(gè)個(gè)體都有相應(yīng)的適應(yīng)值（目標(biāo)值），然后根據(jù)適應(yīng)值（目標(biāo)值）大小進(jìn)行選擇、交叉和變異等模擬自然進(jìn)化的操作，反復(fù)進(jìn)行，對問題進(jìn)行求解；而在分布估計(jì)算法中，沒有傳統(tǒng)的交叉、變異等操作，取而代之的是概率模型的學(xué)習(xí)和采樣，分布估計(jì)算法通過一個(gè)概率模型表示候選解在空間的分布，采用統(tǒng)計(jì)學(xué)習(xí)手段從群體宏觀的角度建立一個(gè)描述解分布的概率模型，然后根據(jù)概率模型隨機(jī)采樣產(chǎn)生新的種群，選擇優(yōu)秀種群，估計(jì)概率模型，如此反復(fù)進(jìn)行，實(shí)現(xiàn)種群的進(jìn)化，直到滿足終止條件。根據(jù)概率模型的復(fù)雜程度以及不同的采樣方法，分布估計(jì)算法發(fā)展了很多不同的具體實(shí)現(xiàn)方法，但是都可以歸納為下面兩個(gè)主要步驟：首先通過對種群的評估，選擇優(yōu)秀的個(gè)體集合，建立解空間的概率模型；然后由概率模型隨機(jī)采樣產(chǎn)生新的種群，一般采用蒙特卡羅方法，對概率模型采樣得到新的種群。

在遺傳算法中，計(jì)算適應(yīng)值的大小，適應(yīng)值大的解將以較大的概率進(jìn)行復(fù)制，而分布估計(jì)算法直接挑選優(yōu)秀的個(gè)體，避免漏掉一些優(yōu)秀的個(gè)體；遺傳算法的交叉和變異可能會破壞已經(jīng)進(jìn)化好的個(gè)體，而分布估計(jì)算法利用“建立概率模型”和“采樣樣本”兩大操作取代了遺傳算法中的“選擇操作（復(fù)制操作）”、“交叉操作”和“變異操作”，以一種帶有“全局操控性”的操作模式解決了遺傳算法存在的這個(gè)缺點(diǎn)。而且分布估計(jì)算法不需要太多的參數(shù)設(shè)置，編程比遺傳算法簡單。

圖1 基本分布估計(jì)算法的步驟Fig.1 The flowchart of EDA

分布估計(jì)算法的基本步驟如下（如圖1所示）：

步驟1 在解空間內(nèi)按均勻分布隨機(jī)產(chǎn)生N個(gè)點(diǎn)（解），組成初始群體；

步驟2 根據(jù)適應(yīng)值評價(jià)函數(shù)（目標(biāo)函數(shù)）計(jì)算群體中的各個(gè)解的適應(yīng)值，同時(shí)保留最好解；

步驟3 根據(jù)適應(yīng)值，選出適應(yīng)值較好的m個(gè)個(gè)體組成優(yōu)勢群體；

步驟4 根據(jù)優(yōu)勢群體的數(shù)據(jù)，估計(jì)優(yōu)勢群體的概率分布模型；

步驟5 根據(jù)估計(jì)的概率模型進(jìn)行隨機(jī)采樣，產(chǎn)生N個(gè)新個(gè)體，組成新的種群；

步驟6 若滿足某種停止準(zhǔn)則，則算法結(jié)束，群體中的最好個(gè)體就是優(yōu)化的結(jié)果；否則算法轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

2.2 解多目標(biāo)優(yōu)化問題的分布估計(jì)算法

隨著分布估計(jì)算法的發(fā)展與應(yīng)用，該算法在解決一些實(shí)際問題時(shí)表現(xiàn)了優(yōu)越性能，一些基于分布估計(jì)算法思想的解多目標(biāo)優(yōu)化問題的算法也相繼被提出來。Khan等學(xué)者將非劣排序多目標(biāo)遺傳算法（NSGA-II）中的選擇策略和貝葉斯優(yōu)化算法(BOA)結(jié)合起來，提出了多目標(biāo)貝葉斯優(yōu)化算法(mBOA)，取得了比NSGAII更好的效果。Laumanns等學(xué)者把SPEA2和 BOA結(jié)合起來，用于解決多目標(biāo)背包問題，效果很好。Zhang和Zhou等學(xué)者提出的規(guī)則模型分布估計(jì)算法（RM_MEDA），該算法是比較經(jīng)典的分布估計(jì)算法求解多目標(biāo)優(yōu)化問題的算法，效果令人滿意。

正態(tài)分布（normal distribution）是一個(gè)在數(shù)學(xué)、物理及實(shí)際工程等領(lǐng)域都非常重要的概率分布。大自然界中很多隨機(jī)變量的概率分布都可以近似地用正態(tài)分布來描述。

由概率論知識可知，均值μ，方差σ的估計(jì)值分別為：

由計(jì)算機(jī)仿真理論可知,設(shè) u1和 u2是兩個(gè)獨(dú)立的[0,1]區(qū)間內(nèi)的均勻分布隨機(jī)數(shù)，那么同時(shí)可以產(chǎn)生2個(gè)正態(tài)分布 X ～ N(μ, σ2) 的隨機(jī)數(shù)為：

這里給出一種基于正態(tài)分布的分布估計(jì)算法的多目標(biāo)優(yōu)化算法，其步驟如下：

步驟2 計(jì)算N個(gè)種群的不同目標(biāo)函數(shù)的適應(yīng)值；

步驟3 根據(jù)不同的目標(biāo)函數(shù)，選出各自適應(yīng)性最好的m/p個(gè)解（假設(shè)有p個(gè)目標(biāo)函數(shù)），構(gòu)成子群體m個(gè)（m＜N，一般m/N比例為0.4左右），并將其中的非劣解保留至下一代，若有相同的解則只保留一個(gè)；

步驟4 根據(jù)挑選的m個(gè)優(yōu)勢個(gè)體信息，按正態(tài)分布公式（2）和（3）估計(jì)每個(gè)變量均值?iu和方差?iσ；

步驟 5 從構(gòu)建的正態(tài)分布概率模型中按公式（4）進(jìn)行隨機(jī)采樣，得到N個(gè)新解，構(gòu)成新的種群；

步驟6 若達(dá)到算法的終止條件則結(jié)束（如達(dá)到規(guī)定迭代次數(shù)nmax），否則執(zhí)行步驟2。

3 算法測試

這里選擇了3個(gè)典型的測試函數(shù)組進(jìn)行實(shí)驗(yàn)，算法的群體規(guī)模為N=100，m=40，進(jìn)化100代，其pateto解集如圖2、圖3和圖4所示。

測試函數(shù)1：

圖2 測試函數(shù)1的pateto解集Fig.2 Pareto-optimal set of test function 1

圖3 測試函數(shù)2的pateto解集Fig.3 Pareto-optimal set of test function 2

為了說明本文算法的有效性，選取典型的測試函數(shù) ZDT1、ZDT2、ZDT3、ZDT6作對比測試，使用文獻(xiàn)[7]中的多樣性指標(biāo)：均值和方差，對算法求得的非劣解集進(jìn)行對比評價(jià)，并將本文算法與文獻(xiàn)[7]中的非劣排序多目標(biāo)遺傳算法( nondominated sorting genetic algorithm II，NSGA-II)，此算法是采用實(shí)數(shù)編碼，文獻(xiàn)[8]的規(guī)則模型分布估計(jì)算法（RM-MEDA）進(jìn)行比較，如表1所示。這里NSGA-II的實(shí)驗(yàn)結(jié)果來自文獻(xiàn)[7]，RM-MEDA的實(shí)驗(yàn)結(jié)果來自文獻(xiàn)[8]和本文算法的實(shí)驗(yàn)結(jié)果是用 Matlab語言編程運(yùn)行獲得。

圖4 測試函數(shù)3的pateto解集Fig.4 Pareto-optimal set of test function 3

表1 均值和方差Table 1 The mean and variance

4 結(jié)束語

本文提出了一種分布估計(jì)的多目標(biāo)優(yōu)化算法，根據(jù)每個(gè)目標(biāo)函數(shù)挑選若干個(gè)解組成種群，然后進(jìn)行估計(jì)概率分布模型，通過仿真實(shí)驗(yàn)，證明了該算法的有效性和穩(wěn)定性。

[1] 戚玉濤, 劉芳, 劉靜樂, 任元, 焦李成. 基于免疫算法和EDA的混合多目標(biāo)優(yōu)化算法[J]. 軟件學(xué)報(bào), 2013, 24(10):2251-2266.

[2] 梁玉潔, 許峰. 自適應(yīng)混合多目標(biāo)分布估計(jì)進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用, 2014, 50(5): 46-50, 207.

[3] 周樹德, 孫增圻. 分布估計(jì)算法綜述[J]. 自動化學(xué)報(bào),2007, 33(2): 113-124.

[4] Muhliebe H, Paass G. From recombination of genes to the estimation of distributionsI. binary parameters[C]. Lecture notes in computer science. Berlin, Germany: Springer Verlag,1996, 1141: 178-187.

[5] Pelikan M, Godberg D E, paz E C. Linkage problem, distribution estimation, and Bayesian networks[J]. Evolutionary Computation. 2000, 8(3): 311-340.

[6] Paul T K, Iba H. Linear and combinatorial optimizations by estimation of distribution algorithms[C]. 9th MPS Symposium on Evolutionary Computation, IPSJ, Japan, 2002.

[7] Qi Yu-tao, Liu Fang, Liu Ji-le, Ren Yuan, Jiao Li-cheng.Hybrid immune algorithm with EDA for multi-objective optimization[J]. Journal of Software, 2013, 24(10): 2251- 2266.

[8] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[9] ZHANG Qingfu, ZHOU Aimin, JIN Yaochu． RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 41-63.

Multi-objective Optimization Problem Solved by Estimation of Distribution Algorithm

GAO Shang, LIU Yong
(1. School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003, China;2. Artificial Intelligence of Key Laboratory of Sichuan Province, Zigong 643000)

Some methods for solving multi-objective optimization problems are discussed. In order to improve the convergence and accuracy of multi-objective optimization algorithm, a multi-objective optimization algorithm based on distribution estimation is proposed. 3 typical test functions of pateto-optimal sets were given. Through the 4 test functions, compared with the Nondominated Sorting Genetic Algorithm (NSGA-II) and Regularity Model-based Mul-tiobjective estimation of distribution algorithm (RM-MEDA), the test results show that the algorithm has good convergence and distribution, and the effect is stable.

Multi-objective optimization; Estimation of distribution algorithm; Convergence

TP18

A

10.3969/j.issn.1003-6970.2017.12.005

本文著錄格式：高尚，劉勇. 基于分布估計(jì)算法的多目標(biāo)優(yōu)化[J]. 軟件，2017，38（12）：25-28

人工智能四川省重點(diǎn)實(shí)驗(yàn)室開放基金(2016RYJ03)

高尚(1972-)，男，安徽天長人，教授，博士，從事智能計(jì)算研究；劉勇(1981-)，男，四川自貢人，實(shí)驗(yàn)師，碩士，研究方向?yàn)閺?fù)雜系統(tǒng)優(yōu)化。