The Nature of Niching: Genetic Algorithms and the Evolution of Optimal, Cooperative Populations


Abstract

Genetic algorithms (GAs) with fitness sharing have been analyzed and succesfully applied to problems in search and optimization, while GAs using varios types of resource sharing have been incorporated into classifiers, immune system models, artificial ecologies, artificial economies, etc. Both types of sharing are based on the same observation of nature: dividing a finite resource among competing organisms limits the size of populations dependent on that resource. If multiple resources are involved, each resource can be considered a niche, and each subpopulation exploiting a niche can be considered a species. By treating population slots as a finite resource, we obtain the traditional, fixed-size population simple GA. By further treating the figure of merit (i.e. the function to be optimized) as a limited resource, we obtain fitness sharing. If our problem domain manifests explicit resources, such as rewards for correct classification of examples, we can enforce resource sharing. Both fitness and resource sharing have been studied separately, and usually under the assumption of non-overlapping niches, or perfect sharing. Little effort has been made to understand the more complicated situation of niche overlap. Yet the resolution of niche overlap is critical to successful, useful niching. Non-overlapping niches can be covered by non-competing species, while heavily overlapped niches induce competition between species in which only the best will survive to represent the overlapping resources. Somewhere in between the two extremes of overlap must lie critical boundary between cooperation (all species survive) and competition (one dominant species survives). We seek this boundary for the simplest case of niche overlap: two niches. We first define the general mechanism of sharing, and investigate where sharing-induced-niches fits into the larger frameworks of context-dependent function optimization, natural ecologies, and models of cooperation and competition. We then map fitness sharing to resource sharing, and show that they are identical when there is no niche overlap (i.e. perfect sharing). We go on to analyze the three cases: perfect sharing, fitness sharing (with overlap) and resource sharing (with overlap). We find that even under severe selective pressure with high degrees of niche overlap, a stable equilibrium population is quickly found and indefinitely maintained, a population consisting of diverse species covering the best niches. We find that maintenance of the sharing equilibrium degrades gradually as niche overlap and fitness discrepancies increase. We create a control map for the two-niche case, plotting the boundary between surviving niche pairs (cooperation) and untenable niche pairs (competition). Controlling this boundary will allow us to use sharing to evolve the types of cooperation and competition appropiate to the problem at hand. We extend the above analysis by looking at some aspects of the general case of multiple overlapping niches. We discover that calculating the equilibrium point for three or more niches under resource sharing can be computationally expensive, as evidenced by the difficulty that GA selection has in reaching it. We present some evidence that equilibrium can thus represent solutions to hard problems, and that selection plus sharing might be a computationally intensive yet efficient algorithm (even without the exploration operators of recombination and mutation). In addition to analyzing the existence, resilience, nature, and meaning of sharing equilibrium, we also explore its utility. We apply various sharing methods to specific problems from three domains: function optimization (search), multi-objective optimization, and lay-out/packing problems. We find that sharing is a robust, flexible, and extensible technique, whose simplicity and similarity with nature give us further confidence in its general applicability. We hope our results ameliorate some of the over-reaching criticisms frequently used to dismiss sharing as a niching method, by demostrating that sharing is not computationally expensive, that its performance degrades gracefully with decreasing a priori knowledge of niche distribution, and that simple and intuitive techniques can be found to extend sharing's domain of utility.