A Genetic Algorithm

Genetic algorithms (GAs) are stochastic, parallel search algorithms based on the mechanics of natural selection, the process of evolution [4, 3]. GAs were designed to efficiently search large, non-linear, poorly-understood search spaces where expert knowledge is scarce or difficult to encode and where traditional optimization techniques fail. They are flexible and robust, exhibiting the adaptiveness of biological systems. As such, GAs appear well-suited for searching the large, poorly-understood spaces that arise in design problems; specifically designing control strategies for mobile robots.

The CHC Genetic Algorithm

CHC, the non-traditional genetic algorithm used in this paper, differs from traditional GAs in a number of ways [2]:

1. For a population of size N, it guarantees the best individuals found so far always survive by putting the children and parents together and selecting the best N individuals for further processing. In a traditional GA, the parent population does not survive to the next generation.
2. To avoid premature convergence, two similar individuals separated by a small Hamming distance (this threshold is set by the user) are not allowed to mate.
3. During crossover, two parents exchange exactly oned- half of their randomly selected non-matching bits.
4. Mutation isn't needed during normal processing.
5. Instead, an external mutation operator re-initializes the population when the population has converged or search has stagnated.

The CHC genetic algorithm generally does well with small populations [2]. Limited resources and the computational cost of the simulations led to our use of small populations and selection of the CHC genetic algorithm for this work.

Case-Based Reasoning

Case-based reasoning (CBR) is based on the idea that reasoning and explanation can best be done with reference to prior experience, stored in memory as cases [12]. When confronted with a problem to solve, a case-based reasoner extracts the most similar case in memory and uses information from the retrieved case and any available domain information to tackle the current problem. This paper uses the basic tenet of CBR -- the idea of organizing information based on ``similarity'' -- to help augment genetic algorithm search.