岛屿遗传算法（IGA）

名称

岛屿遗传算法（Island Genetic Algorithms, IGA），岛屿模型遗传算法（Island Model Genetic Algorithms, IMGA），岛屿并行遗传算法（Island Parallel Genetic Algorithms, IPGA），分布式遗传算法（Distributed Genetic Algorithms, DGA）

分类

查看分类思维导图

岛屿遗传算法是遗传算法的一种变体，其引入了空间种群结构，灵感来源于地理隔离种群中的演化过程。该算法与其他具有空间结构的演化算法密切相关，例如元胞遗传算法和扩散遗传算法。

• 计算智能
  • 生物启发计算
    • 演化计算
      • 演化算法
        • 遗传算法
          • 岛屿遗传算法

策略

种群结构

在岛屿遗传算法中，整体种群被划分为多个子种群，每个子种群称为一个“岛屿”。这些岛屿在一定代数内独立演化，并周期性地在岛屿之间进行个体迁移。这种结构有助于更好地保持种群多样性，并降低早熟收敛的风险。

迁移

算法会周期性地从每个岛屿中选择一部分个体迁移到其他岛屿。迁移拓扑用于定义岛屿之间的连接关系，其形式可以从简单的环形拓扑到更复杂的全连接图，或自定义网络结构。迁移率和迁移频率是影响算法性能的关键参数。

岛屿演化

每个岛屿都可视作一个独立运行的遗传算法，在其局部种群上执行选择、交叉和变异等算子。各岛屿内部的演化过程可以分别进行独立调节，从而支持跨岛屿的异构搜索策略。这使得算法能够探索搜索空间中的不同区域，并保持解特征的多样性。

收敛与终止

当满足预设终止条件时，岛屿遗传算法停止运行，例如达到最大迭代代数或找到足够优质的解。算法终止后，通常会比较各个岛屿上的最优解，并将其中全局最优的解作为最终结果输出。

过程

数据结构

• 种群：由若干个体构成的集合，表示问题的潜在候选解。
• 岛屿：能够独立演化的一个子种群。
• 迁移策略：定义岛屿之间迁移的拓扑结构、迁移率和迁移频率。

参数

• 岛屿数量：算法中子种群的数量。
• 岛屿规模：每个岛屿内部包含的个体数量。
• 迁移拓扑：岛屿之间的连接模式（例如环形、全连接或自定义结构）。
• 迁移率：在一次迁移事件中，每个岛屿迁出的个体比例。
• 迁移频率：两次迁移事件之间间隔的演化代数。
• 选择方法：用于选择繁殖个体的策略（如锦标赛选择、轮盘赌选择）。
• 交叉算子：用于组合父代遗传信息以生成子代的算子。
• 变异算子：用于对个体遗传信息引入随机变化的算子。
• 终止条件：决定算法何时停止的条件（如最大代数、解质量阈值）。

算法步骤

1. 初始化种群：
   1. 创建一个由若干个体组成的种群。
   2. 将种群划分为指定数量的岛屿。
2. 评估种群中每个个体的适应度。
3. 对每个岛屿，重复执行以下步骤，直到满足终止条件：
   1. 根据所选选择方法选出用于繁殖的父代个体。
   2. 对选中的父代施加交叉算子以生成子代。
   3. 以给定概率对子代施加变异算子。
   4. 评估子代的适应度。
   5. 根据替换策略（如精英保留、代际替换）用子代更新当前岛屿种群。
   6. 当达到迁移频率时，执行迁移操作：
      1. 根据迁移率从当前岛屿中选出一部分个体。
      2. 按照迁移拓扑将选中的个体发送到相连岛屿。
      3. 接收来自相连岛屿的迁入个体，并将其整合到当前岛屿种群中。
4. 比较各个岛屿上的最优解，并输出全局最优解。

注意事项

优点

• 多样性保持：岛屿结构使各子种群能够独立演化，从而有助于维持遗传多样性并降低早熟收敛风险。
• 易于并行化：岛屿遗传算法天然适合并行实现，因为每个岛屿都可以在独立的计算资源上同时处理，从而提高计算效率。
• 鲁棒性强：岛屿遗传算法具有分布式特性，因此更不易陷入局部最优，并能够探索搜索空间中的不同区域。

缺点

• 参数敏感：岛屿遗传算法的性能高度依赖于迁移参数（如拓扑、迁移率和迁移频率）的合理配置，而这些参数往往较难调节。
• 通信开销：岛屿间的个体迁移会引入额外的通信开销，尤其在大规模问题或通信带宽受限时，可能影响整体效率。
• 同步问题：根据具体实现方式，岛屿遗传算法可能需要在各岛屿之间设置同步点；若各岛屿演化速度不同，则可能导致部分计算资源空闲等待。

启发式建议

岛屿配置

• 可从适中的岛屿数量开始（如 5–10 个），再根据问题复杂度和可用计算资源进行调整。
• 应确保每个岛屿具有足够的种群规模，以维持多样性并避免岛内过早收敛。
• 可尝试不同的岛屿规模和种群规模组合，以在探索与开发之间寻求平衡。

迁移拓扑

• 在初步实验中，可优先采用简单迁移拓扑（如环形拓扑），并在有需要时逐步尝试更复杂的拓扑结构。
• 在选择迁移拓扑时，应结合问题结构以及期望的岛屿间交互程度进行考虑。
• 也可依据领域知识或具体问题需求，对迁移拓扑进行定制设计。

迁移率与迁移频率

• 可先采用较低的迁移率（如岛屿种群的 5%–10%），以保证每个岛屿有足够时间独立演化。
• 应根据问题复杂度以及期望保持的多样性水平对迁移率进行调整。
• 迁移频率可设置为使每个岛屿在迁移发生前先经历若干代独立演化（如每 10–20 代迁移一次）。
• 可通过实验比较不同迁移率与迁移频率设置，以在多样性保持和收敛速度之间取得平衡。

算子配置

• 可先采用标准遗传算法算子作为初始配置，例如锦标赛选择、单点交叉和位翻转变异。
• 应根据问题特性和期望的搜索行为，对算子参数（如锦标赛规模、交叉概率和变异概率）进行调节。
• 还可考虑采用自适应或自调节算子参数，以动态控制探索与开发之间的平衡。

终止条件

• 应根据问题复杂度和可用计算资源设定最大迭代代数。
• 可增加解质量阈值作为附加终止条件，以便在找到满意解时提前停止算法。
• 可持续监测各个岛屿上的最优解演化情况；若在连续若干代内无显著改进，则可考虑终止算法。