基于分布估計算法的多目標優(yōu)化

高 尚，劉 勇

（1. 江蘇科技大學計算機科學與工程學院，江蘇 鎮(zhèn)江 212003；2. 人工智能四川省高校重點實驗室，自貢 643000）

基于分布估計算法的多目標優(yōu)化

高 尚1，劉 勇2

（1. 江蘇科技大學計算機科學與工程學院，江蘇 鎮(zhèn)江 212003；2. 人工智能四川省高校重點實驗室，自貢 643000）

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

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

0 引言

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

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

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

求解多目標優(yōu)化問題的算法研究目前很熱門。目前解多目標優(yōu)化問題的算法分為兩大類：傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法。傳統(tǒng)優(yōu)化算法有加權(quán)法、層次優(yōu)化法、約束法和目標規(guī)劃法等。傳統(tǒng)優(yōu)化算法實質(zhì)上就是將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題，通過采用單目標優(yōu)化的方法達到對多目標函數(shù)的求解，這些算法往往只能得到一個解而非Pareto最優(yōu)解集。這樣得到的解往往與想要得到的最優(yōu)解集相去甚遠，遠遠滿足不了現(xiàn)代工程實踐的應用要求。智能優(yōu)化算法通過對自然現(xiàn)象的仿真模擬，建立在生物智能或物理現(xiàn)象基礎(chǔ)上的隨機搜索算法。智能優(yōu)化算法具有自組織、自適應、自學習性等特征，為解決復雜的工程問題提供了重要的技術(shù)方法。智能優(yōu)化算法還具有較高的并行性，一次運行可以求得多個Pareto最優(yōu)解，具有傳統(tǒng)算法不可比擬的優(yōu)勢。因此隨著信息技術(shù)的進步尤其是智能化技術(shù)的進步，各種智能算法的出現(xiàn)，使得利用更加科學合理的智能優(yōu)化算法成為發(fā)展趨勢。解多目標問題的智能優(yōu)化算法目前有進化算法（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]和分布估計算法（Estimation of Distribution Algorithm，EDA）[2]等。

2 分布估計算法的多目標優(yōu)化

2.1 基本分布估計算法

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

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

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

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

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

步驟2 根據(jù)適應值評價函數(shù)（目標函數(shù)）計算群體中的各個解的適應值，同時保留最好解；

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

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

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

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

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

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

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

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

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

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

步驟2 計算N個種群的不同目標函數(shù)的適應值；

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

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

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

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

3 算法測試

這里選擇了3個典型的測試函數(shù)組進行實驗，算法的群體規(guī)模為N=100，m=40，進化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作對比測試，使用文獻[7]中的多樣性指標：均值和方差，對算法求得的非劣解集進行對比評價，并將本文算法與文獻[7]中的非劣排序多目標遺傳算法( nondominated sorting genetic algorithm II，NSGA-II)，此算法是采用實數(shù)編碼，文獻[8]的規(guī)則模型分布估計算法（RM-MEDA）進行比較，如表1所示。這里NSGA-II的實驗結(jié)果來自文獻[7]，RM-MEDA的實驗結(jié)果來自文獻[8]和本文算法的實驗結(jié)果是用 Matlab語言編程運行獲得。

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

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

4 結(jié)束語

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

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

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

[3] 周樹德, 孫增圻. 分布估計算法綜述[J]. 自動化學報,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

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

人工智能四川省重點實驗室開放基金(2016RYJ03)

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