Chaotic Optimization

Logo of tswjThe Scientific World Journal
. 2015; 2015: 704587.
Published online 2015 Mar 24. doi: 10.1155/2015/704587
PMCID: PMC4387984
PMID: 25879067

From Determinism and Probability to Chaos: Chaotic Evolution towards Philosophy and Methodology of Chaotic Optimization

1. Introduction

Philosophy of determinism comes from the development of classic mechanic that was originally established and studied by Isaac Newton, Pierre-Simon Laplace, Gottfried Wilhelm Leibniz, and so forth. Strict determinism indicates that causality can be expressed and implemented by mathematical calculation and logical reasoning. As Pierre-Simon Laplace said, “we may regard the present state of the universe as the effect of its past and the cause of its future” []. In the philosophy of determinism, everything is deterministic and predictable. However, the discovery of probability breaks dominated position of determinism in scientific philosophy. Particularly, the proposal of law of larger numbers extends the recognition scale of science, which explains the relationship between probability and frequency. The two philosophies and methodologies, determinism and probability, dominate researches in science until the discovery of chaos, another philosophy and methodology which can present and explain the natural world. In optimization field, deterministic and stochastic optimization algorithms are theoretically supported by philosophy and methodology of determinism and probability. However, because some fundamental works of chaos theory are not completed yet, research and development of chaotic optimization algorithm are still rarely mentioned and studied in optimization field. This paper tries to present a limit work on chaotic optimization algorithm with evolution concept.
Most of evolutionary computation (EC) algorithms are inspired from natural phenomena, such as genetic algorithm that mimics the process of natural selection and survival of the fittest. EC can be involved in continuous and combinational optimization problems, and its algorithm has a metaheuristic or stochastic characteristic in their search mechanisms []. As EC algorithms have been developed further and deeply, not only biological phenomena but also physical and mathematical phenomena and mechanisms are introduced into EC area to implement new EC algorithms. This research subject is one of computational paradigm studies in natural computing area and enriches research context of computational intelligence. In a viewpoint of EC search scheme, its algorithms encompass two components in their search mechanisms. One is a search methodology by a variety of implementations, and the other is an iterative process to simulate evolution. Most of EC algorithms do not require the optimization problem to have some specific characteristics, and few of them utilize any mathematical properties or mechanisms to ensure convergence of the algorithms. If we introduce mathematical optimization property or mechanism that simulates the natural phenomena, such as chaotic ergodicity, into an optimization iterative process, we may implement new EC algorithms that partially ensure their convergence. The hint and philosophy behind this motivation benefit are to improve the global convergence characteristic of the algorithm.
The study on chaos theory comes from the real problems of physics, ecology, and mathematics since three-body problem was studied by Poincare et al. []. It is developed originally to describe the system behaviour that cannot be described either by deterministic system or by stochastic system, which enriches our knowledge on unpredictable property of natural system. That means the system cannot be normalized by a set of differential equations or probability density function. Chaos and chaotic system have many characteristics for implementing an evolutionary search prototype and framework and improving EC algorithms. Nonlinearity, ergodicity, and sensitiveness are major explicit properties of chaos and chaotic system. The ergodicity of chaotic system can support more diversity to enhance exploration and exploitation capability of EC algorithms. It can approach to any desired point in search space with arbitrary accuracy and movement track. The sensitiveness of initial condition of chaotic system can lead to different search paths and escape from local optima for enhancing search performance of EC algorithms. The motion of perturbation around chaotic attractor can be simulated as an optimization search scheme and framework by EC.
There are typically three applications in which chaos is used in optimization area, that is, a local search method, a parameter tuning technique, and the new EC algorithm inspiration resource. Some chaotic systems are introduced into conventional EC algorithm frameworks to make population diversity in local search and to tune the parameters of algorithm []. The ergodicity property and behaviour are modelled as a search prototype to make a new EC algorithm, such as chaotic evolution optimization framework []. Chaotic Krill Herd algorithm was proposed by fusing Krill Herd algorithm and chaos theory [], and some of its improved versions were proposed and studied [].
Chaotic evolution (CE) is a population-based algorithm framework that simulates chaotic motion behaviour in a search space []. Because of the ergodicity of chaotic system, chaotic motion can visit any point with arbitrary accuracy. CE algorithms take into account ergodicity property in its search mechanism to implement a new optimization scheme. There are three parameters as algorithm setting in its framework, a chaotic system and its parameter(s), a direction rate to guide the percentage of search direction, and a crossover rate. The chaotic system supports a basic simulation parameter, chaotic parameter, to implement the search function. Parameter of the chaotic system is simply set at the value that can lead to a chaotic output of the system. The direction rate decides search direction of each individual in CE algorithm, which is usually set at a random value. The crossover operation reserves extensibility of CE algorithm for further study, which can be set at 100%. It means that the mutant vector of CE algorithm can be directly presented as the chaotic vector of CE algorithm. For an empirical study, it is not a necessary parameter in CE optimization framework []. However, we cannot deny its effectiveness in theory from our current best knowledge.
This paper extends the work of [] by introducing new chaotic systems into the CE algorithm framework and conducts a comparison study with DE algorithms. We use 25 benchmark functions with 10- and 30-dimensional setting to evaluate our new designed CE algorithms. We also establish a new interactive EC (IEC) algorithm by using CE optimization framework and evaluate its performance by using a pseudo-IEC user, that is, a Gaussian mixture model. Some statistical tests, such as Wilcoxon sign-ranked test, Friedman test, and Bonferroni-Dunn's test, are applied to evaluate significance and ranking of the algorithms in the related experiments and discussions. This work does not pursue obtaining a final winner algorithm from comparisons but to discover and discuss the fundamental aspect of CE from viewpoint of chaotic optimization and optimization mechanism of CE algorithm with different chaotic systems behind the evaluation results. Some study subjects are analysed and discussed taking into account evaluation results and statistical tests. These topics are the relationship between distribution characteristic of chaotic system and optimization performance, algorithm ranking, interactive CE algorithm, disadvantages and improvement approaches of CE algorithm, a notation system of CE, and so forth. These research subjects present the originality and primary contribution of this paper.
Following this introductory section, an overview of the CE algorithm framework and chaotic systems used in this paper are reported in Section 2. We present several new CE algorithms in this paper, which demonstrates scalability of the chaotic algorithm framework. Interactive CE (ICE) algorithm framework is introduced in Section 2 as well. In Section 3, experimental evaluations of chaotic evolution are performed and some statistical tests are applied. We discuss our proposed CE algorithms and obtained evaluation results. In Section 4, we analyse our proposed new IEC algorithm. We discuss some issues based on ICE experimental simulation using a pseudo-IEC user, which is implemented by a Gaussian mixture model. The topic on algorithmic notation of CE is defined for its further development and study. Finally, we conclude the whole work, and some open topics, further opportunities, and future works are discussed in Section 5.

2. Chaotic Evolution Algorithm Framework, Interactive Chaotic Evolution, and Chaotic System

2.1. A Brief Review of Chaotic Evolution Algorithm

Deterministic system and stochastic system are two views in which we understand and describe the nature in philosophy and in science. They lead to two corresponding algorithm methodologies in optimization field, that is, deterministic and stochastic optimization algorithms. Evolutionary computation can be partially categorized into the later one, that is, stochastic optimization algorithm. However, since chaotic phenomenon and mechanism were found [], chaos and chaotic system are as well a tool to describe and study the nature besides deterministic and stochastic systems. In optimization field, there must be a set of chaotic optimization algorithms inspired and normalized by chaotic philosophy and methodology. This is the fundamental motivation that prompts us to discover and study new optimization algorithms in the viewpoint of chaotic optimization.
The concepts of “evolution” and “chaos” have more the same characteristics in common []. First, both words refer to the phenomena that need to be explained and to the theories that are supported to do the explaining []. Second, there must be an iteration in both evolution and chaos processes, so the phenomena of them can appear. Third, the concepts and theories of evolution and chaos influence and enhance all research works by introducing and fusing the fundamentals of their concepts and approaches.
Inspired from chaotic motion of nonlinear system that has an ergodicity property, a chaotic ergodicity based EC algorithm, chaotic evolution, was proposed and studied recently []. It simulates the chaotic motion in a search space for implementing optimization. Because chaotic motion has an ergodicity property, the proposed algorithm can guarantee its global convergence partially. The scalability of the algorithm is better than other EC algorithms by introducing different chaotic systems.
Suppose that an array on the left side of Figure 1 presents individuals, contour lines at the right side are a fitness landscape, and circles on the landscape are the individuals. CE algorithm for one search generation is described below. It is repeated until a satisfied solution is found or the search reaches to the desired generations.
  • (1)
    Choose one individual as a target vector.
  • (2)
    Obtain a chaotic parameter from a chaotic system
    CPi = Chaotic  System (CPi−1).
  • (3)
    Make a mutant vector by
    Mutant  Vec⁡.i = Target  Vec⁡.i(1 + DiCPi).
  • (4)
    Generate a chaotic vector by crossing the target vector and the mutant vector
    Chaotic  Vec⁡.i = Cr(Mutant  Vec⁡.i, Target  Vec⁡.i).
  • (5)
    Compare the target vector and the chaotic vector and choose whichever a better one as offspring in the next generation.
  • (6)
    Go to (1) and generate other offspring until all individuals are replaced with offspring in the next generation.
An external file that holds a picture, illustration, etc.
Object name is TSWJ2015-704587.001.jpg
Chaotic evolution algorithm framework; there are three special vectors in chaotic evolution algorithm, a target vector that is an individual in the population, a mutant vector that simulates the chaotic motion from a chaotic system, and a chaotic vector that is made by conducting crossover operation on a target vector and a mutation vector.
The terms of vector and individual mean the same search points. (1)–(4) are summarized as in (1), (2), and (3). This sketches the chaotic evolution algorithm which is easily implemented, where D i is called a direction factor and CPi is a chaotic parameter. There are several chaotic evolution variations in (1) for selecting different chaotic systems, crossover methods in (4), and others. After initial population needs fitness evaluation once, only the chaotic vector in (5) needs a fitness evaluation in every generation.

2.2. Interactive Chaotic Evolution Algorithm

Interactive evolutionary computation (IEC) is a niche research field in EC community []. The primary objective of IEC purposes solving the optimization problems that should embed subjective evaluation of real human into the optimized solution. Most of the evaluation spaces of IEC application are hard to be explicitly expressed or cannot be represented at all, so the real human's evaluation is necessary to achieve the final optimal solution. However, human fatigue is a serious issue for an IEC optimization application, because a real human has his or her evaluation limitation, and physiological or psychological tolerance capacity comparing with a tirelessness computer. So to relieve human's fatigue is a practical problem in IEC algorithm study and application.
From a framework viewpoint, there are three main parts in an IEC based optimization system. They are (1) a target system that is optimized, (2) an IEC algorithm (including an IEC interface) that conducts actual optimization function, and (3) a real human who provides his or her evaluation. The target system and the real human are fixed in an IEC optimization application, so there is a study subjective to relieve human's fatigue in the IEC algorithm part. One is to enhance optimization performance of IEC algorithm. The other is to improve IEC interface for a user friendly interaction.
If we implement a CE algorithm in an IEC application and replace the fitness function with a real human's evaluation, the IEC framework is an implementation of interactive chaotic evolution (ICE). In the nature of ICE algorithm, there is a paired comparison-based mechanism when surviving an offspring between chaotic vector and target vector. In an IEC application, these two vectors present two IEC solutions for a real human to perform evaluations. Comparing with other IEC algorithms, such as interactive genetic algorithm (IGA), this paired comparison mechanism benefits real human's evaluation rather than evaluating all individuals together as in IGA. If the ICE algorithm can present significantly optimization performance compared to other paired comparison-based IEC algorithms, such as interactive differential evolution (IDE) [] or its variations [], ICE can be a practical algorithm implementation in IEC framework and enrich IEC algorithm family. We will investigate this subject in this paper.

2.3. Chaotic Systems

The search function of CE is implemented by generating a chaotic vector. It is decided by chaotic parameter from a chaotic system, which has the ergodicity property. By applying a variety of chaotic systems in the CE algorithm framework, we can implement its variations in different way. In this study, we introduce four chaotic systems, that is, logistic map, tent map, Gaussian map, and Hénon map to investigate the optimization performances of CE with these four chaotic maps. Here, we make a brief review on these chaotic maps.

2.3.1. Logistic Map

The logistic map is a polynomial mapping with two degrees that can arise from a chaotic phenomenon by a simple nonlinear system easily []. Equation (4) shows its mathematical expression, where μ is a parameter that decides the behaviour of system; μ is usually set at (0,4]. For the values of μ > 4, the map does not project interval [0,1] into itself. When μ = 4, the system arises from chaotic phenomenon. The bifurcation diagram of logistic map is shown in Figure 2(a) that presents the whole system behaviour:
xn = μxn−1(1 − xn−1).
Bifurcation digrams of (a) logistic map, (b) tent map, (c) Gaussian map, and (d) Hénon map. Parameter μ in logistic map can be set at (0,4]; chaos happens when μ = 4 in (a). Parameter μ in tent map can be set at [1,2]; chaos happens when μ = 2 in (b). Parameter β in tent map can be set at [−1, +1]; chaos happens when α = 6.20 and β = −0.5 in (c). Parameters a = 1.4 and b = 0.3 are a classic setting in Hénon map; one of its invariant points on the attractor, x=(6097)/28=0.631354477 and y=(36097)/280=0.189406343, can be used as an initial value setting.

2.3.2. Tent Map

The tent map is defined as in (5) whose function curve is like the tent-like shape. The parameter μ is within (0,2]. Depending on the value of μ, the tent map demonstrates a range of dynamical behaviours from predictable to chaotic (see its bifurcation diagram in Figure 2(b)). When μ equals 2, the map becomes chaotic:
xn={μxn1μ(1xn1)if  0xn<0.5,if0.5xn1.

2.3.3. Gaussian Map

The Gaussian map is a nonlinear map that is given by a Gaussian function (equation (6)), whose bifurcation diagram resembles a mouse (Figure 2(c)). The system can become chaotic, when the parameters α and β are set at 6.20 and −0.5, respectively:

2.3.4. Hénon Map

The Hénon map has two points (x ny n) in the plane, and it maps them into a new point (equation (7)). The system behaviour depends on its parameters, that is, a and b. Different from the other chaotic maps, Hénon map is a two-dimensional nonlinear system. It is chaotic when its parameters have values of a = 1.4 and b = 0.3, which is a classic parameter setting. For other values of a and b, the map may be chaotic or intermittent or converge to a periodic orbit (Figure 2(d)). The Hénon map does not have a strange attractor for all values of the parameters a and b, but there are invariant points on the attractor; x=(6097)/28=0.631354477 and y=(36097)/280=0.189406343 are examples of them:

3. Chaotic Evolution Optimization Evaluation Analysis and Discussion

3.1. Experimental Settings and Results

We use 25 benchmark functions from [] to evaluate our proposed CE algorithms with new introduced chaotic systems. Table 1 presents their type, characteristic, search bound, and optimum fitness value of these benchmark functions. For all benchmark functions, its dimensional settings are 10 and 30. For all algorithms, it runs up to 1000 generations with 30 trails running. The population size is 5∗dimension; that is, 50 and 150 are for 10D and 30D benchmark functions, respectively.

Table 1

Test functions (Uni = unimodal, Multi = multimodal, Sh = shifted, Rt = rotated, GB = global on Bounds, HC = hybrid composition, and NM = number matrix).
NumberTypeCharacteristicBoundsOptimum fitness
f 1UniSh sphere[−100,100]−450
f 2Sh Schwefel 1.2−450
f 3Sh Rt Elliptic−450
f 4f 2 with noise−450
f 5Schwefel 2.6 GB−310

f 6MultiSh Rosenbrock[−100,100]390
f 7Sh Rt Griewank[0,600]−180
f 8Sh Rt Ackley GB[−32,32]−140
f 9Sh Rastrigin[−5,5]−330
f 10Sh Rt Rastrigin[−5,5]−330
f 11Sh Rt Weierstrass[−0.5,0.5]90
f 12Schwefel 2.13[ππ]−460
f 13Sh expanded F8F2[−3,1]−130
f 14Sh Rt Scaffer F6[−100,100]−300

f 15HybridHC function[−5,5]120
f 16Rt HC function 1120
f 17f 16 with noise120
f 18Rt HC function 210
f 19f 18 with basin10
f 20f 18 with GB10
f 21Rt HC function 3360
f 22f 21 with NM360
f 23NC Rt f 21360
f 24Rt HC function 4260
f 25f 24 without bounds260
There are five CE algorithms in our evaluation, that is, CE-logistic, CE-tent, CE-Gauss, CE-Hénon-rand, and CE-Hénon-attrac. Two DE algorithms (DE/best/1/bin and DE/rand/1/bin) are used to be compared with CE algorithms []. Abbreviations and their meaning are in Table 2. CE with Hénon map has two initialization methods. One uses random value within (0, 1] (CE-Hénon-rand), and the other uses an attractor, x=(6097)/28=0.631354477 and y=(36097)/280=0.189406343 (CE-Hénon-attrac.). Other chaotic systems of chaotic evolution algorithms use the uniform random number within (0, 1] as their initial value. The evaluation hardware environment is PC with Windows 8.1 (x64) on Intel(R) Core(T) i7-4500 (CPU@1.80 GHz, 2.39 GHz, 4 GRAM); the algorithms are implemented in MATLAB (R2011b).

Table 2

Algorithm parameter setting and abbreviations of the algorithms used in evaluation.
CE-logisticChaotic evolution with logistic map (random initialization within (0, 1], μ = 4).
CE-tentChaotic evolution with tent map (random initialization within (0, 1], μ = 2).
CE-GaussChaotic evolution with Gaussian map (random initialization within (0, 1], α = 6.2, β = −0.5).
CE-Hénon-randChaotic evolution with Hénon map (random initialization within (0, 1], a = 1.4, b = 0.3).
CE-Hénon-attrac.Chaotic evolution with Hénon map (initialization with attractors explained in Figure 2a = 1.4, b= 0.3).
CE crossover rate1

DE/best/1/binDE with the best individual as base vector.
DE/rand/1/binDE with random individual as base vector.
DE scale factor F1
DE crossover rate1
We apply Wilcoxon sign-ranked test and Friedman test on the fitness value at 1000th generation and make two groups with and without DE algorithms to rank the algorithms. We use Bonferroni-Dunn's test to check the significance of algorithm rank in both groups. Tables Tables33 and and44 are the fitness mean value of ALL algorithms at 1000th generation for 10D and 30D benchmark functions, respectively.

Table 3

Mean fitness values of F1–F25 with 10D. The fitness values in bold and italic font are the best and worst optimization results among the five chaotic evolution algorithms, respectively. The (†) and (‡) marks mean that they are significantly better than or as the same as DE/best/1/bin and DE/rand/1/bin, respectively, by Wilcoxon sign-ranked test (P < 0.05).

Table 4

Mean fitness values of F1–F25 with 30D. The explanations of special marks are as the same as in Table 3.
F11124.2699129.963125.7166†‡130.6959 123.5876†‡130.007124.5107†‡
F14−286.7−286.454−286.813†‡286.369 −286.822†‡−286.57†‡−286.962†‡

3.2. Chaotic Evolution Optimization Performance

One of the objectives in this paper is to investigate the optimization performance by using different chaotic systems in CE algorithm framework. Tables Tables33 and and44 show the mean of fitness value at the 1000th generation of each algorithm for 10D and 30D benchmark functions. The fitness values with bold font and italic font indicate the best and the worst fitness values among five proposed CE algorithms. From these two tables, we can conclude that CE with tent map obtains the worst fitness value for most of 10D and 30D benchmark functions. CE with Gaussian map and Hénon map using attractor initialization obtains the best results in 10D and 30D benchmark functions. It presents the fact that CE algorithm with tent map is less useful for most of benchmark tasks practically.
We apply Wilcoxon sign-ranked test (P < 0.05) on results with the best and the worst fitness values; most of the results indicate that there is a significant difference between all pairs. It addresses the fact that the optimization performance of CE is influenced significantly by the chaotic system.
Figure 2 shows the output ranges of four bifurcation diagrams of chaotic system used in our proposed CE algorithms. For further investigating the output distribution of each chaotic system, we calculate their output distribution in equal intervals and their percentages in Table 5.

Table 5

System output total number and its percentage in each interval of logistic map, tent map, Gaussian map, and Hénon map with attractor initiation after 105 iterations. The output of Hénon map with random initiation is out of the interval (0,1].
There are some relationships between output distribution characteristic of chaotic system and optimization performance of CE. In logistic map, most of the system outputs cover the intervals of (0,0.1] and (0.9,1], whose percentages are up to 20.55% and 20.52%, respectively. When making a mutation vector from a target vector, the mutation vector will locate in the position near the target vector with adding the length of (0,0.1]∗target and far from it with adding that of (0.9,1]∗target. It presents exploitation and exploration functions of CE algorithm with the logistic map. Most of the output values locate in the interval (0,0.1] in tent map, which indicates that the exploitation capability of CE with tent map is better than the others. However, its evolution speed is slow due to lack of exploration function. This is a primary reason why CE with the tent map has the worst optimization results in most of benchmark tasks. It is a disadvantage of CE-tent algorithm. The outputs of Gaussian map and Hénon map seem averagely to locate in the intervals among (0,0.5] and (0,1], respectively. These distributions ensure the exploitation and exploration functions of CE with Gaussian map and Hénon map. So they show the better optimization performance among the five CE algorithms averagely.

3.3. Comparison with Differential Evolution

We select two DE algorithms (DE/best/1/bin and DE/rand/1/bin) as two competitors to make a comparative evaluation with our proposed five chaotic evolution algorithms. The † and ‡ marks in Tables Tables33 and and44 show that our proposed CE algorithms have significantly better or equal performance to the evaluation performances of DE/best/1/bin and DE/rand/1/bin from the Wilcoxon sign-ranked tests (P < 0.05), respectively. By comparing the winner number of CE algorithms in Tables Tables33 and and4,4, CE algorithms, which are applied to higher dimensional benchmark functions (30D), can obtain better optimization performance than that applied to lower dimensional benchmark functions (10D). Particularly for the benchmark tasks, F11, F13, F14, F18, F19, F20, and F25, whose fitness landscapes are more complex, our proposed algorithms can obtain significantly better optimization performance.

3.4. Algorithm Ranking

We apply Friedman test on our proposed five CE algorithms and two DE algorithms to make an algorithm rank. Table 6 is the rank results of seven competitive algorithms. We can observe that DE/best/1/bin is the winner algorithm for both 10D and 30D benchmark functions averagely. However, for the F10–F14, F18–F20, its ranks become down because optimization results of our proposed algorithms are better than those in these benchmark tasks. Proposed CE algorithms have powerful optimization capability in the benchmark tasks with more complex fitness landscape from Table 6, especially for the higher dimensional tasks (30D). From evaluation metric of the average rank, the proposed CE algorithms have almost the same rank for some pairs, for example, CE-logistic and CE- Hénon-rand and CE-Gauss and CE-Hénon-attrac. in the 10D group. The same observations can be found in the 30D group as well. Table 7 is the algorithm rank only among five CE algorithms. CE-Gauss and CE-CE-Hénon-attrac. are the winner algorithm from the metric of average rank. The rank scores among five algorithms are not different so much. We suppose that the comparison within five CE algorithms and the comparison within CE and DE (seven algorithms) may not present significant difference when they are applied to a variety of benchmark tasks, that is, in a large sample condition.

Table 6

Algorithms' rank with DE by Friedman test for F1–F25 of 10D and 30D, respectively. The abbreviation meanings are in Table 2.
10-dimensional function

30-dimensional function

Table 7

Algorithms' rank without DE by Friedman test for F1–F25 of 10D and 30D, respectively. The abbreviation meanings are in Table 2.
10-dimensional function

30-dimensional function
We apply Bonferroni-Dunn's tests on the results of Friedman test to evaluate our hypothesis whether these algorithms have a significant difference. The tests are applied on a group with DE to compare CE and DE and on a group without DE to compare the CE algorithms with different chaotic systems. Both tests are for the 10D and 30D benchmark tasks. The evaluation metrics of critical difference (CD) are calculated with (8), in which k is the number of algorithms and N is the number of benchmark functions:
In our evaluation, k = 7 and k = 5 are for the groups with and without DE and N = 25 for both groups. Parameter q is critical value for nonparametric multiple-comparison testing with a control []; we use qα=0.01,k=7 = 3.144 and q α=0.05,k=7 = 2.639 and q α=0.01,k=5 = 3.024 and q α=0.05,k=5 = 2.498 in our calculations of CD. The results are CDqα=0.01,k=7 = 1.92 and CDqα=0.05,k=7 = 1.61 and CDqα=0.01,k=5 = 1.35 and CDqα=0.05,k=5 = 1.11. By comparing with the average values of mean ranking, there are not any CD values excluding average values in each group (taking the algorithm with the less rank value as a control algorithm). These results indicate that (1) CE algorithms have the same optimization capabilities comparing with the DE algorithms, and (2) there is not any significant difference among CE algorithms with different chaotic systems setting, when CE is applied to a variety of benchmark tasks (in the viewpoint of large sample condition).

4. Interactive Chaotic Evolution Optimization Evaluation Analysis and Discussion

4.1. Experimental Settings and Results

We propose using CE algorithm framework to implement a new IEC algorithm, interactive chaotic evolution (ICE). It is one of originalities and contributions in this paper. We use a Gaussian mixture model (equation (9)) as a pseudouser to evaluate ICE algorithm. Dimension setting of the Gaussian mixture model is 3, 5, 7, 10, 13, 15, 17, and 20. The population size of the algorithms is 20 and we evaluate them with 20 generations to simulate the characteristic of IEC algorithms, that is, with less population size and less generation. Other parameter settings are as well in Section 3; we use interactive version of DE, that is, IDE, to compare it with the new proposed ICE. Table 8 is the mean value of all the algorithms at 20th generation; we apply Wilcoxon sign-ranked test to evaluate the significance of results. Figure 3 shows convergent curves of 5D, 10D, 15D, and 20D Gaussian mixture models:
σ=1.52121.52121.52121.52121.52121.52121.52121.52121.52121.5212,μ=102.521.5221231.512.513.53102.521.5221231.512.513.53102.521.5221,    ai=(3.1,3.4,4.1,3.0)T.
Interactive chaotic evolution convergent curves of 5D, 10D, 15D, and 20D Gaussian mixture model. All the ICE algorithms present fast convergent speed, especially in 10D and 20D tasks. IDE/best can obtain better final results than ICE, but it needs more fitness evaluation (i.e., more human subjective evaluation in IEC application) to find the best base vector. From the metric of fitness evaluation time, ICE is significantly better than IDE/best when these two algorithms call the same fitness function time.

Table 8

Means of Gaussian mixture models with 3D, 5D, 7D, 10D, 13D, 15D, 17D, and 20 D. The abbreviation meanings are in Table 2. The (†) and (‡) marks mean that the proposed algorithms are significantly better than or as the same as IDE/best/1/bin and IDE/rand/1/bin, respectively, by Wilcoxon sign-ranked test (P < 0.05).
3D−5.32−5.05− 4.81− 4.96†‡− 5.36†‡− 4.86− 5.08
5D−2.47−2.23− 2.39†‡− 2.52†‡− 2.47†‡− 2.47†‡− 2.46†‡
7D−1.50−1.00− 1.17− 1.13− 1.36†‡− 1.25†‡− 1.31†‡
10D−0.34−0.17− 0.55− 0.56− 0.46− 0.48− 0.42
13D−5.20−5.17− 4.73− 4.98− 5.32†‡− 4.81− 5.09
15D−2.59−2.13− 2.49†‡− 2.41− 2.48†‡− 2.43†‡− 2.43†‡
17D−1.32−0.87− 1.23− 1.24†‡− 1.30†‡− 1.28†‡− 1.29†‡
20D−0.35−0.22− 0.48†‡− 0.46†‡− 0.48†‡− 0.38†‡− 0.52†‡

4.2. Interactive Chaotic Evolution and Its Paired Comparison Mechanism

We analyse the optimization results of CE algorithms at the 1000th generation in Section 3. From the evaluation results and statistical tests, our proposed CE algorithms have better optimization performance in the initial 10 or 20 generations than that of DE algorithms in some benchmark tasks. This feature of CE algorithm can benefit the IEC [], so ICE algorithm should be a powerful algorithm to the IEC application.
One of the characteristics in IEC is that it is required to run with less generation and less population size to solve the user fatigue problem. IEC user compares each individual with others kept in their memory and the mental load and fatigue increase. Reference [] pointed out that human cannot process more than five to nine different items simultaneously. The population sizes of many IEC applications frequently exceed this memory limitation, and displaying more than five to nine sounds or movies, that is, time series object, to an IEC user, is not practical. Paired and multiple comparison-based IEC solves this problem by replacing the comparison of all individuals with paired or multiple comparisons []. It is therefore expected to reduce IEC user fatigue.
In the running process of CE algorithm framework (Section 2.1), there are paired comparison mechanisms in its principle when surviving the target vector and the chaotic vector into the next generation. If we apply the ICE algorithm for a concrete IEC application, it is expected that the optimization performance of ICE may be better than that of IDE from the initial optimization results from Section 3Table 8 sketches that ICE algorithms are significantly better than or are as the same as IDE/best/1/bin and IDE/rand/1/bin. In the viewpoint of fitness evaluation number, ICE algorithms are as the same as IDE/rand/1/bin but less than IDE/best/1/bin, because human user must compare all individuals together to select the best individual as the base vector. ICE presents better optimization performance than that of IDE/best/1/bin. That is, it can reduce human evaluation time and obtain optimization results better or at least as the same as IDE/best/1/bin algorithms, especially in initial generation shown in Figure 3.

4.3. Fusion of Chaotic Evolution and Differential Evolution

Evaluation results indicate that the convergent speeds of CE algorithms become down in some benchmark functions, especially in 15D tasks (Figure 3). However, convergence speeds of DE algorithms seem to be with the same tendency in Figure 3. If we fuse CE and DE together to make a hybrid algorithm optimization framework, the performance of hybrid algorithm should expectedly be better than any of the single algorithms. For example, when the convergence speeds of DE become slow, we can apply the CE algorithm with multiple chaotic systems to increase its population diversity and vice versa. Fusion algorithm can be implemented in dimension level, individual level, and generation level. This is a promising topic for the further investigation.
There are multiple implementations of the CE algorithm framework. We initially have investigated their optimization performance and output distribution of chaotic systems. Another opportunity for enhancing optimization performance of CE is to fuse multiple chaotic systems in one CE algorithm. It is as well a promising research topic for further study. There are three methods to implement this algorithm framework. First is to apply one chaotic system for a certain generation and change another for the following generations by observing the algorithm convergent speed or other evaluation metrics. Second is to fuse CE with multiple chaotic systems in individual level; that is, some of individuals are searching by the law of one chaotic system and some of the others by that of other chaotic systems. Third is to apply different chaotic systems on different dimensions of one individual. The landscape or search situation is different from all dimensions, and this must be matched by different dimensional searches with different chaotic systems. We can design a CE algorithm with multiple chaotic systems by obtaining the fitness landscape information in the whole or the particle dimensions. Some methods of analysing and approximating the fitness landscape information can be found in []. This is a research subject in our future work.

4.4. Algorithmic Notation of Chaotic Evolution

We develop an algorithmic notation system for a better explanation and further development of CE algorithms. The actual search function of chaotic algorithms is implemented by a chaotic system, in which there are some parameters. This is one element in chaotic evolution. Another parameter of chaotic evolution is the crossover rate.
We abbreviate chaotic evolution as CE and use the notation format CE/x/y/z to make a note of a certain chaotic evolution algorithm, where xy, and z present a chaotic system, the parameters of chaotic system, and a crossover rate, respectively. For example, the CE algorithm with Gaussian map in this paper can be a notation as “CE/Gaussian/(α = 6.2, β = −0.5, random initialization)/1.”

5. Conclusion and Future Works

In this paper, we develop a chaotic optimization algorithm that is theoretically supported by the fundamental of chaos theory. We introduce four chaotic systems in a well-designed CE algorithm framework to implement several CE algorithms, that is, CE-logistic, CE-tent, CE-Gauss, CE-Hénon-rand, and CE-Hénon-attrac. We analyse the optimization performances of these developed algorithms. A comparative evaluation is conducted by applying the Wilcoxon sign-ranked test and the Friedman test with two DE algorithms. We propose a new IEC algorithm, that is, ICE that has a paired comparison mechanism in its search scheme. A series of topics on optimization performances of chaotic evolution algorithms, comparison with DE algorithms, algorithms rank, interactive chaotic evolution, and fusion of these algorithms for enhancing performance are analysed and discussed.
In this paper, we do not pursue obtaining the results of the best winner algorithm but analyse and discuss the algorithm optimization mechanism of CE and the philosophy behind it. In the modern scientific world, there are two primary philosophies and methodologies to describe and study nature world from the determinism and probability viewpoint. In the optimization field, there are corresponding deterministic and stochastic optimization algorithms that are supported by these two methodologies. EC is one of stochastic optimization algorithms. However, after the discoveries of chaotic phenomena and systems, chaos becomes the third methodology to study the nature world. Chaotic optimization algorithm should therefore be researched and developed in optimization field. Chaotic evolution is one of the implementations, although it has many disadvantages in its search scheme, such as searching without considering fitness landscape, exploration, and exploitation depending on chaotic system rather than adaptive mechanism. In the theoretical analysis of CE, we will analyse concrete CE algorithm with Markov chain [] and other mathematical models. They are interesting research topics on evaluating CE performance by a variety of benchmark functions and comparing it with other metaheuristics algorithms []. We will further investigate these topics in our future work and hopefully discover new knowledge behind CE algorithm. It should benefit both chaos theory and evolutionary optimization hopefully.

Conflict of Interests

The author declares that there is no conflict of interests regarding the publication of this paper.


1. Simon P., de Laplace M., Truscott F. W., Emory F. L. A Philosophical Essay on Probabilities. Vol. 166. New York, NY, USA: Dover; 1951. []
2. Pei Y., Takagi H. A survey on accelerating evolutionary computation approaches. Proceedings of the International Conference of Soft Computing and Pattern Recognition (SoCPaR '11); October 2011; pp. 201–206. [CrossRef[]
3. Diacu F., Holmes P. Celestial Encounters: The Origins of Chaos and Stability. Princeton, NJ, USA: Princeton University Press; 1996. []
4. Poincare H. Les méthodes nouvelles de la mécanique céleste: Méthodes de MM. Newcomb, Glydén, Lindstedt et Bohlin. Volume 2. Gauthier-Villars et fils; 1893. []
5. Coelho L. D. S., Bora T. C., Lebensztajn L. A chaotic approach of differential evolution optimization applied to loudspeaker design problem. IEEE Transactions on Magnetics2012;48(2):751–754. doi: 10.1109/TMAG.2011.2174204. [CrossRef[]
6. Pei Y. Chaotic evolution: fusion of chaotic ergodicity and evolutionary iteration for optimization. Natural Computing2014;13(1):79–96. doi: 10.1007/s11047-013-9409-2. [CrossRef[]
7. Wang G.-G., Guo L., Gandomi A. H., Hao G.-S., Wang H. Chaotic krill herd algorithm. Information Sciences2014;274:17–34. doi: 10.1016/j.ins.2014.02.123. [CrossRef[]
8. Wang G.-G., Gandomi A. H., Alavi A. H. A chaotic particle-swarm krill herd algorithm for global numerical optimization. Kybernetes2013;42(6):962–978. doi: 10.1108/K-11-2012-0108. [CrossRef[]
9. Wang G., Guo L., Wang H., Duan H., Liu L., Li J. Incorporating mutation scheme into krill herd algorithm for global numerical optimization. Neural Computing and Applications2014;24(3-4):853–871. doi: 10.1007/s00521-012-1304-8. [CrossRef[]
10. Smith L. Chaos: A Very Short Introduction. Oxford, UK: Oxford University Press; 2007.[]
11. Takagi H. Interactive evolutionary computation: fusion of the capabilities of EC optimization and human evaluation. Proceedings of the IEEE2001;89(9):1275–1296. doi: 10.1109/5.949485. [CrossRef[]
12. Takagi H., Pallez D. Paired comparison-based interactive differential evolution. Proceedings of the World Congress on Nature & Biologically Inspired Computing (NaBIC ’09); December 2009; Coimbatore, India. pp. 475–480. [CrossRef[]
13. Pei Y., Takagi H. Triple and quadruple comparison-based interactive differential evolution and differential evolution. Proceedings of the 12th Workshop on Foundations of Genetic Algorithms; 2013; ACM; pp. 173–182. []
14. May R. M. Simple mathematical models with very complicated dynamics. Nature1976;261(5560):459–467. doi: 10.1038/261459a0. [PubMed] [CrossRef[]
15. Suganthan P. N., Hansen N., Liang J. J., et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. KanGAL Report2005;(2005005)
16. Storn R., Price K. Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization1997;11(4):341–359. doi: 10.1023/A:1008202821328.[CrossRef[]
17. Zar J. H. Biostatistical Analysis. Delhi, India: Pearson Education; 2007. []
18. Miller G. A. The magical number seven, plus or minus two: some limits on our capacity for processing information. Psychological Review1956;63(2):81–97. doi: 10.1037/h0043158. [PubMed] [CrossRef[]
19. Pei Y., Takagi H. Fourier analysis of the fitness landscape for evolutionary search acceleration. Proceedings of the IEEE Congress on Evolutionary Computation (CEC '12); June 2012; pp. 1–7. [CrossRef[]
20. Pei Y., Takagi H. Accelerating IEC and EC searches with elite obtained by dimensionality reduction in regression spaces. Evolutionary Intelligence2013;6(1):27–40. doi: 10.1007/s12065-013-0088-9.[CrossRef[]
21. Wang G., Guo L. A novel hybrid bat algorithm with harmony search for global numerical optimization. Journal of Applied Mathematics2013;2013:21. doi: 10.1155/2013/696491.696491 [CrossRef[]

Articles from The Scientific World Journal are provided here courtesy of Hindawi Limited

No comments:

Post a Comment