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

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

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

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

　從表2、表3可以看出相比LCA算法，本文ALCAKS算法魯棒性和全局搜索能力有一定程度的提高，因此本文提出的改進方案是可行的。
參考文獻
[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.