Genetic Algorithms


Overview of Genetic Algorithms

Genetic Algorithms simulate nature on a very abstract level to get solutions for sophisticated problems. The simulation corresponds to the current understanding of genetic processes. Especially promising is the usage of evolutionary genetic algorithms for problems where no constructive solution algorithms are known or where they would just be far too complex to implement. Genetic algorithms are searching through an arbitrary search space both for exploration and exploitation purpose.

With evolutionary genetic algorithms problems can be solved by checking whether one of the trial solutions (in the abstract population of data) already is a good solution of the problem. It checks whether a member (called an abstract chromosome) fulfils all criteria required for a good solution of the problem. To create such a solution, trial chromosomes will be genetically recombined to form new chromosomes that are new members of the abstract population. Starting with some random chromosomes, finally one solution will be found - if our basic assumption that the evolution solves our problem in an efficient way is true.

Demonstration with the Knapsack problem

Knapsack problem: Now let's see what happens if we have these items for the Knapsack problem:
Number, weight and value of all items
# 1 2 3 4 5 6 7 8 9 10 11 12 13
weight 3 3 3 3 3 4 4 4 7 7 8 8 9
value 4 4 4 4 4 5 5 5 10 10 11 11 13
In the following textbox you will see the solutions generated for the Knapsack problem:
If the applet does not show in your browser or appletviewer, you can also start
  java Knapsack
directly.
Copyright © André Platzer |