1. 基本概念
- 帶約束的單目標(biāo)優(yōu)化問題基本可以表述為 最小化一個(gè)函數(shù)f(x)苛聘，在滿足g(x)<=0的情況下
- 變量類型：連續(xù)仙粱、離散/整數(shù)阻星、二進(jìn)制或排列抗楔，甚至還有混合變量
- 變量數(shù)量N：N=10和N=1000截然不同。N太大在二階導(dǎo)數(shù)的計(jì)算上非常昂貴勾徽，需要有效地處理內(nèi)存
- 約束：不平等式g(x)和平等式h(x)的約束滑凉，可能讓搜索島嶼化，把可行空間做映射變換是個(gè)解決方案
- 多模態(tài)：存在少數(shù)幾個(gè)甚至多個(gè)局部最優(yōu)解喘帚，需要確保在搜索空間中探索了足夠多的區(qū)域
- 可區(qū)分性：可微函數(shù)==可以計(jì)算一階二階導(dǎo)數(shù)畅姊，可以使用梯度方法。但如果不可知?jiǎng)t需要全局搜索（屬于黑盒優(yōu)化領(lǐng)域）
- 評估時(shí)間：評估成本非常重要吹由，可能需要分布式計(jì)算
- 不確定性：通常假設(shè)目標(biāo)函數(shù)和約束函數(shù)是確定性的若未。然而，如果一個(gè)或多個(gè)目標(biāo)函數(shù)是不確定的倾鲫，這會引入噪音粗合，需要對不同的隨機(jī)種子重復(fù)評估求期望。
2 單目標(biāo)問題
2.1 Ackley
- Ackley 函數(shù)廣泛用于測試優(yōu)化算法乌昔。如上圖所示隙疚，在其二維形式中，它的特點(diǎn)是外部區(qū)域幾乎平坦磕道，中心有一個(gè)大孔供屉。該函數(shù)有可能使優(yōu)化算法，特別是爬山算法，陷入其眾多局部最小值之一。
- 公式推薦的參數(shù)值為：
硝全。
- 輸入域：
- 全局最小值：
Ackley
2.2 Griewank
- Griewank 函數(shù)有許多分布廣泛的局部最小值氢烘，這些最小值是有規(guī)律分布的。復(fù)雜性顯示在放大的圖中眉枕。
- 公式參數(shù)值：d 維度
- 輸入域：
- 全局最小值：
Griewank
2.3 Zakharov
- Zakharov 函數(shù)除了全局最小值之外沒有局部最小值。它在此處以二維形式顯示.
- 公式參數(shù)值：d 維度
- 輸入域：
- 全局最小值：
Zakharov
2.4 Rastrigin
- Rastrigin 函數(shù)有幾個(gè)局部最小值。它是高度多模態(tài)的录别，但最小值的位置是有規(guī)律的分布的。它以二維形式顯示在上圖中邻吞。
- 公式參數(shù)值：d 維度
- 輸入域：
- 全局最小值：
Rastrigin
2.5 rosenbrock
- rosenbrock庶灿，定義可以在中找到。它是一個(gè)非凸函數(shù)吃衅，由 Howard H. Rosenbrock 于 1960 年引入往踢，也稱為 Rosenbrock 的 valley 或 Rosenbrock 的香蕉函數(shù)。
- Rosenbrock 函數(shù)徘层，也稱為 Valley 或 Banana 函數(shù)峻呕，是基于梯度的優(yōu)化算法的流行測試問題。它以二維形式顯示在上圖中趣效。
- 該函數(shù)是單峰的瘦癌，全局最小值位于一個(gè)狹窄的拋物線谷中。然而跷敬，即使這個(gè)山谷很容易找到讯私，收斂到最小值也很困難（Picheny et al., 2012）。
- 公式參數(shù)值：d 維度
- 輸入域：
或
- 全局最小值：
image.png
3 多目標(biāo)問題
3.1 BNH
To Thanh Binh and Ulrich Korn. Mobes: a multiobjective evolution strategy for constrained optimization problems. In IN PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS (MENDEL97, 176–182. 1997.- 帕累托最優(yōu)解由解構(gòu)成
這些解決方案使用粗體連續(xù)曲線標(biāo)記。在問題中添加這兩個(gè)約束不會使無約束的帕累托最優(yōu)前沿中的任何解決方案都不可行斤寇。因此桶癣，約束可能不會給解決這個(gè)問題帶來任何額外的困難。
3.2 ZDT
Eckart Zitzler, Kalyanmoy Deb, and Lothar Thiele. Comparison of multiobjective evolutionary algorithms: empirical results. Evolutionary Computation, 8(2):173–195, 2000.- 問題構(gòu)建：
- 其中兩個(gè)目標(biāo)必須最小化牙寞。功能
可以被認(rèn)為是收斂的函數(shù)，通常
適用于帕累托最優(yōu)解（ZDT5 除外）
- ZDT1：一個(gè) 30 變量問題 (??=30) 具有凸帕累托最優(yōu)集
- ZDT2：一個(gè) 30 變量問題（??=30) 具有非凸帕累托最優(yōu)集：
- ZDT3：一個(gè) 30 變量問題（??=30) 有許多不連貫的帕累托最優(yōu)前沿：
- ZDT4：一個(gè) 10 變量 (??=10) 具有凸帕累托最優(yōu)集的問題莫秆。該問題存在多個(gè)局部帕累托最優(yōu)解间雀。因此，算法很容易陷入局部最優(yōu)镊屎。
- ZDT5：在 ZDT5 中惹挟，變量由比特環(huán)解碼》觳担總共使用了 11 個(gè)離散變量匪煌，其中??1由 30 位表示，其余的??2至??11每個(gè) 5 位党巾。功能??(??)除了數(shù)數(shù)1對應(yīng)的變量萎庭。另外，請注意目標(biāo)函數(shù)具有欺騙性齿拂，因?yàn)??(??(????))隨著 1 的數(shù)量減少驳规，但當(dāng)所有變量確實(shí)為 1 時(shí)具有最小值。
- ZDT6：一個(gè) 10 變量 (??=10) 具有非凸帕累托最優(yōu)集的問題署海。整個(gè)帕累托最優(yōu)區(qū)域的解決方案密度是不均勻的吗购。
3.3 OSY
- Osyczka 和 Kundu 使用了以下六變量測試問題
- 帕累托最優(yōu)區(qū)域是五個(gè)區(qū)域的串聯(lián)。每個(gè)區(qū)域都存在一些限制砸狞。然而捻勉，對于整個(gè)帕累托最優(yōu)區(qū)域，???_4=???_6=0. 下表顯示了五個(gè)區(qū)域中每個(gè)區(qū)域中的其他變量值以及每個(gè)區(qū)域中有效的約束刀森。
3.4 TNK
- 自從
踱启，可行目標(biāo)空間也與可行決策變量空間相同。無約束的決策變量空間由正方形中的所有解組成0≤(??1,??2)≤??. 因此研底，唯一不受約束的帕累托最優(yōu)解是???1=???2=0. 但是埠偿，包含第一個(gè)約束使該解決方案不可行。受約束的帕累托最優(yōu)解位于第一個(gè)約束的邊界上榜晦。由于約束函數(shù)是周期性的冠蒋，并且第二個(gè)約束函數(shù)也必須滿足，所以不是第一個(gè)約束邊界上的所有解都是帕累托最優(yōu)的乾胶。帕累托最優(yōu)集是斷開的抖剿。由于帕累托最優(yōu)解位于非線性約束曲面上朽寞，因此優(yōu)化算法可能難以在所有不連續(xù)的帕累托最優(yōu)集上找到解的良好分布。
3.5 DTLZ
- DTLZ1問題的特點(diǎn)是存在
個(gè)局部最優(yōu)斩郎，所以MOGA不容易找到最優(yōu)Pareto集脑融。
- DTLZ2 由于自定義M，該問題也可以被用于測試算法對大量目標(biāo)函數(shù)的問題的性能孽拷。
- DTLZ3 為了增加搜索全局最優(yōu)的難度吨掌，建議在g函數(shù)等于Rastrigin的情況下使用上面的問題半抱，即當(dāng)g滿足Rastrigin的最優(yōu)化時(shí)脓恕，該問題才能找到全局最優(yōu)
- DTLZ4問題由DTLZ2修改而來，側(cè)重于測試MOEA算法的解的分布性
- DTLZ5問題將測試MOEA收斂到曲線的能力窿侈，還將允許一種更簡單的方法(通過繪制FMFM和任何其他目標(biāo)函數(shù))來直觀地演示MOEA的性能炼幔。由于這條Pareto-最優(yōu)曲線附近的解有一個(gè)自然偏差，這個(gè)問題對于一個(gè)算法來說可能很容易解決史简。
- DTLZ6問題基于DTLZ5進(jìn)行修改乃秀，算法很難像DTLZ5那樣收斂到真正的pareto最優(yōu)前沿。
- 該問題有
個(gè)不連通的最優(yōu)Pareto 區(qū)域圆兵，用于測試算法在不同的Pareto區(qū)域里維持子種群的能力
DTLZ
3.6 DAS-CMOP
- DAS-CMOP是個(gè)可調(diào)約束的多目標(biāo)優(yōu)化基準(zhǔn)函數(shù)集跺讯。共9個(gè)基準(zhǔn)函數(shù)，其中前1-6個(gè)是2目標(biāo)的優(yōu)化問題殉农，7-9是3目標(biāo)優(yōu)化問題刀脏。
-
其約束的強(qiáng)度和難度用：(η,ζ,γ）控制，η,ζ,γ∈[0,1],這個(gè)值可以自定義超凳，也可以使用作者提供的16個(gè)參數(shù)組控制
DAS-CMOP
