进化策略

2025年6月25日 | 阅读时长11分钟

进化策略 (ES)，或者单数的进化策略一词，是一种典型的随机全局优化算法。该方法最初由工程师手动设计，用于设计最优空气动力学设计，例如在 20 世纪 60 年代在风洞实验中最小化阻力。

进化策略是受自然选择启发的进化算法的一个分支。与其他进化算法不同，ES 不使用交叉操作。因此，它只通过变异来消耗候选解，从而有效地逼近一种并行随机爬山的形式。

它是如何工作的？

进化策略从随机生成的候选解种群开始。然后，算法会经历许多迭代步骤（称为代），执行以下主要步骤：

步骤 1. 评估

使用适应度函数评估每个候选解，并测量每个解的性能如何。

步骤 2. 选择

截断选择意味着选择性能最佳的候选解。

步骤 3. 繁殖

对选定的候选解（称为父代）应用变异（小的随机变化）来创建新的子代。

步骤 4. 替换

根据 ES 的变体，子代将替换上一代，或者与上一代竞争以成为下一代的一部分。

关键参数

μ (mu)： 系统从每个不同的群体中选择父代。
λ (lambda)： 个体总数（种群大小）。
λ / μ： 每个父代产生固定数量的子代。将数量设为整数值，以便所有父代获得相同数量的子代。

符号表示

这些策略在配置进化过程时遵循独特的结构。
(μ, λ)-ES： 子代在每一代中替换父代。
(μ + λ)-ES： 在混合的子代和现有的生物体之间进行选择，以选择继续生存的个体。

示例

当五个父代管理 20 个总候选解时，表示法为 (5, 20)-ES。

一个非常简单的版本称为 (1+1)-ES，它以类似于基本随机爬山法的方式，从单一父代产生一个后代。

开发 (μ, λ)-ES

本节将专门介绍 (μ, λ) 进化策略的实现，其中只有子代才会在代际之间替换父代。

在本演示中，我们将使用 Ackley 函数，这是一个著名且具有挑战性的优化问题。

Ackley 函数是一个多峰目标函数，具有许多局部最小值。对于基本的局部搜索算法来说，它很难避免次优区域并卡在其中。

因此，进化策略类型的全局优化是理想的选择。

在二维空间中，它被定义为，其全局最小值在 [0, 0] 处，评估值为 0.0。

示例

from numpy import asarray
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import argsort
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed

# objective function
def objective(v):
	x, y = v
	return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20

# check if a point is within the bounds of the search
def in_bounds(point, bounds):
	# praticularize all dimensions of the point
	for d in range(len(bounds)):
		# checking if it is out of bounds for this dimension
		if point[d] < bounds[d, 0] or point[d] > bounds[d, 1]:
			return False
	return True

# evolution strategy (mu, lambda) algorithm
def es_comma(objective, bounds, n_iter, step_size, mu, lam):
	best, best_eval = None, 1e+10
	# calculating the number of children per parent
	n_children = int(lam / mu)
	# initial population
	population = list()
	for _ in range(lam):
		candidate = None
		while candidate is None or not in_bounds(candidate, bounds):
			candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
		population.append(candidate)
	# performing the search task
	for epoch in range(n_iter):
		# evaluate fitness for the population
		scores = [objective(c) for c in population]
		# rank scores in ascending order
		ranks = argsort(argsort(scores))
		# selecting the indexes for the top mu ranked solutions
		selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
		# create children from parents
		children = list()
		for i in selected:
			# checking if this parent is the best solution
			if scores[i] < best_eval:
				best, best_eval = population[i], scores[i]
				print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
			# create children for parent
			for _ in range(n_children):
				child = None
				while child is None or not in_bounds(child, bounds):
					child = population[i] + randn(len(bounds)) * step_size
				children.append(child)
		# replacing population with children
		population = children
	return [best, best_eval]

# seed the pseudorandom number generator
seed(1)
# defining the range for input
bounds = asarray([[-5.0, 5.0], [-5.0, 5.0]])
# defining the total iterations
n_iter = 5000
# defining the maximum step size
step_size = 0.15
# number of parents selected
mu = 20
# the number of children generated by parents
lam = 100
# perform the evolution strategy (mu, lambda) search
best, score = es_comma(objective, bounds, n_iter, step_size, mu, lam)
print('Done!')
print('f(%s) = %f' % (best, score))

输出

 
0, Best: f([-0.82977995 2.20324493]) = 6.91249
0, Best: f([-1.03232526 0.38816734]) = 4.49240
1, Best: f([-1.02971385 0.21986453]) = 3.68954
2, Best: f([-0.98361735 0.19391181]) = 3.40796
2, Best: f([-0.98189724 0.17665892]) = 3.29747
2, Best: f([-0.07254927 0.67931431]) = 3.29641
3, Best: f([-0.78716147 0.02066442]) = 2.98279
3, Best: f([-1.01026218 -0.03265665]) = 2.69516
3, Best: f([-0.08851828 0.26066485]) = 2.00325
4, Best: f([-0.23270782 0.04191618]) = 1.66518
4, Best: f([-0.01436704 0.03653578]) = 0.15161
7, Best: f([0.01247004 0.01582657]) = 0.06777
9, Best: f([0.00368129 0.00889718]) = 0.02970
25, Best: f([ 0.00666975 -0.0045051 ]) = 0.02449
33, Best: f([-0.00072633 -0.00169092]) = 0.00530
211, Best: f([2.05200123e-05 1.51343187e-03]) = 0.00434
315, Best: f([ 0.00113528 -0.00096415]) = 0.00427
418, Best: f([ 0.00113735 -0.00030554]) = 0.00337
491, Best: f([ 0.00048582 -0.00059587]) = 0.00219
704, Best: f([-6.91643854e-04 -4.51583644e-05]) = 0.00197
1504, Best: f([ 2.83063223e-05 -4.60893027e-04]) = 0.00131
3725, Best: f([ 0.00032757 -0.00023643]) = 0.00115
Done!
f([ 0.00032757 -0.00023643]) = 0.001147

开发 (μ + λ)-ES

在 (μ + λ) 进化策略中，父代在代际传递中像其他后代候选解一样行事。

父代和它们新产生的后代都将成为下一代成员，而不会首先消除父代。在这种策略中，父代和它们的子代都必须竞争才能生存。

系统以坚定不移的决心运行，同时保留其最佳结果。当此策略继续运行时，它可能会过早地停留在次优解上，而不是达到最优结果。

通过保持强大的表现者在其种群中，该算法可以更快地检测和利用有前景的区域来找到更好的答案。

示例

# evolution strategy (mu + lambda) of the ackley objective function
from numpy import asarray
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import argsort
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed

# objective function
def objective(v):
	x, y = v
	return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20

# checking if a point is within the bounds of the search
def in_bounds(point, bounds):
	# enumerate all dimensions of the point
	for d in range(len(bounds)):
		# check if out of bounds for this dimension
		if point[d] < bounds[d, 0] or point[d] > bounds[d, 1]:
			return False
	return True

# evolution strategy (mu + lambda) algorithm
def es_plus(objective, bounds, n_iter, step_size, mu, lam):
	best, best_eval = None, 1e+10
	# calculate the number of children per parent
	n_children = int(lam / mu)
	# initial population
	population = list()
	for _ in range(lam):
		candidate = None
		while candidate is None or not in_bounds(candidate, bounds):
			candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
		population.append(candidate)
	# performing the search operation
	for epoch in range(n_iter):
		# evaluating fitness for the population
		scores = [objective(c) for c in population]
		# ranking the scores in ascending order
		ranks = argsort(argsort(scores))
		# selecting the indexes for the top mu ranked solutions
		selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
		# create children from parents
		children = list()
		for i in selected:
			# checking if this parent is the best solution ever seen
			if scores[i] < best_eval:
				best, best_eval = population[i], scores[i]
				print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
			# keeping the parent
			children.append(population[i])
			# creating children for parent
			for _ in range(n_children):
				child = None
				while child is None or not in_bounds(child, bounds):
					child = population[i] + randn(len(bounds)) * step_size
				children.append(child)
		# replacing population with children
		population = children
	return [best, best_eval]

# seed the pseudorandom number generator
seed(1)
# defining range for input
bounds = asarray([[-5.0, 5.0], [-5.0, 5.0]])
# defining the total iterations
n_iter = 5000
# defining the maximum step size
step_size = 0.15
# number of parents selected
mu = 20
# the number of children generated by parents
lam = 100
# performing the evolution strategy (mu + lambda) search
best, score = es_plus(objective, bounds, n_iter, step_size, mu, lam)
print('Done!')
print('f(%s) = %f' % (best, score))

输出

 
0, Best: f([-0.82977995 2.20324493]) = 6.91249
0, Best: f([-1.03232526 0.38816734]) = 4.49240
1, Best: f([-1.02971385 0.21986453]) = 3.68954
2, Best: f([-0.96315064 0.21176994]) = 3.48942
2, Best: f([-0.9524528 -0.19751564]) = 3.39266
2, Best: f([-1.02643442 0.14956346]) = 3.24784
2, Best: f([-0.90172166 0.15791013]) = 3.17090
2, Best: f([-0.15198636 0.42080645]) = 3.08431
3, Best: f([-0.76669476 0.03852254]) = 3.06365
3, Best: f([-0.98979547 -0.01479852]) = 2.62138
3, Best: f([-0.10194792 0.33439734]) = 2.52353
3, Best: f([0.12633886 0.27504489]) = 2.24344
4, Best: f([-0.01096566 0.22380389]) = 1.55476
4, Best: f([0.16241469 0.12513091]) = 1.44068
5, Best: f([-0.0047592 0.13164993]) = 0.77511
5, Best: f([ 0.07285478 -0.0019298 ]) = 0.34156
6, Best: f([-0.0323925 -0.06303525]) = 0.32951
6, Best: f([0.00901941 0.0031937 ]) = 0.02950
32, Best: f([ 0.00275795 -0.00201658]) = 0.00997
109, Best: f([-0.00204732 0.00059337]) = 0.00615
195, Best: f([-0.00101671 0.00112202]) = 0.00434
555, Best: f([ 0.00020392 -0.00044394]) = 0.00139
2804, Best: f([3.86555110e-04 6.42776651e-05]) = 0.00111
4357, Best: f([ 0.00013889 -0.0001261 ]) = 0.00053
Done!	
f([ 0.00013889 -0.0001261 ]) = 0.000532

过程：(μ + λ) 进化策略

(μ + λ)-ES 是一种强大的优化算法，它通过在每一代中匹配父代和子代个体来演化候选解的种群。以下是此分步过程。

1. 初始化

首先，确定主要参数：父代个体数量 (μ) 和每代子代数量 (λ)。这些值有助于演化种群并在每次迭代中发展种群。

其次，生成 μ 个体的初始种群。如果搜索空间是有限的，则定义搜索问题的搜索空间，并且每个个体表示为在有界搜索空间内随机采样的实值参数向量。这保证了起始种群的多样性。

初始化后，需要评估种群中的每个个体以找到其适应度。这意味着将目标函数应用于每个解，以确定其与最优结果的接近程度。该过程的后续步骤将使用这些适应度值进行选择。

2. 重组

在每一代中，从当前的种群中选择 ρ 个父代。个体适应度是选择父代的基础，性能越高，被选中的可能性越大。这有助于传播高质量的解决方案。

使用重组算子从选定的父代中繁殖 λ 个子代。重组从多个父代获取信息并将其混合成新的个体。中间重组和离散重组是常见的技术，其中在重组之前对父代之间的参数进行平均，并且参数本身是从两个父代中随机选择的。

3. 变异

生成子代后，通过变异处理子代以产生随机变化。变异有助于探索搜索空间并避免过早收敛。在进化策略中使用的所有变异方法中，高斯变异可能是最常用的，因为它涉及将子代中的每个参数扰动一个从正态分布采样的微小随机值。

变异步长（也称为变异强度）可以随时间调整，以进一步提高算法的适应性。具体来说，1/5 成功规则会根据变异是否提高适应度来改变或调整步长。自适应的另一种选择是让每个个体拥有并演化其变异率。

4. 适应度评估

然后，在通过目标函数评估每个子代后，对子代进行变异以创建新个体。这设置了新开发解决方案的适应度值，并为选择过程做准备。

5. 选择

这种 (μ + λ) 策略形成一个组合池，其中 μ 个父代与 λ 个子代结合；因此，该池包含 μ + λ 个个体。然后评估这个包含 μ 个个体的完整组，并从中选择适应度最佳的个体。

这些将成为这些选定个体的下一代。通过包含父代和子代，良好的解决方案将茁壮成长，但包含它们也可能导致种群过快地趋向于局部最小值。

此过程重复进行，直到达到一定的代数或满足终止条件（例如，适应度或最长运行时间）。优化的最终结果是我们在此过程中遇到的最佳解决方案。

(μ + λ) 进化策略的优点

非常适合连续优化

进化策略由于其在处理实值参数时能够高效运行的设计，因此非常适合解决不同领域的连续优化问题。

探索与利用的平衡

在两者之间，该算法在探索搜索空间的新区域（全局搜索）和从良好解决方案中进行“局部搜索”改进之间取得了良好的权衡，从而避免了过早收敛。

对复杂函数具有鲁棒性

ES 可以由鲁棒的、不可微的和非凸的目标函数组成。因此，对于没有梯度信息或梯度信息不可靠的现实世界问题，它非常灵活。

易于并行化

这使得该算法自然易于并行化，并且种群中个体的评估是独立的。它允许使用多个处理器或分布式系统更快地执行。

(μ + λ) 进化策略的缺点

高计算成本

在高维或复杂问题中，该算法需要大量的适应度评估。长期而言，它会消耗太多时间，并增加对计算时间的要求。

对参数设置敏感

策略参数（变异强度、步长、种群大小 μ 和 λ；选择策略）的选择是 ES 上性能高度依赖的参数。错误的选择可能导致收敛缓慢或不稳定。

过早收敛的风险

当种群多样性过快丢失时，算法会过早收敛。为了不陷入局部最小值，保持探索和利用之间的平衡非常重要。

结论

进化策略 (ES) 是一种受自然选择启发的随机优化方法，本教程已涵盖。ES 使用选择、变异和重组来演化种群，以提高其在后续时间步的适应度。有两种主要变体：(μ, λ) ES，其中子代替换父代；以及 (μ + λ) ES，其中父代和子代共同竞争生存，以提供不同的探索-利用平衡。

类似地，您还学习了如何在 Python 中实现 ES 来寻找复杂多峰函数的最小值，例如 Ackley 函数。它通过实际示例和实践方法，展示了该方法在连续、不可微优化问题上的有效性。

下一主题支持向量机中的主要核函数

进化策略

它是如何工作的？

关键参数

符号表示

开发 (μ, λ)-ES

开发 (μ + λ)-ES

过程：(μ + λ) 进化策略

(μ + λ) 进化策略的优点

(μ + λ) 进化策略的缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

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

机器学习

监督式学习

分类

杂项

相关教程

面试题

进化策略

它是如何工作的？

关键参数

符号表示

开发 (μ, λ)-ES

开发 (μ + λ)-ES

过程：(μ + λ) 进化策略

(μ + λ) 进化策略的优点

(μ + λ) 进化策略的缺点

结论

相关帖子

机器学习中的基尼指数

什么是大型语言模型 (LLM)

什么是 LSTM 网络

传统特征工程模型

神经网络中 Batch 和 Epoch 的区别

降维技术

机器学习中的猫分类

机器学习中的卷积类型

需了解的 5 个 Scikit-learn 数据转换器

联合概率分布

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器