Keywords

1 Introduction

This research deals with the hybridization of the two softcomputing fields, which are chaos theory and evolutionary computation. This paper is aimed at investigating the novel adaptive control scheme for multi-chaos driven Differential Evolution algorithm (DE) [1]. Although a number of DE variants have been recently developed, the focus of this paper is the further development of ChaosDE concept, which is based on the embedding of chaotic systems in the form of Chaos Pseudo Random Number Generators (CPRNG) into the DE.

A chaotic approach generally uses the chaotic map in the place of a pseudo random number generator [2]. This causes the heuristic to map unique regions, since the chaotic map iterates to new regions. The task is then to select a very good chaotic map as the pseudo random number generator.

The focus of our research is the direct embedding of chaotic dynamics in the form of CPRNG for evolutionary algorithms. The initial concept of embedding chaotic dynamics into the evolutionary algorithms is given in [3]. Later, the initial study [4] was focused on the simple embedding of chaotic systems in the form of chaos pseudo random number generator (CPRNG) for DE and Self Organizing Migration Algorithm (SOMA) [5] in the task of optimal PID tuning. Also the PSO (Particle Swarm Optimization) algorithm with elements of chaos was introduced as CPSO [6]. The concept of ChaosDE proved itself to be a powerful heuristic also in combinatorial problems domain [7]. At the same time the chaos embedded PSO with inertia weigh strategy was closely investigated [8], followed by the introduction of a PSO strategy driven alternately by two chaotic systems [9].

And based on the promising experimental results with PSO algorithm driven adaptively by two different chaotic systems, the idea was to extend this approach also on DE algorithm.

Firstly, the motivation for this research is proposed. The next section is focused on the description of evolutionary algorithm DE. The core of methodology of your presented research, which is the concept of adaptive chaos driven DE is explained in section four, followed by the experiment description. Results and conclusion follow afterwards.

2 Related Work and Motivation

This research is an extension and continuation of the previous successful initial experiments with multi-chaos driven PSO and DE algorithms [10, 11]. Recent research [12–14] shows that chaos driven heuristics applied to many interdisciplinary problems have better overall performance than canonical (original) versions of such heuristics. Furthermore there exist many possible approaches for hybridization, injection and control of chaotic complex dynamics into the heuristics.

In this paper the novel adaptive control concept for DE/rand/1/bin strategy driven alternately by two chaotic maps (systems) is introduced. From the aforementioned previous research it follows, that very promising experimental results were obtained through the utilization of different chaotic dynamics. And at the same time it was clear that different chaotic systems have different effects on the performance of the algorithm. The idea was then to connect these two different influences to the performance of DE into the one multi-chaotic concept. The previous research was aimed at the determining of the switching time (certain number of generations/iterations) between different chaotic systems. Such a “manual” approach proved to be successful, but also many open issues have arisen (i.e. when to start the switching, how many times, etc.). The novelty of the proposed adaptive approach is that, the chaotic pseudorandom number generators are switched over automatically without prior knowledge of the optimization problem and without any manual setting of the “switching point”.

3 Differential Evolution

DE is a population-based optimization method that works on real-number-coded individuals [1, 15]. DE is quite robust, fast, and effective, with global optimization ability. A schematic of the canonical DE strategy is given in Fig. 1. There are essentially five sections to the code depicted in Fig. 1.

Fig. 1.
figure 1

DE schematic

Full size image

Section 1 describes the input to the DE. D is the size of the problem, G max is the maximum number of generations, NP is the total number of solutions, F is the scaling factor, CR is the factor for crossover, x (lo) and x (hi) represents the initial bounds of the solutions. F and CR together make the internal tuning parameters for the heuristic.

Section 2 in Fig. 1 outlines the initialization of the heuristic, i.e. creation of the initial population. Each solution x i,j,G=0 is created randomly between the two bounds x (lo) and x (hi). The parameter j represents the index to the values within the solution and parameter i indexes the solutions within the population. So, to illustrate, x 4,2,0 represents the fourth value of the second solution at the initial generation.

After initialization, the population is subjected to repeated iterations in Sect. 3.

Section 4 describes the conversion routines of DE. Initially, three random numbers r 1 , r 2 , r 3 are selected, unique to each other and to the current indexed solution i in the population in 4.1. Henceforth, a new index j rand is selected in the solution. j rand points to the value being modified in the solution as given in 4.2. In 4.3, two solutions, x j , r1 , G and x j , r2,G are selected through the index r 1 and r 2 and their values subtracted. This value is then multiplied by F, the predefined scaling factor. This is added to the value indexed by r 3 .

However, this solution is not arbitrarily accepted in the solution. A new random number is generated, and if this random number is less than the value of CR, then the new value replaces the old value in the current solution. The fitness of the resulting solution, referred to as a perturbed vector u j , i , G , is then compared with the fitness of x j , i , G . If the fitness of u j , i , G is greater than the fitness of x j , i , G , then x j , i , G is replaced with u j , i , G ; otherwise, x j , i , G remains in the population as x j , i , G+1 . Hence the competition is only between the new child solution and its parent solution.

4 The Concept of Adaptive Multi-chaotic DE

The general idea of ChaosDE and CPRNG is to replace the default pseudorandom number generator (PRNG) with the discrete chaotic map. As the discrete chaotic map is a set of equations with a static start position, we created a random start position of the map, in order to have different start position for different experiments (runs of EA’s). This random position is initialized with the default PRNG, as a one-off randomizer. Once the start position of the chaotic map has been obtained, the map generates the next sequence using its current position.

In this research, direct output iterations of the chaotic maps (iteration x or y – see Sect. 5) were used for the generation of real numbers in the process of crossover based on the user defined CR value and for the generation of the integer values used for selection of individuals.

Previous successful initial experiments with multi-chaos driven PSO and DE algorithms [10, 11] have manifested that very promising experimental results were obtained through the utilization of Delayed Logistic, Lozi, Burgers and Tinkerbelt maps. The last two mentioned chaotic maps have unique properties with connection to DE: strong progress towards global extreme, but weak overall statistical results, like average cost function (CF) value and std. dev., and tendency to premature stagnation. While through the utilization of the Lozi and Delayed Logistic map the continuously stable and very satisfactory performance of ChaosDE was achieved. The above described influences around switching point (500 or 1500 generations) are visible from the Fig. 2, which depicts the illustrative example of time evolution of average CF values for all 50 runs of four combinations of Multi-Chaotic DE and canonical DE/rand/1/bin strategies.

Fig. 2.
figure 2

Comparison of the time evolution of avg. CF values for the all 50 runs of Canonical DE, and all four versions of Multi-ChaosDE; shifted Ackley’s original function, D = 30.

Full size image

To maximize the benefit from the influences of different chaotic dynamics a new adaptive control approach was developed. It does not require any prior knowledge of the optimization problem and any manual setting of the one ore more “switching points”. The exact transition point is determined by following simple rule: If the change of global best value between two subsequent generations is less than 0.001 over more than 1 % of total number of generations, the chaotic systems used as the CPRNGs are alternated.

5 Chaotic Maps

This section contains the description of discrete dissipative chaotic maps used as the chaotic pseudo random generators for DE. Following chaotic maps were used: Burgers (1), and Lozi map (2).

The Burgers mapping is a discretization of a pair of coupled differential equations which were used by Burgers [16] to illustrate the relevance of the concept of bifurcation to the study of hydrodynamics flows. The map equations are given in (1) with control parameters a = 0.75 and b = 1.75 as suggested in [17].

$$ \begin{aligned} & X_{n + 1} = aX_{n} - Y_{n}^{2} \\ & Y_{n + 1} = bY_{n} + X_{n} Y_{n} \\ \end{aligned} $$
(1)

The Lozi map is a discrete two-dimensional chaotic map. The map equations are given in (2). The parameters used in this work are: a = 1.7 and b = 0.5 as suggested in [17]. For these values, the system exhibits typical chaotic behavior and with this parameter setting it is used in the most research papers and other literature sources.

$$ \begin{aligned} & X_{n + 1} = 1 - a\left| {X_{n} } \right| + bY_{n} \\ & Y_{n + 1} = X_{n} \\ \end{aligned} $$
(2)

6 Results

IEEE CEC 2013 benchmark set [18] was utilized within this experimental research for the purpose of performance comparison of Multi-Chaotic DE and state of the art adaptive representative jDE.

Experiments were performed in the combined environments of Wolfram Mathematica and C language; jDE therefore used the built-in C language pseudo random number generator Mersenne Twister C representing traditional pseudorandom number generators in comparisons. All experiments used different initialization, i.e. different initial population was generated in each run.

Within this research, one type of experiment was performed. It utilizes the maximum number of generations fixed at 1500 generations, Population size of 75 and dimension dim = 30. This allowed the possibility to analyze the progress of all studied DE variants within a limited number of generations and cost function evaluations.

The parameter settings (see Table 1) for Multi-Chaos DE were obtained based on numerous experiments and simulations. ChaosDE requires lower values of CR and F for almost any CPRNG and benchmark test function. The same settings was used also for the jDE, except values of mutation and crossover control parameters F and CR (see Sect. 3), which are not required, since they are adaptively tuned during the run of the algorithm.

Table 1. Parameter set up for ChaosDE, multi-Chaos DE and jDE
Full size table

To track the influence of adaptive multi-chaotic approach, an experiment encompasses three groups:

  • Two versions of ChaosDE with Lozi map or Burgers map (i.e. single chaos approach – no alternation).

  • Two versions of adaptive Multi-Chaos DE: Initialized with Lozi map or Burgers map.

  • State of the art adaptive representative jDE.

The results of the experiments are shown in Tables 2 and 3. Table 2 contains the final average CF values, whereas Table 3 shows the minimum found CF values representing the best individual solution for all 50 repeated runs of ChaosDE, Multi-Chaos DE and jDE. Finally the Table 4 shows the overall performance comparison for aforementioned three groups of DE versions. Within Tables 2 and 3, the bold values represent the best performance, italic equal. Detailed results analysis is present in the conclusion section.

Table 2. Final average CF values: Performance comparison for ChaosDE, Multi-Chaos DE and jDE on CEC 13 Benchmark Set, dim = 30, max. Generations = 1500
Full size table
Table 3. Best solutions - minimal CF values: Performance comparison for ChaosDE, Multi-Chaos DE and jDE on CEC 13 Benchmark Set, dim = 30, max. Generations = 1500
Full size table
Table 4. Overall statistical performance comparison
Full size table

7 Conclusion

The primary aim of this work is to use and test the hybridization of natural chaotic dynamics with evolutionary algorithm as the multi-chaotic pseudo random number generator. In this paper the novel adaptive concept of DE/rand/1/bin strategy driven alternately by two chaotic maps (systems) is introduced. These two different influences to the performance of DE were connected here into the one adaptive multi-chaotic concept with automatic switching without prior knowledge of the optimization problem and without any manual setting of the “switching point”. Repeated simulations were performed on the IEEE CEC 13 benchmark set. The obtained results were compared with the original predecessor ChaosDE and state of the art adaptive representative jDE. The findings can be summarized as follows:

  • The high sensitivity of the DE to the internal dynamics of the chaotic PRNG is fully manifested.

  • When comparing simple ChaosDE and adaptive Multi-Chaos DE, the both multi-chaotic versions have kept stable performance for both average and minimal observed final CF values. While through the utilization of simple ChaosDE, the aforementioned different influences of two chaotic dynamics have been revealed. Both versions of ChasoDE have outperformed all other studied heuristic in the case of min CF value (i.e. the best individual solution founded). Nevertheless in case of average results, the performance was the worst. This supports the claim, that adaptive multi chaotic approach suppresses the weak spots of particular CPRNGs, which are the weak overall statistical results, like average CF value and std. dev.; and tendency to stagnation; thus that adaptive multi chaotic approach connects such strong progress towards global extreme with stable searching process without premature stagnation issues given by particular CPRNGs.

  • When comparing the adaptive Multi-Chaos DE and adaptive jDE, the performance is comparable in case of final average CF values; whereas in case of min. CF values the chaos driven heuristic has outperformed the adaptive jDE.

  • Based on the previous point, we can assume that in case of differential evolution, the sensitivity to the adaptive changes of internal chaotic dynamics driving the selection of individuals and crossover process may be higher than sensitivity to the adaptive tuning of control parameters. Nevertheless this will be more experimentally investigated in future work and research experiments.

  • Furthermore the direct embedding of chaotic dynamics into the evolutionary/swarm based algorithms is advantageous, since it can be easily implemented into any existing algorithm or strategy. Also there are no major adjustments in the code required (instead of calling function Rand(), one iteration of chaotic system is taken).