NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses extensions.)

## 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) There are two variants of the models to create the new generation of solutions:

- **Generational model**: 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.

- **Steady-State model**: Two fathers from the population are chosen and combinated to create a pair of children. The best of them will replace one solution of the actual population (a few individuals are replaced each state).

A) There are two selection methods in this model:

- **Tournament selection**: with a tournament size of 3 by default.
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.

- **Roulette selection**: also known as roulette wheel selection. The fitness
level is used to associate a probability of selection with each individual
chromosome

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. There are two variants:

- **One Point crossover**: a cut (point) is selected on the first father or chromosome. All data beyond this point will be exchanged between the two fathers.

- **Double Point crossover**: Instead of cutting the parental chromosomes at a single point as in the previous case, two cuts are randomly chosed. Both parents solutions are combined to create the new solutions.

- **Uniform crossover**: Both parents chromosomes are recombined choosing a random list of gens of one of them and the rest of them from the another chromosome.

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 CROSSOVER-TYPE? selector controls which type of crossover are going to use the genetic algotihm: Uniform crossover or Segment crossover.

The SELECTION-TYPE? selector controls which type of selection method we prefer to select the fathers: Tournament selection or roulette selection.

The N-TOURNAMENT-SELECTION slider controls how many possible fathers are going to be involved when tournament selection method is selected.

The MODEL-TYPE? selector controls which schema (way to generate next population) is going to be used by our Genetic Algorithm.

The ELITISM? switch controls if the most fit handful of individuals are guaranteed a place in the next generation or not.

The REPLACEMENT-NUMBER slider controls how many chromosomes are going to be replaced when we are using steady-state model.

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

## 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.

This model is a extension of:

* 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.