My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
BasicSummary  
Updated Aug 8, 2008 by jonathan...@gmail.com

Purpose of Evolving Algorithms

This project aims to find the limits and requirements to evolve complicated algorithms. Software applications such as Avida are limited to only being able to find logic functions. Evolving Algorithms aims to find the necessary mechanics to evolve higher-order algorithms involving loops and other chaotic structures. The goal is to quantify or at least qualitatively describe the necessary machinery, starting points, and modes of fitness to evolve various types of functions.

This project is currently in its infant stages. We have gotten some minor programs to work but have not gotten to the "evolving" stage yet, though that should happen soon.

Instruction Set

The goal is to have a basic state machine with a pluggable instruction set. The machine consists of:

  • virtually infinite registers (you can restrict how many registers you will use in your evolution defaulted at 5, but there is no explicit limit). Seeing how a change in the number of registers affects the evolved algorithms will be one of our tests.
  • virtually infinite stacks of virtually infinite length (like the registers, we can restrict these evolutionarily. It currently defaults to 5.)
  • a marker-based jump system. To prevent insertions from blowing up the algorithm, we are using markers for jumps. Also, the markers don't have to match exactly, they just have to be in a user-defined closeness range.

The instruction set was inspired by Avida, but differs from it in several important ways:

  • We're not placing restrictions on anything - number of registers, number of stacks, or which operations operate on which thing
  • We're allowing parameters to our instructions - Avida is focused entirely on self-contained instructions
  • There is no divide or copy instructions - the built-in mutation system is entirely responsible for copying the algorithm and mutating it
  • There is no input/output - the input/output register(s) will be determined by convention, and the halting of the program will signal that the result is ready

Comparison to Avida

Overall, we feel that this system is much better for general usage than Avida. Avida tries to model "digital life" and does so very poorly. As a model for life, Avida does not do well. As a model for algorithmic computation - Avida does not do well (it is Turing-complete, but its constructs are difficult to use except for the precoded and very silly copy/divide cycle). As a model for testing the limits of evolutionary computation - Avida does not do well.

In fact, in Avida, you can only even test for logic functions!!! A real function is essentially untestable and therefore unevolvable in Avida! It is amazing that this "Digial Life" application does not even potentially have the power to evolve a function that requires a loop!

Anyway, enough about the problems with Avida. Our goal is to devise a research platform to identify the limits and requirements of evolutionary algorithms.

Research Directions

Some possible research directions:

  • see what types of complexity limit evolvability
  • see what types of instructions can accomodate previously limited evolvability
  • attempt to discover generalizable rules for evolvability
  • see how stochasticity can affect evolution (i.e. make jump targets stochastically choosable and randomized functions)
  • identify the requirements for an algorithm to transition from solving one set of problems to another
  • identify the degree of specificity required to produce a better algorithm

Not Covered

PLEASE NOTE - this platform DOES NOT INTEND to model cost theory (another area which Avida tries and fails to model). For an application to model cost theory, see:

http://www.mendelsaccountant.info/

Powered by Google Project Hosting