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

Print

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

This document is currently not available here.

Share

COinS