元胞遗传算法（CGA）

Goat_Yang2026/3/21约 1525 字大约 5 分钟

元胞遗传算法（CGA）

名称

元胞遗传算法（Cellular Genetic Algorithms, cGAs）

分类

查看分类思维导图

元胞遗传算法是遗传算法的一个子类，其引入了空间局部性交互机制，灵感来源于元胞自动机。该类算法与并行遗传算法和扩散遗传算法密切相关。:contentReference[oaicite:0]

计算智能
- 生物启发计算
  - 演化计算
    - 演化算法
      - 遗传算法
        元胞遗传算法

策略

在元胞遗传算法中，个体被排列在一个空间网格中，通常为二维晶格结构，其中每个个体仅与其直接邻域内的个体发生交互。这种局部化交互机制有助于形成生态位并保持种群的遗传多样性，因为有潜力的解能够在种群中逐步产生并扩散。:contentReference[oaicite:1]

重叠的邻域结构在限制遗传物质快速传播的同时促进了解空间的探索，从而在局部优化与全局搜索之间取得平衡。这种结构化种群方法有助于防止过早收敛，并增强算法跳出局部最优的能力。:contentReference[oaicite:2]

选择与繁殖算子均在个体的局部邻域内执行，由此高质量解能够逐步涌现，并随时间在网格中扩散。这种扩散过程使算法能够在利用优质解的同时，维持搜索全过程中的种群多样性。:contentReference[oaicite:3]

过程

数据结构

种群：由个体构成的二维网格，其中每个个体表示问题的一个候选解。
个体：对问题解的编码表示，通常采用定长字符串形式（如二进制、整数或实数编码）。
邻域：与某一中心个体发生交互的一组个体，通常定义为其相邻网格单元（如 von Neumann 邻域或 Moore 邻域）。

参数

种群规模：网格中的个体总数。
网格拓扑：网格的形状及其连接方式（如方形、六边形或环面结构）。
邻域规模：每个邻域中包含的个体数量。
选择方法：在邻域内选择父代个体进行繁殖的策略。
交叉概率：应用交叉算子生成子代的概率。
变异概率：应用变异算子引入随机扰动的概率。

步骤

初始化种群：
1. 创建一个二维个体网格，并随机生成初始解。
2. 评估种群中每个个体的适应度。
当终止条件未满足时，重复以下过程：
1. 对种群中的每个个体：
  1. 确定当前个体的邻域。
  2. 在邻域内依据给定选择方法选取父代。
  3. 按照交叉概率对所选父代施加交叉算子，生成子代。
  4. 按照变异概率对子代施加变异算子。
  5. 评估子代的适应度。
  6. 若最优子代的适应度高于当前个体，则用其替换当前个体。
2. 更新终止条件（如迭代代数上限或适应度阈值）。
返回种群中找到的最优解。

注意事项

优点

通过维持局部化交互与生态位结构，促进种群多样性并降低过早收敛风险。
易于并行实现，因为每个个体的繁殖过程相对独立。
对具有复杂适应度景观和多个局部最优的问题具有较好的求解能力。

缺点

由于较大的种群规模及局部交互机制，可能需要更多计算资源。
网格拓扑和邻域规模的选择会显著影响算法性能，因此需要谨慎调整。
与传统遗传算法相比，优质解在网格中的扩散速度可能较慢。

启发式建议

种群初始化

可利用问题相关启发式规则或领域知识生成初始解，以保证初始种群具有较好的多样性并覆盖潜在优良区域。
若缺乏先验知识，则应采用随机初始化方式，以最大化种群多样性。

网格拓扑与邻域规模

对大多数问题而言，采用方形网格以及 von Neumann 邻域或 Moore 邻域（即 4 邻域或 8 邻域）通常具有较好效果。
可考虑采用环面网格以消除边界效应，并确保所有个体具有一致的邻域规模。
较大的邻域有助于优质解更快扩散，但也可能削弱种群多样性。

选择方法

小规模锦标赛选择（如锦标赛规模为 2–4）通常能在维持选择压力的同时较好地保持多样性。
也可采用适应度比例选择，但当适应度分布高度偏斜时，该方法可能导致过早收敛。

交叉率与变异率

通常可从较高交叉率（如 0.8–0.9）开始，以增强新解生成能力和搜索探索性。
可采用较低变异率（如 $1/L$ ，其中 $L$ 为编码长度），以在不破坏优良结构的前提下引入适度扰动。
可根据种群多样性和收敛速度自适应调整交叉率与变异率。

终止条件

应根据问题复杂度和可用计算资源设置最大迭代代数。
可采用适应度阈值作为停止准则，即当找到满意解时终止算法。
还可考虑基于种群多样性或适应度改进速率的收敛判据。

并行化

可利用元胞遗传算法天然适合并行实现的特点，将各个个体的繁殖过程分配到不同处理器或线程上执行。
需要对种群网格的更新过程进行同步，以保证一致性并避免竞争条件。