【學界】多目標優化詳解

來自專欄『運籌OR帷幄』大數據人工智慧時代的運籌學

作者：三名狂客

『運籌OR帷幄』責任編輯： @愛牛氓的帆爺 （東北大學系統工程碩士生）

本篇文章是由以上作者在CSDN上的優秀文章（原文鏈接: 多目標優化詳解 - CSDN博客 ），通過『運籌OR帷幄』責任編輯整理修改而成的。

歡迎原鏈接轉發，轉載請私信 @留德華叫獸 獲取信息，盜版必究。

敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：『運籌OR帷幄』大數據人工智慧時代的運籌學

1、前言

生活中 ,許多問題都是由相互衝突和影響的多個目標組成。人們會經常遇到使多個目標在給定區域同時儘可能最佳的優化問題 ,也就是多目標優化問題。優化問題存在的優化目標超過一個並需要同時處理 ,就成為多目標優化問題。

多目標優化問題在工程應用等現實生活中非常普遍並且處於非常重要的地位 ,這些實際問題通常非常複雜、困難 ,是主要研究領域之一。自 20世紀 60年代早期以來 ,多目標優化問題吸引了越來越多不同背景研究人員的注意力。因此 ,解決多目標優化問題具有非常重要的科研價值和實際意義。

實際中優化問題大多數是多目標優化問題 ,一般情況下 ,多目標優化問題的各個子目標之間是矛盾的 ,一個子目標的改善有可能會引起另一個或者另幾個子目標的性能降低 , 也就是要同時使多個子目標一起達到最優值是不可能的 , 而只能在它們中間進行協調和折中處理 , 使各個子目標都儘可能地達到最優化。其與單目標優化問題的本質區別在於 ,它的解並非唯一 ,而是存在一組由眾多 Pareto最優解組成的最優解集合 ,集合中的各個元素稱為 Pareto最優解或非劣最優解。

2、多目標優化問題的描述

多目標優化問題用文字描述為 D 個決策變數參數、N 個目標函數、m + n個約束條件組成一個優化問題 ,決策變數與目標函數、約束條件是函數關係。在非劣解集中決策者只能根據具體問題要求選擇令其滿意的一個非劣解作為最終解。

多目標優化問題的數學形式可以如下描述 [1 ] :

min　y = f( x) = [ f1 ( x) , f2 ( x) , …, fn ( x) ]

n = 1, 2, …, N

s. t. 　gi ( x) ≤0　i = 1, 2, …, m hj ( x) = 0　j = 1, 2, …, k

x = [ x1 , x2 , …, xd , …, xD ]

xd_min ≤xd ≤xd_max　d = 1, 2, …, D

其中: x為 D維決策向量 , y為目標向量 , N 為優化目標總數 ; gi

( x) ≤0為第 i個不等式約束 , hj ( x) = 0為第 j個等式約束 , fn

( x)為第 n個目標函數; X是決策向量形成的決定空間 , Y是目標向量形成的目標空間。gi ( x) ≤0和 hj ( x) = 0確定了解的可行域 , xd_max和 xd_m in為每維向量搜索的上下限。

對於多目標優化問題中最優解或非劣最優解可進行如下定義 :

定義 1 f(x)的支配關係與 x的支配關係是一致的。

定義 2　Pareto最優解是不被可行解集中的任何解支配的解 ,若 x3 是搜索空間中一點 ,說 x3 為非劣最優解 ,當且僅當不存在 x (在搜索空間可行性域中 )使得 fn ( x) ≤fn ( x3 )成立 ,

n = 1, 2, …, N。

定義 3　給定一個多目標優化問題 f( x) , f ( x3 )是全局最優解當且僅當對任意 x (在搜索空間中 ) ,都有 f( x3 ) ≤f( x) 。

定義 4　由所有非劣最優解組成的集合稱為多目標優化問題的最優解集 ( Pareto op timal set) ,也稱為可接受解集或有效解集。

3、不同演算法在多目標優化中的應用

多目標優化問題不存在唯一的全局最優解 ,過多的非劣解是無法直接應用的 ,所以在求解時就是要尋找一個最終解。求最終解主要有三類方法 :

a)生成法 ,即先求出大量的非劣解 ,構成非劣解的一個子集 ,然後按照決策者的意圖找出最終解 ;

b)交互法 ,不先求出很多的非劣解 ,而是通過分析者與決策者對話的方式逐步求出最終解 ;

c)事先要求決策者提供目標之間的相對重要程度 ,演算法以此為依據 ,將多目標問題轉換為單目標問題進行求解。而這些主要是通過演算法來實現的 ,一直以來很多專家學者採用不同演算法解決多目標優化問題 ,如多目標進化演算法、多目標粒子群演算法和蟻群演算法、模擬退火演算法及人工免疫系統等。

（1）多目標進化演算法

多目標進化演算法 (MOEA )是一類模擬生物進化機制而形成的全局性概率優化搜索方法 ,在 20世紀 90年代中期開始迅速發展 ,其發展可以分為兩個階段。第一階段主要有兩種方法即不基於 Pareto優化的方法和基於 Pareto優化的方法 ;第二個階段就是在此基礎上提出了外部集這個概念 ,外部集存放的是當前代的所有非支配個體 ,從而使解集保持較好的分布度。這個時期提出的多目標進化演算法更多地強調演算法的效率和有效性。在這兩個階段中 , 比較典型的多目標進化演算法有 NS2 GA2[ 3 ]、PESA2和 SPEA2。對於這三種演算法而言 ,其優點較多但是其缺點也比較明顯的。如 NSGA2的優點在於運行效率高、解集有良好的分布性 ,特別對於低維優化問題具有較好的表現 ;其缺點在於在高維問題中解集過程具有缺陷 ,解集的多樣性不理想。PESA2的優點在於其解的收斂性很好 ,比較容易接近最優面 ,特別是在高維問題情況下 ;但其不足之處在於選擇操作一次只能選取一個個體 ,時間消耗很大 ,而且階級的多樣性不佳。SPEA2的優點在於可以取得一個分布度很好的解集 ,特別是在高維問題的求解上 ,但是其聚類過程保持多樣性耗時較長 ,運行效率不高。

多目標進化演算法的基本原理描述如下 : 多目標進化演算法從一組隨機生成的種群出發 ,通過對種群執行選擇、交叉和變異等進化操作 ,經過多代進化 ,種群中個體的適應度不斷提高 , 從而逐步逼近多目標優化問題的 Pareto最優解集。與單目標進化演算法不同 ,多目標進化演算法具有特殊的適應度評價機制。為了充分發揮進化演算法的群體搜索優勢 ,大多數 MOEA均採用基於 Pareto排序的適應度評價方法。在實際應用中 ,為使演算法更好地收斂到多目標優化問題的 Pareto最優解 ,現有的MOEA通常還採用了精英策略、小生境和設置外部集等關鍵技術。

MOEA一般框架所描述的演算法思想如下 : MOEA通過對種群 X ( t)執行選擇、交叉和變異等操作產生下一代種群 X ( t + 1) 。在每一代進化過程中 ,首先將種群 X ( t)中的所有非劣解個體都複製到外部集 A ( t)中 ,然後運用小生境截斷運算元剔除A ( t)中的劣解和一些距離較近的非劣解個體 ,以得到個體分布更為均勻的下一代外部集 A ( t + 1) ,並且按照概率 pe從 A ( t + 1)中選擇一定數量的優秀個體進入下代種群。在進化結束時 ,將外部集中的非劣解個體作為最優解輸出 , 目前 , MOEA研究取得了大量成果 ,已被應用於許多領域 ,如工程領域、工業領域和科學領域。其中 ,工程領域的應用最多 ,如電子工程、水利工程、風電工程和控制等。

（2）多目標粒子群演算法

粒子群優化演算法 ( PSO )是一種源於對鳥群捕食行為的研究而發明的進化計算技術 ,最先由 Barnhart博士和 Kennedy博士於 1995年提出 [ 7 ]。它是一種基於迭代的優化工具 ,系統初始化一組隨機解 ,通過迭代搜尋最優值 ,不但具有全局尋優能力 ,而且具有較強的局部尋優能力。在基本粒子群演算法 [ 8, 9 ]中 , 粒子群由 n個粒子組成 ,每個粒子的位置 xi 代表優化問題在 D維搜索空間中潛在的解。粒子在搜索空間中以一定的速度飛行 , 這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整下一步飛行方向和距離。所有的粒子都有一個被目標函數決定的適應值 , 並且知道自己到目前為止發現的最好位置 (個體極值 pi )和當前的位置 ( xi ) 。除此之外 , 每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(全局極值 pg ) , 是所有最好位置中的最優值 。

粒子群演算法的數學描述如下 :每個粒子 i包含為一個 D維的位置向量 xi = ( xi1 , xi2 , …, xiD )和速度向量 vi = ( vi1 , vi2 ,…, viD ) ,粒子 i搜索解空間時 ,保存其搜索到的最優經歷位置pi = ( pi1 , pi2 , …, piD ) 。在每次迭代開始時 ,粒子根據自身慣性和經驗及群體最優經歷位置 pg = ( pg1 , pg2 , …, pgD )來調整自己的速度向量以調整自身位置。 c1、c2 是正常數 , 稱之為加速因子 ; r1、r2 為 [ 0, 1 ]中均勻分布的隨機數 , d為 D維中的維數 ;ω是慣性權重因子。由於粒子群演算法具有高效的搜索能力 , 有利於得到多目標意義下的最優解 ;通過代表整個解集種群 ,按並行方式同時搜索多個非劣解 ,也即搜索到多個 Pareto最優解 ;同時 ,粒子群演算法的通用性比較好 ,適合處理多種類型的目標函數和約束 ,並且容易與傳統的優化方法結合 ,從而改進自身的局限性 ,更高效地解決問題。因此 ,將粒子群演算法應用於解決多目標優化問題上具有很大的優勢。

粒子群演算法思想描述如下 :初始化種群後 ,種群的大小記為 N。基於適應度支配的思想 ,將種群劃分成兩個子群 ,一個稱為非支配子集 A,另一個稱為支配子集 B ,兩個子集的基數分別為 n1、n2 ,滿足兩個子群基數之和為 N [13 ]。外部精英集用來存放每代產生的非劣解子集 A,每次迭代過程只對 B 中的粒子進行速度和位置的更新 , 並對更新後的 B 中的粒子基於適應度支配思想與 A中的粒子進行比較 ,若 xi ∈B , ? xj ∈A,使得 xi 支配 xj,則刪除 xj,使 xi 加入 A 更新外部精英集 ;且精英集的規模要利用一些技術維持在一個上限範圍內 ,如密度評估技術、分散度技術等。最後 ,演算法終止的準則可以是最大迭代次數 Tmax、計算精度ε或最優解的最大凝滯步數 Δt等。

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號後台留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

同時我們有：【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群，想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕，獲得入群傳送門。

學術界|工業界招聘、徵稿等信息免費發布，請見下圖：

推薦閱讀：