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:
How to load items on a trolley that can at most carry a certain maximum
weight, if I also want to get the most valuable items with me?
Assuming we have two items weighted 3 and valued 4 and one item weighted
5 and valued 7, and we have a trolley that can carry no more than 7 units
of weight. Our Genetic Algorithm should find out (via clever trial) that
we should take the two items weighted 3, with a total weight of 6 (which
is less than 7) so that we carry a value of whole 8 (which is more than
the alternate 7).
For the (final) solution of the Knapsack problem it is checked whether
most value is taken but the maximum weight is not exceeded. The final solution
will be value=24.
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 |