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

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

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.

• Author : Dake
• Software : Inkscape

Этот файл доступен по лицензии Creative Commons Attribution-Share Alike 2.5 Generic

Вы можете свободно:

• делиться произведением – копировать, распространять и передавать данное произведение
• создавать производные – переделывать данное произведение

При соблюдении следующих условий:

• атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
• распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.

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