![]() |
|||
![]()
|
![]() |
![]() |
![]() |
2.1. INITIALIZATIONFirst, one must decide on the best way to encode possible solutions. Each encoding is known as a chromosome or genotype, which consists of a number of genes. Typically, a binary coding is used to create a genotype, with 1 indicating the presence of an gene and 0 indicating absence. These genes are then concatenated to form a chromosome of fixed length n, where n is the number of genes. Binary encoding is normally used; however, there are cases where a real number may be appropriate. For an example, refer to Table 1. In Table 1, each car has certain genes. In the transmission column, 0 indicates a manual transmission, while 1 indicates an automatic transmission. In the drive column, 0 indicates 2-wheel drive, while 1 indicates 4-wheel drive. In the passenger column, 0 indicates two passengers, and 1 indicates four passengers. So, the Car 1 chromosome would be encoded as 010, while the Car 2 chromosome would be encoded as 101. Thus, a population of two has just been generated. GAs are not limited to binary encoding. Real numbers or string values can also be used, as well as variable-length chromosomes. However, GAs traditionally use fixed-length encodings. The population size should be relatively small while in testing phases (<500 genotypes). Once the system matures, the population should expand as much as possible, constrained by computer resources and time. The bigger the population, the better chance that the GA will find a close-to-optimal solution.
The initial population should be diverse, since these genotypes will be combined to create new solutions that did not previously exist in the population. One of the advantages of GAs is that they can investigate new solutions that humans don't have the time to think about or generate. The initial population can be generated randomly. A better starting point for GAs, though, would be to heuristically generate an initial population. The better the starting point, the more quickly GAs can converge or find a good solution. The remaining steps attempt to improve on the overall quality of the population. 2.2. EVALUATIONThe purpose of this step is to evaluate the fitness of all the genotypes in the population. This step is typically the most difficult and computationally costly, since the fitness function must be applied to each member of the population. Depending on the domain, it is also sometimes difficult to create an effective fitness function. One alternative is to partially compute the fitness, and require the user to finish evaluating potentially promising genotypes. This might prove useful for those situations where the fitness function cannot be explicitly encoded, and requires human input for accurate evaluation. Fitness functions should be able to evaluate both the valid and invalid genotypes in the population. An invalid genotype is a solution that is not feasible or applicable for the problem. The fitness function should evaluate these invalid genotypes since they may still contain good genetic material. If your fitness function automatically discards those genotypes, then that combination of genes will be lost. Plotting all possible genotypes and their evaluated fitness produces a fitness landscape, an n-dimensional region that contains all possible solutions. The peaks and valleys of this landscape indicate the maxima or minima that the GA is searching for. In the car example, an example fitness function could be the decimal equivalent of the chromosome, i.e., the genotype encoded as 101 would be evaluated to have a fitness of 5. This is a trivial fitness function, and an actual implementation of a GA would certainly use a more realistic function. The result of this step is a population ordered by fitness. The determination can then be made on which genotypes will survive to the next generation, simulating the evolutionary paradigm. 2.3. SELECTIONIn this step, selected members in the population reproduce and exchange genetic material. Generally, the low fitness genotypes are culled and the best are rewarded. The genotypes with better fitness can expand to take up a larger percentage of the population, while those genotypes with poor fitness will decrease in numbers. There are a variety of selection operators that can be applied:
The selection operators are not limited to those explained, as there are many variations that can exist for particular domains. 2.4. SEARCHNow that the population has adjusted itself to take advantage of the higher fitness genotypes, search operators are used to recombine or create new genotypes. The two most popular are crossover and mutation. Crossover exchanges genetic material between genotypes, and mutation injects random changes to selected genes. 2.4.1. Crossover The crossover operation allows genotypes to exchange genes. Crossover is not essential for success, but it does allow genotypes to essentially exchange genetic information. Figure 2 illustrates a crossover operation of length 2 acting on two genotypes of length 5. In this case, the two genotypes exchange their tails (the last two positions, hence a crossover of 2), resulting in two new and different genotypes. Crossover will not always create a new genotype that was not present in the current population, but it does allow the exchange of genes. The crossover operation is not limited to the one explained here. Different types of problem-specific crossover operations have been implemented.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |