国外新颖优化算法

韩毅　徐梓斌　张亮　邓丽丽　章美玲

摘 要：本文描述了2018年文献[1]提出的一种新颖元启发式优化算法——排超联赛算法（Volleyball Premier League Algorithm， VPLA），算法靈感来自于排球超级联赛的一个完整赛季中，各个排球队之间的比赛和互动过程。在排球比赛过程中，教练的临场指挥会起到关键作用，因此VPLA算法将临场指挥作为重要算子之一。此外，VPLA算法还考虑了排球比赛过程中的换人活动和排球队员通过学习而提高自身能力的过程。

关键词：排超联赛;互动;元启发式;算子

排球比赛中，一张网将两队各六名队员分开。为了获得一分，每个队必须让球落在另一队的场地上。一方的球员试图让球越过球网落到另一队的场地上，另一队球员极力救球并尽力让球过网落到对方场地，场上形成了拉锯战。拉锯战持续进行，直到某队出现失误使得对方得1分。比赛即将开始时，主教练把出场队员名单交给第二裁判员。运动员入场后，3名球员站在前排，另外3人站在后排。每个队都可以根据自己队员的情况，组成自己的场上阵容。比赛期间，教练站在球场附临场指挥和指导运动员。板凳球员坐在场下，随时准备好参加比赛（图1）。

在一场普通排球比赛中，影响比赛结果的因素很多。每场比赛结果未知，球队输赢都有可能，弱队胜强队也不足为奇。通常用球队实力来刻画强队更有可能击败对手的事实。球队关注即将到来的比赛，不考虑后续即将到来的比赛。鉴于之前的赛果、当前球队实力和赢下比赛的几率，每支球队在场上的首发阵容会进行相应调整。当球队i击败球队j时，球队i赢得比赛的优势就是球队j的劣势，球队有了某种劣势，也说明球队缺少某种优势。

联赛等于种群，赛季轮次表示当前迭代次数，球队是种群的解，星期表示每轮联赛赛程。

排球比赛的教练可以通过现场指导和平时指导来提高运动员的基本技能。教练通过模拟与真实比赛强度相同的训练，来提升运动员的移动速度、预判能力、把握时机能力、沟通更累和团队合作能力，从而满足团队的战略要求。

一、VPLA算法

（一）解表达方式

球队成员分为场上球员、板凳球员和教练。算法的解由两个部分组成，分别称为主动部分和被动部分。主动部分代表每个团队的六名场上队员，被动部分代表板凳队员，解的适应度函数值由这六名场上队员决定（图2）。

球队的阵容决定了球队在场上的整体风格，一般来说排球比赛里通常有3种阵容——“4-2”“2-4”和“5-1”，队形中“H-S”风格表示攻击手和二传手的个数。教练需要根据场上球员和板凳球员的类型和能力决定最好的阵容，通常来看场上队员和板凳球员的数量相同。在比赛过程中，阵容会不断变化。教练在比赛中会不断安排阵容调整，因此场上队员与板凳队员的角色也不断变化（图3）。

（二）初始解

每支球队都有自己的阵容和替补，对于VPLA算法，NT表示球队数量，x表示第i支球队场上阵容的第j个队员，x表示第i支球队替补席的第j个队员。

初始种群可以由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（x）表示第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表示位置重排次数。