萬(wàn) 珺， 何 健

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

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

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

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

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

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

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

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

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

APO算法主要分為3個(gè)步驟.

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

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

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

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

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

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

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

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

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

表1 各隊(duì)之間的公路距離

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)設(shè)置

進(jìn)行了一個(gè)驗(yàn)證性實(shí)驗(yàn)來(lái)證明所提出方法的可行性.為了簡(jiǎn)化描述，選擇了2018年中超比賽中的6支球隊(duì)進(jìn)行巡回賽.巡回賽為每支球隊(duì)都與其他球隊(duì)進(jìn)行比賽，最終以積分來(lái)排名.6支球隊(duì)分別為江蘇蘇寧、北京人和、山東魯能、上海申花、廣州恒大和河南建業(yè).巡回賽中，每天只比賽一場(chǎng)，整個(gè)賽程共30天.賽程優(yōu)化的目標(biāo)是實(shí)現(xiàn)最小化所有球隊(duì)的行程距離總和.在這個(gè)例子中，我們?cè)O(shè)定各城市之間的公路距離是固定的，如表1所示.另外，對(duì)于擬態(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è)”隊(duì)為主場(chǎng)球隊(duì)，“恒大”隊(duì)為客場(chǎng)球隊(duì).可以看到，每支球隊(duì)分別和其他5支球隊(duì)進(jìn)行主客場(chǎng)共10場(chǎng)比賽，整個(gè)賽程為30場(chǎng)比賽.

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

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

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

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

表4 兩種賽程方案的行程距離對(duì)比

3 結(jié) 論

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

參考文獻(xiàn)

[1] 曾芳,桂趙曼.體育聯(lián)賽中基于GSO算法的賽程優(yōu)化方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 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] 都揚(yáng)揚(yáng), 木仁. 具有主客場(chǎng)賽制的各大聯(lián)賽賽程優(yōu)化安排與設(shè)計(jì)[J]. 中國(guó)管理科學(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é)報(bào), 2018, 40(1): 77-81.

[7] 沈林成, 王祥科, 朱華勇,等. 基于擬態(tài)物理法的無(wú)人機(jī)集群與重構(gòu)控制[J]. 中國(guó)科學(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]. 計(jì)算機(jī)研究與發(fā)展, 2011,48(5):848-854.