Abstract
Chaotic maps play an important role in improving evolutionary algorithms (EAs) for avoiding the local optima and speeding up the convergence. However, different chaotic maps in different phases have different effects on EAs. This paper focuses on exploring the effects of chaotic maps and giving comprehensive guidance for improving multiobjective evolutionary algorithms (MOEAs) by series of experiments. NSGA-II algorithm, a representative of MOEAs using the nondominated sorting and elitist strategy, is taken as the framework to study the effect of chaotic maps. Ten chaotic maps are applied in MOEAs in three phases, that is, initial population, crossover, and mutation operator. Multiobjective problems (MOPs) adopted are ZDT series problems to show the generality. Since the scale of some sequences generated by chaotic maps is changed to fit for MOPs, the correctness of scaling transformation of chaotic sequences is proved by measuring the largest Lyapunov exponent. The convergence metric γ and diversity metric Δ are chosen to evaluate the performance of new algorithms with chaos. The results of experiments demonstrate that chaotic maps can improve the performance of MOEAs, especially in solving problems with convex and piecewise Pareto front. In addition, cat map has the best performance in solving problems with local optima.
1. Introduction
Multiobjective evolutionary algorithms have attracted widespread attention and have been applied successfully in many areas, such as test task scheduling problem (TTSP) [1], reservoir operation [2], proportional integral and derivative (PID) controller [3], and distribution feeder reconfiguration (DFR) [4]. One key challenge in multiobjective evolutionary algorithms is the problem of resolving local optima and the speed of convergence. There are different solutions for improving evolutionary algorithms. Some approaches have been devoted to propose new algorithms, such as MOEA/D [5], SPEA-2 [6], and NSGA-II [7]. Other researchers have proposed a variety of hybrid algorithms, which combined the advantages of two different methods. For example, a new hybrid evolutionary algorithm (EA) based on the combination of the honey bee mating optimization (HBMO) and the discrete particle swarm optimization (DPSO), called DPSO-HBMO, is applied to solve the multiobjective distribution feeder reconfiguration (DFR) problem [4]. Another approach has focused on modifying original algorithms. For example, new particle swarm optimization (PSO) methods were proposed by using chaotic maps for parameter adaptation [8]. The results showed that chaos embedded PSO can improve the quality of results in some optimization problems. Chaos variables are loaded into the variable colony of the immune algorithm in the immune evolutionary algorithm, and the experimental results indicate that the new immune evolutionary algorithm improves the convergence performance and search efficiency [9]. Due to the characteristics such as randomness, regularity, ergodicity, and initial value sensitiveness, chaos has been widely applied in the original evolutionary algorithms to improve the performance.
Recently researches have been done to the chaos embed in evolutionary algorithms. For example, Alatas et al. [8] applied seven chaotic maps to generate seven new chaotic artificial bee colony algorithms. Three phases were adopted in generating these algorithms to solve three different benchmark single objective problems. Results showed that these methods have somewhat improved the solution quality. Tavazoei and Haeri [10] introduced ten chaotic maps in weighted gradient direction to solve two test functions. Results showed that none of these maps transcends other maps for all of the problems and desired criteria. Those researches demonstrated that chaotic sequences replacing the random parameters in three phases, including initial population, crossover operator, and mutation operator, can improve the performance of evolutionary algorithms. However, questions remain that for a given MOP, which chaotic map should be chosen in order to achieve the best performance. It is also not clean what kinds of combination of chaotic maps used in a particular phase have the best property. Therefore, it is difficult to give comprehensive guidance to improve the performance of evolutionary algorithms.
In addition, from the problems solved by COA, it can be seen that single objective optimization problems are the focus. Comparisons of different chaotic maps in improving the effects of COAs for solving single objective problems are common, but it is rare in solving multiobjective optimization problems (MOPs). Yu et al. [11] revealed that COA is not effective for solving MOPs, whereas the experiments in Alatas and Akin [12] showed the opposite. The results on these foregoing researches demonstrate that COAs are successful and competitive for solving single objective optimization problem, but effects of COAs on solving MOPs are not consistent.
In summary, although there have been many researches about the chaos and its application in COAs, the effects of different chaotic maps used in different phases on the performance of evolutionary algorithms have not yet been fully evaluated, especially for the multiobjective evolutionary algorithms.
In this paper, we explore the relationships of chaotic maps and phases on improving multiobjective evolutionary algorithms by a series of experiments. We will answer the question whether chaotic maps are suitable to improve the evolutionary algorithms in solving MOPs. We also investigate which phase should be chosen when one chaotic map is used to improve a multiobjective evolutionary algorithm.
In this research, NSGA-II is chosen as the main optimization algorithm, because it captures the core ideas and characteristics of MOEAs with the properties of a fast nondominated sorting procedure, an elitist strategy, a parameterless approach, and a simple yet efficient constraint-handling method [7]. Despite these good aspects of NSGA-II for solving MOPs, it may be entrapped into local optimal solutions. Thus, the properties of chaos can help to improve the performance of NSGA-II.
In order to reflect the diversity of chaotic maps, ten chaotic maps that have been widely used in pioneering researches are studied in this paper. They are circle map, cubic map, Gauss map, ICMIC map, logistic map, sinusoidal map, tent map, Baker’s map, cat map, and Zaslavskii map. Each chaotic map has its own property and has its own effect on improving the performance of evolutionary algorithms. For example, logistic map has Chebyshev-type distribution but not uniform distribution. As a result, it is necessary for optimal solution to go through multiple iterations.
Similar to past researches, chaotic maps are used in three common phases in evolutionary algorithms in experiments, that is, chaotic sequences for initial population, chaotic sequences for crossover operator, and chaotic sequences for mutation operator.
Five benchmark MOPs including ZDT1, ZDT2, ZDT3, ZDT4, and ZDT6 [7] are chosen as test problems. These MOPs have different characteristics and can reflect the property of evolutionary algorithms from different aspects. For example, we can use problem ZDT4 to evaluate the performance of evolutionary algorithms for resolving local optimal, because ZDT4 has different local Pareto-optimal solutions in the search space.
In addition, ranges of chaotic maps are not always fit for test problems. Scaling transformation is needed to apply chaotic sequences. For example, Coelho and Mariani [13] adopted Zaslavskii’s map by changing its range to and Alatas [12, 14, 15] took a similar approach. The problem is whether the chaotic sequences through scaling transformation still maintain the properties of chaos. In this paper, the correctness of scaling transformation of chaotic sequences is proved by measuring the largest Lyapunov exponent.
Finally, the criteria of convergence and distribution proposed by Deb et al. [7] are adopted in this paper to evaluate the effects of the combinations of phases and chaotic maps on improving the performance of multiobjective evolutionary algorithms. One is metric γ, which measures the extent of convergence to a known set of Pareto-optimal solutions. The other is metric Δ, which measures the extent of spread achieved among the obtained solutions.
From the results of experiments, it can be seen that NSGA-II embedded with chaotic maps in most cases get better results with regard to the metrics γ and Δ. The effects of using chaotic maps depend on which chaotic map is selected and in which phase it is used. In particular, chaos can improve the ability of NSGA-II in solving ZDT3 and ZDT6, which are difficult for the original NSGA-II algorithm. Besides, cat map is good at solving problems with local optima, such as ZDT4.
The rest of paper is organized as follows. Section 2 gives a summary of related work on applying chaos to improve evolutionary algorithms. Section 3 shows the phases in which chaos can be embedded in evolutionary algorithms. Section 4 defines ten chaotic maps which are embedded in NSGA-II in the experiments. Section 5 proves that the chaotic sequences through scaling transformation still hold the properties of chaos. Section 6 describes the test problems and metrics used in the experiments. Section 7 presents the performance results of the experiments. Section 8 concludes the paper.
2. Related Work
Applying chaotic maps to improve evolutionary algorithms has been studied for a while. There are two different strategies to apply the chaotic maps in the evolutionary algorithms.
One is to use chaotic sequences generated by chaotic maps to replace the random parameters needed by evolutionary algorithms. Coelho [16] proposed a quantum-behaved particle swarm optimization (QPSO). Random sequences of mutation operator in QPSO were replaced with chaotic sequences based on Zaslavskii map. The results demonstrated that it is a powerful strategy to diversify the population and improve the performance in preventing premature convergence to local minima. Dos Coelho and Alotto considered the chaotic crossover operator using the Zaslavskii map to solve multiobjective optimization problems [17]. Zhang et al. [18] proposed three chaotic sequences based multiobjective differential evolution (CS-MODE) to solve short-term hydrothermal optimal scheduling with economic emission (SHOSEE). In the modified mutation operator, chaotic theory is used to increase the population diversity, and some adaptive tuning parameters are produced by chaotic mappings to control the evolution.
The other strategy is to use the chaos optimization as an operator. For example, Alatas [14] applied chaotic search in case that a solution does not obtain improvements in artificial bee colony (ABC) algorithm. The results showed that the strategy has better performance than that of ABC algorithm. Wang and Zhang [19] employed chaos analogously. When the value of objective function had no improvement in continuous iterations, one chaotic system was applied to reinitialize half of the population. It replaced the worst half part of the population in order to jump out of the local optimum, whereas the best half part is kept unchanged.
Since evolutionary algorithms have sensitive dependence on their initial condition and parameters, the improvements on these parameters can have a good effect. That may be one of the reasons that the first strategy is widely adopted. In the first strategy, it is necessary to consider the phases of replacing random sequences with chaotic sequences and the different chaotic maps adopted.
For the phases of the evolutionary algorithms, Caponetto et al. [20] introduced chaotic sequences instead of random ones during all the phases of the evolution process. Results showed that the behaviors of all operators were influenced by chaotic sequences. Alatas [15], Ahmadi and Mojallali [21], and Ma [22] focused on random parameters in initial population. Coelho [16] and Zhang et al. [18] did their research on mutation operator. However, which phase is the best choice was not discussed.
To study the performance of different chaotic maps, some researchers give the comparisons of different chaotic maps solving both single objective optimization problems and MOPs. Talatahari et al. [23] proposed a novel chaotic improved imperialist competitive algorithm (CICA) for global optimization. Seven chaotic maps were utilized to improve the movement step of the algorithm, and the logistic and sinusoidal maps were found as the best choices. Caponetto et al. [20] proposed an experimental analysis on the convergence of evolutionary algorithms. Six chaotic maps, four phases, and single-objective statistical tests showed an improvement of evolutionary algorithms when chaotic sequences were used instead of random processes. Lu et al. [1] proposed a chaotic nondominated sorting genetic algorithm (CNSGA) to solve the automatic test task scheduling problem (TTSP). According to the different capabilities of the logistic and the cat chaotic operators, the CNSGA approach using the cat population initialization, the cat or logistic crossover operator, and the logistic mutation operator performs well and is very suitable for solving the TTSP. The comparisons of the performance of chaotic maps in these researches are based on solving one specific problem, so the results cannot be generalized to offer guidance on how to choose a chaotic map for solving other problems. Furthermore, most researches focus on single objective problems.
In contrast, this paper performs extensive experiments on genetic multiobjective evolutionary algorithms embedded with chaotic sequences. It focuses on exploring the relationships of phases and chaotic maps on improving multiobjective evolutionary algorithms. As mentioned above ten chaotic maps and three phases of evolutionary algorithms are considered. Five general benchmark problems are used to demonstrate that the conclusions can be generalized. Finally the guidance is presented to help researchers choose the suitable chaotic map and phases in multiobjective evolutionary algorithms for different MOPs.
3. Phases in Chaos Embedded Evolutionary Algorithms
With the ergodic property, chaos is adopted to enrich the searching behavior and to avoid solutions being trapped into local optimum in optimization problems. In this section three key phases in evolutionary algorithms, initialization, crossover, and mutation, are chosen to be embedded with chaos. Those three phases are described as follows.
3.1. Initialization
Initial population is the starting point of iterations. Ergodicity and diversity of initial population are very important for making sure that the individuals in the population spread in the search spaces uniformly as far as possible. In this case, initial population is generated by chaotic maps which can form a feasible solution space with good distribution by the properties of randomicity and ergodicity of chaos. Chaotic sequences can guarantee the diversity of the initial population, speed up its convergence, and enhance global search capability.
More specifically, a chaotic map, such as logistic map or cat map, is adopted instead of random population initialization of evolutionary algorithms. In the experiments of multiobjective evolutionary algorithms with chaos, the initial population is generated by chaos maps. For example, one of the individuals can be denoted by , , . For the logistic map initialization, .
3.2. Crossover Operator
Crossover operator is most important for evolutionary algorithms. Most of the offsprings are generated through the crossover operator. It has a great influence on the convergence speed. A good crossover operator may prevent premature convergence. Ergodicity of chaos helps search all the solutions, avoid solutions from falling into local optimum, and gain the global optimum.
There are many different crossover operators, such as simulated binary crossover operator [7] in NSGA-II algorithm and multiparent arithmetic crossover operator. Chaotic sequences substitute random parameters in the crossover operators. Chaotic sequences do not change the randomness of the parameter but display better randomness and therefore enhance the global performance of evolutionary algorithms.
In this paper, simulated binary crossover (SBX) operator is adopted in the experiment. According to SBX, two child individuals and are generated by a pair of parents and as follows: and is generated in the following manner: where is a random number in the range . is the distribution index for the crossover operator.
Since is a random number, can be generated by chaotic maps. For instance, if the chaotic map is a logistic map and in the th iteration , then in the th iteration, .
3.3. Mutation Operator
Mutation operator is indispensable in the process of evolutionary algorithms. This mechanism avoids solutions from falling into local optimum and guarantees more possibilities of obtaining global optimum. The properties of chaos, like randomness and sensitivity to initial conditions, contribute to preventing solutions from being trapped into local optimum.
Random parameters in mutation operators, for instance, polynomial variation, are replaced by chaotic sequences. For a solution , the polynomial mutation is described as where and are the upper and lower bounds of , and where is a random number ranging from 0 to 1. is the distribution index for the mutation operator.
The phase for mutation is that is calculated by chaotic maps in iterations. For example, if the chaotic map is logistic map, and in the th iteration , then in the th iteration, .
As a representative of MOEAs, the framework of NSGA-II algorithm is adopted in the experiments. In order to eliminate the effect of NSGA-II algorithm, other two different mutation operators, that is, Gauss mutation and Cauchy mutation, are chosen to replace polynomial variation.
3.3.1. Gauss Mutation
If random variable has the probability density function: then obeys Gauss normal distribution with the parameters , ; that is, .
Gauss mutation means that the random numbers obeying gauss distribution substitute in polynomial mutation; that is, .
3.3.2. Cauchy Mutation
The probability density function of Cauchy distribution concentrated near the origin. It is defined as
It is similar to Gauss probability density function. The difference is that the value of Cauchy distribution is lower than the value of Gauss distribution in the vertical direction, and Cauchy distribution is closer to the horizontal axis in the horizontal direction. Cauchy mutation means that the random numbers obeying Cauchy distribution substitute in polynomial mutation.
4. Chaotic Maps
Chaotic maps generate chaotic sequences in the process of evolutionary algorithms. Ten chaotic maps including both one-dimensional maps and two-dimensional maps are introduced in this section. They will be used to improve the performance of MOP algorithms.
4.1. One-Dimensional Maps
(1) Circle Map. Circle map is a member of a family of dynamical systems on the circle first defined by Andrey Kolmogorov. He proposed this family as a simplified model for driven mechanical rotors specifically, a free-spinning wheel weakly coupled by a spring to a motor. The circle map equations also describe a simplified model of the phase-locked loop in electronics. The circle map [24] is given by iterating the map: with and ; it generates chaotic sequence in .
(2) Cubic Map. Cubic map is one of the most commonly used maps in generating chaotic sequences in various applications. This map is formally defined by the following equation [25]:
Cubic map generates chaotic sequences in with .
(3) Gauss Map. Gauss map is also one of the well-known and commonly employed maps in generating chaotic sequences [26] as follows:
This map also generates chaotic sequences in (0, 1).
(4) ICMIC Map. The iterative chaotic map with infinite collapses (ICMIC) [27] is defined by the following equation:
The parameter “” is an adjustable parameter. This paper chooses . Because the range of is not , the chaotic sequences need to be transformed to change the range.
(5) Logistic Map. As a well-known chaotic map, logistic map is one of the simplest maps and was introduced by May in 2004 [28]. It is often cited as an example of how complex behavior can arise from a very simple nonlinear dynamical equation. Logistic map generates chaotic sequences in . This map is formally defined by the following equation:
Parameter is set to 4 in the simulation.
(6) Sinusoidal Iterator. The sinusoidal iterator [29] is formally defined by the following equation: In this paper the simplified equation is used in the following iteration: (7) Tent Map. Tent chaotic map is very similar to the logistic map, which displays specific chaotic effects [30]. This map is defined by the following equation: where is ranging from 0 to 1.
Tent map generates chaotic sequences in (0, 1).
4.2. Two-Dimensional Maps
(1) Baker’s Map. The Baker map [31] is described by the following formulas:
In the following simulations, one dimension of Baker’s map, which is similar to tent map, is adopted. The equation is defined by
This map generates chaotic sequences in (0, 1).
(2) Arnold’s Cat Map. Arnold’s cat map is named after Vladimir Arnold, who demonstrated its effects in the 1960s using an image of a cat. It is represented by [32]
It is obvious that the sequences and .
(3) Zaslavskii Map. Zaslavskii map [33] is an interesting dynamic system with chaotic behavior. The discretized equation is given by
The Zaslavskii map shows a strange attractor with the largest Lyapunov exponent for , , and . In this case, it can be calculated that . Only one dimension is chosen in the following simulation. Since the scale of is not , the chaotic sequences generated need scale transformation.
5. Chaotic Properties of Sequences Generated by Scale Transformation
As mentioned in the previous sections, the scale of sequences generated by chaotic maps is not always fit for the problems to be solved. Some sequences have to change their scale, and some sequences are generated by one dimension of a two-dimension chaotic map. Hence, it is necessary to demonstrate the chaotic properties of sequences after these changes.
Detecting the presence of chaos in a dynamical system is usually solved by measuring the largest Lyapunov exponent which describes quantitatively the speed of index divergence or convergence between the adjacent phase space orbits. A positive largest Lyapunov exponent indicates chaos. Since the chaotic sequences adopted in this paper are discrete, the Lyapunov exponent of discrete series can be calculated by small data sets arithmetic [34]. This method makes full use of all the data, obtains higher accuracy, and has stronger robustness for the amount of data, the embedding dimension, and the time delay.
5.1. Small Data Sets Arithmetic
The reconstructed trajectory, , can be expressed as a matrix where each row is a phase-space vector; that is, where is the state of the system at discrete time . For an -point time series, , each is given by where is the lag or reconstruction delay, and is the embedding dimension. Thus, is an matrix, and the constants , , , and are related as After reconstructing the dynamics, the algorithm locates the nearest neighbor of each point on the trajectory. The nearest neighbor , where , is found by searching for the point that minimizes the distance to the particular reference point . This is expressed as where is the initial distance from the th point to its nearest neighbor, and denotes the Euclidean norm. We impose an additional constraint that the nearest neighbors have a temporal separation greater than the mean period of the time series: where is the mean period of time series. can be estimated by the reciprocal of the mean frequency of the power spectrum. This allows us to consider each pair of neighbors as nearby initial conditions for different trajectories. The largest Lyapunov exponent is estimated as the mean rate of separation of the nearest neighbors.
For each reference point , is the distance between the th pair of nearest neighbors after discrete time:
Assume that reference point and its nearest neighbor have index divergence rate ; then where is the initial separation. By taking the logarithm of both sides of (25) we get Equation (26) represents a set of approximately parallel lines (for ), each with a slope roughly proportional to . The largest Lyapunov exponent is easily and accurately calculated using a least square fit to the “average” line defined by where denotes the average over all values of . So where is the number of with .
Choose a linear area of the curve , and apply the least square method to get the regression straight line. Then the slope of the regression straight line is the largest Lyapunov exponent .
5.2. The Lyapunov Exponent of Sequences
In the calculation process, the embedding dimension is calculated through the method of false nearest neighbors (FNN). For the time delay , a good approximation of is equal to the number lagging where the autocorrelation function drops to of its initial value.
Since different test problems have different ranges, chaotic sequences need to be changed to different scales. Two kinds of sequences used in experiments need to be investigated: sequences with scales changed and sequences generated by one dimension of a two-dimension chaotic map.
5.2.1. Sequences with Scales Changed
Since the sequence to generated by ICMIC is not in , the new sequence to has to be generated by the following function:
The sequence to is in the range of . The Lyapunov exponent of the new sequence is calculated through small data sets arithmetic. The average Lyapunov exponent of 10 runs is 0.0744. Since it is a positive number, the new sequence to conforms to the chaotic nature.
5.2.2. Sequences Generated by One Dimension of a Two-Dimension Chaotic Map
For the Zaslavskii map, one dimension is chosen in the following simulation. The sequence to is generated by 100 iterations through Zaslavskii map. The new sequence to is generated by the following function: Then the sequence to is in . By a similar processing with ICMIC, the average Lyapunov exponent is 0.00194. Then the new sequence to conforms to the chaotic nature.
6. Test Problem and Performance Measures
6.1. Test Problems
Two-objective optimization problems are chosen to test and measure the performance improvement of the evolutionary algorithms using chaotic maps in three phases. We use well-defined benchmark functions as objective functions. Their properties are shown in Table 1.
6.2. Performance Measures
Two criteria are used to evaluate the performance of multiobjective optimization: (1) convergence to the Pareto-optimal set and (2) maintenance of diversity in solutions of the Pareto-optimal set [7]. Two metrics are adopted to evaluate the effects of the combinations of phases and chaotic maps.
The first metric γ measures the extent of convergence to a known set of Pareto-optimal solutions. It is defined as where is the minimum Euclidean distance of every obtained solution to the Pareto-optimal front. The smaller the value of this metric is, the nearer the convergence toward Pareto-front is.
The other metric Δ measures the extent of spread achieved among the obtained solutions. The metric Δ is defined by The parameter is the Euclidean distance between consecutive solutions in the obtained nondominated set of solutions. The parameters and are the Euclidean distances between the extreme solutions and the boundary solutions of the obtained nondominated set. The parameter is the average of all distances , assuming that there are solutions on the best nondominated front.
7. Experiments and Results
To explore the relationship of phases and chaotic maps to solve MOPs, NSGA-II algorithm is chosen as the main framework. The ten chaotic maps mentioned in Section 4 are embedded in three different phases in the original NSGA-II algorithm. Each time only one parameter is modified. For example, if initial population is generated by chaotic map, the crossover and mutation operator are not changed. Similarly, if crossover operator is modified by a chaotic map, the initial population and mutation operator are not changed. The solutions, generated by the chaos embedded NSGA-II algorithm, are evaluated by two metrics: γ and Δ. For reader’s convenience, the new algorithms with different combinations of chaotic maps and phases are named as “cns_[chaotic map]_[phase],” and the results of different algorithms on test problems are named as “cns_[chaotic map]_[phase]_[test problem].” In addition, “i” represents the phase for initial population, “c” represents the phase for crossover operator, and “m” represents the phase for mutation operator. For example, the results through modified initial population by logistic map solving ZDT1 problem are named as “cns_logistic_i_zdt1.”
Each combination of one chaotic map and one phase needs one experiment. In this research, 10 chaotic maps with 3 different phases based on 2 metrics solving 5 test problems need 150 basic experiments and obtain 300 results. Each experiment obtains a Pareto front. The values of convergence metric γ and the diversity metric Δ are also calculated.
In order to compare with the results of original NSGA-II algorithm, we focused on the difference of the γ and Δ values of the original NSGA-II algorithm and the new algorithm. For example, the γ of results of “cns_sinusoidal_i_zdt1” is named as “cns_sinusoidal_i_zdt1_gama,” and the γ of results of NSGA-II solving ZDT1 problem is named as “ns_zdt1_gama.” Then the difference is named as “ns_zdt1_gama—cns_sinusoidal_i_zdt1_gama.” When the processes of algorithms get to convergence, the difference is very small. The properties of convergence and diversity in the process of iterations need to be taken into account, so the γ values of each generation in the iterations are recorded and the differences of γ of each generation are obtained. This process also applies to Δ.
Some main parameters in the process of NSGA-II algorithm are introduced in the following paragraphs. Then the results of experiments are shown and analyzed.
7.1. The Main Parameters
The main parameters in the process of NSGA-II algorithm are presented in this section. Choosing an appropriate representation of a chromosome is very important for solving problems. Real numbers are chosen to represent the genes. One chromosome represents one individual. The initial population has 100 individuals, and each chromosome has a certain number of genes which are represented by a real number. Each individual of the initial population is generated randomly with the range based on the test problems. The iteration will not terminate until the number of iterations gets to 250. For the process of NSGA-II algorithm, a parent population is selected by tournament selection depending on the nondominated rank and the crowed-comparison operator. Then the new population is generated by crossover and mutation operators. The crossover operation is executed with the probability of . The probability of mutation is equal to the reciprocal of , which is the dimension number of a chromosome; that is, .
Those parameters are summarized in Table 2. In the table, is the number of iterations, is the scale of the population, is the number of dimensions of a chromosome, and and are the probabilities of crossover and mutation operations.
7.2. Convergence Performance
It is known that the γ difference is used to evaluate the performance of the chaotic maps in different phases in multiobjective evolutionary algorithms. An example is chosen for further explanation in detail. As in Figure 1, the graph shows the results of solving ZDT1 problems with Baker’s map in crossover operator in NSGA-II. The differences of γ between the experiment “cns_baker_c_zdt1” and the experiment “ns_zdt1” in the 250 iterations are given. As seen from the figure, the black line is above the red line which represents 0, so the new algorithm “cns_bakers_c” is better than NSGA-II algorithm in solving ZDT1 problem with regard to the convergence metric.
The γ results of all the experiments are given similar to Figure 1. Since it is difficult to show so many graphs in this paper, the results of three typical problems are chosen, that is, ZDT1, which is a simple convex problem, ZDT3, whose Pareto front is piecewise, and ZDT4, which has local optima. The graphs in Figures 2, 3, and 4 provide a comparison of the performance of solving different MOPs with chaotic maps in initial population. ZDT4 is chosen to show the performance of chaotic maps in different phases on solving the same MOP, as shown in Figures 4, 5, and 6. Each subgraph is labeled with the name of the chaotic map used.
In order to quantify the effect of chaotic maps and phases with regard to the metric γ, the average of γ difference in 250 generations is calculated to represent the effect of the new algorithms.
Since the order of magnitude of γ is not the same, the comparison of these γ values is not convenient. The normalized values are obtained by dividing the γ values by the maximum of the absolute values of the γ based on one test problem. The results of normalization are shown in Table 3.
Table 3 can be presented in a more intuitive way. If , the numerical value of γ is replaced by “++.” Similarly, “+” represents , “0” represents , “−” represents , and “− −” represents . Therefore “++” means that the effect of the new algorithm with chaotic maps is much better, whereas “− −” is much worse. Table 4 shows the results.
As shown in Table 4, most of the combinations of chaotic maps and phases have a positive effect on improving the performance of NSGA-II algorithm. The effect of some chaotic maps is very good, especially in some particular phases. For example, Baker’s map in crossover operator, Gauss map in crossover operator and initial population, ICMIC map in initial population, sinusoidal map in initial population, tent map in crossover operation, and Zaslavskii map in initial population have very good effect.
Since ZDT4 problem has or different local Pareto-optimal fronts in the search space, the solutions easily get entrapped into local optimum. As seen from Table 4, chaotic maps used for crossover and mutation operator have significant improvement on evolutionary algorithms solving ZDT4 problem; especially cat map has the best performance in ten maps. Circle map and cubic map have less contribution in solving those MOPs. The distribution of cat map is relatively uniform. It is probably the reason for the good performance in solving problems with local optima.
The original NSGA-II algorithm is not good at solving ZDT3 and ZDT6 problems, because Pareto-optimal front of ZDT3 is disconnected and solutions of ZDT6 are nonuniformly spaced. However, it can be seen in Table 4 that chaotic maps can improve NSGA-II especially in crossover operation and initial population in solving ZDT3 and ZDT6 problem.
In order to eliminate the special effect of the NSGA-II algorithm, the polynomial mutation operator in NSGA-II is changed by the Gauss mutation and Cauchy mutation operators. Four typical chaotic maps, which include two chaotic maps with best performance and two chaotic maps with worst performance, are chosen to be used in the experiments. These chaotic maps are circle map, cubic map, sinusoidal map, and tent map. The values of γ differences are shown in Tables 5 and 6. As seen from Tables 5 and 6, the performance of sinusoidal map and tent map is better than the performance of circle map and cubic map. Sinusoidal map in initial population is better than that in crossover operation, and tent map in crossover operation is better than that in initial population. This means the rules of combinations of chaotic maps and phases in solving MOPs are almost the same as in the previous observations. So the rules based on the framework of NSGA-II algorithm are applicable to other MOEAs.
In general, Baker’s map with a phase for crossover operator, sinusoidal map with phases for initial population and mutation operator, and tent map with a phase for crossover operator could be the best choice for improving evolutionary algorithms for MOPs without local optimum. For problems with local optimum, cat map has good performance on improving evolutionary algorithms.
7.3. Diversity Performance
Similar to the convergence metric γ, the differences of the diversity metric Δ between the results of the new algorithm with chaotic maps and the original NSGA-II algorithm are used to measure the performance. Figure 7 shows the performance of chaotic maps in crossover operator in solving ZDT1 with metric Δ. Each subgraph shows the effect of one chaotic map. To be seen more clearly, the first subgraph in Figure 7 is shown in Figure 8.
As seen from Figures 7 and 8, the Δ difference is not stable in 250 generations. The average values of Δ difference in 250 generations are calculated to represent the effect of the new algorithms. For brevity, the rest of results are not shown in graphs but in Table 7.
As seen from Table 7, the Δ values have little difference. We count the number of combinations of chaotic maps and phases for solving one problem in different threshold values. For example, there are 18 combinations whose values of Δ are greater than zero. Based on the number of the combinations of chaotic maps and phases in different threshold values, the values of diversity metric Δ are summarized in Table 8.
In Table 8 the rank of the number of Δ in different threshold values is , especially for larger threshold. ZDT1 problem, which is a convex function and has no local optima, is a relatively easy problem. Chaotic maps bring the biggest improvements on solving ZDT1. Though the solutions of ZDT6 are nonuniformly spaced, chaotic maps can find better spread of solutions. While ZDT4 problem is a complex problem and the solutions are easily trapped into local optima, chaotic maps can improve the distribution of the solutions. ZDT2 problem is a convex function, and the solutions sometimes fall into the local optimum. The effects of chaotic maps can be generalized. The Pareto front of ZDT3 problem is segmented, so the Δ value of ZDT3 is larger and the ranking of ZDT3 is lower. It is our observation that Δ is not fit for evaluating the solutions to problems which are disconnected.
Based on the diversity metric Δ, chaotic maps have the best improvement on solving convex problems without local optima and have better effect on solving problems which have nonuniform solutions. For problems with local minimum, chaotic maps embedded algorithms can improve the performance with regard to metric Δ.
A short summary can be given according to the above experiments. First, chaotic maps can improve the performance of MOEAs, but the results showed that no one chaotic map outperforms other maps for all of the problems. The results in this paper give some guidance on how to choose a chaotic map and a phase in MOEAs. Second, an interesting discovery is that cat map has best performance on solving problems with local optima. Uniformity of cat map may be one of the reasons for the good performance of solving ZDT4.
8. Conclusion
The focus of this paper is to explore the relationships of chaotic maps and phases in MOEAs in solving MOPs. The main framework of algorithms in experiments is the NSGA-II algorithm. The combinations of ten chaotic maps and three phases are chosen in the experiments. Two metrics, convergence metric γ and diversity metric Δ, are used to evaluate the convergence and diversity properties of the algorithms with chaotic maps. The test problems are ZDT series which were all MOPs. The ergodicity and initial value sensitivity of chaotic maps can help evolutionary algorithms avoid solutions from falling into local optimal and get better convergence. In the experimental results, almost all chaotic maps have good effects on improving the performance of evolutionary algorithms to solve MOPs without local optima. Cat map has best performance on solving problems with local optimum. This work gives insight on choosing chaotic maps and phases for different problems. Our future work will perform further experiments with more chaotic maps on other MOEAs and formulate the theory analysis.
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
Acknowledgment
This research is supported by the National Natural Science Foundation of China under Grant no. 61101153 and Prof. Qiu is supported by NSF CNS 1359557.