Case Injected Genetic Algorithms

  How do we combine a genetic algorithm with case-based memory? Our first approach worked as follows. When confronted with a (new) problem, the CBR module looks in its case base for similar problems and their associated solutions. Note that case-based reasoning research has shown that defining a problem similarity metric is non-trivial [Leake1996]. If the system finds any similar problems, a small number of their solutions get injected into the initial population of the genetic algorithm. The rest of the population is initialized randomly (to maintain diversity) and the GA searches from this combined population. This works well if we have a good measure of problem similarity.

However, if we assume that similar solutions must have come from similar problems, CIGAR can operate on the basis of solution similarity and avoid the issue of defining problem similarity metrics. In this scenario, shown in Figure 1, we periodically inject a small number of solutions similar to the current best member (candidate solution) of the GA population into the current population, replacing the worst members. We call this the ``closest to the best'' strategy, one of several possible injection strategies. The GA continues searching with this combined population.

  

Figure: Conceptual view of CIGAR.

What are cases and how do we save them to the case-base? During GA search, whenever the fitness of the best individual in the population increases, the new best individual is stored in the case-base. A case is a member of the population (a candidate solution) together with ancillary information including fitness, the generation this case was generated, and its parents [Louis, McGraw, & Wyckoff1993]. Reusing old solutions has been a traditional performance improvement procedure. Our work differs in that 1) we attack a set of tasks, 2) store and reuse intermediate candidate solutions, and 3) do not depend on the existence of a problem similarity metric avoiding indexing problems common to case-based systems.

What happens if our similarity measure is noisy and/or leads to unsuitable retrieved solutions? By definition, unsuitable solutions will have low fitness and will quickly be eliminated from the GA's population. CIGAR may suffer from a slight performance hit but will not break or fail - the genetic search component will continue making progress towards a solution. CIGAR is robust. As noted earlier, we can choose schemes other than injecting the closest to the best; furthest from the worst and probabilistic versions of both have proven effective.