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 boolean[] w klasie Individual.

2. Funkcja przystosowania (fitness)

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

totalValue  = Σ value[i]   dla bitów = 1
totalWeight = Σ weight[i]  dla bitów = 1

Następnie:

• jeśli totalWeight ≤ capacity → fitness = totalValue,
• 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ę populationSize 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 (tournamentSize) 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 crossoverProbability (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 mutationProbability (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 (bestEver), 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 populationSize]
    Init --> EvalInit[Oceń wszystkie osobniki<br/>oblicz fitness]
    EvalInit --> Best[Zapamiętaj najlepszego osobnika<br/>jako bestEver]
    Best --> GenLoop{Czy gen ≤ generations?}
    GenLoop -- nie --> Return([Zwróć bestEver])
    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/>> bestEver, zaktualizuj bestEver]
    UpdateBest --> Replace[Bieżąca populacja<br/>= nowa populacja]
    Replace --> Increment[gen = gen + 1]
    Increment --> GenLoop

Loading

Struktura projektu

src/main/java/com/github/mako321/knapsack/
  Item.java               – pojedynczy przedmiot (record: name, value, weight)
  KnapsackProblem.java    – instancja problemu (record: lista przedmiotów + pojemność)
  Individual.java         – osobnik (chromosom binarny + fitness)
  Population.java         – populacja osobników + agregaty
  Selection.java          – selekcja turniejowa
  Crossover.java          – krzyżowanie jednopunktowe
  Mutation.java           – mutacja bit-flip
  GaConfig.java           – parametry algorytmu (record)
  GeneticAlgorithm.java   – główna pętla AG
  Main.java               – przykładowa instancja + uruchomienie

src/test/java/com/github/mako321/knapsack/
  IndividualTest, SelectionTest, CrossoverTest,
  MutationTest, GeneticAlgorithmTest         – testy jednostkowe (JUnit 5)

Parametry konfiguracji (GaConfig)

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

Wszystkie parametry są walidowane w konstruktorze rekordu.

Uruchomienie

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

Wymagania

• JDK 25 (projekt używa rekordów oraz instancyjnej metody main z Javy 25).

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=2200, avg=  ...
Generation   1: best=2350, avg=  ...
...
Generation 100: best=4350, avg=  ...

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