Algorytm genetyczny dla problemu plecakowego

Implementacja algorytmu genetycznego (AG) rozwiązującego dyskretny problem plecakowy 0/1.

Problem plecakowy 0/1

Mamy zbiór przedmiotów, każdy z określoną wartością i wagą. Plecak ma ustaloną pojemność (maksymalną dopuszczalną wagę). Cel: wybrać taki podzbiór przedmiotów, żeby:

• suma wag nie przekroczyła pojemności,
• suma wartości była jak największa.

Jak działa algorytm genetyczny

Algorytm genetyczny (AG) jest inspirowany doborem naturalnym. Zamiast szukać rozwiązania analitycznie, utrzymuje populację kandydatów i poprawia ją z pokolenia na pokolenie, naśladując trzy mechanizmy biologiczne: selekcję, krzyżowanie i mutację.

Główne pojęcia:

• Osobnik (chromosom): pojedyncze rozwiązanie zakodowane jako wektor genów.
• Populacja: zbiór osobników w danym pokoleniu.
• Funkcja przystosowania (fitness): liczbowa miara jakości rozwiązania; im wyższa, tym osobnik „lepszy".
• Pokolenie: jeden cykl ewolucji: selekcja → krzyżowanie → mutacja → ocena nowej populacji.

1. Reprezentacja (chromosom)

Każde rozwiązanie to wektor bitów długości n (liczba przedmiotów). Bit i = 1 oznacza, że bierzemy przedmiot i; 0 zostawiamy. Przykład dla 5 przedmiotów:

chromosom = [1, 0, 1, 1, 0]   ⇒   bierzemy przedmioty 0, 2, 3

W kodzie chromosom to numpy.ndarray typu bool w klasie Individual. Tablica numpy pozwala oceniać fitness wektorowo (mnożenie przez tablicę wartości / wag) zamiast iterować po bitach w pętli Pythona.

2. Funkcja przystosowania (fitness)

Dla danego osobnika obliczamy sumę wartości i sumę wag wybranych przedmiotów:

total_value  = Σ value[i]   dla bitów = 1
total_weight = Σ weight[i]  dla bitów = 1

Następnie:

• jeśli total_weight ≤ capacity → fitness = total_value,
• w przeciwnym razie → fitness = 0 (kara za nadwagę).

Strategia „kary zerowej" jest najprostsza: osobniki przekraczające pojemność efektywnie nie biorą udziału w selekcji, ponieważ przegrywają każdy turniej z osobnikiem o dodatnim fitnessie.

3. Inicjalizacja

Tworzymy populację population_size osobników o losowych chromosomach (każdy bit niezależnie 0 lub 1 z prawdopodobieństwem 0.5). To gwarantuje różnorodność populacji startowej, dzięki której algorytm zaczyna od szerokiego rozproszenia kandydatów w przestrzeni rozwiązań.

4. Selekcja: turniej

Selekcja decyduje, którzy osobnicy zostaną rodzicami kolejnego pokolenia. W tej implementacji używamy selekcji turniejowej:

1. Wylosuj k osobników z bieżącej populacji (z powtórzeniami).
2. Wybierz spośród nich tego o najwyższym fitnessie; on jest „rodzicem".
3. Powtórz, by wybrać kolejnego rodzica.

Parametr k (tournament_size) reguluje presję selekcyjną:

• k = 2: łagodna selekcja, większa różnorodność, wolniejsza konwergencja,
• k większe: silna presja na najlepszych, szybsza konwergencja, większe ryzyko utknięcia w optimum lokalnym.

W odróżnieniu od selekcji ruletkowej, turniej nie wymaga skalowania fitnessu i jest odporny na ujemne lub zerowe wartości.

5. Krzyżowanie: jednopunktowe (single-point)

Z pary rodziców powstaje para dzieci poprzez wymianę „ogonów" chromosomów po losowym punkcie cięcia:

parent A:  [1 0 1 | 1 0 0 1]
parent B:  [0 1 0 | 0 1 1 0]
                ↓ punkt cięcia = 3
child  1:  [1 0 1 | 0 1 1 0]
child  2:  [0 1 0 | 1 0 0 1]

Krzyżowanie zachodzi z prawdopodobieństwem crossover_probability (typowo 0.7–0.9). Jeśli losowanie nie zezwoli na krzyżowanie, dzieci są kopiami rodziców. Zadaniem krzyżowania jest eksploatacja: łączenie cech dobrych rozwiązań w nadziei, że potomek odziedziczy „najlepsze fragmenty" obojga.

6. Mutacja: odwracanie bitów (bit-flip)

Każdy bit dziecka jest niezależnie odwracany z małym prawdopodobieństwem mutation_probability (typowo 1–5% dla pojedynczego bitu):

przed mutacją: [1 0 1 1 0 0 1]
                       ↑
po mutacji:    [1 0 1 0 0 0 1]

Mutacja odpowiada za eksplorację: wprowadza losową wariancję, dzięki której algorytm może wyjść z optimum lokalnego i sprawdzić nowe regiony przestrzeni rozwiązań. Zbyt duża mutacja zamienia AG w przeszukiwanie losowe; zbyt mała prowadzi do przedwczesnej konwergencji.

7. Pętla ewolucji

Powyższe operatory są stosowane cyklicznie przez generations iteracji. W każdym pokoleniu:

1. Z bieżącej populacji wybieramy parami rodziców (turniej).
2. Krzyżujemy rodziców → dwoje dzieci.
3. Mutujemy każde dziecko.
4. Dodajemy dzieci do nowej populacji, aż osiągnie zaplanowany rozmiar.
5. Oceniamy całą nową populację.
6. Bieżąca populacja = nowa populacja.

Algorytm zapamiętuje najlepszego osobnika napotkanego w całym przebiegu (best_ever), nawet jeśli w kolejnych pokoleniach zostanie wyparty przez „średnie" rozwiązania. Dzięki temu wynik nigdy się nie pogarsza.

8. Schemat blokowy

flowchart TD
    Start([Start]) --> Init[Wygeneruj losową populację<br/>o rozmiarze population_size]
    Init --> EvalInit[Oceń wszystkie osobniki<br/>oblicz fitness]
    EvalInit --> Best[Zapamiętaj najlepszego osobnika<br/>jako best_ever]
    Best --> GenLoop{Czy gen ≤ generations?}
    GenLoop -- nie --> Return([Zwróć best_ever])
    GenLoop -- tak --> NewPop[Utwórz pustą<br/>nową populację]
    NewPop --> Fill{Czy nowa populacja<br/>jest pełna?}
    Fill -- tak --> EvalNew[Oceń nową populację]
    Fill -- nie --> SelA[Selekcja turniejowa<br/>→ rodzic A]
    SelA --> SelB[Selekcja turniejowa<br/>→ rodzic B]
    SelB --> CrossDecision{rand < p_cross?}
    CrossDecision -- tak --> Cross[Krzyżowanie jednopunktowe<br/>A × B → dziecko 1, dziecko 2]
    CrossDecision -- nie --> Copy[Skopiuj rodziców<br/>jako dziecko 1, dziecko 2]
    Cross --> Mut1[Mutacja bit-flip<br/>na dziecku 1]
    Copy --> Mut1
    Mut1 --> Mut2[Mutacja bit-flip<br/>na dziecku 2]
    Mut2 --> AddChildren[Dodaj oba dzieci<br/>do nowej populacji]
    AddChildren --> Fill
    EvalNew --> UpdateBest[Jeśli najlepszy z nowej populacji<br/>> best_ever, zaktualizuj best_ever]
    UpdateBest --> Replace[Bieżąca populacja<br/>= nowa populacja]
    Replace --> Increment[gen = gen + 1]
    Increment --> GenLoop

Loading

Struktura projektu

knapsack/
  __init__.py
  item.py             – pojedynczy przedmiot (dataclass: name, value, weight)
  problem.py          – instancja problemu (dataclass: lista przedmiotów + capacity)
  individual.py       – osobnik (chromosom binarny + fitness)
  population.py       – populacja osobników + agregaty
  selection.py        – selekcja turniejowa
  crossover.py        – krzyżowanie jednopunktowe
  mutation.py         – mutacja bit-flip
  config.py           – parametry algorytmu (dataclass)
  algorithm.py        – główna pętla AG
main.py               – przykładowa instancja + uruchomienie

Jedna klasa = jeden plik. Bez dziedziczenia, bez Strategy pattern — dla materiału dydaktycznego prosta struktura jest cenniejsza niż elastyczność.

Parametry konfiguracji (GaConfig)

Parametr	Domyślnie	Znaczenie
population_size	100	Liczba osobników w populacji (musi być parzysta).
generations	100	Liczba pokoleń.
tournament_size	3	Liczba uczestników turnieju (selekcja).
crossover_probability	0.85	Prawdopodobieństwo krzyżowania pary rodziców.
mutation_probability	0.02	Prawdopodobieństwo zmiany pojedynczego bitu.
random_seed	42	Ziarno generatora; gwarantuje powtarzalność wyników.

Wszystkie parametry są walidowane w __post_init__ dataclassy.

Uruchomienie

Cała konfiguracja runu znajduje się w pliku main.py: instancja problemu (lista przedmiotów + pojemność) oraz GaConfig. Modyfikacja danych albo parametrów polega na edycji tego jednego pliku, następnie:

source .venv/bin/activate
pip install numpy   # jednorazowo
python main.py

Wymagania

• Python 3.11+ (type hints generyczne, dataclasses).
• numpy (chromosom + wektorowa ocena fitness).

Przykładowy wynik

Knapsack Genetic Algorithm
==========================
Items: 12, capacity: 10
Population: 100, generations: 100, tournament: 3, p_cross: 0.85, p_mut: 0.02, seed: 42

Generation   0: best=3500, avg=1160.40
Generation   1: best=3640, avg=2017.30
...
Generation 100: best=4350, avg=3910.30

Best solution found:
  - Laptop       value=1200 weight= 3
  - Camera       value= 800 weight= 2
  - Headphones   value= 300 weight= 1
  - Watch        value= 450 weight= 1
  - Tablet       value= 700 weight= 2
  - Phone        value= 900 weight= 1
Total value:  4350
Total weight: 10 / 10
Fitness:      4350