第19章　世界杯竞赛算法

19.1　世界杯竞赛算法的提出

世界杯竞赛（World Competitive Contests，WCC）算法是2016年由Yosef和Habib提出的一种模拟世界杯竞赛的优化算法^[63]。该算法的设计灵感来自世界杯竞赛的运动规则，如篮球世界杯竞赛。我们知道，有许多竞争竞赛形式的体育运动，每个团队都有一套规则，并把一些队员分成不同的组。该算法从第一轮开始，竞赛队伍进入不同的组，将开始与他们的对手队竞争。取胜的队伍晋升到下一阶段继续其竞争。高水平的团队将上升到最后的淘汰阶段，并将在下一轮中相互竞争。在一个赛季结束时，冠军产生，其他团队将等待新的赛季。

世界杯竞赛算法通过对8个基准函数的实验和数值结果，与遗传算法（GA）、帝国竞争算法（ICA）、粒子群优化算法（PSO）、蚁群优化算法（ACO）和学习自动机（LA）5种算法对比，在稳定性、收敛性、标准差和寻优时间几个方面进行比较的结果表明，在许多情况下，WCC算法比其他算法具有更好的性能。

WCC算法属于无约束的优化算法，它既可以作为离散和连续的优化算法，也可以应用于多目标或单目标优化问题。虽然WCC是受人类运动规则启发而提出的优化算法，但它可以应用于求解经济学、计算机科学、工程等领域的优化问题。

19.2　世界杯竞赛算法的描述

WCC算法从第一批团队开始。每个团队都有几个机动的选手。所要参赛的团队根据地理距离被分成不同的组，并开始在不同组内相互竞争。这个阶段的比赛可以被看作是局部优化。全局优化阶段是在分组比赛之后开始的。被淘汰的团队将不会被从比赛中移除，他们将等待新赛季的比赛。WCC算法包括几个主要阶段：生成初始团队、分组、举办比赛、评分、淘汰、终止。下面对WCC算法每一阶段进行具体介绍。

1. 生成初始团队

生成初始团队的数量通常根据问题变量的具体性质随机生成。图19.1列出一个有9个选手的球队的例子。一支球队由不同角色的多名选手组成。每个选手都有自己的角色，这对于算法的良好性能和收敛性非常重要。根据问题的性质，可以应用许多不同角色。每一支球队都用一个1×（N+1）数组表示，作为问题的一个解，定义如下。

Team=［P₁，P₂，…，P_i，…，P_N］（19.1）

其中，N表示问题的维度；P_i表示第i球员。

2. 分组

分组或分类是指组织团队分成不同的组，以便互相竞争。分组有许多方法，如海明距离、最大可能、最小似然等方法。第二个阶段是根据问题的性质，图19.2表示8个组及一个必须被放入其中一个组的团队。标记在边缘的值在团队和组之间是相似的。第一组比赛将在球队分组后进行。

3. 举办比赛

举办比赛必须遵循一些比赛规则，如何定义规则取决于竞赛的性质。这里只考虑一个竞争比赛规则的两个终止条件：一是时间间隔；二是根据达到得分数呼叫“比赛终止”，而不是考虑“时间”终止条件。在比赛中，对手团队通常模仿对方的价值观，并采取措施通过帮助他们的球员更加积极地改善自己的状态、发挥更积极的作用，并获得更多的进球。得分越高，表明团队的状态越好。

在WCC算法中，有一个到对方篮板投中得一分的罚球。当球员接到球后，裁判将发出投球指令，球员投篮后，裁判宣布判罚得分数。

球员在比赛过程中的角色可概括为如下几方面。

（1）投篮：投篮是一个球员朝向对手的篮板投掷一个球的过程。在WCC算法中，球员向对手的篮板投出的球数及投球得分数被认为是他对队友的价值。如果竞争对手获得的分数提升，团队将更新其球员的价值；否则，就无法更换球员。

（2）进攻：在投篮等进攻角色中，一名球员以不同的价值向对手球队掷球是随机发生的。尽管进攻和投篮角色在某些方面是相似的，但他们在其他方面是不同的。一个球员在投篮角色中选择他最有价值的队友，而进攻角色中的球员传球会为对手随机创造价值。

（3）传球：传球是球员之间的主要联系之一。如图19.3所示，一个球员将球传给一个随机选择的队友，并改变他的价值。

（4）穿越：穿越是从球员到他的队友长传球的一种方式。在WCC算法中，交叉传递命名为一个α角度，如图19.4所示。α值越大，距离范围越大。正如图19.4所示，将交叉传递作为左旋转来实现。

4. 评分函数

每个团队都可以视为待优化问题的一个解。有很多团队，每个团队都有不同于其他团队的优点。分数值是指示开发的解如何接近最好解的值。正如前面提到的，一个团队是由一些球员组成的，他们的价值观是DNA序列起始位置的基序。适应度函数在优化算法和算法的收敛性和相关性方面起主要作用，要么会收敛到一个不好的解，要么在设计不合适的情况下收敛困难。优化速度也是一个至关重要的因素，因此必须快速计算。考虑到问题的本质，可以把评分函数的最大化（或最小化）定义为

Score（team）=Score（P₁，P₂，…，P_N，Score）（19.2）

显然，要解决对式（19.3）这个得分函数的最大化问题。得分值更高的团队表示更值得称赞的成功团队。图19.5列出了如何计算得分的示例。

其中，k∈｛A，T，C，G｝；l为基序的长度；i为DNA序列的样品编号。

5. 淘汰阶段

在第一组比赛举行之后，其中最有功绩的球队彼此将进入最后的淘汰阶段。一个球队的竞争对手可以通过不同的方法选择，如随机确定、最大相似性、最小相似性、最大似然、最小似然和许多其他方法。这些阶段将继续，直到选择出冠军。弱队将等待一个新的季节开始。在一个新的季节开始时，弱队必须改变球员的角色和价值观。图19.6所示为16个优秀球队在淘汰赛阶段的对阵图。

被其他队淘汰的未能晋级淘汰赛的那些球队，在这个阶段必须为国际比赛的新赛季做好准备。

6. 停止条件

可以选择以下选项之一作为终止条件。

（1）预定季节结束。

（2）分配的时间已到。

（3）达到确定的精度。

（4）保持好几个赛季的最好成绩。

（5）调用评分函数的防腐数据。

（6）使用上述选项的组合。

19.3　世界杯竞赛算法的实现流程

世界杯竞赛算法的实现流程如图19.7所示。