精英遗传算法（EGA）
2026/3/21约 1634 字大约 5 分钟
精英遗传算法（EGA）
名称
精英遗传算法（Elitist Genetic Algorithm, Elitist GA, Elitism GA）
分类
精英遗传算法是遗传算法的一种变体，隶属于演化计算领域；演化计算是计算智能和生物启发计算的一个分支。该算法与稳态遗传算法、代际遗传算法等其他遗传算法变体具有密切联系。
- 计算智能
- 生物启发计算
- 演化计算
- 演化算法
- 遗传算法
- 精英遗传算法
- 遗传算法
- 演化算法
- 演化计算
- 生物启发计算
策略
精英遗传算法遵循标准遗传算法的基本框架，并在此基础上引入精英保留机制。该机制确保每一代中的最优个体能够不经过交叉、变异等遗传操作，直接传递到下一代种群中。
算法首先初始化一个候选解种群，这些候选解通常表示为二进制串或实值向量。随后，利用预定义的适应度函数对每个个体进行评估，以衡量该解在特定问题背景下的优劣程度。
在每一代迭代中，算法通过选择算子选取父代个体用于繁殖。常用的选择方法包括锦标赛选择、轮盘赌选择和基于排序的选择。被选中的父代随后执行交叉操作，通过父代之间的遗传信息交换生成子代。之后，再对子代施加变异操作，以引入随机扰动，从而增强对搜索空间的探索能力。
精英保留机制用于保存当前代中的最优个体。这些精英个体会被直接复制到下一代，从而保证高质量解不会在演化过程中因遗传操作而丢失。新一代种群中的其余个体位置，则由通过交叉和变异产生的子代填充。
上述选择、交叉、变异与精英保留过程不断重复，直到达到预设代数上限或找到满意解为止。精英遗传算法在利用当前已发现优质解与探索搜索空间中新区域之间保持平衡，从而逐步收敛到高质量解。
过程
数据结构
- 种群：由个体构成的数组，每个个体表示一个候选解。
- 个体：用于编码候选解的二进制串或实值向量。
- 适应度：表示个体解质量的标量值。
参数
- 种群规模：种群中个体的数量。
- 交叉概率：对一对父代执行交叉操作的概率。
- 变异概率：对个体执行变异操作的概率。
- 精英规模：每一代中需要保留的精英个体数量。
- 最大迭代代数：算法运行的最大代数。
伪代码
- 随机生成个体，初始化种群。
- 评估种群中每个个体的适应度。
- 当终止条件未满足时（例如达到最大迭代代数）：
- 使用选择算子选择父代个体（例如锦标赛选择）。
- 对选出的父代执行交叉操作，生成子代。
- 对子代执行变异操作。
- 评估子代的适应度。
- 从当前种群中选出精英个体。
- 将精英个体与子代合并，构造新种群。
- 用新种群替换当前种群。
- 返回搜索过程中找到的最优个体。
注意事项
优点
- 精英保留能够保存当前已找到的最优解，避免高质量个体丢失。
- 精英机制能够加快算法收敛，因为最优解总能被传播到下一代。
- 在解的质量和收敛速度方面，精英遗传算法通常优于标准遗传算法。
缺点
- 当精英规模设置过大时，精英遗传算法更容易发生早熟收敛。
- 精英机制带来的额外选择压力会降低种群多样性，进而可能削弱搜索空间的探索能力。
- 为维护和更新精英个体，算法可能需要额外的计算资源。
启发式建议
种群规模
- 种群规模应足够大，以维持种群多样性并支持对搜索空间的有效探索。
- 常见经验做法是根据问题复杂度，将种群规模设置在 50 到 200 个个体之间。
- 若种群规模过小，则由于多样性不足，算法可能难以找到较优解。
- 若种群规模过大，则算法可能收敛缓慢，并消耗更多计算资源。
交叉概率
- 交叉概率决定了对一对父代执行交叉操作的可能性。
- 通常建议采用较高的交叉概率（如 0.8 至 0.95），以促进遗传信息交换和新子代生成。
- 若交叉概率过低，则算法会更多依赖变异来产生新解，从而可能降低收敛效率。
变异概率
- 变异概率决定了对个体执行变异操作的可能性。
- 较低的变异概率（如 0.01 至 0.1）通常已足以引入小幅扰动并维持种群多样性。
- 若变异概率过高，则算法可能表现得过于随机，难以稳定收敛到优质解。
- 变异概率应结合问题规模及期望的探索程度进行调整。
精英规模
- 精英规模决定了每一代中被保留的最优个体数量。
- 较小的精英规模（如 1 到 5）通常已足以保存当前发现的优良解。
- 若精英规模过大，则算法可能过早收敛，并削弱对新区域的探索能力。
- 精英规模的设置应在保留高质量解与维持种群多样性之间取得平衡。
终止准则
- 最大迭代代数是常用的终止准则，可确保算法在预设迭代次数后停止。
- 其他终止准则还包括达到目标适应度值、最优适应度在连续若干代内无明显改进，或达到时间上限等。
- 终止准则的具体选择应结合问题需求与可用计算资源进行确定。
- 设定合理的终止准则有助于避免不必要的计算，同时保证算法有足够机会收敛到较优解。