A New Differential Evolution Based Metaheuristic for Discrete Optimization

A New Differential Evolution Based Metaheuristic for Discrete Optimization

Ricardo Sérgio Prado (Instituto Federal de Minas Gerais, Brazil), Rodrigo César Pedrosa Silva (Universidade Federal de Ouro Preto, Brazil), Frederico Gadelha Guimarães (Universidade Federal de Ouro Preto, Brazil) and Oriane M. Neto (Universidade Federal de Minas Gerais, Brazil)
Copyright: © 2012 |Pages: 16
DOI: 10.4018/978-1-4666-1574-8.ch006
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The Differential Evolution (DE) algorithm is an important and powerful evolutionary optimizer in the context of continuous numerical optimization. Recently, some authors have proposed adaptations of its differential mutation mechanism to deal with combinatorial optimization, in particular permutation-based integer combinatorial problems. In this paper, the authors propose a novel and general DE-based metaheuristic that preserves its interesting search mechanism for discrete domains by defining the difference between two candidate solutions as a list of movements in the search space. In this way, the authors produce a more meaningful and general differential mutation for the context of combinatorial optimization problems. The movements in the list can then be applied to other candidate solutions in the population as required by the differential mutation operator. This paper presents results on instances of the Travelling Salesman Problem (TSP) and the N-Queen Problem (NQP) that suggest the adequacy of the proposed approach for adapting the differential mutation to discrete optimization.
Chapter Preview
Top

1. 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.

Complete Chapter List

Search this Book:
Reset