Abstract
Performance of genetic algorithms (GAs) is mainly determined by several factors. Not only the genetic operators affect the performance of a GA with varying degrees, but also the parameter settings for genetic operators interact in a complicated manner with each other in influencing a GA’s performance. Though many studies have been conducted for this cause, they failed to converge to consistent conclusions regarding the importance of different genetic operators and their parameter settings on the performance of GAs. Actually, optimizing the combinations of different strategies and parameters for different problem types is an NPcomplete problem in itself, and is still an open research problem for GAs (Mitchell, 1996). Recognizing the intrinsic difficulties in finding universally optimal parameter configurations for different classes of problems, we advocate the experience-based approach to discovering generalized guiding rules for different problem domains. To this end, it is necessary for us to gain a better understanding about how different genetic operators and their parameter combinations affect a GA’s behavior. In this research, we systematically investigate, through a series of experiments, the effect of GA operators and the interaction among GA operators on the performance of the GA-based batch selection system as proposed in Deng (2007). This paper intends to serve as an initial inquiry into the research of useful design guidelines for configuring GA-based systems.
TopParameter Configuration For Genetic Operators
It is commonly believed that crossover is the major operator of GAs, with mutation preventing the population from early convergence to a certain solution before an extensive exploration of other candidate solutions is made (Holland, 1992a). Crossover enables GAs to focus on the most promising regions in a solution space; however, mutation alone does not advance the search for a solution. Crossover is also a more robust constructor of new candidate solutions than mutation (Spears, 1993).
However, Muhlenbein (1992) argues that the power of mutation has been underestimated in traditional GAs. According to Mitchell (1996), it is not a choice between crossover or mutation but rather the balance among crossover, mutation, and other factors, such as selection, that is all important. The correct balance also depends upon the details of the fitness function and the encoding. Furthermore, crossover and mutation vary in relative usefulness over the course of a run. Actually, the theretical analysis of crossover is still to a large extent an open problem (Back, et al., 1997).
In addition to the GA operators, the population size also affects the performance of GAs. The specification of the population size affects the diversification of the population body and the implicit parallelism of a GA, and will thus affect the quality of the generated solutions and the performance of the solution-generating process. Choosing an appropriate population size for a GA is a necessary but difficult task for GA users. Usually, the parameter settings for most GA applications are based on De Jong’s recommendations (De Jong, 1975). According to De Jong’s experiments with five problems in function minimization, the best population size was 50~100, the best crossover rate was about 0.6, and the best mutation rate was 0.001. In a later study, Spears & De Jong (1991) suggested a wider range for the crossover rate as 0.5~0.8. Mitchell (1996) also observed that it was common in GA applications to set crossover rate at 0.7~0.8.
Key Terms in this Chapter
Schemata: A general pattern of bit strings that is made up of 1, 0, and #, used as a building block for solutions of the GA.
NP-Complete Problems: The hardest problems in the class NP—the class of nondeterministic polynomial problems.
Implicit Parallelism: A property of the GA which allows a schema to be matched by multiple candidate solutions simultaneously without even trying.
Fitness Function: The objective function of the GA for evaluating a population of solutions.
Batch Selection: Selecting the optimal set of products to produce, with each product requiring a set of resources, under the system capacity constraints.
Landscape: A function plot showing the state as the “location” and the objective function value as the “elevation”.
Genetic Operators: Selection, crossover, and mutation, for combining and refining solutions in a population.