Extending the genetic algorithm paradigm: A meta-operator to effect dynamic structural changes
Date of Publication
Master of Science in Computer Science
Biochemistry, Biophysics, and Structural Biology
College of Computer Studies
Arnulfo P. Azcarraga
Defense Panel Chair
Defense Panel Member
Kai Shan Fernandez
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.
Archives, The Learning Commons, 12F Henry Sy Sr. Hall
284 p., 28 cm.
Computer algorithms; Simulation method Operator theory
Tan, W. (1998). Extending the genetic algorithm paradigm: A meta-operator to effect dynamic structural changes. Retrieved from https://animorepository.dlsu.edu.ph/etd_masteral/2010