考慮多種訓練方式的自適應最有價值球員算法

王 寧，劉 勇

（上海理工大學管理學院，上海 200093）

（?通信作者電子郵箱806929086@qq.com）

0 引言

智能優化算法是受人類智能、生物群體社會性或自然現象規律的啟發，模仿其規律所提出來的求解問題的算法，為許多傳統優化技術很難解決的組合優化問題提供了切實有效的解決辦法［1］。智能優化算法因其全局優化性能較好，可以進行并行計算和通用性強等特點，已廣泛應用于系統控制、人工智能、生產調度、計算機工程等領域，展示出了其強大的優勢，并且具有更好的應用前景。

最有價值球員算法（Most Valuable Player Algorithm，MVPA）是Bouchekara［2］于2017 年提出的新型智能優化算法。該算法受到體育比賽的啟發，球員們為了贏得聯賽冠軍而進行隊伍競爭，并且他們單獨進行競爭以贏得MVP 獎杯。每個球員即代表一個潛在的解，通過競爭階段來不斷提高球員的水平，從而產生一個MVP，即對應問題的最優解。

MVPA 具有結構簡單、參數設置少、收斂速度較快等優點，已經應用到降低圓形天線陣列的最大旁瓣電平的優化問題［3］、壓力容器設計問題［4］等實際問題中；然而，MVPA 在求解復雜優化問題時存在尋優精度低、收斂速度慢等缺陷。為了提高算法的優化性能，文獻［4］將教與學優化算法引入MVPA中，算法設計了兩種訓練模式來分別提高球員的能力和隊伍的凝聚力，提高了算法的收斂速度和搜索精度。

本文分析了MVPA 尋優精度低的原因，并從球員初始化方式出發，提出了考慮多種訓練方式的自適應最有價值球員算法（Adaptive Most Valuable Player Algorithm Considering Multiple Training Methods，ACMTM-MVPA）。球員除了通過個體競爭和隊伍競爭提升技能之外，還考慮球員為了進入球隊而付出的努力和訓練對提高球員技能的重要性，最后使用一系列標準測試函數和求解暴雨強度公式參數優化問題對ACMTM-MVPA的有效性進行了驗證。

1 最有價值球員算法

在MVPA 中，將每個球員看作一個潛在的可行解，并將球員分配到不同的隊伍中去，通過個體競爭和隊伍競爭來使球員的能力不斷提高，并最終產生一個MVP 球員，即算法的最優解。算法可以分為個體競爭和隊伍競爭兩個階段，個體競爭意味著球員之間的競爭，隊伍競爭即隊伍之間的比賽。球員數量即群體的大小，球員的各種能力就是球員的維度，適應度函數就是球員的水平，適應度越好，說明水平越高。

1.1 初始化

首先在搜索空間內隨機生成PlayersSize個球員，并隨機分成TeamsSize個隊伍。隊伍生成方法［2］如下：

其中：ceil為向上取整函數；nT1表示第一部分的隊伍數量，nP1表示第一部分每個隊伍的隊員數量；nT2表示第二部分的隊伍數量，nP2表示第二部分每個隊伍的隊員數量。

1.2 競爭階段

在完成初始化之后，算法進入競爭階段。在該階段中，球員通過隊內競爭來提高自身能力，同時球隊為了提升其實力與其他隊伍進行隊間競爭。下文給出球員之間的個體競爭以及球隊之間的隊伍競爭的具體方法。

1.2.1 個體競爭

在個體競爭階段，每個球員都致力于成為所在隊伍中的最佳球員(FranchisePlayer)和聯盟最有價值球員(MVP)。為此，球員努力去提高自身能力，并與所在隊伍中最佳球員和聯盟最有價值球員作比較。因此，每個球員按照如式（5）［2］更新：

其中：TEAMi表示第i個隊伍中隊員；rand是［0，1］區間服從均勻分布的常數；FranchisePlayeri表示第i個隊伍中的最佳球員；MVP表示聯盟最有價值球員。

1.2.2 隊伍競爭

在球員完成個體競爭之后，球隊之間進行隊伍競爭。在這個階段，TEAMi和TEAMj兩個隊伍相互比賽。按以下機制選取獲勝隊伍。

以最小化問題為例，首先按照式（6）標準化隊伍的適應度［2］。

其中：fitnessN(TEAMi)是第i個隊伍未標準化的適應度值；min(fitness(ALL Teams) 是全聯盟中最小的適應度值。TEAMi打敗TEAMj的概率［2］如式（7）所示：

其中：文獻［2］中的k取1；fitnessN(TEAMi)為第i個隊伍標準化后的適應度值；Pr表示獲勝概率。

根據式（6）～（7），獲勝概率分為不同和相同兩種情況。

如果兩個隊伍的獲勝概率不同，則會生成一個［0，1］區間的隨機數，如果這個隨機數大于較高的獲勝概率，則獲勝概率較低的隊伍獲勝；反之，則獲勝概率較高的隊伍獲勝。

如果兩個隊伍的適應度相同，則會得到相同的獲勝概率。因此，還需要再生成一個［0，1］區間的隨機數，若這個隨機數高于0.5，第一個隊伍獲勝；否則，第二個隊伍獲勝。

當球隊TEAMi獲勝時，則TEAMi中隊員按如式（8）［2］更新：

其中：TEAMi表示第i個隊伍中隊員；rand表示［0，1］內均勻分布的隨機數；FranchisePlayerj表示第j個隊伍中的最佳球員。

當球隊TEAMi獲勝時，該隊伍中隊員按如式（9）［2］更新：

2 考慮多種訓練方式的自適應MVPA

在現實的球賽中，每一個球隊都想挑選實力強勁的球員，以此來增強球隊的實力，從而提高球隊在聯賽中的地位。但是MVPA 采用隨機的方式初始化球員，并且球隊選拔球員具有較強的隨機性和盲目性，因此，本文考慮加入訓練階段。訓練階段的加入就是通過多種訓練方式來增強球員的能力。在訓練階段中，本文加入了鄰域搜索算法和混沌序列與反向學習算法。鄰域搜索算法主要是讓想將實力較弱的球員培養出實力強勁的球員，通過局部搜索的方式，讓球員能快速靠近較優解；混沌序列和反向學習算法主要是淘汰實力弱的球員，篩選出實力強勁的球員。同時，可以提高球員的訓練速度和效率，從而有助于提高算法的收斂速率，通過球隊的整體平均水平和優秀球員的平均水平決定是選擇鄰域搜索算法還是混沌序列和反向學習算法或保持不變。

在現實的聯賽中，比賽初期的球隊之間的實力差距較大，球員水平也參差不齊，在球隊比賽的過程中，即使是對方球隊中的最佳球員，也不一定有很多值得學習的地方，但隨著比賽的不斷推進，實力弱的球隊以及球員可能會被不斷地淘汰或者是提高，到比賽后期球隊和球員的實力都會越來越強，對于球員來說，贏的球隊中的最佳球員一定有很多值得球員學習的地方，也能通過學習提高自身的能力和水平。因此，在比賽初期，球員更多地需要自我探索，而在比賽后期，雙方球隊和球員的實力都很強，球員都可以從對方最佳球員的身上學習到很多技巧和方法。基于此，本文考慮在隊伍競爭階段球隊輸了比賽后的更新公式中加入自適應球員進化因子，在迭代前期，自適應球員進化因子較大，增強算法的全局搜索能力；在迭代后期，自適應球員進化因子較小，增強算法的局部尋優能力。

2.1 訓練階段

在MVPA 中，球員在初始化后被隨機分配至各個球隊。而在實際的過程中，球員必須達到一定的水平，滿足球隊的要求才能進入球隊。因此，球員要通過訓練不斷提高自身能力。借鑒籃球聯賽中球員加入隊伍之前的海選過程，為提高球員的質量和球隊的整體水平，在MVPA 的基礎上，引入訓練階段來提高算法的尋優精度和收斂速度。

訓練階段加入在競爭階段之前，這樣球員提高自身能力除了通過個體競爭和隊伍競爭之外，還有球員為了通過進入球隊而進行的努力和訓練。在訓練階段，球員為了進入理想的球隊，會不斷訓練來提高自己的能力。在訓練過程中，球員可能會出現以下三種情況：

1）當球員水平高于優秀球員的平均水平時，球員覺得自身能力很強，且自己的訓練方法很有效，則會一直按照自己的方法進行訓練。

2）當球員水平高于所有球員的平均水平但低于優秀球員的平均水平時，球員覺得自身能力還需要加強，且自己的訓練方法有一定的效果，則會微調整訓練方法以獲得更好的效果。

3）當球員水平不高于所有球員的整體平均水平時，球員覺得自身能力不行，且訓練方法沒有效果，則會很大程度地調整自己的訓練方法，以獲得意想不到的良好效果。

設定fi表示當前球員的適應度值，fmin表示當前所有球員的最小適應度值，favg表示當前所有球員的平均適應度值，將適應度值優于favg的適應度值求平均得到favg'。

當fi≤favg'，此時球員水平高于優秀球員的平均水平，球員的能力比較強，可能不會做出改變，因此，這里考慮球員保持不變，如式（10）所示：

當favg'＜fi＜favg，球員對自己的訓練方法進行局部調整，局部搜索策略是以每個當前解Playeri為中心，在其周圍通過式（11）產生一個較優的解：

其中：r1、r2為（0，1）內隨機數；φ為微調因子；Playerimin 和分別為第i個球員的下界和上界。

當fi≥favg時，球員可能會在很大程度上調整自己的訓練方法，本文采取混沌序列和反向學習的方法來更新球員，先用Cat混沌序列產生一個解，然后再使用式（12）產生相對應的反向解。

混沌現象［5］是在非線性動力系統中表現的確定性、類隨機的過程，這種過程既非周期又不收斂，混沌理論看似混亂但其內在結構十分精致，具有隨機性、規律性和遍歷性等特點，已經逐漸作為智能優化算法的優化機制得到廣泛應用。基于不同映射的混沌序列的發生器會產生具有不同概率密度分布的混沌序列，這種分布特性的差異會影響算法的效率。Cat映射具有良好的遍歷均勻分布特性，當最優解均勻分布于自變量期間或靠近自變量區間的中間位置時，有助于提升搜索效率。其動力學方程如下：

反向學習策略（Opposition-Based Learning，OBL）是由Tizhoosh［6］在2005年首次提出的一種新技術。文獻［7］證明了反向學習算法的學習速度快，而且優化能力更強，文獻［8］表明通過反向學習來進行種群的初始化，更有助于提高算法的收斂速率。其基本思想為設X=(x1，x2，…，xD)表示D維空間中的一個可行解，其對應的反向解X'=(x'1，x'2，…，x'D)可定義為：

其中：aj、bj分別為xj的下、上邊界。由于反向解有50%以上的可能性比原解更優，因此，若將反向解和原解進行合并，并選擇其中較優的解，則獲取最優解的概率將大大提高。

2.2 自適應球員進化因子

為了獲得更好的效果，MVPA 需要平衡好全局搜索和局部搜索能力：在算法初期，進化因子μ較大，讓球員有更多的自我提升機會，從而擴大球員的探索區域；在算法后期，進化因子μ較小，讓球員向優秀球員學習，使得球員能夠達到最佳狀態；同時，在算法初期，球員應該有較強的自我學習能力，不斷去探索。隨著算法的迭代，球員不能增強向優秀球員的學習能力，對應的局部開發能力逐漸增強。

根據以上準則，本文對式（8）進行了調整，添加了自適應的球員進化因子，如式（15）～（16）所示：

式中：球員進化因子μ∈[0，1]，MAXITER為最大迭代次數，ITER為當前迭代次數。由式（16）可知，在算法迭代初期，μ≈1，此時式（15）中，球員的提升主要來源于對自身的探索開發，具有較強的全局搜索能力；隨著算法的不斷迭代，μ不斷減小，此時球員應向最佳球員學習，吸收最佳球員的優點增強自己，不斷提升，此時，算法的局部開發能力增強，從而提高算法的收斂速度和尋優精度。

綜上所述，ACMTM-MVPA的基本流程如下：

步驟1 初始化階段，在搜索空間內，隨機生成PlayersSize個球員，并計算出所有球員的適應度值，以及所有球員的平均適應度值和高于平均值的球員的平均值。

步驟2 訓練階段，按照式（10）～（12）生成一個球員數量為PlayersSize的群體。然后這些球員被隨機分配組成隊伍數量為TeamsSize的球隊。通過評估這些球員的能力，選出MVP（聯盟最有價值球員）和每個球隊FranchisePlayer（每個隊伍中的最佳球員）。

步驟3 個體競爭階段，在該階段每個球隊都要進行個體競爭并按照式（5）更新選定球隊的每個球員對應的解。

步驟4 隊伍競爭階段，按照式（6）標準化球隊的適應度。

步驟5 按照式（7）計算隊伍的獲勝概率。

步驟6 根據獲勝機制按照式（15）或式（9）更新球隊中隊員的技能。

步驟7 檢查是否滿足算法停止準則，若滿足，則輸出當前最優解并結束算法；否則轉至步驟2。

3 數值實驗

3.1 參數設置

為驗證新算法的性能，選取了15 個測試函數作為實驗對象，這些函數的函數名、表達式、維數、搜索范圍和理論最優值如表1 所示。為了檢驗新算法的合理性和有效性，將提出的ACMTM-MVPA 與MVPA、粒子群優化（Particle Swarm Optimization，PSO）算法和遺傳算法（Genetic Algorithm，GA）進行比較實驗。

本文的實驗環境為：計算機CPU 為i5-3210M，內存為4 GB，操作系統Windows 7，編程軟件Matlab 2016b。ACMTMMVPA 的參數設置為：球員數量PlayersSize=100，隊伍數量TeamsSize=20，最大迭代次數MAXITER=300，φ=0.001，最大適應度評價次數為3× 104。MVPA 的參數設置為：球員數量PlayersSize=100，隊伍數量TeamsSize=20，最大迭代次數MAXITER=300，最大適應度評價次數為3× 104。PSO 算法的參數設置為：群體規模N=30，最大迭代次數T=300，權重的上下界為wmax=0.9，wmin=0.4，學習因子c1=c2=2，最大適應度評價次數為3× 104。GA 的參數設置為：種群規模PopSize=100，最大迭代次數MaxIteration=300，交叉概率Pc=0.6，變異概率Pm=0.01，最大適應度評價次數為3× 104。

表1 測試函數Tab.1 Test functions

3.2 算法的尋優精度及計算成本比較

本節評估在相同的最大適應度評價次數下，算法的尋優精度以及平均運行時間。對于每個測試函數，ACMTMMVPA、MVPA、PSO 和GA 均獨立運行30 次，結果如表2 所示，其中：Best 表示最優值，Mean 表示均值，Worst 表示最差值，Sd表示標準差，Meantime表示平均運行時間（單位：s）。

由表2 可知，對于f2(x)、f3(x)、f4(x)、f5(x)、f7(x)、f9(x)、f10(x)、f13(x)，本文算法均達到了最優解，其他函數的優化結果也都要優于MVPA、PSO 算法和GA 算法，同時通過不同測試函數在測試結果的標準差可知，ACMTM-MVPA具有較好的魯棒性。

在算法運行時間方面，ACMTM-MVPA在競爭階段之前添加了訓練階段，使得算法在前期可以搜索到更多的可行解，同時增加了算法的運行時間；自適應球員進化因子的添加，一方面能夠讓算法避免過早陷入局部最優解，另一方面，也會抑制算法的收斂速度，并增加了算法的運行時間。雖然訓練階段和自適應球員進化因子的添加增加了算法的運行時間，但極大地提高了算法的優化精度，而且運行時間的增加在可接受的范圍內。

為了更直觀地顯示ACMTM-MVPA 的優化精度和收斂速度，圖1～6 展示了函數f2(x)、f4(x)、f6(x)、f9(x)、f10(x)、f14(x)的收斂曲線（部分函數縱坐標的函數值取以10 為底的對數）。從圖中可以看出，與MVPA、PSO 算法和GA 算法相比，ACMTM-MVPA 不僅優化精度高而且收斂速度快。對于ACMTM-MVPA 來說，6個測試函數都在50次迭代次數以內就收斂到一個較優解，由圖1、圖2、圖5可知，f2(x)、f4(x)、f10(x)均收斂到相應的理論最優值。可以得出，ACMTM-MVPA對復雜函數的優化具有十分顯著的效果。

圖1 f2(x)進化曲線Fig.1 Evolution curve of f2(x)

圖2 f4(x)進化曲線Fig.2 Evolution curve of f4(x)

3.3 算法的收斂速度比較

為了測試ACMTM-MVPA 的收斂速度，設定各個函數的優化精度為10E-15，函數的維數為500，設定適應度函數最大評價次數為3× 104，獨立運行20 次，比較搜索到給定精度需要的最小評價次數Mini_FEs、平均評價次數Mean_FEs以及達到優化精度的成功率SR［9］，測試結果如表3 所示。成功率指的是尋優達到給定精度的次數與總次數的比值，反映了算法的穩健性；函數平均評價次數反映算法的收斂速度和計算代價。

圖3 f6(x)進化曲線Fig.3 Evolution curve of f6(x)

圖4 f9(x)進化曲線Fig.4 Evolution curve of f9(x)

圖5 f10(x)進化曲線Fig.5 Evolution curve of f10(x)

圖6 f14(x)進化曲線Fig.6 Evolution curve of f14(x)

由表3 可知，ACMTM-MVPA 搜索到給定精度所需的評價次數的最小值、平均值在大多數函數測試中都是最小的，在同樣的精度條件下，評價次數越少，說明算法的搜索速度越快。盡管ACMTM-MVPA 在處理函數f11時的搜索速度跟其他三個算法一樣，但是在其他14個函數上都優于MVPA、PSO 算法和GA算法。此外，成功率為0表明，對于20次獨立運行，在規定的迭代次數下，算法不能達到給定的優化精度；成功率為1 表明，對于所有20 次獨立運行，在規定的迭代次數下，算法都能達到給定的優化精度。表3 結果表明，本文算法相較于其他算法具有更好的收斂速度和穩健性。

表2 實驗結果對比（500維）Tab.2 Comparison of experimental results（500 dimensions）

續表

表3 算法評價次數比較Tab.3 Comparison of algorithmic evaluation times

4 ACMTM-MVPA在暴雨強度公式中的應用

隨著經濟社會的發展，中國步入城鎮化快速發展的階段，城鎮化率已由1978年的17.9%增加到2018年的59.58%。在全球氣候變化與快速城鎮化背景下，中國城市洪澇災害日益嚴重。城市洪澇災害已成為制約當地社會經濟發展的突出問題［10-11］。暴雨強度公式是確定城市防洪除澇或者排水工程設計標準的重要依據，其選擇的合理性直接影響工程的規模和效益，也直接影響著工程投資建設進度［12］。

根據我國現行的排水規范，一個重現期的暴雨強度公式［12］形式為：

式中：h為暴雨強度（mm/s）；t為降雨歷時（min）；A、B、n為常數。這是常用的一種洪水災害危險性分析模型，已經被廣泛用于給水排水設計等洪水災害管理中，由公式可知，該式為超定非線性方程，因此公式的參數優化問題實際上是一個非線性優化問題。然而，傳統的優化方法不僅計算量大、通用性差，且所求結果也往往不太理想，本文提出將ACMTM-MVPA應用于暴雨強度公式參數優化中，以期獲得良好的效果。

根據文獻［13］附表中不同重現期暴雨強度與降雨歷時的數據。用ACMTM-MVPA 來優化式（18）中的參數A、B、n使下式優化準則函數極小化［13］：

其中：參數A、B、n的變化范圍分別是［0，30］，［0，100］，［0，2］，算法的迭代次數T=1 000。為了方便比較，同時給出了文獻［14］中提供的使用傳統回歸法（簡稱傳統法）、優選回歸法（簡稱優選法）以及文獻［15］中自適應光學優化算法所得的擬合結果，表4 給出了不同方法對各重現期暴雨強度公式擬合效果的比較。由表4 可知，在相同的數據和標準情況下，傳統法和優選法的優化結果明顯弱于ACMTM-MVPA 和自適應光學優化算法，雖然自適應光學優化算法和ACMTM-MVPA 的優化結果相近，但由文獻［15］可知，自適應光學優化算法的迭代次數為5 000，本文中ACMTM-MVPA 的迭代次數只有1 000次，由此可知，ACMTM-MVPA 具有較快的優化速率和較高的擬合精度。同時，ACMTM-MVPA 具有參數設置簡單、搜索精度高以及不易陷入局部最優解的特點，可嘗試廣泛應用于不同的復雜優化模型。

表4 不同方法對各重現期暴雨強度公式擬合效果的比較Tab.5 Fitting effect comparison of storm intensity formula for each reproducing period by different methods

5 結語

本文針對MVPA 在求解復雜優化問題時尋優精度低、收斂速度慢的缺陷，提出一種考慮多種訓練方式的自適應最有價值球員算法。在競爭階段之前添加了訓練階段，來提高球員的能力和球隊的整體實力，從而提高最優解的質量；在隊伍競爭階段，引入自適應球員進化因子，均衡了算法全局開發和局部搜索能力，從而有效地提高算法的尋優精度和收斂速度。選取了15 個測試函數進行數值實驗，結果表明，與MVPA、PSO 算法和GA 相比，本文提出的ACMTM-MVPA 在求解復雜優化問題時不僅收斂速度快，而且優化精度高。同時，將算法應用于暴雨強度公式參數優化中，并與傳統回歸法、優選回歸法和自適應光學優化算法進行比較，結果表明，ACMTMMVPA 對暴雨強度公式參數優化中取得了最好的擬合效果，說明該算法的應用是成功的，可以考慮推廣至其他復雜優化問題的應用。