Article Preview
TopI. Introduction
The great development in the field of Evolutionary Algorithms (EAs) in the last decades has greatly improved their efficiency and applicability to solve optimization problems in many different domains in engineering and computer science (Eiben & Smith, 2008). The family of EAs includes today a wide range of optimization techniques and heuristic methods, among which the class of Genetic Algorithms is perhaps the most popular, successfully adapted to solve various classes of discrete and continuous optimization problems (Gen & Cheng, 1997; Goldberg, 1989). Nonetheless the family has recently been increased by new members, such as Artificial Immune Systems (de Castro & Timmis, 2002), Estimation of Distribution Algorithms (Larranaga & Lozano, 2002), Differential Evolution algorithms (Price, 1999; Price & Storn, 1997; Price, Storn, & Lampinen, 2005) and others.
The Differential Evolution (DE) algorithm was first proposed in the mid 1990s for optimization with continuous variables (Price, 1999; Price & Storn, 1997; Price, Storn, & Lampinen, 2005) and is nowadays an important and powerful optimizer in this context for single objective optimization (Mezura-Montes, Velázquez-Reyes, & Coello, 2006; Price, Storn, & Lampinen, 2005; Chakraborty, 2008) and, more recently, also for multi-objective problems (Batista, Guimarães, & Ramírez, 2009; Xue, Sanderson, & Graves, 2003). This success is mainly due to its powerful yet simple differential mutation mechanism, which uses differential vectors built with pairs of randomly chosen vectors among the candidate solutions, in order to produce new solutions. As the population evolves, the search directions and step sizes in the differential mutation change over time, self-adapting according to the distribution of the population in the search domain. DE uses a rather greedy yet stochastic approach to problem solving, combining simple arithmetic operators with the classical operators of crossover, mutation and selection to evolve a random initial population to a high-quality final solution.
The DE algorithm fits the general scheme of an EA and, for this reason, inherits much of the background and terminology from EAs. However, the differential mutation has no direct basis or inspiration on any natural process. The way this operator generates perturbations (mutations) is based on heuristic and mathematical arguments that indicate its adequacy for optimization, instead of arguments derived from nature. Nevertheless, the DE metaheuristic can be classified as an instance of EAs, since it evolves a population of candidate solutions for the problem with stochastic heuristic operators inspired in very general ideas of natural computing and natural adaptation.
Although the algorithm was initially designed for nonlinear continuous optimization, some discrete versions of the DE have been proposed in the literature, particularly in the last few years. For instance, Qian et al. (2008) present a discrete version of DE for permutation flow shop scheduling problems. Alatas et al. (2008) develop a discrete version of DE for mining association rules in data mining, proposing specific rounding and repairing operators. Onwubolu and Davendra (2006) have also reported interesting results on flow shop scheduling problems.