APP下载

基于模拟退火算法的中超赛程编排优化研究

2016-11-16刘宝友马延龙

河北科技大学学报 2016年5期
关键词:客场对阵赛程

刘宝友,王 涛,马延龙

(河北科技大学环境科学与工程学院,河北石家庄 050018)



基于模拟退火算法的中超赛程编排优化研究

刘宝友,王 涛,马延龙

(河北科技大学环境科学与工程学院,河北石家庄 050018)

为了促进赛事的公平性、实现人性化的赛程编排设计,同时达到减少出行里程、节约资源、保护环境的目的,采用计算机辅助建模的方法,对中超赛程编排进行优化研究。假设以总体出行里程最短、兼具赛程的公平性和设计的人性化为优化目标,以百度地图提供的球队所在城市间的距离数据为依据,通过改进模拟退火算法对2015年中超赛程编排进行优化,运用Matlab求解得到最优方案。结果表明:在最优赛程安排下得到的各支球队最优出行里程为5.022×105km,相对2015年中超的实际赛程编排总里程减少了12.08%,由此节省燃油14.50 t,减少排放二氧化硫43.9 kg,对大气中二氧化硫减排的贡献率为11.11%,节约资金91 467.4元。该结果可以为中超实际主客场赛程编排的优化提供参考。

环境规划与管理;中超赛程;模拟退火算法;最优化;冷却进度表

模拟退火算法(simulated annealing algorithm)是一类从局部拓展到全局的随机性组合系统优化方法[1],它利用杂交粒子群优化算法中的杂交运算与带高斯变异粒子群优化算法中的变异运算处理大规模复杂数据的优化问题[2]。与其他方法相比,该算法具有描述简单、约束较少、使用灵活、运行效率高等优点,适于求解非确定多项式问题(NP)、旅行商问题(TSP)等优化组合问题。改进退火算法的优化性能主要涉及全过程状态函数与温度更新函数,这些环节的设计将决定模拟退火算法的快速性、收敛性与鲁棒性等[3-4]。

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

1 中超赛程现状及分析

2015年中超联赛采用主客场双循环赛制[9],参赛队伍是2014年排名前16的球队(升级队代替降级队)。球队在一个城市进行完一场比赛后乘坐交通工具进入另一个城市参加比赛,所有球队进行完上半程比赛后回到各自城市休整,下半程与上半程对阵球队相同但主客场位置调换,所有比赛结束后,各球队回到各自所在的城市。

在中超赛程中,考虑到旅途劳累与主场优势等因素,任一球队不宜连续3次以上(>3)做主场或客场,此时通过建立退火模型进行系统优化,不仅可使赛程编排更为合理,更能确保球队队员实力的正常发挥,实现相对公平。各支球队的地理位置与所在城市之间的距离分别如图1和表1所示。

表1 2015年不同中超球队之间的距离

2 中超赛程优化模型的构建

2.1 模型假设

在赛制编排中,将中超赛程所有方案表示为一个有向的赋权图C=(V,E)[10],其中V∈(V1,V2,…,V16),是16支球队集合中的一支;E∈(E1,E2,…,E16),是不同于V的另一支球队。最优赛程Z与有向对阵赛程C的关系为

(1)

约束条件如下:

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

2)交通工具统一为宇通标准55座大巴车,中途不更换其他交通工具;

3)Sa,b=0,a和b为同在一个城市的不同球队;

4)所有球队打完上半程后回各自城市进行休整;

5)退火算法参数取舍得当,不会陷入局部最优;

6)两城市之间的路程精确到整数位。

2.2 模型分析

首先将2014年球队排名作为2015年各队的队号(用a1,a2,…,a16表示,升级队代替降级队),按照抽签法的原则进行单循环随机排列,对应到b1,b2,…,b16的位置。对16支球队的位置进行蛇形编排,即对阵双方位置为bi↔b17-i,固定1号位置不动,2号位置到16号位置(包括位置上的球队),顺序轮转,循环一轮后对阵双方为b1↔b2, b3↔b16, b4↔b15, b5↔b14, b6↔b13, b7↔b12, b8↔b11, b9↔b10。共可进行15轮循环,此时位置对阵总数U=15轮×8场/轮=120场。

将15轮比赛进行全排列共有15!≈1.3×1012种可能情况,编排情况相对较多,应用模拟退火算法,根据Metropolis接受准则[11-12],持续进行“产生新解—判断与目标函数的差距—决定接受或舍弃”的迭代过程,算法法则如下:

(2)

利用概率算子min{1,exp(-Δf/Tk)}>random[0,1]选择性接受可行解,以概率exp(-Δf/Tk)选择性接受劣质解[13-15]。通过迭代算子Tk+1=CTk,k←k+1,其中C∈(0,1)进行迭代运算,则速度与位置更新公式如下:

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)

在运行算法过程中,性能相对较好的编排结果应该被赋予更高的选中率,若用f代表目标函数,可用式(6)为概率Pi选择合适的取值。

(6)

为了提升赛程的相对公平性,任一球队不宜连续3次以上(>3)做主场或客场,则模型设计基本原则如下:

1)任一球队如果本轮打主场则下一轮优先考虑打客场;

2)任一球队如果本轮打客场则下一轮优先考虑打主场。

设定第1轮比赛对阵双方主客场随机选取,从第2轮到第15轮主客场受限程度依次递增,首先穷举第1轮所有可能主客场情况并利用dgr_flag与wish_host分别提供危险标志和希望标志(初始值为零),数据结构如下:

dgr_flg=zeros(1,TEAM_NUM);%每个球队提供一个危险标志

wish_host=zeros(1,TEAM_NUM);%每个球队希望打主场标志。

2.3 算法寻优步骤

16支球队分为8组对阵,每组对阵有2种主客场情况,则共28=256种主客场情况,选取其中1种进行完整的15轮循环,此时寻优步骤如下:

1)在256种主客场编排中随机选取1种情况进行蛇形编排与顺序轮转,得到完整的15轮循环过程;

2)利用模拟退火算法进行种群寻优并判断每组对阵的2支球队是否已经连续做了3次主场(或客场)[18-19],如果对阵的2支球队都已经做了3次主场(或客场)且下一场希望相同,则结束进程返回步骤1)重新随机选取;

图2 算法的总体流程图Fig.2 Flow diagram of algorithm

3)如果对阵的2支球队都已经连续3次做了主场(或客场),但2支球队对待下一场比赛希望做主场还是客场的情况相反,此时可以完成循环并输出最优解;

4)如果对阵的2支球队下一场都想做主场(或者客场),但只有其中1支队伍已经连续3次做了主场(或客场),则此队拥有优先选择权,完成循环并输出最优解;

5)如果对阵的2支球队下一场都想做主场(或客场),但是2支球队都没有连续3次做主场(或客场),则可根据队号大小决定,队号大的优先选择,完成循环并输出最优解。

图3 利用模拟退火算法的全局寻优结果Fig.3 Global optimization results by stimulated annealing algorithm

该算法的总体流程见图2。在中超联赛中,下半程赛程完全翻转上半程赛程,即对阵双方、主客场安排与轮次顺序完全确定。本文从中超联赛实际情况出发,在上半程对阵双方与主客场安排确定的情况下利用退火算法对下半程进行寻优,将优化后的上、下半程的赛程之和作为中超比赛整体的赛程,则此赛程即为最优的全局编排方案[20]。

3 结果分析与讨论

3.1 结果分析

按照模拟退火算法初始值设置的一般原则,经过多次尝试,选取初始退火温度T0=500 000,在终止条件Tk+1=CTk中令C=0.95,通过运行Matlab程序,可得到全局寻优的模拟退火图,如图3所示。

运行时长2 990.91s,随机选取种类超过25万种,最终得到表2所示的运行结果。从表2可以得到每支球队出行的具体路线,同时计算出16支球队最短的出行里程为5.022×105km。

由于气候等不可抗因素对赛程编排具有一定的影响,某些球队所在城市在特定时段内不适宜做主场。以某支球队在前3场不适宜做主场为例,在利用算法寻找最优结果之前,人为赋予该球队主场危险标志,即默认此球队在前3轮比赛之前已经做主场参加了3场比赛,此时在进行前3轮比赛中该球队始终拥有优先选择主客场的权利,此时在算法寻优过程中该球队始终处于客场状态,可得到在赛程前3场中此队做客场的最优情况。通过合理使用危险标志与期望标志,可使优化的中超联赛赛程更趋人性化设计,可有效避免一些不可抗因素对球赛的干扰,有利于球员各自水平的正常发挥。

表2 全局优化后的中超赛程安排

注:表中各个球队均以队名中的后2个字作为简称,例如“上海申鑫”简写为“申鑫”。

3.2 结果讨论

根据中国汽车燃料消耗量网(the website of automobile fuel consumption of China)的信息可知,标准宇通55座大巴车的百公里耗油量为25 L,0号柴油5.3元/L,GB 252—2015规定0号柴油含硫量不高于0.2%(质量分数,下同),此处按0.15%计算。相对2015年中超实际编排方案,优化后编排里程减少69 032 km,燃油量减少了14.50 t,节约资金91 467.4元,同时减少二氧化硫排放43.9 kg。实际应用中,由于出行里程缩短而使道路通畅率上升,百公里耗油量随之降低,最终节能效果更加明显。

根据2015-09-07人民网环保部报道,2015年上半年中国二氧化硫总体排放量为989.1万t,机动车排放量约占总排放量的6%,即59.346×104t。由以上数据计算可知,优化后赛程编排对二氧化硫排放贡献率由4.5×10-8减少为4.0×10-8,贡献率减少了11.11%。因此,对赛程进行优化编排对改善空气质量具有一定的作用。

4 模型评价

优化后的模型通过合理嵌套模拟退火算法全局寻优,可以快速寻找到中超比赛最优的主客场赛程方案和各队的行程路线,程序简单且可操作性强;在中超赛程下半程对阵双方和主客场确定的情况下利用模拟退火算法优化轮次,相比于中超目前下半程轮次与上半程相同的情况而言,具有更高的实用价值。

优化后的模型通过抽签法随机编排位置号,智能编排减少人工干预,且充分考虑部分参赛城市因不确定因素某时段不适合做主场的情况,体现赛事的公平性和更好的人性化安排。

优化后的模型易于理解且具有很强的自适应性和推广价值,可应用在足球、篮球和羽毛球等各类体育赛事中。

5 结 语

优化思想可为赛程编排问题提供解决方法与手段,合理优化路径使大量无序态的赛程安排趋于有序化,通过寻求最优赛程方案使比赛更趋合理公平,并可节约资源、保护环境。与2015年中超实际赛程相比,应用该模型后比赛里程减少69 032 km,节省开支91 467.4元,燃油量减少了14.50 t,减少二氧化硫排放43.9 kg。本研究可为主客场赛程安排分析求解提供参考,并对进一步有效保护环境、提升空气质量提供思路。

[1] 刘浩, 韩晶. MATLAB R2014a 完全自学一本通[M]. 北京:电子工业出版社, 2015.

[2] 余胜威. MATLAB优化算法案例分析与应用[M]. 北京:清华大学出版社, 2014.

[3] 吴意乐, 何庆. 基于改进遗传模拟退火算法的WSN路径优化算法[J]. 计算机应用研究, 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]. 北京:北京航空航天大学出版社, 2011.

[6] 赵文红, 张红斌. 一种改进的粒子群优化算法[J]. 河北科技大学学报, 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]. 北京: 科学出版社, 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] 梁广辉. 中超联赛可持续发展的SWOT分析[D]. 北京: 北京体育大学, 2011.

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

[10]孙士平, 吴建军. 直接搜索模拟退火算法的自适应改进[J]. 计算机工程与应用, 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]. 同济大学学报(自然科学版),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]胡运权. 运筹学基础及应用[M]. 北京:高等教育出版社, 2008.

[15]吴受章. 最优控制理论与应用[M]. 北京:机械工业出版社, 2008.

[16]胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报,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]. 计算机工程与科学, 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].同济大学学报( 自然科学版),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]张银蒲. 遗传算法在组播路由优化中的应用[J]. 河北科技大学学报, 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;责任编辑:王海云

刘宝友(1973—),男,河北卢龙人,教授,博士,主要从事绿色化学、环境规划与管理方面的研究。

E-mail:lby7150@sina.com

X32;O224;TP301.6

A

刘宝友,王 涛,马延龙.基于模拟退火算法的中超赛程编排优化研究[J].河北科技大学学报,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.

猜你喜欢

客场对阵赛程
中国经济:从客场到主场的全球化发展新格局
赛程回顾
飞跃绿墙 詹姆斯对阵凯尔特人10大精彩表演
2017—18赛季英格兰足球超级联赛赛程
2015-16赛季NBA季后赛东部对阵
2015-16赛季NBA季后赛西部对阵
认识足球(九)
2016欧洲杯小组赛赛程
冲巨浪
FINA2011上海第14届世界游泳锦标赛赛程