Genetic Algorithm

GAs operate simultaneously on a population of potential solutions applying the principle of natural evolution, i.e., survival of the fittest, to produce better and better approximations to a solution of a problem. At each generation, a new set of approximations (population) is created by the process of selecting individuals according to their level of fitness in the problem domain and breeding them together using operators borrowed from natural genetics. This process leads to the evolution of populations of individuals which are better suited to their environment than the individuals that they are created from. The major elements of the GA operations are:

• Initialization, which is usually achieved by generating the required number of individuals using a random number generator. A chromosome representation is needed to describe each individual in the population of interest. The binary representation which is most commonly used in GAs, however, does not yield satisfactory results when applied to multi-dimensional, high precision numerical problems. A more natural representation, real-valued representation, is more attractive for numerical function optimization over binary encodings. With this kind of representation, the computational speed of computers increases as there is no need to convert bit-strings to real values and vice versa, and less memory is required as the floatingpoint computers can deal with real values directly.

• Evaluation, which is done by evaluating the predefined fitness functions. The fitness function is used to provide a measure of how individuals have performed in the problem domain. In many cases, the fitness function value corresponds to the number of offspring which an individual can expect to produce in the next generation. It is the driving force behind GAs.

• Selection, which is performed based upon the individual's fitness such that the better individuals have an increased chance of being selected. There are several schemes for the selection process: roulette wheel selection, scaling techniques, tournament, elitist models, and ranking methods. The first selection method is adopted in this research.

• Cross-over and mutation, which are the basic search mechanisms for producing new solutions based on existing solutions in the population. These operators enable the evolutionary process to move towards "promising" regions of the search space. Like their counterpart in nature, crossover produces new individuals which recombine some parts of both parents' genetic material while mutation alters one individual to produce a single new solution. The crossover operation is applied with a probability Px ("crossover probability" or "crossover rate") when the pairs are chosen for breeding. A mutation operator is introduced to prevent premature convergence to local optima by randomly sampling new points in the search domain and is applied with low probability Pm ("mutation rate").

• Termination, which is the end of a run of a GA. A common practice is to terminate a GA after a pre-specified number of generations and then test the quality of the best member of the population against the problem definition. If no acceptable solutions are found, a GA may be restarted or initialized to a fresh search.

In this study, the values of the rate of selection, crossover, and mutation were chosen as 0.08, 0.6, and 0.05 respectively.

Was this article helpful?

0 0

Post a comment