關于計算機算法設計及其評價標準分析

李仟奕

【摘要】隨著機器學習大熱，一大批算法涌現(xiàn)出來。現(xiàn)實世界中的許多問題往往需要同時優(yōu)化幾個目標，這些目標在大多數(shù)情況下是沖突的。針對多目標優(yōu)化問題，進化算法被驗證是較為高效的。本文針對進化算法，首先概述進化算法的特點，隨后再對其評價標準展開了簡要分析。

【關鍵詞】進化算法;機器學習;評價標準;多目標

在處理許多問題時，往往需要對多個目標進行考慮，用數(shù)學的方式來說就是同時對目標函數(shù)集合進行優(yōu)化，這個過程稱為多目標優(yōu)化。在解決多目標優(yōu)化問題時，多目標進化算法是較為常用的且高效的算法。其如此受歡迎的原因主要有以下幾點：（1） 使用該類算法去解決問題時不需要對問題有預先只是，也就是說即使不了解問題也可以對其進行求解;（2） 該類基于種群的搜索方法能夠在一次運行中獲得多個解決方案，這能夠保證決策者在最終多個解中選擇自己偏向的方案;（3） 這類算法的全局搜索能力強，在負責的解空間能夠進行全局搜索，善于跳出局部最優(yōu)，找到全局最優(yōu)解。

1 不同的多目標進化算法

1.1 多目標遺傳算法

Goldberg提出了第一個處理多目標優(yōu)化的遺傳算法，并將選擇建立在個體的非支配方面。其基本思想是，首先給所考慮的種群中的所有非支配個體分配等級1，然后將被分配等級的個體刪除，隨后找到相對于其余個體的新的非支配個體，并給它們分配等級2，以此類推，直到種群中的所有個體都被分配等級。

多目標遺傳算法（MOGA）是由Fonseca和Fleming提出的。MOGA使用了進化個體之間的非支配關系來給他們計算等級。然而，有一個微小的區(qū)別。在被評價的種群中，局部的非支配個體，和以前一樣，被賦予等級1。而被支配的個體，則以種群內(nèi)支配它們的個體數(shù)量的繼承者來排序[1]。

1.2 多目標粒子群算法

Raquel和Naval提出的多目標粒子群算法（MOPSO）結合了最近鄰密度估計器的概念，用于選擇全局最佳粒子，也用于從外部非主導解檔案中刪除粒子。當選擇當前全局最優(yōu)解時，根據(jù)密度估計器對非主導解的檔案進行降序排序，并從列表的頂部隨機選擇一個粒子[2]。另一方面，當外部檔案滿了，它又會根據(jù)密度估計器的值按降序排序，并從列表的底部隨機選擇一個粒子進行刪除。這種方法使用Coello等人提出的突變算子，其方式是只在流程開始的一定代數(shù)期間應用。最后，作者采用了NSGA-II中的約束處理技術。

1.3蟻群優(yōu)化算法

蟻群優(yōu)化（ACO）是一種用于解決困難的組合優(yōu)化問題的元啟發(fā)式方法。ACO的靈感來源是真實螞蟻的信息素線索鋪設和跟隨行為，螞蟻使用信息素作為通信媒介。通過與生物實例類比，ACO是基于由（人工）信息素蹤跡為媒介的簡單代理群體（稱為（人工）螞蟻）內(nèi)部的間接通信。ACO中的信息素蹤跡作為分布式的數(shù)字信息，被螞蟻用來概率地 構建正在解決的問題的解決方案，并在算法執(zhí)行過程中對其進行調整，以反映其搜索經(jīng)驗。在初始化參數(shù)和信息素軌跡后，主循環(huán)包括三個主要步驟。首先，螞蟻根據(jù)信息素信息和可用的啟發(fā)式信息，對所考慮的問題實例構建解。一旦螞蟻完成了他們的解決方案，這些解決方案可能會在一個可選的局部搜索階段進行改進。最后，在下一次迭代開始之前，信息素軌跡將被調整以反映螞蟻的搜索經(jīng)驗[3]。

1.4 灰狼算法

灰狼算法（GWO）是最近提出的一種基于群智能的算法。GWO算法的靈感來自于自然界中的灰狼，即尋找獵物的最佳方式。GWO算法應用了自然界中相同的機制，它遵循狼群等級制度來組織狼群中的不同角色。在GWO中，狼群的成員根據(jù)狼的角色類型被分為四組，以幫助推進狩獵過程。這四組分別是阿爾法、貝塔、德爾塔和歐米伽，其中阿爾法代表了目前發(fā)現(xiàn)的最佳狩獵方案。在GWO論文原文中，為了符合自然界中灰狼的優(yōu)勢等級，將種群劃分為四組[4]。該算法的設計者進行了大量的實驗，觀察到在基準問題和一組低維真實世界的案例研究中，考慮四組可以獲得最佳的平均性能。然而，在解決大規(guī)模挑戰(zhàn)性問題時，考慮更多或更少的群體可以作為未來的工作進行研究。

1.5 人工蜂群算法

人工蜂群（ABC）算法是一種基于蜂群的元啟發(fā)式算法，由Karaboga提出，用于優(yōu)化數(shù)值問題。它的靈感來自于蜜蜂的智能覓食行為。該算法具體基于Tereshko和Loengarov提出的蜜蜂群覓食行為模型。該模型由三個基本部分組成：受雇和失業(yè)的覓食蜂，以及食物來源。前兩個組成部分，即就業(yè)和失業(yè)的覓食蜂，尋找豐富的食物來源，這是第三個組成部分，靠近它們的蜂巢。該模型還定義了兩種領先的行為模式，這是自組織和集體智慧的必要條件：招募覓食者到豐富的食物來源導致正反饋，覓食者放棄差的來源導致負反饋。在ABC中，人工覓食蜂群（代理）尋找豐富的人工食物來源（給定問題的良好解決方案）。為了應用ABC，首先將考慮的優(yōu)化問題轉換為尋找使目標函數(shù)最小化的最佳參數(shù)向量的問題。然后，人工蜜蜂隨機發(fā)現(xiàn)一組初始解向量，然后通過采用以下策略對其進行迭代改進：通過鄰域搜索機制向更好的解發(fā)展，同時放棄差的解[5]。

2 多目標進化算法評價標準

多目標進化算法領域的一個重要問題是如何對算法的性能評價。由于一個多目標進化算法單次運行就可以得到一組非支配解，所以多目標進化算法的性能評價通常是指不同非支配解集的比較。目前已經(jīng)提出了各種按性能評價指標來評價非支配解集的質量。例如，世代距離（GD）、反世代距離（IGD）、超體積（HV）、空間指標（Spacing）等等[6]。

世代距離計算的是算法結果集合M到參考集合M’的最小平均距離。計算值越小則說明算法獲得的解集質量越好。它的優(yōu)點是計算代價較小，消耗計算資源少，但具有僅度量解集的收斂性，無法評估多樣性和依賴參考集的局限性。

反世代距離計算的是每個參考點到最近的算法獲得的解的平均距離。值越小則算法的表現(xiàn)越好。相比于世代距離，它能夠同時評價算法獲得解的收斂性和多樣性，同樣，它消耗的計算資源也比較小。缺點與世代距離一樣，也是需要參考集合。

超體積計算的是算法獲得的解集與事先設定的參照點所圍成的目標空間中區(qū)域的體積。值越大就說明算法表現(xiàn)性能更好。它能夠再評價收斂性的同時也對種群的多樣性進行評價。但它也一些不足，如它消耗較多的計算資源，每次計算一次超體積都會花費更多的時間，特別是當問題的規(guī)模和維度增加時，耗時更多。并且，預先設定的參考點比較難以確定，設定不同的參考點對最終的結果影響也很大。

空間指標計算的是算法最終收斂得到的每個解到其他解的最小距離的標準差。值越小就說明最終得到的解集分布越均勻。它的優(yōu)點是能夠很好的度量解集的均勻性，但同時這也是它的缺點，因為分布均勻的點不一定是廣泛的，也就是說，不能保證算法最終獲得的解是多樣的。并且它也不能很好地度量解集的收斂性。

結束語

綜上所述，可以得出在解決多目標優(yōu)化問題方向，已經(jīng)有許許多多不同的進化算法被提出，文中只列舉了一些較為典型和經(jīng)典的算法，這些算法都具有各自不同的特點，各自適合解決的問題也是不盡相同。憑借進化算法一次運行可以獲取多個解方案以及其優(yōu)秀的全局搜索特性，它的熱度也仍在逐漸升高。同時，各種檢驗算法性能的評估標準也有許多，這里也僅僅列舉了一些較為常用的評價指標。大多數(shù)評價指標都存在自身的優(yōu)點和缺點，所以當評價某個具體進化算法的時候，通常都會選用多個評價指標來從多方面來評價性能。由此可見，對于進化算法和評價標準必須一起發(fā)展，相互促進，提升算法解決現(xiàn)實問題的能力。

{參考文獻}

[1]王瑞琪，李珂，張承慧.基于混沌多目標遺傳算法的微網(wǎng)系統(tǒng)容量優(yōu)化[J].電力系統(tǒng)保護與控制，2011，39（22）：16-22.

[2]吳小剛，劉宗歧，田立亭，丁冬，楊水麗.基于改進多目標粒子群算法的配電網(wǎng)儲能選址定容[J].電網(wǎng)技術，2014，38（12）：3405-3411.

[3]夏小云，周育人.蟻群優(yōu)化算法的理論研究進展[J].智能系統(tǒng)學報，2016，11（01）：27-36.

[4]龍文，蔡紹洪，焦建軍，伍鐵斌.一種改進的灰狼優(yōu)化算法[J].電子學報，2019，47（01）：169-175.

[5]劉三陽，張平，朱明敏.基于局部搜索的人工蜂群算法[J].控制與決策，2014，29（01）：123-128.

[6]胡涵，李振宇.多目標進化算法性能評價指標綜述[J].軟件導刊，2019，18（09）：1-4.

山東省青島市黃島區(qū)山東科技大學? 山東青島? 250000