Python 3 的轻量级协方差矩阵适应进化策略 (CMA-ES) 实现。
项目描述
CMA-ES
轻量级协方差矩阵适应进化策略 (CMA-ES) [1] 实现。
消息
- 2021/02/02该库的维护者@nmasahiro撰写的论文“Warm Starting CMA-ES for Hyperparameter Optimization”在 AAAI 2021 被接受 :tada:
- 2020/07/29 Optuna 的内置 CMA-ES 采样器在 Optuna v2.0 中稳定使用了这个库。请查看v2.0 发布博客。
安装
支持的 Python 版本为 3.6 或更高版本。
$ pip install cmaes
或者您可以通过conda-forge安装。
$ conda install -c conda-forge cmaes
用法
这个库提供了一个“询问和告诉”风格的界面。
import numpy as np
from cmaes import CMA
def quadratic(x1, x2):
return (x1 - 3) ** 2 + (10 * (x2 + 2)) ** 2
if __name__ == "__main__":
optimizer = CMA(mean=np.zeros(2), sigma=1.3)
for generation in range(50):
solutions = []
for _ in range(optimizer.population_size):
x = optimizer.ask()
value = quadratic(x[0], x[1])
solutions.append((x, value))
print(f"#{generation} {value} (x1={x[0]}, x2 = {x[1]})")
optimizer.tell(solutions)
您可以通过自动超参数优化框架Optuna [2]使用这个库。Optuna 的内置 CMA-ES 采样器在引擎盖下使用此库可从v1.3.0获得并稳定在v2.0.0。有关详细信息，请参阅文档或v2.0 发布博客。
import optuna
def objective(trial: optuna.Trial):
x1 = trial.suggest_uniform("x1", -4, 4)
x2 = trial.suggest_uniform("x2", -4, 4)
return (x1 - 3) ** 2 + (10 * (x2 + 2)) ** 2
if __name__ == "__main__":
sampler = optuna.samplers.CmaEsSampler()
study = optuna.create_study(sampler=sampler)
study.optimize(objective, n_trials=250)
CMA-ES 变体
热启动 CMA-ES [3]
暖启动 CMA-ES 是一种通过初始化 CMA-ES 来传递类似 HPO 任务的先验知识的方法。它估计一个有希望的分布并生成多元高斯分布的参数，如下所示：
| Rot Ellipsoid 函数 | 椭球函数 |
|---|---|
 |
 |
源代码
import numpy as np
from cmaes import CMA, get_warm_start_mgd
def source_task(x1: float, x2: float) -> float:
b = 0.4
return (x1 - b) ** 2 + (x2 - b) ** 2
def target_task(x1: float, x2: float) -> float:
b = 0.6
return (x1 - b) ** 2 + (x2 - b) ** 2
if __name__ == "__main__":
# Generate solutions from a source task
source_solutions = []
for _ in range(1000):
x = np.random.random(2)
value = source_task(x[0], x[1])
source_solutions.append((x, value))
# Estimate a promising distribution of the source task
ws_mean, ws_sigma, ws_cov = get_warm_start_mgd(
source_solutions, gamma=0.1, alpha=0.1
)
optimizer = CMA(mean=ws_mean, sigma=ws_sigma, cov=ws_cov)
# Run WS-CMA-ES
print(" g f(x1,x2) x1 x2 ")
print("=== ========== ====== ======")
while True:
solutions = []
for _ in range(optimizer.population_size):
x = optimizer.ask()
value = target_task(x[0], x[1])
solutions.append((x, value))
print(
f"{optimizer.generation:3d} {value:10.5f}"
f" {x[0]:6.2f} {x[1]:6.2f}"
)
optimizer.tell(solutions)
if optimizer.should_stop():
break
完整的源代码可在此处获得。
可分离 CMA-ES [4]
sep-CMA-ES 是一种将协方差矩阵约束为对角线的算法。由于降低了模型复杂度，降低了协方差矩阵的学习率。因此，该算法在可分离函数上的性能优于 CMA-ES。
源代码
import numpy as np
from cmaes import SepCMA
def ellipsoid(x):
n = len(x)
if len(x) < 2:
raise ValueError("dimension must be greater one")
return sum([(1000 ** (i / (n - 1)) * x[i]) ** 2 for i in range(n)])
if __name__ == "__main__":
dim = 40
optimizer = SepCMA(mean=3 * np.ones(dim), sigma=2.0)
print(" evals f(x)")
print("====== ==========")
evals = 0
while True:
solutions = []
for _ in range(optimizer.population_size):
x = optimizer.ask()
value = ellipsoid(x)
evals += 1
solutions.append((x, value))
if evals % 3000 == 0:
print(f"{evals:5d} {value:10.5f}")
optimizer.tell(solutions)
if optimizer.should_stop():
break
完整的源代码可在此处获得。
IPOP-CMA-ES [5]
IPOP-CMA-ES 是一种随着人口规模的增加重新启动 CMA-ES 的方法，如下所示。
源代码
import math
import numpy as np
from cmaes import CMA
def ackley(x1, x2):
# https://www.sfu.ca/~ssurjano/ackley.html
return (
-20 * math.exp(-0.2 * math.sqrt(0.5 * (x1 ** 2 + x2 ** 2)))
- math.exp(0.5 * (math.cos(2 * math.pi * x1) + math.cos(2 * math.pi * x2)))
+ math.e + 20
)
if __name__ == "__main__":
bounds = np.array([[-32.768, 32.768], [-32.768, 32.768]])
lower_bounds, upper_bounds = bounds[:, 0], bounds[:, 1]
mean = lower_bounds + (np.random.rand(2) * (upper_bounds - lower_bounds))
sigma = 32.768 * 2 / 5 # 1/5 of the domain width
optimizer = CMA(mean=mean, sigma=sigma, bounds=bounds, seed=0)
for generation in range(200):
solutions = []
for _ in range(optimizer.population_size):
x = optimizer.ask()
value = ackley(x[0], x[1])
solutions.append((x, value))
print(f"#{generation} {value} (x1={x[0]}, x2 = {x[1]})")
optimizer.tell(solutions)
if optimizer.should_stop():
# popsize multiplied by 2 (or 3) before each restart.
popsize = optimizer.population_size * 2
mean = lower_bounds + (np.random.rand(2) * (upper_bounds - lower_bounds))
optimizer = CMA(mean=mean, sigma=sigma, population_size=popsize)
print(f"Restart CMA-ES with popsize={popsize}")
完整的源代码可在此处获得。
BIPOP-CMA-ES [6]
BIPOP-CMA-ES 应用了两种交错重启策略，一种具有不断增加的种群规模，另一种具有不同的小种群规模。
源代码
import math
import numpy as np
from cmaes import CMA
def ackley(x1, x2):
# https://www.sfu.ca/~ssurjano/ackley.html
return (
-20 * math.exp(-0.2 * math.sqrt(0.5 * (x1 ** 2 + x2 ** 2)))
- math.exp(0.5 * (math.cos(2 * math.pi * x1) + math.cos(2 * math.pi * x2)))
+ math.e + 20
)
if __name__ == "__main__":
bounds = np.array([[-32.768, 32.768], [-32.768, 32.768]])
lower_bounds, upper_bounds = bounds[:, 0], bounds[:, 1]
mean = lower_bounds + (np.random.rand(2) * (upper_bounds - lower_bounds))
sigma = 32.768 * 2 / 5 # 1/5 of the domain width
optimizer = CMA(mean=mean, sigma=sigma, bounds=bounds, seed=0)
n_restarts = 0 # A small restart doesn't count in the n_restarts
small_n_eval, large_n_eval = 0, 0
popsize0 = optimizer.population_size
inc_popsize = 2
# Initial run is with "normal" population size; it is
# the large population before first doubling, but its
# budget accounting is the same as in case of small
# population.
poptype = "small"
for generation in range(200):
solutions = []
for _ in range(optimizer.population_size):
x = optimizer.ask()
value = ackley(x[0], x[1])
solutions.append((x, value))
print(f"#{generation} {value} (x1={x[0]}, x2 = {x[1]})")
optimizer.tell(solutions)
if optimizer.should_stop():
n_eval = optimizer.population_size * optimizer.generation
if poptype == "small":
small_n_eval += n_eval
else: # poptype == "large"
large_n_eval += n_eval
if small_n_eval < large_n_eval:
poptype = "small"
popsize_multiplier = inc_popsize ** n_restarts
popsize = math.floor(
popsize0 * popsize_multiplier ** (np.random.uniform() ** 2)
)
else:
poptype = "large"
n_restarts += 1
popsize = popsize0 * (inc_popsize ** n_restarts)
mean = lower_bounds + (np.random.rand(2) * (upper_bounds - lower_bounds))
optimizer = CMA(
mean=mean,
sigma=sigma,
bounds=bounds,
population_size=popsize,
)
print("Restart CMA-ES with popsize={} ({})".format(popsize, poptype))
完整的源代码可在此处获得。
基准测试结果
| 罗森布洛克函数 | 六峰骆驼功能 |
|---|---|
 |
 |
此实现（绿色）与pycma（蓝色）相比较。有关详细信息，请参阅基准。
链接
其他库：
我尊重所有参与 CMA-ES 的图书馆。
参考：
- [1] N. Hansen，CMA 进化策略：教程。arXiv:1604.00772, 2016。
- [2]秋叶拓哉、佐野翔太郎、柳濑俊彦、太田健、小山正典。2019. Optuna：下一代超参数优化框架。在 2019 年 8 月 4 日至 8 日举行的第 25 届 ACM SIGKDD 知识发现和数据挖掘会议 (KDD '19) 上。
- [3] Masahiro Nomura、Shuhei Watanabe、Youhei Akimoto、Yoshihiko Ozaki、Masaki Onishi。“用于超参数优化的热启动 CMA-ES”，AAAI。2021 年。
- [4]雷蒙德·罗斯，尼古拉斯·汉森。实现线性时间和空间复杂度的 CMA-ES 的简单修改。第 10 届国际平行问题解决自然会议，2008 年 9 月，德国多特蒙德。inria-00287367。
- [5] Auger, A., Hansen, N.：随着人口规模的增加，重新启动 CMA 进化策略。见：2005 年 IEEE 进化计算大会论文集 (CEC'2005)，第 1769-1776 页 (2005a)
- [6] Hansen N. 在 BBOB-2009 功能测试平台上对 BI-Population CMA-ES 进行基准测试。在遗传和进化计算会议的研讨会论文集中，GECCO，第 2389-2395 页。ACM，2009 年。
