适应度缩放遗传算法（FSGA）
2026/3/21约 1656 字大约 6 分钟
适应度缩放遗传算法（FSGA）
名称
适应度缩放遗传算法（Fitness Scaling Genetic Algorithm, Fitness Scaling GA, FSGA）
分类
适应度缩放遗传算法是标准遗传算法的一种变体，隶属于演化计算领域，而演化计算又是计算智能与生物启发计算的一个分支。该算法与排序选择遗传算法、玻尔兹曼选择遗传算法等其他遗传算法变体密切相关。
- 计算智能
- 生物启发计算
- 演化计算
- 演化算法
- 遗传算法
- 适应度缩放遗传算法
- 遗传算法
- 演化算法
- 演化计算
- 生物启发计算
策略
适应度缩放遗传算法在标准遗传算法中引入适应度缩放机制，以减弱种群中优势个体的主导作用，因为这类个体可能导致算法过早收敛。通过对个体适应度值进行缩放，可以调控选择压力，从而在搜索空间的探索与开发之间实现更为合理的平衡。
适应度缩放
个体的原始适应度值通过某种缩放函数进行变换。常见的缩放方法包括线性缩放、 截断和幂律缩放。具体采用何种缩放函数，应依据问题特性以及期望的选择压力水平进行确定。
选择
在完成适应度缩放之后，基于缩放后的适应度值采用标准遗传算法中的选择方法，如轮盘赌选择或锦标赛选择。这样可以保证个体的被选概率与其相对缩放适应度成正比，而非直接由原始适应度决定。
遗传算子
对被选中的个体施加标准遗传算法中的遗传算子，即交叉和变异，以生成下一代种群。缩放后的适应度值并不直接作用于遗传算子本身，而是通过影响选择过程来决定哪些个体参与繁殖。
过程
数据结构：
- 种群：由个体构成的数组，表示问题的潜在候选解。
- 个体：表示单个解，通常编码为二进制串或实值向量。
- 适应度：用于存储种群中每个个体适应度值的数组。
- 缩放适应度：用于存储种群中每个个体缩放后适应度值的数组。
参数：
- 种群规模：种群中个体的数量。
- 交叉概率：对一对被选个体施加交叉算子的概率。
- 变异概率：对个体施加变异算子的概率。
- 缩放方法：所采用的适应度缩放函数（如线性缩放、 截断、幂律缩放）。
- 缩放参数：与所选缩放方法相关的附加参数（如缩放因子、截断阈值）。
- 初始化种群
- 创建由随机遗传信息构成的个体数组
- 评估种群中每个个体的适应度
- 将适应度值存储到适应度数组中
- 当终止条件未满足时，重复步骤 3-7
- 对适应度值进行缩放
- 对适应度数组应用所选缩放方法
- 将缩放后的适应度值存储到缩放适应度数组中
- 选择用于繁殖的个体
- 基于缩放适应度数组采用选择方法（如轮盘赌选择、锦标赛选择）
- 选择若干对个体构成交配池
- 应用交叉算子
- 对每一对被选中的个体，生成一个 0 到 1 之间的随机数
- 若该随机数小于交叉概率，则执行交叉操作生成子代
- 否则，不加修改地将所选个体加入新种群
- 应用变异算子
- 对新种群中的每个个体，生成一个 0 到 1 之间的随机数
- 若该随机数小于变异概率，则对该个体执行变异操作
- 用新种群替换旧种群
- 评估新种群中每个个体的适应度
- 将适应度值存储到适应度数组中
- 返回搜索过程中找到的最优解
注意事项
优点：
- 通过调控选择压力，有助于防止算法过早收敛
- 有助于在搜索空间的探索与开发之间实现更合理的平衡
- 能够较好处理个体间适应度差异较大的问题
缺点：
- 引入了额外参数（缩放方法及其相关参数），需要进行调节
- 缩放方法的选择可能依赖于具体问题特性，因此通常需要实验比较
- 相较于标准遗传算法，适应度缩放会带来额外的计算开销
启发式建议
缩放方法的选择
- 线性缩放方法简单且有效，适用于适应度值分布范围较窄的问题
- 当种群中存在少数适应度极高、需要抑制其主导作用的个体时， 截断较为适用
- 幂律缩放可通过调整缩放因子，在探索与开发之间提供可调节的平衡机制
缩放参数的设定
- 对于线性缩放，应选择适当的缩放因子，以维持合理选择压力并避免过早收敛
- 在 截断中，截断阈值应根据期望的选择压力水平和种群适应度分布来设定
- 对于幂律缩放，应依据问题特性以及探索与开发之间的平衡需求调整缩放因子
选择压力的平衡
- 可在演化初期采用较低选择压力（如使用较小缩放因子的线性缩放）以增强探索能力
- 随着算法运行逐步提高选择压力，从而将搜索重点转向开发与收敛
- 应持续监测种群多样性，并在观察到过早收敛迹象时调整缩放参数
与其他遗传算法变体结合
- 适应度缩放可与其他遗传算法变体结合使用，例如生态位方法或自适应算子，以进一步提升算法性能
- 在组合多种技术时，应注意算法复杂度增加以及不同组成部分之间可能产生的非预期相互作用
- 可通过实验比较不同技术组合与参数设置，以确定针对具体问题的最有效配置