微型遗传算法（μGA）

名称

微型遗传算法（Micro Genetic Algorithm, MGA, Micro-GA, μGA）

分类

查看分类思维导图

微型遗传算法是遗传算法的一种紧凑型变体。遗传算法是一类受自然选择和遗传机制启发的基于种群的元启发式优化方法。该算法隶属于演化计算与计算智能的 broader fields。

• 人工智能
  • 计算智能
    • 生物启发计算
      • 演化计算
        • 演化算法
          • 遗传算法
            • 微型遗传算法

策略

微型遗传算法旨在利用较小的种群规模高效求解优化问题，其种群规模通常介于 5 到 50 个个体之间。相较于传统遗传算法，这种紧凑型种群结构通常具有更快的收敛速度和更低的计算复杂度。

微型遗传算法采用迭代式演化过程，其中每一次迭代对应一代种群演化。在每一代中，种群通过选择、交叉和变异等操作产生新的子代。选择过程倾向于保留适应度较高的个体，使其在繁殖过程中更有可能被选为父代。

交叉操作在被选中的父代之间进行，通过交换遗传信息生成新子代。该过程旨在整合父代中的优良特征，从而产生潜在更优的候选解。随后，以一定概率对子代施加变异操作，通过引入随机扰动来维持种群多样性，并探索搜索空间中的新区域。

子代生成后，将替换种群中适应度最低的个体，从而保证种群规模在整个优化过程中保持不变。这种精英式替换策略能够保留迄今为止发现的最优解，并防止有价值的遗传信息丢失。

微型遗传算法持续执行上述迭代过程，直至满足终止条件，例如达到最大迭代代数或找到满意解。由于种群规模较小，该算法通常收敛较快，但也更容易早熟收敛到次优解。为缓解这一问题，可引入种群重启机制，即利用新的随机个体重新初始化种群，或采用多样性保持机制。

过程

数据结构：

• 种群：由若干个体组成的数组，表示优化问题的潜在候选解。
• 个体：表示单个候选解，通常编码为位串、整数串或实数向量。
• 适应度：赋予每个个体的数值，用于衡量其所表示解的质量。

参数：

• 种群规模：种群中的个体数量，通常较小（5–50）。
• 交叉概率：对一对被选父代施加交叉操作的概率。
• 变异概率：对子代施加变异操作的概率。
• 最大迭代代数：算法终止前允许执行的最大代数。

过程：

1. 用少量随机生成的个体初始化种群。
2. 评估种群中每个个体的适应度。
3. 当终止条件未满足时，重复步骤 4–9。
4. 采用某种选择方法（如锦标赛选择）从种群中选取父代。
5. 以等于交叉概率的概率，对选中的父代执行交叉操作以产生子代。
6. 以等于变异概率的概率，对子代施加变异操作。
7. 评估子代的适应度。
8. 用子代替换种群中适应度最低的个体。
9. 若满足终止条件，则返回找到的最优解；否则，转至步骤 4。

注意事项

优点：

• 由于种群规模较小，收敛速度快，因此适用于计算资源有限或时间受限的问题。
• 与传统遗传算法相比，内存需求更低，因为其维持的是紧凑型种群。
• 尤其在搜索空间较小或只需近似最优解的问题中，能够较快找到较优解。

缺点：

• 由于种群规模小且多样性不足，更容易早熟收敛到次优解。
• 由于探索能力受限，可能较难跳出局部最优。
• 对于需要广泛搜索的大规模或高复杂度优化问题，往往不太适用。

启发式建议

种群规模

• 可从较小的种群规模开始，通常设定在 5 到 50 个个体之间。
• 若问题较为复杂或需要更高多样性，可适当增大种群规模。
• 在选择种群规模时，应综合权衡收敛速度与早熟收敛风险。

交叉概率与变异概率

• 可将交叉概率设为较高水平（如 0.8–0.9），以促进父代之间的遗传信息交换。
• 变异概率宜保持较低水平（如 0.01–0.1），以在不过度破坏优良解的前提下引入适度扰动。
• 应结合具体问题特性以及探索与开发之间的平衡需求，对变异概率进行调整。

终止条件

• 可设置最大迭代代数作为终止条件，以防止算法无限运行。
• 还可考虑引入其他终止条件，例如达到目标适应度值，或在连续若干代内无明显改进。

重启机制与多样性保持

• 当算法表现出陷入次优区域的迹象时，可引入重启机制，用新的随机个体重新初始化种群。
• 可采用多样性保持技术，例如生态位方法或拥挤机制，以维持种群多样性并防止早熟收敛。

问题编码

• 应根据问题特性和约束条件，选择合适的编码方式（如二进制、整数或实数编码）。
• 编码方式应便于交叉与变异操作有效执行，并保证生成的解具有可行性。

适应度评估

• 应设计合适的适应度函数，以准确反映个体在具体优化问题中的质量或性能。
• 必要时可对适应度值进行归一化或缩放，以避免极端适应度值对选择过程产生过度支配。

选择方法

• 应采用能够兼顾潜在优良区域探索与已有优质解利用的选择方法。
• 锦标赛选择是一种常用方案，因为可通过调整锦标赛规模灵活控制选择压力。

参数调节

• 应通过实验比较不同参数设置（如种群规模、交叉概率和变异概率），以确定特定问题下更有效的配置。
• 也可采用参数调节技术，如网格搜索或自适应参数控制，在算法运行过程中自动调整参数。