Advanced Evolutionary Algorithms in Data Mining
 389 Downloads
Keywords
Evolutionary Algorithm Differential Evolution Memetic Algorithm Differential Evolution Algorithm Artificial Immune SystemDefinition of the Subject
Evolutionary algorithms (EAs) are stochastic populationbased methods inspired by nature. A population consists of several individuals usually encoded as vectors. During an evolutionary process, a population is transformed into a new population. After some such transformations, the algorithm stops and returns a best found individual as solution.
Differential Evolution (DE) is an evolutionary algorithm for global optimization over continuous spaces as well as for optimization over discrete spaces. Nowadays, it is used as a powerful global optimization method within a wide range of research areas.
As a plethora of data are generated in every possible means and data dimensionality increases on a large scale, it is imperative to increase power of methods in data mining, knowledge discovery, as well as in optimization methods that are dealing with highdimensional massive data, uncertainty environments, and dynamic systems.
Introduction
(Das and Suganthan 2011): To tackle complex computational problems, researchers have been looking into nature for years – both as model and as metaphor – for inspiration. Optimization is at the heart of many natural processes like Darwinian evolution itself. Through millions of years, every species had to adapt their physical structures to fit to the environments they were in. A keen observation of the underlying relation between optimization and biological evolution led to the development of an important paradigm of computational intelligence – the evolutionary computing techniques for performing very complex search and optimization.
Researchers and scientists from various disciplines such as bioinformatics, engineering, chemistry, among many others, often have to deal with the classical problem of optimization and/or search.
Evolutionary algorithms are populationbased algorithms and they are suitable for solving continuous optimization problems as well as for discrete optimization. Evolutionary algorithms include Genetic Algorithms (GA), Evolution Strategies (ES), Evolutionary Programming (EP), Genetic Programming (GP), and DE. Evolutionary algorithms are under a wider group of natureinspired algorithms, which include also swarm intelligence algorithms (like particle swarm optimization, ant colony optimization, bat algorithms, etc.) and other algorithms (like artificial immune systems, memetic algorithms, harmony search, etc.).
These algorithms usually have several control parameters that are responsible for tuning/controlling the algorithm itself during the optimization process. Good values of the control parameters might improve an algorithm’s performance.
Objective and Scope of the Article
In this chapter, an overview of DE is presented with the emphasis on a variety of different evolutionary methods available today. The evolutionary algorithms are suitable mechanisms in various domains where an optimization problem can be formulated as a global optimization problem, in which derivatives of the objective function are unavailable, the objective function is multimodal, or it has many local minima. This chapter presents mechanisms that were recently proposed for control parameters and mutation strategies in the DE algorithm. Basic features, advantages, and drawbacks of DE as well as of other evolutionary methods are presented. For the readers not very familiar with the field of evolutionary computation, this article should be a good introduction into the topic, whereas for more experienced readers, it should deepen their knowledge.
Background

Dimensionality – problems may have high dimensions, e.g., big data in data mining (Wu et al. 2014) – in literature also known as “largescale optimization.”

Multimodality – problems that have only one optimum, i.e., unimodal, are easy to solve in many cases, while multimodal problems are more challenging.

Constraints – problems have inequality and equality constraints, which are needed to be satisfied when solving constrained optimization problems. Constraints divide solutions from a whole search space into two groups of feasible and infeasible solutions.

Dynamic environment – if problem changes its characteristics during the time (e.g., optimum point is moving around in the search space during optimization, etc.), an EA needs to follow these dynamic changes.

Others.
Multiobjective EAs applied in the domain of data mining have mainly dealt with feature selection, classification, clustering, and association rule mining. Multiobjective EAs for data mining are presented in Mukhopadhyay et al. 2014a, b.
Basics of Differential Evolution
DE is a floatingpoint encoding evolutionary algorithm for global optimization over continuous spaces (Storn and Price 1997; Price et al. 2005; Feoktistov 2006). It is a population based algorithm with a small number of control parameters.
The DE and GA algorithms belong to the evolutionary algorithms but there are some differences between the DE and GA. GA uses a different order of operators, i.e., the order in the GA algorithm is crossover, mutation, and selection. The another important difference appears in a mutation phase. While GA usually uses mutation in order to introduce very small change(s) of an individual, DE applies much bigger change(s) of an individual during the mutation.
DE has three control parameters: mutation scale factor, F, crossover rate, Cr, and population size, Np. The original DE algorithm (Storn and Price 1995, 1997) keeps all three parameters fixed during the optimization process.
Initialization
Mutation
Before next operation starts, a check if some components of the mutant vector are out of their lower and upper bounds is applied. The components are randomly generated once again until they are out of bounds or they are set on bounds, which are widely used approaches for repairing a mutant vector.
Crossover
Beside the “binomial” crossover, DE has an exponential crossover variant (Price et al. 2005). The first one is used more times in practice.
Selection
After selection, the DE algorithm continues once again with a mutation operation followed by crossover until some stopping conditions are met. The stopping condition is predefined with a maximal number of generations, or a maximum number of function evaluations, etc.
Control Parameters
Globally, we distinguish between two major forms of setting parameter values: parameter tuning and parameter control. Parameter tuning means that an EA user finds good values of the parameters before running an algorithm and then running the algorithm using these (fixed) values. Parameter control means that parameter values are changing during the optimization process, by taking the actual search progress into account.
The original DE algorithm keeps all three control parameters fixed during the optimization process. However, there still exists a lack of knowledge about how to find reasonably good values for the control parameters of DE, for a given problem (Liu and Lampinen 2005). Thus, users are still faced with the problem of preliminary testing and hand tuning of its control parameters prior to commencing the actual optimization process (Teng et al. 2009). As a solution, approaches with adaptation and selfadaptation have proved to be highly beneficial for automatically and dynamically adjusting control parameters during the optimization process. Selfadaptation allows an evolutionary algorithm to adapt itself to any general class of problem, by reconfiguring itself accordingly, and does this without any user interaction (Bäck et al. 1997). On the other hand, when solving a particular problem using tuning, it is possible to find very good parameter values which are usually more competitive than a selfadaptive mechanism (Brest et al. 2015).

Deterministic – a deterministic rule is applied to change the value of a parameter.

Adaptive – some form of feedback from the search is used for determining the change of parameter’s value.

Selfadaptive – the idea of “evolution of the evolution” can be used to implement the selfadaptations of parameters. Parameters are encoded into the individuals and they undergo the actions of some operators. The better values of these encoded parameters lead to better individuals which, in turn, are more likely to survive and produce offspring and, hence, propagate these better parameter values (Eiben et al. 1999).
A Brief Overview of DE Algorithms
Since DE was introduced in 1995, several improvements were proposed. DEbased algorithms have showed a great performance and win or are ranked top among all algorithms on several evolutionary computation competitions. For excellent DE overview, its related work and applicability within various domains see surveys Das and Suganthan 2011; Neri and Tirronen 2010. Here, we outline some stateoftheart DEbased algorithms for single optimization.
Qin and Suganthan (Qin et al. 2009) proposed a Selfadaptive Differential Evolution algorithm (SaDE), where the choice of a mutation strategy and control parameters F and Cr are gradually selfadapted according to the learning experience. The algorithm combines two mutation strategies DE/rand/1 and DE/currenttobest/1. The parameter F is approximated by a normal distribution N (0.5, 0.3). A set of F values are randomly sampled from such normal distribution and applied to each target vector within the current population. The SaDE algorithm gradually adjusts the range of Cr values for a given problem according to previous Cr values which have generated trial vectors for successfully entering the next generation. Cr is approximated by a normal distribution with mean value Cr _{ m } and standard deviation Std = 0.1, denoted by \( \mathcal{N} \)(Cr _{ m }, Std), where Cr _{ m } is initialized as 0.5.
Zhang and Sanderson (2009) proposed selfadaptive DE (JADE) with anew mutation strategy, which utilizes information not only from the best individual but also from other good solutions.
Wang et al. in Wang et al. 2013 proposed a version of DE with generalized oppositionbased learning and selfadapting control parameters.
A distributed DE with several subpopulations and two migration selection approaches to maintaining a high diversity in the subpopulations are presented in Cheng et al. (2013).
An improved version of JADE is SuccessHistory based Adaptive DE (SHADE) (Tanabe and Fukunaga 2013). SHADE uses a historical memory in order to adapt the control parameters F and CR, currenttopbest/l mutation strategy (i.e., the same as used JADE), and external archive. LSHADE (Tanabe and Fukunaga 2014) is an improved version of the SHADE using linear population size reduction.
Applications
A short outline of applications where the jDE algorithm and other DEbased algorithms are applied: imagebased modeling and computer vision – reconstruction of procedural tree models (Zamuda et al. 2011; Zamuda and Brest 2014), tunning chess evaluation function (Bošković et al. 2011), dynamic optimization (Brest et al. 2013), underwater glider path planning (Zamuda and Sosa 2014), and hydrothermal optimization (Glotić and Zamuda 2015).
Future Directions
In the Differential Evolution algorithm that belongs to evolutionary algorithm, the adaptive and selfadaptive mechanisms of control parameters could improve performance of the algorithm. More mutation strategies and different crossover schemes can also be applied in the algorithm in order that the algorithm can adapt to a particular optimization problem.
Evolutionary algorithms find their applications in many domains of data mining such as bioinformatics, image processing, computer vision, pattern recognition, text categorization, information retrieval, and extraction, among many others. When solving real world problems, challenges are to deal with largescale optimization and how to allow an expert to interject her/his domain specific expert knowledge.
Codes and Other Sources
DE home page: www1.icsi.berkeley.edu/~storn/code.html (source codes of DE in many programming languages).
Benchmarks for Evaluation of Evolutionary Algorithms: www.ntu.edu.sg/home/epnsugan/indexfiles/cecbenchmarking.htm
Bibliography
 Bäck T, Fogel DB, Michalewicz Z (eds) (1997) Handbook of evolutionary computation, IOP Publishing Ltd., Bristol, UKGoogle Scholar
 Bošković B, Brest J, Zamuda A, Greiner S, Žumer V (2011) History mechanism supported differential evolution for chess evaluation function tuning. Soft Comput Fusion Found Methodol Appl 15:667–682Google Scholar
 Brest J, Maučec MS (2008) Population size reduction for the differential evolution algorithm. Appl Intell 29(3):228–247CrossRefGoogle Scholar
 Brest J, Greiner S, Bošković B, Mernik M, Žumer V (2006) Selfadapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Trans Evol Comput 10(6):646–657CrossRefGoogle Scholar
 Brest J, Korošec P, Šilc J, Zamuda A, Bošković B, Maučec MS (2013) Differential evolution and differential antstigmergy on dynamic optimisation problems. Int J Syst Sci 44:663–679zbMATHCrossRefGoogle Scholar
 Brest J, Zamuda A, Bošković B (2015) Adaptation in the differential evolution. In: Fister I, Fister I Jr (eds) Adaptation and hybridization in computational intelligence. Adaptation, learning, and optimization, vol 18. Springer International Publishing, Cham, CH. pp 53–68Google Scholar
 Cheng J, Zhang G, Neri F (2013) Enhancing distributed differential evolution with multicultural migration for global numerical optimization. Inform Sci 247:72–93MathSciNetCrossRefGoogle Scholar
 Das S, Suganthan P (2011) Differential evolution: a survey of the stateoftheart. IEEE Trans Evol Comput 15(1):27–54Google Scholar
 Das S, Abraham A, Chakraborty U, Konar A (2009) Differential evolution using a neighborhoodbased mutation operator. IEEE Trans Evol Comput 13(3):526–553CrossRefGoogle Scholar
 Eiben AE, Smith JE (2003) Introduction to evolutionary computing, Natural computing. Springer, BerlinzbMATHCrossRefGoogle Scholar
 Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141CrossRefGoogle Scholar
 Elsayed S, Sarker R, Essam D (2014) A selfadaptive combined strategies algorithm for constrained optimization using differential evolution. Appl Math Comput 241:267–282MathSciNetCrossRefGoogle Scholar
 Feoktistov V (2006) Differential evolution: in search of solutions (Springer optimization and its applications). Springer, New York/SecaucusGoogle Scholar
 Glotić A, Zamuda A (2015) Shortterm combined economic and emission hydrothermal optimization by surrogate differential evolution. Appl Energy 141:42–56CrossRefGoogle Scholar
 Karafotias G, Hoogendoorn M, Eiben A (2015) Parameter control in evolutionary algorithms: trends and challenges. IEEE Trans Evol Comput 19(2):167–187CrossRefGoogle Scholar
 Liu J, Lampinen J (2005) A fuzzy adaptive differential evolution algorithm. Soft Comput 9(6):448–462zbMATHCrossRefGoogle Scholar
 Mallipeddi R, Suganthan P (2010) Ensemble of constraint handling techniques. IEEE Trans Evol Comput 14(4):561–579CrossRefGoogle Scholar
 Mukhopadhyay A, Maulik U, Bandyopadhyay S, Coello C (2014a) Survey of multiobjective evolutionary algorithms for data mining: part II. IEEE Trans Evol Comput 18(1):20–35CrossRefGoogle Scholar
 Mukhopadhyay A, Maulik U, Bandyopadhyay S, Coello Coello C (2014b) A survey of multiobjective evolutionary algorithms for data mining: part I. IEEE Trans Evol Comput 18(1):4–19CrossRefGoogle Scholar
 Neri F, Tirronen V (2009) Scale factor local search in differential evolution. Memetic Comp 1(2):153–171CrossRefGoogle Scholar
 Neri F, Tirronen V (2010) Recent advances in differential evolution: a survey and experimental analysis. Artif Intell Rev 33(1–2):61–106CrossRefGoogle Scholar
 Price KV, Storn RM, Lampinen JA (2005) Differential evolution, a practical approach to global optimization. Springer, Berlin Heidelberg, Germany.Google Scholar
 Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):398–417CrossRefGoogle Scholar
 Storn R, Price K (1995) Differential evolution – a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical report TR95012, BerkeleyGoogle Scholar
 Storn R, Price K (1997) Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11:341–359zbMATHMathSciNetCrossRefGoogle Scholar
 Tanabe R, Fukunaga A (2013) Evaluating the performance of shade on cec 2013 benchmark problems. In: 2013 IEEE congress on evolutionary computation (CEC), 20–23 june, 2013, Cancun, Mexico. IEEE, pp 1952–1959Google Scholar
 Tanabe R, Fukunaga A (2014) Improving the search performance of SHADE using linear population size reduction. In: 2014 IEEE congress on evolutionary computation (CEC2014), 6–11 July 2014, Beijing, China. IEEE, pp 1658–1665Google Scholar
 Teng NS, Teo J, Hijazi MHA (2009) Selfadaptive population sizing for a tunefree differential evolution. Soft Comput Fusion Found Methodol Appl 13(7):709–724Google Scholar
 Wang H, Rahnamayan S, Wu Z (2013) Parallel differential evolution with selfadapting control parameters and generalized oppositionbased learning for solving highdimensional optimization problems. J Parallel Distrib Comput 73(1):62–73CrossRefGoogle Scholar
 Wu X, Zhu X, Wu GQ, Ding W (2014) Data mining with big data. IEEE Trans Knowl Data Eng 26(1):97–107CrossRefGoogle Scholar
 Zamuda A, Brest J (2014) Vectorized procedural models for animated trees reconstruction using differential evolution. Inform Sci 278:1–21MathSciNetCrossRefGoogle Scholar
 Zamuda A, Sosa JDH (2014) Differential evolution and underwater glider path planning applied to the shortterm opportunistic sampling of dynamic mesoscale ocean structures. Appl Soft Comput 24:95–108CrossRefGoogle Scholar
 Zamuda A, Brest J, Bošković B, Žumer V (2011) Differential evolution for parameterized procedural woody plant models reconstruction. Appl Soft Comput 11:4904–4912CrossRefGoogle Scholar
 Zhang J, Sanderson A (2009) JADE: adaptive differential evolution with optional external archive. IEEE Trans Evol Comput 13(5):945–958CrossRefGoogle Scholar