1.4　截断选择

截断选择是最基本的选择算法之一。Heinz Muhlenbein（1993）在关于育种者遗传算法（breeder genetic algorithm）的论文中指出，截断选择需要根据适应度对种群进行分类。分类后，选择一定比例（例如1/3）的种群作为育种种群。然后从育种种群中取样潜在解，以帮助生产下一代。创建第二代的具体方法将在第2章中讨论。图1-1展示了如何将整个种群按截断选择来划分。

图1-1　截断选择

截断选择算法可以用清单1-1中的伪代码表示。

清单1-1　截断选择伪代码

def truncate_select(breeding_ratio, sorted_population)
  # Sort the population. For efficiency you should move
  # this outside the selection function and perform the sort
  # once for each batch of selections you will perform.
  sort(sorted_population)
  # Determine the size of the breeding population.
  count = len(sorted_population) * breeding_ratio
  # Obtain a uniformly distributed (all numbers have
  # equal probability) single random number
  # between 0 and count.
  index = uniform_random(0,count)
  # Return the selected element.
  return sorted_population [index]

截断选择算法的最大限制之一，就是必须对种群进行排序，你必须不断使整个种群处于已知的排序状态。这种排序严重限制了该算法针对多核和分布式计算而并行化的能力。结果，该算法无法在大种群中很好地伸缩，因为你可能有许多不同的选择在并行运行。

此外，由于亲本只生孩子，而亲本没有加入下一代，因此有可能没有孩子达到或超过上一代最优解的分数。因此，你应该用精英来选择一个或多个最优解，并直接复制到下一代。如果不用精英，你的最佳得分可能会在两次迭代之间降低。