利用擬態(tài)物理學(xué)優(yōu)化算法的中超賽程優(yōu)化方法*

萬 珺， 何 健

(1.武漢輕工大學(xué) 體育部，湖北 武漢 430048;2.武漢輕工大學(xué) 數(shù)學(xué)與計算機學(xué)院，湖北 武漢 430048)

對于主客場賽制的聯(lián)賽，賽程的時間表直接影響各隊的行程安排.優(yōu)秀的賽事組織者會在日程安排上盡量減少一些交通等費用[1].因此，行程成本問題成為多年來重要的優(yōu)化問題.比賽時間表的優(yōu)化研究具有如下意義[2]：(1) 降低比賽中各支球隊的行程成本；(2) 合理安排比賽間隔，使運動員保持充沛體力.關(guān)于行程費用，球隊總是乘交通工具往返于城市之間，隨著石油價格迅速上漲，交通費用變高.另一個考慮因素是運動員的體力，運動員在沒有足夠休息時間的情況下連續(xù)比賽，會降低比賽競技能力[3].所以，有必要為每個球隊安排公平賽程.

調(diào)度大型運動賽程通常是非常困難的，需要考慮特定的運動規(guī)則，以及許多常常相互沖突的因素，包括行程距離等.由于存在一個較大的解決方案搜索空間，這個調(diào)度過程通過人工完成是相對費時的.目前，一些學(xué)者提出了一些賽程編排方案.例如，文獻(xiàn)[4]以最小化所有球隊的行程距離為目標(biāo)，提出了一種基于蒙特卡洛的賽程優(yōu)化方法.文獻(xiàn)[5]提出一種基于集成約束規(guī)劃的賽程優(yōu)化方法，用來最小化每個球隊的轉(zhuǎn)場次數(shù).然而，大多數(shù)關(guān)于多維分配問題的研究集中在三維問題上，為了使其可以自然擴展到更高維度，這些方法都是利用拉格朗日松弛來識別強邊界的分支邊界.多維分配問題一般是NP難題，由于問題的復(fù)雜性，啟發(fā)式解決方法能夠得到更好的結(jié)果.為此，一些學(xué)者提出了一些智能搜索算法[6]來搜索最優(yōu)賽程編排方法，如禁忌搜索、遺傳算法、模擬退火算法等，目的是降低比賽中各球隊的時間和行程成本.

擬態(tài)物理學(xué)優(yōu)化(artificial physics optimization, APO)算法[7]是一種新的智能搜索算法.該算法是受牛頓第二定律啟發(fā)，通過個體間的虛擬力來調(diào)整個體的速度和位置，最終收斂到全局最優(yōu)解[8].與傳統(tǒng)遺傳算法和粒子群優(yōu)化算法相比，APO具有較好的全局搜索和避免陷入局部最優(yōu)的能力，且收斂速度快、穩(wěn)定性好[9].為此，本文利用APO算法提出一種賽程優(yōu)化方法，以中超聯(lián)賽為例，最小化聯(lián)賽的總行程距離.實驗結(jié)果表明提出的方法能夠有效減少各隊的總行程，具有可行性和有效性.

1 利用APO算法的賽程編排方法

1.1 擬態(tài)物理學(xué)優(yōu)化算法(APO)

擬態(tài)物理學(xué)是由Spear等人在2005年受物理力學(xué)而啟發(fā)提出的一種優(yōu)化方法.在其基本框架中，問題的解決方案表現(xiàn)為物理個體，每個個體都具有空間質(zhì)量、速度和扭矩分量.它們的移動受到物理規(guī)則的控制.每個個體由于其他個體的虛擬力作用，在搜索空間中尋找最佳位置[10].

在APO算法中，多維范圍內(nèi)非線性目標(biāo)函數(shù)的全局最小位置問題定義為：

min{f(X):X∈Ω?Rd},f:Ω?Rd→R，

APO算法主要分為3個步驟.

第一步：初始化.隨機形成d維決策空間中的組群，并初始化組群中的個體數(shù)量N，引力常數(shù)G.根據(jù)問題類型，粒子的初始速度設(shè)定為零.為每個個體計算目標(biāo)函數(shù)值，在t階段具有最大適應(yīng)度的個體的位置向量稱為最佳x，即xbest.

第三步：移動.將個體移動到一個特定的位置，這是根據(jù)計算的總力來完成的.這個力被用來計算個體速度和位置的更新.在時間t+1時，個體i的空間坐標(biāo)和速度由以下等式更新：

式中，α是在[0,1]范圍內(nèi)均勻分布的隨機值，0≤w<1是用戶定義的慣性值，較大的w會引起較大的速度變化.

1.2 目標(biāo)函數(shù)

在本文中，賽程編排的目標(biāo)函數(shù)是所有球隊的總行程距離.同時設(shè)定了一些懲罰函數(shù)，目標(biāo)是使優(yōu)化算法快速接近最優(yōu)可行解.讓不可行的解決方案進(jìn)入種群非常重要，因為良好的解決方案通常是在可行和不可行的解決方案之間進(jìn)行培育的結(jié)果.在這里，我們以兩支球隊所在城市的最短公路距離作為路程度量.目前百度地圖的應(yīng)用非常廣泛，從中提取距離信息是非常方便且有效的，以此來計算各球隊之間的確切距離.那么，適應(yīng)度函數(shù)由下式給出：

式中，h表示懲罰權(quán)重，設(shè)置為100，RTk表示所違反約束的編號，TDi表示球隊i行程的總里程.

約束條件：RT1表示每支球隊的主場城市之間的距離是固定的，且往返行程也相同.RT2表示每支球隊客場打完一場比賽后不回主場城市休息，直接轉(zhuǎn)到下場比賽城市.RT3表示每支球隊連續(xù)兩場比賽之間的間隔不少于1天.

1.3 賽程編排優(yōu)化的基本步驟

本文采用了一種新的智能搜索算法來進(jìn)行賽程編排優(yōu)化，即擬態(tài)物理學(xué)優(yōu)化算法.編排優(yōu)化的基本步驟如下：步驟1，輸入?yún)?shù)和約束條件，例如球隊數(shù)量、距離信息、比賽持續(xù)時間等.步驟2，生成隨機時間編排表種群，并獲取總行程距離.步驟3，計算編排表的適應(yīng)度函數(shù)，并通過擬態(tài)物理學(xué)優(yōu)化算法進(jìn)行尋優(yōu).步驟4，將當(dāng)前獲得的局部最優(yōu)解與全局最優(yōu)解進(jìn)行比較，計算施加在每個個體上的力，并更新個體的速度和位置.步驟5，待算法收斂或達(dá)到最大迭代次數(shù)，獲得最終的最優(yōu)方案.

表1 各隊之間的公路距離

2 實驗及分析

2.1 實驗設(shè)置

進(jìn)行了一個驗證性實驗來證明所提出方法的可行性.為了簡化描述，選擇了2018年中超比賽中的6支球隊進(jìn)行巡回賽.巡回賽為每支球隊都與其他球隊進(jìn)行比賽，最終以積分來排名.6支球隊分別為江蘇蘇寧、北京人和、山東魯能、上海申花、廣州恒大和河南建業(yè).巡回賽中，每天只比賽一場，整個賽程共30天.賽程優(yōu)化的目標(biāo)是實現(xiàn)最小化所有球隊的行程距離總和.在這個例子中，我們設(shè)定各城市之間的公路距離是固定的，如表1所示.另外，對于擬態(tài)物理學(xué)優(yōu)化算法，設(shè)置參數(shù)為種群數(shù)量N=50，慣性權(quán)重w=0.5，引力常數(shù)G=0.09.

2.2 結(jié)果分析

為了更好地進(jìn)行性能分析，將本文方法與文獻(xiàn)[4]方法進(jìn)行比較，兩種方法獲得的最優(yōu)賽程編排方案如表2和表3所示.其中，“建業(yè)-恒大”表示“建業(yè)”隊為主場球隊，“恒大”隊為客場球隊.可以看到，每支球隊分別和其他5支球隊進(jìn)行主客場共10場比賽，整個賽程為30場比賽.

從表2和表3可以看出，文獻(xiàn)[4]方法中的賽程安排沒有本文方法的科學(xué)，文獻(xiàn)[4]方法中的第20和第21場比賽中，恒大隊連續(xù)兩天進(jìn)行比賽，雖然都是在主場比賽，但這樣也很消耗隊員體力，不能很好地保證公平性.而在本文方法的賽程安排中，沒有一支球隊會連續(xù)比賽.

表2 文獻(xiàn)[4]方法獲得的賽程編排方案

表3 本文方法獲得的賽程編排方案

為了更加清晰地顯示兩種賽程編排方案的行程，表4給出了統(tǒng)計結(jié)果.可以看出，本文方法的賽程編排方案中，江蘇蘇寧、山東魯能、上海申花、廣州恒大和河南建業(yè)這5支隊伍的行程距離都有所降低，只有北京人和的行程稍微增加.本文賽程編排方案的總行程為46 807 km，比文獻(xiàn)[4]方案減少了2 997 km，優(yōu)化率為6.02%，證明了本文方法的有效性和可行性，可以為中超比賽等類似比賽進(jìn)行賽程編排優(yōu)化.

表4 兩種賽程方案的行程距離對比

3 結(jié) 論

為了提高中超聯(lián)賽的賽程經(jīng)濟性，提出了一種利用擬態(tài)物理學(xué)優(yōu)化算法的賽程優(yōu)化方法.根據(jù)百度地圖獲取每支球隊主場之間的公路距離，以最小化總行程距離為目標(biāo)，通過APO算法獲得一個最佳賽程編排方案.結(jié)果表明在具有6支隊伍的比賽編排實驗中，本文方法的編排方案更加合理有效，大大降低了球隊行程距離.

參考文獻(xiàn)

[1] 曾芳,桂趙曼.體育聯(lián)賽中基于GSO算法的賽程優(yōu)化方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2018, 40(1),72-76.

[2] HAO G, ZHANG J. Design and practice of the competition schedule arrangement system of swimming sports based on artificial intelligence[C]// International Conference on Real Time Intelligent Systems. Springer, Cham, 2016:440-454.

[3] HUANG G, PING L, WANG Q. A hybrid metaheuristic ACO-GA with an application in sports competition scheduling[C]// International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/distributed Computing. IEEE, 2007:611-616.

[4] 都揚揚, 木仁. 具有主客場賽制的各大聯(lián)賽賽程優(yōu)化安排與設(shè)計[J]. 中國管理科學(xué), 2015，23(1):171-175.

[5] LARSON J, JOHANSSON M, CARLSSON M. An integrated constraint programming approach to scheduling sports leagues with divisional and round-robin tournaments[C]// International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer International Publishing, 2014:144-158.

[6] 劉嵐,蘭小毅.基于MILP模型和QPSO算法的綠色物流調(diào)度方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2018, 40(1): 77-81.

[7] 沈林成, 王祥科, 朱華勇,等. 基于擬態(tài)物理法的無人機集群與重構(gòu)控制[J]. 中國科學(xué):技術(shù)科學(xué), 2017,47(3): 266-285.

[8] JIA B, ZHONG P, ZHU F. Adaptive artificial physics optimization of reservoir flood regulation[J]. Journal of Hydroelectric Engineering, 2016, 35(8):32-41.

[9] TEEPARTHI K, KUMAR D M V. Security-constrained optimal power flow with wind and thermal power generators using fuzzy adaptive artificial physics optimization algorithm[J]. Neural Computing & Applications, 2016:1-17.

[10] 謝麗萍,曾建潮.基于擬態(tài)物理學(xué)方法的全局優(yōu)化算法[J]. 計算機研究與發(fā)展, 2011,48(5):848-854.