交叉熵方法（CEM）

名称

交叉熵方法（Cross-Entropy Method, CEM）

分类

查看分类思维导图

交叉熵方法是一种随机优化技术，属于计算智能与生物启发计算的范畴。它与优化领域关系密切，并与进化算法、分布估计算法等元启发式方法具有相似性。

• 计算智能
  • 生物启发计算
    • 优化
      • 元启发式算法
        • 随机优化
          • 交叉熵方法

策略

交叉熵方法是一种迭代式优化算法，其核心思想是通过最小化目标分布与参数化分布之间的交叉熵，逐步逼近问题的最优解。其中，目标分布代表最优解所在的理想分布，而参数化分布则用于生成候选解。

采样与评估

在每一轮迭代中，CEM 首先从参数化分布中采样生成一批候选解。随后，利用适应度函数或目标函数对这些候选解进行评估，以衡量各解对原问题的求解效果。

精英选择

在完成候选解评估后，CEM 从中选取一部分表现最优的解，称为精英解（elite solutions）。这些精英解将用于更新参数化分布的参数，使其逐步向目标分布靠近。

分布更新

参数化分布的参数依据精英解进行更新。通常，这一过程通过最小化精英解经验分布与参数化分布之间的交叉熵来实现。更新后的分布将作为下一轮迭代中生成候选解的基础。

上述采样、评估、精英选择与分布更新过程不断重复，直至满足停止条件，例如达到最大迭代次数或找到足够满意的解。

流程

1. 初始化参数化分布的参数。
2. 重复以下过程，直至满足停止条件：
   1. 从参数化分布中采样生成一批候选解。
   2. 利用适应度函数对候选解进行评估。
   3. 根据适应度值选出精英解。
   4. 通过最小化精英解经验分布与参数化分布之间的交叉熵，更新参数化分布的参数。
3. 返回搜索过程中找到的最优解。

数据结构

• 候选解：通过参数化分布采样得到的一批潜在可行解。
• 精英解：依据适应度值从候选解中筛选出的表现最优子集。
• 参数化分布：用于生成候选解的概率分布；在连续优化问题中通常采用高斯分布，在离散优化问题中通常采用伯努利分布。

参数

• 批量大小：每次迭代中生成的候选解数量。
• 精英比例：被选为精英解的候选解所占比例。
• 学习率：用于更新参数化分布参数的步长。
• 停止准则：用于终止算法的条件，例如最大迭代次数或适应度阈值。

注意事项

优点

• 对高维搜索空间中的复杂优化问题具有较强求解能力。
• 不依赖梯度信息，因此适用于黑盒优化问题。
• 既可处理连续优化问题，也可处理离散优化问题。

缺点

• 算法性能较大程度上依赖于参数化分布形式及其初始参数的选择。
• 可能需要较多目标函数评估次数，从而带来较高计算开销。
• 精英比例和学习率等参数通常需要精细调节，才能获得较优性能。

启发式建议

参数化分布的选择

• 对于连续优化问题，宜采用具有自适应均值和方差的高斯分布。
• 对于离散优化问题，宜采用具有自适应概率参数的伯努利分布。

批量大小与精英比例

• 批量大小应在探索能力与计算开销之间取得平衡。较大的批量规模有助于增强探索，但会增加计算成本。
• 精英比例通常可设置在 0.1 至 0.2 之间，以在聚焦优良解的同时维持一定多样性。

学习率

• 学习率应使算法在前期具有足够的探索能力，在后期具备较强的开发能力。
• 可根据优化过程的收敛情况动态调整学习率，例如随着算法逐渐收敛而适当减小学习率。

停止准则

• 应结合计算预算和问题复杂度设定最大迭代次数。
• 可监测固定若干轮迭代内最优适应度值的改进幅度；若改进低于某一阈值，则可提前停止。

问题相关考虑

• 可将领域知识融入参数化分布的初始化以及适应度函数的设计中。
• 可结合具体问题的约束条件与边界处理机制，以保证生成解的可行性。