![]() |
Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin CRC Press, CRC Press LLC ISBN: 0849398045 Pub Date: 11/01/98 |
Previous | Table of Contents | Next |
Evolutionary computation is the name given to a collection of algorithms based on the evolution of a population toward a solution of a certain problem. These algorithms can be used successfully in many applications requiring the optimization of a certain multi-dimensional function. The population of possible solutions evolves from one generation to the next, ultimately arriving at a satisfactory solution to the problem. These algorithms differ in the way a new population is generated from the present one, and in the way the members are represented within the algorithm. Three types of evolutionary computing techniques have been widely reported recently. These are Genetic Algorithms (GAs), Genetic Programming (GP) and Evolutionary Algorithms (EAs). The EAs can be divided into Evolutionary Strategies (ES) and Evolutionary Programming (EP). All three of these algorithms are modeled in some way after the evolutionary processes occurring in nature.
Genetic Algorithms were envisaged by Holland [12] in the 1970s as an algorithmic concept based on a Darwinian-type survival-of-the-fittest strategy with sexual reproduction, where stronger individuals in the population have a higher chance of creating an offspring. A genetic algorithm is implemented as a computerized search and optimization procedure that uses principles of natural genetics and natural selection. The basic approach is to model the possible solutions to the search problem as strings of ones and zeros. Various portions of these bit-strings represent parameters in the search problem. If a problem-solving mechanism can be represented in a reasonably compact form, then GA techniques can be applied using procedures to maintain a population of knowledge structure that represent candidate solutions, and then let that population evolve over time through competition (survival of the fittest and controlled variation). The GA will generally include the three fundamental genetic operations of selection, crossover and mutation. These operations are used to modify the chosen solutions and select the most appropriate offspring to pass on to succeeding generations. GAs consider many points in the search space simultaneously and have been found to provide a rapid convergence to a near optimum solution in many types of problems; in other words, they usually exhibit a reduced chance of converging to local minima. GAs show promise but suffer from the problem of excessive complexity if used on problems that are too large.
Generic algorithms are an iterative procedure that consists of a constant-sized population of individuals, each one represented by a finite linear string of symbols, known as the genome, encoding a possible solution in a given problem space. This space, referred to as the search space, comprises all possible solutions to the optimization problem at hand. Standard genetic algorithms are implemented where the initial population of individuals is generated at random. At every evolutionary step, also known as generation, the individuals in the current population are decoded and evaluated according to a fitness function set for a given problem. The expected number of times an individual is chosen is approximately proportional to its relative performance in the population. Crossover is performed between two selected individuals by exchanging part of their genomes to form new individuals. The mutation operator is introduced to prevent premature convergence.
Every member of a population has a certain fitness value associated with it, which represents the degree of correctness of that particular solution or the quality of solution it represents. The initial population of strings is randomly chosen. The strings are manipulated by the GA using genetic operators, to finally arrive at a quality solution to the given problem. GAs converge rapidly to quality solutions. Although they do not guarantee convergence to the single best solution to the problem, the processing leverage associated with GAs make them efficient search techniques. The main advantage of a GA is that it is able to manipulate numerous strings simultaneously, where each string represents a different solution to a given problem. Thus, the possibility of the GA getting stuck in local minima is greatly reduced because the whole space of possible solutions can be simultaneously searched. A basic genetic algorithm comprises three genetic operators.
Starting from an initial population of strings (representing possible solutions), the GA uses these operators to calculate successive generations. First, pairs of individuals of the current population are selected to mate with each other to form the offspring, which then form the next generation. Selection is based on the survival-of-the-fittest strategy, but the key idea is to select the better individuals of the population, as in tournament selection, where the participants compete with each other to remain in the population. The most commonly used strategy to select pairs of individuals is the method of roulette-wheel selection, in which every string is assigned a slot in a simulated wheel sized in proportion to the strings relative fitness. This ensures that highly fit strings have a greater probability to be selected to form the next generation through crossover and mutation. After selection of the pairs of parent strings, the crossover operator is applied to each of these pairs.
The crossover operator involves the swapping of genetic material (bit-values) between the two parent strings. In single point crossover, a bit position along the two strings is selected at random and the two parent strings exchange their genetic material as illustrated below.
The swapping of genetic material between the two parents on either side of the selected crossover point, represented by |, produces the following offspring:
Offspring A | = a1 a2 a3 a4 | b5 b6 |
Offspring B | = b1 b2 b3 b4 | a5 a6 |
Previous | Table of Contents | Next |