排序选择遗传算法（RSGA）

名称

排序选择遗传算法（Ranked Selection Genetic Algorithm），排序选择（Rank Selection），基于排序的选择（Rank-based Selection）

分类

查看分类思维导图

排序选择遗传算法是遗传算法的一种变体。遗传算法是一类受自然选择与进化原理启发的经典优化方法，隶属于演化计算领域，而演化计算又是计算智能的一个分支。该算法与锦标赛选择、适应度比例选择等其他选择机制密切相关。

• 计算智能
  • 演化计算
    • 演化算法
      • 遗传算法
        • 选择方法
          • 排序选择遗传算法

策略

排序选择遗传算法在标准遗传算法的选择阶段引入了一种不同的处理方式。它并不直接依据适应度值来确定个体的被选概率，而是首先按照适应度对种群中的个体进行排序，然后为每个个体分配相应的等级。随后，个体的选择概率不再由其实际适应度值决定，而是根据其等级进行计算。

这种基于排序的选择方法有助于缓解直接基于适应度进行选择时所带来的问题，例如优化初期少数高适应度个体过早主导选择过程，以及由此引发的早熟收敛。通过先赋予个体等级、再根据等级进行选择，排序选择遗传算法能够提供更加平衡且可控的选择压力，从而增强对搜索空间的探索能力，并维持种群多样性。

等级通常以线性或指数方式进行分配，其中最优个体获得最高等级，最差个体获得最低等级。随后，通过预先设定的公式或映射函数，将这些等级转换为相应的选择概率。该映射函数可以用来调节选择压力：较高的选择压力更倾向于优先保留高等级个体，而较低的选择压力则会使选择概率分布更加均匀。

过程

数据结构：

• 种群：由若干个体组成的列表或数组，表示优化问题的潜在候选解。
• 个体：种群中的单个解，通常表示为一个取值列表或数组（基因）。
• 适应度函数：用于评估个体解质量的函数。

参数：

• 种群规模：种群中个体的数量。
• 变异率：在变异步骤中某个基因发生变异的概率。
• 交叉率：两个个体被选中执行交叉的概率。
• 选择压力：控制等级到选择概率映射关系的参数。

步骤：

1. 随机生成个体，初始化种群。
2. 使用适应度函数评估种群中每个个体的适应度。
3. 按适应度值从高到低对种群进行排序（由优到劣）。
4. 根据个体在排序后种群中的位置，为每个个体分配等级。
5. 利用预定义映射函数，根据个体等级计算其选择概率。
6. 重复以下过程，直到生成新的种群：
   1. 根据已计算的选择概率，从种群中选取两个父代个体。
   2. 对选中的父代执行交叉操作，生成子代个体。
   3. 以一定概率对子代个体执行变异操作。
   4. 将生成的子代个体加入新种群。
7. 用新种群替换旧种群。
8. 重复步骤 2–7，直到满足终止准则（如达到最大迭代代数或达到期望适应度水平）。
9. 返回种群中找到的最优个体作为问题的解。

注意事项

优点：

• 降低早熟收敛风险：通过使用等级而非直接使用适应度值，排序选择遗传算法能够减弱少数高适应度个体在优化早期对选择过程的过度支配，从而提升搜索空间探索能力。
• 有助于保持多样性：基于排序的方式能够提供更加平衡的选择压力，从而减少潜在有价值遗传信息的过早丢失。
• 选择压力可调：通过修改将等级映射到选择概率的函数，能够较为方便地调节选择压力，从而对算法行为进行细化控制。

缺点：

• 计算复杂度增加：排序选择遗传算法需要在每一代根据适应度值对种群进行排序，当种群规模较大时，这一过程会带来较高计算开销。
• 对排序方案敏感：算法性能可能对所采用的排序方案（如线性排序、指数排序）以及选择压力参数较为敏感，因此通常需要仔细调参。
• 缺乏适应度比例信息：与适应度比例选择不同，排序选择遗传算法并不直接利用适应度值进行选择；对于某些适应度差异本身具有重要意义的问题，这一特性可能并不理想。

启发式建议

种群规模

• 初始时应设置足够大的种群规模，以维持多样性并有效探索搜索空间，常见范围为 50–200 个个体。
• 对于更复杂的问题或更大的搜索空间，可适当增大种群规模，以保证搜索覆盖度和种群多样性。

变异率

• 变异率应设置得足够低，以避免过于频繁地破坏优良解，常见范围为 0.01–0.1。
• 应根据问题复杂度以及所需探索程度调整变异率。对于具有大量局部最优的问题，较高变异率可能更有利。

交叉率

• 交叉率应设置得足够高，以促进个体之间遗传信息的交换，常见范围为 0.6–0.9。
• 可通过实验比较不同交叉率设置，在探索与开发之间寻求更合适的平衡。

选择压力

• 初始时可采用适中的选择压力，以在偏向高等级个体和维持种群多样性之间取得平衡。
• 当算法收敛速度过慢，或希望更加强化对优良解的利用时，可适当提高选择压力。
• 当算法出现早熟收敛，或希望增强对搜索空间的探索时，可适当降低选择压力。

排序方案

• 可先采用线性排序方案作为初始选择方式，即个体选择概率随等级从优到劣线性递减。
• 若希望更突出高等级个体、形成更强的选择压力，可考虑采用指数排序方案。
• 应结合具体问题，通过实验比较不同排序方案，并观察其对算法性能的影响。

终止准则

• 可设置最大迭代代数作为终止准则，以防止算法无限运行。
• 还可采用基于适应度的终止准则，例如当最优适应度达到某一阈值，或最优适应度在连续若干代内不再改进时停止算法。
• 可监测种群收敛情况；若种群多样性低于某一阈值，则可提前终止算法，以避免在已收敛种群上继续浪费计算资源。