Comparison among five evolutionary-based optimization algorithms
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], [4], [5]. Despite their benefits, GAs may require long processing time for a near-optimum 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 (MAs) [7], particle swarm optimization (PSO) [8], ant-colony 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.
Section snippets
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.
Comparison among evolutionary algorithms' results
All the EAs described earlier have been coded using the Visual Basic programming language and all experiments took place on a 1.8 GHz AMD Laptop machine. The performance of the five EAs is compared using two benchmark problems for continuous optimization and a third problem for discrete optimization. A description of these test problems is given in the following.
Conclusions
In this paper, five evolutionary-based search methods were presented. These include: GA, MA, PSO, ACO, and SFL. A brief description of each method is presented along with a pseudocode to facilitate their implementation. Visual Basic programs were written to implement each algorithm. Two benchmark continuous optimization test problems were solved using all but the ACO algorithm, and the comparative results were presented. Also presented were the comparative results found when a discrete
References (27)
- et al.
Ant colonies for the traveling salesman problem
Biosystems, Elsevier Sci
(1997) - et al.
Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of Jobs
Eur J Oper Res
(2004) - et al.
A direct stochastic algorithm for global search
J Appl Math Comput
(2003) - Lovbjerg M. Improving particle swarm optimization by hybridization of stochastic search heuristics and self-organized...
Adaptation in natural and artificial systems
(1975)- et al.
Using genetic algorithms to solve optimization problems in construction
Eng Constr Archit Manage
(1999) Optimization of construction time-cost trade-off analysis using genetic algorithms
Can J Civil Eng
(1999)- et al.
Method for conceptual design applied to office buildings
J Comput Civil Eng
(2002) - Joglekar A, Tungare M. Genetic algorithms and their use in the design of evolvable hardware....
- Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms....
Particle swarm optimization
Ant system: optimization by a colony of cooperating agents
IEEE Trans Syst Man Cybern
Optimization of water distribution network design using the shuffled frog leaping algorithm
J Water Resour Plan Manage
Cited by (0)
- 1
Tel.: +1 519 888 4567x2174; fax: +1 519 888 6197.
- 2
Tel.: +1 519 888 4567x2412; fax: +1 519 888 6197.