Based on the principles of Darwinian natural selection, genetic algorithms are a well established search and optimisation technique. They can be said to 'evolve' solutions to complex problems. However, genetic algorithms can be slow to use, as they require a lot of computer resources to function. Given the restrictions of computer resources they cannot guarantee to find a required global optimum in a reasonable time. This thesis presents new techniques and operators, which can improve the efficacy and efficiency of genetic algorithms. The operators exploit the orthogonal arrays of Taguchi method. An operator that uses orthogonal arrays to create initial populations of genetic algorithms was developed. For binary encoded genetic algorithms it was found to be unreliable but is advantageous if it is used in combination with random initialisation when multiple runs are practical. The initialisation operator was found to be successful with floating-point encoded genetic algorithms. From the initialisation research the 'refocusing' and 'roving hypercube' operators were developed. The refocusing operator redraws the population of a genetic algorithm after a predetermined number of generations. Results showed it to be an effective operator, improving search performance in most cases. The roving hypercube operator was found to be a very effective pseudo-mutation operator that replaces a chromosome with a fitter individual after performing a local search. A search algorithm, which uses only the refocusing and roving hypercube operators, was developed. When compared with a standard genetic algorithm it produces better result having sampled fewer places in a problem space. Aside from the orthogonal array contributions a novel diploid chromosomes genetic algorithm that searches for robust optima was developed. Tests showed that it found the required optimum 100% of the time. A set of new measurement techniques suitable for presenting the results of the experiments performed and novel crossover and mutation operators for use with floating-point encoded genetic algorithms are introduced. This thesis presents a valuable and useful set of operators for use with genetic algorithms.
Date of Award | Nov 2002 |
---|
Original language | English |
---|
Supervisor | Hefin Rowlands (Supervisor) |
---|
- Genetic algorithm
- Search
- local search
- diploid
- real encoded
- orthogonal array
Genetic Algorithms, Orthogonal Arrays and Diploid Chromosomes
Lee, S. (Author). Nov 2002
Student thesis: Doctoral Thesis