摘  要： 提出一種帶淘汰制的自適應(yīng)參數(shù)調(diào)整方法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法在計(jì)算效果上有一定程度的提高，同時(shí)解決了參數(shù)設(shè)置問(wèn)題。
關(guān)鍵詞： 聯(lián)盟競(jìng)賽算法；魯棒性；全局搜索；自適應(yīng)參數(shù)調(diào)整；淘汰制

　聯(lián)盟競(jìng)賽算法LCA[1]（League Championship Algorithm）是一種基于迭代的群體智能優(yōu)化算法。
參考文獻(xiàn)[1]中的實(shí)驗(yàn)結(jié)果表明，聯(lián)盟競(jìng)賽算法相比粒子群優(yōu)化算法，計(jì)算效果和效率都有一定的優(yōu)勢(shì)，因此該算法具有較好的應(yīng)用前景。目前國(guó)內(nèi)外對(duì)該算法做的研究主要集中在算法的擴(kuò)展上，參考文獻(xiàn)[2]和參考文獻(xiàn)[3]都是將算法擴(kuò)展為能夠解決約束優(yōu)化問(wèn)題的算法，參考文獻(xiàn)[4]將算法擴(kuò)展為解決組合優(yōu)化問(wèn)題的算法。
通過(guò)初步分析和實(shí)驗(yàn)證明，算法主要存在兩個(gè)缺點(diǎn)：（1）需手動(dòng)設(shè)置多個(gè)參數(shù)，且在算法的運(yùn)行中參數(shù)是靜態(tài)不變的，因此對(duì)每個(gè)優(yōu)化問(wèn)題，需嘗試不同的參數(shù)組合分別運(yùn)行算法以找到一個(gè)較好的結(jié)果；（2）算法魯棒性較低，在優(yōu)化不同函數(shù)時(shí)，全局搜索能力差距較大，大大降低算法的實(shí)用性。目前還沒(méi)有文獻(xiàn)解決這些問(wèn)題。
　針對(duì)以上兩個(gè)缺點(diǎn)，本文提出一種帶淘汰制的自適應(yīng)聯(lián)盟競(jìng)賽算法ALCAKS（Adaptive League Championship Algorithm with Knockout System）。
1 聯(lián)盟競(jìng)賽算法
1.1 聯(lián)盟競(jìng)賽算法基本流程
（1）初始化團(tuán)隊(duì)數(shù)量、陣型、比賽輪數(shù)S等，令當(dāng)前迭代次數(shù)t=0；
（2）產(chǎn)生一個(gè)賽季的比賽賽程；
（3）將最優(yōu)適應(yīng)值的團(tuán)隊(duì)陣型保存到Xt；
（4）根據(jù)第t輪的比賽賽程進(jìn)行比賽，并按照一定規(guī)則判斷比賽輸贏；
（5）t=t+1，若t>S，執(zhí)行步驟（9）；
（6）更新團(tuán)隊(duì)陣型：每個(gè)團(tuán)隊(duì)產(chǎn)生一個(gè)新陣型，若新陣型適應(yīng)值比當(dāng)前陣型適應(yīng)值更優(yōu)，則替換當(dāng)前陣型；
（7）判斷是否要產(chǎn)生新賽程，若是則根據(jù)某種規(guī)則產(chǎn)生新賽程并替換舊賽程，否則繼續(xù)使用舊賽程；
（8）轉(zhuǎn)步驟（3）；
（9）輸出全局最優(yōu)解Xs。

    綜上所述，算法要求手動(dòng)設(shè)置pc、c1和c2三個(gè)參數(shù)，其在運(yùn)行中是靜態(tài)不變的。對(duì)每個(gè)優(yōu)化問(wèn)題，需設(shè)置不同的參數(shù)組合分別運(yùn)行算法以找到一個(gè)較好的結(jié)果。此外，本文通過(guò)實(shí)驗(yàn)（實(shí)驗(yàn)結(jié)果見(jiàn)2.2節(jié)）發(fā)現(xiàn)算法魯棒性較低。針對(duì)這些問(wèn)題，本文提出一種帶淘汰制的自適應(yīng)參數(shù)調(diào)整方法。
2 帶淘汰制的自適應(yīng)聯(lián)盟競(jìng)賽算法
    為下文提出自適應(yīng)參數(shù)調(diào)整方法和引入淘汰制提供基礎(chǔ)，本文先給出一種檢測(cè)收斂過(guò)慢和陷入局部極值的方法。
2.1 檢測(cè)收斂速度
     為檢測(cè)收斂速度，在算法中增加變量數(shù)組Gbest，Gbest[i]保存算法迭代到第i輪時(shí)的最好適應(yīng)值。對(duì)于求解函數(shù)最小值時(shí)，任意i（0≤i≤S-2）都滿足Gbest[i+1]≤Gbest[i]。當(dāng)算法在第i輪（i≥w）出現(xiàn)|Gbest[i]-Gbest[i-w]|小于某閾值時(shí)，認(rèn)為算法收斂過(guò)慢或陷入局部極值，其中w是窗口大小。為區(qū)分收斂過(guò)慢與陷入局部極值，再增加一個(gè)變量數(shù)組Tbest，Tbest[i]保存算法在第i輪中產(chǎn)生的新團(tuán)隊(duì)陣型中的最好適應(yīng)值。如圖2和圖3所示，給出算法在優(yōu)化Rosenbrock函數(shù)時(shí)出現(xiàn)的收斂過(guò)慢及陷入局部極值這兩種結(jié)果，每種結(jié)果隨著比賽輪數(shù)i的增加，Gbest[i]和Tbest[i]的變化曲線。
    在正常收斂速度下Gbest曲線穩(wěn)步下降，Tbest曲線波動(dòng)較大；從圖2看出，當(dāng)算法收斂過(guò)慢時(shí)，如在第80輪~180輪迭代期間，Gbest曲線無(wú)變化，但Tbest曲線波動(dòng)較大；從圖3看出，當(dāng)算法陷入局部極值時(shí)，Gbest曲線和Tbest曲線變化幅度都較小，兩條曲線最終重疊一起。

根據(jù)上述的實(shí)驗(yàn)結(jié)果和分析得出：
　（1）固定pc值，c1和c2值越大，收斂速度越快。當(dāng)c1和c2值過(guò)小時(shí)，會(huì)導(dǎo)致收斂過(guò)慢而最終無(wú)法找到全局最優(yōu)值。
?。?）固定c1和c2值，pc值越小，收斂速度越快，全局尋優(yōu)能力會(huì)稍微變?nèi)酢?br /> 根據(jù)以上觀點(diǎn)，本文提出自適應(yīng)參數(shù)調(diào)整方案如下：
　（1）算法初始時(shí)，設(shè)置較大參數(shù)值，較大pc值使算法專(zhuān)注于全局搜索，保持團(tuán)隊(duì)陣型多樣性，較大c1、c2值使算法收斂速度不易過(guò)慢（本文實(shí)驗(yàn)設(shè)pc=0.8，c1=c2=1）；
?。?）當(dāng)算法收斂過(guò)慢時(shí)，減小pc以加快收斂速度；當(dāng)算法陷入局部極值時(shí)，減小c1和c2值以減慢收斂速度，保持團(tuán)隊(duì)陣型多樣性（本文實(shí)驗(yàn)pc=pc×0.8、c1=c1×0.8和c2=c2×0.8）。
2.3 淘汰機(jī)制
　由表1可見(jiàn)，算法設(shè)置同一種參數(shù)組合時(shí)，針對(duì)不同優(yōu)化問(wèn)題，算法收斂到全局最優(yōu)的比例差別較大，如當(dāng)pc為0.01，c1和c2為1時(shí)，優(yōu)化Ackley時(shí)收斂到全局最優(yōu)的比例僅55%，而其他函數(shù)收斂到全局最優(yōu)的比例都較高；當(dāng)算法優(yōu)化同一函數(shù)時(shí)，設(shè)置不同的參數(shù)組合收斂到全局最優(yōu)的比例差距也較大，如當(dāng)優(yōu)化Ackley時(shí)，收斂到全局最優(yōu)的比例最高有99%，最低僅47%。由此可見(jiàn)算法的魯棒性較低。
　為提高算法的計(jì)算效果，本文將淘汰機(jī)制引入算法。在體育團(tuán)隊(duì)聯(lián)賽中一般有淘汰機(jī)制，如從32強(qiáng)到16強(qiáng)，這個(gè)過(guò)程必須淘汰一半的團(tuán)隊(duì)。本文借鑒淘汰賽思想提出淘汰策略：將所有團(tuán)隊(duì)按照?qǐng)F(tuán)隊(duì)適應(yīng)值從優(yōu)到差進(jìn)行排序，選擇排在前面的一半團(tuán)隊(duì)進(jìn)行重新隨機(jī)初始化。
　首先算法陷入局部極值很可能是由最優(yōu)適應(yīng)值的團(tuán)隊(duì)已經(jīng)陷入局部極值，且較差適應(yīng)值的團(tuán)隊(duì)向較優(yōu)適應(yīng)值團(tuán)隊(duì)靠攏導(dǎo)致，所以只有將較優(yōu)適應(yīng)值團(tuán)隊(duì)淘汰后才能更好地跳出局部極值；其次為了保持參賽團(tuán)隊(duì)總數(shù)不變，直接對(duì)要淘汰的團(tuán)隊(duì)進(jìn)行初始化，可解釋為加入新團(tuán)隊(duì)參與比賽。
如果算法每輪迭代都使用該策略，將導(dǎo)致算法收斂過(guò)慢或無(wú)法收斂。因此本文提出基于收斂速度的淘汰機(jī)制：
　（1）初始化開(kāi)關(guān)變量Kswitch=false，值為true表示淘汰狀態(tài)開(kāi)啟，該狀態(tài)下算法每完成一個(gè)賽季都會(huì)執(zhí)行淘汰策略；值為false表示淘汰狀態(tài)關(guān)閉，不執(zhí)行淘汰策略；
?。?）當(dāng)發(fā)現(xiàn)算法陷入局部極值時(shí)，令Kswitch=true；當(dāng)發(fā)現(xiàn)算法收斂過(guò)慢時(shí)，令Kswitch=false；
2.4 帶淘汰制的自適應(yīng)聯(lián)盟競(jìng)賽算法流程
　綜上所述，改進(jìn)的聯(lián)盟競(jìng)賽算法具體步驟如下：
　（1）初始化團(tuán)隊(duì)數(shù)量、陣型、最大比賽輪數(shù)S、窗口大小w、Gbest、Tbest、閾值λs等；Kswitch=false、t=0；
?。?）產(chǎn)生一個(gè)賽季的比賽賽程；
?。?）將最優(yōu)適應(yīng)值的團(tuán)隊(duì)陣型保存到Xt；
?。?）根據(jù)第t輪的賽程進(jìn)行比賽，并判斷比賽輸贏；
?。?）t=t+1，若t>S，執(zhí)行步驟（11）；
?。?）更新團(tuán)隊(duì)陣型和Gbest、Tbest；
　（7）按式（8）檢測(cè)算法是否收斂過(guò)慢或陷入局部極值；若算法收斂過(guò)慢，則按2.2節(jié)方案減小Pc值并令Kswitch=false；若算法陷入局部極值，則按2.2節(jié)方案減小C1和C2值并令Kswitch=true；
 （8）若Kswitch=true，調(diào)用2.3節(jié)的淘汰策略；
 （9）判斷是否要產(chǎn)生新賽程，若是則根據(jù)某種規(guī)則產(chǎn)生新賽程并替換舊賽程，否則繼續(xù)使用舊賽程；
 （10）轉(zhuǎn)步驟（3）；
 （11）輸出全局最優(yōu)解Xs。
3 實(shí)驗(yàn)
　本文通過(guò)5個(gè)經(jīng)典的函數(shù)優(yōu)化問(wèn)題來(lái)測(cè)試改進(jìn)后的聯(lián)盟競(jìng)賽算法和原始聯(lián)盟競(jìng)賽算法的性能。測(cè)試函數(shù)包括：Sphere、Rosenbrock、Rostrigin、Griewank和Ackley，其自變量取值范圍分別為：[-100，100]、[-2.048，2.048]、 [-5.12，5.12]、[-32.76，32.76]、[-5.12，5.12]。
　實(shí)驗(yàn)采用隨機(jī)初始化團(tuán)隊(duì)陣型，函數(shù)值作為適應(yīng)值，結(jié)束條件為最大迭代次數(shù)，由于5個(gè)測(cè)試函數(shù)的全局最優(yōu)值都是0，假設(shè)最優(yōu)值<λs時(shí)，認(rèn)為算法收斂到全局最優(yōu)。設(shè)團(tuán)隊(duì)數(shù)量L=10、迭代次數(shù)S=2 000、函數(shù)維數(shù)n=5、λs=1E-06，w=40，對(duì)LCA采用12種不同參數(shù)組合。
　將ALCAKS和LCA的不同參數(shù)組合對(duì)每個(gè)測(cè)試函數(shù)分別試驗(yàn)100次。實(shí)驗(yàn)結(jié)果如表2和表3所示，對(duì)LCA只列出效果較好的3種參數(shù)組合。表2列出算法對(duì)每個(gè)測(cè)試函數(shù)在100次實(shí)驗(yàn)中收斂到全局最優(yōu)的比例。表3列出算法對(duì)測(cè)試函數(shù)在100次實(shí)驗(yàn)中收斂到全局最優(yōu)的最優(yōu)值平均值。

　從表2、表3可以看出相比LCA算法，本文ALCAKS算法魯棒性和全局搜索能力有一定程度的提高，因此本文提出的改進(jìn)方案是可行的。
參考文獻(xiàn)
[1] KASHAN A H. League championship algorithm： a new algorithm for numerical function optimization [C]. International Conference of Soft Computing and Pattern Recognition， 2009.
[2] KASHAN A H. A new algorithm for constrained optimization inspired by the sport league championships [C].  Evolutionary Computation（CEC）， 2010.
[3] KASHAN A H. An efficient algorithm for constrained global optimization and application to mechanical engineering design： League championship algorithm（LCA）[J]. Computer-Aided Design， 2011， 43： 1769-1792.
[4] POURALI Z， AMINNAYERI M. A novel discrete league championship algorithm for minimizing earliness/tardiness penalties with distinct due dates and batch delivery consideration[C]. Advanced Intelligent Computing， 2012.
[5] KASHAN A H， KARIMI B， JOLAI F. Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes [C]. Int J Prod Res， 2006.