Extending the genetic algorithm paradigm: A meta-operator to effect dynamic structural changes
Date of Publication
1998
Document Type
Master's Thesis
Degree Name
Master of Science in Computer Science
Subject Categories
Biochemistry, Biophysics, and Structural Biology
College
College of Computer Studies
Department/Unit
Computer Science
Thesis Adviser
Arnulfo P. Azcarraga
Defense Panel Chair
Maria Alvarez
Defense Panel Member
Kai Shan Fernandez
Philip Chan
Abstract/Summary
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.
Abstract Format
html
Language
English
Format
Accession Number
TG02909
Shelf Location
Archives, The Learning Commons, 12F Henry Sy Sr. Hall
Physical Description
284 p., 28 cm.
Keywords
Computer algorithms; Simulation method Operator theory
Recommended Citation
Tan, W. G. (1998). Extending the genetic algorithm paradigm: A meta-operator to effect dynamic structural changes. Retrieved from https://animorepository.dlsu.edu.ph/etd_masteral/2010