An adaptive genomic difference based genetic algorithm and its application to memetic continuous optimization

Abstract

Continuous function optimization is ubiquitous in many branches of Science and Technology. Memetic algorithms are a particularly interesting approach to the optimization of continuous, non-linear, multimodal, ill-conditioned or noisy functions as these algorithms do not require derivatives and balance global exploratory search with local refinement. The Wang genetic algorithm promotes genetic diversity (exploratory capacities) by applying crossover only to parents with sufficient different chromosomes (genomes). In this work an improvement of the Wang algorithm is proposed that allows for an adaptive evaluation of the genomic difference between individuals in a way that is independent of the optimization problem and takes into account the stage of the evolutionary process. Moreover, the work proposes an original and relevant memetic algorithm combining the improved Wang genetic algorithm, for exploration purposes, with the covariance matrix adaptation evolutionary strategy (CMA-ES) for refinements. The proposed algorithm is empirically evaluated using 25 bench marking functions against five state-of-the-art memetic algorithms revealing superior performance which is a strong evidence on the relevance of proposed algorithm.

Keywords

Memetic algorithms GA local search continuous optimization evolution strategies CMA-ES Wang algorithm

1. Introduction

Memetic algorithms (MA) – otherwise known as cultural algorithms, Baldwinian or Lamarckian evolutionary algorithms, hybrid or genetic local search algorithms – are one trendy research topic in Evolutionary Computation and can be viewed as an extension of conventional genetic algorithms (GA) [26, 13, 12, 16]. The conventional GA operates on a population of individuals each one of which being a candidate solution to the considered optimization problem. Classically, each individual is composed by chromosomes (represented by a binary string) whose elements (bits) are called genes. Associated with each individual there is a figure of merit (fitness function) indicating how good this candidate solution is. The algorithm itself is an iterative stochastic procedure where in each generation, individuals are stochastically selected based on their fitness. Selected individuals (parents) will have a chance to crossover their genome among each other, thus propagating part of their genes to new individuals (offsprings). During this process sometimes mutation occurs, i.e., one gene flips its value with low probability. Offsprings can replace total or partially the old population. The whole process repeats until a given stop criterion is met.

Roughly speaking, a MA combines the global search (exploration) provided by an evolutionary process similar to the above mentioned one, with individual refinements, the so called local search (exploitation). Exploration promotes search in distinct regions of the search space, whereas exploitation searches around the neighborhood of a good solution aiming at producing better quality solutions.

This work focuses on memetic algorithms for real-valued (continuous) function optimization. Continuous function optimization is an ubiquitous problem in the many branches of Science and Technology, and becomes even more relevant when functions are non-linear, multimodal, ill-conditioned or noisy as most of the classic methods may not be effective. Evolutionary computation approaches are a particularly interesting to the optimization of such functions, as they use only information of the value of the function in a limited number of points and do not require the computation of derivatives. This is in clear contrast with conventional analytical methods that, depending on the function to optimize, may have their application quite limited. Evolutionary approaches in which real-valued solutions are directly coded as individuals of a population include the real-coded genetic algorithms [6], evolution strategies [2], evolutionary programming [17], particle swarm optimisation [14], and differential evolution [29]. For a recent comprehensive view of the available methods see [20]. Currently there is a large body of evidence suggesting that MAs not only converge to high-quality solutions, but also search vast solution spaces more efficiently than other evolutionary approaches [24].

This work proposes two main contributions:

1.
It proposes an improvement of the Wang genetic algorithm [31, 32]. Wang algorithm promotes genetic diversity in the population by applying crossover only to parents with sufficient different chromosomes (genomes). This conditional application of variation operators replaces the classical probability based application of these operators. Our improvement allows for an adaptive evaluation of the genomic difference between individuals in a way that is independent of the optimization problem and takes into account the stage of the evolutionary process. Less crossover, more mutation in the beginning and more crossover, less mutation towards the end of the evolutionary process (see Section 4);
2.
The work also proposes an original and relevant memetic algorithm combining the improved Wang genetic algorithm, for exploration purposes, with the covariance matrix adaptation evolutionary strategy (CMA-ES) [10] for exploitation (Section 5). There are a variety of memetic algorithms for continuous function optimization – see Section 2 – but to the best of the authors’ knowledge this particular symbiosis is not being considered. Furthermore, the proposed algorithm is empirically evaluated using 25 bench marking functions [30] against five state-of-the-art memetic algorithms and has shown superior performance which is a strong evidence on the relevance of proposed algorithm.

The rest of the paper is organized as follows. Section 2 briefly reviews the related work on memetic algorithms for continuous function optimization. Section 3 presents the required background, formulating the studied problem and introducing both the Wang algorithm and the CMA-ES. Section 4 describes the proposed improvement to the Wang algorithm and Section 5 describes the proposed memetic algorithm. Section 6 summarizes the experimental setup used for empirical evaluation and includes a brief discussion of the obtained results. Section 7 presents the main conclusions of the work. Appendix A specifies CMA-ES and Appendix B summarizes the 25 functions used to evaluate the proposed algorithm.
2. Related work

Many different instances of memetic algorithms (MA) have been reported and applied across a wide variety of domains, see [28, 25] for recent reviews. This work focuses on memetic algorithms for continuous optimization. These have to deal with at least the following basic issues: adoption of a global and of a local searcher, and integration issues such as computational resources balancing between the global and local searchers or communication between them.

Work on memetic algorithms for continuous optimization have been developed around one or more of the above issues. Most of these work employs real-coded evolutionary algorithms. In general, generational real-valued genetic algorithm (GA) are used as global searcher due to their recognized exploratory capabilities. Much less works are employing steady-state GA, references [24, 22, 23] being some examples of such works.

In a typical MA an offspring undergoes local refinement with a given probability. Obviously, some local searchers are more suitable for some problems than others. Adaptive MAs use a set of predefined local searchers and select the one that seems more appropriated at each decision point. Algorithm UACOR-c [18] belongs to the family of MA with a pool of local searchers, including CMA-ES. UACOR-c employs ant colony optimization for global exploration of the search space.

The covariance matrix adaption evolutionary strategy (CMA-ES) is, by far, the most used local searcher for continuous optimization whenever a single local search mechanism is used. MA-LSCh-CMA [24] is an advanced memetic algorithms based on steady-state GA and CMA-ES. The algorithm employs the concept of local search chains. In a sense, this is similar to resume exploitation of an individual in the exact point where it was left in a previous local search occasion. IPOP-CMA-ES [1] and UACOR-c [18] are two other examples of memetic algorithms that resorts to CMA-ES. Pro-SaDE and Pro-DEGL [7] are two algorithms that resort to differential evolution (DE) instead of CMA-ES.

More recently, memetic differential evolution and its variants have been study in [19, 3], In this approach each new point generated by Differential Evolution is subject to refinement by local search. The work in [15] discusses and compares memetic algorithms in the context of both conventional and multi-agent based evolutionary algorithms.

3. Background

This section starts by formulating the type of problem we are aiming at solving and reviews the framework required for the proposed algorithms.

3.1 Problem formulation

The problem we are interested in can be formulated as follows. Let $\vec{x}$ be a vector of $D$ design variables $\vec{x}=(x_{1},\ldots,x_{j},\ldots,x_{D})$ . Each continuous variable is bounded, i.e., $x_{j}\in[L_{j},U_{j}]$ . The Cartesian product defined over the design variable domains is called the search space. Let $f:\operatorname*{\mathbb{R}}^{D}\rightarrow\operatorname*{\mathbb{R}}$ be real-valued function, i.e., $\vec{x}\rightarrow f(\vec{x})$ , find $\vec{x}^{*}\in\operatorname*{\mathbb{R}}^{D}$ with the small (or large) possible value of $f$ (not necessarily a global extreme).

Notice that this formulation is quite general. The only implicit requirement for $f$ is that search points $\vec{x}$ can be freely evaluated. It does not require a differentiable $f$ , e.g., its gradient may not be available. Moreover, besides non-smooth, $f$ can be non-linear, non-convex, non-separable, multimodal, ill-conditioned or noisy. A search cost can be defined as the number of evaluated search points.

3.2 CMA-ES as local searcher

The covariance matrix adaptation evolution strategy (CMA-ES) [10] is a well-known, powerful, and state-of-the-art evolution strategy that will be adopted here as a local searcher in the proposed memetic algorithm. Endowing memetic algorithms with CMA-ES is not a novelty. For example, memetics algorithms such as IPOP-CMA-ES [1], MA-LSCh-CMA [24], or UACOR-c [18] also adopt CMA-ES as a local searcher. However, the proposed hybridization using CMA-ES is a novelty that, as it will be shown below, it is quite relevant.

Although well-known, CMA-ES is now summarized for completeness. The ( $\mu$ , $\lambda$ )-CMA-ES adopted here is an iterative population based algorithm evolving $\mu$ real-valued individuals in each generation $i$ . From these $\lambda\geqslant\mu$ offsprings are generated, i.e., sampled from a multivariate normal distribution. More concretely, the new $k$ -th offspring $\vec{x}_{k}[i+1](k=1,\ldots,\lambda)$ is s.t.:

$\displaystyle\vec{x}_{k}[i+1]\sim\operatorname*{\mathcal{N}}(\vec{m}[i],\sigma% [i]^{2}C[i])\sim\vec{m}[i]+\sigma[i]\operatorname*{\mathcal{N}}(0,C[i])$ (1)

where $\vec{m}[i]$ is the the mean vector in generation $i$ , $\sigma[i]$ , is the so-called step size and controls the step length, and $C[i]$ is the current covariance matrix that determines the shape of the distribution ellipsoid. $\operatorname*{\mathcal{N}}(\mu,\sigma)$ stands for a normal (Gaussian) distribution with mean $\mu$ and standard deviation $\sigma$ .

Given $\lambda\geqslant\mu$ offsprings, $\mu$ best ones are selected and used to update the mean value $\vec{m}[i+1]$ as well as the covariance matrix and the step-size. Algorithm Appendix A in Appendix A specifies the CMA-ES.

3.3 The Wang algorithm

In the canonical genetic algorithm (GA) crossover and mutation operators are applied with pre-defined probabilities, typically named $p_{c}$ and $p_{m}$ , respectively. In [31] Wang proposed an interesting GA variant for the subset sum problem, a kind of the knapsack problem. In the Wang GA variant, variation operators are applied conditionally rather than using probabilities. In particular, crossover is applied whenever a difference degree $d$ between a pair of selected individuals from the population (the parents), is greater than a pre-defined threshold $\tau$ . The difference degree takes values in the unit interval and measures the difference between the parent genomes as follows:

$d=\frac{\delta}{L}$ (2)

where $\delta$ is the number of different genes in the homologous positions in the parent chromosomes, and $L$ is the length (number of bits) of the chromosomes. For instance, $d(``010",``111")=2/3$ .

Should the selected parents failed the difference test, the mutation operator is applied to one of them and the mutated individual is viewed as a new offspring. The whole process is repeated until the number of offsprings equals a pre-defined population size. Algorithm 3.3 presents a specification of this process.

The Wang algorithm: a GA that prefers mating dissimilar genomes [31].InputInput OutputOutput Population size: $N$ ; Genomic difference threshold: $\tau$ ; Max number of generations: $M$

Output the fittest individual in the population Randomly initialize the population with $N$ individuals i = 1 M The number of offspring equals $N$ Select a pair of individuals from the population (the parents) Compute the difference degree $d$ between the parents using (2) ( $d>\tau$ ) Create two offsprings by applying crossover to the parents Create one offspring by mutating one of the parents Replace the old population with offsprings.

Clearly the user-defined threshold $\tau$ controlling the applicability of variation operators plays a crucial role in the performance of the algorithm. On the one hand, a $\tau$ close to 1 only allows exchange of genetic material between parents with very different genomes. On the other hand, as $\tau$ tends to zero crossover occurs for almost any pair of parents, independently of their genomic difference and, therefore, less and less mutations occur.

While the former case is desirable in the initial generations of the algorithm the latter becomes more convenient in the final generations when there are individuals in the population representing values near the solution of the optimization problem. For dealing with this issue, in [31, 32] $\tau$ is adjusted from generation $i$ to the next according to $\tau[i+1]=Q\tau[i]$ where $Q\in(0,1)$ is an user-defined hyper-parameter called cooling ratio.

4. The proposed improvement to the Wang algorithm

Despite the above efforts, the problem of setting the initial $\tau[i=0]$ remains. On the one hand this hyper-parameter is problem dependent. On the other hand, a poor guest of $\tau[i=0]$ severely degrades the performance of the whole algorithm. To address this critical issue, in this work we propose an improvement to the original Wang algorithm as follows. Let $\bar{d}$ be the average difference degree computed over all the parent pairs selected from the current population. We set the initial threshold $\tau[i=0]$ to $\bar{d}$ and use it for say $g$ generations ( $g<M$ ; $M$ being the user-defined maximum number of generations). After these $g$ generations a new value of $\bar{d}$ is computed and used to reinitialize $\tau$ . Between $\tau$ reinitializations, cooling is still applied. Algorithm 4 specifies the improved Wang algorithm.

An improved Wang algorithm: mating dissimilar genomes with adaptive difference thresholds.InputInput OutputOutput Population $\mathbf{P}$ with $N$ individuals Max number of generations: $M$ ; Number of generations for resetting $\tau$ : $g<M$ Cooling ratio: $Q$

Output the fittest individual in the population

i = 0 M-1 ( $i\mbox{ mod }g==0$ ) Compute the average difference degree $\bar{d}$ over all parent pairs selected from $\mathbf{P}$ $\tau[i]=\bar{d}$ $\tau[i]=Q\tau[i-1]$ // cooling The number of offspring equals $N$ Select a pair of parents from $\mathbf{P}$ Compute the difference degree $d$ between the parents ( $d>\tau[i]$ ) Create two offsprings by applying crossover to the parents Create one offspring by mutating one of the parents Replace $\mathbf{P}$ with offsprings.

Although simple to implement, the proposed improvement addresses some critical issues of the original Wang algorithm: 1) it sets automatically an otherwise user-defined, problem-dependent parameter the threshold $\tau$ – this prevents the annoying trial-and-error process of parameter tuning each time the algorithm is applied. As mentioned, $\tau$ controls the applicability of variation operators and plays thus a crucial role in the performance of the algorithm. 2) by setting dynamically the threshold $\tau$ the proposed mechanism allows for an adaptive evaluation of the difference between individual genomes in a way that is independent of the optimization problem, and 3) it takes into account the stage of the evolutionary process. Less crossover, more mutation in the beginning and more crossover, less mutation towards the end due to cooling.

Moreover, Algorithm 4 is general enough to be used with binary, integer, permutations, or real-valued chromosomes. Once the chromosome representation is selected, appropriated definitions of difference degree, crossover, and mutation operators can be established. Next subsections describe the adopted operators for the real-valued case.

4.1 Defining the difference degree for real-valued chromosomes

Let $\vec{p}_{i}\in\operatorname*{\mathbb{R}}^{D}(i=1,2)$ , i.e.,

$\vec{p_{i}}=(p_{i,1},\ldots,p_{i,j},\ldots,p_{i,D})$ (3)

be a pair of real-valued parents with $L$ being the length of the chromosomes. The difference-degree, $d$ , between the real-valued parents is defined as:

$d=\frac{|\vec{e}_{1}-\vec{e}_{2}|}{2}$ (4)

where $\vec{e}_{1}=\vec{p}_{1}/|\vec{p}_{1}|$ , $\vec{e}_{2}=\vec{p}_{2}/|\vec{p}_{2}|$ and $|\vec{e}_{1}-\vec{e}_{2}|$ is a distance, such as the Euclidean distance, between $\vec{e}_{1}$ and $\vec{e}_{2}$ . It is clear that $d\in[0,1]$ . A similar definition has been used in [4, 6, 5].

4.2 On real-valued variation operators

In an attempt to identify those variation operators that promote population diversity, in this work three crossover operators (BLX- $\alpha$ [8], UNDX [27] and PNX [9]) and one mutation operator (Non-uniform mutation [21]) are considered. These are briefly described below.

4.2.1 BLX- $\alpha$

The BLX- $\alpha$ crossover operator [8] promotes high genomic diversity between parents and offsprings and among offsprings. Consider the definition (3) and let $\max_{j}=\max(\vec{p}_{1j},\vec{p}_{2j})$ , ${\min}_{j}=\min(\vec{p}_{1j},\vec{p}_{2j})$ , and ${I}=\max_{j}-{\min}_{j}$ $(j=1,\ldots,D)$ . The BLX- $\alpha$ randomly generates offspring with the $j$ -th gene within $[{\min}_{j}-\alpha I;{\max}_{j}+\alpha{I}]$ as follows. Let $u$ be uniformly sampled from the unit interval, an offspring $\vec{c}=(c_{1},\ldots,c_{j},\ldots,c_{L})$ is s.t.

$c_{j}=(1-\gamma)p_{1,j}+\gamma p_{2,j}$ (5)

where $\gamma=(1+2\alpha)u-\alpha$ . A typical parameter setting for $\alpha$ is 0.5.

4.2.2 UNDX

In this operator multiple parents are used to create offsprings $\vec{c}_{1},\vec{c}_{2}$ as follows:

$\displaystyle\vec{c}_{1}=\vec{m}+z_{1}\vec{e}_{1}+\sum\limits_{k=2}^{L}{z_{k}% \vec{e}_{k}}$ $\displaystyle\vec{c}_{2}=\vec{m}-z_{1}\vec{e}_{1}-\sum\limits_{k=2}^{L}{z_{k}% \vec{e}_{k}}$ (6) $\displaystyle\vec{m}=\frac{\vec{p}_{1}+\vec{p}_{2}}{2}$ $\displaystyle z_{1}\sim\operatorname*{\mathcal{N}}(0,\sigma^{2}_{1}),z_{k}\sim% \operatorname*{\mathcal{N}}(0,\sigma^{2}_{2})$ $\displaystyle\sigma_{1}=\alpha d_{1},\sigma_{2}=\beta d_{2}/\sqrt{L}$ $\displaystyle\vec{e}_{1}=(\vec{p}_{1}-\vec{p}_{2})/|\vec{p}_{1}-\vec{p}_{2}|$ $\displaystyle\vec{e}_{i}\bot\vec{e}_{j}(i,j=1,2,\ldots,D,i\not=j)$

where $\vec{p}_{i}$ is the $i$ -th parent, $d_{1}=|\vec{p}_{1}-\vec{p}_{2}|$ and $d_{2}$ is the distance from $\vec{p}_{3}$ to $\vec{p}_{1}-\vec{p}_{2}$ ; $\alpha$ and $\beta$ are user-defined hyper-parameters with default values $\alpha=0.5$ and $\beta=0.35$ .

4.2.3 PNX

In this operator, the $j$ -th gene of the offspring $\vec{c}$ , $c_{j}$ is computed as follows:

$\displaystyle c_{j}=\begin{cases}y_{1j},\text{ if }r<0.5\\ y_{2j},\text{otherwise}\end{cases}y_{1j}\sim\operatorname*{\mathcal{N}}(p_{1j}% ,\frac{|p_{2j}-p_{1j}|}{\eta})$ $\displaystyle y_{2j}\sim\operatorname*{\mathcal{N}}(p_{2j},\frac{|p_{2j}-p_{1j% }|}{\eta})$

where $r$ is a [0, 1] uniformly distributed random number, $p_{i,j}$ is the $j$ -th gene of the $i$ -th parent and $\eta$ is an user-defined hyper-parameter. The larger the value of $\eta$ the more centered is the search around the parents. In the following we set $\eta=2$ .

4.2.4 Non-uniform mutation

Given an individual $\vec{x}=(x_{1},\ldots,x_{j},\ldots,x_{L})$ , the mutated individual $\vec{x}^{{}^{\prime}}=(x^{{}^{\prime}}_{1},\ldots,x^{{}^{\prime}}_{j},\ldots,x% ^{{}^{\prime}}_{L})$ is s.t.:

$\displaystyle x^{{}^{\prime}}_{j}=\begin{cases}x_{j}+\triangle(i,x^{r}_{j}-x_{% j})\hskip 11.381102pt\mbox{ if }r\leqslant 0.5\\ x_{j}-\triangle(i,x_{j}-x^{l}_{j})\hskip 11.381102pt\mbox{ otherwise}\end{cases}$

where $r$ is an uniformly distributed random number in [0,1], $x^{l}_{j}$ and $x^{r}_{j}$ are the lower and upper bounds of the $j$ -th gene, respectively, and $i$ is the generation number. The function $\triangle(i,y)$ takes values in the interval $[0,y]$ and is given by:

$\displaystyle\triangle(i,y)=y(1-r^{1-\frac{i}{M}})^{b}$ (7)

where $M$ is the maximum number of generations and $b$ is an user-defined hyper-parameter determining the strength of the mutation and it is set to 4 subsequently.

5. A new memetic algorithm

The section presents the proposed memetic algorithm, i.e., Algorithm 5. The algorithm combines the proposed Algorithm 4 as a global searcher with CMA-ES to exploit the neighborhood of a globally evolved solution. Integration issues such as i) the computational cost balancing among the global and local searchers, ii) communication between local and global searchers, iii) local search chains, and iv) restarting, are addressed next.

The proposed memetic algorithm. See text for details.InputInput OutputOutput Global searcher (Algorithm 4) hyper-parameters Local seacher CMA-ES (Algorithm Appendix A) hyper-parameters Population size: $N$ Number of global search generations: $n_{G}$ Number of local search generations: $n_{L}$ Output the fittest individual in the population

Uniformly initialize a population $\mathbf{P}$ with $N$ individuals

termination condition not met

Apply global searcher Algorithm 4 over $\mathbf{P}$ for $n_{G}$ generations

$\vec{x}$ = fittest individual in $\mathbf{P}$ $\vec{x}^{\prime}$ = nearest individual to $\vec{x}$ in $\mathbf{P}$ remove $\vec{x}$ from $\mathbf{P}$ (state( $\vec{x}$ ) available) CMA-ES hyper-parameters = state( $\vec{x}$ ) Use input CMA-ES hyper-parameters as default CMA-ES $\vec{m}=\vec{x}$ CMA-ES $\sigma=(\vec{x}-\vec{x}^{\prime})/2$ Apply local searcher Algorithm Appendix A (CMA-ES) for $n_{L}$ generations

// Communication from the local to the global searcher $\mathbf{P}_{L}$ = CMA-ES resulting population $x_{L}$ = the fittest individual in $\mathbf{P}_{L}$ Save CMA-ES hyper-parameters as state( $x_{L}$ ) ( // $\mu$ is the size of $\mathbf{P}_{L}$ ; ) $\mu$ $(\mu==N)$ Replace $\mathbf{P}$ with $\mathbf{P}_{L}$ ; $(\mu<N$ ) Randomly replace individuals in $\mathbf{P}$ with those of $\mathbf{P}_{L}$ ; $(\mu>N$ ) Replace $\mathbf{P}$ with the $N$ fittest individuals of $\mathbf{P}_{L}$ ;

(fittest individual in $\mathbf{P}$ stays the same for $n$ consecutive generations) Uniformly initialize population $\mathbf{P}$ with $N$ individuals

5.1 Balancing between global and local search

The overall search cost of a memetic algorithm is related to the number of (fitness) function evaluation. The performance of the algorithm depends on how this search cost is balanced among its global and local searchers. Typically, a local/global search ratio $R_{L/G}$ is defined as $R_{L/G}=\frac{n_{L}}{n_{G}}$ , where $n_{L}$ is the number of function evaluations allowed each time the local searcher is called. Sometimes, this is named local search intensity [24]. Similarly, the global search intensity, $n_{G}$ , is the number of fitness function evaluations allowed each time the global searcher is called. In Algorithm 5 this ratio is user-defined.

5.2 Communications between global and local search

In a memetic algorithm, a form of bidirectional communication between the two searchers is required. In Algorithm 5, global searcher (Algorithm 4) communicates with the local searcher (Algorithm Appendix A) as follows. The memetic algorithm 5 maintains a population $\mathbf{P}$ of $N$ individuals which is shared with the global searcher. After running $n_{G}$ generations, the fittest individual in $\mathbf{P}$ , $\vec{x}$ , is selected, removed from the population, and its neighborhood is further exploited by the local searcher. This is accomplished by setting the mean value $\vec{m}$ of CMA-ES to $\vec{x}$ and by selecting (heuristically) the $\sigma$ of CMA-ES to half the distance between $\vec{x}$ and the $\vec{x}^{\prime}$ the nearest individual to $\vec{x}$ in $\mathbf{P}$ .

Basically, the communication between the local and the global searcher is carryout by integrating the current local population into the global one $\mathbf{P}$ with $N$ individuals. CMA-ES has a population $\mathbf{P}_{L}$ with a user-defined number of individuals $\mu$ . After $n_{L}$ generation, $\mathbf{P}_{L}$ is integrated into $\mathbf{P}$ . The integration of these populations depends on their relative sizes. If $\mu$ is equal to $N$ , $\mathbf{P}_{L}$ simply replaces $\mathbf{P}$ . If $\mu<N$ , $\mu$ individuals are randomly removed from $\mathbf{P}$ and replaced by the individuals of $\mathbf{P}_{L}$ . Alternatively, the $N$ fittest individuals of $\mathbf{P}_{L}$ replace $\mathbf{P}$ . Notice that by doing this, the fittest individual in $\mathbf{P}_{L}$ will always be integrated in $\mathbf{P}$ .

5.3 Local search chains

Algorithm 5 adopts the local search chains as advocated in [24, 22, 23] that consists in the following. Every time the CMA-ES algorithm is applied to refine the fittest individual, $\vec{x}$ , the CMA-ES state is saved. By state we mean the covariance matrix, the step size, and all other auxiliary hyper-parameters described in Appendix A. Whenever a fittest individual is further exploited by CMA-ES, its corresponding state is also restored in CMA-ES, if available. If it is the first time that a given fittest individual is going to be exploited by the local searcher, default values of those hyper-parameters are used.

This is equivalent to resume the exploitation of $\vec{x}$ for multiple $n_{L}$ times and has been shown to be an asset in practice [24, 22, 23].

5.4 Random restarting

As in every evolutionary process, sometimes, stagnation occurs. Restarting is a common remedy for such cases. For such reasons, the proposed algorithm also includes a restarting mechanism. In the event of stagnation in the best solution, for say $n$ successive generations, population $\mathbf{P}$ is randomly reinitialized.

6. Empirical evaluation

In this section an empirical evaluation of the proposed algorithms is provided. In a first moment, the sensitivity of Algorithm 4 to the three crossover operators of Section 4.2 is analyzed. Afterwards, the performance of Algorithm 5 is contrasted with state of the art memetic algorithms.

6.1 Experimental setup

The test suite used in the experimental evaluation consists of 25 benchmark functions that have been used as benchmark functions after the Special Session on Real Parameter Optimization of the 2005 IEEE Congress on Evolutionary Computation. There are five unimodal functions (F ${}_{1}$ –F ${}_{5}$ ) and twenty multimodal ones (F ${}_{6}$ –F ${}_{25}$ ). Multimodal functions are: i) basic multimodal (F ${}_{6}$ –F ${}_{12}$ ); ii) expanded (F ${}_{13}$ and F ${}_{14}$ ); and iii) hybrid composition functions (F ${}_{15}$ –F ${}_{25}$ ). These functions are summarized in Appendix B.

For facilitating the performance comparison of the proposed memetic algorithm with other memetic algorithms available in the literature, the evaluation criteria postulated for the above mentioned Special Session are also adopted here [30]:

•
The population of an algorithm is uniformly initialized within the search space of the test function, except for F ${}_{7}$ and F ${}_{25}$ for which specific ranges exist;
•
An algorithm is ran 25 times over each test function and the average of the error $\bar{e}$ is computed (over the 25 runs) for the fittest individual in the algorithm population. The error value for a solution $\vec{x}$ is defined as $e=|f(\vec{x})-f(\vec{x}^{})|$ , where $\vec{x}^{}$ is the known global minimum of the function;
•
The maximum number of fitness evaluations, allowed for each algorithm run is $\mbox{FE}_{\max}=10^{4}D$ , where $D\in\{30,50\}$ is the number of design variables, i.e., $\vec{x}\in\operatorname{\mathbb{R}}^{D}$ ;
•
Each run stops either when $e<e_{\min}=10^{-8}$ or when the maximal number of evaluations is achieved.
•
A run is termed successful* if the algorithm achieves $e_{\min}$ within $\mbox{FE}_{\max}$ ;
•
The success rate is defined as $SR=\frac{\mbox{number of successful runs}}{\mbox{total runs}}$ .

6.2 Parameter setting

In general, hyper-parameters are problem dependent. Below the used hyper-parameters are enumerated and a brief explanation on how their values were found is given:

•
The (global) population size, $N=30$ ;
•
The cooling ratio of global searcher (Algorithm 4) $Q$ = 0.9;
•
The size of offspring population in CMA-ES, $\lambda=3(4+\mbox{floor}(3\log(D)))$ ;
•
The local/global search ratio $R_{L/G}=$ 5 with $n_{L}=$ 2000;
•
Crossover operator: BLX- ${\alpha}$ with $\alpha=0.5$ (Section 4.2.1);
•
Mutation operator: Non-uniform mutation (Section 4.2.4);

For illustrating purposes, we show how we heuristically tuned $R_{L/G}$ and $n_{L}$ for Algorithm 5 equipped with the BLX- $\alpha$ crossover operator. Table 1 presents the obtained average error, $\bar{e}$ , and the average number of function evaluations FE ${}_{\text{mean}}$ over 25 runs for three pairs $(R_{L/G};n_{L})$ and for functions F ${}_{1}$ –F ${}_{7}$ with $D=30$ only. As we can see, for the pairs $(R_{L/G}=$ 0.5; $n_{L}=500$ ), and ( $R_{L/G}=2;n_{L}=500)$ , Algorithm 5 was not able to reach a success rate of $100\%$ for F ${}_{4}$ –F ${}_{6}$ . However, when $(R_{L/G}=5;n_{L}=2000)$ the algorithm achieves $SR=1$ for all the considered functions. Consequently, we adopt that latter pair of values in all subsequent experiments.

Table 1
Example of the obtained results in preliminary experiments to set the local/global search ratio $R_{L/G}$ in Algorithm 5. See text for details

$(R_{L/G}=0.5;n_{L}=500)$ $(R_{L/G}=2,n_{L}=500)$ $(R_{L/G}=5,n_{L}=2000)$

Fun. $\bar{e}$ FE ${}_{\text{mean}}$ $S R$ $\bar{e}$ FE ${}_{\text{mean}}$ $S R$ $\bar{e}$ FE ${}_{\text{mean}}$ $S R$

F ${}_{1}$ 8.93E-09 1.97E+04 1.00 8.93E-09 9.74E+03 1.00 8.87E-09 1.43E+04 1.00

F ${}_{2}$ 8.98E-09 5.59E+04 1.00 8.78E-09 2.94E+04 1.00 8.86E-09 2.52E+04 1.00

F ${}_{3}$ 8.92E-09 1.42E+05 1.00 8.59E-09 7.04E+04 1.00 8.57E-09 6.36E+05 1.00

F ${}_{4}$ 1.00E-08 2.09E+05 0.44 1.00E-08 6.99E+04 0.60 8.60E-09 2.85E+04 1.00

F ${}_{5}$ 4.97E+03 2.95E+05 0.00 4.97E+03 2.02E+05 0.00 9.29E-09 2.43E+05 1.00

F ${}_{6}$ 1.00E-08 2.01E+05 0.88 1.00E-09 1.08E+05 0.92 8.89E-09 1.02E+05 1.00

F ${}_{7}$ 9.12E-09 4.59E+04 1.00 8.79E-09 2.47E+04 1.00 8.88E-09 2.01E+04 1.00

6.3 On the influence of the different crossover operators

	$(R_{L/G}=0.5;n_{L}=500)$	$(R_{L/G}=2,n_{L}=500)$	$(R_{L/G}=5,n_{L}=2000)$
F ${}_{1}$	8.93E-09	1.97E+04	1.00	8.93E-09	9.74E+03	1.00	8.87E-09	1.43E+04	1.00
F ${}_{2}$	8.98E-09	5.59E+04	1.00	8.78E-09	2.94E+04	1.00	8.86E-09	2.52E+04	1.00
F ${}_{3}$	8.92E-09	1.42E+05	1.00	8.59E-09	7.04E+04	1.00	8.57E-09	6.36E+05	1.00
F ${}_{4}$	1.00E-08	2.09E+05	0.44	1.00E-08	6.99E+04	0.60	8.60E-09	2.85E+04	1.00
F ${}_{5}$	4.97E+03	2.95E+05	0.00	4.97E+03	2.02E+05	0.00	9.29E-09	2.43E+05	1.00
F ${}_{6}$	1.00E-08	2.01E+05	0.88	1.00E-09	1.08E+05	0.92	8.89E-09	1.02E+05	1.00
F ${}_{7}$	9.12E-09	4.59E+04	1.00	8.79E-09	2.47E+04	1.00	8.88E-09	2.01E+04	1.00

Typically, crossover operators play a key role in the global search of memetic algorithms. For this reason, we also studied the performance of Algorithm 5 under the three different crossover presented in Section 4.2. This was done resorting to functions F ${}_{1}$ –F ${}_{7}$ with $D\in\{30;50\}$ . The results are indicated in Table 2.

Table 2
Evaluation of the influence of crossover operators BLX- $\alpha$ , UNDX, and PNX in Algorithm 5

		BLX- $\alpha=0.5$		UNDX		PNX
$D$	Fun	$\bar{e}$	FE ${}_{\text{mean}}$	$\bar{e}$	FE ${}_{\text{mean}}$	$\bar{e}$	FE ${}_{\text{mean}}$
30	F ${}_{1}$	8.80E-09	1.43E+04	8.87E-09	1.43E+04	8.67E-09	1.43E+04
	F ${}_{2}$	8.75E-09	2.53E+04	8.86E-09	2.52E+04	8.99E-09	2.47E+04
	F ${}_{3}$	8.58E-09	6.34E+05	8.57E-09	6.36e+05	9.18E-09	6.32E+05
	F ${}_{4}$	9.16E-09	2.88E+04	8.60E-09	2.85E+04	8.59E-09	2.83E+04
	F ${}_{5}$	9.34E-09	2.43E+05	9.29E-09	2.43E+05	9.30E-09	2.42E+05
	F ${}_{6}$	8.85E-09	1.10E+05	8.89E-09	1.02E+05	8.65E-09	1.01E+05
	F ${}_{7}$	8.79E-09	2.11E+04	8.88E-09	2.01E+04	8.51E-09	2.00E+04
50	F ${}_{1}$	9.01E-09	2.20E+04	8.87E-09	2.17E+04	8.74E-09	2.17E+04
	F ${}_{2}$	8.97E-09	5.61E+04	9.04E-09	5.68E+04	8.93E-09	5.65E+04
	F ${}_{3}$	9.26E-09	1.72E+05	8.87E-09	1.69E+05	9.32E-09	1.68E+05
	F ${}_{4}$	8.94E-09	6.83E+04	9.13E-09	6.83E+04	9.37E-09	6.91E+04
	F ${}_{5}$	9.59E-09	4.34E+05	9.67E-09	4.33E+05	9.57E-09	4.35E+05
	F ${}_{6}$	8.78E-09	2.72E+05	9.10E-09	2.53E+05	9.05E-09	2.62E+05
	F ${}_{7}$	9.15E-09	3.51E+04	8.94E-09	3.39E+04	9.01E-09	3.53E+04

Table 3

Average error $\bar{e}$ over 25 runs for each benchmark function with $D=30$ obtained by Algorithm 5 and five other state-of-the-art memetic algorithms. The minimum (best) values achieved in each function are emphasized in italic

Fun.	Pro-SADE	Pro-DEGL	IPOP-CMA-ES	UACOR-c	MA-LSCh-CMA	Algorithm 5
F ${}_{1}$	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{2}$	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{3}$	2.28E+06	4.20E+04	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{4}$	2.00E-05	1.00E-08	1.11E+04	1.14E+03	1.31E+04	1.00E-08
F ${}_{5}$	5.51E+01	1.91E+01	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{6}$	1.36E+00	1.20E+00	1.00E-08	1.00E-08	1.19E+01	1.00E-08
F ${}_{7}$	4.70E+03	4.69E+03	1.00E-08	1.00E-08	8.87E-04	1.00E-08
F ${}_{8}$	2.10E+01	2.09E+01	2.01E+04	2.00E+04	2.02E+01	2.10E+01
F ${}_{9}$	1.00E-08	3.58E+01	9.38E-01	2.95E+01	7.82E-09	1.28E+01
F ${}_{10}$	1.01E+02	5.18E+01	1.65E+01	2.91E+01	1.83E+01	1.49E+01
F ${}_{11}$	3.37E+01	2.01E+01	5.48E+00	3.82E+01	4.35E+00	3.96E+01
F ${}_{12}$	1.48E+03	2.35E+04	4.43E+04	2.21E+03	7.69E+02	1.22E+06
F ${}_{13}$	2.95E+00	3.40E+00	2.49E+00	2.26E+00	2.34E+00	2.32E+00
F ${}_{14}$	1.29E+01	1.31E+01	1.29E+01	1.32E+01	1.27E+01	1.27E+01
F ${}_{15}$	3.86E+02	3.83E+02	2.08E+02	1.92E+02	3.08E+02	2.00E+02
F ${}_{16}$	6.97E+01	1.76E+02	3.50E+01	6.14E+01	1.36E+02	1.22E+02
F ${}_{17}$	7.20E+01	1.60E+02	2.91E+02	2.87E+02	1.35E+02	1.24E+02
F ${}_{18}$	8.56E+02	9.09E+02	9.04E+02	8.73E+02	8.16E+02	8.15E+02
F ${}_{19}$	8.67E+02	9.10E+02	9.04E+02	8.83E+02	8.16E+02	8.15E+02
F ${}_{20}$	8.52E+02	9.10E+02	9.04E+02	8.78E+02	8.16E+02	8.15E+02
F ${}_{21}$	5.00E+02	6.79E+02	5.00E+02	5.00E+02	5.12E+02	8.57E+02
F ${}_{22}$	9.09E+02	8.04E+02	8.03E+02	8.57E+02	5.26E+02	5.00E+02
F ${}_{23}$	5.00E+02	6.77E+02	5.34E+02	5.34E+02	5.34E+02	8.64E+02
F ${}_{24}$	2.00E+02	9.72E+02	9.10E+02	3.41E+02	2.00E+02	2.09E+02
F ${}_{25}$	1.63E+03	1.64E+04	2.11E+02	2.63E+02	2.11E+02	2.09E+02

Curiously enough, from Table 2 it is not obvious the difference of performance relative to these operators; all operators achieving similar results. As the crossover operators yield different offspring for the same parents, the results of Table 2 may indicate that, by preferring mating individuals with dissimilar genomes, the improved Wang Algorithm 4 is effective as a general searcher being insensitive to type of crossover operator used. This hypothesis is further analyzed bellow.

6.4 Comparison with state-of-the-art memetic algorithms

Figure 1.

Convergence curves (log of the error vs. the number of the function evolutions) relative to each one of the 25 benchmark functions for $D=30$ obtained by the proposed memetic Algorithm 5.

In this section the results of the performance comparison between the proposed memetic algorithm and five other state-of-the-art memetic algorithms are presented in two tables. Tables 3 and 4 show the average error over 25 runs off each benchmark function for $D=30$ and $D=50$ , respectively. The competing algorithms are: Pro-SADE and Pro-DEGL [7], IPOP-CMA -ES [1], UACOR-c [18], and MA-LSCh-CMA [24]. Values lower than $10^{-8}$ are rounded off to $10^{-8}$ . Minimum (best) values achieved in each test function are emphasized in italic. The displayed data for each of the five algorithms were collected from their respective papers, above.

Figure 2.

Convergence curves relative to each one of the 25 benchmark functions for $D=50$ obtained by the proposed memetic Algorithm 5.

Table 4

Average error $\bar{e}$ over 25 runs for each benchmark function with $D=50$ obtained by Algorithm 5 and five other state-of-the-art memetic algorithms. The minimum (best) values achieved in each function are emphasized in italic

Fun.	Pro-SADE	Pro-DEGL	IPOP-CMA-ES	UACOR-c	MA-LSCh-CMA	Algorithm 5
F ${}_{1}$	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{2}$	7.40E-04	1.00E-08	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{3}$	7.82E+05	1.93E+05	1.00E-08	1.00E-08	1.00E-08	1.00E-08
F ${}_{4}$	6.64E+01	1.08E-01	4.68E+05	1.69E+04	3.76E+05	1.00E-08
F ${}_{5}$	1.95E+03	2.23E+03	2.85E+00	1.00E-08	4.88E+00	1.00E-08
F ${}_{6}$	1.15E+01	8.77E-01	1.00E-08	1.00E-08	6.57E+01	1.00E-08
F ${}_{7}$	6.20E+03	6.20E+03	1.00E-08	1.00E-08	2.37E-03	1.00E-08
F ${}_{8}$	2.11E+01	2.11E+01	2.01E+01	2.01E+01	2.05E+01	2.12E+01
F ${}_{9}$	6.61E-01	7.94E+01	1.39E+00	8.18E+01	6.90E-09	3.20E+02
F ${}_{10}$	6.23E+01	9.24E+01	1.72E+00	7.45E+01	3.74E+01	3.02E+02
F ${}_{11}$	6.61E+01	6.14E+01	1.17E+01	1.07E+01	1.08E+01	7.65E+01
F ${}_{12}$	7.34E+03	6.32E+04	2.27E+05	1.27E+04	2.76E+03	6.08E+06
F ${}_{13}$	6.90E+00	5.41E+00	4.59E+00	4.76E+00	3.51E+00	3.37E+01
F ${}_{14}$	2.28E+01	2.26E+01	2.29E+01	2.31E+01	2.23E+01	2.33E+01
F ${}_{15}$	3.96E+02	3.44E+02	2.04E+02	1.74E+02	2.88E+02	2.64E+02
F ${}_{16}$	4.85E+01	1.63E+02	3.09E+01	7.01E+01	6.40E+01	3.25E+02
F ${}_{17}$	1.92E+02	9.36E+01	2.34E+02	3.17E+02	8.32E+01	3.67E+02
F ${}_{18}$	9.05E+02	9.28E+02	9.13E+02	9.08E+02	8.45E+02	8.35E+02
F ${}_{19}$	8.97E+02	9.28E+02	9.12E+02	8.76E+02	8.45E+02	8.36e+02
F ${}_{20}$	9.11E+02	9.29E+02	9.12E+02	8.64E+02	8.41E+02	8.36E+02
F ${}_{21}$	5.00E+02	9.50E+02	1.00E+03	5.00E+02	5.45E+02	7.20E+02
F ${}_{22}$	9.60E+02	9.28E+02	8.05E+02	8.92E+02	5.00E+02	5.00E+02
F ${}_{23}$	5.06E+02	9.35E+02	1.01E+03	5.41E+02	5.81E+02	7.25E+02
F ${}_{24}$	2.00E+02	6.81E+02	9.55E+02	8.26E+02	2.00E+02	2.16E+02
F ${}_{25}$	1.69E+03	1.67E+03	2.15E+02	3.53E+02	5.81E+02	2.15E+02

6.5 Brief discussion

Tables 3 and 4 show that, under the conditions of the study, one can claim that the proposed Algorithm 5 outperforms all the others, independently of $D$ . More concretely, the proposed memetic algorithm achieved a minimum $\bar{e}$ value for 15 out of 25 functions for $D=30$ (Table 3) and for 12 out of 25 function for $D=50$ (Table 4). Under the same criteria, the second best algorithm is MA-LSCh-CMA with minima in 10/25 functions independently of $D$ . For $D=50$ algorithm UACOR-c achieved the same score.

Figures 1 and 2 show the convergence curves yielded by the proposed MA for $D=30$ and $D=50$ , respectively. From these figures one can see that he convergence of the algorithm is, to a great extend, independent of $D$ .

Also, it is worth noting that the proposed algorithm clearly outperformed IPOP-CMA-ES, independently of $D$ . The latter algorithm was the winner of the IEEE Congress on Evolutionary Computation special section competition [1].

Another interesting observation is that the proposed memetic algorithm achieved $\bar{e}\leqslant e_{\min}=10^{-8}$ in functions F ${}_{1}$ –F ${}_{7}$ . No other competitor algorithm achieved a similar result.

Considering the average errors over all benchmark functions, Algorithm 5 performed significantly better than any of the others. It should be stressed that similarly to the proposed Algorithm 5, IPOP-CMA-ES, UACOR-c, and MA-LSCh-CMA all use CMA-ES as a local searcher. Consequently, the performance improvement observed for Algorithm 5 can only be due to synergy between the improved Wang algorithm and CMA-ES, as CMA-ES is common to all four mentioned algorithms.

Although the conditions of the competition are arguably questionable from the statistical test of hypotheses point of view, it is interesting to observe that the best classified algorithms performed well for both $D=30$ and $D=50$ , no matter the functions. This may indicate that this simplified test conditions can be an indicator for the real performance of the algorithms over a variety of real-world continuous optimization problems.

7. Conclusions

This work proposes an adaptive extension of the Wang algorithm that promotes genetic diversity in a population by applying crossover only to parents with sufficient different chromosomes (genomes). This conditional application of variation operators replaces the classical probability based application of these operators. The proposed extension allows for an adaptive evaluation of the genomic difference between individuals in a way that is independent of the optimization problem and takes into account the stage of the evolutionary process. These features are deemed relevant in memetic algorithms where a global searcher is combined with a local searcher for addressing the exploration/exploitation trade-of of evolutionary computation. Consequently, this work also proposes an original and relevant memetic algorithm for continuous optimization combining the adaptive extension of Wang genetic algorithm, for exploration purposes, with the covariance matrix adaptation evolutionary strategy (CMA-ES) for exploitation.

The proposed memetic algorithm was empirically compared against five state-of-the-art memetic algorithms using a classical bench marking function set and has shown superior performance under strict competing comparing conditions. This can be viewed as a strong evidence on the relevance of the proposed algorithms.

Appendix B

This appendix summarizes the 25 functions used in Section 6 for empirical evaluation of the proposed algorithm. These have been used as benchmark functions after the Special Session on Real Parameter Optimization of the 2005 IEEE Congress on Evolutionary Computation. Functions are unimodal (F ${}_{1}$ –F ${}_{5}$ ) and multimodal (F ${}_{6}$ –F ${}_{25}$ ). Within the multimodal, functions are further organized in: i) basic multimodal functions (F ${}_{6}$ –F ${}_{12}$ ); ii) expanded functions (F ${}_{13}$ and F ${}_{14}$ ); and iii) hybrid composition functions (F ${}_{15}$ –F ${}_{25}$ ). The original description of the benchmark function set is available from [30] where properties and further implementation details can be found.

In the following $\vec{x},\vec{z}\in\operatorname*{\mathbb{R}}^{D}$ where $D$ is the number of design variables, e.g., $\vec{x}=(x_{1},\ldots,x_{j},\ldots,x_{D})$ . Each continuous variable is bounded, e.g., $x_{j}\in[L_{j},U_{j}]$ .

•

Unimodal functions

–

Shifted Sphere Function

$\text{F}_{1}(\vec{x})=\sum_{i=1}^{D}{z}_{i}^{2}+b$

where $\vec{z}=\vec{z}-\vec{o}$ , $\vec{o}$ is the shift global optimum and $b=-450$ .

–

Shifted Schwefel’s Problem 1.2

$\text{F}_{2}(\vec{x})=\sum_{i=1}^{D}(\sum_{j=1}^{i}{z}_{j})^{2}+b$

–

Shifted Rotated High Conditioned Elliptic Function

$\text{F}_{3}(\vec{x})=\sum_{i=1}^{D}(10^{6})^{\frac{i-1}{D-1}}{z}_{i}^{2}+b$

–

Shifted Schwefel’s Problem 1.2 with Noise in Fitness

$\text{F}_{4}(\vec{x})=\left(\sum_{i=1}^{D}\left(\sum_{j=1}^{i}{z}_{j}\right)^{% 2}\right)(1+0.4|\operatorname*{\mathcal{N}}(0,1)|)+b$

–

Schwefel’s Problem 2.6 with Global Optimum on Bounds

$\text{F}_{5}(\vec{x})=\max{|\mathbf{A}_{i}\vec{x}-\mathbf{B}_{i}|}+b_{5};i=1,% \ldots,D$

where $\mathbf{A}_{i}$ is a $D\times D$ matrix with random elements and $\mathbf{B}_{i}=\mathbf{A}_{i}\vec{o}$ , $b_{5}=-310$ .

•

Basic Multimodal Functions

–

Shifted Rosenbrock’s Function

$\text{F}_{6}(\vec{x})=\sum_{i=1}^{D-1}(100({z}_{i}^{2}-{z}_{i+1})^{2}+({z}_{i}% -1)^{2})+b_{6};b_{6}=390$

–

Shifted Rotated Griewank’s Function without Bounds

$\text{F}_{7}(\vec{x})=\sum_{i=1}^{D}\frac{{z}_{i}^{2}}{4000}-\prod_{i=1}^{D}% \cos\left(\frac{{z}_{i}}{\sqrt{i}}\right)+1+b_{7};b_{7}=-180$

–

Shifted Rotated Ackley’s Function with Global Optimum on Bounds

$\text{F}_{8}(\vec{x})=-20\exp\left(-0.2\sqrt{\frac{1}{D}\sum_{i=1}^{D}{z}_{i}^% {2}}\right)-\exp\left(\frac{1}{D}\cos(2\pi{z}_{i})\right)+20+e+b_{8};b_{8}=-140$

–

Shifted Rastrigin’s Function

$\text{F}_{9}(\vec{x})=\sum_{i=1}^{D}({z}_{i}^{2}-10\cos(2\pi{z}_{i})+10)+b_{9}% ;\vec{z}=\vec{x}-\vec{o};b_{9}=-330$

•

Shifted Rotated Rastrigin’s Function

$\text{F}_{10}(\vec{x})=\sum_{i=1}^{D}({z}_{i}^{2}-10\cos(2\pi{z}_{i})+10)+b_{1% 0};\vec{z}=(\vec{x}-\vec{o})\mathbf{M}$

where $\mathbf{M}$ is a $D\times D$ transformation matrix condition number 2, and $b_{10}=-330$ .

•

Shifted Rotated Weierstrass Function

$\text{F}_{11}(\vec{x})=\sum_{i=1}^{D}\left(\sum_{k=0}^{kmax}[a^{k}\cos(2\pi b^% {k}({z}_{i}+0.5))]\right)-D\sum_{k=0}^{kmax}[a^{k}\cos(\pi b^{k})]+b_{11}$

where $a=0.5,b=3,kmax=3,b_{11}=90$ , and $\vec{z}=(\vec{x}-\vec{o})\mathbf{M}$ .

•

Schwefel’s Problem 2.13

$\text{F}_{12}(\vec{x})=\sum_{i=1}^{D}(\mathbf{A}_{i}-\mathbf{B}_{i}(\vec{x}))^% {2}+b_{12}$

where $\mathbf{A}_{i}=\sum_{j=1}^{D}(a_{ij}\sin\alpha_{j}+b_{ij}\cos\alpha_{j})$ , $\mathbf{B}_{i}(\vec{x})=\sum_{j=1}^{D}(a_{ij}\sin{x}_{j}+b_{ij}\cos{x}_{j})$ , $a_{ij},b_{ij}$ being integer random numbers in [-100, 100], $b_{12}=-460$ .

•

Expanded Functions

–

Shifted Expanded Griewank’s plus Rosenbrock’s Function (F ${}_{8}$ F ${}_{2}$ )

$\text{F}_{13}(\vec{x})=\text{F}_{8}(\text{F}_{2}({z}_{1},{z}_{2}))+\text{F}_{8% }(\text{F}_{2}({z}_{2},{z}_{3}))+\ldots+\text{F}_{8}(\text{F}_{2}({z}_{D-1},{z% }_{D}))+\text{F}_{8}(\text{F}_{2}({z}_{D},{z}_{1}))+b_{13};$

$b_{13}=-130$

–

Shifted Rotated Expanded Scaffer’s F ${}_{6}$ Function

$\text{F}_{14}(\vec{x})=\text{F}({z}_{1},{z}_{2})+\ldots+\text{F}({z}_{D-1},{z}% _{D})+\text{F}({z}_{D},{z}_{1})+b_{14};b_{14}=-300$

with

$F(x,y)=0.5+\frac{\sin^{2}(\sqrt{x^{2}+y^{2}})-0.5}{(1+0.001(x^{2}+y^{2}))^{2}}$

•

Composition functions

–

Hybrid Composition Function: F ${}_{15}$ is a combination of Rastrigin, Weierstrass, Ackley, and Sphere functions.

–

F ${}_{16}$ is a rotated version of hybrid composition function F ${}_{15}$ .

–

F ${}_{17}$ : F ${}_{16}$ with Noise in Fitness

$\text{F}_{17}=(\text{F}_{16}-b_{16})(1+0.2|\operatorname*{\mathcal{N}}(0,1)|)+% b_{17};b_{17}=120$

–

Rotated Hybrid Composition Function: F ${}_{18}$ is a rotation of Ackley, Rastrigin, Sphere, Weierstrass, and Griewank functions.

–

F ${}_{19}$ : Rotated hybrid composition function with narrow basin global optimum.

–

F ${}_{20}$ : Rotated hybrid composition function with global optimum on the bounds.

–

Rotated Hybrid Composition Function: F ${}_{21}$ is a rotation of the rotated expanded Scaffer, Rastrigin, F ${}_{2}$ F ${}_{8}$ , Weierstrass, and Griewank functions.

–

F ${}_{22}$ is a rotated hybrid composition function like F ${}_{21}$ but with a high condition number matrix.

–

F ${}_{23}$ is non-Continuous rotated hybrid composition function based on F ${}_{21}$ .

–

Rotated Hybrid Composition Function: F ${}_{24}$ is a rotation of the Weierstrass, rotated expanded Scaffer, F ${}_{2}$ F ${}_{8}$ , Ackley, Rastrigin, Griewank, Non-Continuous Expanded Scafferâ€™s F6 Function, Non-Continuous Rastrigin, High Conditioned Elliptic function, and Sphere Function with Noise in Fitness.

–

Rotated Hybrid Composition Function without bounds: F ${}_{25}$ is like F ${}_{24}$ except that no exact search range is set.

Footnotes

Acknowledgments

This work was supported in part by the Scientific and Technological Research Program of Chongqing Municipal Education Commission (No. KJ1500607, KJ1400629), The National Natural Science Foundation of China (Grant No. 61402063, 61502063), the National Key Research and Development Program of China (2016YFE0132200), and CTBU Open Grant No. 1456027. J. V. de Oliveira acknowl-edges the support from FCT (the Portuguese Board of Science and Technology) grant number SFRH/ BSAB/128153/2016.

Appendix A

In this appendix CMA-ES is specified using the notation and terminology of [] where further implementation details and guidance can be found.

The covariance matrix adaption evolution strategy (CMA-ES) [] set $\lambda,\mu,w_{i=1,\ldots,\mu},c_{1},c_{\sigma},c_{\mu}$ set the evolution paths $\mathbf{p}_{\sigma}=0,\mathbf{p}_{c}=0$ set the covariance matrix $C=I$ set the mean $\mathbf{m}\in\operatorname*{\mathbb{R}}^{n}$ and the step-size $\sigma\in\operatorname*{\mathbb{R}}_{+}$

a stop criterion is met k = 1 $\lambda$ // sample new population $\mathbf{y}_{k}\sim\operatorname*{\mathcal{N}}(0,C)$ $\mathbf{x}_{k}=\mathbf{m}+\sigma\mathbf{y}_{k}\sim\operatorname*{\mathcal{N}}(% \mathbf{m},\sigma^{2}C)$

// selection and recombination $\langle\mathbf{y}\rangle_{w}=\sum_{i=1}^{\mu}w_{i}\mathbf{y}_{i:\lambda}$ $\mathbf{m}\leftarrow\mathbf{m}+\sigma\langle\mathbf{y}\rangle_{w}$

// step-size control $\mathbf{p}_{\sigma}\leftarrow(1-c_{\sigma})\mathbf{p}_{\sigma}+\sqrt{c_{\sigma% }(2-c_{\sigma})\mu_{\mbox{eff}}}C^{-\frac{1}{2}}\langle\mathbf{y}\rangle_{w}$ $\sigma\leftarrow\sigma\exp({\frac{c_{\sigma}}{d_{\sigma}}(\frac{||\mathbf{p}_{% \sigma}||}{\mbox{E}||\operatorname*{\mathcal{N}}(0,I)||}-1)})$

// covariance matrix adaptation $\mathbf{p}_{c}\leftarrow(1-c_{c})\mathbf{p}_{c}+h_{\sigma}\sqrt{c_{c}(2-c_{c})% \mu_{\mbox{eff}}}\langle\mathbf{y}\rangle_{w}$

$C\leftarrow(1-c_{1}-c_{\mu})C+c_{1}(\mathbf{p}_{c}\mathbf{p}_{c}^{\mbox{T}}+% \delta(h_{\sigma})C)+c_{\mu}\sum_{i=1}^{\mu}w_{i}\mathbf{y}_{i:\lambda}\mathbf% {y}_{i:\lambda}^{\mbox{T}}$

References

Auger

and Hansen

, A restart CMA evolution strategy with increasing population size, In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, 2005, pp. 1769–1776.

Beyer

H.G.

and Schwefel

H.P.

, Evolution strategies, Natural Computing 1 (2002), 3–52.

Cabassi

and Locatelli

, Computational investigation of simple memetic approaches for continuous global optimization, Computers & Operations Research 72 (2016), 50–70.

Chen

Z.Q.

and Wang

R.L.

, A new framework with fdpp-lx crossover for real-coded genetic algorithm, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94.A(6) (2011), 1417–1425.

Chen

Z.Q.

and Wang

R.L.

, Solving m-way graph partitioning problem using genetic algorithm, IEEJ Transactions on Electrical and Electronic Engineering 6 (2011), 483–489.

Chen

Z.Q.

and Wang

R.L.

, Two efficient real-coded genetic algorithms for real parameter optimization, International Journal of Innovative Computing, Information and Control 7(8) (2011), 4871–4883.

Epitropakis

Tasoulis

Pavlidis

Plagianakos

and Vrahatis

, Enhancing differential evolution utilizing proximity-based mutation operators, IEEE Transactions on Evolutionary Computation 15(1) (2011), 99–119.

Eshelman

L.J.

and Schaffer

J.D.

, Real-coded genetic algorithms and interval schemata, in: Foundation of Genetic Algorithms II Whitley

D.L.

, (Ed.), Morgan Kaufmann, 1992.

Eshelman

L.J.

and Schaffer

J.D.

, An effective real-parameter genetic algorithm with parent centric normal crossover for multimodal optimization, In: Lecture Notes in Computer Science 3102, K. Deb et al., Springer, 2004.

10.

Hansen

and Ostermeier

, Completely derandomized self-adaptation in evolution strategies, Evolutionary Computation 9(2) (2001), 159–195.

11.

Hansen

, The CMA evolution strategy: A comparing review, In Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms Lozano

J.A.

Larrañaga

Inza

and Bengoetxea

, eds, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 75–102.

12.

Hart

W.E.

Krasnogor

and Smith

J.E.

, Editorial introduction special issue on memetic algorithms, Evolutionary Computation 12(3) (Sept 2004), v–vi.

13.

Hart

W.E.

Krasnogor

and Smith

J.E.

, Recent advances in memetic algorithms, Studies in Fuzzyness and Soft Computing Series, Springer, New York: Heidelberg, 2004.

14.

Kennedy

and Eberhart

R.C.

, Particle swarm optimization, In Proceedings of the IEEE International Conference of Neural Networks, 1995, pp. 1942–1948.

15.

Korczynski

Byrski

and Kisiel-Dorohinicki

, Buffered local search for efficient memetic agent-based continuous optimization, Journal of Computational Science (2017).

16.

Krasnogor

and Smith

J.E.

, A tutorial for competent memetic algorithms: Model, taxonomy, and design issue, IEEE Transactions on Evolutionary Computation 9(5) (2005), 474–488.

17.

Lee

C.Y.

and Yao

, Evolutionary programming using mutations based on the levy probability distribution, IEEE Transactions on Evolutionary Computation 8(1) (2004), 1–13.

18.

Liao

and Stützle

, A unified ant colony optimization algorithm for continuous optimization, European Journal of Operational Research 234 (2014), 597–609.

19.

Locatelli

Maischberger

and Schoen

, Differential evolution methods based on local searches, Computers & Operations Research 43 (2014), 169–180.

20.

Locatelli

and Schoen

, Global Optimization: Theory, Algorithms, and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2013.

21.

Michalewicz

, Genetic Algorithms + Data Structures = Evolution Programs, Springer, New York, 1992.

22.

Molina

Lozano

and Herrera

, MA-SW-Chains: Memetic algorithm based on local search chains for large scale continuous global optimization, 2010.

23.

Molina

Lozano

Sánchez

A.M.

and Herrera

, Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SW-Chains, Soft Computing 15(11) (2011), 2201–2220.

24.

Molina

Lozano

Garcia-Martinez

and Herrera

, Memetic algorithms for continuous optimisation based on local search chains, Evolutionary Computation 18(1) (2010), 27–63.

25.

Neri

and Cotta

, Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2 (2012), 1–14.

26.

Ong

Y.S.

Krasnogor

and Ishibuchi

, Special issue on memetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 37(1) (2007), 2–5.

27.

Ono

and Kobayashi

, A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover, in: Proceedings of the Seventh International Conference on Genetic Algorithms, 1997, pp. 246–253.

28.

Smith

J.E.

, Coevolving memetic algorithms: A review and progress report, IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics 37(1) (2007), 6–17.

29.

Storn

and Price

K.V.

, Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization 11(4) (1997), 341–359.

30.

Suganthan

P.N.

Hansen

Liang

J.J.

Deb

Chen

Y.P.

Auger

and Tiwari

, Problem definitions and evaluation criteria for the CEC 2005 special session on real parameter optimization, Nanyang Technological University, 2005.

31.

Wang

R.L.

, A genetic algorithm for subset sum problem, Neurocomputing 57 (2004), 463–468.

32.

Wang

R.L.

and Okazaki

, An improved genetic algorithm with conditional genetic operators and its application to set-covering problem, Soft Computing 11 (2007), 687–694.

An adaptive genomic difference based genetic algorithm and its application to memetic continuous optimization

Abstract

Keywords

1. Introduction

3. Background

3.1 Problem formulation

3.2 CMA-ES as local searcher

4.1 Defining the difference degree for real-valued chromosomes

4.2.1 BLX- α

4.2.4 Non-uniform mutation

5.1 Balancing between global and local search

5.2 Communications between global and local search

5.3 Local search chains

5.4 Random restarting

6. Empirical evaluation

6.1 Experimental setup

Table 2 Evaluation of the influence of crossover operators BLX- α , UNDX, and PNX in Algorithm 5

7. Conclusions

Appendix B

Footnotes

Acknowledgments

Appendix A

References

4.2.1 BLX- $\alpha$

Table 2
Evaluation of the influence of crossover operators BLX- $\alpha$ , UNDX, and PNX in Algorithm 5