李仟奕

【摘要】隨著機(jī)器學(xué)習(xí)大熱，一大批算法涌現(xiàn)出來(lái)。現(xiàn)實(shí)世界中的許多問(wèn)題往往需要同時(shí)優(yōu)化幾個(gè)目標(biāo)，這些目標(biāo)在大多數(shù)情況下是沖突的。針對(duì)多目標(biāo)優(yōu)化問(wèn)題，進(jìn)化算法被驗(yàn)證是較為高效的。本文針對(duì)進(jìn)化算法，首先概述進(jìn)化算法的特點(diǎn)，隨后再對(duì)其評(píng)價(jià)標(biāo)準(zhǔn)展開(kāi)了簡(jiǎn)要分析。

【關(guān)鍵詞】進(jìn)化算法;機(jī)器學(xué)習(xí);評(píng)價(jià)標(biāo)準(zhǔn);多目標(biāo)

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

1 不同的多目標(biāo)進(jìn)化算法

1.1 多目標(biāo)遺傳算法

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

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

1.2 多目標(biāo)粒子群算法

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

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

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

1.4 灰狼算法

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

1.5 人工蜂群算法

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

2 多目標(biāo)進(jìn)化算法評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

空間指標(biāo)計(jì)算的是算法最終收斂得到的每個(gè)解到其他解的最小距離的標(biāo)準(zhǔn)差。值越小就說(shuō)明最終得到的解集分布越均勻。它的優(yōu)點(diǎn)是能夠很好的度量解集的均勻性，但同時(shí)這也是它的缺點(diǎn)，因?yàn)榉植季鶆虻狞c(diǎn)不一定是廣泛的，也就是說(shuō)，不能保證算法最終獲得的解是多樣的。并且它也不能很好地度量解集的收斂性。

結(jié)束語(yǔ)

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

{參考文獻(xiàn)}

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

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

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

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

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

[6]胡涵，李振宇.多目標(biāo)進(jìn)化算法性能評(píng)價(jià)指標(biāo)綜述[J].軟件導(dǎo)刊，2019，18（09）：1-4.

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