基于模擬退火算法的中超賽程編排優(yōu)化研究

劉寶友，王 濤，馬延龍

(河北科技大學(xué)環(huán)境科學(xué)與工程學(xué)院，河北石家莊 050018)

?

基于模擬退火算法的中超賽程編排優(yōu)化研究

劉寶友，王 濤，馬延龍

(河北科技大學(xué)環(huán)境科學(xué)與工程學(xué)院，河北石家莊 050018)

為了促進(jìn)賽事的公平性、實(shí)現(xiàn)人性化的賽程編排設(shè)計，同時達(dá)到減少出行里程、節(jié)約資源、保護(hù)環(huán)境的目的，采用計算機(jī)輔助建模的方法，對中超賽程編排進(jìn)行優(yōu)化研究。假設(shè)以總體出行里程最短、兼具賽程的公平性和設(shè)計的人性化為優(yōu)化目標(biāo)，以百度地圖提供的球隊(duì)所在城市間的距離數(shù)據(jù)為依據(jù)，通過改進(jìn)模擬退火算法對2015年中超賽程編排進(jìn)行優(yōu)化，運(yùn)用Matlab求解得到最優(yōu)方案。結(jié)果表明：在最優(yōu)賽程安排下得到的各支球隊(duì)最優(yōu)出行里程為5.022×105km，相對2015年中超的實(shí)際賽程編排總里程減少了12.08%，由此節(jié)省燃油14.50 t，減少排放二氧化硫43.9 kg，對大氣中二氧化硫減排的貢獻(xiàn)率為11.11%，節(jié)約資金91 467.4元。該結(jié)果可以為中超實(shí)際主客場賽程編排的優(yōu)化提供參考。

環(huán)境規(guī)劃與管理；中超賽程；模擬退火算法；最優(yōu)化；冷卻進(jìn)度表

模擬退火算法(simulated annealing algorithm)是一類從局部拓展到全局的隨機(jī)性組合系統(tǒng)優(yōu)化方法[1]，它利用雜交粒子群優(yōu)化算法中的雜交運(yùn)算與帶高斯變異粒子群優(yōu)化算法中的變異運(yùn)算處理大規(guī)模復(fù)雜數(shù)據(jù)的優(yōu)化問題[2]。與其他方法相比，該算法具有描述簡單、約束較少、使用靈活、運(yùn)行效率高等優(yōu)點(diǎn),適于求解非確定多項(xiàng)式問題(NP)、旅行商問題(TSP)等優(yōu)化組合問題。改進(jìn)退火算法的優(yōu)化性能主要涉及全過程狀態(tài)函數(shù)與溫度更新函數(shù)，這些環(huán)節(jié)的設(shè)計將決定模擬退火算法的快速性、收斂性與魯棒性等[3-4]。

圖1 2015年中超地圖
Fig.1 Geographical map of Chinese Super League in 2015

1 中超賽程現(xiàn)狀及分析

2015年中超聯(lián)賽采用主客場雙循環(huán)賽制[9]，參賽隊(duì)伍是2014年排名前16的球隊(duì)(升級隊(duì)代替降級隊(duì))。球隊(duì)在一個城市進(jìn)行完一場比賽后乘坐交通工具進(jìn)入另一個城市參加比賽，所有球隊(duì)進(jìn)行完上半程比賽后回到各自城市休整，下半程與上半程對陣球隊(duì)相同但主客場位置調(diào)換，所有比賽結(jié)束后，各球隊(duì)回到各自所在的城市。

在中超賽程中，考慮到旅途勞累與主場優(yōu)勢等因素，任一球隊(duì)不宜連續(xù)3次以上(>3)做主場或客場，此時通過建立退火模型進(jìn)行系統(tǒng)優(yōu)化，不僅可使賽程編排更為合理，更能確保球隊(duì)隊(duì)員實(shí)力的正常發(fā)揮，實(shí)現(xiàn)相對公平。各支球隊(duì)的地理位置與所在城市之間的距離分別如圖1和表1所示。

表1 2015年不同中超球隊(duì)之間的距離

2 中超賽程優(yōu)化模型的構(gòu)建

2.1 模型假設(shè)

在賽制編排中，將中超賽程所有方案表示為一個有向的賦權(quán)圖C=(V，E)[10]，其中V∈(V1,V2,…,V16)，是16支球隊(duì)集合中的一支;E∈(E1,E2,…,E16),是不同于V的另一支球隊(duì)。最優(yōu)賽程Z與有向?qū)﹃囐惓藽的關(guān)系為

(1)

約束條件如下：

1)任意兩地往返路程相同,即Si,j=Sj,i；

2)交通工具統(tǒng)一為宇通標(biāo)準(zhǔn)55座大巴車，中途不更換其他交通工具；

3)Sa,b=0,a和b為同在一個城市的不同球隊(duì)；

4)所有球隊(duì)打完上半程后回各自城市進(jìn)行休整；

5)退火算法參數(shù)取舍得當(dāng)，不會陷入局部最優(yōu)；

6)兩城市之間的路程精確到整數(shù)位。

2.2 模型分析

首先將2014年球隊(duì)排名作為2015年各隊(duì)的隊(duì)號(用a1,a2,…,a16表示，升級隊(duì)代替降級隊(duì))，按照抽簽法的原則進(jìn)行單循環(huán)隨機(jī)排列，對應(yīng)到b1,b2,…,b16的位置。對16支球隊(duì)的位置進(jìn)行蛇形編排，即對陣雙方位置為bi?b17-i，固定1號位置不動，2號位置到16號位置(包括位置上的球隊(duì))，順序輪轉(zhuǎn)，循環(huán)一輪后對陣雙方為b1?b2, b3?b16, b4?b15, b5?b14, b6?b13, b7?b12, b8?b11, b9?b10。共可進(jìn)行15輪循環(huán)，此時位置對陣總數(shù)U=15輪×8場/輪=120場。

將15輪比賽進(jìn)行全排列共有15！≈1.3×1012種可能情況，編排情況相對較多，應(yīng)用模擬退火算法，根據(jù)Metropolis接受準(zhǔn)則[11-12]，持續(xù)進(jìn)行“產(chǎn)生新解—判斷與目標(biāo)函數(shù)的差距—決定接受或舍棄”的迭代過程，算法法則如下：

(2)

利用概率算子min{1,exp(-Δf/Tk)}>random[0,1]選擇性接受可行解，以概率exp(-Δf/Tk)選擇性接受劣質(zhì)解[13-15]。通過迭代算子Tk+1=CTk，k←k+1，其中C∈(0,1)進(jìn)行迭代運(yùn)算，則速度與位置更新公式如下：

vi,j(k+1)=χ[vi,j(k)+c1r1(pi,j(k)-xi,j(k))+c2r2(pg,j(k)-xi,j(k))],

(3)

xi,j(k+1)=xi,j(k)+vi,j(k+1),(j=1,…,n),

(4)

(5)

在運(yùn)行算法過程中，性能相對較好的編排結(jié)果應(yīng)該被賦予更高的選中率，若用f代表目標(biāo)函數(shù)，可用式(6)為概率Pi選擇合適的取值。

(6)

為了提升賽程的相對公平性，任一球隊(duì)不宜連續(xù)3次以上(>3)做主場或客場，則模型設(shè)計基本原則如下：

1)任一球隊(duì)如果本輪打主場則下一輪優(yōu)先考慮打客場；

2)任一球隊(duì)如果本輪打客場則下一輪優(yōu)先考慮打主場。

設(shè)定第1輪比賽對陣雙方主客場隨機(jī)選取，從第2輪到第15輪主客場受限程度依次遞增，首先窮舉第1輪所有可能主客場情況并利用dgr_flag與wish_host分別提供危險標(biāo)志和希望標(biāo)志(初始值為零)，數(shù)據(jù)結(jié)構(gòu)如下:

dgr_flg=zeros(1,TEAM_NUM);%每個球隊(duì)提供一個危險標(biāo)志

wish_host=zeros(1,TEAM_NUM);%每個球隊(duì)希望打主場標(biāo)志。

2.3 算法尋優(yōu)步驟

16支球隊(duì)分為8組對陣，每組對陣有2種主客場情況，則共28=256種主客場情況，選取其中1種進(jìn)行完整的15輪循環(huán)，此時尋優(yōu)步驟如下：

1)在256種主客場編排中隨機(jī)選取1種情況進(jìn)行蛇形編排與順序輪轉(zhuǎn)，得到完整的15輪循環(huán)過程；

2)利用模擬退火算法進(jìn)行種群尋優(yōu)并判斷每組對陣的2支球隊(duì)是否已經(jīng)連續(xù)做了3次主場(或客場)[18-19]，如果對陣的2支球隊(duì)都已經(jīng)做了3次主場(或客場)且下一場希望相同，則結(jié)束進(jìn)程返回步驟1)重新隨機(jī)選取；

圖2 算法的總體流程圖Fig.2 Flow diagram of algorithm

3)如果對陣的2支球隊(duì)都已經(jīng)連續(xù)3次做了主場(或客場)，但2支球隊(duì)對待下一場比賽希望做主場還是客場的情況相反，此時可以完成循環(huán)并輸出最優(yōu)解；

4)如果對陣的2支球隊(duì)下一場都想做主場(或者客場)，但只有其中1支隊(duì)伍已經(jīng)連續(xù)3次做了主場(或客場)，則此隊(duì)擁有優(yōu)先選擇權(quán)，完成循環(huán)并輸出最優(yōu)解；

5)如果對陣的2支球隊(duì)下一場都想做主場(或客場)，但是2支球隊(duì)都沒有連續(xù)3次做主場(或客場)，則可根據(jù)隊(duì)號大小決定，隊(duì)號大的優(yōu)先選擇，完成循環(huán)并輸出最優(yōu)解。

圖3 利用模擬退火算法的全局尋優(yōu)結(jié)果Fig.3 Global optimization results by stimulated annealing algorithm

該算法的總體流程見圖2。在中超聯(lián)賽中，下半程賽程完全翻轉(zhuǎn)上半程賽程，即對陣雙方、主客場安排與輪次順序完全確定。本文從中超聯(lián)賽實(shí)際情況出發(fā)，在上半程對陣雙方與主客場安排確定的情況下利用退火算法對下半程進(jìn)行尋優(yōu)，將優(yōu)化后的上、下半程的賽程之和作為中超比賽整體的賽程，則此賽程即為最優(yōu)的全局編排方案[20]。

3 結(jié)果分析與討論

3.1 結(jié)果分析

按照模擬退火算法初始值設(shè)置的一般原則，經(jīng)過多次嘗試，選取初始退火溫度T0=500 000,在終止條件Tk+1=CTk中令C=0.95，通過運(yùn)行Matlab程序，可得到全局尋優(yōu)的模擬退火圖，如圖3所示。

運(yùn)行時長2 990.91s，隨機(jī)選取種類超過25萬種，最終得到表2所示的運(yùn)行結(jié)果。從表2可以得到每支球隊(duì)出行的具體路線，同時計算出16支球隊(duì)最短的出行里程為5.022×105km。

由于氣候等不可抗因素對賽程編排具有一定的影響，某些球隊(duì)所在城市在特定時段內(nèi)不適宜做主場。以某支球隊(duì)在前3場不適宜做主場為例，在利用算法尋找最優(yōu)結(jié)果之前，人為賦予該球隊(duì)主場危險標(biāo)志，即默認(rèn)此球隊(duì)在前3輪比賽之前已經(jīng)做主場參加了3場比賽，此時在進(jìn)行前3輪比賽中該球隊(duì)始終擁有優(yōu)先選擇主客場的權(quán)利，此時在算法尋優(yōu)過程中該球隊(duì)始終處于客場狀態(tài)，可得到在賽程前3場中此隊(duì)做客場的最優(yōu)情況。通過合理使用危險標(biāo)志與期望標(biāo)志，可使優(yōu)化的中超聯(lián)賽賽程更趨人性化設(shè)計，可有效避免一些不可抗因素對球賽的干擾，有利于球員各自水平的正常發(fā)揮。

表2 全局優(yōu)化后的中超賽程安排

注:表中各個球隊(duì)均以隊(duì)名中的后2個字作為簡稱，例如“上海申鑫”簡寫為“申鑫”。

3.2 結(jié)果討論

根據(jù)中國汽車燃料消耗量網(wǎng)(the website of automobile fuel consumption of China)的信息可知，標(biāo)準(zhǔn)宇通55座大巴車的百公里耗油量為25 L，0號柴油5.3元/L，GB 252—2015規(guī)定0號柴油含硫量不高于0.2%(質(zhì)量分?jǐn)?shù)，下同)，此處按0.15%計算。相對2015年中超實(shí)際編排方案，優(yōu)化后編排里程減少69 032 km，燃油量減少了14.50 t，節(jié)約資金91 467.4元，同時減少二氧化硫排放43.9 kg。實(shí)際應(yīng)用中，由于出行里程縮短而使道路通暢率上升，百公里耗油量隨之降低，最終節(jié)能效果更加明顯。

根據(jù)2015-09-07人民網(wǎng)環(huán)保部報道，2015年上半年中國二氧化硫總體排放量為989.1萬t，機(jī)動車排放量約占總排放量的6%，即59.346×104t。由以上數(shù)據(jù)計算可知，優(yōu)化后賽程編排對二氧化硫排放貢獻(xiàn)率由4.5×10-8減少為4.0×10-8，貢獻(xiàn)率減少了11.11%。因此，對賽程進(jìn)行優(yōu)化編排對改善空氣質(zhì)量具有一定的作用。

4 模型評價

優(yōu)化后的模型通過合理嵌套模擬退火算法全局尋優(yōu)，可以快速尋找到中超比賽最優(yōu)的主客場賽程方案和各隊(duì)的行程路線，程序簡單且可操作性強(qiáng)；在中超賽程下半程對陣雙方和主客場確定的情況下利用模擬退火算法優(yōu)化輪次，相比于中超目前下半程輪次與上半程相同的情況而言，具有更高的實(shí)用價值。

優(yōu)化后的模型通過抽簽法隨機(jī)編排位置號，智能編排減少人工干預(yù)，且充分考慮部分參賽城市因不確定因素某時段不適合做主場的情況，體現(xiàn)賽事的公平性和更好的人性化安排。

優(yōu)化后的模型易于理解且具有很強(qiáng)的自適應(yīng)性和推廣價值，可應(yīng)用在足球、籃球和羽毛球等各類體育賽事中。

5 結(jié) 語

優(yōu)化思想可為賽程編排問題提供解決方法與手段，合理優(yōu)化路徑使大量無序態(tài)的賽程安排趨于有序化，通過尋求最優(yōu)賽程方案使比賽更趨合理公平，并可節(jié)約資源、保護(hù)環(huán)境。與2015年中超實(shí)際賽程相比，應(yīng)用該模型后比賽里程減少69 032 km，節(jié)省開支91 467.4元，燃油量減少了14.50 t，減少二氧化硫排放43.9 kg。本研究可為主客場賽程安排分析求解提供參考，并對進(jìn)一步有效保護(hù)環(huán)境、提升空氣質(zhì)量提供思路。

[1] 劉浩, 韓晶. MATLAB R2014a 完全自學(xué)一本通[M]. 北京:電子工業(yè)出版社, 2015.

[2] 余勝威. MATLAB優(yōu)化算法案例分析與應(yīng)用[M]. 北京:清華大學(xué)出版社, 2014.

[3] 吳意樂, 何慶. 基于改進(jìn)遺傳模擬退火算法的WSN路徑優(yōu)化算法[J]. 計算機(jī)應(yīng)用研究, 2016, 33(10): 53-58.

WU Yile, HE Qing. WSN path optimization algorithm based on improved genetic simulated annealing algorithm[J]. Application Research of Computers, 2016, 33(10): 53-58.

[4] MISEVICIUS A. A modified simulated annealing algorithm for the quadratic assignment problem[J]. Informatica, 2003, 14(4):497-514.

[5] 史峰, 王輝, 郁磊, 等. MATLAB智能算法30個案例分析[M]. 北京:北京航空航天大學(xué)出版社, 2011.

[6] 趙文紅, 張紅斌. 一種改進(jìn)的粒子群優(yōu)化算法[J]. 河北科技大學(xué)學(xué)報, 2006, 27(4): 317-320.

ZHAO Wenhong, ZHANG Hongbin. An improved basic particle swarm optimization algorithm[J]. Journal of Hebei University of Science and Technology,2006, 27(4)：317-320.

[7] 郭亞軍. 綜合評價理論與方法[M]. 北京: 科學(xué)出版社, 2002.

[8] MANTAWY A H, ABDEL-MAGID Y L, SELIM S Z. A simulated annealing algorithm for unit commitment[J]. IEEE Transactions on Power Systems, 1998,13(1):197-204.

[9] 梁廣輝. 中超聯(lián)賽可持續(xù)發(fā)展的SWOT分析[D]. 北京: 北京體育大學(xué), 2011.

LIANG Guanghui. SWOT Analysis of Chinese Super League of Sustainable Development[D]. Beijing: Beijing Sport University, 2011.

[10]孫士平, 吳建軍. 直接搜索模擬退火算法的自適應(yīng)改進(jìn)[J]. 計算機(jī)工程與應(yīng)用, 2015, 51(23):31-37.

SUN Shiping, WU Jianjun. Adaptive improvement of direct search simulated annealing algorithm[J]. Computer Engineering and Applications, 2015,51(23):31-37.

[11]陳華根, 李麗華, 許惠平,等. 改進(jìn)的非?？焖倌M退火算法[J]. 同濟(jì)大學(xué)學(xué)報(自然科學(xué)版)，2006,34(8):1121-1125.

CHEN Huagen, LI Lihua, XU Huiping, et al. Modified very fast simulated annealing algorithm[J]. Journal of Tongji University(natural science)，2006, 34(8):1121-1125.

[12]HERSHBERGER J, SURI S, BHOSLE A M. On the difficulty of some shortest path problems[J].ACM Transactions on Algorithms, 2007, 2607(1):343-354.

[13]CLERC M, KENNEDY J. The particle swarm-explosion, stability and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73.

[14]胡運(yùn)權(quán). 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M]. 北京：高等教育出版社, 2008.

[15]吳受章. 最優(yōu)控制理論與應(yīng)用[M]. 北京：機(jī)械工業(yè)出版社, 2008.

[16]胡大偉, 朱志強(qiáng), 胡勇. 車輛路徑問題的模擬退火算法[J]. 中國公路學(xué)報，2006, 19(4): 123-126.

HU Dawei, ZHU Zhiqiang, HU Yong. Simulated annealing algorithm of vehicle routing problem[J]. China Journal of Highway and Transport,2006, 19(4):123-126.

[17]MEISSNER M, SCHMUKER M, SCHNEIDER G. Optimized particle swarm optimization (OPSO) and its application to artificial neural network training[J]. BMC Bioinformatics, 2006(7): 125-135.

[18]陸平靜, 李寶, 易任嬌, 等. 一種基于改進(jìn)模擬退火算法的程序性能優(yōu)化參數(shù)搜索算法[J]. 計算機(jī)工程與科學(xué), 2015, 37(7): 1227-1232.

LU Pingjing, LI Bao, YI Renjiao,et al. An improved simulated annealing algorithm for program optimization parameters search[J]. Computer Engineering and Science, 2015, 37(7):1227-1232.

[19]陳華根，吳健生，王家林,等．模擬退火算法機(jī)理研究[J].同濟(jì)大學(xué)學(xué)報( 自然科學(xué)版)，2004，32(6):802-805．

CHEN Huagen, WU Jiansheng, WANG Jialin, et al. Mechanism study of simulated annealing algorithm[J]. Journal of Tongji University(Natural Science)， 2004, 32(6):802-805.

[20]張銀蒲. 遺傳算法在組播路由優(yōu)化中的應(yīng)用[J]. 河北科技大學(xué)學(xué)報, 2011,32(3):261-264.

ZHANG Yinpu. Application of genetic algorithm to optimization of multicast routing[J]. Journal of Hebei University of Science and Technology, 2011,32(3):261-264.

Study of Chinese Super League schedule optimization based on simulated annealing algorithm

LIU Baoyou, WANG Tao, MA Yanlong

(School of Environmental Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China)

To optimizethe scheduleof Chinese Super League by establishing the mathematical model can not onlypromotefairness, obtain the humanization designation, but also achieve the aim of savingmileages, resources and protecting environment effectively.Assuming the distance between any two cities was the Baidu map of direct distance, promoting fairness and humanization as well as pursuing the shortest mileage. Wholetraveling distance of 2015 Chinese Super League schedule was optimized based on the improved simulated annealing algorithm and the model was established by Matlab. The results indicated that the whole traveling distance of optimized tournament is 5.022×105km, which reduced 12.08% compared with that of actual schedule of 2015 Chinese Super League. Furthermore, 14.5 tons of fuel can be saved, 43.9 kg of sulfur dioxide emissions can be reduced, SO2contribution can be reduced to 11.11% and 91 467.4 yuan can be saved in the optimized designation.

environmental planning and management; Chinese Super League schedule; simulated annealing algorithm; optimization; cooling schedule

1008-1542(2016)05-0497-06

10.7535/hbkd.2016yx05011

2016-03-10；

2016-04-08；責(zé)任編輯：王海云

劉寶友(1973—)，男，河北盧龍人，教授，博士，主要從事綠色化學(xué)、環(huán)境規(guī)劃與管理方面的研究。

E-mail:lby7150@sina.com

X32;O224;TP301.6

A

劉寶友，王 濤，馬延龍.基于模擬退火算法的中超賽程編排優(yōu)化研究[J].河北科技大學(xué)學(xué)報,2016,37(5):497-502.

LIU Baoyou, WANG Tao, MA Yanlong.Study of Chinese Super League schedule optimization based on simulated annealing algorithm[J].Journal of Hebei University of Science and Technology,2016,37(5):497-502.