國外新穎優(yōu)化算法

韓毅　徐梓斌　張亮　鄧麗麗　章美玲

摘 要：本文描述了2018年文獻[1]提出的一種新穎元啟發(fā)式優(yōu)化算法——排超聯(lián)賽算法（Volleyball Premier League Algorithm， VPLA），算法靈感來自于排球超級聯(lián)賽的一個完整賽季中，各個排球隊之間的比賽和互動過程。在排球比賽過程中，教練的臨場指揮會起到關鍵作用，因此VPLA算法將臨場指揮作為重要算子之一。此外，VPLA算法還考慮了排球比賽過程中的換人活動和排球隊員通過學習而提高自身能力的過程。

關鍵詞：排超聯(lián)賽;互動;元啟發(fā)式;算子

排球比賽中，一張網(wǎng)將兩隊各六名隊員分開。為了獲得一分，每個隊必須讓球落在另一隊的場地上。一方的球員試圖讓球越過球網(wǎng)落到另一隊的場地上，另一隊球員極力救球并盡力讓球過網(wǎng)落到對方場地，場上形成了拉鋸戰(zhàn)。拉鋸戰(zhàn)持續(xù)進行，直到某隊出現(xiàn)失誤使得對方得1分。比賽即將開始時，主教練把出場隊員名單交給第二裁判員。運動員入場后，3名球員站在前排，另外3人站在后排。每個隊都可以根據(jù)自己隊員的情況，組成自己的場上陣容。比賽期間，教練站在球場附臨場指揮和指導運動員。板凳球員坐在場下，隨時準備好參加比賽（圖1）。

在一場普通排球比賽中，影響比賽結果的因素很多。每場比賽結果未知，球隊輸贏都有可能，弱隊勝強隊也不足為奇。通常用球隊實力來刻畫強隊更有可能擊敗對手的事實。球隊關注即將到來的比賽，不考慮后續(xù)即將到來的比賽。鑒于之前的賽果、當前球隊實力和贏下比賽的幾率，每支球隊在場上的首發(fā)陣容會進行相應調(diào)整。當球隊i擊敗球隊j時，球隊i贏得比賽的優(yōu)勢就是球隊j的劣勢，球隊有了某種劣勢，也說明球隊缺少某種優(yōu)勢。

聯(lián)賽等于種群，賽季輪次表示當前迭代次數(shù)，球隊是種群的解，星期表示每輪聯(lián)賽賽程。

排球比賽的教練可以通過現(xiàn)場指導和平時指導來提高運動員的基本技能。教練通過模擬與真實比賽強度相同的訓練，來提升運動員的移動速度、預判能力、把握時機能力、溝通更累和團隊合作能力，從而滿足團隊的戰(zhàn)略要求。

一、VPLA算法

（一）解表達方式

球隊成員分為場上球員、板凳球員和教練。算法的解由兩個部分組成，分別稱為主動部分和被動部分。主動部分代表每個團隊的六名場上隊員，被動部分代表板凳隊員，解的適應度函數(shù)值由這六名場上隊員決定（圖2）。

球隊的陣容決定了球隊在場上的整體風格，一般來說排球比賽里通常有3種陣容——“4-2”“2-4”和“5-1”，隊形中“H-S”風格表示攻擊手和二傳手的個數(shù)。教練需要根據(jù)場上球員和板凳球員的類型和能力決定最好的陣容，通常來看場上隊員和板凳球員的數(shù)量相同。在比賽過程中，陣容會不斷變化。教練在比賽中會不斷安排陣容調(diào)整，因此場上隊員與板凳隊員的角色也不斷變化（圖3）。

（二）初始解

每支球隊都有自己的陣容和替補，對于VPLA算法，NT表示球隊數(shù)量，x表示第i支球隊場上陣容的第j個隊員，x表示第i支球隊替補席的第j個隊員。

初始種群可以由F矩陣和S矩陣表示，矩陣的行表示球隊個數(shù)，矩陣的列表示隊員數(shù)。

二、比賽賽程

賽程是比賽的重要因素，VPLA算法采用單循環(huán)賽制（Single Round Robin， SRR）生成聯(lián)賽賽程。在每個賽季，每支球隊都只與其他球隊碰面一次且僅一次。進入下一個賽季，所有球隊再重復碰面。球隊的數(shù)量一般為偶數(shù)，如果球隊的數(shù)量非偶數(shù)，則增加一個虛擬球隊，與虛擬球隊碰面的球隊當期輪次輪空。

在應用SRR方法時，畫一個N-1條邊的規(guī)則多邊形，每個頂點和中心點表示一支球隊，用水平線連接多邊形左右兩邊對應的頂點，還有一條邊連接多邊形的中心點和最上邊的頂點。每條連接邊代表一場比賽，端點表示兩支對戰(zhàn)的球隊。通過順時針旋轉(zhuǎn)多邊形，可以確定下一輪次的對陣表，一旦多邊形轉(zhuǎn)了一圈，則進入下一個賽季。圖4利用了SRR方法，設有N個球隊，每支球隊每個賽季要打N-1場比賽，賽季總比賽場次為N（N-1）/2。

（一）競賽

通常情況下，每支球隊每周只有一場比賽，比賽成績只有輸贏兩種情況。球隊成績要通過五局三勝制決定，前四局中局點為25分，如果兩隊24比24，則贏得該局比賽需要2分分差，第五局比賽為搶15分。算法通過公式（3-4）確定球隊贏球概率（實力）。

φ（i）表示第i支球隊的實力，f（x）表示第i支球隊的適應值，Z表示所有球隊的適應值總和。如果目前有兩支球隊j和k進行比賽，則球隊j贏得比賽的概率為P（j，k）。

VPLA算法采用均勻分布的隨機數(shù)r∈[0，1]來確定比賽的獲勝者， 如果r≤p（j，k）則j隊獲勝，否則k隊獲勝。顯然，如果兩個球隊的適應度值相差不大，則p（j，k）和p（k，j）趨近0.5。比賽獲勝者確定后，失敗的球隊采用“知識共享”、“位置重排”和“換人”策略彌補劣勢，獲勝球隊采用“主導”策略。

（二）知識共享策略

排球教練在比賽中對球隊表現(xiàn)有顯著影響。教練負責訓練運動員、在比賽中評估球員的技能和安排場上陣容。教練最主要的任務之一是分析隊員和對手在比賽中的表現(xiàn)?；诜治鼋Y果，教練獲取了新的技戰(zhàn)術知識。之后，教練與球員和替補隊員共享知識。教練實時分析比賽中的對戰(zhàn)過程、比賽間歇和每局比賽的持續(xù)時間，并指導場上隊員和替補隊員。VPLA算法將教練的活動稱為知識共享，這能有助于處于劣勢的球隊在比賽中改善場上表現(xiàn)。

λf和λs是場上陣容和替補陣容系數(shù)，r1和r2是[0，1]之間隨機數(shù)，如果用δks表示知識共享率，則Nks=n×δks表示球隊中需要進行知識共享的隊員數(shù)量。

（三）位置重排策略

在排球比賽中，每個位置決定一名球員的場上職責。球員們都有各自需要完成的任務，他們將盡最大努力相互合作，努力取得最佳戰(zhàn)績。場上隊員的角色包括攔網(wǎng)手、外線攻擊手、自由人、二傳手和對手。教練試圖為每個角色安排最合適的球員，以便在聯(lián)賽中獲得最好的戰(zhàn)績。由于財政資源短缺等狀況，球隊沒有足夠資金招募到所有想要的球員，所以球隊必須利用現(xiàn)有的球員，并試圖在聯(lián)賽中提升球員的表現(xiàn)。球員在教練的領導下接受訓練，以便他們有能力完成各種場上角色（打所有不同的位置）。VPLA算法對輸球的球隊采用位置重排策略，使得球隊中的隊員位置可以相互交換，以獲得更好的表現(xiàn)。圖1中給出了位置重排策略的應用，左邊球隊將球員2和4的位置互換。如果δrs位置重排率，則Nrs=n×δrs表示位置重排次數(shù)。