Image:Knapsack ga.svg
Un article de Wikipédia, l'encyclopédie libre.
Knapsack_ga.svg (605 × 745 pixels • taille du fichier : 46 ko • type MIME : image/svg+xml)
 Ce fichier et les informations de sa page de description sont présents sur Wikimedia Commons. |
Contents |
[edit] Description
Illustration of the knapsack problem solved using a genetic algorithm. The items represented by the chromosomes are those from Image:Knapsack greedy.svg.
[edit] Problem
Which boxes to choose to maximize the amount of money while still fullfilling a given constraint (ie. capacity of the bag) ?
[edit] Solution
Basic genetic algorithm :
Generate a population of individuals whose chromosomes represent the selected items (1 = object is selected, 0 = not selected). Each individual is tested according to a fitness function (in knapsack problem, the goal is to optimize the money stored in the bag).
The evolution starts, the bad solutions are discarded, the best individuals are used for reproduction and share their chromosomes (cross-over operator) or are simply copied, mutations may also happen (change a 0 to 1 and vice-versa).
After several generations, the population converges towards an approximated solution or the real solution with luck.
[edit] Licensing
- Author : Dake
- Software : Inkscape
   |
This file is licensed under the Creative Commons Attribution ShareAlike 2.5 License. In short: you are free to share and make derivative works of the file under the conditions that you appropriately attribute it, and that you distribute it only under a license identical to this one. Official license |
Pages contenant l’image
Les pages ci-dessous contiennent cette image :
