217.

[Cover] [Contents] [Index]

Page 293

the idea of the ‘survival of the fittest’ structures in the current population is used to create a new population based on both structured and randomised information exchange between the present and the new population. The GA search process can be allowed to run for a pre-specified number of iterations, or the search can be continued until the fitness function converges. The GA is said to have converged if approximately 95% of the structures forming the population contains the same value.

Why can the performance GA surpass that of more traditional search methodologies, e.g. calculus-based, enumerative schemes and random search algorithms? As Goldberg (1989) notes, there are several significant differences between GA and other algorithms that contribute to GA’s highly promising performance. The first difference is that G A uses multiple start points for performing the search process and deals with the special trial structures, which are codings of the original parameter set. The second reason is that GA uses an objective function (the measure of fitness of each trial structure) to lead its search process, and is not dependent on derivatives or auxiliary knowledge. Finally, the transition from one generation to the succeeding generation is based on probabilistic, instead of deterministic, rules.

The initial population used in a GA may be chosen at random or composed of heuristically selected initial points. A fitness function is used to evaluate each structure’s performance. GA then constructs a new generation using three basic operators known as reproduction, crossover and mutation. In the reproduction process, individuals are randomly selected from the present population. Although the selection is random, the expected number of times an individual is selected is associated with the individual’s performance. For example, if an individual’s performance is three times the average performance of the population, this individual will be present three times in the new generation. As a result, individuals with low performance will be filtered out, and only high performance individuals will survive.

In order to introduce new individuals into the search process in the new generation, GA uses the procedures of crossover and mutation. Crossover can be regarded as information exchange between two individuals. For instance, in a simple crossover process for two individuals (both represented by string of length λ), a cutting point within the string is randomly selected. Then two substrings, addressed from to λ, of both individuals are exchanged. This will form two new individuals. Figure 7.4 illustrates the process.

The mutation operation is carried out by randomly changing bits within the individual’s coding from 1 to 0 or from 0 to 1. The main contribution of the mutation operation is to ensure that the search process by the genetic algorithm will not be limited by local maxima (or minima). Goldberg

[Cover] [Contents] [Index]