2 Week Project on Genetic Algorithms

Genetic Algorithms are a subset of Evolutionary Algorithms, which are a subset of Evolutionary Computing, which is a subset of Artificial Intelligence.  Essentially, Genetic Algorithms are a type of search used to find solutions, or the best result, to optimization problems, such as the backpack and salesman problems.  As its name suggests, these styles of algorithms arrive at their results by using a process that mirrors biological evolution–the members of a population mate, creating a new generation with the better characteristics of the current generation, as well possibly mutating some aspects of the new members.

The structure of Genetic Algorithms is often as follows:

1) Define target and terminators – The target is most often the goal the algorithm is attempting to achieve, such as a particular string, calculation, or result.  Terminators are failsafes, such as a maximum number of population iterations, to assure  the program does not run indefinitely, or derail from the problem at hand.

2) Initialize population – The importance of this step is in choosing the population size most useful for the problem at hand.  In many cases, a larger population size is not always desirable, as it can greatly increase the resources the algorithm requires to run or complete.  Conversely, having too small a population can increase the time required for the data within the algorithm to evolve.

3) Evaluate fitness – This step is often very important in getting ready for the mating stage.  Essentially, this steps rates each member of the population based on some sort of criteria.  For example, in attempting to generate a specific string, each char within the member string is rated based on how close it is to the chars in the target string.  Depending on the goals of the algorithm, the members of the population might be sorted based on their fitness in this stage.

4) Mate (Elitism and Mutation) – This step mates two members of the population together, and produces two children.  Mating is made up of four stages:

  1. Selection – The selection stage determines which two members to mate together.  Examples of how to determine these pairs include: Roulette–members with a higher fitness have a greater chance of being mated–Rank–members are ranked and mated together based on their fitness–Random–randomly select to members that have not yet mated–Steady–the top X percent of the population is mated together–and Elitism–where the top X percent of the population is directly copied into the new generation.
  2. Encoding – The encoding stage determines the type of, and how, data is transferred to children.  Examples include: Binary–each piece of data is represented as a bit–Permutation–data is a sequence of numbers or characters–Value–data is values of various types–and Tree–data is a part of a tree of data and functions.  This type of encoding is often used to evolve functions, rather than data.
  3. Crossover – The crossover stage determines how the parent’s data is presented in its children.  As examples, Single and Multi encoding work by selecting one or multiple, respectively, points where everything before this point will be parent A’s genetic data, and everything after will be parent B’s genetic data.  Other examples include Uniform–where genetic data is randomly selected from parents–and Arithmetic–where a predefined function determines what data is copied from what parent.
  4. Mutation – This is an optional stage.  As in biological evolution, this stage gives new members of a population a random chance to mutate some of their genetic data, either positively or negatively.

6) Assign new population – This step very simply sees the new generation overriding the current generation.  Upon completion the process returns to stage 3, and repeats until either the target or terminator is met.

 

Resources and Helpful Links:

http://www.obitko.com/tutorials/genetic-algorithms/index.php

http://www.generation5.org/content/2003/gahelloworld.asp

http://www.ai-junkie.com/ga/intro/gat3.html

http://www.dreamincode.net/forums/topic/230020-evolutionary-algorithms-genetic-algorithms/

http://en.wikipedia.org/wiki/Genetic_algorithms

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s