Notes on Implementing Genetic Algorithms

October 18, 2009 Ideas 0 Comments

XIAS (cross-integrated algorithm system) supports the following algorithm types so far:

  • Fractal
  • Grammar
  • L-System

The next natural extension of XIAS is an implementation of genetic algorithms.  I have a bit of experience with genetic algorithms from designing the EvoSpeak engine, which basically combined stochastics and genetic algorithms to evolve towards good-sounding melodies.

In keeping with the overall theme of the XIAS project, the designs for this genetic algorithm implementation focus on portability and ease-of-use.  As such, the system may seem a little oversimplified.  Only time will tell whether it will suffice for algorithmic composition needs or whether I will need to extend the features of the genetic algorithms.  For now, here are some notes that I've brainstormed for the implementation of this new system.

Data Structure of the GA Engine

  • Engine
    • Alleles (effectively the algorithm's domain; string)
    • Cumulative point distribution (count; integer)
  • Individuals
    • Data String (genetic data; string)
    • Points (count; integer)

GA Engine Operation

  • Create m individuals with random alleles
  • Rate each of the individuals
    • Pass data string to transform function
    • Feed transformed output to fitness evaluation function
    • Distribute points according to fitness performance
  • Breed the top n individuals according to point distribution with each other to create m new individuals
  • Repeat with the new generation of individuals

Mutation in the GA Engine

  • Deterministic Approach
    • Create a function that takes two parent alleles and returns a third allele different from both (think cross product)
    • Run the function on every qth allele
  • Nondeterministic Approach
    • Replace a child allele with a random allele with a given frequency

Quick Summary of GA Engine Implementation

  • Randomize Individuals
  • Rate
    • Functional Transformation
    • Fitness Evaluation
    • Point Allocation
  • Reproduce
    • Allele Combination
    • Allele Mutation
  • Repeat

The only real problem left to solve is concerning reproduction.  How do we choose which individuals to combine with which individuals in order to produce a population of exactly m members, given that we want the children to have the best possible combinations of genes based on the point distribution of the parents?