![]() |
|||
![]()
|
![]() |
![]() |
![]() |
2.6. VARIATIONSGAs usually converge to a single genotype, or solution. There are times when it might be necessary to find either several or all the optimal solutions for a problem. Methods that prevent a GA from converging to a single solution are known as niching methods. Niching methods reduce competition between genotypes where there is sufficient difference, thus allowing subpopulations to exist. Each of these subpopulations occupy one section of the entire search space. Within each subpopulation, the genotypes would hopefully evolve to the local maximum. If each subpopulation successfully evolved, then multiple maximums could be found, as opposed to one single optimal solution. Niching can also be used to prevent premature convergence even when a single solution is desired. There are two classes of niching methods: crowding and sharing. Crowding methods restrict individual replacement to reduce competition between genotypes that greatly differ within a niche. When a new genotype is introduced into the population, it replaces an individual who most resembles it. Sharing methods reduce a genotype's fitness when similar genotypes exist within a particular niche. Using the sharing method incurs an additional computational cost, since genotypes must be compared to each other. There exist iterative techniques where the same population is run several times, or subpopulations run with communication between them, in the hope that different solutions could be discovered. This usually does not happen. Beasley addressed this problem by using derating functions. Derating functions vary the fitness function between runs so that the same search space is not explored. The difficulty lies in knowing when all the solutions have been found so that the runs may be terminated. Another variation of GAs is to implement them in parallel. Large and complex problems usually require bigger populations and costly fitness evaluations. Partitioning the computational load across n-number of processors would reduce overall processing time. Typically, each subpopulation or each individual genotype can be separately processed in parallel. Parallel GAs can be classified into four categories: global parallelization, coarse- and fine-grained algorithms, and hybrid approaches (Cantu-Paz, 1995). Global parallelized GAs are relatively easy to implement. In global parallelization, genotype evaluation and selection operator application are accomplished in parallel. Coarse-grained parallel GAs divide the population into isolated subpopulations and use a migration operator to exchange individuals between subpopulations. Fine-grained parallel GAs divide the populations even smaller, using a large parallel system to process each tiny population. Finally, the hybrid approach uses a combination of the first three. It seems that parallelization is not a difficult task; however, studies are needed to focus on the particular aspects of these systems (Cantu-Paz, 1995). Genetic algorithms are described as weak methods. These algorithms do not need to know anything about the problem domain to generate solutions. They can easily be applied to a variety of problems. Weak methods, though, rarely find the optimal solution to a problem. GAs are not guaranteed to find the optimal solution in a given problem. They do, however, find a good solution in the time allotted. Given enough time, they could find an optimal solution, but then so could more traditional methods. And, we rarely have that much time to allocate for problem-solving. 3. TECHNIQUES AND APPLICATIONSGAs can be used in unison with expert systems. Most hybrid systems combine other AI techniques. Two basic ways to use GAs and expert systems together is to either:
Attitude Determination. Recent work has been done in the area of attitude determination using the global positioning system (GPS). This approach uses an adaptive scheme that employs a fuzzy expert system to improve a Kalman filter's performance (Ghisleni and Marradi, 1996). GAs are used in this approach to design the membership functions of the fuzzy rules. So far, this system has provided good results in comparison to traditional approaches. Production Planning. Researchers have applied GAs and expert systems using the first approach (Hamada, Baba, Sato, and Yufu, 1995). Their problem involved creating the best schedule for steelmaking processes. They created a system that greatly reduced the workload of the human operators and produced efficient schedules. Their approach was to divide the problem into subproblems, and developed optimization software that consists of:
The scheduling problem consisted of how to create the most efficient charge (pot of molten steel) groups. There are numerous constraints that the scheduler must follow to use the furnaces most efficiently. For example, some charges could not follow others due to temperature changes. The group used a procedural method to create the charge groups, an expert system to generate coarse schedules, and a GA to optimize the coarse solutions into the best solution (Hamada et al., 1995, p. 65). They compared their schedules with manmade schedules, and found that the GA generated schedules were superior in quality and took less time to prepare. A schedule is created by first using the procedural approach to form charge groups, taking into account constraints and costs. The expert system then orders the charge groups as best as possible to meet production constraints. The researchers could not extract enough knowledge from the human operators to create rules that could generate a good schedule (Hamada et al., 1995, p. 65). The GA in this case uses chromosomes (genotypes) that consist of three blocks, with each block representing a category. Each block is a sequence of charge groups belonging to one of these categories. Decoding the chromosome results in a schedule. Both crossover and mutation operators are used here. The roulette-wheel selection operator is used to perform crossover, and is implemented in such a way so that invalid schedules are avoided. The mutation operator uses two operations: the first switches two genes at random, and the second selects a random gene and inserts it into another position (Hamada et al., 1995, p. 65). Controller Design. GAs have also been used to find the optimal design for a fuzzy logic controller (Kim and Zeigler, 1996). In this case, the fuzzy logic controller is a working prototype of a plant for producing oxygen from a Martian atmosphere. They developed Hierarchical Distributed Genetic Algorithms (HDGA), which supports a multiresolutional search paradigm that finds a design that can satisfy stringent operational specifications. HDGA can dynamically create clusters that are used for problem-solving. In this case, HDGA optimizes the fuzzy rules used by the controller by manipulating their membership functions. Optimization resulted in a fuzzy controller design that maintained an error rate of ±2%, comfortably under the maximum tolerance of ±5% (Kim et al., 1996). HDGA consists of multilevel clusters; each cluster consists of a controller and agents that solve an abstracted version of the given problem (Kim et al., 1996, p. 77). The controller, not to be confused with the fuzzy logic controller, is a small expert system that controls execution of the agent GAs. This expert system makes decisions based on the information gathered by the agent GAs. HDGA uses a binary encoding scheme for the chromosomes, and has the ability to vary search resolutions.
|
![]() |
|
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. |