Extending the genetic algorithm paradigm: A meta-operator to effect dynamic structural changes

• Main Author: Tan, Wilfred G.
• Format: text
• Language: English
• Published: Animo Repository 1998
• Subjects: Computer algorithms; Simulation method Operator theory; Biochemistry, Biophysics, and Structural Biology
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/2010
• Institution: De La Salle University

The Simple Genetic Algorithm (SGA) paradigm works using the three basic operators: Selection, Mutation and Crossover. Using these three operators, the GA converges towards the optimal point. However, in a situation where all organisms fail, the GA will logically not reach the optimal point. Using Markov chain analysis, the study introduces the notion of a catastrophe, and enumerates two types of catastrophe. Catastrophes can be either an environmental disaster or a genetic failure. In both cases where a catastrophe occurs the SGA is shown to be unable to converge toward the optimal point. The study also introduces a new meta operator REX which extends the SGA paradigm to enable it to reach the optimal point. Using Markov chain analysis, the study shows that the SGA indeed converges towards the optimal point if it is modified using REX and that it never converges if it is left unmodified. REX can either be used as a Recycle operator, or as an EXtension operator. Recycling means inverting bits in the chromosome to find a defective gene. In this study, Extension means enlarging the scope of the gene such that the search space of the SGA is expanded. Simulation and experiments solving the San Mateo Trail problem are carried out using the Sunderland Genetic Algorithm Simulator (SUGAL) to validate the ideas presented in the theoretical sections.