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. Genetic algorithms are also provided ready for use in the Orbital library.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
Discrete knapsack problem: (NP-complete)- 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.
| # | 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 |
BreederControl
As part of the Orbital library, you will find a graphical tool, BreederControl. It allows you to set up genetic algorithms and keep track of the progress of the evolving populations by plugging in your evolutionary search problem. BreederControl provides a convenient user-interface for setting GA parameters, manipulating genomes, importing/exporting data. Furthermore, it supports automated logbooks for breeder settings and progress, sequential history files, statistics and more. Passing the genetic algorithm problem class by command-line or menu, activates user-specific genetic algorithm problems. By nature of the Java implementation, BreederControl runs under most operating systems, including Windows, Linux and Mac. For the example above, BreederControl looks like this:
Download
If you want to get the genetic algorithm implementations, the BreederControl user interface, and the simple Knapsack demonstration:- see Orbital library