一種解決群進化算法參數(shù)設置問題的最優(yōu)向量法

張志強， 王偉鈞， 施 達

(1.成都大學模式識別與智能信息處理四川省高校重點實驗室， 成都 610106; 2.成都大學計算機學院， 成都 610106)

在很多群進化算法研究中，會設置數(shù)值型參數(shù)來實現(xiàn)算法搜索的策略。例如，群進化算法如果融入禁忌搜索策略，則會出現(xiàn)控制禁忌表長度的參數(shù)；如果群進化算法采用了Memetic進化搜索策略，則會出現(xiàn)控制數(shù)據(jù)種群個數(shù)的參數(shù)，因此算法需要設置相關參數(shù)值，而設置不同的參數(shù)值，則會影響算法搜索的效率。由此看見，為了能夠解決群進化算法參數(shù)設置問題，需要設計有效的參數(shù)值設定方法。

目前有文獻針對啟發(fā)式算法參數(shù)的設置做了相應的研究。文獻[1-3]根據(jù)算法特點和參數(shù)設置的經(jīng)驗相結(jié)合，對算法的參數(shù)進行了設定，并利用設定的參數(shù)值進行了算法的測試。文獻[4-11]根據(jù)算法特點設置了多個參數(shù)預設值，并利用設定的參數(shù)預設值進行算法的測試，并根據(jù)測試結(jié)果進行數(shù)據(jù)分析，從而確定最好參數(shù)值。文獻[12]根據(jù)算法特點設置了多個參數(shù)預設值，并根據(jù)獲取的部分樣本數(shù)據(jù)采用統(tǒng)計最優(yōu)值個數(shù)大小的判定規(guī)則來確定參數(shù)值。文獻[13]提出了利用參數(shù)分析方法工具(irace)來確定算法參數(shù)的策略。文獻[14]提出了對算法參數(shù)進行方差分析來確定算法參數(shù)的策略。

雖然對于啟發(fā)式算法的參數(shù)設置方法已有相關文獻進行了研究，但有些方法實現(xiàn)比較復雜，需要利用工具進行分析，而有些方法實現(xiàn)又過于簡單，依據(jù)經(jīng)驗來直接設置參數(shù)值。從基于復雜性和有效性方面進行考慮，提出新的有效算法參數(shù)設置方法對解決參數(shù)設置問題的研究具有重要的意義。為此，以群進化算法搜索結(jié)果的樣本數(shù)據(jù)為基礎，提出一種算法參數(shù)設置的最優(yōu)向量法，將樣本數(shù)據(jù)轉(zhuǎn)換為向量進行計算，依據(jù)向量計算的判定規(guī)則進行最優(yōu)參數(shù)值的確定，以期為群進化算法中參數(shù)設置的優(yōu)化提供參考。

1 常規(guī)統(tǒng)計方法

當群進化算法進行參數(shù)設置時，通常情況下可以設置多個參數(shù)值進行算法調(diào)優(yōu)，以獲取最優(yōu)參數(shù)值。最優(yōu)參數(shù)值的確定一般可以采用常規(guī)統(tǒng)計方法來實現(xiàn)，該方法的實現(xiàn)過程如下所示。

第一步，首先根據(jù)群進化算法H的參數(shù)結(jié)構(gòu)，結(jié)合問題的求解需求，預設n組參數(shù)值集合P= {P1，P2， …，Pi，…，Pn}，其中Pi表示預設的第i組參數(shù)值。

第二步，采用群進化算法H對m個測試用例圖進行搜索測試，獲得一批測試結(jié)果的樣本數(shù)據(jù)。當群進化算法參數(shù)采用了第i(1 ≤i≤n)組參數(shù)值，對m個測試用例圖進行搜索測試后，會獲得一個由m個測試結(jié)果樣本數(shù)據(jù)構(gòu)成的向量APi，即:APi= (a1Pi，a2Pi，…，akPi，…，amPi)T(1 ≤i≤n，1≤k≤m)。

由此可見，最終獲得的測試結(jié)果樣本數(shù)據(jù)由向量組A構(gòu)成，這里A= {AP1，AP2，…，APi，…，APn}，向量組A用二維向量矩陣表示為

1≤i≤n， 1≤k≤m

(1)

式(1)中:akPi為利用第i組參數(shù)值Pi設置的群進化算法對第k個測試用例圖進行搜索的結(jié)果數(shù)據(jù)；n為參數(shù)值的組數(shù)；m為測試用例圖個數(shù)。

1≤i≤n， 1≤k≤m}|

(2)

統(tǒng)計最小值數(shù)據(jù)元素個數(shù)為

1≤i≤n， 1≤k≤m}|

(3)

這里統(tǒng)計最大值或最小值則需要根據(jù)群進化算法解決的問題需求來確定。

第四步，根據(jù)統(tǒng)計出的nbsi的值，確定最優(yōu)參數(shù)值為

(4)

式(4)中:nbsx為n個nbsi值中的最大值；x為取最大值時所對應A的列向量序號；Px為對應的第x組參數(shù)值；Popt為最優(yōu)的第opt組參數(shù)值。

從式(4)可以看出，最優(yōu)參數(shù)值確定的原則是以統(tǒng)計的樣本數(shù)據(jù)最好值個數(shù)為依據(jù)。

2 最優(yōu)向量法

從常規(guī)統(tǒng)計方法可以看出，該方法雖然可以根據(jù)樣本數(shù)據(jù)進行最優(yōu)參數(shù)值的確定。但該方法有一些缺點。

(1)當統(tǒng)計的nbsx有多個相同值時，這時無法準確判斷在多個相同值中選擇哪個值作為最優(yōu)參數(shù)值來設置群進化算法，使得其搜索能力相對最強。

(2)采用常規(guī)統(tǒng)計方法只能依據(jù)最值(根據(jù)問題的定義采用最大值或最小值)來判定參數(shù)的最優(yōu)值，根據(jù)最值在有限樣本數(shù)據(jù)量中進行判定不一定能找到最優(yōu)向量值，從而也就不一定能找到最優(yōu)參數(shù)值。

為此，提出了最優(yōu)向量法來解決這些問題。最優(yōu)向量法的主要思想是依據(jù)群進化算法的參數(shù)結(jié)構(gòu)，利用第1節(jié)方法獲取向量組A，以此構(gòu)建有限樣本數(shù)據(jù)，再以有限樣本數(shù)據(jù)量為基礎采用向量計算方式來準確判定樣本數(shù)據(jù)中的最優(yōu)向量，從而確定最優(yōu)參數(shù)值。

2.1 向量的標準化處理

在最優(yōu)向量法中，首先對每個向量進行標準化處理，這樣使得在計算向量的長度和向量間的夾角時能保證所有需要處理的向量都在同一個象限中。

(5)

如果樣本數(shù)據(jù)中數(shù)據(jù)值越小表示結(jié)果值越優(yōu)，則采用的轉(zhuǎn)換形式為

(6)

式(6)中:a′kPi為對akPi標準化處理后的結(jié)果；A″為轉(zhuǎn)換后的向量組。

如果以式(5)進行標準化處理后，A″中所有數(shù)據(jù)值都在[0，1]范圍內(nèi)，A″中所有列向量的方向都在第一象限；如果以式(6)進行標準化處理后，A″中所有數(shù)據(jù)值都在[-1，0]范圍內(nèi)，A″中所有列向量的方向都在第三象限。

2.2 向量的長度計算

為了在有限的樣本數(shù)據(jù)中準確找到最優(yōu)列向量，從而找到產(chǎn)生該最優(yōu)列向量樣本數(shù)據(jù)所對應的參數(shù)值作為最優(yōu)參數(shù)值，將針對前面已完成標準化處理的樣本數(shù)據(jù)向量組A″，計算每個列向量的長度，即計算列向量的模。向量組A″中每個列向量長度計算過程為

1≤i≤n

(7)

式(7)中:A″Pi為A″中第i個列向量；‖A″Pi‖為列向量長度。

再計算所有列向量的長度后，找出長度值最大的列向量A″Px，則A″Px為最優(yōu)向量法中找到的最優(yōu)列向量，產(chǎn)生該列向量樣本數(shù)據(jù)所對應的參數(shù)值為最優(yōu)參數(shù)值Popt，該過程為

(8)

式(8)中:A″Px為長度值最大的第x個列向量；x為取最大值時所對應A″的列向量序號。

2.3 向量間的夾角度計算

在計算列向量A″Pi的長度時，如果出現(xiàn)多個最大長度值相同的列向量，從多個相同值的列向量中找出最優(yōu)列向量則可以通過計算向量間的夾角度進行判定。

首先在向量組A″找出理想列向量A″Pideal，理想列向量A″Pideal是由向量組A″中每個行向量中其分量的最大值或者最小值構(gòu)成(這里采用最大值或最小值由求解問題的描述來決定)。由于向量組A″是經(jīng)過標準化處理的，因此，根據(jù)求解問題的描述，如果在樣本數(shù)據(jù)中取最大值為最好值，則采用式(5)進行標準化處理，這時理想列向量A″Pideal= (1，1，…，1)T， |A″Pideal| =m；如果在樣本數(shù)據(jù)中取最小值為最優(yōu)值，則采用式(6)進行標準化處理，這時理想列向量A″Pideal=(-1，-1，…，-1)T， |A″Pideal| =m。

當理想列向量確定后，依次從多個相同最大向量長度值的列向量集合S中獲取每個A″Pu(1 ≤u≤ |S|)，計算A″Pu與A″Pideal的夾角度進行判斷，如果夾角度越小，表明該向量越靠近理想向量，最優(yōu)向量法認為該向量越優(yōu)。如果理想列向量A″Pideal= (1，1，…，1)T，則夾角度變化如圖1所示；如果理想列向量A″Pideal=(-1，-1，…， -1)T，則夾角度變化如圖2所示。在圖1中可以看出，當θ1<θ2，則cosθ1> cosθ2，說明向量1比向量2更靠近理想向量，最優(yōu)向量法認為向量1比向量2更優(yōu)。在圖2中，當θ1<θ2，則cosθ1> cosθ2，說明向量1比向量2更靠近理想向量，最優(yōu)向量法認為向量1比向量2更優(yōu)。

圖1 第一象限的向量間夾角度變化情況

圖2 第三象限的向量間夾角度變化情況

產(chǎn)生最優(yōu)列向量A″Py以及對應的最優(yōu)參數(shù)值Popt為

(9)

式(9)中:S為最大向量長度值的列向量集合；A″Pu為最大長度值的列向量；θu為向量A″Pideal和A″Pu間的夾角度；A″Py為與向量A″Pideal間夾角度最小的第y個列向量；y為取最小夾角度時所對應A″的列向量序號。

2.4 最優(yōu)向量法的實現(xiàn)流程

最優(yōu)向量法的實現(xiàn)流程如圖3所示。從圖3中可以看出，當最大長度值的向量有多個時，則進入向量間夾角度值的計算判定過程，當與理想向量夾角度最小的向量有多個時，則可認為最優(yōu)向量有多個，這時可以從它們中隨機選擇一個作為最優(yōu)向量。一般來說，通過向量長度計算和向量間的夾角度計算兩個階段的判定基本上都能找出唯一的最優(yōu)向量，從而確定出最優(yōu)參數(shù)值。

圖3 最優(yōu)向量法的實現(xiàn)流程

3 實驗分析

最優(yōu)向量法采用Java編程實現(xiàn)，測試環(huán)境為Windows7(64 bit)、CPU為Intel Pentium(R) G630 (2.7 GHz)、內(nèi)存為8 GB。

3.1 求解問題的描述

進行最優(yōu)向量法驗證的求解問題采用圖論的黑白著色問題(black and white coloring problem， BWC)，該問題被文獻[15]提出并證明為NP(non-deterministic polynomial)難問題。在文獻[15]中該問題主要描述為給定一個圖G= (V，E)，其中V為圖G的頂點集，E為圖G的邊集，對圖G的頂點進行黑白著色，將集合V分割為B和W兩個頂點集，其中，B為著黑色的頂點集，W為著白色的頂點集，圖G中沒有跨越集合B和集合W中頂點的邊，即圖G中每條邊關聯(lián)的兩個頂點不能分別是B和W中的頂點，當集合B中的頂點個數(shù)確定后，則|W|的最大值是問題的最優(yōu)解。

3.2 實驗結(jié)果分析

根據(jù)求解問題的描述，設計了基于Memetic思想的群進化算法搜索BWC問題解，群進化算法中設置了禁忌表長度L和數(shù)據(jù)種群個數(shù)d作為參數(shù)。首先設定參數(shù)d和L的預設值(d，L)，這里d和L的取值范圍分別為{4， 8， 12， 16}和{10， 60， 90， 200}，可見參數(shù)預設值有16種，即P= {(4，10)， (4，60)， (4，90)， (4，200)， (8，10)， (8，60)， (8，90)， (8，200)， (12，10)， (12，60)， (12，90)， (12，200)， (16，10)， (16，60)， (16，90)， (16，200)}，n= 16。

利用群進化算法對第一組benchmark圖進行搜索測試，當每種參數(shù)預設值確定后，每個benchmark圖測試20次，每次測試30 min，由此，獲得的搜索結(jié)果如表1所示。這里為了更準確地分析出群進化算法在不同參數(shù)中的搜索能力，采用搜索結(jié)果的平均值作為樣本數(shù)據(jù)源進行最優(yōu)向量法的分析。

表1 群進化算法對第一組benchmark圖的搜索結(jié)果

以表1數(shù)據(jù)為樣本數(shù)據(jù)，根據(jù)常規(guī)統(tǒng)計方法策略利用式(2)發(fā)現(xiàn)nbs1=2、nbs3=2并且最大，由此根據(jù)式(4)準確判斷最優(yōu)參數(shù)預設值比較困難。

為了克服常規(guī)統(tǒng)計方法策略的缺點，采用最優(yōu)向量法來處理樣本數(shù)據(jù)。根據(jù)表1樣本數(shù)據(jù)得到向量組A；對向量組A利用式(5)(根據(jù)BWC問題描述，樣本數(shù)據(jù)中選擇最大值為最好值)進行向量標準化處理后得到向量組A″。

根據(jù)式(7)計算A″中每個列向量長度值為{1.9， 1.6， 2.0， 1.5， 1.3， 1.3， 1.4， 1.0， 1.5， 1.5， 1.5， 1.6， 1.6， 1.9， 1.6， 1.3}，在這組數(shù)據(jù)中，列向量A″P3的長度值最大，即||A″P3|| = 2.0，利用式(8)得到A″Px=A″P3，則Popt=Px=P3，采用最優(yōu)向量法確定的最優(yōu)參數(shù)值組合為{d= 4，L= 90}。如果有多個列向量長度最大值相同時，則按照第2.3節(jié)的式(9)進行向量間夾角度的計算來進一步判定。

利用群進化算法對第二組benchmark圖進行搜索測試，當每種參數(shù)預設值確定后，每個benchmark圖測試20次，每次測試30 min，由此獲得的搜索結(jié)果如表2所示。

根據(jù)表2的數(shù)據(jù)，不同參數(shù)值的群進化算法搜索結(jié)果中Best最大值個數(shù)和Avg最大值個數(shù)統(tǒng)計情況如表3所示。

表2 群進化算法對第二組benchmark圖的搜索結(jié)果

表3 搜索結(jié)果中最大值個數(shù)的統(tǒng)計(表2數(shù)據(jù))

在表3中，利用最優(yōu)向量法找出的參數(shù)值{d= 4，L= 90}設定的群進化算法搜索的Best最大值個數(shù)為4，Avg最大值個數(shù)為7，其算法搜索能力相對最強。

利用群進化算法對第三組benchmark圖進行搜索測試，當每種參數(shù)預設值確定后，每個圖測試10次，每次測試30 min，由此獲得的搜索結(jié)果如表4所示。

表4 群進化算法對第三組benchmark圖的搜索結(jié)果

續(xù)表

根據(jù)表4的數(shù)據(jù)進行統(tǒng)計，統(tǒng)計結(jié)果如表5所示。從表5可以看出，根據(jù)表1測試的結(jié)果利用最優(yōu)向量法確定的最優(yōu)參數(shù)值組合{d= 4，L= 90}來設置群進化算法，其能發(fā)現(xiàn)42個測試圖的最大值，能發(fā)現(xiàn)的最好值個數(shù)最多，其搜索能力相對最強。

表5 搜索結(jié)果中最大值個數(shù)的統(tǒng)計(表4數(shù)據(jù))

由此可見，針對獲取的樣本數(shù)據(jù)，可以利用最優(yōu)向量法對樣本數(shù)據(jù)進行處理，從而比較準確地確定最優(yōu)參數(shù)值。

3.3 與其他文獻算法的比較分析

為了驗證最優(yōu)向量法對已有文獻提出的群進化算法參數(shù)設置的有效性，在實驗中，將最優(yōu)向量法應用到文獻[16]提出的群進化算法的參數(shù)設置中進行測試。

文獻[16]提出了一種Memetic群進化算法(算法名:Memetic_D_O_MLCP)來解決最小負載著色問題(minimum load coloring problem，MLCP)，該問題已被其他文獻證明為NP難問題。文獻[16]提出的Memetic算法的參數(shù)設置方式是根據(jù)文獻[16]中表1的樣本數(shù)據(jù)采用常規(guī)統(tǒng)計方法確定，其算法參數(shù)被確定為{p= 12，L= 90}；而根據(jù)文獻[16]中表1的樣本數(shù)據(jù)(以Avg數(shù)據(jù)為處理對象)，采用最優(yōu)向量法策略(文獻[16]提出了值越大結(jié)果越優(yōu)的判定規(guī)則)，根據(jù)式(7)計算A″中每個列向量長度值為{2.05， 2.12， 2.36， 1.72， 2.04， 2.23， 2.08， 1.86， 1.81}，列向量A″P3的長度值最大，即||A″P3|| = 2.36，利用式(8)得到A″Px=A″P3，則Popt=Px=P3，采用最優(yōu)向量法確定的最優(yōu)參數(shù)值組合為{p= 4，L= 90}。這里參數(shù)變量p和L均為文獻[16]提出的參數(shù)變量(p為數(shù)據(jù)種群個數(shù)，L為禁忌表長度)。將參數(shù){p= 4，L= 90}設置到Memetic算法中，并利用文獻[16]提出的59個benchmark圖例進行算法測試(每個圖測試20次，每次測試30 min，與文獻[16]的實驗條件一致)。獲得的測試結(jié)果如表6所示。

在表6中，m表示文獻[16]benchmark圖中著紅色的頂點初始個數(shù)；Memetic_D_O_MLCP (p=4，L=90)代表利用最優(yōu)向量法設置參數(shù)的Memetic算法；Memetic_D_O_MLCP (p=12，L=90)代表文獻[16]中利用常規(guī)統(tǒng)計方法設置參數(shù)的Memetic算法；Best表示Memetic算法能夠搜索到的MLCP解決方案的最好值，最好值用加粗表示。

表6 Memetic_D_O_MLCP(p=4，L=90)與Memetic_D_O_MLCP(p=12，L=90)的比較結(jié)果

續(xù)表

從表6的結(jié)果分析發(fā)現(xiàn)，在59個benchmark圖例中，利用最優(yōu)向量法確定參數(shù)設置的Memetic算法能夠搜索到46個圖例的最好值，利用文獻[16]提出的常規(guī)統(tǒng)計方法確定參數(shù)設置的Memetic算法能夠搜索到43個圖例的最好值，其中兩個算法有30個圖例的搜索結(jié)果相同，由此看見，本文算法能夠搜索到的最好值個數(shù)比文獻[16]算法搜索到的最好值個數(shù)多。另外，本文算法搜索結(jié)果中有16個圖例的最好值比文獻[16]算法的結(jié)果好，從而改進了文獻[16]中16個圖例的最好值結(jié)果。

4 結(jié)論

通過提出的最優(yōu)向量法，主要用于解決群進化算法參數(shù)設置問題，其能夠根據(jù)有限樣本數(shù)據(jù)通過向量計算來準確地找到最優(yōu)參數(shù)值，從而克服常規(guī)統(tǒng)計方法策略的缺點，通過實驗結(jié)果分析表明該方法具有相應的有效性。本文最優(yōu)向量法特點如下。

(1)在提供的有限樣本數(shù)據(jù)中可以確定唯一的選擇項。

(2)提供的樣本數(shù)據(jù)量越多，確定最優(yōu)參數(shù)值的準確度越高。

(3)可以根據(jù)不同群進化算法參數(shù)結(jié)構(gòu)來構(gòu)建不同類別的樣本數(shù)據(jù)，并利用該方法進行樣本數(shù)據(jù)的處理，從而使得方法的處理過程具有通用性。