改進的分布估計算法求解多目標優化問題?

吳燁燁 高 尚

（江蘇科技大學計算機科學與工程學院 鎮江 212003）

1 引言

多目標優化問題（Multi-Objective Optimization Problems，MOPs）是科學研究、工程實踐和社會生活中普遍存在的一類優化問題。對于多目標優化問題，一個解對于某個目標來說可能是較好的，而對于其他目標來講可能是較差的［1］，因此，存在一個折中解的集合，稱為Pareto 最優解集（Pareto-optimal set）或非支配解集（Non-dominated set）［1］。隨著進化算法的出現與不斷發展，多目標進化算法已成為進化算法應用研究的熱點之一，前人提出了許多優秀的多目標進化算法（Multi-Objective Evolution Algorithm，MOEA），如小生境Pareto 遺傳算法NPGA［2］、強度Pareto 進化算法SPEA［3］及其改進算法SPEA-2［4］、非劣排序遺傳算法NSGA［5］及其改進算法NSGA-Ⅱ［6］等。

分布估計算法（Estimation of Distribution Algorithm，EDA）是一種新興的基于統計學原理的隨機優化算法［7］，傳統遺傳算法用交叉、變異模擬自然進化操作，分布估計算法不采用傳統的交叉、變異操作，而是采用建立概率模型和采樣的方式實現進化［8］。EDA 通過建立概率模型描述候選解在搜索空間的分布信息，采用統計學習手段從群體宏觀的角度建立一個描述解分布的概率模型，然后對概率模型隨機采樣產生新的種群，如此反復實現種群的進化［9］。隨著分布估計算法的發展以及該算法在解決一些問題時所表現出來的優越性能，基于分布估計算法的新型進化優化算法成為研究熱點。Zhang 和Zhou 等［10］提出了基于規則模型的多目標分布估計算法（RM_MEDA），該算法是在EDA 基礎上結合連續MO問題的Pareto解集在決策空間上的特性而產生的新算法［11］，非常適合于求解變量相關的連續多目標優化問題，后人多在此算法基礎上進行優化。Dai等［12］將遺傳算法與分布估計算法相結合，提出了一種混合遺傳算法和分布式估計的算法，提高算法的全局收斂能力；Mo等［13］提出了基于精英策略的多目標分布估計算法；王雪松等［14］利用差分進化算法的局部搜索能力，提出一種混合分布估計算法和差分算法的多目標優化算法；喬英等［15］將在多目標分布估計算法中引入了細菌覓食行為，提出基于細菌覓食行為的多目標分布估計算法，增強算法的局部搜索能力。

本文在RM_MEDA 的基礎上，提出了一種改進的多目標分布估計優化算法，通過正交試驗設計來初始化種群，使初始種群的分布更加均勻，以提高種群的多樣性；在種群進化時設計一種選擇算子，在算法初期充分使用分布估計算法使種群快速定位，后期則多用遺傳算法進行局部優化，提高算法的局部搜索能力；進化期間利用精英種群存放最優解，避免優秀個體流失的同時也加快種群進化，同時利用精英種群指導種群進化，最后根據評價指標和數值實驗結果對新算法的收斂性和多樣性進行了評測。

2 多目標優化問題

2.1 基本概念

多目標優化問題是在約束區域內綜合考慮各個目標求得折中最優解集。不失一般性，一個具有n個決策變量、m個目標變量的多目標優化問題可表述為

其中，x為n維決策向量，y=F(x)為m維的目標向量。gi(x)≤0，i=1，2，…，l定義了l個不等式的約束；hj(x)=0，j=1，2，…，k定義了k個等式約束。

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

定義1（可行解和可行集）滿足約束條件的解稱為可行解，可行解集合成為可行集，記為Xf。

定義2（Pareto 占優）假設xA，xB是兩個可行解，則稱與xB相比，xA是Pareto 占優的（非支配的），當且僅當

記作xA?xB，也稱為xA支配xB。

定義3（Pareto 最優解）一個解x*被稱為Pareto最優解（或非支配解），當且僅當 ??x∈Xf:x?x*。

定義4（Pareto 最優解集）Pareto 最優解集是所有Pareto 最優解的集合，也稱為非支配解集，記為Ps。

定義5（Pareto 前沿面）Pareto 最優解集中的所有Pareto 最優解對應的目標向量組成的曲面稱為Pareto前沿面PF：

2.2 RM_MEDA

Zhang 和Zhou 等學者提出的基于規則模型的多目標分布估計算法RM_MEDA［10］，是將分布估計算法融入MOEAs 的一次重要嘗試。RM_MEDA 的理論基礎是：在寬松的條件下，根據Karush-Kuhn-Tucker 準則［16-17］，含有m個目標的連續MOPs 的PS 結構在決策空間里是呈分段連續的(m-1)維流行分布［18］。因此連續的兩個目標優化問題的Pareto 解集是一個分段連續的曲線，而連續的三個目標的優化問題的Pareto 解集是一個分段連續的曲面，以此類推［19］。RM_MEDA 的算法流程如下所示：

輸入：N（種群規模），T（最大迭代次數），K（聚類數目），（目標函數）。

Step1. 初始化：令t=0；在決策空間內隨機均勻產生初始種群Pop(0)→；計算初始種群Pop(0)中每個個體的目標函數值f；

Step2. 構建模型：根據Pop(t)中每個個體的信息，運用局部主成分分析法劃分種群，然后建立PS流型結構模型；

Step3. 采樣：基于Step2 過程中建立好的概率模型，利用蒙特卡羅方法隨機采樣產生一個新的解集Q，并且計算新解集中的每個個體的目標函數值 ；

Step4. 選擇：采用NSGA-II非支配排序的選擇操作，從解集Q∪Pop(t) 中選取N個優秀個體作為Pop(t+1)；

Step5. 若t=T，則滿足終止條件，算法結束。否則，轉入Step2。

輸出：Pop(t)和每個個體對應的目標函數值。

諸多實驗表明，RM_MEDA 在求解變量相關、非線性、凹空間等復雜連續MOPs有傳統MOEAs無法比擬的優勢［18］，然而它也存在幾個明顯的不足：1）初始化種群采用隨機生成方式，隨機性較大；2）局部優化能力較差，容易陷入局部最優解；3）每次進化過程都需要根據現有的種群分布信息建立概率模型，這樣使得算法的運行時間過長，效率降低。

3 改進的多目標分布估計算法

3.1 正交設計初始化種群

正交試驗設計（Orthogonal Design，OD）是一種高效、快速、靈活的多因素、單效應變量試驗方法。將正交試驗設計應用到演化種群的初始化，可以確保演化個體在變量搜索空間均勻分散以加快算法收斂速度。

采用正交設計的方法產生初始種群，可以讓初始種群更好地均勻分布在決策空間內，相比隨機生成具有更好的分布性，同時可以提高算法對初始種群的利用能力。

3.2 種群生成方式

3.2.1 父代種群的生成方式

在進化算法中，父代種群的質量直接決定子代種群的質量，這也符合“馬太效應”的思想：好的愈好，壞的愈壞。因此，本文引入了精英種群策略：每次進化都由種群中優秀個體組成的精英種群作為父代種群進行進化。通過精英種群中個體的引導作用來產生優秀的子代個體，可以有效地防止在種群進化過程中優秀個體流失，并且可以加快算法收斂速度。算法首先將初始化種群中的優秀個體（非支配解）作為第一代父代種群，第二代及以后的父代種群則是由前一代的父子種群合并后的新種群中的優秀個體組成。隨著種群不斷進化，精英種群中的優秀個體不斷增多，當精英種群的容量超過了設定的容量N時，則利用小生境排擠技術，計算種群中所有個體的適應度，剔除相對不好的個體，維護精英種群。

這樣的生成方式，保證了父代種群中的個體都是優秀個體，在提高父代種群質量的同時也提高了子代種群的質量，加快種群進化。從另一個方面來看，即使子代種群的優劣性未知，但是父代種群中始終存放著上一代的最優個體，這樣通過父代和子代的相互促進，能更好的將優秀個體保留到下一代，加速算法收斂到真實的Pareto前沿。

3.2.2 子代種群的生成方式

分布估計算法具有良好的全局收斂能力，但最明顯的缺陷就是局部搜索能力差，容易使算法陷入局部最優。本文借助簡單的遺傳算法，利用EDA和交叉變異兩種方式來生成子代種群，在算法初期充分發揮EDA 的全局搜索能力，使種群能迅速定位，找到真實的Pareto 前沿；算法后期則主要利用交叉變異方法從“微觀”的角度進行局部尋優，發揮遺傳算法的局部搜索能力。通過分布估計算法和遺傳算法的結合，算法較好地兼顧了全局收斂能力和局部搜索能力，使算法能夠跳出局部最優，生成的個體也具有良好的多樣性。但是，如何恰當地融合兩種生成子代的方式是本節內容的重點。

2016年中國大學生消費市場總規模達到6 850億元，其中，日常生活消費總規模達4 980億元，大學生月均生活費達1 423元，另外還有教育培訓、文娛、數碼產品等其它消費支出，其中月均三餐支出為705.8元，恩格爾系數為32%，已經達到富裕水平。

本文引入一種選擇算子choose，計算公式如下：

其中，t為當前迭代次數；tmax為最大迭代次數；choose0為常數。從上述公式可以看出，隨著算法的不斷進行，迭代次數t不斷增加，chooset會越來越小。按照上面的算法思路，算法前期使用分布估計算法，算法后期使用遺傳算法，因此通過產生一個隨機數pt進行比較，且pt滿足0 ≤pt≤1，若pt大于chooset，則用遺傳算法的交叉變異方法產生子代，否則用分布估計算法產生子代。這樣即使用于判斷的隨機數pt存在一定隨機性，但隨著chooset不斷變小，pt小于chooset的概率也會跟著變小，可以減少由隨機數帶來的隨機性。這樣的策略就可以滿足在算法初期充分利用分布估計算法從全局角度搜索產生子代，快速指導種群進化使其呈現一定的規律；在算法后期則主要利用交叉變異的方法進行精確搜索。另外，在每一次迭代過程中通過概率選擇來決定每個新種群的生成方式，可以動態地均衡兩種算法的使用比例，尋優結果更加穩定。

3.3 自適應小生境技術

Goldberg 等［2］在1994 年提出將小生境技術用于多目標進化算法NPGA，小生境技術是目前應用較多的多峰函數優化方法，采用小生境形式可以在一定程度上可以保證種群在Pareto 最優區域的均勻分布［21］。本文使用小生境技術來維護精英種群：當精英種群中的個體數超過精英種群的容量時，利用小生境技術評價種群個體的好壞，刪除其中較差的個體，從而維護種群的多樣性。小生境技術利用小生境種群可以實現對多個局部極值進行同步搜索，能有效避免算法的早熟收斂。

適應度計算方法為

其中：F(p)為個體p的適應度；Q為精英種群內非支配解的數量；sh(dpq)為個體p和q的共享函數；dpq為它們之間目標向量的歐式距離為 常 數 ；σshare為小生境半徑。

一般小生境算法是在一開始就人為設定小生境半徑σshare，這就存在隨機性，因為σshare的值會直接影響精英種群的分布性：如果σshare過大，那么半徑內的個體過多，在只保留一個優秀個體的要求下，其余很多優秀個體就會被淘汰，影響了小生境算法的收斂速度；如果σshare過小，那么應該被淘汰的個體就可能被免于淘汰，從而達不到預期效果。而且因為缺乏先驗知識，很難給出恰當的σshare值，因此本文使用一種簡單的方式來動態調整小生境半徑：計算精英種群中每個個體到其他個體的歐式距離的最小值，小生境半徑則為這些最小值的平均值，如式（9）所示：

這樣計算得到的小生境半徑，近似反應了當前精英種群內部個體的理想分布，而且可以排除相似性較高的個體，也不需要過多的先驗知識，因而該方法能夠較準確地將密度大的個體從精英種群中剔除，維護種群的多樣性。

3.4 算法流程

參數：N（種群大小），T（最大迭代次數），Pop（當前種群），A（精英種群），Q（子代種群）

Step1. 利用4.2 節中的正交設計初始化種群Pop(0)，t=1；

Step3. 將種群Pop(t-1)中的非劣解存入精英種群A中；

Step4.判斷精英種群A的容量是否超出種群容量N，若沒有，則轉入Step 5，否則利用4.3節中的自定義小生境技術刪除個體直到精英種群A 的大小變為N；

Step5.若t=T 則達到算法終止條件，算法結束，輸出精英種群A 及每個個體的目標函數值；否則轉Step 6；

Step6. 根據4.3 節中介紹的選擇因子公式，計算chooset；隨機產生一個[0，1]內的隨機數pt，若pt＜chooset，則轉入Step 7；否則轉入Step 8；

Step7.對精英種群A執行分布估計方式產生新種群Q；

Step8.對精英種群A執行NSGA-II的交叉變異方法產生新種群Q；

Step9.Pop(t)=Q∪A，即合并子代種群和父代種群，t=t+1，轉入Step 3。

4 數值實驗

4.1 算法性能指標

多目標優化算法性能的評價主要體現在收斂性與分布性。Deb 等在文獻［6］中提出的收斂性指標? 和多樣性指標Δ 來評價。

1）收斂性指標：

其中，n為所獲得的非支配解的個數，di為第i個非支配解與理論Pareto 前沿的最小距離。收斂性指標越小，說明算法越逼近Pareto最優前沿。

2）多樣性指標：

其中，di相鄰兩個個體之間的歐式距離；dˉ為di的均值；df、dl分別為算法獲得的邊界解與相應極端解之間的距離。Δ 指標可以反應非劣解能否均勻的分布在整個解空間內，因此多樣性指標也被稱為分布指標。Δ 指標越小，表示所求的Pareto最優解集在解空間中的分布越均勻。

4.2 數值實驗及分析

本文的實驗選取ZDT1、ZDT2、ZDT3、ZDT6 這四個常用的多目標測試函數進行數值實驗，并與NSGA-II、RM_MEDA 這兩個經典多目標優化算法進行比較。參數設置：種群規模N=100，最大迭代次 數T=250 ，NSGA-II 的 交 叉 概 率pc=0.9 ，ηc=20，ηm=20，變異概率pm=1/n（n為種群的維數），RM_MEDA 和本文算法的聚類數目K=5，簇擴展系數為0.25，最大訓練次數為50，本文算法的選擇算子choose0=1。實驗分別對三種算法均獨立運行20 次，將得出的收斂度指標和多樣性指標分別取均值、方差，匯總統計在表1和表2中。

從表1 和表2 可以看出，無論是收斂性還是多樣性，本文算法都優于另兩種算法，對于較復雜的ZDT6測試函數，三種算法的性能都有下降，但整體來說本文算法求得的Pareto 前沿在收斂性和分布性上仍優于NSGA-II和RM_MEDA。

表1 收斂度指標? 的統計結果

表2 多樣性指標Δ 的統計結果

圖1、圖2 分別展示了RM_MEDA 和本文算法對四個測試函數的仿真實驗，其中，測試函數的理想Pareto 前 沿 可 以 從https：//www.cs.cinvestav.mx/～emoobook/apendix-d/apendix-d.html得到。

從圖1～圖4 可以看出，ZDT1～ZDT3 這三個簡單的測試函數，本文算法都找到的Pareto 最優解集都收斂到了理想Pareto 前沿，相比RM_MEDA 算法性能相差不大；而對于ZDT6 測試函數，RM_MEDA并沒有收斂到理想的Pareto 前沿，這是因為ZDT6的前沿分布不均勻，而RM_MEDA 局部收斂性能不強，導致算法最終陷入局部最優，而本文算法則避免了這樣的問題。

圖1 RM_MEDA和本文算法在ZDT1算法上的實驗結果對比

圖2 RM_MEDA和本文算法在ZDT2算法上的實驗結果對比

圖3 RM_MEDA和本文算法在ZDT3算法上的實驗結果對比

圖4 RM_MEDA和本文算法在ZDT6算法上的實驗結果對比

5 結語

本文提出了一種改進的多目標分布估計算法，利用正交設計來初始化分布較均勻的初始種群，提高了種群多樣性，也讓初始種群得以充分利用；利用分布估計算法和遺傳算法兩種進化方式來生成子代種群，均衡地調節了算法的全局和局部搜索能力；引入精英種群，存放最優解的同時，也作為父代種群指導種群進化，提高算法的收斂性。仿真實驗的結果也證明了該算法具有較好的收斂性和多樣性。