A chromosome-repairing genetic algorithm (CRGA) capable of finding exact solutions.

摘要

A Chromosome Repairing Genetic Algorithm (CRGA) that finds exact solutions is developed and discussed. Unlike traditional Genetic Algorithms, this algorithm does not merely find an approximate answer, but instead finds exact answers for the case of discrete search spaces. It is a predominately parallel algorithm, and exhibits a speed-to-convergence advantage relative to a purely random search. It also features a serial form of niching for overcoming genetic drift, thereby reducing the computational burden on the host computer as compared to maintaining two separate, yet simultaneous, populations.; Fundamentally, the CRGA works by repairing chromosomes found at the point of genetic drift of the chromosome population through using interpolation. It is demonstrated against the Knight's Tour problem, which consists of placing a knight on a chessboard, and traveling to each and every square but once, using the rules of chess. The choice of interpolation used for this particular problem is Euler Interpolation, by which a damaged chromosome, representing a near-solution, is repaired and transformed into an exact solution.; The CRGA overcomes a typical limiting performance for GAs in not finding an exact solution in a reasonable amount of time, even after producing good solutions relatively quickly. It therefore extends present GA capabilities. It provides a robust and powerful replacement for both traditional GAs and Simulated Annealing Algorithms (SAAs). The basic concepts also are applicable to Genetic Programming (GP) problems.; This dissertation also establishes the necessity of genetic mutations (birth defects) for any mortal species, simulated or otherwise, for maintaining genetic diversity.