天天看點

多目标進化算法的性能評價名額總結(一)

注:此次總結的隻是多目标性能評價名額中很少的一部分。

一、名額的常見分類方法:

1.考慮名額同時能評估的解集數目(1個或2個解集),可将名額分為一進制和二進制名額。

一進制名額:接受一個解集作為參數進行評估。

二進制名額:接受兩個解集作為參數,通過比較兩個解集的支配關系或其他方面,給出哪個解集更好的判斷。

2.多目标進化算法解集的性能評價名額主要分為三個方面:

1)解集的收斂性評價(convergence), 反映解集與真實Pareto前沿之間的逼近程度(距離)。一般我們希望所得解集距離PF盡可能近。

2)解集的均勻性評價(uniformity / evenness), 展現解集中個體分布的均勻程度。一般我們希望所得解集在PF上分布盡可能均勻。

3)解集的廣泛性評價(spread), 反映整個解集在目标空間中分布的廣泛程度。一般我們希望所得解集在PF上分布盡可能廣、盡可能完整地表達PF。

也有一些學者,不這樣分類,分為基數名額,收斂性名額,和多樣性/分布性名額,認為多樣性包括均勻性(evenness)和廣泛性/範圍(spread),具體如下:

1)基數名額:評估解集中存在的解的個數。

2)收斂性名額(精确度名額):評估解集到理論帕累托最優前沿的距離(逼近程度)。

3)多樣性名額:包括評估解集分布的均勻性(evenness)和廣泛性/範圍(spread)。均勻性展現解集中個體分布的均勻程度;廣泛性反映整個解集在目标空間中分布的廣泛程度。

二、常用性能評價名額回顧

1.GD:解集P中的每個點到參考集P *中的平均最小距離表示。GD值越小,表示收斂性越好。
多目标進化算法的性能評價名額總結(一)

其中P是算法求得的解集,P 是從PF上采樣的一組均勻分布的參考點,而dis(x,y)表示解集P中的點y和參考集P中的點x之間的歐式距離。

優點:相比HV,計算代價是輕量級的。

缺點:1)僅度量解集的收斂性,無法評估多樣性;

2)需要參考集,使得這個測度很容易不客觀;

2.convergence metric γ:解集P中的每個點到參考集P *中的最小距離的平均值。(類似GD)
多目标進化算法的性能評價名額總結(一)

其中P是算法求得的解集,P 是從PF上采樣的均勻分布的參考點集,而dis(x,y)表示參考集P中的點x和解集P中的點y之間的歐式距離。

3.Spacing:度量每個解到其他解的最小距離的标準差。Spacing值越小,說明解集越均勻。
多目标進化算法的性能評價名額總結(一)

其中表示第di個解到P中其他解的最小距離,d-表示所有di的均值。

缺點:僅度量解集的均勻性,而不考慮它的廣泛性。

4. diversity metric △:衡量所獲得的解集的廣泛程度。
多目标進化算法的性能評價名額總結(一)

參數df和dl是極端解與所獲得的非支配集的邊界解之間的歐幾裡德距;di 是所獲得的非支配解集中的連續解之間的歐幾裡德距離;

d是di 的平均值。

假設最佳非支配前沿有N個解。使用N個解,有N-1個連續距離。當隻有一個解,即N=1時,分母=分子。值得注意的是,這不是解可能的最壞情況。我們可以有一個場景,其中di 存在很大的差異。在這種情況下,度量可能大于1。是以,上述度量的最大值可以大于1.然而,良好的分布将使所有距離di 等于d并且将使得df=dl = 0(在非支配集合中存在極端解)。是以,對于最廣泛和均勻展開的非支配解集,△的分子将為零,使得路徑成本為零。對于任何其他分布,度量的值将大于零。

對于具有相同df和dl值的兩個分布,度量△在極端解中具有更高的值和更差的解的分布。

5.超體積名額(HV,Hypervolume):算法獲得的非支配解集與參照點圍成的目标空間中區域的體積。HV值越大,說明算法的綜合性能越好。
多目标進化算法的性能評價名額總結(一)

代表δ表示 Lebesgue 測度,用來測量體積。 |S| 表示非支配解集的數目, vi表示參照點與解集中第 i 個解構成的超體積。

優點:1)同時評價收斂性和多樣性;

2)無需知道PF或參考集;

缺點:1)計算複雜度高,尤其是高維多目标優化問題;

2)參考點的選擇在一定程度上決定超體積名額值的準确性;

6.反轉世代距離(IGD,Inverted Generational Distance):每個參考點到最近的解的距離的平均值。IGD值越小,說明算法綜合性能越好。
多目标進化算法的性能評價名額總結(一)

其中P是算法求得的解集,P 是從PF上采樣的一組均勻分布的參考點,而dis(x,y)表示參考集P中的點x到解集P中的點y之間的歐式距離。

優點:1)可同時評價收斂性和多樣性;

2)計算代價小;

缺點:2)需要參考集;

7.C-metric解集覆寫率:
多目标進化算法的性能評價名額總結(一)

分子表示B中被A中至少一個解支配的解的數目;分母表示B中包含的解的總數。

C(A,B)=1表示B中所有解都被A中的一些解所支配;C(A,B)=0表示B中沒有解被A中的任一解所支配。

8.IGD-NS 注:為什麼要識别非貢獻解呢?因為非貢獻解影響收斂
多目标進化算法的性能評價名額總結(一)

P是PF上均勻采樣的參考點集,P是算法獲得的解集,P’是P中的非貢獻解集。

公式的前一部分和IGD很相似,控制P的收斂性和多樣性;

第二部分是每個非貢獻解到參考集P的點的最小距離之和。

是以,IGD-NS值越小,說明收斂和多樣性越好,且解集的非貢獻解盡可能少。

9.KD:衡量是否每個解集都至少包含一個與拐點相近的解或該解集是否包括全部拐點。
多目标進化算法的性能評價名額總結(一)

其中d(vi,G)是K中的第i個真實拐點vi到G中最接近解之間的歐幾裡得距離。

KD值越小,說明檢測拐點的能力越完整;

當所獲的解集覆寫到所有的拐點時,KD=0。

三、參考集的缺陷:

不少名額在計算時都需要參考集,因為有參考集的存在,名額的客觀型就值得懷疑,如下圖所示。

多目标進化算法的性能評價名額總結(一)

解集B肯定比A要好,可是因為選用了圖中的參考集。而且,絕大多數實際問題都沒參考集。

四、支配關系的缺陷:

在高維多目标裡,很多解集或解都互相不支配,這時候支配關系這種東西就很雞肋了。

繼續閱讀