Resum

Illustration of the knapsack problem solved using a genetic algorithm. The items represented by the chromosomes are those from Image:Knapsack greedy.svg.

Problem

Which boxes to choose to maximize the amount of money while still fullfilling a given constraint (ie. capacity of the bag) ?

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.

Llicència

• Author : Dake
• Software : Inkscape

Aquest fitxer està publicat sota la llicència de Creative Commons Reconeixement i Compartir Igual 2.5 Genèrica.

Sou lliure de:

• compartir – copiar, distribuir i comunicar públicament l'obra
• adaptar – fer-ne obres derivades

Amb les condicions següents:

• reconeixement – Heu de donar la informació adequada sobre l'autor, proporcionar un enllaç a la llicència i indicar si s'han realitzat canvis. Podeu fer-ho amb qualsevol mitjà raonable, però de cap manera no suggereixi que l'autor us dóna suport o aprova l'ús que en feu.
• compartir igual – Si modifiqueu, transformeu, o generareu amb el material, haureu de distribuir les vostres contribucions sota una llicència similar o una de compatible com l'original

https://creativecommons.org/licenses/by-sa/2.5CC BY-SA 2.5 Creative Commons Attribution-Share Alike 2.5 truetrue