Mahfoud S.W. Niching Methods for Genetic Algorithms

Dissertation. — University of Illinois, 1995. — 264 p.Niching methods extend genetic algorithms to domains that require the location and maintenance of multiple solutions. Such domains include classification and machine learning, multimodal function optimization, multiobjective function optimization, and simulation of complex and adaptive systems.
This study presents a comprehensive treatment of niching methods and the related topic of population diversity. Its purpose is to analyze existing niching methods and to design improved niching methods. To achieve this purpose, it first develops a general framework for the modeling of niching methods, and then applies this framework to construct models of individual niching methods, specifically crowding and sharing methods.
Using a constructed model of crowding, this study determines why crowding methods over the last two decades have not made effective niching methods. A series of tests and design modifications results in the development of a highly effective form of crowding, called deterministic crowding. Further analysis of deterministic crowding focuses upon the distribution of population elements among niches, that arises from the combination of crossover and replacement selection. Interactions among niches are isolated and explained. The concept of crossover hillclimbing is introduced.
Using constructed models of fitness sharing, this study derives lower bounds on the population size required to maintain, with probability γ a fixed number of desired niches. It also derives expressions for the expected time to disappearance of a desired niche, and relates disappearance time to population size. Models are presented of sharing under selection, and sharing under both selection and crossover. Some models assume that all niches are equivalent with respect to fitness. Others allow niches to differ with respect to fitness.
Focusing on the differences between parallel and sequential niching methods, this study compares and further examines four niching methods: crowding, sharing, sequential niching, and parallel hillclimbing. The four niching methods undergo rigorous testing on optimization and classification problems of increasing difficulty, a new niching-based technique is introduced that extends genetic algorithms to classification problems.Genetic Algorithms
Diversity
Niching Methods
Models of Niching Methods
Crowding: Selection
Crowding: Selection Plus Crossover
Sharing: Selection
Sharing: Selection Plus Crossover
Parallel Versus Sequential Niching