The average function values obtained by the average function values obtained by PSO, CPSO, KH, CKH, BBO, and CBBO at
Chaos theory is a novelty approach that has been widely used into various applications. One of the famous applications is the introduction of chaos theory into optimization. Note that chaos theory is highly sensitive to initial condition and has the feature of randomness. As chaos theory has the feature of randomness and dynamical properties, it is easy to accelerate the optimization algorithm convergence and enhance the capability of diversity. In this work, we integrated 10 chaotic maps into several metaheuristic algorithms in order to extensively investigate the effectiveness of chaos theory for improving the search capability. Extensive experiments have been carried out and the results have shown that chaotic optimization can be a very promising tool for solving optimization algorithms.
- metaheuristics algorithm
Chaos theory is a novelty approach, which has been used into various applications widely . One of the most famous applications is the introduction of chaos theory into optimization. Note that chaos theory is highly sensitive to initial condition and has the feature of randomness . The most metaheuristic optimization algorithms belong to stochastic algorithms. The property of randomness is obtained by using probability distribution, such as uniform and Gaussian method. There is a randomness method in optimization filed called chaotic optimization (CO), which has the property of dynamical, nonrepetition, and ergodicity. The dynamical property ensures different solutions produced by algorithm and searches different modal objective search space, even on the complex multimodal landscape. Moreover, because of the ergodicity property of CO, it can perform searches at higher speeds compared to the stochastic algorithms with probability distribution. As chaos theory has the feature of randomness and dynamical properties, it is easy to accelerate the convergence of optimization algorithm and enhance the capability of diversity.
Since it has same properties of metaheuristic algorithms, it is natural that numerous metaheuristic algorithms have been combined with chaos theory. Generally, the most metaheuristic optimization algorithms are considered as stochastic approach. Compared to deterministic method, stochastic algorithm are much more flexible and universal. The simple idea of metaheuristic optimization algorithm is using greedy strategy for searching the promising solution areas to find out the optimum one. There are three categories of metaheuristic optimization algorithms: evolutionary algorithm, which mimics the evolution process, is the most popular algorithm in this kind. It contains genetic algorithm (GA) , different evolution (DE) , and the evolutionary strategy (ES) . The second category is the swarm intelligence, the population-based algorithms. Particle swarm optimization algorithm (PSO) , wolf search algorithm (WSA) , and cuckoo search (CS)  are the well-known algorithms in this category. The third algorithm neither belongs to evolutionary algorithm nor SI, such as dynamic group optimization (DGO), [9, 10] which can be considered as the third category. In the most cases, metaheuristic algorithm has two phases: exploration and exploitation. Simply put, the exploration phase occurs when the algorithm discovers promising search area, and the exploitation phase refers to search the most promising solution obtained from the exploration phase as quickly as possible.
Although many metaheuristic algorithms can accelerate the search speed, they still have one major drawback, premature convergence. If the search space has many local optimums, it is very easy to stick into a local optimum. In order to deal with this problem, many researches proposed many methods, for example, using adaptive method adjusts parameters, using hybrid method enhances the search capability. However, balancing global exploration and local exploitation are still difficult, because better global exploration capability is usually accompanied by worse local exploitation, and vice versa. Introducing chaos is the most suitable approach to solve those problems. It has the property of the nonrepetition, ergodicity, and dynamic. The dynamic property ensures the solutions produced by algorithms variety, and searches different landscapes search space, and the ergodicity and nonrepetition enhance the speed of searching. Chaotic optimization not only accelerates the speed of algorithm but also enhances the variety of movement pattern. In this work, we integrated 10 chaotic maps into several metaheuristic algorithms to extensively investigate the effectiveness of chaos theory for improving the search capability. The performance of the approach is tested on 14 benchmark functions, which are the CEC2009 competition testing functions that contains unimodal functions and multimodal problems.
In reality, optimizations are very hard to solve, many of them belong to NP-hard problems. To solve such problems, optimization algorithms have to be used. According to the “No free lunch theorem,” there is no such efficient algorithm for all problems. As a result, many optimization algorithms have been developed and tried to use various improving techniques to enhance the capability of searching to see that if they can cope with these challenging optimization problems. Chaos can be described as a bounded nonlinear system with ergodic and stochastic properties. It is very sensitive to the initial condition and the parameters. Recently, numerous improvements, which rely on the chaos approach, have been proposed for metaheuristics algorithm.
2.1. Metaheuristics algorithms
In this section, we will introduce three most well-known chaotic optimizations which based metaheuristics optimization algorithms.
2.1.1. Particle swarm optimization algorithms (PSO)
Original particle swarm optimization is a population-based heuristic method which is discovered by mimicking social models of bird flocking and swarming to find the optimal solutions. It was proposed by Kennedy  in 1995.
The position of the
where and are random generator between (0, 1), and and are acceleration constants that control the speed of incensement. means the velocity of ith particle at
In chaotic particle swarm optimization algorithm , the random generator is replaced by sequence of chaotic maps. and are modified by the chaotic maps, and it can be described as follows:
where is the sequence generated by the chaotic map at each independent run, and
In Eq. (4),
2.1.2. Krill herd algorithm (KH)
The krill herd algorithm mimics the behavior of krill individuals in krill herds (KH) . This algorithm was proposed by Gandomi in 2012. There are three main actions in KH, which is shown as follows:
Motion induction: this activity refers to the density maintenance of the herd. It can be described as follows:
where is the maximum induced speed, , is the inertia weight. and are the local effect and target effect, respectively, and is calculated as follows:
where is the coefficient and can be defined as follows:
The second activity is foraging, and the mathematic equation is shown as follows:
where , is the foraging speed, is the weight of foraging movement, shows the attractive of food, and is the best solution obtained so far.
The third activity is the diffusion, which is a random activity, and it can be defined as follows:
where is the maximum diffusion speed and is a random vector in [−1, 1].
The position of krill
Note: can be regarded as a scale factor of the speed vector.
In the chaotic KH , researchers used chaotic maps in tuning the random vector; it improves the ability of KH to avoid local optimum. In the classical KH, the most important random value is calculated in Eq. (7); therefore, the parameter r is substituted by chaotic maps as follows:
2.1.3. Biogeography-based optimization algorithm (BBO)
The biogeography-based optimization algorithm (BBO) was inspired by biogeography . It simulates relations between different species which are located in different habitats, such as immigration, mutation, and emigration. BBO can be summarized into three rules.
Individuals living with high habitat suitability index (HSI) are more likely to immigrate to habitats with low HIS.
Habitants living with low HSO are more likely to allow immigrations from high HSI.
The HSI value may change randomly.
For each habitat, it has three rates: immigration , emigration
In chaotic BBO , researchers used chaotic map to provide chaotic behaviors for selection operator, emigration, and mutation.
For selection operator, the rand value is substituted by the value from chaotic maps. The pseudo code is as follows:
For emigration, it can be calculated as follows:
The probability of mutation is defined by the chaotic map as follows:
2.2. Phase in chaos embedded metaheuristics algorithms
From Section 2.1, we can find that the most chaos embedded metaheuristic algorithms have three key phases: initialization, operators, and random generator. In this section, we describe them as follows:
Initialization: the starting positions in metaheuristics algorithm are generated randomly. Diversity of initial population is very important for helping the population spread in search space. Therefore, the initial populations are generated by chaotic maps, which can produce a well distribution by the properties of random and ergodicity of chaos. The chaotic sequence can accelerate the convergence and enhance the global search capability. The pseudo code of initialization is as follows:
where the is the weight of ith weight, and
Operators: generally, metaheuristics algorithms have several operators, such as selection operator, crossover operator, and mutation operator. Most of them are controlled by probabilities. In order to improve the capability of searching optimum, the probabilities can be substituted by chaotic sequence. The mathematical formula can be described as follows:
For a crossover operator:
For a mutation operator:
Random generator: Random parameters in metaheuristics algorithms, for instance, polynomial variation, are replaced by chaotic sequences. For a solution
The phase for random generator is that is calculated by chaotic maps in iterations. For example, if the chaotic map is logistic map, then in the (
2.3. Chaotic maps
In this section, we present the chaotic maps used, which generate chaotic sequences in the process of evolutionary algorithms. Ten chaotic maps are one-dimensional maps.
The first is the Chebyshev map, which is a common chaotic map and used in digital communication and neural network widely. It can be defined as follows:
where the range is (−1,1). Note that is the
Circle map is a simplified model for both driven mechanical rotors. Furthermore, it is a one-dimensional map which maps a circle onto itself. Circle map is presented as follows:
Gauss/Mouse map can be described as follows:
This map also generates chaotic sequences in (0,1).
Iterative map with infinite collapses can be presented as follows:
Logistic map can be written as follows:
Piecewise map is governed by the following equation:
The sine map belongs to a unimodal map and is similar to the logistic map, which can be described as follows:
Singer map is a one-dimensional system like the following:
where = 1.07 and the range is (0,1).
Sinusoidal map can be defined as follows:
Tent chaotic map is very similar to the logistic map, which displays specific chaotic effects.
Tent map can be described as follows:
In order to get an unbiased result, we set the initial point as 0.7 for all chaotic maps in this work. Ten chaotic maps are shown in Figure 1.
In this section, we evaluate the performance of the chaotic metaheuristics algorithms; several experiments were carried out to test the efficiency. Twenty-three benchmark functions were used in our experiment. In order to obtain an unbiased result, all experiments were performed in the same environment.
In our experiments, we used the average and StD of the function value to compare the performance of the algorithms. Our focus was to compare our proposed algorithm with the other algorithms using two evaluation criteria. We compared the performance of the chaotic algorithm with the other well-known algorithms. The maximum number of fitness evaluations (FEs) is 10,000 ×
Objective function value: algorithms were run 50 times for each benchmark function, and the average and SD were calculated.
The number of function evaluations (FEs): FEs are also recorded in our study; they are required to be less than . is fixed at , which is smaller and harder to reach than that used by Noman and Iba. The notation CNT indicates the number of runnings in which algorithms could reach . The maximum number of FEs is 10,000 ×
To obtain an unbiased result, we compared our algorithm with five well-known optimization algorithms of different types, such as evolutionary and warm-based algorithms. Several studies have shown that they have good performance on optimization problems. These algorithms include particle swarm optimization algorithm, Krill herd algorithm, and Biogeography-based optimization algorithm and their chaos-based algorithms. The experiments were carried out on a PC with a 3.60-Hz processor and 8.0 RAM in MatLab R2014b.
The global optimization toolbox used in our experiment includes PSO algorithms. We used the standard PSO algorithm;
This group contains twenty-three benchmark functions
From the results of the 23 benchmark functions, we can find that, in general, the chaotic algorithms outperform the other algorithms in terms of the average function value and the number of function evaluations. The results presented in this section confirm that the proposed chaotic algorithm exhibits a higher convergence velocity and greater robustness than the other algorithms.
4. Discussion and conclusion
The convergence properties of metaheuristics algorithms are strongly related to its stochastic nature and they use a random sequence for its parameters during running. Generating random sequences with a long period and a good uniformity are very important for easy simulating complex phenomena, sampling, numerical analysis, decision-making, and especially in heuristic optimization. Its quality determines the reduction of storage and computation time to achieve a desired accuracy. Chaos has properties of randomness, nonrepetition, and ergodicity; it matched the stochastic feature of metaheuristic optimization algorithms perfectly. Chaotic optimization not only accelerates the speed of algorithm, but can also enhance the variety of movement pattern.
Chaos has been observed in various applications widely. In this chapter, we used chaos theory combined with the latest algorithm to analyze the properties. The first advantage of chaotic algorithms is using fewer chaotic maps to enhance the searching capability. Secondly, chaotic optimization performs search at higher speed compared to the stochastic searches that rely on probability. Moreover, chaotic optimization is a simple structure and easy to implement. For future studies, it may be well worth employing chaotic algorithms for solving real-world engineering problems.
Assarzadeh Z, Naghsh-Nilchi AR. Chaotic particle swarm optimization with mutation for classification. Journal of Medical Signals and Sensors. 2015; 5(1):12
Saremi S, Mirjalili S, Lewis A. Biogeography-based optimisation with chaos. Neural Computing and Applications. 2015; 25(5):1077-1097
Goldberg DE, Holland JH. Genetic algorithms and machine learning. Machine Learning, 1988; 3(2):95-99
Storn R, Price K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 1997; 11(4):341-359
Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 2001; 9(2):159-195
Kennedy J. Particle swarm optimization. In Encyclopedia of machine learning. 2011;760-766. Springer US
Tang R, Fong S, Yang XS, Deb S. Wolf search algorithm with ephemeral memory. In: InDigital Information Management (ICDIM); 2012 Aug 22; IEEE; 2012
Gandomi AH, Yang XS, Alavi AH. Cuckoo search algorithm: A metaheuristic approach to solve structural optimization problems. Engineering with Computers. 2013; 29(1):17-35
Tang R, Fong S, Deb S, Raymond W. Dynamic group search algorithm. Computational and Business Intelligence (ISCBI). 2016
Tang R, Fong S, Deb S, Wong R. Dynamic group search algorithm for solving an engineering problem. Operational Research
Gandomi AH, Alavi AH. Krill herd: A new bio-inspired optimization algorithm. Communications in Nonlinear Science and Numerical Simulation. 2012
Wang GG, Guo L, Gandomi AH, Hao GS, Wang H. Chaotic krill herd algorithm. Information Sciences. 2014
Simon D. Biogeography-based optimization. IEEE transactions on evolutionary computation. 2008
Guo W, Li W, Kang Q, Wang L, Wu Q. Chaotic biogeography-based optimisation. International Journal of Computing Science and Mathematics. 2014