Genetic Algorithms, Orthogonal Arrays and Diploid Chromosomes

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.

Name dc:type.qualificationname

Doctoral Thesis

Level dc:type.qualificationlevel

Student thesis

Year dc:date.issued

2002

Author dc:creator

• Lee, Shane

• Genetic algorithm
• Search
• local search
• diploid
• real encoded
• orthogonal array

Language dc:language

eng

Identifier

oai:pure.atira.dk:studenttheses/c72580ff-5ede-446f-872e-dd82ae82c4d3

OAI identifier oai:identifier

oai:pure.atira.dk:studenttheses/c72580ff-5ede-446f-872e-dd82ae82c4d3