紧凑遗传算法（cGA）

名称

紧凑遗传算法（Compact Genetic Algorithm, cGA）

分类

查看分类思维导图

紧凑遗传算法是标准遗传算法的一种变体，属于进化计算领域，而进化计算又是计算智能的重要分支。它与其他基于种群的优化算法密切相关，例如分布估计算法（Estimation of Distribution Algorithms, EDAs）和概率模型构建遗传算法（Probabilistic Model-Building Genetic Algorithms, PMBGAs）。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
        • 紧凑遗传算法

策略

紧凑遗传算法并不显式维护一个个体种群，而是基于种群的概率模型进行搜索。该模型通常表示为一个概率向量，其中每个元素对应某一基因（或比特）在个体中出现的概率。

概率向量更新

在每次迭代中，算法根据当前概率向量采样生成两个候选解。随后，利用目标函数对这两个候选解进行评价，并比较其适应度值。根据比较结果，概率向量会朝着更优解所对应的比特模式方向更新。该更新通常通过简单的频率调整规则实现，即对优胜解中的对应比特概率进行增加，同时对较差解中的对应比特概率进行减少，步长由预设的小幅更新量控制。

收敛与终止

生成候选解、适应度评估以及概率向量更新的过程会不断重复，直至满足收敛条件或达到最大迭代次数。收敛通常可通过监测概率向量的熵来判断，因为熵能够反映当前种群模型的不确定性或多样性。随着算法不断推进，熵通常会逐步下降，这表明模型逐渐趋于集中，并朝某一特定解收敛。

流程

数据结构

• 概率向量（probability_vector）：概率向量，其中每个元素表示某一比特在个体中出现的概率。
• 最优解（best_solution）：当前搜索过程中找到的最优解。
• 最优适应度（best_fitness）：当前找到的最优解对应的适应度值。

参数

• 种群规模（population_size）：用于更新概率向量的虚拟种群规模。
• 最大迭代次数（max_iterations）：算法允许执行的最大迭代次数。
• 步长（step_size）：根据候选解比较结果更新概率向量时所采用的步长。

伪代码

1. 将 probability_vector 初始化为各元素均为 0.5。
2. 将 best_solution 和 best_fitness 初始化为 None。
3. 在达到 max_iterations 或检测到收敛之前，重复以下过程：
   1. 根据 probability_vector 采样生成两个候选解 solution1 和 solution2。
   2. 利用目标函数计算 solution1 和 solution2 的适应度值。
   3. 若 solution1 的适应度优于 solution2：
      1. 按照 step_size，增加 solution1 中对应比特的概率，并减少 solution2 中对应比特的概率，从而更新 probability_vector。
   4. 否则：
      1. 按照 step_size，增加 solution2 中对应比特的概率，并减少 solution1 中对应比特的概率，从而更新 probability_vector。
   5. 若当前较优解的适应度优于 best_fitness：
      1. 用该较优解及其适应度值更新 best_solution 和 best_fitness。
4. 返回 best_solution 和 best_fitness。

注意事项

优点

• 内存开销低：与传统遗传算法相比，紧凑遗传算法只需维护一个概率向量，而无需显式保存整个种群，因此具有更高的内存效率。
• 收敛速度较快：由于搜索直接围绕种群概率模型展开，算法能够更快集中到搜索空间中的潜在优良区域。
• 搜索具有自适应性：概率向量的更新机制能够根据目标函数反馈动态调整搜索方向，从而实现更有针对性的探索。

缺点

• 多样性有限：随着算法逐步收敛，虚拟种群的多样性会不断下降，这可能导致早熟收敛，并降低跳出局部最优的能力。
• 对步长敏感：算法性能对步长参数较为敏感。不合适的步长可能造成收敛过慢，或过早陷入次优区域。
• 缺乏显式种群：由于没有显式种群，算法在维持和利用多样解方面可能存在不足，尤其是在多峰优化问题中更为明显。

启发式建议

种群规模

• 虚拟种群规模应结合问题复杂度以及探索与开发之间的平衡需求进行设定。
• 较大的种群规模有助于保持多样性并增强探索能力，但可能降低收敛速度。
• 较小的种群规模能够加快收敛，但也可能增加早熟收敛的风险。

步长

• 步长决定了在比较候选解后，概率向量每次更新的幅度。
• 较大的步长有助于加快收敛，但可能使算法越过最优区域。
• 较小的步长能够实现更平滑、更精细的搜索，但可能导致收敛速度变慢。
• 在实际应用中，可根据算法搜索进程动态调整步长，例如在接近收敛时逐步减小步长。

收敛判据

• 可通过监测概率向量的熵来判断是否收敛，因为熵反映了虚拟种群的不确定性或多样性水平。
• 可以设定一个熵阈值，当熵低于该阈值时认为算法已经收敛。
• 此外，也可设置最大迭代次数，以避免算法在未收敛时无限运行。

初始化

• 概率向量通常初始化为各元素均为 0.5，表示搜索起点不偏向任一取值。
• 在某些情况下，若已知问题的先验知识，也可将概率向量初始化为更具信息性的取值，以引导搜索更快进入潜在优良区域。

精英保留

• 紧凑遗传算法可以通过引入精英保留机制来始终保存当前找到的最优解。
• 具体做法是：每当搜索过程中发现更优解时，就及时更新最优解及其适应度值。
• 精英保留有助于防止优质解在迭代过程中丢失，并保证算法始终保留迄今发现的最佳结果。