Plenary Lecture 12 A Critical Review of the Mathematical Robustness of Genetic Algorithms in Optimization Problems

摘要

Genetic Algorithms (GAs) have been shown to be particularly effective in many optimization problems due to their ability to search in a continuous space without getting trapped in local optima while exploiting the entire search space. Some recent research works however, show that the mathematical theory of GAs are not fully understood and its validity may be questioned. This may affect the quality and reliability of solutions obtained from the GA optimization process. In addition, sensitivity of critical parameters in GAs may also affect the quality of solution. If GAs are applied properly, similar solutions should be expected at each replication, regardless of where the search process starts. Some of the critical parameters affecting search performance include the number of genetic operators, the number of decision variables, the parameter for selective pressure, and the parameter for non-uniform mutation. In this presentation I provide a critical review of the mathematical foundation of GAs and also show a sensitivity analysis of the critical parameters that may affect the quality of solutions. Attention is directed specifically to the schema theory, which are considered to be the building blocks for GA operation. Using my previous collaborative work with Dr. David Lovell of the University of Maryland, College Park I show a hard upper bound on the number of matching schemata in binary and real coded GAs for a population of a given size and string length. A loose upper bound is commonly reported in the published literature, but does not take into account redundancies that are inevitable for certain values of the population size. In this ppresentation, this over-counting is rectified. A special case when the string length is small compared to the population size is shown to have a particularly elegant solution. In order to investigate the effects of critical parameters when adopting GAs I show a sensitivity analysis using previous collaborative work with Dr. Eungcheol Kim of the University of Incheon, South Korea, which shows that quality of solutions depend on their proximity of convergence from different starting points. Finally, we investigate the improvement in solution quality with the derived hard upper bound.