基于優(yōu)劣解距離法的群智能優(yōu)化算法性能排序

郭恩銘，方洋旺,2，彭維仕，杜澤弘

(1.西安郵電大學計算機學院，陜西 西安 710121；2.西北工業(yè)大學無人系統技術研究院， 陜西 西安 710072；3.武警工程大學裝備管理與保障學院，陜西 西安 710086； 4.上海機電工程研究所，上海 201109)

0 引言

群智能是指自然界智能行為特征和生物現象，適應性、自我學習、健壯性和效率使生物媒介(如昆蟲和鳥類)能夠承擔復雜的任務[1]。人們根據這些群智能行為特征[2]，提出了群智能優(yōu)化算法。例如：哈里斯鷹優(yōu)化算法(Harris hawk optimization，HHO)[3]、松鼠搜索算法(squirrel search algorithm，SSA)[4]、海洋捕食者算法(marine predators algorithm，MPA)[5]、被囊群優(yōu)化算法(tunicate swarm algorithm，TSA)[6]等。

但是工程實際中，如何選擇合理的群智能優(yōu)化算法，則需要對算法的性能進行分析和比較。其中，文獻[7]針對機器人群學習的性能分別對蝙蝠算法(bat algorithm，BA)、粒子群算法(particle swarm optimization，PSO)、灰狼優(yōu)化器(grey wolf optimization，GWO)進行了分析，研究中使用避障基準任務通過t檢測法對三種算法的性能對比在不同的機械手的數量(NR)和通訊范圍(CR)條件下機器人的社交學習能力，但t檢測法要求數據是來自正態(tài)分布且不能用于多組比較，最后結果是針對機器人系統選擇算法的建議。文獻[8]提出人像散度模型，來評價貓群算法(cat swarm algorithm，CSO)與粒子群和人工蜂群算法的性能。相關改進算法和原算法比較中[9-10]用的都是算法的標準差、平均值等單個指標來評估算法性能的優(yōu)劣。如何綜合地評估算法的性能對于算法的應用非常重要。

針對傳統評估指標不能合理評估算法性能的問題，提出基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的評估方法，逼近理想解排序法又簡稱優(yōu)劣解距離法。

1 TOPSIS方法原理

TOPSIS方法是一種用于許多實際問題的簡單的MCDA技術[11-12]。由于其使用的簡便性，被廣泛應用于解決多標準問題[11]。采用TOPSIS方法能夠在極大保留原始數據特點信息的基礎上清晰地反映不同方案之間的差距。

TOPSIS方法是由Hwang和Yoon[13]提出，設有m個方案P={p1,p2,…,pm}，每個方案pi(i=1,2,…,m)由n個評價屬性{ai1,ai2,…,ain}構成，即n個屬性決定一個方案。

TOPSIS方法的步驟如下：

1) 設多屬性決策矩陣A=(aij)m×n，之后對多屬性決策矩陣進行規(guī)范化得到規(guī)范化矩陣B=(bij)m×n，規(guī)范化方法為：

(1)

2) 對B進行加權得到加權矩陣C=(cij)m×n，設屬性的權重W={w1,w2,…,wn}，則加權矩陣的計算公式為：

cij=wj·bij。

(2)

3) 計算正理想解P*和負理想解P0，P*中每個屬性值都為最優(yōu)值；P0中每個屬性都為最差值，公式如下：

(3)

(4)

4) 計算每個備選方案pi到正理想解和負理想解的距離

(5)

(6)

5) 計算m個方案P對應的排序指標，計算公式：

(7)

6) 得到排序指標之后按其大小進行排序，該順序就是每個方案的優(yōu)劣排序。

2 基于TOPSIS法的群智能優(yōu)化算法 性能排序方法

本章主要介紹用于構建TOPSIS綜合評估指標的7種屬性指標，說明7種屬性數據在TOPSIS法中的處理過程以及對結果的排序。

2.1 群智能優(yōu)化算法評估屬性指標

在研究和實驗中不同問題選用哪種算法來解決，這涉及到重點考慮算法的哪種特性，實際中需要考慮算法的計算時間、精度、尋優(yōu)能力和成功率等性能。若從單一性能指標，可能會給出不合理的決策結果，因此需要綜合評估群體智能算法性能。

2.1.1平均計算時間

為了評估算法的收斂速度，定義算法的平均計算時間。令算法循環(huán)運行N次，算法的N次運行時間為t={t1,t2,…,tn}，則平均計算時間S為：

(8)

2.1.2計算精度

為了評估算法的尋優(yōu)能力，定義算法的計算精度。令N次循環(huán)運行的結果為C={c1,c2,…,cn}，理論最優(yōu)值為Z，則計算精度X為：

X=|min{C}-Z|，

(9)

測試的函數都是求最小值函數，因此在公式中的min{C}就是使用N次循環(huán)結果中實際取得的最優(yōu)值。

2.1.3算法覆蓋度

為了評估算法的全局搜索能力，定義算法的覆蓋度。覆蓋度越大所得結果越可能是全局最優(yōu)，結果的可靠性越強。

首先要得到所有搜索粒子的位置，如圖1和圖2分別對應兩次迭代的粒子位置，需要將兩次迭代的所有搜索位置都記錄下來。

圖1 第一次粒子迭代位置Fig.1 The first particle iteration position

圖2 第二次粒子迭代位置Fig.2 The second particle iteration position

之后對自變量范圍[bl,bu]進行區(qū)間劃分，自變量x中所有xi(i=1,2,…,n)都在同一范圍[bl,bu]內的隨機取值，通過計算得到在維度為dim的時候能劃分為多少區(qū)間并確定每個區(qū)間的標志。如圖1和圖2中設bl和bu分別為0和15，劃分步長大小為1，故每個維度可分為15個小區(qū)間，因此共有15×15=225個區(qū)間。

使用一維數組下標來表示每個區(qū)間的序號，通過相應的轉換公式將粒子所在高維度坐標轉換為十進制整數，該整數就是粒子所在區(qū)間的序號，即一維數組的下標。如圖3所示為圖1和圖2轉化為一維數組存儲，數字為每個區(qū)間的序號。

圖3 一維存儲數組Fig.3 One-dimensional storage array

找到區(qū)間之后對該區(qū)間進行判斷：是否已經被搜索過，若該區(qū)間未被搜索過，則將對應一維數組元素變?yōu)?，通過對數組求和得到粒子搜索的空間，計算搜索空間占所有空間的比例得到覆蓋度。

設自變量范圍[bl,bu]按劃分步長α進行區(qū)間劃分，自變量x={xi}(i=1,2,…,n)都是在同一范圍[bl,bu]內的隨機取值，區(qū)間的總數量n為自變量區(qū)間劃分數量m的維度dim次方，則總自變量空間大小的計算為：

(10)

n=mdim。

(11)

使用一維零數組A來存儲所有區(qū)間，通過式(5)和式(6)將粒子向量x={x1,x2,…,xn}轉換為一個十進制整數j，該整數就是粒子所在區(qū)間的編號。

(12)

(13)

最終得到的數組A中為1的位置就是所有粒子所搜索的區(qū)域，之后計算占比，則覆蓋度F為：

(14)

2.1.4覆蓋速率

為了評估算法的搜索速度，定義算法的覆蓋速率。上述定義的覆蓋度是在所有迭代中的所有粒子搜索空間占整個空間的比例，且知道了每個算法的平均計算時間，則覆蓋速率為覆蓋度F除以平均計算時間S得出

(15)

2.1.5最優(yōu)與最差值

為了評估算法的收斂精度和魯棒性，定義算法的最優(yōu)與最差值。令n次循環(huán)值中找到其中的更優(yōu)為Xbest和更差值為Xworst，則最優(yōu)與最差值為：

(16)

2.1.6尋優(yōu)成功率

為了評估算法的穩(wěn)定性，定義算法的尋優(yōu)成功率。設尋優(yōu)成功的精度條件為y，數組C={c1,c2,…,cn}用來存儲每次尋優(yōu)是否成功，初始化C為零數組，若成功則將對應位置的數組元素修改為1，則數組中元素值為：

(17)

之后C中元素的和除以循環(huán)次數n，則尋優(yōu)成功率L為：

(18)

2.2 TOPSIS法綜合指標構建

2.2.1構建群體智能優(yōu)化算法的多屬性決策矩陣

同一個算法在不同屬性上以及不同算法在同一屬性值上的數值存在差距，因此對相關數據進行處理，方法如下：

1) 計算精度和最優(yōu)值處理，兩者的值都是小數，在Matlab中當數值過小放入矩陣中會直接變?yōu)?，因此不能直接進行傳參，在對值的處理上首先為三種算法創(chuàng)建三個計數器，初始計數器值為0，之后對屬性值進行放大處理，循環(huán)放大10倍，直到屬性值大于1，之后將計數器的值作為該屬性的值放入矩陣中。

2) 覆蓋度和覆蓋速率處理，兩者的值不是非常小的小數，且不同算法的同一屬性值的差距并不是很大，使用計數器方法只適合兩個值相差很大的情況，進行計數之后兩種算法在同一屬性上的差距會有所縮小，因此不使用上述計數器方法，在此不斷對三種算法同時放大，每次放大10倍，直到所有的值都大于1的時候結束。

3) 其他值不作處理直接使用。

對數據值進行了上述處理，由于不同屬性數據存在不同的特性，可能有的數據越大越好，有的越小越好，因此我們要統一屬性值類型，使所有屬性數據變?yōu)樵酱笤胶谩?/p>

預處理之后計算精度和最優(yōu)值由越小越好變?yōu)樵酱笤胶?；覆蓋度、覆蓋速率、最差值和尋優(yōu)成功率類型為越大越好；平均計算時間屬于越小越好的類型，在此對其作倒數處理，使其變?yōu)樵酱笤胶谩?/p>

使用處理結果構建多屬性決策矩陣。在算法評估中共有3種算法，因此有3種方案，即m=3；算法共有7種評估屬性，即n=7。算法原始多屬性決策矩陣A如式(19)所示：

GWO ABC PSO

(19)

2.2.2歸一化群體智能優(yōu)化算法的多屬性決策矩陣

已經得到算法的多屬性決策矩陣A，之后計算每種屬性數據的平方和sum_square，對得到的平方和求根號sum_square_root，最后求每種算法的屬性在相應的sum_square_root中所占比例得到歸一化矩陣B中的對應元素數據bij，在此以最優(yōu)值屬性的計算為例給出歸一化計算的公式，則最優(yōu)值屬性的歸一化數據b11、b12、b13計算為：

sum_square=GWO最優(yōu)值+ABC最優(yōu)值+ PSO最優(yōu)值，

(20)

(21)

(22)

GWO ABC PSO

(23)

式(23)為歸一化矩陣B，B中的其他元素的歸一化計算與最優(yōu)值相同，只需將屬性數據值替換。

2.2.3確定正負理想解

權重不同產生的綜合評估結果也不一樣，這里考慮等權，認為在實際過程中7個評價指標同等重要。因此權重相同均為1/7，即：權重W中的任意元素wi(i=1,2,…,7)=1/7，在算法評估中權重矩陣C=(1/7)·B，如式(24)。目的是驗證評估方法的正確性。當然，權重的確定決策者可以通過專家打分的方法獲得，或者通過數據計算權重也可以根據實際需要設置指標的權重，然后再利用本文的方法評估算法的性能。

(24)

之后需要確定正、負理想解P*和P0，正理想解矩陣如式(25)，負理想解矩陣如式(26)。之前已經將所有屬性都統一為越大越好的類型，屬性評估每個屬性的最大數據作為正理想解中的元素；每個屬性的最小數據作為負理想解，計算如式(27)和式(28)。

(25)

(26)

(27)

(28)

2.2.4計算群智能優(yōu)化算法到正負理想解的距離以及綜合指標

根據正、負理想解以及權重矩陣可以通過式(5)和式(6)計算得到每種算法的各屬性值到正、負理想解的距離，根據式(7)計算得到每種算法的綜合指標大小，并通過綜合指標進行排序。

在綜合性能指標計算中分子部分使用的是負理想解的距離，但是也可以使用正理想解距離，二者的不同之處在于若使用負理想解，則綜合指標越大越好；使用正理想解，則綜合指標越小越好，最后的綜合指標排序上方案的排名順序是不變的。

3 仿真驗證

3.1 三種典型群體智能優(yōu)化算法概述

為了驗證本文所提方法的正確性，我們選取群體智能算法中三種典型的算法：灰狼算法、人工蜂群算法和粒子群算法。

灰狼算法于2014年提出，其原理是利用灰狼尋找獵物的最佳方式[14]搜索目標，該算法搜索能力強、靈活性好、算法實現簡單[15]。

人工蜂群算法[16]于2005年提出，主要利用蜜蜂尋找食物的原理搜索目標，該算法具有操作簡單、控制參數少、搜索精度高、魯棒性強[17]等優(yōu)點。

粒子群算法是一種基于群的搜索過程，其中每個個體稱為一個粒子，它可以記住群體和自身的最佳位置，以及速度[18]。算法具有步驟簡潔、收斂速度較快、收斂精度高等優(yōu)點，過早收斂、易陷入局部最優(yōu)等缺點。

3.2 設置測試函數

測試函數使用的是標準測試函數，將函數分為單峰U(Unimodal)、多峰M(Multimodal)、可分S(Separable)和不可分N(Non-Separable)函數。測試中使用單峰可分函數US：Step、Shpere；單峰不可分函數UN：Rosenbrock、Schwefel絕對值；多峰可分函數MS：Rastrigin；多峰不可分函數MN：Griewank、Ackley。US和UN歸于單峰函數中測試，MS和MN歸于多峰函數中測試。

3.3 單峰函數下的群體智能優(yōu)化算法性能排序

3.3.1三種典型算法的性能指標計算

單峰可分測試函數的可接受精度為10-17(尋優(yōu)成功條件)，單峰不可分函數可接受精度中Rosenbrock為10-4，Schwefel絕對值為10-10。數值是根據提前運行4個單峰測試函數，觀測三種算法的最優(yōu)值而確定的數值。

三種算法循環(huán)運行100次，每個算法的種群數為50，維度為3，每個算法迭代300次，保存每次循環(huán)三種算法的7個屬性值。表3為單峰測試函數的運行結果。

表3 單峰測試函數結果Tab.3 Unimodal test function results

3.3.2三種典型算法的綜合排序結果

表4是三種算法在4個單峰函數上的TOPSIS數據，通過觀察綜合評價指標可以得出算法由7種屬性構成的綜合性能在不同測試函數上的性能優(yōu)劣，并根據綜合性能給出算法的性能排序。

表4 單峰函數正、負理想解以及綜合評價指標Tab.4 The positive ideal solution and negative ideal solution of unimodal function and the comprehensive evaluation index

3.3.3仿真結果分析

表3中Step和Rosenbrock函數的平均計算時間T、計算精度A、覆蓋度C、覆蓋速率R、最優(yōu)值B、最差值W、尋優(yōu)成功率F屬性中算法排序如式(29)和式(30)：

(29)

(30)

通過上述表述，單從一個屬性上來說，每個屬性可以得出三種算法的排名，但若多個屬性一起，例如：Rosenbrock函數要求7個屬性排名最好時，ABC、GWO和PSO無法比較，因為7種屬性的算法排名不同，此時就很難判斷ABC、GWO和PSO兩種算法哪個最好。

此時，通過TOPSIS方法可以對多屬性值進行計算從而得出綜合評估指標，為研究者提供7種屬性同時最優(yōu)的選擇建議。如表4中的數據排名可以得出PSO算法最好，GWO算法次之，ABC算法最差。

3.4 多峰函數下的群體智能優(yōu)化算法性能排序

3.4.1三種典型算法的性能指標計算

多峰可分和多峰不可分測試函數的可接受精度為10-10，通過提前運行3個多峰測試函數觀測三種算法的最優(yōu)值而確定的數值。表5為三種算法在3個多峰函數上的測試數據。

3.4.2三種典型算法的綜合排序結果

多峰函數的TOPSIS綜合評價指標的計算過程和單峰函數相同，在此不再重復展示。表6是三種算法在多峰可分與多峰不可分函數上的TOPSIS數據。

3.4.3仿真結果分析

分析表5和表6中數據可以得出在單屬性比較中可以通過單屬性數據對三種算法進行排序，若多屬性評估則可以通過TOPSIS方法得出綜合評價指標，得出算法的排序，多峰函數中PSO算法最好，GWO算法次之，ABC算法最差。

通過上述分析可以得出TOPSIS方法是可行的，使用TOPSIS方法對多種屬性進行綜合評估就可以提供一種解決思路。

從表4和表6的綜合指標可以得出在循環(huán)運行C=100次，每個算法的種群數為N=50，維度為D=3，每個算法迭代I=300次的條件下，4種類型的函數中PSO算法綜合指標最好，GWO算法次之，ABC最差。

現在改變公共參數，觀察使用TOPSIS方法評估算法的排序是否會改變，參數改變主要從以下兩個方面：改變種群數量、改變迭代次數。設置C=50、N=100、D=3、I=100，增加種群數量，直接給出在單峰函數和多峰函數下的綜合指標，如表7所示。

觀察表7中的數據可以看出：10個函數中PSO算法最好、GWO算法次之、ABC算法最差。

表7 N=100的綜合評價指標Tab.7 N=100 comprehensive evaluation index

再次改變種群數量，設置C=50、N=200、D=3、I=100，單峰函數和多峰函數下的綜合指標如表8。

通過觀察表8的數據可以看出在Sphere函數中GWO算法已經超過PSO算法，其他函數中PSO算法優(yōu)于GWO算法，但和表7相比Rosenbrock函數中二者之間的差距變小，其他函數二者差距變大，ABC算法依舊最差。

表8 N=200的綜合評價指標Tab.8 N=200 comprehensive evaluation index

改變種群數量，設置N=300，單峰函數和多峰函數下的綜合指標如表9。

表9 N=300的綜合評價指標Tab.9 N=300 comprehensive evaluation index

觀察表9得出在Sphere函數上GWO算法優(yōu)于PSO算法，在Step、Griewank和Schwefel絕對值中依舊是PSO優(yōu)于GWO，但和表8相比二者之間的差值再次變小，其他函數差值變大。

通過比對表7、表8和表9的數據可以得出在種群數量在不斷增大的時候GWO算法的性能越來越好，而PSO算法的性能在下降，開始出現GWO算法的綜合性能優(yōu)于PSO算法，雖然有部分函數PSO和GWO之間的差值變大，但是對比表8和表9，表8中有4個函數差值變大，而表9中有2個函數差值變大。ABC算法的綜合性能也在增加，雖然增加的幅度不大。

改變迭代次數，增加迭代次數I=150，單峰和多峰函數下的綜合指標如表10。

表10 I=150的綜合評價指標Tab.10 I=150 comprehensive evaluation index

對比表7和表10的數據得出Step、Griewank、Ackley、Rosenbrock函數中PSO算法和GWO算法之間的差值減小，其他函數差值變大。

改變迭代次數I=250，函數的運行結果如表11。

對比表10和表11的數據可以看出除Rosenbrock函數外其他函數上PSO和GWO的差值在變大，且PSO的綜合指標的值比表10的值要大，而GWO的值要小。

通過比對表7、表10和表11的數據可以看出在其他參數不變，迭代次數增大的情況下，PSO算法的綜合指標越來越好，而GWO算法的綜合指標越來越差，二者之間的差值在不斷變大。

4 結論

本文提出一種基于優(yōu)劣解距離法(TOPSIS)法的評估算法綜合性能的方法。該方法定義了7項表示群體智能算法性能的指標，給出了指標的計算模型。通過對數據的分析可以得出三種算法在不同測試函數中每個單屬性下的排名，不同的排名反映了算法的不同性能上的優(yōu)劣。為了綜合評估群體智能算法的性能，利用TOPSIS方法對不同算法綜合性能進行排序，結合數據進行分析可以得出：

1) 在其他條件不變，種群數量不斷增大的時候，GWO算法的綜合性能會越來越好，PSO算法的綜合性能會變差。在種群數量大到一定值的時候，GWO算法的性能會優(yōu)于PSO算法，三種算法的綜合性能排序會變?yōu)镚WO最優(yōu)、PSO次之、ABC最差。

2) 在其他條件不變，迭代次數不斷增大的時候，PSO算法的綜合性能會越來好，GWO算法的性能會變差，二者之間的差值會不斷加大，PSO算法的性能會越來越優(yōu)于GWO算法。

仿真結果表明，本文所提方法的正確性以及適用性，不僅適用于GWO、PSO和ABC三種算法的測試及排名，還能應用于其他不同算法的評估。