进化规划（EP）

名称

进化规划（Evolutionary Programming, EP）

分类

查看分类思维导图

进化规划是一种受生物学启发的优化技术，属于更广义的演化计算范畴，而演化计算又是计算智能的一个子领域。它与遗传算法和进化策略等其他演化算法密切相关。

• 计算智能
  • 生物启发计算
    • 演化计算
      • 进化规划

策略

进化规划是一种基于种群的优化技术，其思想来源于生物进化原理。该算法维护一个候选解种群，其中每个个体都表示待求问题的一个潜在解。通过变异和选择的迭代过程，这些候选解在连续世代中不断进化，以逐步提升其适应度或解的质量。

表示方式

在进化规划中，每个候选解通常表示为一个定长实值向量，或表示该解的一组参数。具体采用何种表示形式，取决于所求解问题的性质。

变异

进化规划的主要变异算子是变异操作。在每一代中，每个候选解都会经历变异过程，即按照预先设定的变异策略，对其参数进行小幅随机扰动。该变异策略旨在向解中引入细微的随机变化，从而实现对搜索空间的探索。

评估与选择

在变异阶段之后，使用适应度函数对每个候选解进行评估，以衡量其相对于问题目标的质量或性能。适应度函数为每个解赋予一个适应度值，用以表征其相对优劣。

随后，根据适应度值执行选择过程，以决定哪些候选解能够存活到下一代。选择机制通常倾向于保留适应度更高的解，从而促进性能更优个体的生存与延续。

迭代

变异、评估与选择的过程会重复执行，直到达到预设的最大代数或满足终止条件。随着进化代数的推进，种群通常会逐步演化，并向更优解收敛。

过程

1. 初始化种群：
   1. 确定种群规模以及候选解的表示方式。
   2. 对种群中的每个候选解进行随机初始化。
2. 评估初始种群：
   1. 对每个候选解，利用适应度函数计算其适应度值。
3. 重复以下过程，直到达到指定代数或满足终止条件：
   1. 变异：
      1. 对种群中的每个候选解：
         1. 应用变异策略生成一个新的子代解。
         2. 评估该子代解的适应度。
   2. 选择：
      1. 根据适应度值，从当前种群及其子代中选出存活个体。
      2. 以选出的个体替换当前种群，形成新一代种群。
4. 返回进化过程中找到的最优解。

数据结构

• 种群：由候选解构成的数组或列表。
• 候选解：一个定长实值向量，或一组表示潜在解的参数。
• 适应度值：表示候选解质量或性能的标量值。

参数

• 种群规模：种群中候选解的数量。
• 进化代数：允许执行的最大迭代次数或代数。
• 变异策略：用于对候选解进行变异的方法，例如高斯变异或柯西变异。
• 选择机制：用于选择存活个体的策略，例如锦标赛选择或截断选择。

注意事项

优点

• 简单性：与其他演化算法相比，进化规划的实现相对简单直观。
• 灵活性：进化规划易于适配不同问题领域，能够处理连续优化问题和离散优化问题。
• 鲁棒性：进化规划具有较强的跳出局部最优能力，能够较有效地探索搜索空间。

缺点

• 参数敏感性：进化规划的性能可能对变异策略及其相关参数的选择较为敏感。
• 收敛速度：与某些其他优化算法相比，进化规划的收敛速度可能较慢，尤其是在高维问题中。
• 缺乏交叉算子：与遗传算法不同，进化规划通常不使用交叉操作，这可能限制其对搜索空间的探索能力。

启发式建议

种群规模

• 初始种群规模建议至少设置为问题维数的 10 倍。
• 对于更复杂或高维的问题，可适当增大种群规模，以保证足够的搜索能力。

变异策略

• 可优先采用高斯变异作为初始方案，因为它是一种常用且有效的变异策略。
• 可尝试不同的变异策略，例如柯西变异或自适应变异，以观察其是否能改善特定问题上的性能。
• 应根据问题的尺度和特性调整变异步长或方差。

选择机制

• 锦标赛选择因其简单且有效，是进化规划中较常用的选择方式。
• 对于大规模种群问题，可考虑采用截断选择，因为其计算效率可能更高。
• 可通过调整选择压力（如锦标赛规模）来平衡探索与开发。

终止准则

• 应结合可用计算资源和问题复杂度设置最大进化代数。
• 可监测历代最优适应度值的变化情况，若在一定代数内无显著提升，则可考虑提前终止。
• 还可结合具体问题需求设置附加终止条件，例如达到目标适应度值或达到最大允许运行时间。