微分进化

2025年6月18日 | 阅读11分钟

引言

差分进化算法是一种启发式算法，旨在解决连续变量的非线性、不可微函数的全局优化问题。

与其他进化计算领域算法类似，差分进化算法在许多方面与遗传算法和进化策略等方法有共同之处。它首先创建一个初始的可能解集；这些解通过变异和选择进行演化。该算法通过最小化目标函数值来保留最优的候选解。

差分进化算法的主要优势之一是能够解决具有非线性、不可微和/或多变量目标函数的problem。此外，它使用的控制参数较少，易于实现，并且比许多其他广泛使用的优化方法更有用。

差分进化

DE是一种迭代随机优化技术，用于在连续值参数的非线性、不可微空间中搜索全局最优解。

为了使算法实用，它应该满足以下标准：

获得一个可以处理不可微、非线性以及任何类型成本函数的优化解决方案。
广泛支持并行化，以处理计算密集型函数。
易于用户交互，具有有限且易于理解的控制参数。
在连续的独立模拟中，提供与全局最小值相当的收敛水平。
DE在满足所有这些需求方面表现得更为成功，使其成为连续参数空间中稳健且全能有效的进化优化器。

算法概述

DE以实数（也称为基因组或染色体）的决策向量群体开始，这些向量是随机生成的。这些向量是多参数矢量化优化问题的解的候选。该过程涉及三个主要操作：

变异： 两个随机选择的种群向量之间的加权差形成新向量的基础，该新向量通过添加第三个向量获得。
交叉： 将一个独立的变异向量与目标向量集成，以增加变异性，并将其定义为试探向量。
选择： 当试探向量的目标函数值较低时，试探向量会替换目标向量，以便将更适应的字符串实例传递到下一代。

这些操作会 successive 执行，直到达到停止条件，例如固定的评估次数。

变异策略

DE中的变异策略遵循DE/x/y/z的表示法

x：要变异的向量，例如，rand表示随机，best表示成本最低的向量，在此处适用。
y：在变异中使用差分向量的情况。
z：交叉的类型，例如，binomial bin。

例子包括

DE/rand/1/bin：在随机向量中，它使用一个差分向量和二项式交叉。
DE/best/2/bin：使用两个差分向量和二项式交叉的更好向量，适用于增加预选大种群的多样性。

参数和实用性

DE只需要三个关键参数：

种群大小 (NP)

另一个参数 F，一个范围在 [0, 2] 之间的缩放因子，用于调节变异过程中的差分变化。

交叉率 (CR) 位于 [0, 1] 区间内，并根据经验证据选择。

因此，DE既可行又易于应用。随着时间的推移，出现了几种DE变体，详见《差分进化近期进展：最新调查》（2016）等研究。

有了这些理解，从头开始实现DE的任务就变得相当容易了。

差分进化算法的原始方法

DE算法的大部分研究都围绕着创建候选解决方案的种群。这些解决方案表示为随机向量，我们从 [0, 1) 区间上的均匀分布中提取这些向量。

初始化步骤

应使用rand()函数在矩阵内生成随机值。
如下所示，这些随机值现在必须进行缩放，以便落在每个变量定义的范围内，由下界和上界确定。
边界应以二维数组的形式传递，该数组表示每个输入变量的下界和上界。

缩放功能的改进是为了帮助候选解决方案稍微类似于定义的problem空间，以便DE算法能够有效地搜索解决方案空间。

将变异投入差分进化算法的运行

对于DE算法初始化，会根据定义的边界来制定候选解决方案。第一个种群通过适应度函数进行评估，然后进行修改以获得最佳解决方案。

种群和目标函数初始化

pop = bounds[:, 0] + (rand(pop_size, len(bounds)) * (bounds[:, 1] - bounds[:, 0]))
def obj(x):
    return 0
bounds = asarray([[-5.0, 5.0]])
obj_all = [obj(ind) for ind in pop]

Iterative Process:

This algorithm involves a parody of m iterations, the population is then updated by mutation and crossover.
for i in range(iter):
    for j in range(pop_size):
        candidates = [candidate for candidate in range(pop_size) if candidate != j]
        a, b, c = pop[choice(candidates, 3, replace=False)]
        mutated_vector = a + F * (b – c)

关键点

变异过程通过将一个当前解与其两个随机选择的解向量（b和c）之间的加权差相加，并将其与第三个任意解向量（a）相加来扰乱当前解。
参数 F 在调节这些波动大小方面起着核心作用，通常在 [0, 2] 区间内变化。
这种变异保证了种群内的变化，这对于充分搜索解空间至关重要。

接下来是交叉和选择阶段，以进一步提高候选解决方案的质量。

差分进化算法优化

以下是差分进化（DE）算法的分步实现：

突变

变异步骤通过对两个随机选择的种群基因型和一个第三基因型之间的加权向量差生成一个变异向量。

代码片段

def mutation(x, F):
    return x[0] + F * (x[1] - x[2])
mutated = mutation([a, b, c], F)

边界检查

为了限制变异因子在其超出规定范围时，请使用剪切变异向量值的方法。

代码片段

def check_bounds(mutated, bounds):
    return [clip(mutated[i], bounds[i, 0], bounds[i, 1]) for i in range(len(bounds))]
mutated = check_bounds(mutated, bounds)

交叉

通过将变异向量与目标向量进行交叉操作，根据均匀分布的随机变量和交叉率创建一个试探向量。

代码片段

def crossover(mutated, target, dims, cr):
    p = rand(dims)
    trial = [mutated[i] if p[i] < cr else target[i] for i in range(dims)]
    return trial
trial = crossover(mutated, pop[j], len(bounds), cr)

选拔

取试探向量并减去目标向量，保留目标函数值较低的那个。

代码片段

obj_target = obj(pop[j])
obj_trial = obj(trial)
if obj_trial < obj_target:
    pop[j] = trial
    obj_all[j] = obj_trial

整合

以下函数将DE算法的所有步骤结合在一起：

该函数包含了整个DE过程，并返回最佳解决方案以及问题相关的适应度。

代码片段

def differential_evolution(obj, bounds, pop_size, iter, F, cr):
    pop = bounds[:, 0] + (rand(pop_size, len(bounds)) * (bounds[:, 1] - bounds[:, 0]))
    obj_all = [obj(ind) for ind in pop]
    for _ in range(iter):
        for j in range(pop_size):
            candidates = [candidate for candidate in range(pop_size) if candidate != j]
            a, b, c = pop[choice(candidates, 3, replace=False)]
            mutated = mutation([a, b, c], F)
            mutated = check_bounds(mutated, bounds)
            trial = crossover(mutated, pop[j], len(bounds), cr)
            obj_target = obj(pop[j])
            obj_trial = obj(trial)
            if obj_trial < obj_target:
                pop[j] = trial
                obj_all[j] = obj_trial
    best_idx = argmin(obj_all)
    return pop[best_idx], obj_all[best_idx]

球函数上的差分进化算法

此处提供的实现使用DE算法来解决球函数，这是一个基本的优化测试函数。以下是过程的细分：

球函数

目标函数定义为：f(x) = x1^2 + x2^2

它在点 (0,0) 处有一个唯一的全局优化解，对应的函数值为0。

差分进化步骤

初始化

在参数空间（代表候选解的菜单）内选择随机种群。[-5,5]。

突变

使用以下公式生成变异向量：
mutated=a+F⋅(b−c)

边界检查

由于变异更新的新向量可能会违反边界，请确保所有向量都已裁剪到边界内。

交叉

基于交叉率 cr，由变异向量与目标向量融合而成的试探向量。

选拔

为了提交，当试探向量比目标向量具有更好的（较低的）目标函数值时，用试探向量替换目标向量。

迭代优化

将此过程执行固定次数，并记录遇到的最佳解决方案。

代码

from numpy.random import rand
from numpy.random import choice
from numpy import asarray
from numpy import clip
from numpy import argmin
from numpy import min
from numpy import around
def obj(x):
    return x[0]**2.0 + x[1]**2.0
def mutation(x, F):
    return x[0] + F * (x[1] - x[2])
def check_bounds(mutated, bounds):
    mutated_bound = [clip(mutated[i], bounds[i, 0], bounds[i, 1]) for i in range(len(bounds))]
    return mutated_bound
def crossover(mutated, target, dims, cr):
    p = rand(dims)
    trial = [mutated[i] if p[i] < cr else target[i] for i in range(dims)]
    return trial
 
def differential_evolution(pop_size, bounds, iter, F, cr):
    pop = bounds[:, 0] + (rand(pop_size, len(bounds)) * (bounds[:, 1] - bounds[:, 0]))
    obj_all = [obj(ind) for ind in pop]
    best_vector = pop[argmin(obj_all)]
    best_obj = min(obj_all)
    prev_obj = best_obj
    for i in range(iter):
        for j in range(pop_size):
            candidates = [candidate for candidate in range(pop_size) if candidate != j]
            a, b, c = pop[choice(candidates, 3, replace=False)]
            mutated = mutation([a, b, c], F)
            mutated = check_bounds(mutated, bounds)
            trial = crossover(mutated, pop[j], len(bounds), cr)
            obj_target = obj(pop[j])
            obj_trial = obj(trial)
            if obj_trial < obj_target:
                pop[j] = trial
                obj_all[j] = obj_trial
        best_obj = min(obj_all)
        if best_obj < prev_obj:
            best_vector = pop[argmin(obj_all)]
            prev_obj = best_obj
            print('Iteration: %d f([%s]) = %.5f' % (i, around(best_vector, decimals=5), best_obj))
    return [best_vector, best_obj]
 
 
pop_size = 10
bounds = asarray([(-5.0, 5.0), (-5.0, 5.0)])
iter = 100
F = 0.5
cr = 0.7
solution = differential_evolution(pop_size, bounds, iter, F, cr)
print('\nSolution: f([%s]) = %.5f' % (around(solution[0], decimals=5), solution[1]))

输出

Iteration: 0 f([[1.00344 0.17044]]) = 1.03594
Iteration: 1 f([[-0.42909  0.64404]]) = 0.59890
Iteration: 3 f([[0.64313 0.16389]]) = 0.44047
Iteration: 5 f([[ 0.11072 -0.18159]]) = 0.04523
Iteration: 9 f([[ 0.11413 -0.05922]]) = 0.01653
Iteration: 10 f([[0.06599 0.00535]]) = 0.00438
Iteration: 12 f([[0.04743 0.03815]]) = 0.00370
Iteration: 13 f([[0.02509 0.00535]]) = 0.00066
Iteration: 18 f([[ 0.01202 -0.00349]]) = 0.00016
Iteration: 21 f([[-0.00661  0.00765]]) = 0.00010
Iteration: 23 f([[0.00323 0.00459]]) = 0.00003
Iteration: 24 f([[-0.00173  0.00267]]) = 0.00001
Iteration: 26 f([[0.00201 0.00231]]) = 0.00001
Iteration: 27 f([[-0.00012 -0.00155]]) = 0.00000
Iteration: 29 f([[0.00095 0.00079]]) = 0.00000
Iteration: 30 f([[-1.2e-04  5.0e-05]]) = 0.00000
Iteration: 39 f([[1.e-05 1.e-05]]) = 0.00000
Iteration: 44 f([[-0.e+00  1.e-05]]) = 0.00000
Iteration: 48 f([[ 0. -0.]]) = 0.00000
Iteration: 53 f([[-0. -0.]]) = 0.00000
Iteration: 56 f([[0. 0.]]) = 0.00000
Iteration: 59 f([[-0.  0.]]) = 0.00000
Iteration: 63 f([[-0.  0.]]) = 0.00000
Iteration: 65 f([[ 0. -0.]]) = 0.00000
Iteration: 66 f([[ 0. -0.]]) = 0.00000
Iteration: 68 f([[0. 0.]]) = 0.00000
Iteration: 69 f([[ 0. -0.]]) = 0.00000
Iteration: 71 f([[0. 0.]]) = 0.00000
Iteration: 72 f([[-0. -0.]]) = 0.00000
Iteration: 76 f([[ 0. -0.]]) = 0.00000
Iteration: 78 f([[ 0. -0.]]) = 0.00000
Iteration: 79 f([[-0. -0.]]) = 0.00000
Iteration: 80 f([[-0. -0.]]) = 0.00000
Iteration: 83 f([[-0.  0.]]) = 0.00000
Iteration: 84 f([[ 0. -0.]]) = 0.00000
Iteration: 86 f([[-0.  0.]]) = 0.00000
Iteration: 87 f([[0. 0.]]) = 0.00000
Iteration: 90 f([[0. 0.]]) = 0.00000
Iteration: 92 f([[ 0. -0.]]) = 0.00000
Iteration: 93 f([[-0.  0.]]) = 0.00000
Iteration: 98 f([[-0.  0.]]) = 0.00000

Solution: f([[-0.  0.]]) = 0.00000

二维球目标函数的差分进化搜索

代码

from numpy.random import rand
from numpy.random import choice
from numpy import asarray
from numpy import clip
from numpy import argmin
from numpy import min
from numpy import around
from matplotlib import pyplot

def obj(x):
    return x[0]**2.0 + x[1]**2.0

def mutation(x, F):
    return x[0] + F * (x[1] - x[2])
 
def check_bounds(mutated, bounds):
    mutated_bound = [clip(mutated[i], bounds[i, 0], bounds[i, 1]) for i in range(len(bounds))]
    return mutated_bound

def crossover(mutated, target, dims, cr):
    p = rand(dims)
    trial = [mutated[i] if p[i] < cr else target[i] for i in range(dims)]
    return trial
 
 
def differential_evolution(pop_size, bounds, iter, F, cr):
    pop = bounds[:, 0] + (rand(pop_size, len(bounds)) * (bounds[:, 1] - bounds[:, 0]))
    obj_all = [obj(ind) for ind in pop]
    best_vector = pop[argmin(obj_all)]
    best_obj = min(obj_all)
    prev_obj = best_obj
    obj_iter = list()
    for i in range(iter):
        for j in range(pop_size):
            candidates = [candidate for candidate in range(pop_size) if candidate != j]
            a, b, c = pop[choice(candidates, 3, replace=False)]
            mutated = mutation([a, b, c], F)
            mutated = check_bounds(mutated, bounds)
            trial = crossover(mutated, pop[j], len(bounds), cr)
            obj_target = obj(pop[j])
            obj_trial = obj(trial)
            # perform selection
            if obj_trial < obj_target:
                pop[j] = trial
                obj_all[j] = obj_trial
        best_obj = min(obj_all)
        if best_obj < prev_obj:
            best_vector = pop[argmin(obj_all)]
            prev_obj = best_obj
            obj_iter.append(best_obj)
            print('Iteration: %d f([%s]) = %.5f' % (i, around(best_vector, decimals=5), best_obj))
    return [best_vector, best_obj, obj_iter]

pop_size = 10
bounds = asarray([(-5.0, 5.0), (-5.0, 5.0)])
iter = 100
F = 0.5
cr = 0.7
solution = differential_evolution(pop_size, bounds, iter, F, cr)
print('\nSolution: f([%s]) = %.5f' % (around(solution[0], decimals=5), solution[1]))
pyplot.plot(solution[2], '.-')
pyplot.xlabel('Improvement Number')
pyplot.ylabel('Evaluation f(x)')
pyplot.show()

输出

 
Iteration: 1 f([[-0.22544 -0.38483]]) = 0.19892
Iteration: 5 f([[-0.13006  0.12466]]) = 0.03246
Iteration: 10 f([[-0.03427  0.08677]]) = 0.00870
Iteration: 13 f([[-0.00201 -0.01124]]) = 0.00013
Iteration: 17 f([[-0.0023  -0.00526]]) = 0.00003
Iteration: 21 f([[0.00123 0.00462]]) = 0.00002
Iteration: 22 f([[ 1.00e-05 -3.49e-03]]) = 0.00001
Iteration: 24 f([[ 0.00181 -0.00273]]) = 0.00001
Iteration: 25 f([[0.00028 0.00132]]) = 0.00000
Iteration: 26 f([[ 0.00028 -0.00095]]) = 0.00000
Iteration: 27 f([[ 1.e-05 -4.e-04]]) = 0.00000
Iteration: 28 f([[ 0.00011 -0.00015]]) = 0.00000
Iteration: 29 f([[1.e-05 4.e-05]]) = 0.00000
Iteration: 36 f([[2.e-05 3.e-05]]) = 0.00000
Iteration: 38 f([[-2.e-05 -1.e-05]]) = 0.00000
Iteration: 41 f([[0. 0.]]) = 0.00000
Iteration: 42 f([[-0.  0.]]) = 0.00000
Iteration: 43 f([[-0.  0.]]) = 0.00000
Iteration: 48 f([[-0.  0.]]) = 0.00000
Iteration: 52 f([[-0.  0.]]) = 0.00000
Iteration: 54 f([[ 0. -0.]]) = 0.00000
Iteration: 57 f([[0. 0.]]) = 0.00000
Iteration: 58 f([[0. 0.]]) = 0.00000
Iteration: 59 f([[-0.  0.]]) = 0.00000
Iteration: 60 f([[ 0. -0.]]) = 0.00000
Iteration: 63 f([[0. 0.]]) = 0.00000
Iteration: 66 f([[ 0. -0.]]) = 0.00000
Iteration: 67 f([[-0.  0.]]) = 0.00000
Iteration: 70 f([[ 0. -0.]]) = 0.00000
Iteration: 75 f([[ 0. -0.]]) = 0.00000
Iteration: 76 f([[ 0. -0.]]) = 0.00000
Iteration: 81 f([[-0. -0.]]) = 0.00000
Iteration: 82 f([[0. 0.]]) = 0.00000
Iteration: 83 f([[0. 0.]]) = 0.00000
Iteration: 85 f([[-0.  0.]]) = 0.00000
Iteration: 86 f([[-0. -0.]]) = 0.00000
Iteration: 88 f([[-0. -0.]]) = 0.00000
Iteration: 98 f([[ 0. -0.]]) = 0.00000

Solution: f([[ 0. -0.]]) = 0.00000

结论

DE是非线性/不可微和多模态目标函数优化的一种有效方法。它易于理解，不复杂，控制参数少，且不需要太多控制。DE具有一个初始的解向量种群，并在分步优化技术中使用变异、交叉和选择。

变异为种群带来变化；交叉允许在解空间中进行搜索；选择只允许最优解向前传递。DE易于实现，可针对各种问题进行优化，并允许并行解决方案以快速计算。由于种群大小、缩放因子、交叉率等参数，该方法收敛于全局最优点/解决方案，在理论和实践问题中都表现出色。

下一主题机器学习的重要性

微分进化

引言

差分进化

算法概述

差分进化算法的原始方法

初始化步骤

将变异投入差分进化算法的运行

差分进化算法优化

突变

球函数上的差分进化算法

二维球目标函数的差分进化搜索

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

机器学习

监督式学习

分类

杂项

相关教程

面试题

微分进化

引言

差分进化

算法概述

差分进化算法的原始方法

初始化步骤

将变异投入差分进化算法的运行

差分进化算法优化

突变

球函数上的差分进化算法

二维球目标函数的差分进化搜索

结论

相关帖子

Light Gradient Boosted Machine (LightGBM)

交叉验证

文本摘要简介

使用 LangChain 构建聊天机器人 Web 应用

什么是序数数据？

什么是机器学习中的 Softmax 激活函数

时间序列预测的自回归 (AR) 模型

精确率-召回率曲线 (PR 曲线) – ML

LDA 在机器学习中的应用

在 Python 中创建 AdaBoost 回归模型

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器