# Knowledge-Based Perturbation LaF-CMA-ES for Multimodal Optimization
## 3 The KbP-LaF-CMAES Algorithm
### Convergence Analysis of Kbp-LaF-CMAES  
In the proposed algorithm, the solutions of exploration are not directly applied to the two variants of CMA-ES. Therefore, the adaptability and convergence of CMAES are not affected by the strategies of Kbp and LaF. The convergence of CMA-ES proved to be equivalent to the convergence of Kbp-LaF-CMAES. The evolutionary process of the evolutionary algorithm can be modeled as an inhomogeneous Markovian process [30]. As a population-based stochastic optimization algorithm, the evolutionary process of CMA-ES is considered a resampling process [31]. Two primary strategies are included in CMA-ES, covariance matrix self-adaptation and step-size adaptation [32]. Then, the description of the theoretical derivation of its empirically observed convergence rate is tackled in this Section [33]. In CMA-ES, the state space \((X_{t},\sigma_{t})\in\mathbb{R}^{n}\times\mathbb{R}\) is constructed. Where \(X_{t}\in\mathbb{R}^{n}\) represent the individual at iteration \(t\). \(\sigma_{t}\) is the overall step size of an underlying sampling distribution at iteration \(t\). Then, CMA-ES is the stochastically recursive sequence on the state space. \[(X_{t+1},\sigma_{t+1})=\mathcal{F}((X_{t},\sigma_{t}),U_{t}) \tag{11}\]  
\(\mathcal{F}\) is the transition function of the algorithm. In CMA-ES, the transition function \(\mathcal{F}\) depends on the benchmark function \(f\) only through the comparison of candidate solutions. \(U_{t}\) is the distribution obtained by the selected solutions. The \(p\) individuals of the population are created by a \(\mathcal{Sol}\) function. \[X_{t}^{i}=\mathcal{Sol}\Big{(}(X_{t},\sigma_{t}),U_{t}^{i}\Big{)},i=1,\cdots,p \tag{12}\]  
where \(\mathcal{Sol}\big{(}(x,\sigma),u^{i}\big{)}=x+\sigma u^{i}\). Then, the \(p\) candidate individuals are evaluated on \(f\) and ordered by the objective. The permutation process is denoted as \(\mathcal{S}\in\mathfrak{S}(p)\). Where \(\mathfrak{S}(p)\) is the permutation set of \(p\) elements. \[\mathfrak{S}(p)\times\mathbb{U}^{p}\rightarrow\mathbb{U}^{p} \tag{13}\]  
\[(\mathcal{S},U_{t})\mapsto\mathcal{S}*U_{t}=\Big{(}U_{t}^{\mathfrak{S}(1)}, \cdots,U_{t}^{\mathfrak{S}(p)}\Big{)} \tag{14}\]  
The update process of \((X_{t},\sigma_{t})\) is executed according to the strategy of selection and mutation. More precisely, a measurable function \(\mathcal{G}\) called the update function that maps \(\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{U}^{p}\) onto \(\mathbb{R}^{n}\times\mathbb{R}\). \[(X_{t+1},\sigma_{t+1})=\mathcal{G}((X_{t},\sigma_{t}),\mathcal{S}*U_{t})= \mathcal{G}((X_{t},\sigma_{t}),Y_{t}) \tag{15}\]  
where \(Y_{t}\) denotes the ordered coordinates of \(U_{t}\). CMA-ES is determined by the quadruplet \((\mathcal{Sol},\mathcal{G},\mathbb{U}^{p},p)\). (1) Invariance properties of CMA-ES  
Suppose that \(\mathcal{M}\) is a strictly monotonic mapping, \(f^{\prime}\) is the mapping function. \((X_{t}^{\prime},\sigma_{t}^{\prime})\) is the Markov chain obtained when optimizing \(f^{\prime}\) using the same sequence \((X_{t},\sigma_{t})_{t\in\mathbb{N}}\) and the same initial state \((X_{0}^{\prime},\sigma_{0}^{\prime})=(X_{0},\sigma_{0})\). **Proof 1. ** Invariance to Strictly Monotonic Transformations of \(f\). Assume \(\big{(}X_{t}^{\prime},\sigma_{t}^{\prime}\big{)}=(X_{t},\sigma_{t})\), and denote \(X_{t}^{i}=\mathcal{Sol}\big{(}(X_{t},\sigma_{t}),U_{t}^{i}\big{)}\). Because \(\mathcal{Ord}\Big{(}f\big{(}X_{t}^{1}\big{)},\cdots,f\Big{(}X_{t}^{p}\Big{)} \Big{)}=\mathcal{O}rd\Big{(}f\big{(}X_{t}^{1}\big{)},\cdots,f\Big{(}X_{t}^{p} \Big{)}\Big{)}=\mathcal{S}\), the following equation is induced. \(\mathcal{Ord}\) is the ordering function that returns the permutation set of \(p\) elements. \[(X_{t+1},\sigma_{t+1})=\mathcal{G}((X_{t},\sigma_{t}),\mathcal{S}*U_{t})= \mathcal{G}\big{(}\big{(}X_{t}^{\prime},\sigma_{t}^{\prime}\big{)},\mathcal{S}* U_{t}\big{)}=\big{(}X_{t+1}^{\prime},\sigma_{t+1}^{\prime}\big{)} \tag{16}\]  
\(\square\)  
**Proof 2. ** Invariance to Translation of \(f\).