Parallel Single and Multiple Objectives Genetic Algorithms: A Survey

1. Introduction

Genetic algorithms (GAs) are a class of powerful search techniques that are popularly being used to solve problems in many different disciplines such as business, engineering, and science (Aguirre & Coello, 2002; Al-Somani, 2000; Alander, 1994). Researchers have found GAs to be especially useful for solving problems with large number of parameters whose effects on the problems are not well understood. For many complex problems, GAs find good solutions in reasonable amounts of time. However, GAs usually require large number of expensive function evaluations to be made. Based on the cost of each evaluation GAs may take days, months or even years to find an acceptable solution. Therefore, parallelization of GAs is an attractive proposition in such situation.

Parallel GAs (PGAs) have been found to be particularly easy to implement and at the same time yield substantial gains in performance (Grama, Gupta, & Kumar, 1993). For example, adoption of sequential GA based solution to problems such as classification and association rule mining tasks with very large population sizes and long chromosomal representations may take considerable amount of time. Parallel GAs can provide effective solutions to these problems. PGAs have been observed to yield good results for different classes of problems. However, there are many problems that are highly dominated by computational costs and also many open questions arise in designing appropriate PGAs for these (Alba & Tomasdni, 2002). In particular, the design of PGAs involves making choices like single or multiple population, size of the population in either case, and for multiple population one must decide how many to use. Furthermore the population may remain isolated or they may communicate by exchanging individual or some other information. Communication involves extra cost and additional decision making depending on the pattern of communication, on the number of individuals participating in the communication, and on the frequency of communication. This paper reviews the state-of-the-art models of the PGAs and identifies their pros and cons. Additionally, some of the emerging issues (Cantu-Paz, 1998; Alba & Troya, 2002) are discussed.

So far, we have confined our discussions to the single objective genetic algorithms and its parallel-realization. However, most real world search and optimization problems do involve multiple objectives (Coello et al., 2002). A suitable solution may require making trade-offs (conflicting scenario) among different objectives. A solution that is optimum with respect to one objective may require compromising other objectives. Hence, simultaneous optimization of various objectives considering Pareto- optimal solutions (Coello, 1999) is required.

The ability of GAs to find multiple Pareto optimal solutions in one run makes it a preferred technique for solving multi-objective optimization problems. Over the years a large number of multi-objective evolutionary algorithms (MOEAs) have been proposed (Coello, 2000, 2001; Knowles & Corne, 2000; Deb, 2001; Fonseca & Flemming, 1993; Zitzler et al., 2003). MOEAs like Vector Evaluated Genetic Algorithm (VEGA), Multi-Objective Genetic Algorithm (specifically Fonseca MOGA), Niched-Pareto Genetic Algorithm (NPGA), Non-Dominated Sorting Genetic Algorithm-II (NSGA II), Strength Pareto Evolutionary Algorithm (SPEA), Pareto-Archived Evolution Strategy (PAES), etc, are computationally very expensive, because instead of searching for single optimal solution, one generally needs to find the whole front of Pareto optimal solution. For that reason, parallelizing MOGAs (in general) has caught the attention of interest of many researchers.