1.5　联赛选择

联赛选择是演化算法的另一种流行的选择算法。它易于实现，解决了截断选择的可伸缩性问题。联赛选择通过一系列轮数来进行，并总是让获胜者进入下一轮。轮数是一种训练设置，对于每一轮，你必须在种群中选择两个随机个体，得分较高的个体进入下一轮联赛 ^[3]。

联赛选择可用于从种群中选择适应或不适应的个体。要让适应度分数较少者胜出，你只需要进行一次反转联赛。联赛选择的一个例子如图1-2所示。

图1-2　联赛选择

在图1-2中，我们使用的轮数为3。第1轮，我们随机选择了两名成员。个体#2获得最佳分数，进入第2轮。在第2轮中，选择了新的竞争者——个体#20，得分为202，赢得了第2轮联赛，并进入第3轮。在第3轮中，个体#20保持冠军身份，并赢得了整个联赛。清单1-2总结了该算法。

清单1-2　联赛选择

# Perform a tournament selection with the specified number of
# rounds. A high score is considered desirable (maximize)
def tournament_select(rounds,population)
  # Nothing has been selected yet
  champ = null
  # Perform the rounds. There is a "round zero" where the first
  # contender is chosen becomes the champ by default.
  for x from 0 to rounds:
    # Choose a random contender from the population. 
    contender = uniform_random(population)
　
    # If we do not yet have a champ,
    # then the current contender is the champ by default.
    if champ is null:
      champ = contender
    # If the contender has a better score, it is the new champ.
    else if contender.score > champ.score:
      champ = contender
　
  return champ

从清单1-2所示的代码中可以看到，不需要排序。你还可以将“小于”运算符翻转为“大于”运算符，从而创建反转选择。

使用联赛选择还可以打破演化算子经常使用的典型世代模型。打破世代模型将极大提高并行处理的效率，缺少世代模型也更接近生物学。由于每天都有婴儿出生，因此人类世代的开始和结束并没有一个明确的时刻。

要放弃世代模型，请使用联赛选择，并选择两个合适的亲本来生一个孩子。要选择不适应的种群成员，请进行反转联赛。不适应的种群成员被“杀死”，由新的孩子代替。这种联赛模型消除了对精英的需求。最优解永远不会被取代，因为反转联赛永远不会选择它。

该算法对于并行处理非常有效。并行处理循环可能类似于清单1-3。

清单1-3　并行演化

best = null
required_score = [the score you want]
# Loop so long as we either do not yet have a best,
# or the best.score is less than required_score.
parallel while best is null or best.score < required_score:
  # Lock, and choose two parents. We do not want changes
  # to the population while picking the parents.
  lock:
    parent1 = tournament_select(5, population)
    parent2 = null
　
  # Pick a second parent.
  # Do not select the same individual for both parents.
  while parent2 == null or parent1 == parent2:
    parent2 = uniform_random(population)
# Parents are chosen, so we can exit the lock
# and use crossover to create a child. 
child = crossover(parent1, parent2)
child.score = score(child)
# we must now choose (and kill) a victim.
# The victim is replaced by the new child.
lock:
  victim = reverse_select(5, population) 
  population.remove(victim)
  population.add(child)
# See if the child is the new best.
  if child.score > best.score
    best = child

清单1-3的代码包括两个加锁的部分。一个线程一次只能执行一个加锁的部分，当某个线程位于加锁区域内时，其他线程必须等待。为了提高效率，应该优化加锁部分中的代码，以便非常快速地执行。第一个锁只选择两个亲本，耗时的部分是为孩子计分。孩子的创建和计分在所有锁之外，这种方法很好，因为无须等待计分。将耗时的代码保留在锁之外，总是一个好习惯。最后的锁选择一个要被“杀死”的群成员并插入该孩子。我们还将跟踪至今为止找到的最优解。

你可能已经注意到上面的交叉（crossover）函数。交叉是将新成员添加到种群的几种方法之一。交叉将在第2章中讨论。

联赛选择在生物学上也是合理的。为了生存到第二天，个体不需要战胜种群中最快的掠食者，只需要战胜它在任何给定的一天遇到的掠食者。