A niching chaos optimization algorithm for multimodal optimization

Abstract

Niching is the technique of finding and preserving multiple stable niches, or favorable parts of the solution space possibly around multiple optima, for the purpose of solving multimodal optimization problems. Chaos optimization algorithm (COA) is one of the global optimization techniques, but as far as we know, a niching variant of COA has not been developed . In this paper, a novel niching chaos optimization algorithm (NCOA) is proposed. The circle map with a proper parameter setting is employed considering the fact that the performance of COA is affected by the chaotic map. In order to achieve niching, NCOA utilizes several techniques including simultaneously contracted multiple search scopes, deterministic crowding and clearing. The effects of some components and parameters of NCOA are investigated through numerical experiments. Comparison with other state-of-the-art multimodal optimization algorithms demonstrates the competitiveness of the proposed NCOA.

1 Introduction

Many practical scientific and engineering problems could be considered as multimodal optimization problems. Concerning these problems, it is often desirable to simultaneously find all or most of the multiple global and local optima instead of a single optimum and then to choose the most appropriate solution on the basis of practical issues.

Niching (Yu and Suganthan 2010) refers to the technique of finding and preserving multiple stable niches, or favorable parts of the solution space possibly around multiple optima, with a view of preventing convergence to a single optimum. Many niching methods have been developed in last two decades, including crowding (Sareni and Krähenbühl 1998), fitness sharing (Miller and Shaw 1996), speciation (Li et al. 2002), clearing (Pétrowski 1996), ABSE (Xu et al. 2015). Moreover, many niching evolutionary algorithms (EAs) were developed, such as species-based PSO (Parrott and Li 2006), FER-PSO (Li 2007), LIPS (Qu et al. 2013), lbest PSO with a ring topology (Li 2010), FER-DE (Liang et al. 2014), NGKA (Sheng et al. 2010), Niching GSA (Yazdani et al. 2014), TSC (Stoean et al. 2010). But the issues, such as large size of population, low convergence speed and low success rate, still remain challenges for these niching algorithms.

Chaos optimization algorithm (COA) (Li and Jiang 1998) is one of the global optimization techniques, which utilizes chaotic numerical sequences. COA has some positive features such as easy implementation, short execution time and robust mechanism of escaping from the local optimum (Yuan et al. 2012). The effects of chaotic maps were investigated by Yang et al. (2007) and Tavazoei and Haeri (2007). To improve the performance of COA, parallel COA was proposed (Yuan et al. 2015) and hybrid approaches with other search techniques were developed (Yuan et al. 2012, 2014). But, as far as we know, a niching variant of COA has not been developed .

In this paper, a niching chaos optimization algorithm (NCOA) is proposed for solving multimodal optimization problems. In view of the fact that the computational efficiency of COA is affected by the chaotic maps, NCOA employs the circle map with a proper parameter setting rather than the logistic map that commonly used in COA. NCOA is a population-based parallel COA, and in order to achieve niching, several techniques including simultaneously contracted multiple search scopes, deterministic crowding (Sareni and Krähenbühl 1998) and clearing (Pétrowski 1996) are utilized in NCOA. The effects of some components of NCOA are investigated through numerical experiments, and reasonable parameter settings are recommended. The performance of NCOA is demonstrated by comparing with seven other state-of-the-art niching algorithms on a set of commonly used multimodal optimization problems. The experimental results claim that NCOA has competitive capability (small size of population, high convergence speed and high success rate) for multimodal optimization.

The rest of the paper is organized as follows: Sect. 2 briefly reviews the previous researches on COAs with a viewpoint of developing a niching variant of COA. Then the proposed NCOA approach is introduced in Sect. 3. The performance of NCOA is analyzed through numerical experiments in Sect. 4. Finally, the paper is concluded in Sect. 5.

2 Chaos optimization algorithms (COAs)

Consider the optimization problem for (multimodal) objective function with boundary constraints:

$$\begin{aligned}&\max \quad f(\varvec{x})=f(x_{1},x_{2},\ldots ,x_{n})\nonumber \\&\mathrm {s.t.}\quad {\text {lb}}_{i}\le x_{i}\le {\text {ub}}_{i} \quad (i=1,2,\ldots ,n) \end{aligned}$$

(1)

where $f$ is a objective function,  $\varvec{x}=(x_{1},x_{2}, \ldots ,x_{n})^{\mathrm {T}}\in \mathbb {R}^{n}$ is a vector in the $n$-dimensional search space, and  ${\text {LB}}=({\text {lb}}_{1},{\text {lb}}_{2},\ldots ,{\text {lb}}_{n})$ and ${\text {UB}}=({\text {ub}}_{1},{\text {ub}}_{2},\ldots ,{\text {ub}}_{n})$ are lower and upper boundaries of the decision variables, respectively.

Chaos optimization algorithm (COA) is a global optimization technique, which utilizes numerical sequences generated by means of chaotic maps. The pseudo-code of COA (Yang et al. 2007; Tavazoei and Haeri 2007) can be illustrated as Algorithm 1. In that, $\varvec{z}^{k},\, k=0,1,2,\ldots$ is a $n$-dimensional chaos variable, $\varvec{x}^{k}, k=0,1,2,\ldots$ is a feasible solution, $ChaosMap$ is a chaos map, and $LinearMap$ is a linear map that maps chaos variables into search space.

From the first article (Li and Jiang 1998) on COA was reported, the research on COAs has been advanced in three branches.

First, the effects of chaos maps on the performance of COA have been investigated. The first version of COA used the logistic map (May 1976) defined as Eq. (2).

$$\begin{aligned} z^{k+1}= \mu z^{k}(1-z^{k}),\, z^{k}\in (0,1),\quad 0<\mu \le 4 \end{aligned}$$

(2)

where $\mu$ is a control parameter. When $\mu =4$, numerical sequence generated by the logistic map is chaotic, and its probability density function (PDF) $\rho (z)$ and the Lyapunov exponent (LE) can be derived as Eqs. (3) and  (4), respectively:

$$\begin{aligned} \rho (z)= & {} \frac{1}{\pi \sqrt{z(1-z)}} \end{aligned}$$

(3)

$$\begin{aligned} \text {LE}= & {} \lim _{n\rightarrow \infty }\frac{1}{n}\sum _{k=0}^{n}\ln |f'(z^{k})|=0.6931 \end{aligned}$$

(4)

The PDF of chaotic sequences of the logistic map is shown in Fig. 1a, and a chaotic sequence of the logistic map in two-dimensional space $(z^{1},z^{2})$ is shown in Fig. 1b.

Fig. 1

The PDF and the chaos sequence of the logistic map. a The PDF of the logistic map. b The chaos sequence of the logistic map

Yang et al. (2007) and Chen et al. (2011) noticed that the PDF of the logistic map rapidly increases near two ends of the interval $(0,1)$, and so numerous searches are close to the two ends. This may reduce the computational efficiency and global searching capability. Therefore, they proposed the improved logistic map to flatten the PDF of the logistic map. Tavazoei and Haeri (2007) and Yang et al. (2014) introduced several chaos maps that can be used as search pattern in COAs and compared them based on numerical simulation. They also recommended to adopt an appropriate chaotic map generating chaotic sequences with a uniform or nearly uniform PDF and a large LE such as the circle map. But they have not discussed the effects of control parameters of the circle map.

Second, parallel version of COA was proposed. An essential feature of chaotic sequence is the sensitivity on initial condition, that is, a small perturbation on the starting value leads to vastly different future behavior. Therefore, COAs’ performance is usually affected by starting values. To overcome this limitation, Yuan et al. (2012, (2014, (2015) proposed mutative-scale parallel COA (MPCOA). In MPCOA, a population (a set of feasible solutions) (Pop) is reserved and updated:

$$\begin{aligned} \mathrm{{Pop}} = \begin{bmatrix} \varvec{x}_{1}^{*},\ldots ,\varvec{x}_{p}^{*},\ldots ,\varvec{x}_{N}^{*} \end{bmatrix} = \begin{bmatrix} x_{11}^{*}&\cdots&x_{1p}^{*}&\cdots&x_{1N}^{*} \\ \vdots&\ddots&\vdots&\ddots&\vdots \\ x_{i1}^{*}&\cdots&x_{ip}^{*}&\cdots&x_{iN}^{*} \\ \vdots&\ddots&\vdots&\ddots&\vdots \\ x_{n1}^{*}&\ldots&x_{np}^{*}&\cdots&x_{nN}^{*} \end{bmatrix}\nonumber \\ \end{aligned}$$

(5)

where $i=\lbrace 1,2,\ldots ,n\rbrace$ represents the index of decision variable of the objective function and $p=\lbrace 1,2,\cdots ,N\rbrace$ represents the index of individual in the population. The $p$th individual (feasible solution) $\varvec{x}_{p}^{*}$ is represented by:

$$\begin{aligned} \varvec{x}_{p}^{*} = \begin{bmatrix} x_{1p}^{*},\ldots ,x_{ip}^{*},\ldots ,x_{np}^{*} \end{bmatrix}^{\mathrm {T}},\quad p=1,2,\ldots ,N \end{aligned}$$

(6)

The objective function is evaluated on each individual and represented by:

$$\begin{aligned} F^{*}&=\begin{bmatrix} f_{1}^{*},\ldots ,f_{p}^{*},\ldots ,f_{N}^{*} \end{bmatrix}\nonumber \\&=\begin{bmatrix} f(\varvec{x}_{1}^{*}),\ldots ,f(\varvec{x}_{p}^{*}),\ldots ,f(\varvec{x}_{N}^{*}) \end{bmatrix} \end{aligned}$$

(7)

The best individual is represented as:

$$\begin{aligned} \varvec{x}^{*}=\varvec{x}^{*}_{q},\quad q=\arg \max _{1\le p\le N} f^{*}_{p} \end{aligned}$$

(8)

The search scopes of all of the individuals are equal and represented as Eq. (9).

$$\begin{aligned} {\text {LB}}'= & {} ( {\text {lb}}'_{1},\ldots ,{\text {lb}}'_{i},\ldots ,{\text {lb}}'_{n} )^{\text {T}}\nonumber \\ {\text {UB}}'= & {} ( {\text {ub}}'_{1},\ldots ,{\text {ub}}'_{i},\ldots ,{\text {ub}}'_{n} )^{\text {T}} \end{aligned}$$

(9)

where ${\text {lb}}'_{i}$ and ${\text {ub}}'_{i}$ are the lower and upper boundaries of the $i$th decision variable and represented as Eq. (10).

$$\begin{aligned}&{\text {lb}}'_{i}=\max \lbrace x_{i}^{*} - \varPhi ({\text {ub}}_{i} - {\text {lb}}_{i} ), {\text {lb}}_{i} \rbrace \nonumber \\&{\text {ub}}'_{i}=\min \lbrace x_{i}^{*} + \varPhi ({\text {ub}}_{i} - {\text {lb}}_{i} ), {\text {ub}}_{i} \rbrace ,\, i=1,2,\ldots ,n \end{aligned}$$

(10)

where $x_{i}^{*}$ is a $i$th decision variable of the best individual $\varvec{x}^{*}$ and $\varPhi$ is a parameter called the contraction factor. In Eq. (10), to avoid search scopes exceeding the boundaries of the original search space, they are restricted to those boundaries.

The contraction factor $\varPhi$ is gradually reduced so as to improve the accuracy of solutions, and several contraction patterns have been proposed. In Yuan et al. (2014, (2015), the contraction factor is defined as:

$$\begin{aligned} \varPhi =\left( \frac{S-l}{S} \right) ^{4} \end{aligned}$$

(11)

where $l$ is a iteration number and $S$ is a maximum number of iteration allowed. And in  Yuan et al. (2012), the contraction factor is defined as:

$$\begin{aligned} \varPhi = \left\{ \begin{array}{ll} \displaystyle 1-\left( \frac{l-S_{1}}{l} \right) ^{2}, &{}\quad l\ge S_{1} \\ 1, &{}\quad l<S_{1} \end{array} \right. \end{aligned}$$

(12)

where $S_{1}$ is normally selected to (0.05–0.2 S). But they have not presented the theoretical validity for these contraction patterns. It can also be noticed that in MPCOA approach, the search scopes of all of the individuals are equal, and therefore, at the end of search process, all of the individuals are converged to one solution.

Finally, hybrid approaches were researched. Several hybrid approaches are listed in Table 1.

In all of the hybrid approaches, COA takes charge of global search and companions are of local search. This is based on the consideration that COAs’ local search capability is generally bad. The motion steps of chaotic variables between two successive iterations are commonly big, which causes feasible solutions to jump far away in the search space. Thus, even if COA has approached around the optimum, it may need to spend much computational effort to reach the optimum eventually (Yang et al. 2007). But this limitation can be overcome by using appropriate contraction pattern without any other local searcher.

Based on the study of earlier researches on COAs, we propose niching variant of COA. First of all, the effect of control parameters of the circle map is investigated and reasonable values of parameters are selected. For the purpose of niching, each individual of the population has own search scope and is converged various solution by using niching techniques including deterministic crowding and clearing. Moreover, to assure that NCOA has good capability of not only exploration but also exploitation, optimal contraction pattern is utilized. The details of NCOA are presented in the next section.

Table 1 Hybrid approaches with COAs

Fig. 2

The PDF and chaos sequences of the circle map with different parameter settings. a The PDF and a chaos sequence of the circle map with the parameter $\varOmega =0.5, K=3$. b The PDF and a chaos sequence of the circle map with the parameter $\varOmega =0.5, K=7$. c The PDF and a chaos sequence of the circle map with the parameter $\varOmega =0.5, K=11$

3 The niching chaos optimization algorithm (NCOA)

3.1 The effect of control parameters of the circle map

The circle map (Devaney 2003) is a one-dimensional map expressed as:

$$\begin{aligned} z^{k+1}=z^{k}+\varOmega -\frac{K}{2\pi }\sin (2\pi z^{k})\bmod 1 \end{aligned}$$

(13)

The circle map exhibits very unexpected behavior as a function of parameters $\varOmega$ and $K$. In the case in which the parameter $\varOmega$ is fixed to $\varOmega =0.5$, the relation between the LE and the parameter $K$ is shown in Table 2, and the PDF and chaotic sequences in two-dimensional space are illustrated in Fig. 2. Table 1 and Fig. 2 show that not only the LE of the circle map gets bigger, but also the PDF of the chaos sequence becomes more uniform with an increase in the parameter $K$. So, the circle map with the parameters $\varOmega =0.5, K=11$ is employed for the proposed NCOA.

Table 2 The relation between the LE and the parameter $K$ of the circle map ($\varOmega =0.5$)

3.2 Simultaneously contracted multiple search scopes

To accomplish niching, search scopes should be simultaneously contracted at each individual rather than only at the best one in the current population. That is, there coexist $N$ search scopes centered on each individual, and they are gradually contracted during search process (Fig. 3).

The search scope of the $p$th individual is expressed as Eq. (14) and Eq. (15).

$$\begin{aligned} {\text {LB}}'_{p}= & {} ( {\text {lb}}'_{1p},\ldots ,{\text {lb}}'_{ip},\ldots ,{\text {lb}}'_{np} )^{\text {T}}\nonumber \\ {\text {UB}}'_{p}= & {} ( {\text {ub}}'_{1p},\ldots ,{\text {ub}}'_{ip},\ldots ,{\text {ub}}'_{np} )^{\text {T}},\quad p=1,2,\ldots ,N \end{aligned}$$

(14)

$$\begin{aligned} {\text {lb}}'_{ip}= & {} \max \lbrace x_{ip}^{*} - \varPhi ({\text {ub}}_{i} - {\text {lb}}_{i} ), {\text {lb}}_{i} \rbrace \nonumber \\ {\text {ub}}'_{ip}= & {} \min \lbrace x_{ip}^{*} + \varPhi ({\text {ub}}_{i} - {\text {lb}}_{i} ), {\text {ub}}_{i} \rbrace ,\quad i=1,2,\ldots ,n\nonumber \\ \end{aligned}$$

(15)

where ${\text {lb}}'_{ip}$ and ${\text {ub}}'_{ip}$ are the lower and upper boundaries of the $i$th decision variable of the $p$th individual.

A chaos variable $\varvec{z}=(z_{1},\ldots ,z_{i},\ldots ,z_{n})$ is mapped onto the search scope of the $p$th individual by using Eq. (16):

$$\begin{aligned}&x_{i}= {\text {lb}}'_{ip} + z_{i} \times ( {\text {ub}}'_{ip} - {\text {lb}}'_{ip} ), \nonumber \\&\qquad i=1,2,\ldots ,n;\; p=1,2,\ldots ,N \end{aligned}$$

(16)

where the index of individual $p$ is selected in order. As a result, a chaos variable $\varvec{z}=(z_{1},\ldots ,z_{i},\ldots ,z_{n})$ is mapped to a new feasible solution $\varvec{x}=(x_{1},\ldots ,x_{i},\ldots ,x_{n})$ that lies in the hypercube $\prod _{i=1}^{n}[{\text {lb}}'_{ip},{\text {ub}}'_{ip}]$ centered at the $p$th individual $\varvec{x}_{p}^{*}$.

According to the optimal contraction theorem (Chen et al. 2009), in an optimal contraction way, the whole search cost is evenly distributed in all contraction stages, and each contraction takes the same contracting ratio. In other words, the uniform contraction pattern is optimal. Furthermore, more contraction stages are preferred as optimization hardness increases. So, the uniform contraction pattern is utilized in NCOA.

Fig. 3

Simultaneously contracted multiple search scopes

At the beginning of search process, the contraction factor is initialized to $\varPhi =0.5$ and updated at each $N\times {\text {NumSample}}$ function evaluations such as:

$$\begin{aligned} \varPhi \leftarrow \varPhi \times CR \end{aligned}$$

(17)

where ${\text {NumSample}}$ is a number of feasible solutions generated around each individual in one contraction stage and ${\text {CR}}(<1)$ is a contracting ratio between adjacent contraction stages.

If the maximum number of function evaluation and a level of accuracy are predefined, then ${\text {NumSample}}$ and ${\text {CR}}$ can be calculated as Eq. (18) and Eq. (19):

$$\begin{aligned} \text {NumSample}= & {} \left[ \frac{\text {EvalLimit}}{(10\sim 50)\times N} \right] \end{aligned}$$

(18)

$$\begin{aligned} \text {CR}= & {} \left( \frac{\text {accuracy}}{\sqrt{\sum _{i=1}^{n}({\text {ub}}_{i}-{\text {lb}}_{i})^{2}}} \right) ^{\scriptstyle \frac{N\times {\text {NumSample}}}{\text {EvalLimit}}} \end{aligned}$$

(19)

where $\text {EvalLimit}$ is the maximum number of function evaluation and $\text {accuracy}$ is a level of accuracy. During search process, all of the search scopes are contracted more than $(10\sim 50)$ times, and at the end of search process, the diameter of all of the contracted search scopes should be smaller than $accuracy$.

3.3 Deterministic crowding and clearing

According to the idea of deterministic crowding (Sareni and Krähenbühl 1998), the new feasible solution is competed with the nearest individual (not the $p$th individual) and replaces it if the new feasible solution has a better fitness. That is,

$$\begin{aligned} \varvec{x}_{q}^{*} \leftarrow \varvec{x}, f_{q}^{*} \leftarrow f(\varvec{x}) \quad \text {if}\quad f(\varvec{x})>f_{q}^{*} \end{aligned}$$

(20)

where $q=\arg \min _{1\le p\le N} d(\varvec{x},\varvec{x}_{p}^{*})$ and $d(\cdot ,\cdot )$ is the Euclidean distance.

If the technique of crowding is not utilized and the new feasible solution is competed with just the $p$th individual, then the metric information is not used in competition, and so NCOA could not guarantee to find all optima for even a simple multimodal problem.

During search process, some individuals may be gathered around a same peak, in spite of crowding. If it happened, it would affect the efficiency of the optimization algorithm and the output of final solutions. Furthermore, it is ideal that each individual is a located different optimum and each optimum is occupied by only one individual at the end of search process. Thus, clearing method (Pétrowski 1996) is utilized.

The population is checked at each contraction stage. If some individuals are gathered closer than predefined radius (clearing radius) $R_{\text {clear}}$, then only the best individual is survived and the others are eliminated. The clearing radius should be smaller than the distance between the nearest two optima. It is normally selected as $(0.01\,{\sim }\,0.1)$ times of the size of search space:

$$\begin{aligned} R_{\text {clear}}=(0.01\,{\sim }\,0.1) \sqrt{\sum _{i=1}^{n} ({\text {ub}}_{i} - {\text {lb}}_{i} ) ^{2} } \end{aligned}$$

(21)

The pseudo-code of clearing can be illustrated as Algorithm 2.

3.4 Population initialization based on partition

Most niching algorithms utilize the distance information, and so initial distribution of the population may have an effect on the performance of algorithms. To improve the performance of niching algorithms, it is desirable that initial population is evenly distributed in the whole search space. Thus, partition-based population initialization (Yazdani et al. 2014) is utilized in NCOA.

If the initial population size is $N$, the number of dimension is $n$, and each dimension is divided into $s$ sections, then the following inequality is satisfied.

$$\begin{aligned} (s-1)^{n} < N \le s^{n} \end{aligned}$$

(22)

So the number of segment can be calculated as:

$$\begin{aligned} s= \lceil N^{\frac{1}{n}} \rceil \end{aligned}$$

(23)

where $\lceil x\rceil$ means the smallest integer which is not less than $x$. And the number of partition is

$$\begin{aligned} {\text {NumPartition}}=s^n \end{aligned}$$

(24)

At the beginning of search process, the population is initialized by a set of center points of $N$ randomly selected partitions.

The pseudo-code of the partition-based partition initialization can be illustrated as Algorithm 3.

3.5 The implementation of NCOA

The pseudo-code of NCOA is illustrated in Algorithm 4, and the flowchart of NCOA is presented in Fig. 4.

Fig. 4

The flowchart of NCOA

4 Experimental study

4.1 Benchmark functions and performance criteria

To assess the performance of NCOA, a set of 14 multimodal optimization benchmark functions (Li 2010) are employed. The characteristics of these functions are listed in Table 3. These benchmark functions are categorized into 5 groups according to the difficulty: 1-D deceptive functions (F1–F3), 1-D multimodal functions (F4–F7), 2-D multimodal functions (F8–F10), more challenging two or higher-dimensional multimodal functions (F11, F12), and high-dimensional multimodal functions (F13, F14). More detailed characteristics of these functions are could be referred to Li (2010) and Qu et al. (2012).

To investigate the effect of each component of NCOA and compare the performance of different multimodal optimizers, 30 independent runs concerning each algorithm have been achieved on each benchmark function.

The performances of the algorithms have been measured in terms of the following four criteria (Qu et al. 2012):

• 1. SR: Success rate (the percentage of runs, in which all of the desired peaks are successfully located)

• 2. PF: Average number of peaks found

• 3. Mean and standard deviation of the number of function evaluation

• 4. SP: Success performance (the ratio of the average number of function evaluations to the success rate)

4.2 The effects of the components of NCOA

First of all, the effects of the components of NCOA including population size, chaos map, initialization and contraction parameters are tested. We noticed that the results on the benchmark functions in the same group have much similar tendency, and thus, the results only for the benchmark functions F3, F7, F9, F10 and F11 are presented in order to avoid intricacy. The function F12 is also excluded in this test, since NCOA is not be able to succeed in all runs on function F12.

Table 3 Test functions

4.2.1 The effect of population size

To investigate the effect of population size, the population size is varied in (1–4) times of the number of optima, and the performance criteria SR and SP are investigated. The population sizes are quantified by the number of optima, and SP are quantified by the maximum number of function evaluation. The results are illustrated in Fig. 5. These graphs show that, as the difficulty of problem increases, a greater population size is required for successful search. But an excessive population size causes SP to increase. Thus, if the number of optima is known or predictable, it is advisable to select the population size to (2–3) times of the number of optima.

4.2.2 The effect of chaotic map

In NCOA, the circle map with parameter $\varOmega =0.5,K=11$ is employed instead of the logistic map. To investigate the effect of chaotic map, the circle map ($\varOmega =0.5,K=11$) is replaced by the circle map ($\varOmega =0.5,K=3$), the logistic map and the uniformly random number generator, respectively. The results of SR and SP with ranks (inside the brackets) are listed in Tables 4 and 5, respectively. The best approach of each test function is boldfaced. Total ranks (summation of all of the individual ranks) are listed in the last row of the tables. From the results, it can be observed that the performance of NCOA is affected by the chaotic map, and the highest performance is attained when the circle map ($\varOmega =0.5,K=11$) is selected. Of course, it is not unique and the other chaotic map or the other parameter settings could be employed.

4.2.3 The effect of initialization

The effect of partition-based initialization is compared with random initialization and listed in Table 6. The table shows that, in the case of using random initialization, the performance of NCOA is significantly decreased, and especially success rate not reached 1 for all of the test functions.

Fig. 5

The effect of population size. a Success rate. b Success performance

4.2.4 The effect of contraction parameters

NCOA has two contraction parameters (contracting ratio CR and a number of feasible solutions generated around each individual in one contraction stage NumSample), and the performance (convergence speed and success rate) of NCOA is intensely affected by these two parameters.

To investigate the effect of these parameters on the performance of NCOA, several pairs of the values of these parameters are selected and tested on the benchmark functions F3, F7, F8, F9, F10 and F11 (Fig. 6). The parameter CR is picked as $CR=0.9^{m}\, (m=1,\ldots , 10)$, and the parameter NumSample is picked as $(2,4,\ldots ,20)$ for F3, F7, F8 F9 and picked as $(10, 20, \ldots , 100)$ for F10 and F11. In Fig. 6, vertical axis indicates the criterion SP, and bars are displayed only if $\mathrm {SR}=1.0$ for F3, F7, F8, F9 and $\mathrm {SR}>0.8$ for F10 and F11.

Table 4 Success rate according to the chaotic maps

From the results, it can be noticed that if the parameter CR is fixed, then success rate tends to increase with an increase in the parameter NumSample, but convergence speed should be slower. If the parameter NumSample is fixed, then success rate tends to increase as the parameter CR approaches 1, but convergence speed should be slower. These parameters are inseparable from each other, and optimal pairs of these parameters are dependent upon the difficulty of optimization problem.

4.3 Comparison with other multimodal optimizers

The performance of NCOA is compared with those of state-of-the-art multimodal optimization algorithms. These algorithms are listed as follows.

• 1. SPSO (Parrott and Li 2006): Species-based PSO, in which the species radius $r_s$ is set to a value smaller than the distance between two closest optima.

• 2. FER-PSO (Li 2007): Fitness–Euclidean distance ratio PSO.

• 3. R2PSO (Li 2010): A lbest PSO with a ring topology, in which each member interacts with only its immediate member to its right.

• 4. R3PSO (Li 2010): A lbest PSO with a ring topology, in which each member interacts with its immediate member.

• 5. R2PSO-lhc (Li 2010): The same as R2PSO, but with non-overlapping neighborhoods.

• 6. R3PSO-lhc (Li 2010): The same as R3PSO, but with non-overlapping neighborhoods.

• 7. FER-DE (Liang et al. 2014): Fitness–Euclidean distance ratio DE, in which “DE/rand/1” mutation strategy is utilized.

Table 5 Success performance according to the chaotic maps

Table 6 The effect of initialization

Fig. 6

The effect of contraction parameters on NCOA’s success performance. a F3 (success rate $=$ 1). b F7 (success rate $=$ 1). c F8 (success rate $=$ 1). d F9 (success rate $=$ 1). e F10 (success rate > 0.8). f F11 (success rate > 0.8)

Level of accuracy, the maximum number of function evaluation and population size for NCOA and the other optimizers are listed in Table 7. Note that the population size for NCOA is much smaller than the other optimizers.

4.3.1 Comparison on the test functions F1–F12

The results for the performance criteria SR and PF (inside the bracket) for the different multimodal optimizers are listed in Table 8. The best performance is reported in boldface. These results show that NCOA has overcome all of the other multimodal optimizers in terms of success rate, and that NCOA has found almost all of the desired optima for all of the test functions except F12. Even though NCOA did not succeed in all runs on function F12, it could be considered to have progression over the other optimizers in terms of the average number of peaks found.

Table 7 Parameters settings for NCOA and the other multimodal optimizers

The results for mean and standard deviation of the number of function evaluation are listed in Table 9. The best performance is reported in boldface. From the results, it can be observed that the convergence speed of NCOA is significantly faster (far more than threefold) than the other optimizers on the test functions F1–F9. NCOA also shows competitive convergence speed on the test functions F10 and F11, even though it does not rank top. Furthermore, the standard deviation of the number of function evaluation of NCOA is much smaller than the others, which means that the convergence behavior of NCOA is very stable.

4.3.2 Comparison on the test functions F13 and F14

We carry out the following experiments to study the effect of increasing dimensionality on the performance of NCOA.

The inverted Rastrigin function (F13) has a single global peak and many local peaks. The number of local peaks increases exponentially as the dimension increases. To locate the single global optimum, optimizers have to overcome these local peaks. We consider an algorithm has located the global peak if the difference between the fitness of the global peak and the best individual is less than 5. Figure 7 shows the results for SR of all multimodal optimizers on the function F13 with varying dimensions from 8 to 15. It is noticeable that the success rates of the other optimizers were rapidly degraded with the dimension increases. On the contrary, NCOA’s success rate was scarcely degraded.

Table 8 The experimental results for SR and PF

Table 9 The experimental results for mean and standard deviation of the number of function evaluation

Fig. 7

The results of SR on F13

Figure 8 shows the results of PF on the generic Hump function (F14). Few algorithms were able to succeed on F14, and thus the criterion PF was used as the performance indicator. From Fig. 8, it can be observed that NCOA has found the most number of peaks and NCOA has been less affected by the increment of dimensionality than the other optimizers.

Fig. 8

The results of PF on F14

5 Conclusion

In this paper, a niching variant of COA called NCOA was proposed for multimodal optimization. In NCOA, the circle map with a proper parameter setting was employed instead of the logistic map. Various techniques (partition-based population initialization, simultaneously contracted search scopes, deterministic crowding and clearing) had been utilized in NCOA to accomplish niching. The effects of the components and parameters of NCOA had been investigated through numerical experiments. Experimental results and comparison with other state-of-the-art multimodal optimization algorithms demonstrate that NCOA has a competitive performance for multimodal optimization.

One more step to extend the current work would be analyzing the search behavior of NCOA more deeply and combining NCOA with other heuristic algorithms (e.g., PSO, DE, harmony search, imperialist competitive algorithm) to speed up the exploitation.