关键词
| 差分进化 | DE/rand/1 | DE/best/1 | 变异操作 | 交叉操作 |
|---|---|---|---|---|
| F缩放因子 | CR交叉率 | 二项式交叉 | 指数交叉 | 选择操作 |
| 约束处理 | 自适应参数 | 边界约束 | 罚函数 | 成功历史 |
| jDE | SaDE | SHADE | L-SHADE | 多目标DE |
摘要
差分进化（Differential Evolution, DE）是由Rainer Storn和Kenneth Price于1995年提出的高效全局优化算法，专门用于解决实数参数空间的连续优化问题。DE以其简洁的算法结构、较少的控制参数和卓越的优化性能著称，在多个基准测试和实际应用中获得优异表现。与传统遗传算法的随机变异不同，DE采用基于差向量的变异策略，使其在局部搜索和全局探索之间实现了良好的平衡。
一、差分进化的基本原理
1.1 算法起源与动机
1995年，Storn和Price在解决切比雪夫多项式拟合问题时提出了差分进化算法。该算法的核心创新在于利用种群中个体间的差分向量来引导搜索方向，这一设计灵感来源于自然界中生物群体协同进化的特性。
DE的核心思想：
其中为三个互不相同的随机索引，为缩放因子。
1.2 算法框架概览
┌─────────────────────────────────────────────────────┐
│ 差分进化流程 │
├─────────────────────────────────────────────────────┤
│ 1. 初始化种群 X⁰ = {x¹, x², ..., xᴺᴾ} │
│ 2. FOR g = 1 TO G_max: │
│ FOR i = 1 TO Nᴾ: │
│ │ 2.1 变异: 生成变异向量 vⁱ │
│ │ 2.2 交叉: 生成试验向量 uⁱ │
│ │ 2.3 选择: 基于适应度决定存活者 │
│ END FOR │
│ 3. 输出最优解 │
└─────────────────────────────────────────────────────┘
1.3 与遗传算法的关键区别
| 特征 | 遗传算法 | 差分进化 |
|---|---|---|
| 变异机制 | 随机扰动 | 差分向量驱动 |
| 搜索方向 | 无方向性 | 沿梯度方向 |
| 参数敏感性 | 中等 | 较低 |
| 收敛速度 | 较慢 | 较快 |
| 全局搜索 | 强 | 中等（依赖参数） |
二、核心操作详解
2.1 初始化
DE在维搜索空间内随机初始化种群：
def initialize_population(NP, D, bounds):
"""
NP: 种群规模
D: 维度
bounds: [(low1, high1), ..., (lowD, highD)]
"""
population = []
for i in range(NP):
individual = np.array([np.random.uniform(low, high)
for low, high in bounds])
population.append(individual)
return np.array(population)边界处理：初始化后需确保所有个体满足边界约束：
2.2 变异操作
2.2.1 基本变异策略
DE/rand/1（最常用，最稳定）：
def de_rand_1(population, F=0.5, i=None):
"""
随机选择三个不同于i的个体
"""
NP = len(population)
candidates = [j for j in range(NP) if j != i]
r1, r2, r3 = random.sample(candidates, 3)
mutant = population[r1] + F * (population[r2] - population[r3])
return mutantDE/best/1（收敛更快但可能早熟）：
def de_best_1(population, fitness, F=0.5, i=None):
"""
使用当前最优个体作为基准
"""
NP = len(population)
best_idx = np.argmin(fitness)
candidates = [j for j in range(NP) if j != i and j != best_idx]
r1, r2 = random.sample(candidates, 2)
mutant = population[best_idx] + F * (population[r1] - population[r2])
return mutantDE/rand/2（更多样化）：
def de_rand_2(population, F=0.5, i=None):
"""
使用两个差分向量
"""
NP = len(population)
candidates = [j for j in range(NP) if j != i]
r1, r2, r3, r4, r5 = random.sample(candidates, 5)
mutant = population[r1] + F * (population[r2] - population[r3]) + \
F * (population[r4] - population[r5])
return mutant2.2.2 变异策略命名规范
DE的变异策略遵循统一的命名规则：DE/x/y/z
- x：基向量选择方式（rand/best/target to best/current to rand）
- y：差分向量数量（1, 2, …）
- z：交叉类型（bin/binomial/exp/exponential）
完整策略列表：
| 策略名称 | 公式 | 特点 |
|---|---|---|
| DE/rand/1 | 全局搜索强 | |
| DE/best/1 | 收敛快 | |
| DE/rand-to-best/1 | 平衡型 | |
| DE/best/2 | 激进型 | |
| DE/rand/2 | 高变异 |
2.3 交叉操作
2.3.1 二项式交叉（Binomial Crossover）
def binomial_crossover(target, mutant, CR, bounds):
"""
二项式交叉：每个维度独立决定来源
"""
D = len(target)
trial = np.zeros(D)
# 强制包含至少一个来自变异向量的维度
j_rand = random.randint(0, D-1)
for j in range(D):
if random.random() < CR or j == j_rand:
trial[j] = mutant[j]
else:
trial[j] = target[j]
# 边界处理
trial = np.clip(trial,
[b[0] for b in bounds],
[b[1] for b in bounds])
return trial2.3.2 指数交叉（Exponential Crossover）
def exponential_crossover(target, mutant, CR, bounds):
"""
指数交叉：连续一段来自变异向量
"""
D = len(target)
trial = target.copy()
# 随机选择起始点
n = random.randint(0, D-1)
L = 0
# 确定连续段长度
while random.random() < CR and L < D:
n = (n + 1) % D
L += 1
# 复制连续段
for _ in range(L):
trial[n] = mutant[n]
n = (n + 1) % D
# 边界处理
trial = np.clip(trial,
[b[0] for b in bounds],
[b[1] for b in bounds])
return trial二项式 vs 指数交叉：
| 特征 | 二项式交叉 | 指数交叉 |
|---|---|---|
| 搜索特性 | 均匀探索 | 局部搜索 |
| 参数敏感性 | CR | CR |
| 适用场景 | 高维问题 | 低维问题 |
2.4 选择操作
def select(target, trial, fitness_target, fitness_trial):
"""
一对一选择：贪婪策略
"""
if fitness_trial <= fitness_target: # 最小化问题
return trial, fitness_trial
else:
return target, fitness_target数学表达：
三、完整算法实现
3.1 标准差分进化
class DifferentialEvolution:
def __init__(self, objective, bounds, NP=None, F=0.5, CR=0.9,
max_iter=1000, tol=1e-8):
self.objective = objective
self.bounds = bounds
self.D = len(bounds)
# 默认种群规模
self.NP = NP if NP else max(10 * self.D, 50)
self.F = F # 缩放因子
self.CR = CR # 交叉概率
self.max_iter = max_iter
self.tol = tol
self.best_fitness = float('inf')
self.best_solution = None
self.history = []
def initialize(self):
self.population = np.array([
[np.random.uniform(low, high)
for low, high in self.bounds]
for _ in range(self.NP)
])
self.fitness = np.array([
self.objective(x) for x in self.population
])
best_idx = np.argmin(self.fitness)
self.best_fitness = self.fitness[best_idx]
self.best_solution = self.population[best_idx].copy()
def mutate(self, i):
"""DE/rand/1/bin"""
while True:
r = random.sample(range(self.NP), 3)
if i not in r:
break
r1, r2, r3 = r
mutant = self.population[r1] + self.F * (
self.population[r2] - self.population[r3]
)
return mutant
def crossover(self, target, mutant):
"""二项式交叉"""
trial = np.zeros(self.D)
j_rand = random.randint(0, self.D - 1)
for j in range(self.D):
if random.random() < self.CR or j == j_rand:
trial[j] = mutant[j]
else:
trial[j] = target[j]
# 边界处理
for j in range(self.D):
low, high = self.bounds[j]
trial[j] = max(low, min(high, trial[j]))
return trial
def step(self):
"""执行一代进化"""
new_population = np.zeros_like(self.population)
new_fitness = np.zeros(self.NP)
for i in range(self.NP):
# 变异
mutant = self.mutate(i)
# 交叉
trial = self.crossover(self.population[i], mutant)
# 选择
fitness_trial = self.objective(trial)
if fitness_trial <= self.fitness[i]:
new_population[i] = trial
new_fitness[i] = fitness_trial
else:
new_population[i] = self.population[i]
new_fitness[i] = self.fitness[i]
self.population = new_population
self.fitness = new_fitness
# 更新最优解
best_idx = np.argmin(self.fitness)
if self.fitness[best_idx] < self.best_fitness:
self.best_fitness = self.fitness[best_idx]
self.best_solution = self.population[best_idx].copy()
def run(self):
self.initialize()
for gen in range(self.max_iter):
self.step()
self.history.append(self.best_fitness)
if gen % 100 == 0:
print(f"Gen {gen}: Best = {self.best_fitness:.8f}")
# 早停条件
if self.best_fitness < self.tol:
break
return self.best_solution, self.best_fitness3.2 高级变体：jDE（自适应DE）
class JDE(DifferentialEvolution):
"""
动态参数自适应差分进化
Brest et al., 2006
"""
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)
# 每个个体独立控制参数
self.F = np.ones(self.NP) * 0.5
self.CR = np.zeros(self.NP)
# 自适应参数范围
self.F_l, self.F_u = 0.1, 1.0
self.CR_l, self.CR_u = 0.0, 1.0
# 自适应概率
self.tau1 = self.tau2 = 0.1
def update_parameters(self, i):
"""动态更新F和CR"""
# 更新F
if random.random() < self.tau1:
self.F[i] = self.F_l + random.random() * (self.F_u - self.F_l)
# 更新CR
if random.random() < self.tau2:
self.CR[i] = self.CR_l + random.random() * (self.CR_u - self.CR_l)
def mutate(self, i):
"""使用个体自适应参数"""
self.update_parameters(i)
while True:
r = random.sample(range(self.NP), 3)
if i not in r:
break
r1, r2, r3 = r
mutant = self.population[r1] + self.F[i] * (
self.population[r2] - self.population[r3]
)
return mutant
def crossover(self, target, mutant, CR_i):
"""使用个体自适应交叉率"""
trial = np.zeros(self.D)
j_rand = random.randint(0, self.D - 1)
for j in range(self.D):
if random.random() < CR_i or j == j_rand:
trial[j] = mutant[j]
else:
trial[j] = target[j]
for j in range(self.D):
low, high = self.bounds[j]
trial[j] = max(low, min(high, trial[j]))
return trial
def step(self):
new_population = np.zeros_like(self.population)
new_fitness = np.zeros(self.NP)
for i in range(self.NP):
mutant = self.mutate(i)
trial = self.crossover(self.population[i], mutant, self.CR[i])
fitness_trial = self.objective(trial)
if fitness_trial <= self.fitness[i]:
new_population[i] = trial
new_fitness[i] = fitness_trial
else:
new_population[i] = self.population[i]
new_fitness[i] = self.fitness[i]
self.population = new_population
self.fitness = new_fitness
best_idx = np.argmin(self.fitness)
if self.fitness[best_idx] < self.best_fitness:
self.best_fitness = self.fitness[best_idx]
self.best_solution = self.population[best_idx].copy()四、参数控制与调节
4.1 缩放因子F的影响
控制差分向量的缩放程度，直接影响算法的探索能力：
| F值 | 特性 | 适用场景 |
|---|---|---|
| F < 0.3 | 局部搜索能力强 | 微调精细解 |
| F ≈ 0.5 | 平衡型 | 通用场景 |
| F > 0.8 | 全局探索能力强 | 多模态问题 |
Warning
F过大（如F > 1.0）可能导致搜索步长过大，跨越最优区域；F过小（如F < 0.2）可能导致搜索停滞，早熟收敛。
4.2 交叉概率CR的影响
CR控制试验向量来自变异向量的比例：
| CR值 | 特性 | 适用场景 |
|---|---|---|
| CR < 0.3 | 接近随机搜索 | 高维复杂问题 |
| CR ≈ 0.5 | 平衡型 | 通用场景 |
| CR > 0.8 | 贪婪搜索 | 单峰问题 |
4.3 种群规模NP
经验公式：
4.4 参数自适应策略
4.4.1 Success History Adaptive DE (SHADE)
class SHADE(DifferentialEvolution):
"""
基于成功历史的自适应DE
Tanabe & Fukunaga, 2013
"""
def __init__(self, *args, H=6, **kwargs):
super().__init__(*args, **kwargs)
self.H = H
# 历史记忆
self.F_means = [0.5] * H
self.CR_means = [0.5] * H
self.archive = [] # 存档非优解
self.k = 0
def update_history(self, successful_F, successful_CR):
"""更新历史记忆"""
if len(successful_F) == 0:
return
# 更新记忆
F_mean = sum(f**2 for f in successful_F) / sum(successful_F)
CR_mean = np.mean(successful_CR)
self.F_means[self.k] = F_mean
self.CR_means[self.k] = CR_mean
# 循环更新索引
self.k = (self.k + 1) % self.H
def sample_parameters(self, i):
"""从历史记忆中采样参数"""
r = random.randint(0, self.H - 1)
F = self.F_means[r]
CR = self.CR_means[r]
# 添加随机扰动
F = F + 0.1 * random.gauss(0, 1)
CR = random.gauss(CR, 0.1)
# 限制范围
F = np.clip(F, 0, 1)
CR = np.clip(CR, 0, 1)
return F, CR五、约束优化中的DE
5.1 罚函数方法
class ConstrainedDE(DifferentialEvolution):
def __init__(self, objective, constraints, *args, penalty=1000, **kwargs):
super().__init__(objective, *args, **kwargs)
self.constraints = constraints
self.penalty = penalty
def evaluate_constraints(self, x):
"""
返回约束违反程度
g(x) <= 0: 不等式约束
h(x) = 0: 等式约束
"""
g_violations = [max(0, g(x)) for g in self.constraints['ineq']]
h_violations = [abs(h(x)) for h in self.constraints['eq']]
return g_violations, h_violations
def penalized_fitness(self, x):
"""计算带惩罚的适应度"""
obj = self.objective(x)
g_viol, h_viol = self.evaluate_constraints(x)
penalty = self.penalty * (sum(g_viol) + sum(h_viol))
return obj + penalty5.2 ε-约束处理方法
class EpsilonConstraintDE(ConstrainedDE):
def __init__(self, *args, epsilon_0=0, rho=0.1, **kwargs):
super().__init__(*args, **kwargs)
self.epsilon_0 = epsilon_0
self.rho = rho
self.epsilon = epsilon_0
def update_epsilon(self, generation):
"""更新ε参数"""
self.epsilon = self.epsilon_0 * (self.rho ** generation)
def comparison(self, x1, x2):
"""基于ε约束的比较"""
g1, _ = self.evaluate_constraints(x1)
g2, _ = self.evaluate_constraints(x2)
total_violation1 = sum(g1)
total_violation2 = sum(g2)
# 优先选择可行解
if total_violation1 <= self.epsilon and total_violation2 > self.epsilon:
return x1
if total_violation2 <= self.epsilon and total_violation1 > self.epsilon:
return x2
# 都可行或都不可行时比较目标函数值
if self.objective(x1) <= self.objective(x2):
return x1
return x25.3 随机排名方法
class StochasticRankingDE(DifferentialEvolution):
"""
随机排名法处理约束
Runarsson & Yao, 2000
"""
def __init__(self, *args, P_f=0.45, **kwargs):
super().__init__(*args, **kwargs)
self.P_f = P_f # 目标比较概率
def compare(self, x1, x2):
g1, _ = self.evaluate_constraints(x1)
g2, _ = self.evaluate_constraints(x2)
v1, v2 = sum(g1), sum(g2)
# 都可行
if v1 == 0 and v2 == 0:
return x1 if self.objective(x1) <= self.objective(x2) else x2
# 基于约束违反度的比较
if random.random() < self.P_f:
return x1 if v1 < v2 else x2
else:
return x1 if self.objective(x1) <= self.objective(x2) else x2六、DE的改进变体
6.1 多目标差分进化
class MODE(DifferentialEvolution):
"""
多目标差分进化
"""
def __init__(self, objectives, *args, **kwargs):
self.objectives = objectives
self.n_objectives = len(objectives)
super().__init__(lambda x: 0, *args, **kwargs) # 占位
def evaluate(self, x):
return np.array([f(x) for f in self.objectives])
def dominates(self, x1, x2):
f1 = self.evaluate(x1)
f2 = self.evaluate(x2)
return all(f1 <= f2) and any(f1 < f2)
def fast_non_dominated_sort(self, population):
"""快速非支配排序"""
domination_count = [0] * len(population)
dominated_set = [set() for _ in range(len(population))]
fronts = [[]]
for i, p in enumerate(population):
for j, q in enumerate(population):
if i != j and self.dominates(p, q):
dominated_set[i].add(j)
elif i != j and self.dominates(q, p):
domination_count[i] += 1
if domination_count[i] == 0:
fronts[0].append(i)
current_front = 0
while fronts[current_front]:
next_front = []
for i in fronts[current_front]:
for j in dominated_set[i]:
domination_count[j] -= 1
if domination_count[j] == 0:
next_front.append(j)
current_front += 1
if next_front:
fronts.append(next_front)
return fronts[:-1] if fronts[-1] == [] else fronts6.2 协方差引导的DE
class CMAguidedDE(DifferentialEvolution):
"""
协方差矩阵引导的差分进化
"""
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)
self.cov_matrix = np.eye(self.D)
def mutate_cma_guided(self, i):
"""使用协方差矩阵引导变异"""
while True:
r = random.sample(range(self.NP), 3)
if i not in r:
break
r1, r2, r3 = r
# 计算加权差分方向
L = np.linalg.cholesky(self.cov_matrix)
scaled_diff = L @ (self.population[r2] - self.population[r3])
mutant = self.population[r1] + self.F * scaled_diff
return mutant
def update_covariance(self):
"""基于成功个体更新协方差"""
# 获取最优个体
best_idx = np.argmin(self.fitness)
# 更新协方差
pass # 简化实现七、算法性能对比
7.1 CEC基准测试表现
在CEC（IEEE Congress on Evolutionary Computation）基准测试中，DE通常在以下函数类型上表现优异：
| 函数类型 | DE表现 | 备注 |
|---|---|---|
| Unimodal | ★★★★☆ | 收敛速度快 |
| Multimodal | ★★★☆☆ | 依赖策略选择 |
| Hybrid Composition | ★★★★☆ | F参数关键 |
| Multi-Swarm | ★★★☆☆ | 适合多峰搜索 |
7.2 参数推荐配置
| 问题类型 | F | CR | NP | 策略 |
|---|---|---|---|---|
| 通用 | 0.5 | 0.9 | 10×D | DE/rand/1/bin |
| 多模态 | 0.6-0.9 | 0.3-0.7 | 15×D | DE/rand/2/bin |
| 高维 | 0.5 | 0.5-0.7 | 5×D | DE/rand/1/exp |
| 约束 | 0.5 | 0.8 | 20×D | DE/best/1/bin |
八、实用工具与框架
8.1 使用scipy.optimize
from scipy.optimize import differential_evolution
def scipy_de_example():
bounds = [(-5, 5)] * 10
result = differential_evolution(
func=objective,
bounds=bounds,
strategy='best1bin',
maxiter=1000,
popsize=15,
tol=1e-7,
mutation=(0.5, 1),
recombination=0.7,
seed=None,
polish=True, # 使用L-BFGS-B精调
updating='immediate'
)
print(f"Optimal value: {result.fun}")
print(f"Solution: {result.x}")
return result8.2 使用jmetalpy
from jmetal.algorithm.singleobjective import DifferentialEvolution
from jmetal.operator import PolynomialMutation
from jmetal.problem import Problem
class MyProblem(Problem):
def __init__(self):
super().__init__()
self.number_of_variables = 10
self.number_of_objectives = 1
self.number_of_constraints = 0
self.lower_bound = [-10] * 10
self.upper_bound = [10] * 10
def evaluate(self, solution):
# 评估函数
pass
def get_name(self):
return "MyProblem"
algorithm = DifferentialEvolution(
problem=MyProblem(),
population_size=100,
CR=0.5,
F=0.5,
max_evaluations=50000
)参考文献
- Storn, R., & Price, K. (1997). Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341-359.
- Brest, J., et al. (2006). Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems. IEEE Transactions on Evolutionary Computation, 10(6), 646-657.
- Das, S., & Suganthan, P. N. (2011). Differential Evolution: A Survey of the State-of-the-Art. IEEE Transactions on Evolutionary Computation, 15(1), 4-31.
- Tanabe, R., & Fukunaga, A. (2013). Success-History Based Parameter Adaptation for Differential Evolution. Proceedings of IEEE CEC, 2013.
- Price, K. V., et al. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer.