探索选择

引入选择

在上一章中，我们学习了如何使用适应度函数来评估解决方案。记住，适应度函数用于衡量一个解决方案的可行性。适应度函数是遗传算法的重要组成部分，但如果不用它们，这些函数就毫无意义。在对种群进行评估并为每个染色体分配适应度之后，现在是时候执行选择操作了。

如果你曾参与过团队合作，就会明白选择合适成员的重要性。无论是体育、音乐、工作还是其他协作项目，挑选合适的人填补岗位并与其他成员互补，对于组织的成功至关重要。这种“选对人担任合适角色”的理念，直接对应于遗传算法中的选择机制。

选择是进化过程中的第一个遗传算子。表面上看，选择负责从种群中选出将在下一步繁殖的染色体；本质上，选择确保下一代染色体比上一代更强。

查尔斯·达尔文的进化论指出，有利于生存的优良特征会在后代中逐渐变得更加普遍。无论你是否相信进化论，“自然选择”这一概念都是遗传算法的核心思想之一。

人工选择与自然选择的区别

在遗传算法的语境下，选择过程更准确地称为人工选择。需要注意的是，自然选择与人工选择之间的区别。在遗传算法中，我们可以自主定义选择标准和适应度准则；而在自然界中，选择是随机的，适应度则是选择过程的结果。也就是说，在自然界中，选择发生在适应度确定之前。而在遗传算法中，我们有能力决定哪些解的特性与其适应度相关，并基于这些标准进行选择。因此，我们能够控制哪些特性在代际之间得以保留。

注意：这一过程与自然选择不同，因为在自然界中，适应度只有在选择发生之后才能确定。

人工选择赋予我们选择对问题至关重要的特性的能力。为了更具体地理解这一点，设想一下你在训练一支短跑队。你有三名短跑运动员，但需要再选一名组成完整的4×100米接力队。你有两个候选人：一位百米成绩为25秒，另一位低于11秒。在这种情况下，你可以自主决定哪位选手更有可能带来成功，并且可以自行定义成功的标准。

选择的目标是根据预设的适应度标准，构建出最强的父代组合，以提高后续世代取得成功的可能性。在本章中，我们将进一步探讨选择如何影响算法性能，介绍选择率的概念，并学习不同的选择技术及其适用场景。

选择的特性

选择对遗传算法的性能至关重要，因为它有助于生成下一代的良好解决方案。其核心思想是：父代具备基于适应度标准而表现出的优势特征，并将这些特征传递给下一代。

试想一下：在中世纪和近代早期的欧洲，君主们会精心挑选配偶以维持王室地位。他们假设“皇室血统”更强大，认为平民基因会破坏他们的血统纯正。

君主们实际上采用了一种松散的选择方式。他们依据领土、权力、财富等因素来选择配偶，这本质上就是一种“适应度”判断。他们希望联姻其他王室成员，从而延续强健的血统和家族的持续繁荣。

然而，由于可婚配的王室成员有限，后期的君主往往不得不“近亲结婚”。起初这似乎不是问题——双方都是贵族，因此都“强大”；但随着近亲通婚现象增多，王室内部出生缺陷的严重程度也日益加剧。那么，为什么皇室血统会遭受这些先天缺陷？根本原因在于缺乏遗传多样性。

早期君主的选择策略过于关注表面的“适应度”，而忽视了遗传多样性的维护。君主们的困境为我们提供了关于遗传算法中选择重要性的深刻教训。

选择与遗传多样性

选择的关键在于平衡遗传多样性和适应度。遗传多样性指的是种群中基因的丰富程度。但这并不意味着适应度水平的多样化。我们可能拥有多个适应度相同但基因结构差异很大的个体。以下图示展示了两个解决One-Max问题的候选方案：

这两个个体具有相同的适应度，但彼此差异显著。在交叉操作中，它们的差异特征可以完美结合，产生一个强大的后代。如下图所示：

如果我们无法保持种群的遗传多样性，算法很可能过早收敛，而无法找到最优解。虽然还有其他策略（如变异）可用于维持遗传多样性，但选择是第一步，其效果对整体性能有显著影响。

选择是一种有偏采样

在统计学中，选择属于一种有偏的采样方式。采样是指从总体中选取一个较小的子集来代表整体。在调查和质量保证中，采样尤为重要，因为它用于推断整体群体的信念或特征。

采样之所以必要，是因为几乎不可能对整个群体进行全面调查。统计学家的目标是获得一个能代表总体的样本，其核心是多样性。而选择的目的却是为了提升下一代的整体质量。这意味着大多数选择策略会倾向于某些个体，因为它们更有可能改善种群。

正如采样只选取部分个体一样，选择策略通常也仅从种群中选取一部分作为父代。其逻辑是：并非所有染色体都适合成为父代，这样可以逐步淘汰较弱的特征，同时保留较强的特征。

被选中用于交叉的父代数量称为选择率。选择率是一个介于 0 和 1 之间的数值，表示被选中用于交叉的种群比例。例如，当种群规模为100，选择率为 0.8 时，意味着将有80个父代被选中进行交叉。

调整选择率会影响算法的运行速度以及收敛速度。选择率为1并不构成问题，通常选择率处于 0.75 到 1 的范围内。

选择压力的重要性

我们可以通过选择压力来衡量一种选择策略在平衡遗传多样性与适应度方面的表现。选择压力是数学上衡量某个染色体被选为父代的可能性的指标。它定义为最适个体被选中的概率与平均适应度个体被选中概率的比值。

选择压力由选择率和选择策略共同决定。在完全随机选择的情况下，选择压力恰好为 1，因为每个个体被选中的概率相同。选择压力越高，说明该策略越倾向于选择适应度更高的个体。它是衡量选择策略偏向程度的指标。

我们可以利用选择压力来量化选择策略是否契合当前问题的需求。如果问题需要更多遗传多样性，应选择低选择压力的策略；如果希望问题快速收敛，则应选择高选择压力的策略。

选择的类型

选择主要分为两类：基于适应度的选择和基于奖励的选择。

基于适应度的选择 是严格依据适应度标准进行的选择。这类策略是最常见的选择方法。其目标是提升适应度，因此假设适应度是未来适应度的最佳预测指标。

基于奖励的选择 是依据个体累计获得的奖励来进行选择。其理念是：高奖励的个体能产生更优秀的后代。奖励可通过多种奖励函数计算得出。这类方法在多目标优化中具有一定优势，但应用相对较少。

在本课程中，我们将仅使用基于适应度的选择策略，因为它们最为常见，且实现起来最简单。

实践

让我们通过一个小测验来检验你对本节课内容的理解：