Genetic Algorithms

Standard GAs are search techniques based on the mechanics of natural selection and genetics [62]. The search for the optimal solution starts by initializing a population of solutions. This initialization is carried out by selecting random values for all the variables in each solution. This population evolves over time and converges to nearly-optimal solutions over a set of generations (iterations) of the algorithm. To set up a simple genetic algorithm, we start by coding (rep-

A chromosome (code) is a string of genes that represent a solution

Figure 6.2: A chromosome (code) is a string of genes that represent a solution.

resenting) each solution in the population by a chromosome that consists of a string of genes. Each gene is the code of a variable, and hence the number of genes is the number of design variables. Figure 6.2 shows a typical chromosome that consists of N genes gi,g2,---,g/v- The value of gt determines the value of that variable in that solution. Associated with each chromosome (solution) is a fitness value which determines how fit is that solution. The fitness of the solution is determined based on the objective of optimization.

Starting with the initial population of solutions, GAs perform a number of operations on the current population to produce a new population of solutions; this new population of solutions is a new generation. At each generation, a Selection operator causes the highly fit solutions to survive in the population, and the less fit solutions to die. The GAs operations are then applied to the surviving solutions to create new solutions (offspring solutions) for the new generation. Of these GAs operations is the Crossover operation which is applied to randomly selected two individuals in the mating pool, bifurcate them at randomly selected sites, swap the string of genes, and create new individuals. The crossover operation is carried out with a probability pc. A Mutation operation is also applied where the mutation operator goes through all the bits in all the genes of the population and modifies a particular bit with a mutation probability p,„. The same processes of selection, crossover and mutation are repeated in each generation to produce a newer generation until a stopping criteria is satisfied. As can be seen from the above brief, the GAs work on a fixed length chromosome, and hence the number of variables should be constant. GAs are then not suitable for the VSDS optimization problems.

GAs work with coded variables sets. Each variable is assigned a number of bits for coding. A member (or a chromosome) is the code for a stack of the binary codes for all variables together in one string. A group of chromosomes is called a population. Subsequent generations follow by performing a series of probabilistic operations on the current population. The basic operations that are used in all genetic algorithms are: reproduction, crossover, and mutation . Pairs of members are selected to undergo a crossover with a probability Pc, at a random point in the chromosome. Mutation is applied to all bits in all members in a generation with a probability Pm.

Given the above description for the different operations of genetic algorithms, there remains the question of why does it work? or in other words, how does it find the global optimal solution? There are different ways of explaining how the genetic algorithms work. One of the most simple ways to explain how it works is

The Schemata Theory, which is briefed below based on [62]. The Markov chain model of genetic algorithms is briefed in Section 6.2.2 based on [101] and [31].

Similarity Templates (schemata)

A schema (plural is schemata) is a subset of chromosomes with similarities at certain string positions. The order of a schema Я, o(H), is the number of fixed positions in the template (e.g., o(011 * 1 * *) = 4, where * is the DO NOT CARE value.) The defining length of a schema, 5(H), is the distance between the first and the last specific positions in the string, e.g., 5(011 * 1 * *)= 4. The number of members of the schema Я at a given time / is m = A particular

schema 5, receives an expected number of members in the next generation under reproduction according to Eq. (6.1).

where /(Я) is a scalar function representing the average fitness for the strings of the schema Я, fp is the population average fitness. A schema survives a crossover operation with the probability Ps, where:

and nh is the number of bits in the member, Pc is the crossover probability. The survival probability of a schemata Я can be approximated by: 1 —o(H)Pm. So, by combining the reproduction, crossover and mutation operations, a particular schema receives an expected number of members in the next generation as given by:

Equation (6.3) represents the Fundamental Theorem of GA.

 
Source
< Prev   CONTENTS   Source   Next >