新型排球超級聯賽算法

胡亞東，馬 良，劉 勇

(上海理工大學 管理學院，上海 200093)

1 引 言

受大自然的啟發而產生的元啟發式算法是一大類具有全局優化性能、通用性強、適合并行計算的現代智能優化方法，目前已開始大量用于解決工程優化問題，具有代表性的有遺傳算法(Genetic Algorithm，GA)[1]、差分進化算法(Differential Evolution Algorithm，DE)[2]、粒子群算法(Particle Swarm Optimization，PSO)[3]、螢火蟲算法(Firefly Algorithm，FA)[4]、正弦余弦算法(Service Component Architecture，SCA)[5]、和聲搜索算法(Harmony Search，HS)[6]、人工蜂群算法(Artificial Bee Colony Algorithm，ABC)[7]、足球聯賽競爭算法(Soccer League Competition，SLC)[8，9]和聯盟冠軍算法(League Championship Algorithm，LCA)[10].除此之外，還包括這些算法與其他方法相結合的混合型算法以及這些算法的改進算法[11-14].這些算法為傳統方法不能解決的難題提出了新的思路和跨領域的、別具特色的優化策略.但是，每種方法都有一定的適用范圍，隨著研究的優化問題越來越復雜，面對具有大規模、非線性、不可微、多目標、不確定等特征時，這些算法也暴露出一些自身存在的不足，例如易早熟收斂、優化精度不高和收斂速度慢等.因此，對新型優化算法的設計具有重要的學術價值.

排球超級聯賽算法(Volleyball Premier League Algorithm，VPL)[15]是由伊朗布什爾波斯灣大學學者Reza Moghdani和 Khodakaram Salimifard在2018年提出的以排球體育賽事為背景的新穎智能優化算法，VPL算法模仿排球運動中的訓練機制，參考普通球隊晉升為最佳球隊的進化過程來解決全局優化問題.該算法的解由場上球員和替補球員兩部分組成，一支球隊代表一個解，聯盟中所有球隊代表一個解集.VPL算法對最優解的搜索過程，是從一個由多支球隊組成的初始群體開始，通過單循環賽制安排球隊之間相互比賽.比賽結束后不僅對各球隊內部進行更新，還將對各球隊之間進行更新，產生出新一代的球員群體.經過多個賽季后逐步使群體進化到包含或者接近最優解的狀態.對于VPL算法這樣的新型智能優化算法，在給優化領域帶來新的求解工具、提出潛在的研究方向的同時，也暴露出自身存在的不足和局限性.

雖然VPL算法具有較強的的全局尋優能力，但是該算法在局部開發性能方面相對欠缺，尤其是在算法運行后期對于復雜函數的全局探索表現出求解精度不高、收斂速度慢等缺陷.面對VPL算法的這些問題，需要進一步改進算法從而提高算法的整體尋優能力，自VPL算法提出以來還沒有學者對該算法做進一步改進，因此本文提出一種新型排球超級聯賽算法(Novel Volleyball Premier League Algorithm，NVPL).新算法引入了聯盟的超級明星球員，每場比賽結束后，失敗球隊在訓練過程中都將在教練的指導下學習、模仿超級明星球員，努力達到超級明星球員的水準；并且新算法還改進了更新過程中的替補策略，使得球隊在比賽失敗后不再是盲目的隨機進行替補，而是根據目前球隊替補實力自適應采取替補算子；最后為平衡算法的全局尋優和局部尋優能力，設計了一種隨機交互訓練策略.NVPL算法更加真實的模擬了排球運動，也提高了算法的尋優能力和求解精度.通過對11個經典測試函數仿真實驗，并與文獻[15]中的排球超級聯賽(VPL)等多種算法進行比較，實驗結果證明了NVPL算法的有效性.

2 排球超級聯賽算法介紹

2.1 排球超級聯賽算法原理

(1)

(2)

lbj和ubj分別是變量j的下界和上界，Rand()是在區間[0，1]上的隨機數.初始群體可以用矩陣F和S表示，其中行數和列數分別表示球隊數和球員數.球隊數的值可以靈活地設置，而球員數與變量的數量相同.

(3)

(4)

(5)

(6)

(7)

2.2 球隊內部更新策略

每場比賽結束之后，針對勝利球隊和失敗球隊分別采取不同的更新策略.對于失敗球隊，教練通過觀察球員在比賽中的表現來訓練球員提升技能.令δks表示每支球隊中參與訓練的球員比率、J表示球員總數，則每次比賽中需要訓練的球員數量Nks可通過(8)式求得.通過公式(9，10)定義訓練過程，其中λf和λs分別為主力陣容系數和替補系數，r1和r2是區間[0，1]上均勻分布的隨機數.

Nks=J×δks

(8)

(9)

(10)

根據比賽進展和形勢發展，教練通過交換各主力球員的位置來獲得更好的表現.δks表示每支球隊中交換主力球員位置的比率，則每次比賽中需要交換位置的球員數量Nrs如式(11).隨機選擇兩個球員i和j后，定義帶有主力陣容和替補屬性的兩個變量A和B，然后將球員i和j的屬性與A和B的屬性互相交換.

Nrs=J×δrs

(11)

Ns=r×J

(12)

替補是排球比賽中的一種特殊過程，教練分析哪些球員和組合表現得好，從而用替補席上的球員替換場上球員，教練試圖選擇一個好的替補策略來形成不同的陣容.設r為區間[0，1]上的均勻分布隨機數，則每次比賽中替補的次數Ns如式(12)計算所得.定義集合F和集合S，分別包含了主力球員和替補球員，然后隨機交換集合F和集合S中的所有成員.

2.3 球隊之間更新策略

2.3.1 學習階段

(13)

θ=d×b×r1-b

(14)

?=d×r2

(15)

b=β-(t×β/T)

(16)

排球教練分析聯盟中所有球隊的表現，通常以一種更接近rank1球隊表現的方式來訓練球員，為了對學習過程進行數學建模，假設所有球隊均以rank1、rank2和rank3球隊為學習對象，式(17-19)共同定義了球隊的主力球員的學習過程.

(17)

(18)

(19)

類似與解的主力陣型屬性，公式(20-23)定義了球隊的替補球員學習過程.

(20)

(21)

(22)

(23)

2.3.2 球員轉會

在排球聯賽中，轉會是指球員從一個球隊轉移到另一個球隊的過程.根據一些規定，球員可以在賽季末變換球隊.基于這一概念，在排球超級聯賽算法中定義了一個算子來模擬這一過程以幫助算法收斂到最優解.在本賽季球員變換球隊時間里，有一組集合H和N(H?N)，由隨機選出的小組組成.集合H中每個球員的所有位置都是從當前可用的球隊中隨機選取，其中r為區間[0，1]上均勻分布的隨機數.假設只有一小部分球隊使用轉會策略，δst表示參加賽季轉會球隊的百分比，則Nst表示參與賽季轉會的球隊數量，如式(24).

Nst=N×δst

(24)

Npr=N×δpr

(25)

2.3.3 淘汰機制

一個賽季結束后，頂級球隊將進入更高級別聯賽，而最差的球隊將在下個賽季降級到更低的聯賽級別，級別被調整球隊的數量取決于聯賽規則.設δpr為賽季末晉升和降級球隊的比例，則被調整級別的球隊數量Npr通過式(25)計算所得，其中N表示聯賽中球隊總數.假設算法中只有一個聯賽可用，此處使用一個特殊的過程來確定晉升的團隊，將表現最差的Npr個球隊從聯賽中淘汰，并生成Npr個新的球隊且添加到聯賽中.為了生成每支晉級球隊，分別從當前超級聯賽的主力陣型和替補屬性中隨機選擇.

3 新型排球超級聯賽算法

3.1 超級明星球員算子

超級明星球員(Super Star Player，SSP)是整個聯盟的核心球員，在比賽中既可以自己得分，也可以帶動隊友得分，并且在比賽的關鍵時刻具有扭轉乾坤的作用.明星球員是完美執行教練意圖的最佳代表，核心往往具有堅定的信念、超強的控制比賽能力，還有引領隊友前進的實力，通常都是聯盟追逐的熱點，也是失敗球隊學習的榜樣.在一場比賽結束后，失敗球隊需要加強訓練去面對下一場競賽.對于這種重要的場下訓練活動，失敗球隊的球員應該以聯盟超級明星球員為標準訓練自己，從而提升球隊的整體實力.在算法的這個更新過程中，每個劣質的解都將根據群體中最優解來優化自身，通過公式(26)來定義該過程：

X(t+1)=X(t)+αX*(t)

(26)

其中X(t)表示失敗球隊的球員；X*(t)表示聯盟超級明星球員；X(t+1)表示X(t)以X*(t)為標準、優化后的結果；α∈[0,1]為學習因子，球員的學習能力各不相同，面對同一個學習對象，優化更新后的結果也各不相同.

3.2 自適應替補策略

本文還對VPL算法的替補算子進行了改進，提出了自適應替補策略.由于VPL算法對每支失敗的球隊都將采取替補策略，并且參與替補的球員也是隨機生成，在球隊有優秀替補時，對于算法的搜索和利用能夠起到不錯的效果；反之，當沒有一個替補球員優于最差的主力球員時，容易使得算法收斂速度放慢，陷入無效搜索中.在現實體育運動中，如果一支球隊的主力球員已是球隊的最佳陣容，那么即使球隊失敗了也沒有必要進行替補操作.因為替補已經非常差了，此時再進行替補操作只會降低主力陣容的整體效果.球隊面對現在的失敗現狀以及實力落后的替補球員，教練應該采取除替補之外的其他策略來提升球隊技能.如果一支失敗的球隊，它的替補陣容里面有比主力陣容更優秀的球員，此時教練應該及時采取替補策略.但需要參與替補球隊的球員數量不應該是隨機生成，而取決于當前球隊有多少替補球員比他的主力球員更優秀.當失敗球隊滿足上述替補要求時，通過下式模擬替補過程：

(27)

(28)

(29)

(30)

3.3 隨機交互訓練

依據經驗學習可知，雖然當前最劣球隊向最佳球隊學習可以使其快速向最佳球隊聚集，但很輕易忽視其他一些有價值的球隊學習機會.在處理具有多個局部最優值問題時，經過一定迭代次數之后可行解逐漸集中于局部最優值附近，很難再跳出當前這個狹小的空間內，這種現象尤為突出.另外最劣球隊僅說明當前解的適應度值最差，并不代表最劣球隊中所有球員都沒有潛在學習價值.對于聯盟中最劣的球隊，如果能夠通過某種訓練方式進行經驗交互，那么可以實現算法對全局開發和局部優化的再平衡.

3.3.1 最劣球隊向最佳球隊隨機學習

(31)

當最劣球隊在最佳球隊臨近的對稱區間內隨機交互訓練時，可以高效挖掘最佳球隊解空間鄰域的信息.特別是在優化問題的早期迭代階段，不同球隊之間實力差異較大，當前最差球隊向最優球隊學習、訓練可以快速向最優球隊靠攏，算法的全局優化能力能夠得到顯著提升.

3.3.2 任一球隊向最佳球隊隨機學習

(32)

在任一球隊向最佳球隊隨機交互訓練過程中，可以實現對其它球隊附近解空間局部信息有效挖掘并利用，加強算法局部優化能力.

3.3.3 隨機交互訓練

將3.3.1和3.3.2中提出的兩種學習策略隨機交互訓練.新球隊Xnew的第j位球員將按照下面的規則執行產生.其偽代碼為：

If rand()

執行(31)

ELSE

執行(32)

End

兩種不同學習策略隨機交互動態產生新球隊，既保持了當前最佳球隊的特性，同時又繼承了最劣球隊與其他球隊的某些特質.另外，隨機交互訓練方式下，新球隊的一部分球員通過最劣球隊向最佳球隊學習產生，實現全局優化；新球隊的另一部分球員通過其他球隊向最佳球隊學習進行經驗交互后產生，實現局部信息的開發.將兩者交互，利用啟發式算法的隨機性特點，使其在全局尋優與局部尋優之間隨機跳躍，回避了算法單一進行全局開發與局部開發的缺陷，從而實現全局優化和局部優化的動態平衡.

根據以上分析，本文所提出的新型排球超級聯賽算法的步驟總結如下：

步驟1.設置參數，進行初始化；

步驟2.計算聯賽中各支球隊的適應度值，并且確定當前最佳球隊；

步驟3.根據單循環賽制生成比賽賽程表，并開始進行比賽；

步驟4.通過實力指數判斷每場比賽的結果，確定勝利球隊和失敗球隊；

步驟5.球隊內部更新：每場比賽結束后，對失敗球隊采取超級明星球員算子、換位策略、自適應替補策略，對勝利球隊運用取勝策略，從而更新最佳球隊；

步驟6.球隊之間更新：每輪比賽結束后，球隊之間進入隨機交互訓練階段；在一個賽季結束之后，各球隊間采取轉會流程、淘汰機制，從而更新最佳球隊；

步驟7.判斷是否達到最大迭代次數，若滿足則算法結束，輸出結果；否則執行步驟3.

4 仿真實驗

為了驗證本文所提出的新型排球超級聯賽算法的有效性、可行性及其他相關性能，選取了一系列經典測試函數進行了大量的計算機仿真數值實驗，并獲得了滿意的效果.由于篇幅限制本文列出11個常用的標準測試函數及其仿真結果，并與文獻[15]中列出的算法仿真結果進行比較.選取的11個經典標準測試函數理論最優值均為0，具體表達式如下：

minF4(x)=maxi{|xi|,1≤i≤n},-100≤xi≤100;

(3πyi+1)](xn-1)2[1+sin2(2πxn+1)]}+

為驗證算法有效性，本文算法均在Windows 10操作系統下的MATLAB R2017a編程實現，運行環境為Intel Core i5 CPU 3.00GHz，8 B RAM.對于所有的標準測試函數，基本參數與文獻[15]中的算法參數設置保持一致，統一設置群體規模為10，維度為30，最大迭代次數均為100.由于智能優化算法的思想是模擬人類體育運動過程且具有一定的隨機性，因此實驗中每種算法獨立運行20次來降低隨機因素干擾.改進后的NVPL算法與改進前的基本VPL算法實驗仿真結果比較見表1，各算法的統計指標統一為20次尋優結果中的最好值、最差值、平均值、標準差.

由表1可以看出，VPL算法在測試函數F1、F2、F3、F4、F5時由于陷于局部最優，多次迭代后均未能穩定得到理論最優值，而采用“隨機交互”策略后的改進NVPL每次均能穩定找到最優值，函數F1-F5的仿真結果體現了改進的算法在避免陷入局部最優上的性能；對于函數F6、F7，改進后的NVPL算法性能雖然得到提高，但是效果不明顯，后續還有改進空間；對于函數F9，VPL算法與NVPL算法均能得到滿意解；對于函數F8、F10、F11，NVPL算法比VPL算法的尋優能力好很多，改進工作取得了顯著效果.另外本文還給出了NVPL算法與VPL算法的測試函數的函數值尋優曲線，如圖1所示.從測試函數的尋優曲線可以看出，改進后的NVPL算法的尋優速度和尋優精度是明顯優于基本VPL算法的.基于改進NVPL算法與標準VPL算法的測試函數的適應度值比較結果(表1)和測試函數迭代收斂曲線(圖1)，可以看出，改進后的NVPL算法對于單峰和多峰函數的優化結果好于標準VPL算法.標準VPL算法從算法的精度來說并不理想，易發生早熟和停滯現象，而改進的NVPL算法則克服了這些缺點.改進優化算法以新的更新方式，建立了全局探索與局部開發之間的平衡機制，加快了算法的收斂速度，使算法更易收斂于最優解.

圖1 測試函數的適應度值的迭代收斂曲線Fig.1 Fitness of test functions is worthy of iterative convergence curve

表2 測試函數結果比較Table 2 Result comparison of test functions

為了進一步對NVPL算法與其他智能優化算法進行比較，本文還將NVPL算法的測試結果與文獻[15]中的排球超級聯賽算法(VPL)、足球聯賽競爭算法(SLC)、聯賽冠軍算法(LCA)、粒子群算法(PSO)、差分進化算法(DE)、遺傳算法(GA)、人工蜂群算法(ABC)、螢火蟲算法(FA)和聲搜索算法(HS)和正弦余弦算法(SCA)進行比較.比較結果如表2所示，可以看出，針對函數F1、F3，NVPL的尋優能力最強，VPL的性能優于LCA、SLC，SCA、PSO、HS、GA、FA、DE、ABC效果最差；針對函數F2、F5，NVPL的尋優能力最強，VPL、SLC的尋優能力差不多，LAC稍微差一點，SCA、PSO、HS、GA、FA、DE、ABC的求解精度均不高；針對函數F4，NVPL的尋優效果最佳，VPL雖然也找到滿意解，但尋優能力不穩定，LCA、SLC的尋優效果稍差，但SLC明顯優于SCA，LCA，PSO、HS、GA、FA、DE、ABC的性能都非常差；針對函數F6、F10，NVPL、VPL、LAC的尋優能力比SLC，SCA、PSO、HS、GA、FA、DE、ABC要強，雖然NVPL的尋優能力要比VPL強，改進后的算法性能得到了提高、改進工作起到了一定效果，但是LAC在所有算法中表現最佳；針對函數F7，NVPL的尋優能力稍好于VPL，SLC、LCA、SCA、PSO、FA、DE次之，HS、GA、ABC較差；針對函數F8，NVPL的尋優能力最強，VPL次之，LCA、SLC，SCA、PSO、HS、GA、FA、DE、ABC較差；針對函數F9，NVPL、VPL和SLC都能夠找到最優值、并且穩定性都非常好，LCA稍差，SCA、PSO、HS、GA、FA、DE、ABC較差；針對函數F11，NVPL和LCA尋優能力最佳，VPL、SLC次之，SCA、PSO、HS、GA、FA、DE、ABC較差.通過上述分析，表明在對所有經典測試函數進行尋優的結果中，NVPL算法和基本VPL算法的優化結果均以絕對的優勢優于進行比較的其它算法.并且相對原有算法而言，本文提出的NVPL算法具有良好的收斂性能，優化結果更佳.

5 結束語

排球超級聯賽算法是一種新型的元啟發式算法，為優化算法的設計提供了新思路.針對基本VPL算法在更新階段中存在收斂速度慢、求解精度不高和易陷入局部最優等缺陷，本文通過引入超級明星球員更新算子、完善自適應替補策略、設計隨即交互訓練方式，提出一種新型排球超級聯賽算法.新算法在避免陷入局部最優的同時還提高了算法的收斂速度和求解問題的精度，通過對11個經典測試函數的仿真測試實驗，結果表明新型排球超級聯賽算法具有較好的優化性能和潛在的應用價值.排球超級聯賽算法是一種新型的智能優化算法，在未來的研究中，除了進一步改進其尋優性能，還可以將算法應用于實際工程問題.