NetLogo Models Library:
Sample Models/Computer Science

(back to the library)

Simple Genetic Algorithm

If you download the NetLogo application, this model is included. You can also Try running it in NetLogo Web

WHAT IS IT?

This model demonstrates the use of a genetic algorithm on a very simple problem. Genetic algorithms (GAs) are a biologically-inspired computer science technique that combine notions from Mendelian genetics and Darwinian evolution to search for good solutions to problems (including difficult problems). The GA works by generating a random population of solutions to a problem, evaluating those solutions and then using cloning, recombination and mutation to create new solutions to the problem.

In this model we use the simple "ALL-ONES" problem to demonstrate how this is possible. We use such a simple problem in this model in order to highlight the solution technique only. The idea of the "ALL-ONES" problem is to find a string of bits (that is, a sequence of just ones and zeros) that contains all ones, and no zeros. Thus the string that best solves this problem is "111111...111".

HOW IT WORKS

The genetic algorithm is composed of the following steps.

1) A population of random solutions is created. Each solution consists of a string of randomly mixed "1"s and "0"s.

2) Each solution is evaluated on the basis of how well it solves the problem. This measure of the "goodness" of the solution is called its "fitness". In this model, our goal is simply to find a solution that consists of all "1"s. (In real-world applications of the genetic algorithm, the goals are much more complex, but the solutions are still usually encoded as binary strings.)

3) A new generation of solutions is created from the old generation, where solutions that have a higher fitness scores are more likely to be chosen as "parent" solutions than those that have low fitness scores.

A) The selection method used in this model is called "tournament selection", with a tournament size of 3. This means that 3 solutions are drawn randomly from the old generation, and the one with the highest fitness is chosen to become a parent.

B) Either one or two parents are chosen to create children. With one parent, the child is a clone or copy of the parent. With two parents, the process is the digital analog of sexual recombination -- the two children inherit part of their genetic material from one parent and part from the other.

C) There is also a chance that mutation will occur, and some of the child's bits will be changed from "1"s to "0"s, or vice versa.

4) Steps 2 and 3 above are repeated until a solution is found that successfully solves the problem.

HOW TO USE IT

Press the SETUP button to create an initial random population of solutions.

Press the STEP button to have one new generation created from the old generation.

Press the GO button to have the genetic algorithm run until a solution has been found.

The best solution found in each generation is displayed in the VIEW. Each white column represents a "1"-bit and each black column represents a "0"-bit.

=== Parameters ===

The POPULATION-SIZE slider controls the number of solutions that are present in each generation.

The CROSSOVER-RATE slider controls what percent of each new generation is created through sexual reproduction (recombination or crossover between two parents' genetic material), and what percent (100 - CROSSOVER-RATE) is created through asexual reproduction (cloning of one parent's genetic material).

The MUTATION-RATE slider controls the percent chance of mutation. This chance applies to each position in the string of bits of a new individual. For instance, if the string is 100 bits long, and the mutation-rate is set at 1%, then on average one bit will be changed during the creation of each new individual.

The PLOT-DIVERSITY? switch controls whether the amount of diversity within the population of solutions is plotted each generation, shown in the "Diversity Plot". Turning off PLOT-DIVERSITY? significantly increases the speed of the model because calculating diversity requires a lot of computation.

The "Fitness Plot" is used to show the best, average, and worst fitness values of the solutions at each generation.

THINGS TO NOTICE

Step through the model slowly, and look at the visual representation of the best solution found in each generation, displayed in the VIEW. How often does the best solution in Generation X+1 appear to be the offspring of the best solution in Generation X?

As the fitness in the population increases, the diversity decreases. Why is this?

THINGS TO TRY

Explore the effects of larger or smaller population sizes on the number of generations it takes to solve the problem completely. What happens if you measure the amount of time (in seconds) that it takes to solve the problem completely?

How does asexual reproduction compare to sexual reproduction for solving this problem? (What if CLONING-RATE is 100, or CLONING-RATE is 0?)

How much mutation is beneficial for the genetic algorithm? Can the genetic algorithm find a perfect solution if there is MUTATION-RATE is 0? What about if MUTATION-RATE is 10.0? Can you find an optimal MUTATION-RATE?

EXTENDING THE MODEL

Many variations on this simple genetic algorithm exist. For example, some genetic algorithms include "elitism". In this case, the best X% of solutions from the old generation are always copied directly into the new generation. Modify this model so that it uses elitism.

Another type of selection for reproduction that is sometimes used in genetic algorithms is called "roulette selection". In this case, you may imagine each solution in the population being assigned a wedge of a large roulette wheel. The size of the wedge is determined by dividing the fitness of each solution by the sum of the fitnesses of all solutions in the population. Thus, the probability of selecting any given solution to reproduce is directly proportional to its fitness. Try implementing this type of selection, and compare its performance to the "tournament selection" method that is currently used in this model.

As noted above, the "ALL-ONES" problem is a toy problem that is not very interesting in its own right. A natural extension of this model is to use the genetic algorithm to solve a problem that is significantly more interesting. Fortunately, you can change the problem that the genetic algorithm is solving by only modifying one thing, the "fitness function", which evaluates how good a given string of bits is at solving whatever problem you are trying to solve. For example, you could evolve rules for how a turtle should move, in order to maximize its food collection as it travels through the world. To do so, you might change the ga-calculate-fitness procedure to run a little simulation where a turtle moves in the world (according to some rules that are defined by the string of "1"s and "0"s), count how much food the turtle collects, and then set the fitness accordingly.

NETLOGO FEATURES

Note that NetLogo's powerful ability to work with agentsets makes it very easy to code the "tournament selection" used in this model. The following code is sufficient:

max-one-of (n-of 3 old-generation) [ga-fitness]

RELATED MODELS

Echo is another model that is inspired by the work of John H. Holland. It examines issues of evolutionary fitness and natural selection.

There are several NetLogo models that examine principles of evolution from a more biological standpoint, including Altruism, Bug Hunt Camouflage, Cooperation, Mimicry, Peppered Moths, as well as the set of Genetic Drift models.

Sunflower Biomorph uses an artistic form of simulated evolution, driven by aesthetic choices made by the user.

CREDITS AND REFERENCES

This model is based off of work by John H. Holland, who is widely regarded as the father of the genetic algorithms. See Holland's book "Adaptation in Natural and Artificial Systems", 1992, MIT Press.

Additional information about genetic algorithms is available from a plethora of sources online.

HOW TO CITE

If you mention this model or the NetLogo software in a publication, we ask that you include the citations below.

For the model itself:

• Stonedahl, F. and Wilensky, U. (2008). NetLogo Simple Genetic Algorithm model. http://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

Please cite the NetLogo software as:

• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

Copyright 2008 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

(back to the NetLogo Models Library)