Celem projektu jest zaimplementowanie algorytmu genetycznego (AG) do rozwiązania problemu plecakowego. Problem plecakowy polega na wyborze określonych przedmiotów w taki sposób, aby ich wartość była jak największa, ale suma ich wag nie przekraczała określonej pojemności plecaka.
Zdefiniuj strukturę chromosomu reprezentującego rozwiązanie problemu plecakowego.
Stwórz losową populację chromosomów reprezentujących różne zestawy przedmiotów w plecaku.
Zaimplementuj funkcję przystosowania, która ocenia każde rozwiązanie pod kątem jego wartości i zgodności z ograniczeniami plecaka (suma wag).
Wybierz rodziców do krzyżowania na podstawie funkcji przystosowania. Możesz użyć metod selekcji takich jak ruletka, ranking, lub turniej.
Wykonaj operację krzyżowania na parach rodziców, aby uzyskać potomstwo. Możesz zaimplementować różne metody krzyżowania.
Wprowadź losowe zmiany w potomstwie, aby zachować różnorodność w populacji.
Zaimplementuj główną pętlę algorytmu genetycznego, w której powtarzasz operacje selekcji, krzyżowania i mutacji przez pewną liczbę pokoleń.
Zapisz najlepsze rozwiązanie znalezione przez algorytm genetyczny.
Wybierz narzędzia i język programowania do implementacji algorytmu genetycznego. Możesz wybrać dowolny język programowania, ale nie można korzystać z gotowych bibliotek do rozwiązywania problemu plecakowego.
Sporządź sprawozdanie z przebiegu projektu. Krótko opisz napotkane problemy i ich rozwiązania przy poszczególnych etapach AG.
Do testowania algorytmu genetycznego w rozwiązywaniu problemu plecakowego można użyć przykładowego zestawu danych, który zawiera wartości i wagi przedmiotów oraz pojemność plecaka. Oto przykładowy zestaw danych:
- Wartości przedmiotów: [60, 100, 120, 50, 60, 30, 70, 110, 130, 60, 90, 40, 80, 90, 110, 120, 50, 100, 30, 70]
- Wagi przedmiotów: [10, 20, 30, 40, 50, 10, 60, 70, 80, 20, 30, 15, 25, 35, 40, 45, 10, 30, 15, 25]
- Pojemność plecaka: 250
Do oceny wysyłamy plik nr_indeksu_imię_nazwisko.zip, np. 123456_Jan_Kowalski.zip. Plik ten musi zawierać sprawozdanie z projektu w formacie PDF oraz plik z kodem źródłowym.
(zawartość typu markdown została wygenerowana i przetłumaczona przez ChatGPT ze źródłowego pliku PDF)