01-01-2013, 01:47 PM
Comparison among five evolutionary-based optimization algorithms
Comparison among five evolutionary.pdf (Size: 372.65 KB / Downloads: 23)
Abstract
Evolutionary algorithms (EAs) are stochastic search methods that mimic the natural biological evolution and/or the social behavior of
species. Such algorithms have been developed to arrive at near-optimum solutions to large-scale optimization problems, for which traditional
mathematical techniques may fail. This paper compares the formulation and results of five recent evolutionary-based algorithms: genetic
algorithms, memetic algorithms, particle swarm, ant-colony systems, and shuffled frog leaping. A brief description of each algorithm is
presented along with a pseudocode to facilitate the implementation and use of such algorithms by researchers and practitioners. Benchmark
comparisons among the algorithms are presented for both continuous and discrete optimization problems, in terms of processing time,
convergence speed, and quality of the results. Based on this comparative analysis, the performance of EAs is discussed along with some
guidelines for determining the best operators for each algorithm. The study presents sophisticated ideas in a simplified form that should be
beneficial to both practitioners and researchers involved in solving optimization problems.
q 2005 Elsevier Ltd. All rights reserved.
Keywords: Evolutionary algorithms; Genetic algorithms; Memetic algorithms; Particle swarm; Ant colony; Shuffled frog leaping; Optimization
1. Introduction
The difficulties associated with using mathematical
optimization on large-scale engineering problems have
contributed to the development of alternative solutions.
Linear programming and dynamic programming techniques,
for example, often fail (or reach local optimum) in
solving NP-hard problems with large number of variables
and non-linear objective functions [1]. To overcome these
problems, researchers have proposed evolutionary-based
algorithms for searching near-optimum solutions to
problems.
Evolutionary algorithms (EAs) are stochastic search
methods that mimic the metaphor of natural biological
evolution and/or the social behavior of species. Examples
include how ants find the shortest route to a source of food
and how birds find their destination during migration. The
behavior of such species is guided by learning, adaptation,
and evolution [1]. To mimic the efficient behavior of these
species, various researchers have developed computational
systems that seek fast and robust solutions to complex
optimization problems. The first evolutionary-based technique
introduced in the literature was the genetic algorithms
(GAs) [2]. GAs were developed based on the Darwinian
principle of the ‘survival of the fittest’ and the natural
process of evolution through reproduction. Based on its
demonstrated ability to reach near-optimum solutions to
large problems, the GAs technique has been used in many
applications in science and engineering [3–5]. Despite their
benefits, GAs may require long processing time for a nearoptimum
solution to evolve. Also, not all problems lend
themselves well to a solution with GAs [6].
In an attempt to reduce processing time and improve the
quality of solutions, particularly to avoid being trapped in
local optima, other EAs have been introduced during the
past 10 years. In addition to various GA improvements,
recent developments in EAs include four other techniques
inspired by different natural processes: memetic algorithms
1474-0346/$ - see front matter q 2005 Elsevier Ltd. All rights reserved.
doi:10.1016/j.aei.2005.01.004
Advanced Engineering Informatics 19 (2005) 43–53
www.elsevierlocate/aei
* Corresponding author. Tel.: C20 50 224 4105; fax: C20 50 224 4690.
E-mail addresses: eelbelta[at]mans.edu.eg (E. Elbeltagi), tarek@
uwaterloo.ca (T. Hegazy), grierson[at]uwaterloo.ca (D. Grierson).
1 Tel.: C1 519 888 4567x2174; fax: C1 519 888 6197.
2 Tel.: C1 519 888 4567x2412; fax: C1 519 888 6197.
(MAs) [7], particle swarm optimization (PSO) [8], antcolony
systems [9], and shuffled frog leaping (SFL) [10]. A
schematic diagram of the natural processes that the five
algorithms mimic is shown in Fig. 1.
In this paper, the five EAs presented in Fig. 1 are
reviewed and a pseudocode for each algorithm is presented
to facilitate its implementation. Performance comparison
among the five algorithms is then presented. Guidelines are
then presented for determining the proper parameters to use
with each algorithm.
Five evolutionary algorithms
In general, EAs share a common approach for their
application to a given problem. The problem first requires
some representation to suit each method. Then, the
evolutionary search algorithm is applied iteratively to arrive
at a near-optimum solution. A brief description of the five
algorithms is presented in the following subsections.