Програма розв'язує задачу про ранець за допомогою генетинчого алгоритму.

• з описом задачі можете ознайомитися тут;
• з описом ГА для цієї задачі тут (ru).

Хромосома представляє собою бінарний рядок (список 0 і 1): 0 - річ не треба покласти в ранець, 1 - треба.

Нехай є 5 речей і хромосома має вигляд [0, 1, 1, 0, 1]. Це означає, що ми повинні покласти в ранець речі під номерами 2, 3, 5 і не покласти речі під номерами 1, 4.

У реалізації використовується турнірна селекція, схрещування в одній точці, мутація (під час мутації хромосома змінює кожен свій ген на ген з протилежним значенням; ймовірність мутації гена - 0.5%)

Ознайомитися з формулою, яка використовується для обчислення здоров'я хромосоми можете в файлі Knapsack.py.

Також об'єкт класу Knapsack збирає статистику про популяцію під час знаходження розв'зку. Статистика - список, що містить середнє арифметичне значення здоров'я кожної популяції. Цю статистику можна використати для побудови графіку еволюції.

Позначення: W - максимальна вага, N - кількість речей, Wi - вага і-ої речі, Pi - ціна і-ої речі, idx - список номерів речей, tw - вага речей, tp - ціна речей.

1. Вхідні данні: W - 13, N - 5

   W1 = 3, P1 = 1

   W2 = 4, P2 = 6

   W3 = 5, P3 = 4

   W4 = 8, P4 = 7

   W5 = 9, P5 = 6

   Вихідні данні: idx = [2, 4], tw = 12, tp = 13.

   

2. Вхідні данні: W - 15, N - 5

   W1 = 6, P1 = 5

   W2 = 4, P2 = 3

   W3 = 3, P3 = 1

   W4 = 2, P4 = 3

   W5 = 5, P5 = 6

   Вихідні данні: idx = [1, 2, 5], tw = 15, tp = 14 або idx = [1, 4, 5], tw = 13, tp = 14.

   

• Knapsack.py - містить реалізацію генетичного алгоритму для задачі про ранець.
• Chromosome.py - містить клас, що моделює хромосому, котра вміє схрещуватися і мутувати.
• Item.py - містить клас, що моделює річ, котру можна покласти в ранець (кожна річ має вагу і ціну).
• SolutionInfo.py - містить клас, що зберігає інформацію про розв'язок: список обраних речей та їх індексів.
• main.py - містить клієнтський код.