杂乱遗传算法（Messy GA）

Goat_Yang2026/3/21约 1870 字大约 6 分钟

杂乱遗传算法（Messy GA）

名称

杂乱遗传算法（Messy Genetic Algorithm, Messy GA）

策略

杂乱遗传算法旨在克服传统遗传算法在处理变长表示和非编码片段问题上的局限性。该算法引入了“杂乱染色体”的概念，即允许同时包含编码区与非编码区的变长字符串，从而在问题表示上具有更高的灵活性。

该算法通常分为两个阶段：原始阶段（primordial phase）与并置阶段（juxtapositional phase）。在原始阶段中，首先生成一个规模较大的杂乱染色体种群，其中包含多样化的构件块（building blocks）或部分解。随后，依据适应度对这些杂乱染色体进行选择，并选取其中表现较优的个体用于繁殖。

在并置阶段中，所选杂乱染色体会接受切割（cut）和拼接（splice）等遗传算子的作用，以实现不同个体之间构件块的重组。其中，切割算子会随机将一条杂乱染色体划分为两个部分，而拼接算子则将两条杂乱染色体连接起来以形成新的子代。该重组与选择过程会重复进行，直到达到预设代数，或找到令人满意的解为止。

杂乱遗传算法还引入了维持种群多样性和防止早熟收敛的机制。通过允许变长表示以及非编码区域的存在，算法能够考察更广泛的潜在解空间，而这些非编码区域在某些情况下也可能对个体整体适应度产生贡献。

过程

数据结构：

种群：由若干杂乱染色体构成的集合，表示潜在候选解。
杂乱染色体：一种变长字符串，其中可同时包含编码区与非编码区。

参数：

种群规模：种群中杂乱染色体的数量。
原始阶段长度：原始阶段持续的代数。
并置阶段长度：并置阶段持续的代数。
切割概率：对杂乱染色体应用切割算子的概率。
拼接概率：对两条杂乱染色体应用拼接算子的概率。

步骤：

初始化：
1. 生成初始种群，其中每条杂乱染色体具有可变长度，并由随机组合的编码区和非编码区构成。
2. 根据具体问题的目标函数评估每条杂乱染色体的适应度。
原始阶段：
1. 按照设定的原始阶段代数重复以下过程：
  1. 根据适应度值，从种群中选取一部分适应度较高的杂乱染色体。
  2. 按照切割概率，对选中的杂乱染色体应用切割算子。
  3. 按照拼接概率，对选中的杂乱染色体应用拼接算子。
  4. 评估新生成杂乱染色体的适应度。
  5. 用新生成的个体替换种群中适应度最低的杂乱染色体。
并置阶段：
1. 按照设定的并置阶段代数重复以下过程：
  1. 根据适应度值，从种群中选取一部分适应度较高的杂乱染色体。
  2. 按照切割概率，对选中的杂乱染色体应用切割算子。
  3. 按照拼接概率，对选中的杂乱染色体应用拼接算子。
  4. 评估新生成杂乱染色体的适应度。
  5. 用新生成的个体替换种群中适应度最低的杂乱染色体。
终止：
1. 检查是否满足终止条件（如达到最大代数，或找到满意解）。
2. 若未满足终止条件，则返回步骤 3。
3. 若满足终止条件，则返回当前找到的最优杂乱染色体作为最终解。