You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
RegCMA is a Python implementation of Regulated Evolution Strategies [1] with Covariance Matrix Adaption [2] for continuous "Black-Box" optimization problems. RegCMA is suitable for optimization in situations where the allowed number of iterations is limited such as hyper-parameter tuning in machine learning model and optimization algorithm, and it attempts to make the most of them to find good solutions.
Regulated Evolution Strategies(hereinafter referred to as RES) is a evolutionary algorithm framework to attempts to find reasonable solutions of following unconstrained minimization problems:
where $x$ denotes $N$-dimensional decision variables, and $f:R^N \mapsto R$ denotes "Black-Box" objective function to be minimized. A RES-based algorithm should satisfy the following updating structure:
where $k = 0,1,\dots$ denotes the iteration, $\mathcal{P} = \lbrace 1,\dots,\lvert \mathcal{P}\rvert\rbrace$ denotes the index set for samples, and $x^{p}(k) \in \mathbb{R}^{N}(p\in\mathcal{P})$ denote individual samples. Random vectors $y^{p}(k) \in \mathbb{R}^{N}(p\in\mathcal{P})$ are drawn from ${\cal N}(0,C(k))$. The distribution parameters $\mu(k) \in \mathbb{R}^{N}$ and $C(k) \in \mathbb{R}^{N \times N}$ can be updated in an arbitrary manner, meanwhile RegCMA employs the manner of CMA-ES[2]. The state $r(k)$ should be called internal regulator, which attenuates the influence of $C(k)$ in future. It is initialized by $r(0)=1$ and updated with the delay factor parameter $\beta \in (0,1)$. In contrast, the parameter $\alpha(k) \in{0,1}$ should be called external regulator, which controls convergence speed of the sample dispersion. The state $T(k)$ indicating the sample dispersion in the framework, is an intentional approximation of $\mathrm{Tr} S_{x}(k) = \frac{1}{\lvert \mathcal{P}\rvert}\sum_{p\in\mathcal{P}} (x^{p}(k)-\mu(k))(x^{p}(k)-\mu(k))^{\top}$ to enable rigorous analysis.
The RES framework provides the following theorem that states convergence of sample dispersion.
Theorem 1 [1]: Let ${\cal A}$ denote an RES-based algorithm. Suppose there exist constants $L_{\log \alpha}(k) \in \mathbb{R}$ and $L_{\log r} > 0$ such that $\log \alpha(k) \le L_{\log \alpha}(k) < +\infty \enspace (\forall k\ge 0)$ and $\left\lvert \log T(k) / \mathrm{Tr} C(k+1) \right\rvert \le L_{\log r} < +\infty \enspace (\forall k\ge 0)$. In addition, suppose $y^{p}(k) \enspace (k \ge 0, p\in\mathcal{P})$ be independent of each other. If ${\cal A}$ is designed so that
With this estimator, we can design the value of $\alpha(k)$ with allowed maximum number iterations and target tolerance of $T(\simeq S_{x})$.
Example
# -*- coding: utf-8 -*-importregcmaimportnumpyasnp# Define the objective function to be minimized.defquadratic(x): returnx.dot(x)
# Define the initial solution.DIMENSION=10x0=np.random.randn(DIMENSION)
option= {
'iteration_max': 100,
'initial_covariance': 1E0,
'convergence_tolerance': 1E-10
}
result=regcma.solve(quadratic, x0, option, plot=True)
In the example above, RegCMA minimizes the objective function with regulating its sampling dispersion so that the convergence index (mean of diagonal components of the $S_{x}$) gradually reaches 1E-10 at iteration 100. The following plot depicts the search trend. The chart of Convergence Index shows that actual convergence index tracks the theoretical reference.