體育聯(lián)賽中基于GSO算法的賽程優(yōu)化方法*

曾芳桂，　趙　曼

(1.武漢大學(xué) 體育部，湖北 武漢 430070；2.中國地質(zhì)大學(xué)(武漢) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074)

目前有多種類型的圖形化體育聯(lián)賽賽程機(jī)制，如單輪巡回賽、雙輪巡回賽等[1].這些比賽的不同之處是賽程、比賽數(shù)量和比賽形式.例如，世界杯決賽有兩個(gè)階段:小組賽階段和淘汰賽階段.在小組賽階段，有8個(gè)小組，每個(gè)小組有4個(gè)隊(duì).每個(gè)隊(duì)都有一場(chǎng)循環(huán)賽，即每個(gè)隊(duì)都要和小組內(nèi)的其他隊(duì)進(jìn)行一場(chǎng)比賽.然后，每組中只有前2支球隊(duì)會(huì)進(jìn)入淘汰賽階段.淘汰賽是一場(chǎng)單淘汰賽，各隊(duì)進(jìn)行一場(chǎng)一次性比賽.在足球、籃球、棒球等聯(lián)賽中，每個(gè)隊(duì)在兩場(chǎng)比賽中互相對(duì)抗，一場(chǎng)是主場(chǎng)，另一場(chǎng)是客場(chǎng)[2].對(duì)于主客場(chǎng)賽制的聯(lián)賽，賽程的安排直接影響各隊(duì)的行程安排.因此，如果賽事組織者能夠在日程安排上幫助減少一些交通等費(fèi)用，這將是有益的[3].在體育聯(lián)賽中，有很多變量影響各個(gè)隊(duì)伍的成本，比如轉(zhuǎn)場(chǎng)方式、轉(zhuǎn)場(chǎng)距離、轉(zhuǎn)場(chǎng)次數(shù)、轉(zhuǎn)場(chǎng)順序等.因此，影響轉(zhuǎn)場(chǎng)成本的比賽調(diào)度問題已經(jīng)成為多年來重要的優(yōu)化問題.目前，一些學(xué)者提出了一些賽程調(diào)度方案.例如，[4]以最小化所有隊(duì)伍的行程距離為目標(biāo)，提出了一種基于蒙特卡洛的賽程優(yōu)化方法.[5]提出一種基于集成約束規(guī)劃的賽程優(yōu)化方法，用來最小化每個(gè)隊(duì)伍的轉(zhuǎn)場(chǎng)次數(shù).

本文以最小化所有隊(duì)伍的總轉(zhuǎn)場(chǎng)次數(shù)為目標(biāo)，提出一種基于群搜索優(yōu)化(group search optimization, GSO)算法的賽程優(yōu)化方案.將賽程安排通過由轉(zhuǎn)場(chǎng)序列矩陣構(gòu)建的賽程序列矩陣來表示，然后通過GSO算法獲得最優(yōu)的轉(zhuǎn)場(chǎng)矩陣，最終形成最優(yōu)賽程調(diào)度方案.在不同隊(duì)伍規(guī)模的比賽場(chǎng)景中進(jìn)行實(shí)驗(yàn)，結(jié)果表明本文方案能夠有效降低轉(zhuǎn)場(chǎng)次數(shù)，具有可行性.

1　聯(lián)賽賽程描述

1.1　賽程約束與優(yōu)化目標(biāo)

每支隊(duì)伍的轉(zhuǎn)場(chǎng)次數(shù)為從其主場(chǎng)出發(fā)到比賽結(jié)束返回時(shí)的轉(zhuǎn)移城市總次數(shù).在主場(chǎng)的比賽叫做主場(chǎng)比賽，在對(duì)手城市的比賽叫客場(chǎng)比賽.優(yōu)化目標(biāo)是最小化所有隊(duì)伍的總轉(zhuǎn)場(chǎng)次數(shù)，并滿足以下限制:(1) 這里的比賽日程是一個(gè)旅行錦標(biāo)賽問題(TTP)[6];(2) 每個(gè)隊(duì)在一周內(nèi)最多只能打一場(chǎng)比賽，而且每周都必須有同樣數(shù)量的主場(chǎng)比賽和客場(chǎng)比賽;(3) 如果在一周后沒有主場(chǎng)比賽，球隊(duì)不會(huì)回到主場(chǎng);(4) 每隊(duì)的比賽順序中最多允許連續(xù)三場(chǎng)主場(chǎng)比賽或連續(xù)三場(chǎng)客場(chǎng)比賽.

1.2　賽程調(diào)度表示

在這項(xiàng)工作中，賽程安排問題分為兩部分:隊(duì)伍轉(zhuǎn)場(chǎng)和隊(duì)伍賽程.n隊(duì)比賽的隊(duì)伍轉(zhuǎn)場(chǎng)和賽程分別由矩陣A和B表示，其中n是偶數(shù).隊(duì)伍轉(zhuǎn)場(chǎng)A由n個(gè)隊(duì)伍的n個(gè)轉(zhuǎn)場(chǎng)序列組成，其中轉(zhuǎn)場(chǎng)序列由0和1組成，0代表主場(chǎng)，1代表客場(chǎng).A(i,j)中的元素代表了隊(duì)伍i在wj周上的比賽類型.例如，一個(gè)可能的轉(zhuǎn)場(chǎng)序列如表1所示.從問題描述來看，每一個(gè)轉(zhuǎn)場(chǎng)序列最多可以有3個(gè)連續(xù)的0或3個(gè)連續(xù)的1.在獲得所有的轉(zhuǎn)場(chǎng)序列后，可以形成隊(duì)伍轉(zhuǎn)場(chǎng)矩陣.表2顯示了4個(gè)隊(duì)伍比賽中的一個(gè)轉(zhuǎn)場(chǎng)矩陣?yán)?很明顯，任何隊(duì)伍都有不同的轉(zhuǎn)場(chǎng)序列.接下來，隊(duì)伍賽程矩陣也由n個(gè)賽程序列組成.隊(duì)伍i的賽程序列是一個(gè)從1到n的序列，除了編號(hào)i.B(i,j)表示在wj周對(duì)陣隊(duì)伍i的隊(duì)伍編號(hào).例如，表3所示為4個(gè)隊(duì)伍比賽的一個(gè)可能的賽程序列.在獲得所有賽程序列后，可以生成隊(duì)伍賽程矩陣.表4顯示了一個(gè)4個(gè)隊(duì)伍比賽的隊(duì)伍賽程矩陣?yán)?表4中每個(gè)賽程矩陣的元素B(i,j)依賴于表2中的隊(duì)伍轉(zhuǎn)場(chǎng)矩陣.例如，B(1,3)可以等于4，因?yàn)锳(1,3)不等于A(4,3).一般來說，B(i,j)可以等于k，當(dāng)且僅當(dāng)A(i,j)不等于A(k,j)時(shí).因?yàn)樵诿恳粓?chǎng)比賽中,一個(gè)隊(duì)伍為主場(chǎng)比賽，而另一個(gè)隊(duì)伍則為客場(chǎng)比賽.

表1　隊(duì)伍1可能的轉(zhuǎn)場(chǎng)序列

表2一個(gè)4隊(duì)參加比賽的隊(duì)伍轉(zhuǎn)場(chǎng)矩陣A例子

Tab.2TransitionmatrixAofamatchwithfourteamsparticipating

隊(duì)伍編號(hào)w1w2w3w4w5w61000111210001130111004111000

表3隊(duì)伍1可能的賽程序列

Tab.3Schedulesequenceofteam1

隊(duì)伍編號(hào)w1w2w3w4w5w61234234

表4　 一個(gè)4隊(duì)參加比賽的隊(duì)伍賽程矩陣B例子

2　基于GSO生成最優(yōu)調(diào)度方案

2.1　個(gè)體編碼

利用GSO算法和序列交換方法解決體育轉(zhuǎn)場(chǎng)聯(lián)賽賽程調(diào)度問題.在初始化GSO算法中的個(gè)體時(shí)，首先隨機(jī)生成前n/2行序列，然后用序列交換方法生成其他n/2行序列，以此構(gòu)建一個(gè)GSO個(gè)體的方案編碼.序列交換用于生成另一半的轉(zhuǎn)場(chǎng)序列，即將所有隊(duì)伍的主/客場(chǎng)進(jìn)行互換.如表5所示，顯示了一次交換之前和之后的轉(zhuǎn)場(chǎng)序列.

表5　一次交換之前和之后的轉(zhuǎn)場(chǎng)序列

表6　在6個(gè)隊(duì)伍比賽中隨機(jī)生成的轉(zhuǎn)場(chǎng)序列

例如，在6個(gè)隊(duì)伍比賽案例中，生成一個(gè)初始個(gè)體的例子如下所示.首先，在賽制約束下通過隨機(jī)選擇生成前3個(gè)轉(zhuǎn)場(chǎng)序列，如表6中上3行所示.在此之后，分別用1、2、3組的轉(zhuǎn)場(chǎng)序列，通過交換方法生成剩余隊(duì)伍4、5、6的轉(zhuǎn)場(chǎng)序列，如表6中下3行所示.

2.2　GSO算法

對(duì)于求解NP困難問題，啟發(fā)式智能算法最為有效[7].其中，GSO算法包含3個(gè)操作，即發(fā)現(xiàn)者操作、搜索者操作和游蕩者操作[8].在迭代過程中，將具有最佳適應(yīng)度值的成員選為發(fā)現(xiàn)者.將適應(yīng)度值高于閾值的多個(gè)成員選為搜索者.將適應(yīng)度值低于閾值的多個(gè)成員選為游蕩者.

式中，yzero表示零度掃描，yright表示右邊掃描，yleft表示左邊掃描，r1∈R1為均值為0、方差為1的正態(tài)分布隨機(jī)數(shù)，r2∈Rs-1為(0,1)內(nèi)的一個(gè)隨機(jī)序列.然后，計(jì)算發(fā)現(xiàn)者搜索到的3個(gè)新位置的適應(yīng)度，并移動(dòng)到具有最優(yōu)適應(yīng)度的位置.如果新位置都不如當(dāng)前位置，則將其頭轉(zhuǎn)向一個(gè)新角度λz+1=λz+r2γmax，其中γmax表示最大轉(zhuǎn)向角.如果在ɑ次迭代結(jié)束后，發(fā)現(xiàn)者沒有找到一個(gè)更好的位置，則停止搜索過程且保持不動(dòng)，即λz+ɑ=λz.

2.3　優(yōu)化轉(zhuǎn)場(chǎng)序列及生成調(diào)度方案

在利用GSO算法優(yōu)化轉(zhuǎn)場(chǎng)序列時(shí)，對(duì)傳統(tǒng)GSO進(jìn)行改進(jìn)，即通過一個(gè)變異操作對(duì)發(fā)現(xiàn)者進(jìn)行變異來生成游蕩者，而不是通過適應(yīng)度閾值判斷來生成，這樣有利于跳出局部最優(yōu)解，提高算法的全局搜索能力[10].

變異過程通過改變轉(zhuǎn)場(chǎng)矩陣A中某一行和列的元素來實(shí)現(xiàn).首先，通過GSO算法獲得當(dāng)前發(fā)現(xiàn)者，即以n×(2n-1)形式的轉(zhuǎn)場(chǎng)序列矩陣來表示；然后，隨機(jī)選擇矩陣中wj列(周)和n行(隊(duì)伍)對(duì)應(yīng)的元素，將其從1變到0或從0變到1.之后，根據(jù)比賽屬性的映射關(guān)系，將相關(guān)的wj和n以同樣的條件改變.

在通過改進(jìn)GSO得到最優(yōu)的轉(zhuǎn)場(chǎng)序列矩陣后，根據(jù)轉(zhuǎn)場(chǎng)序列，通過一個(gè)賽程方案生成算法來構(gòu)建所有隊(duì)伍的賽程時(shí)間表.算法1給出了賽程方案生成算法的偽代碼.

算法1:賽程方案生成算法輸入:所有隊(duì)伍的轉(zhuǎn)場(chǎng)序列(A[1:n,1:n-1])輸出:賽程矩陣1 for(i=1:n)2 if(i>1) then添加隊(duì)伍i之前的隊(duì)伍的賽程;3 endif;4 for(m=1:n-1)5 if(B[i,m]滿足約束條件) then添加賽程序列B[i,m];6 endif;7 whilemin(B[i,:]=0)8 nteam←missingteanm(B[i,m]);9 if(nteam==i+1) then構(gòu)建隊(duì)伍i-1的賽程序列;10 else構(gòu)建隊(duì)伍i的賽程序列;11 endif;12 endwhile;13 endfor;14endfor;15輸出賽程矩陣B[1:n,n:2n-2]←B[1:n,1:n-1];

表7　不同隊(duì)伍數(shù)量下賽程方案的總轉(zhuǎn)場(chǎng)次數(shù)

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

將本文方法與[4]提出的蒙特卡洛賽程安排方法和[5]提出的集成約束規(guī)劃方法進(jìn)行比較.實(shí)驗(yàn)中，設(shè)置隊(duì)伍數(shù)量n從4到20不等，執(zhí)行各種方法獲得最優(yōu)的賽程方案，并計(jì)算各種方案中所有隊(duì)伍的總轉(zhuǎn)場(chǎng)次數(shù).比較結(jié)果如表7所示.

從表7可以看出，本文方法獲得的賽程方案中總轉(zhuǎn)場(chǎng)次數(shù)最小，且隨著比賽隊(duì)伍數(shù)量的增加，其優(yōu)勢(shì)更加明顯，這證明了本文方法的有效性.這是因?yàn)楸疚牟捎昧薌SO算法來進(jìn)行尋優(yōu)，并通過變異機(jī)制來獲得游蕩者，增強(qiáng)了尋優(yōu)能力.此外，本文中的交換過程可以減少運(yùn)行時(shí)間，算法只需要隨機(jī)選擇個(gè)體的前n/2行轉(zhuǎn)場(chǎng)序列，然后使用交換過程生成剩余序列，得到的整體轉(zhuǎn)場(chǎng)序列也滿足比賽約束條件.如果沒有交換過程，算法必須隨機(jī)選擇所有轉(zhuǎn)場(chǎng)序列，得到的解可能不能滿足約束條件，影響后續(xù)的尋優(yōu)過程.

4　結(jié)　論

為了提高各種體育聯(lián)賽的賽程經(jīng)濟(jì)性，將賽程安排方案編碼為一個(gè)賽程矩陣.在滿足賽制約束條件下，通過結(jié)合序列交換和GSO算法來生成聯(lián)賽賽程安排方案，最小化了所有參賽隊(duì)的轉(zhuǎn)場(chǎng)次數(shù)，以此來降低比賽成本.在與其他現(xiàn)有方法的比較中，本文方法表現(xiàn)出了優(yōu)越的性能.在今后的研究中，將考慮轉(zhuǎn)場(chǎng)距離等因素，使其更加貼合實(shí)際情況.

[1]周軼楓, 楊濱峰. 利用卷積神經(jīng)網(wǎng)絡(luò)的體育視頻運(yùn)動(dòng)員檢測(cè)[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2017, 39(1): 95-98.

[2]張玉國, 姜立嘉. 我國高校競(jìng)技體育賽事資源優(yōu)化配置研究——以高校籃球聯(lián)賽為例[J]. 北京體育大學(xué)學(xué)報(bào), 2013, 36(11): 102-107.

[3]HUNG J C, YEN N Y, JEONG H Y, et al. Adaptive mechanism for schedule arrangement and optimization in socially-empowered professional sports games[J]. Multimedia Tools & Applications, 2015, 74(14):5085-5108.

[4]都揚(yáng)揚(yáng), 木仁. 具有主客場(chǎng)賽制的各大聯(lián)賽賽程優(yōu)化安排與設(shè)計(jì)[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]韋煒, 藤村茂, 席裕庚. 求解旅行錦標(biāo)賽問題的改進(jìn)混合局部搜索算法[J]. 計(jì)算機(jī)仿真, 2012, 29(10):252-255.

[7]何常勝, 趙小河, 陳安. 基于遺傳算法和后代校正的WSN覆蓋和連通性優(yōu)化方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2016, 38(2): 89-93.

[8]熊聰聰, 郝璐萌, 王丹,等. 一種基于差分策略的群搜索優(yōu)化算法[J]. 計(jì)算機(jī)科學(xué), 2017, 44(2):250-256.

[9]AKHAND M A H, JUNAED A B M, HOSSAIN M F, et al. Group search optimization to solve traveling salesman problem[C]// International Conference on Computer and Information Technology. IEEE, 2013:72-77.

[10]CHEN D, WANG J, ZOU F, et al. An improved group search optimizer with operation of quantum-behaved swarm and its application [J]. Applied Soft Computing Journal, 2012, 12(2): 712-725.