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章中討論。

聯賽選擇在生物學上也是合理的。為了生存到第二天，個體不需要戰勝種群中最快的掠食者，只需要戰勝它在任何給定的一天遇到的掠食者。