Review of chaotic mapping enabled nature-inspired algorithms

1.   Introduction

Inspired by the living existence that evolved from their ancestors lived millions of years ago, scientists and engineers have proposed a lot of nature-inspired algorithms ^[1], however, most of the algorithms including their improvements were not able to find all the solutions of the existed problems due to the No Free Lunch (NFL) rule ^[2]. And to verify the capability of algorithms, we also formulate many functions to test them, most of them nowadays become classical in literature and so we called them benchmark functions ^[3]. After thorough study of verification experiments, the algorithms were soon applied to solve the real-world engineering problems, for instance, prediction of routing scheme for softwarized vehicular networks ^[4], adaptive routing for edge software-defined vehicular networks ^[5], satellite-terrestrial networks storage strategy planning ^[6]. However, we soon confirmed that there still did not exist an efficient algorithm that could solve all of the problems we met. Therefore, new algorithms even their improvements were remaining under demand.

Literal reviews claimed that the nature-inspired algorithms could be classified into four types based on the source of the inspiration: evolutionary algorithms, swarm-based, human-based, and physics-based ones ^[7]. The exact number of the proposed nature-inspired algorithms might be not known causing its current prosperousness in artificial intelligence ^[8], however, the improvement of a given algorithm might be also difficult to tell in number. It could be relevant to all aspects of an existed algorithm regarding the improvements. For instance, the particle swarm optimization (PSO) algorithm, which was proposed in 1995 ^[9], became popular soon after its birth and various kinds of improvements were raised by scientists and engineers all over the world. In the traditional PSO algorithm, the individuals update their positions according to their velocities, random weighted distance between them and their best trajectories, and the global best candidates in each iteration.

In a detailed study of the improved PSO algorithms, first of all, the continuous domain definition was considered to be not able to meet the request of problems in the digital world. And consequently, the discrete binary version of the PSO algorithm was proposed ^[10]. The weight of the velocity was soon added and better performance was astonishingly achieved ^[11]. Inertia weights were then evaluated to remove the constant characteristics of this weight parameter ^[12]. Some improvements reconsider the involvement of the three parts and decreased them linearly to increase the convergence ratio, and therefore, the neighborhood operator improved PSO algorithm ^[13] was proposed.

Except for the parameters involved in the original algorithm, the participation of individuals in swarms might be another interesting hotspot. A fixed number of successful or failed operations in optimization might be introduced to guarantee convergence ^[14]. While in the fully informed PSO algorithm ^[15], all of the individuals were introduced to play roles in the updating of their positions, discarding the original concept of performance of the velocity, historical best, and global best candidate. Eliminating the historical trajectory with ${\mathrm{c}}_{1} = 0$ ^[16] or replacing the global best candidates with the worst ones in each iteration ^[17] might be other tries.

Furthermore, the velocities or positions of individuals in swarms might also be reinitialized during iterations ^[18]. The multiple updating disciplinary ^[19] might also be introduced. For instance, in the bare-boned PSO algorithm ^[20], half of the individuals in swarms were updated according to the global best candidates in iteration and another half of them with traditional way. The probability might be defined by the number of tunnels for individuals to follow, such as in the heterogeneous PSO ^[21].

Let alone the hybridization of famous algorithms ^[22], the randomness involved in the algorithms was another hot spot in the design of improvements. Traditional pseudo-random numbers are equally selected from the given domain, therefore, the distribution of weights was Gauss distribution, the random steps were equally chosen from the distribution. However, the population number in swarms was not expected to be large in number under the control of current computer hardware. And few samples could not follow the statistics of Gauss distribution. It might decrease the capability in exploration and exploitation ^[23]. Considering the Levy flight ^[24] could generate some long steps after several rounds of small steps, it could be used to increase the performance of algorithms in optimization. The overall better performance demonstrated in the literature proved that such kind of improvement could indeed improve the capability of the original algorithm ^[25]. Another common improvement was to replace the randomness in Gauss distribution with chaos. Because of the pseudo randomness generated by Gauss distribution in computer engineering, the random numbers were believed not well with smaller population size. However, the population size could not be set with larger numbers under the constraints of our real-world computer hardware. Considering the chaos are derived from non-linear dynamic systems, they would perform more chaotically in generating numbers. In fact, almost all of the existed algorithms have been improved with chaos, as shown in Table 1.

Therefore, we focused our attention and collected most of the chaotic mappings in literature and tried to verify its better performance. The main contribution of this paper would be:

1) A collection of 19 popular chaotic mappings and all of them could generated random numbers within an interval of 0 and 1.

2) A brief review of the chaotic improvements and four types of improvements were summarized.

3) Applying in improving the well-known grey wolf optimization (GWO) and sine cosine (SC) algorithms, detailed comparison and simulation experiments were carried out.

The rest of this paper would be arranged as follows: in Section 2, all of the chaos we found which could generate chaos in [0, 1] would be listed. Literature review of the chaotic improvements would be reviewed in Section 3. Some chaotic improvements and the experiments would be shown in Section 4. Discussions would be made and conclusions would be drawn in Section 5.

2.   The chaos

The chaos is a kind of deterministic random-like method, most of them are derived from non-linear dynamic systems ^[39]. Chaos is also a kind of pseudo randomness, however, since they are derived from the chaotic system, most of them would be bounded, irregular and sensitive to the initial conditions ^[40]. Meanwhile, the values would spread all around the domain with a given route from the initial values. The chaos could be used to eliminate the uncertainty of pseudo randomness and therefore, better stability could be wanted.

To replace the pseudo randomness in computer engineering, the chaos should be in an interval between 0 and 1. Consequently, some transformation would be wanted to change the original values if the original chaos were limited in other domains except [0, 1], the following chaotic maps could all generate chaos satisfying the requirements with or without some extra functions.

2.1.   CM1: Bernoulli map

Bernoulli map is a famous map to generate chaos, its formulation might be shown as follows ^[41]:

Where ${x}_{n}$ represents the current chaos with $n-\mathrm{t}\mathrm{h}$ iteration and ${x}_{n+1}$ represents the chaos at the next iteration.

To generate pseudo randomness in the interval between 0 and 1, chaos generated by the Bernoulli map might be transformed with double and absolute functions. A brief view of the values versus five hundred iterations would be shown in Figure 1.

Note that there are five hundred of iterations for the Bernoulli map. For convincement, all of the following chaotic maps would be also iterated five hundred times for comparison.

2.2.   CM2: Chebyshev map

Chaos generated by Chebyshev map could be obtained from an equation formulated as follows ^[32]:

Chaos generated by the Chebyshev map fluctuates in the interval between -1 and 1. Therefore, to replace the pseudo randomness in computer engineering, the final chaos should be transformed with absolute function, as shown in Figure 2.

2.3.   CM3: Circle map

Circle map ^[32] is formulated with the sine function:

Where mod (1) is the mathematical function to find the remainder number after dividing by 1. If a = 0.5 and b = 2, the Circle map would generate chaos in the interval of 0 and 1, as shown in Figure 3.

2.4.   CM4: Gauss map

Gauss map is also called Mouse map ^[32]:

Where $⌊x⌋ = x-xmod\left(1\right)$ represents the integer part of the float number. Gauss map directly generates chaos in [0, 1] domain, seen from Figure 4.

2.5.   CM5: Hybrid map

The hybrid map is a new kind of chaos generator ^[42], the Hybrid system is formulated as follows:

Where ${\mu }_{1}$ = 1.8, ${\mu }_{2}$ = 2.0, b = 0.85. The chaos generated by the Hybrid map falls within -1 and 1. Therefore, the absolute function should be introduced to constraint the chaos to fall in the [0, 1] domain, as shown in Figure 5.

2.6.   CM6 ICMIC map

The iterative chaotic map with infinite collapses (ICMIC) map is a one-dimensional chaotic map ^[43], it is relevant to the sine function and formulated as follows:

Due to the definition of the sine function, the ICMIC map also generates chaos fallen in [-1, 1], the absolute function is also introduced to transform the chaos to fall in [0, 1], seen from Figure 6.

2.7.   CM7 Intermittency map

Intermittency map is an extension of the Bernoulli shift in which the piecewise linear map representing the passive interval is replaced by the following equation ^[32,39]:

Where $\varepsilon$ is a small number and $c$ is calculated as follows:

Intermittent map generates chaos whose values are in [0, 1], yet spread in a weird distribution, seen from Figure 7.

2.8.   CM8 Iterative map

The iterative map is similar to the ICMIC map, as shown in the following equation:

The iterative map also generates chaos in [-1, 1], so it should be transformed by the absolute function. The distribution of chaos could be seen in Figure 8.

2.9.   CM9 Liebovitch map

Liebovitch map was unique, it has two separators in the domain (0, 1) ^[32], as formulated as follows:

Where, $\mathrm{\alpha } < \mathrm{\beta }$ and defined as follows:

Liebovitch map would generate chaos mostly distributed in (0, 0.2) and (0.8, 1) domains, seen from Figure 9.

2.10.   CM10 Logistic map

The logistic map is a classic chaotic map derived from nonlinear dynamics of biological population evidencing chaotic behavior ^[32]:

Initially, ${x}_{0}\ne \{0, \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }0.25, \mathrm{ }0.5, \mathrm{ }0.75, \mathrm{ }1\}$. Logistic map directly generates chaos whose values are in [0, 1] domain, seen from Figure 10.

2.11.   CM11 Kent map

Kent map is a famous map used to generate pseudo-random numbers ^[44], it is defined as follows:

Kent map generates chaos in (0, 1), seen from Figure 11.

2.12.   CM12 Piecewise map

Piecewise map consists of four linear pieces and is formulated as follows:

Obviously, $0 < \mathrm{d} < 0.5$, and ${x}_{n}\in [0, \mathrm{ }1)$, it could also be derived from Figure 12.

2.13.   CM13 Piecewise Linear map

Piecewise Linear map also consists of two piecewise linear segments ^[40], it is defined as follows:

There are two linear segments in the Piecewise Linear map, which generate chaos in (0, 1), as shown in Figure 13.

2.14.   CM14 Quadratic map

The quadratic map is decoded from shared codes ^[41], it is a new kind of Mandelbrot map ^[45] and formulated as follows:

Where $a = 4, b = 0.5$. Quadratic map generates chaos fallen in [-0.5, 0.5]. To replace the pseudo-random numbers, double and absolute functions would be introduced, the final chaos values could be seen in Figure 14.

2.15.   CM15 Sine map

Sine map is another iteration form with sine function ^[32], its formulation is:

To be simple, $\mathrm{a} = 1$, and we can obtain the chaos as shown in Figure 15.

2.16.   CM16 Singer map

Singer map is a one-dimensional system defined as follows ^[32]:

Where $0.9 < \mu < 1.08$. The Singer map generates chaos whose values could be directly treated as pseudo-random numbers, seen from Figure 16.

2.17.   CM17 Sinusoidal map

Sinusoidal map ^[32] is a combination of Sine map and Quadratic map, as shown in the follows equation:

The sinusoidal map also directly generates pseudo-random numbers, as shown in Figure 17.

2.18.   CM18-19 Tent map

There appeared two kinds of Tent maps in literature. One of them is similar to the well-known Logistic map and is defined by the following equation ^[32]:

We called this Tent1 map, labeled CM18 for future applications, it could also directly be used to replace the pseudo-random numbers, as shown in Figure 18.

Another kind of Tent map is introduced by the following iterated function ^[44]:

When μ$= 2-$ε, this Tent map could generate chaos, we called this map Tent2 map, labeled CM19 for future purpose, its values could be seen from Figure 19.

3.   A brief review of chaotic improvements in literature

The chaotic map has been introduced to improve nature-inspired algorithms for many years. Scientists and engineers all around the world were still trying to improve the existed algorithms with chaos.

3.1.   Ways of chaotic applications in improvements

The existed algorithms have been tried to improve their capability in every aspect we could find.

First of all, since all of the individuals in swarms must be initialized at the beginning, the positions of individuals should be spread all over the domain of the given problem, they should be distributed as equally as possible. Every optimum, either being global or local, should be gained access by some individuals to be found as soon as possible. Therefore, the traditional pseudo-random number might also be not the best choice. This kind of effort has been made, for example, in some kind of chaotic PSO algorithm ^[46]. However, our early simulation experiments on some benchmark functions optimized by the chaotic Slime mould (SM) algorithm ^[47] proved that the chaotic initialization might decrease the capability of algorithms in optimization sometimes.

The second kind of chaotic application in improving the existed algorithms is to replace the pseudo-randomness numbers reasonably. Most of the efforts were made on this kind of improvement. Every random number falling within the interval between 0 and 1 might be replaced by chaos. Considering the number of randomnesses, every randomness could be tried to replace by every kind of chaotic map one by one, as jobs executed in the chaotic bat algorithm ^[32], the chaotic whale optimization (WO) algorithm ^[36]. Results might also be fluctuated according to the characteristics of different chaotic maps, even the positions of randomness in mathematics.

The third kind of chaotic application to improve the capability of algorithms might be to define a chaotic domain near the global best candidates in iterations. This is an efficient way to find whether the global best candidate being approaching the optimum or not. For every global best candidate in iterations, the current best position might be used to generate a random domain, several rounds of other chaotic approaches might be carried out to find whether there was another best position or not. This kind of operation increased the time complexity and meanwhile increased the convergence ratio dramatically. Most of our human attention was paid to this kind of improvement, such as the chaotic PSO algorithm ^[46], chaotic grey wolf optimization (GWO) algorithm ^[39].

A new kind of chaotic application was proposed most recently. Almost in all of the swarm-based algorithms, there always existed a controlling parameter to balance the ratio of exploration and exploitation for individuals during iterations. For example, chaotic parameter f in chimp optimization algorithm (ChOA) ^[48], or the control parameter a in the GWO algorithm ^[2]. All of these kinds of parameters were declined linearly from the maximum to minimum or zero. In 2019, a new kind of non-linear chaotic decreased way was proposed by Saxena et al. ^[49], the new control parameter a was defined as a combination of the traditional parameter and chaos following the $\mathrm{\beta }$ distribution. However, although simulation experiments verified its capability in optimization, the overall results were not promising as a whole.

3.2.   Performance of chaotic applications in improvements

For the above four types of chaotic applications, the first kind of improvements had been already proved to be incapable frequently in literature. While the rest kinds of improvements were not deterministic, sometimes the chaotic enabled algorithms would perform better, sometimes they did not.

Due to the chaotic characteristics of chaos, chaotic mapping enabled improvement has been popular in literature for decades. Almost all of the algorithms have been tried to be improved with chaotic mapping, as shown in Table 2.

4.   Applications of chaotic improvements

In Section 3, we found that there were four types of chaotic applications to improve the performance of the existed algorithms. Some of them had already proved to be incapable for most times. Yet some of them were frequently reported to perform better or worse in literature. In Section 2, we collected 19 chaotic maps and all of them could generate chaos in the interval between 0 and 1. Some of them, for example, Logistic and Piecewise maps, were frequently used in applications. Some of them seldom appeared in literature regarding nature-inspired algorithms. In this section, we would carry out some simulation experiments to verify their suitability and capability. For simplicity, the GWO ^[57] and sine cosine (SC) ^[58] algorithms were introduced to be representatives of the swarm-based nature-inspired algorithms, and the convergence rate would be the only metrics to be balanced.

4.1.   Experimental setup

Simulation experiments would be carried out to verify the capability of algorithms. There are 19 chaotic maps, four types of improvements, and two famous algorithms being involved in this paper.

Due to the randomness being involved in every nature-inspired algorithm, the results would be changed every time we got. To reduce the influence of randomness, Monte Carlo methods were always introduced to average the results and verified the capability of algorithms in optimization. In this experiment, 100 Monte Carlo simulation experiments would be carried out and the final results would be their average.

For simplicity, we improved the GWO and SC algorithms with different kinds of chaotic maps. And all of the benchmark functions in Table 3−6 were introduced to carry on simulation experiments.

4.2.   Type 1: Chaotic mapped initialization

For the first kind of improvements, results were shown from Figures 20 to 23.

We can find that although different chaotic maps might generate different kinds of chaos when they are introduced to improve the algorithms at the initialization stage, some of the chaos might perform better, some of them not. For Ackley 1 function, almost all of the chaos introduced to improve the algorithms at the initialization stage performed better than the original. For the Alpine 2 function, all of the chaotic mapped SCA performed better than before, however, only Chebyshev, Tent1, Piecewise, Intermittency, Sine, Gauss, Logistic, ICMIC maps could result in better performance than before.

Optimizing the Chung Reynolds function, only a few of the chaotic maps perform worse than before. However, in a different way for SC algorithm (Liebovitch map performed worse) and the GWO algorithm (Logistic, Chebyshev, Kent, and Liebovitch performed worse).

Similar conclusions could be made on the Bent Cigar function. All of the chaotic maps could yield better performance for the SC algorithm, while for the GWO algorithm, the Hybrid, Chebyshev, Tent2 map would perform worse in improvement.

Based on the results above, we cannot conclude that when the chaotic maps were introduced to improve the randomness at the initialization stage, they would perform better or worse. Different chaotic maps and benchmark functions need to be specially reviewed and verified. It was really hard to predict even for an experienced person. Nevertheless, the chaos introduced at the initialization stage would improve the capability of optimization with a large probability.

4.3.   Type 2: Chaotic mapped randomness

The pseudo-random numbers are always replaced by chaos to reduce the influence of traditional pseudo-randomness.

However, since there always existed more than one random number involved in the algorithms, every randomness might be involved to be replaced like the work in chaotic bat algorithm ^[32]. Furthermore, more chaotic maps might be also introduced to replace each random number respectively.

In this paper, only the first random number was replaced by chaos, the rest of the random numbers remained unchanged, results were also averaged from 100 Monte Carlo simulation experiments, and were shown in Figures 24−27.

Convergence ratio curves of different kinds of equations showed that there might be no strict discipline that could be followed in this kind of experiment, the improvements were random for all of the chaos and benchmark functions.

4.4.   Type 3: Chaotic mapped iterations

The most popular improvements introduced were to carry on several rounds of iterations with chaos. In this kind of experiment, we might choose extra rounds of iterations as chaoticMaxIter = 10.

During the main iteration carrying out by individuals, their positions were updated, and then the best candidate was found. Extra chaoticMaxIter iterations were carried out with chaos, when a better position was achieved, then this new best candidate would be treated as the global best candidate in the current iteration. Otherwise, if chaoticMaxIter iterations were carried to the end and no better position was found, the current best candidate still took the position and led the individuals to the next iteration of swarms.

Due to the extra chaotic exploration and exploitation around the best candidate, who might be the global or local optimum, consequent better results were promised. However, the final results as shown in Figures 28−31 didn't fully support this conclusion.

For Sargan and Holzman's 2 functions, most of the chaotic maps would increase the capability of optimization, only a few of them failed to do so. However, 18/19 chaotic maps failed to increase the SC algorithm in optimizing the Griewank function, the dramatically complex landscape and optima might be the reason. And 13/19 chaotic maps failed to increase the SC algorithm in optimization of Schwefel 1.2 function, the valley shape might be a reason.

Statistically speaking, this kind of improvement could indeed increase the algorithms as a whole, but not all of the chaotic maps could increase or decrease the capability of algorithms in optimization. Confirmative conclusions could be drawn based on the first glance of the benchmark functions or chaotic maps, simulation experiments remain indeed to verify whether a given chaotic map could improve a selected algorithm or not.

4.5.   Type 4: Chaotic mapped controlled parameters

The controlled parameter balancing the exploration and exploitation ratio was mostly declined from the maximum to minimum values linearly, for instance, the energy parameter E in the Harris hawk optimization (HHO) algorithm ^[59], a in the SC algorithm or GWO algorithm. Sometimes other distributions might be also introduced, such as the exponential function in the equilibrium optimization (EO) algorithm ^[60], arctanh ^[61], or cosine ^[62] functions in the slime mould (SM) algorithm. In the SCA and GWO algorithms, the controlled parameters were declined linearly from 2 to zero versus iterations with randomness. The randomness could also be replaced by chaos to improve capability, steadiness, and suitability.

This kind of improvement was just proposed recently with a specific seldom applied chaotic map in $\mathrm{\beta }$ distribution ^[49]. In this experiment, 19 classical chaotic maps were introduced to replace the $\mathrm{\beta }$ ddistributed chaos, results were shown from Figures 32 to 35.

Results showed that sometimes this kind of improvement could improve the capability of the optimization algorithm, but sometimes the chaotic maps would fail to do so. Regarding Schwefeil 1.2 function, all of the chaotic improved GWO algorithms would perform better than the original, while only six of them could improve the SC algorithm.

4.6.   Discussion of the results

Literal researches had been made and four types of classical improvements including a newly proposed version were concluded. Detailed results of works in this paper might be summarized in Tables 7 and 8.

We can find that the chaotic maps could increase the capability of the GWO algorithm more than that of the SC algorithm. Most of the chaotic maps could result in a better performance when they are applied in improving the GWO algorithm, simulation experiments verified their capability. Only a few of them, precisely 6/19, such as the ICMIC, Intermittency, Quadratic, Singer, and Sinusoidal maps could only perform better in less than 10/16 benchmark functions.

On the opposite side, only Bernoulli and Kent map performed better in no less than 10 of 16 benchmark functions. Most of them could not yield better results.

Focusing on the characteristics of benchmark functions, four types including unimodal, multimodal, unimodal with basin-like or valley-like profiles in their three-dimensional profiles ^[3] of benchmark functions were introduced. However, we still cannot draw confirmative conclusions from the experiment results. For example, from the results of simulation experiments on unimodal benchmark functions with the GWO algorithm, we can find that none of the chaotic improved GWO algorithms could perform better in optimizing Ackley 1 function, meanwhile, 16 and 18 of the 19 chaotic maps could perform better in improvement on the Exponential or Sargan function. Regarding the SC algorithm, most of the chaotic maps failed to do so.

5.   Discussion and conclusions

In this paper, we paid attention to the chaotic maps which could generate pseudo-random numbers in an interval between 0 and 1. Nineteen classical chaotic maps were collected and their improvement on the famous GWO and SC algorithms were researched.

Four types of benchmark functions, including two main classical characteristics: modality and uniqueness in profiles, were introduced to carry on the simulation experiments. For the obviousness and simplicity, only convergence ratio experiments were carried out and the convergent curves were shown in figures. We can conclude about the study of chaotic improved research that:

A. Although the chaotic maps could be used to replace the pseudo-random number in computer engineering, they could not increase the performance of algorithms in optimization for sure.

B. Among all of the four types of chaotic improvements, sometimes they could perform better, yet none of them could perform confirmative better for a given problem.

C. Modality and the unique landscape could influence the performance of optimization algorithms, however, they are all not the only reason. A detailed study in mathematics might be needed to find the reason why some of the benchmark functions could be easily optimized, while some of them not.

D. There might be doubtful to apply the chaotic maps in improving optimization algorithms in engineering. It might be OK for a given problem and algorithm, which might occur in some subjects. Nevertheless, due to the uncertainty of a specific chaotic map on all improved ways and functions, it would be unnecessary to establish chaotic improved platforms in computer engineering.

E. It might be a little meaningless to investigate the performance of chaos in optimization henceforth.

Acknowledgments

The authors would like to thank the supports of the following projects: the scientific research team project of Jingchu University of technology with grant number TD202001, and the key research and development project of Jingmen with grant numbers 2019YFZD009.

Conflict of interest

There is no conflict of interest.

Appendix