Keywords

1 Introduction

The idea of natural selection and biological evolution propounded by Charles Darwin resulted in the concept of Evolutionary algorithm (EA). For computing a particular problem, an environment is created where in the potential solution can evolve. Environment is framed by the guidelines of the problem and fortifies the evolution of good solution. EA is a good technique for searching the optimal solutions. EA uses various concepts of reproduction, selection, mutation and recombination. Various evolutionary algorithms have been developed in due course of time. Initially researchers used the genetic algorithm technique for solving complex problems. In 1997, Storn and Price proposed the Differential Evolution (DE) technique. Like various other evolutionary algorithms, DE is also a population based stochastic method. DE is one of the best evolutionary algorithm for solving real valued test functions.

Numerous attempts are being done to improve the performance of DE for several specific applications. The efficiency and performance of DE greatly depends on the trial vector generation strategy and the control parameters used. Several variants of the existing technique are developed by changing these trial vector strategy and control parameters. The three control parameters in DE algorithm are: mutation scale factor F, crossover constant and the population size.

In this paper, a variant of the mutation strategy named RDE is proposed by using three different mutation scale factors. One of the scale factor is a constant value and the other two scale factors are variable values between the range (0,1) where one factor is the complement of the other value. This strategy showed better efficiency compared to the existing mutation strategies.

2 Background Study

Das et al. [6] proposed two new variants of DE, DE with random scale factor (DERSF) and DE with time varying scale factor(DETVSF). The new method showed statistically improved results. Brest et al. [5] presented a new version of DE with self-adaptive control parameter settings showing better efficiency in comparison to the existing techniques. Grosan et al. [9] gave the need for hybridizing evolutionary algorithms and proposed the possibilities on hybridization. Also a review on the existing hybrid techniques were also stated. Das et al. [8] gave a detailed study on particle swarm optimization (PSO) and DE. Subsequently, a mutual synergy of PSO and DE were discussed and results computed. Ali et al. [1] proposed the technique of using nonlinear simplex method with pseudo number to generate the initial population. The method was named as NSDE and results were tabulated and compared. Xin et al. [10] developed a novel adaptive hybrid of PSO and DE (HPSO-DE). This technique maintains the diversity of population.

Gong et al. [3] presented a set of improved DE that try to adaptively choose a suitable strategy for a problem at hand. In this paper, different parameter adaption methods of DE are used for different strategies. The efficiency of the technique was tested and verified. Islam et al. [2] proposed a new mutation strategy using fitness induced parent selection for binomial crossover of DE and a scheme of adapting two of the control parameters to achieve better results. Gong et al. [4] proposed ranking based mutation operator for DE algorithm. Here the selection of the parent in mutation operation is selected according to the ranking in the current population. The proposed operators were integrated into advanced DE variants to verify its effects. The proposed mutation operators enhanced the performance of DE algorithm.

Yu et al. [14] proposed an adaptive DE (ADE) algorithm with new mutation strategy and a two level adaptive parameter control scheme. This technique has a good balance between population diversity and fast convergence. Tang et al. [11] developed a novel variant of DE with an individual dependent mechanism that uses an individual dependent parameter (IDP) and an individual dependent mutation (IDM) strategy. Tabulated results show greater performance to classical technique. Qiu et al. [12] developed the simultaneous use of individuals across generations from objective based perspective. Results obtained show the statistical superiority of the proposed technique to several evolutionary algorithms. Ramadas et al. [9] proposed an algorithm ssFPA/DE where Differential evolution approach was combined with the concept of Flower Pollination Algorithm. The proposed technique gave better results in comparison to tradition DE approach. Ramadas et al. [10] also proposed an new mutation strategy named ReDE – a revised mutation strategy. This strategy used two control parameters and two types of population. The efficiency of the new technique was better than the traditional approach.

3 Differential Evolution

In a search space of n-dimensions of likely solutions, a specified number of vectors are arbitrarily identified. In each iteration or generation, a new vector will be formed by combining two or more vectors which are arbitrarily identified from the population. The outcome vector is with predetermined target vector. A trial vector is created in a process called recombination. If it produce a better value of objective function, then the trial vectors are accepted in next generation. Until some stopping criteria is satisfied, the mutation, recombination and selection are continued. DE use the population of NP candidate solutions denoted as \( X_{i,G} \) where \( i = 1,2 \ldots \) NP where index \( i \) denote population and \( G \) represents generation of population. Differential Evolution algorithm depends on the three operations mainly mutation, selection and reproduction.

Mutation: This operator causes DE to be distinct from other Evolutionary algorithms. It computes the weighted difference between the vectors in population. Mutation starts by arbitrarily choosing three individuals from the population. This operation extends the workspace. For a given parameter \( X_{i,G} \) we are arbitrarily selecting 3 vectors \( X_{r1,G} ,X_{r2,G} \) and \( X_{r3,G} \) such that \( r_{1} ,r_{2} ,r_{3} \) are distinct. Then the donor vector \( V_{i,G} \) is computed as:

$$ V_{i,G} = X_{r1,G} + F \times (X_{r2,G} - X_{r3,G} ) $$
(1)

Here \( F \) is the mutation factor which is a constant from [0,1]. The above strategy is denoted as DE/rand/1. Mutation function demarcates one DE scheme from another. The often used DE codes are given below:

$$ {\text{DE}}/{\text{rand}}/2\quad V_{i,G} = X_{r1,G} + F \times (X_{r2,G} - X_{r3,G} ) + F \times (X_{r4,G} - X_{r5,G} ) $$
(2)
$$ {\text{DE}}/{\text{best}}/1\quad V_{i,G} = X_{best,G} + F \times (X_{r1,G} - X_{r2,G} ) $$
(3)
$$ {\text{DE}}/{\text{best}}/2\quad V_{i,G} = X_{best,G} + F \times (X_{r1,G} - X_{r2,G} ) + F \times (X_{r3,G} - X_{r4,G} ) $$
(4)
$$ {\text{DE}}/{\text{rand}} - {\text{to}} - {\text{best}}/1\quad V_{i,G} = X_{r1,G} + F \times (X_{best,G} - X_{r2,G} ) + F \times (X_{r3,G} - X_{r4,G} ) $$
(5)

where, \( i = 1 \ldots NP \), \( r_{1} ,r_{2} ,r_{3} \in \{ 1, \ldots ,NP\} \) are randomly selected and satisfy: \( r_{1} \ne r_{2} \ne r_{3} \ne i \), \( F \in [0,1] \), F is the control parameter proposed by Storn and Price.

Crossover: This process also termed as recombination, includes successful solutions into the population. The trial vector \( U_{i,G} \) is created for target vector \( X_{i,G} \) through binomial crossover. Components of donor vector enter trial vector with probability \( C_{r} \in [0,1] \). \( C_{r} \) is the crossover probability which is selected along with population size \( NP \ge 4 \).

$$ U_{j,i,G + 1} = \left\{ {\begin{array}{*{20}l} {V_{j,i,G + 1} \;} \hfill & {if\,rand_{i,j} [0,1] \le C_{r} or\,if\,j = I_{rand} } \hfill \\ {X_{j,i,G + 1} \;} \hfill & {if\,rand_{i,j} [0,1] > C_{r} or\,if\,j \ne I_{rand} } \hfill \\ \end{array} } \right. $$
(6)

Here \( rand_{i,j} \approx \cup [0,1] \) and \( I_{rand} \) is random integer from 1,2…N.

Selection: This operation differs from the selection operation of other evolutionary algorithms. Here the population for next generation is chosen from vectors in current population and its subsequent trial vectors. The target vector \( X_{i,G} \) is matched with the trial vector \( V_{i,G} \) and the least value of function is taken into next generation.

$$ X_{i,G + 1} \left\{ {\begin{array}{*{20}l} {U_{i,G + 1} \;} \hfill & {if\,f(U_{i,G + 1} ) \le f(X_{i,G} )\;where\,i = 1,2, \ldots N} \hfill \\ {X_{i,G} \;} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$
(7)

4 Reconstructed Mutation Strategy

In RDE, we have used three control parameters. By involving the best solution vector, this strategy coincides faster as compared to the traditional strategies having random vectors only. The variables \( X_{r1,G} ,\; X_{r2,G} ,\;X_{r3,G} \) are chosen at random. The parameter F known as amplifying parameter takes a constant value. The new parameter N1 takes a varying value which lies between (0,1) and N2 takes the complement of N1. As we are taking three different control parameters, the value of donor vector is improved greatly and hence the efficiency of DE algorithm is enhanced immensely. The proposed strategy is given as:

$$ X^{\prime } = X_{r1,G} + F*\left( {N1*\left( {X_{best,G} - X_{r2,G} } \right) - N2*\left( {X_{best,G} - X_{r3,G} } \right)} \right) $$
(8)

5 Experimental Settings

The above stated variant was implemented using MATLABr2008b on i7 core processor, 64 bit operating system with 12 GB RAM. A comparative result was obtained with the traditional mutation strategies. Here, we have taken 5 traditional mutation strategy (DE/rand/, DE/rand/2, DE/best/1, DE/best/2, DE/rand-to-best/1) and the proposed technique RDE and values obtained were compared. The traditional mutation strategies were replaced with the proposed mutation strategy and RDE was composed. In the experiment conducted, mutation constant F is given the value 0.6 and the crossover probability \( C_{r} \) is given the value 0.8. We have taken fifteen different functions and calculated the results by fixing the value to reach and number of iterations. We have also tested the strategy by fixing the dimension as 25. One of the results obtained and their corresponding graphs are given below:

Based on Best Value after 50 runs (vtr = 1.e − 015):

Based on NFE on fixed VTR for size = 25 (VTR = 1.e − 015) (Table 2):

Based on elapsed time of CPU in seconds for size = 25 (VTR = 1.e − 015) (Table 3):

A comparative analysis was performed and study done on each of the technique. By setting the dimension as 25 and value-to-reach (VTR) as e − 015, the best value, number of function evaluation (NFE) and the CPU time of different function strategies were calculated. It was noted that the proposed hybrid algorithm gave the best value for most of the standard functions.

6 Graphical Results

The above tabulated values were represented in a graphical form. The graphs show performance curve of six different function strategies. The x-axis represents the number of function evaluation for each mutation strategy and y-axis represents the objective function. The graph is plotted for the various values at each iteration for fixed VTR value of e − 015 and dimension size of 25 (Fig. 1).

Fig. 1.
figure 1

Graphical representation of Michelawicz function

Full size image

A comparative study was done based on above graphs. The study showed that the revised mutation strategy gave better results compared to the existing mutation strategy for various functions (Fig. 2).

Fig. 2.
figure 2

Graphical representation for Schwefel function

Full size image

7 Statistical Test

Friedman test was applied and the results obtained were tabulated on the values obtained from Table 1. Table 4 represents the values obtained from the test. N represents the population size and df represents the degree of freedom associated with the source. Asymptotic significance gives the p value of the Friedman test and Chi sq gives the Friedman chi square statistics value. Table 5 depicts the rank position of the various mutation strategies used based on best value, NFE and CPU time (Fig. 3).

Table 1. Best value after 50 runs for different functions
Full size table
Table 2. Based on NFE on fixed VTR for different functions for size = 25 (VTR = 1.e − 15)
Full size table
Table 3. Based on elapsed time of CPU in seconds for different functions for size = 25 (VTR = 1.e − 015)
Full size table
Table 4. Test statistics using Friedman’s test
Full size table
Table 5. Ranks of the different strategies
Full size table
Fig. 3.
figure 3

Bonferroni Dunn chart for best value

Full size image

The above tables show that the new mutation strategy has significant performance in comparison to the existing mutation strategies. Based on the ranks obtained, a graphical representation of the results is shown below. The x axis of the graph represents the six different mutation strategies used and the y axis shows the ranks obtained for each strategy based on different parameters like best value obtained and NFE value obtained (Fig. 4).

Fig. 4.
figure 4

Bonferroni Dunn bar chart for NFE

Full size image

8 Conclusion

In this paper, we have given a simple, efficient mutation strategy. RDE strategy was compared against the existing mutation strategy. The comparative study showed that the proposed strategy gave much better for most of the functions evaluated. A detailed study was done and graphs were plotted. Further the work can be extended to the field of clustering for verifying the performance of the new mutation strategy in that area.