排球比赛中,一张网将两队各六名队员分开。为了获得一分,每个队必须让球落在另一队的场地上。一方的球员试图让球越过球网落到另一队的场地上,另一队球员极力救球并尽力让球过网落到对方场地,场上形成了拉锯战。拉锯战持续进行,直到某队出现失误使得对方得1分。比赛即将开始时,主教练把出场队员名单交给第二裁判员。运动员入场后,3名球员站在前排,另外3人站在后排。每个队都可以根据自己队员的情况,组成自己的场上阵容。比赛期间,教练站在球场附临场指挥和指导运动员。板凳球员坐在场下,随时准备好参加比赛(图1)。
在一场普通排球比赛中,影响比赛结果的因素很多。每场比赛结果未知,球队输赢都有可能,弱队胜强队也不足为奇。通常用球队实力来刻画强队更有可能击败对手的事实。球队关注即将到来的比赛,不考虑后续即将到来的比赛。鉴于之前的赛果、当前球队实力和赢下比赛的几率,每支球队在场上的首发阵容会进行相应调整。当球队i击败球队j时,球队i赢得比赛的优势就是球队j的劣势,球队有了某种劣势,也说明球队缺少某种优势。
联赛等于种群,赛季轮次表示当前迭代次数,球队是种群的解,星期表示每轮联赛赛程。
排球比赛的教练可以通过现场指导和平时指导来提高运动员的基本技能。教练通过模拟与真实比赛强度相同的训练,来提升运动员的移动速度、预判能力、把握时机能力、沟通更累和团队合作能力,从而满足团队的战略要求。
一、VPLA算法
(一)解表达方式
球队成员分为场上球员、板凳球员和教练。算法的解由两个部分组成,分别称为主动部分和被动部分。主动部分代表每个团队的六名场上队员,被动部分代表板凳队员,解的适应度函数值由这六名场上队员决定(图2)。
球队的阵容决定了球队在场上的整体风格,一般来说排球比赛里通常有3种阵容———“4-2”“2-4”和“5-1”,队形中“H-S”风格表示攻击手和二传手的个数。教练需要根据场上球员和板凳球员的类型和能力决定最好的阵容,通常来看场上队员和板凳球员的数量相同。在比赛过程中,阵容会不断变化。教练在比赛中会不断安排阵容调整,因此场上队员与板凳队员的角色也不断变化(图3)。
(二)初始解
每支球队都有自己的阵容和替补,对于VPLA算法,NT表示球队数量,xif,j表示第i支球队场上阵容的第j个队员,xis,j表示第i支球队替补席的第j个队员。
其中ubj和lbj为变量上界和下界,Rand()为[0,1]之间随机数。
初始种群可以由F矩阵和S矩阵表示,矩阵的行表示球队个数,矩阵的列表示队员数。
二、比赛赛程
赛程是比赛的重要因素,VPLA算法采用单循环赛制(Single Round Robin,SRR)生成联赛赛程。在每个赛季,每支球队都只与其他球队碰面一次且仅一次。进入下一个赛季,所有球队再重复碰面。球队的数量一般为偶数,如果球队的数量非偶数,则增加一个虚拟球队,与虚拟球队碰面的球队当期轮次轮空。
在应用SRR方法时,画一个N-1条边的规则多边形,每个顶点和中心点表示一支球队,用水平线连接多边形左右两边对应的顶点,还有一条边连接多边形的中心点和最上边的顶点。每条连接边代表一场比赛,端点表示两支对战的球队。通过顺时针旋转多边形,可以确定下一轮次的对阵表,一旦多边形转了一圈,则进入下一个赛季。图4利用了SRR方法,设有N个球队,每支球队每个赛季要打N-1场比赛,赛季总比赛场次为N(N-1)/2。
(一)竞赛
通常情况下,每支球队每周只有一场比赛,比赛成绩只有输赢两种情况。球队成绩要通过五局三胜制决定,前四局中局点为25分,如果两队24比24,则赢得该局比赛需要2分分差,第五局比赛为抢15分。算法通过公式(3-4)确定球队赢球概率(实力)。
φ(i)表示第i支球队的实力,f(xif)表示第i支球队的适应值,Z表示所有球队的适应值总和。如果目前有两支球队j和k进行比赛,则球队j赢得比赛的概率为P(j,k)。
VPLA算法采用均匀分布的随机数r∈[0,1]来确定比赛的获胜者,如果r≤p(j,k)则j队获胜,否则k队获胜。显然,如果两个球队的适应度值相差不大,则p(j,k)和p(k,j)趋近0.5。比赛获胜者确定后,失败的球队采用“知识共享”、“位置重排”和“换人”策略弥补劣势,获胜球队采用“主导”策略。
(二)知识共享策略
排球教练在比赛中对球队表现有显著影响。教练负责训练运动员、在比赛中评估球员的技能和安排场上阵容。教练最主要的任务之一是分析队员和对手在比赛中的表现。基于分析结果,教练获取了新的技战术知识。之后,教练与球员和替补队员共享知识。教练实时分析比赛中的对战过程、比赛间歇和每局比赛的持续时间,并指导场上队员和替补队员。VPLA算法将教练的活动称为知识共享,这能有助于处于劣势的球队在比赛中改善场上表现。
λf和λs是场上阵容和替补阵容系数,r1和r2是[0,1]之间随机数,如果用δks表示知识共享率,则Nks=n×δks表示球队中需要进行知识共享的队员数量。
(三)位置重排策略
在排球比赛中,每个位置决定一名球员的场上职责。球员们都有各自需要完成的任务,他们将尽最大努力相互合作,努力取得最佳战绩。场上队员的角色包括拦网手、外线攻击手、自由人、二传手和对手。教练试图为每个角色安排最合适的球员,以便在联赛中获得最好的战绩。由于财政资源短缺等状况,球队没有足够资金招募到所有想要的球员,所以球队必须利用现有的球员,并试图在联赛中提升球员的表现。球员在教练的领导下接受训练,以便他们有能力完成各种场上角色(打所有不同的位置)。VPLA算法对输球的球队采用位置重排策略,使得球队中的队员位置可以相互交换,以获得更好的表现。图1中给出了位置重排策略的应用,左边球队将球员2和4的位置互换。如果δrs位置重排率,则Nrs=n×δrs表示位置重排次数。
公式(8)表示将场上阵容的第i和第j个位置相交换,公式(9)表示将替补阵容的第i和第j个位置相交换。
(四)换人策略
换人是排球比赛中主教练调整队员位置的主要策略之一,每个回合之后都可以进行换人。教练必须清楚哪些球员能力强以及哪些球员组合在一起能够配合默契,从而最大限度地提高球队获胜概率。比赛期间,场上队员可以与另一名场上队员互换位置或者被板凳球员换下。教练最重要的职责之一是选择一个好的换人策略,通过改变球员的位置来形成不同的阵容(图1左边球队)。在当今的排球比赛中,换人的次数是有限的,但VPLA算法中的换人次数是无限的。如果r表示[0,1]之间的随机数,则Ns=n×r表示换人次数。
在每场比赛之后,对于输球的一方,集合h为所有被选择的、需要进行换人的位置的集合,集合F是场上球员的候选集,集合S是板凳球员的候选集。首先将集合S与集合h的对应位置球员进行替换,之后将集合F与集合h的对应位置球员进行替换。
(五)胜方策略
VPLA算法中,每个获胜球队通过结合最佳球队在之前比赛中的一些赢球经验和自身的临场发挥来竞争联赛排名。根据胜方策略,球队的最新排名与球队当前排名X(t)、最佳球队X(t)*和惯性权重ψ有关。
r1和r2为[0,1]之间均匀分布的随机数。
三、学习阶段
VPLA算法用rank1表示当前迭代中的最好解,以此类推第二个和第三个最好解分别为rank2和rank3。其余的球队都会向这三支球队学习,球队的学习行为如公式(12-15)所示。
θ和v是系数,β是常数,t为当前迭代次数,T为最大迭代次数,g={s,f},Φ={1,2,3},s和f分别表示球队的替补和场上阵容,Φ中的值分别对应rank1、rank2和rank3,根据g和Φ的值可以构造六种不同的集合{{s,1},{s,2},{s,3},{f,1},{f,2},{f,3}}。
VPLA算法学习阶段的数学模型如公式(16)所示,学习阶段的主要作用是帮助算法进行局部搜索。
(一)球员转会
在排球联赛中,转会是一个球员从一个球队转出到另一个球队的过程。根据规定,球员可以在赛季结束后转会。VPLA算法定义了转会算子来帮助算法收敛到最优解。在转会窗口开放期,选择H支转会球队,设置随机变量r取值范围为[0,1]。从每支转会球队的每个队员开始判断,如果r>0.5,随机选择不在H支球队中的某支球队的对应位置的场上队员和替补队员,用随机选择的场上队员和替补队员分别替换转会球队中的对应球员,直到所有的转会球队都完成转会过程为止。如果用δst表示参与转会的球队比率,则H=N×δst。
(二)升级和降级
一个赛季结束后,低级别的顶级球队将被提升到更高级别的联赛,而高级别联赛中最差的几支球队将在下一个赛季进入更低级别的联赛。如果δpr表示升降级球队的比率,则Npr=N×δpr表示升级或降级的球队数量。首先移除Npr支球队,然后重新产生Npr支球队。从第1支需要随机产生的球队的第1个位置的场上队员和替补队员开始,从剩余球队中随机选择某支球队的对应位置的场上队员和替补队员作为随机产生球队中的队员。
(三)算法执行步骤
1. 设置参数
2. 种群初始化
3. 排序球队
4. 产生联赛赛程
5. 根据赛程,计算球队实力并进行比赛
6. 确定胜方和败方
7. 应用不同算子并排序联赛球队
8. 应用学习阶段算子并排序球队
9. 判断是否达到最大周数限制,是则转步骤(10),否则转步骤(4)
1 0. 采用升降级策略
1 1. 采用球员转会策略
1 2. 排序球队
1 3. 判断是否达到最大赛季限制,是则输出最好球队,否则转步骤(4)
结束语:
本文描述了一种近年来国外学者提出的排超联赛算法,算法考虑了排球联赛中的重要影响因素和过程,提出了10几个优化算子帮助VPLA算法进行全局和局部搜索,为优化领域的学者们提供了新的研究方法和潜在研究方向。
算法存在的问题是在学习阶段没有更新球队的场上阵容,只是更新了替补阵容。对于排球队来讲,比较合理的带队策略要考虑主力队员和替补队员都向强队学习,所以考虑增加主力队员的学习公式(17)。
在知识共享策略中λf和λs以及胜方策略中的ψf和ψs并未详细说明如何取值,δks和δrs的值也未给出,只是在实验部分给出N=10,β=7,δpr=0.05以及δst=0.54。这使得算法无法轻易进行编程实现,使得文献的研究结果的真实性充满疑问。算法采用100000次适应值计算次数作为结束条件,这与算法步骤中按星期和赛季判断算法是否结束的描述存在差异。
摘要：本文描述了2018年文献[1]提出的一种新颖元启发式优化算法——排超联赛算法(Volleyball Premier League Algorithm,VPLA),算法灵感来自于排球超级联赛的一个完整赛季中,各个排球队之间的比赛和互动过程。在排球比赛过程中,教练的临场指挥会起到关键作用,因此VPLA算法将临场指挥作为重要算子之一。此外,VPLA算法还考虑了排球比赛过程中的换人活动和排球队员通过学习而提高自身能力的过程。
关键词：排超联赛,互动,元启发式,算子
参考文献
[1] Moghdani R,Salimifard K.Volleyball Premier League Algorithm[J].Applied Soft Computing,2018,64(3):161-185.