跳至内容
博客
差分进化算法简介：优化算法的创新

差分进化算法简介：优化算法的创新

2019年2月23日

差分进化算法（Differential Evolution，简称 DE）由 Rainer Storn 和 Kenneth Price 于 1995 年提出。这是一种进化算法，通过不断迭代改进候选解以优化问题，针对给定的质量或适应度指标进行优化。它实现简单、需要调的参数少，在工程、机器学习和人工智能领域都有应用。

系列介绍

本系列介绍现代优化算法的发展、原理和应用，从理论基础讲到实际应用场景。

系列主要包括以下内容：

  1. 差分进化（DE）算法
  2. 马尔可夫链蒙特卡罗（MCMC）方法
  3. 自适应 MCMC 方法
  4. 差分进化自适应 Metropolis（DREAM）算法
  5. 其他重要的优化算法及其变体

本文作为系列的第一篇，介绍差分进化（DE）算法。后续几篇分析其他优化算法的理论基础、实现方法和应用范围。

演化计算的发展

演化计算的历史可以追溯到 20 世纪 50 年代。在这个领域的早期发展中，进化算法主要采用种群迭代的计算过程，并逐渐形成了三个主要的研究方向：进化规划算法、进化策略算法和遗传算法。

到了 20 世纪 90 年代，这三个独立发展的研究方向融合成为一个新的研究领域——演化计算。差分进化（DE）算法就出现在这个时期，由 R. Storn 和 K. V. Price 于 1995 年首次提出。

优化问题概述

在介绍 DE 算法之前，我们需要先了解优化问题的本质。简而言之，优化问题就是在给定的约束条件下，寻找使目标函数达到最优值的解。

举个简单的例子：假设我们要在 00 到 11 之间找到三个值，使得函数 ff 最小。这可以表示为：

min⁡ f(x1,x2,x3)=x1+x2+x3s.t.0≤xi<1 \min \ f(x_1, x_2, x_3) = x_1 + x_2 + x_3 \quad \text{s.t.} \quad 0 \leq x_i < 1

在这个问题中，(x1,x2,x3)(x_1, x_2, x_3) 组成一个向量，代表问题的一个可能解，而函数 ff 就是我们的目标函数。我们的任务是在所有可能的向量中，找到使 ff 取得最小值的那个向量。

DE 算法与优化问题

DE 算法是专门设计用于解决优化问题，尤其是全局优化问题的一种方法。它在处理优化问题时具有以下特点：

  1. 目标函数：在 DE 算法中，目标函数用于评估候选解的适应度，即衡量候选解在优化问题中的表现。
  2. 解空间：DE 算法在优化问题的解空间中进行搜索。初始种群的生成以及后续的变异、交叉、选择操作都在这个解空间中进行。
  3. 全局搜索：通过维持种群的多样性和采用全局搜索策略，DE 算法能够有效地跳出局部最优，寻找全局最优解。
  4. 适应性强：DE 算法适用于各种复杂的、多峰的、非线性的优化问题，表现出很强的适应性。

DE 算法的基本步骤

DE 算法的工作流程主要包括四个步骤：初始化、变异、交叉和选择。下面我们详细介绍每个步骤。

初始化

在初始化阶段，我们在 DD 维空间中生成 NPNP 个 DD 维实参向量，通常采用高斯分布或均匀分布进行采样。这里，NPNP 代表种群大小，DD 代表问题的维度。

一个 DD 维向量可表示为：

X⃗=[x1,x2,…,xD]T\vec{X} = \begin{bmatrix} x_1, x_2, \ldots, x_D \end{bmatrix}^T

初始化完成后，我们得到的初始种群为：

X=[X⃗1,X⃗2,…,X⃗NP]T\mathbf{X} = \begin{bmatrix} \vec{X}_1, \vec{X}_2, \ldots, \vec{X} _{NP} \end{bmatrix}^T

在迭代过程中，这些向量会不断更新。第 GG 代的第 ii 个向量可以表示为：

X⃗i,G=[x1,i,G,x2,i,G,…,xD,i,G]\vec{X} _{i, G} = \begin{bmatrix} x _{1, i, G}, x _{2, i, G}, \ldots, x _{D, i, G} \end{bmatrix}

变异

变异操作的目的是生成一个差分向量，记作 V⃗\vec{V}。对于种群中的每一个向量，我们都会生成一个对应的差分向量。

变异过程涉及两个关键概念：

  • 目标向量（target vector）：当前待更新的向量。
  • 差分向量（donor vector）：通过差分变异操作生成的向量。

变异操作的具体步骤如下：

  1. 按顺序选定一个目标向量。
  2. 随机选择另外三个不同的向量。
  3. 对其中两个向量作差，乘以缩放因子 FF，然后加到第三个向量上，得到差分向量。

第 ii 个向量的差分向量生成公式为：

V⃗i=X⃗r1i+F⋅(X⃗r2i−X⃗r3i)\vec{V}_{i} = \vec{X} _{r_1^i} + F \cdot \left( \vec{X} _{r_2^i} - \vec{X} _{r_3^i} \right)

其中，r1ir_1^i, r2ir_2^i, r3ir_3^i 是在 [1,NP][1, NP] 范围内随机选取的不同整数，且都不等于 ii。

交叉

交叉操作的目的是将差分向量与目标向量的元素进行交换，生成待定向量。常见的交叉策略有二项交叉和指数交叉。

二项交叉

  1. 随机选择一个维度 jrandj_{rand}，确保差分向量至少有一个维度被选中。
  2. 对每个维度 jj（从 11 到 DD），生成一个随机数 r∈[0,1]r \in [0,1]。如果 r≤CRr \leq CR 或 j=jrandj = j_{rand}，则选取差分向量的该维度值，否则选取目标向量的该维度值。

指数交叉

  1. 随机选择一个起始维度 jrandj_{rand}。
  2. 从起始维度开始，连续地将差分向量的维度值赋给新的候选解，直到随机数 r>CRr > CR 或已覆盖所有维度。

交叉示例

假设有一个五维问题（D=5D = 5），目标向量 X⃗i\vec{X}_i 和差分向量 V⃗i\vec{V}_i 如下：

X⃗i=[0.1,0.2,0.3,0.4,0.5]\vec{X}_i = [0.1, 0.2, 0.3, 0.4, 0.5]

V⃗i=[0.5,0.4,0.3,0.2,0.1]\vec{V}_i = [0.5, 0.4, 0.3, 0.2, 0.1]

以二项交叉为例，设 CR=0.8CR = 0.8，jrand=2j_{rand} = 2。假设生成的随机数序列为： r1=0.3r_1 = 0.3, r2=0.7r_2 = 0.7, r3=0.9r_3 = 0.9, r4=0.4r_4 = 0.4, r5=0.6r_5 = 0.6。

则生成的待定向量 U⃗i\vec{U}_i 为：

U⃗i=[0.5,0.4,0.3,0.2,0.1]\vec{U}_i = [0.5, 0.4, 0.3, 0.2, 0.1]

选择

选择操作决定将目标向量还是待定向量保留到下一代中，以保持种群大小不变。选择步骤如下：

  1. 计算目标向量 X⃗i\vec{X}_i 和待定向量 U⃗i\vec{U}_i 的适应度值，分别记为 f(X⃗i)f(\vec{X}_i) 和 f(U⃗i)f(\vec{U}_i)。
  2. 比较两个向量的适应度值。
  3. 如果 f(U⃗i)f(\vec{U}_i) 优于或等于 f(X⃗i)f(\vec{X}_i)，则用 U⃗i\vec{U}_i 替换 X⃗i\vec{X}_i；否则，保留 X⃗i\vec{X}_i。

选择步骤确保了 DE 算法在每一代中只保留表现更好的个体，目标函数值因此单调不增。

DE 算法的特点与优势

差分进化算法作为一种有效的随机实参优化技术，具有以下特点和优势：

  1. 简单易实现：DE 算法的基本原理简单明了，易于理解和实现。
  2. 参数少：相比其他进化算法，DE 需要调整的参数较少，主要是种群大小、缩放因子和交叉率。
  3. 全局搜索能力强：通过差分变异和交叉操作，DE 能够在解空间中进行有效的全局搜索。
  4. 适应性好：DE 算法适用于各种类型的优化问题，包括连续、离散、混合整数等。
  5. 并行化潜力：DE 的种群基础结构使其易于并行化，可以充分利用现代计算资源。

小结

差分进化通过随机采样和差分变异在解空间中搜索，不依赖对目标分布的特定假设。需要调的参数只有三个：种群大小、缩放因子和交叉率。

在此基础上衍生出了多种变体，如自适应 DE、多目标 DE 等。

下一步：MCMC 方法

下一篇讨论马尔可夫链蒙特卡罗（MCMC）方法：一类用于从复杂概率分布中采样的算法，包括 Metropolis-Hastings 和 Gibbs 采样，以及它们在贝叶斯推断中的应用。

DE 求的是最优解，MCMC 求的是整个分布。这个区别是后面 DREAM 把两者接起来的前提。

马尔可夫链蒙特卡罗方法概述：概率分布采样的经典方法