Програма розв'язує задачу про ранець за допомогою генетинчого алгоритму.
Хромосома представляє собою бінарний рядок (список 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 - ціна речей.
-
Вхідні данні: 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.
-
Вхідні данні: 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 - містить клієнтський код.