Celem projektu było opracowanie i zbadanie skuteczności algorytmu genetycznego w generowaniu optymalnych planów zajęć dla studentów uczelni. Algorytm uwzględniał kluczowe ograniczenia, takie jak przedmioty obieralne, dostępność sal, harmonogram wykładowców oraz preferencje studentów co do godzin zajęć. Całość została zaimplementowana w języku Python, co umożliwiło elastyczne testowanie różnych parametrów i scenariuszy.
1. Założenia projektu
Głównym celem było stworzenie narzędzia, które w sposób automatyczny generuje plany zajęć, minimalizując konflikty i maksymalizując wygodę zarówno dla studentów, jak i wykładowców. Projekt miał na celu rozwiązanie problemu NP-trudnego, jakim jest planowanie zajęć, poprzez zastosowanie technik inspirowanych procesem ewolucji biologicznej.
Uwzględnione ograniczenia:
- Przedmioty obieralne: Każdy student mógł wybrać zestaw przedmiotów, co wymagało ich dopasowania do ogólnego planu.
- Dostępność sal: Liczba dostępnych sal oraz ich pojemność musiały być respektowane, aby uniknąć sytuacji, w której liczba uczestników przekracza możliwości danej sali.
- Harmonogram wykładowców: Wykładowcy mieli z góry określone godziny, w których byli dostępni.
- Godziny zajęć: Zajęcia nie mogły kolidować w czasie dla grup uczestniczących w różnych przedmiotach.
2. Opis algorytmu genetycznego
Algorytm genetyczny działał w oparciu o symulację procesu ewolucji, w którym „osobniki” (kandydaci na rozwiązania) były oceniane i optymalizowane w kolejnych pokoleniach.
Podstawowe elementy algorytmu:
- Reprezentacja chromosomu:
- Chromosom reprezentował potencjalny plan zajęć. Każdy gen odpowiadał pojedynczemu przedmiotowi i zawierał informacje takie jak godzina zajęć, sala i grupa studentów.
- Funkcja fitness:
- Funkcja oceniała jakość planu zajęć, biorąc pod uwagę:
- Minimalizację konfliktów w godzinach zajęć.
- Dopasowanie liczby studentów do pojemności sal.
- Uwzględnienie dostępności wykładowców.
- Respektowanie preferencji studentów co do godzin zajęć (np. unikanie zajęć porannych).
- Funkcja oceniała jakość planu zajęć, biorąc pod uwagę:
- Inicjalizacja populacji:
- Algorytm rozpoczynał od losowego wygenerowania populacji kandydatów na rozwiązania. Każdy plan zajęć w tej populacji był wygenerowany w sposób częściowo losowy, ale respektujący podstawowe ograniczenia.
- Selekcja:
- Osobniki z wyższą wartością funkcji fitness miały większe szanse na udział w kolejnych etapach (np. selekcja ruletkowa lub turniejowa).
- Krzyżowanie (Crossover):
- Kandydaci byli krzyżowani w celu stworzenia nowego planu zajęć poprzez wymianę fragmentów chromosomów (np. podział na grupy genów odpowiadające różnym dniom tygodnia).
- Mutacja:
- Wprowadzano niewielkie losowe zmiany w chromosomach, takie jak przesunięcie godziny zajęć lub zmiana sali, co pozwalało uniknąć wpadnięcia algorytmu w lokalne minima.
- Ewolucja:
- Proces selekcji, krzyżowania i mutacji był powtarzany przez określoną liczbę pokoleń lub do momentu spełnienia kryteriów zatrzymania (np. uzyskania planu o odpowiednio wysokiej wartości funkcji fitness).
3. Proces realizacji projektu
- Zbieranie danych wejściowych:
- Dane wejściowe obejmowały:
- Listę przedmiotów z przypisanymi grupami studentów.
- Listę dostępnych sal z ich pojemnościami.
- Harmonogram dostępności wykładowców.
- Preferencje czasowe studentów.
- Dane wejściowe obejmowały:
- Implementacja algorytmu:
- Algorytm został zaimplementowany w Pythonie przy użyciu bibliotek takich jak
numpy(do obliczeń numerycznych) orazmatplotlib(do wizualizacji wyników). - Dane wejściowe były reprezentowane w strukturach takich jak listy i słowniki, umożliwiając dynamiczne dopasowanie planu zajęć.
- Algorytm został zaimplementowany w Pythonie przy użyciu bibliotek takich jak
- Testowanie algorytmu:
- Algorytm był testowany na różnych zestawach danych, od małych grup zajęciowych po bardziej złożone scenariusze obejmujące wiele przedmiotów, sal i grup studentów.
- Wyniki były porównywane z manualnie opracowanymi planami zajęć w celu oceny jakości rozwiązań generowanych przez algorytm.
- Optymalizacja parametrów:
- Parametry algorytmu, takie jak rozmiar populacji, liczba pokoleń, współczynniki krzyżowania i mutacji, były dostrajane w celu uzyskania jak najlepszych wyników.
4. Wyniki projektu
- Efektywność: Algorytm genetyczny skutecznie minimalizował konflikty harmonogramowe, takie jak nakładanie się zajęć w salach czy brak dostępności wykładowców.
- Dopasowanie: W testach na dużych zestawach danych algorytm generował plany zajęć spełniające ponad 95% założonych wymagań (np. brak kolizji, spełnienie preferencji studentów).
- Czas działania: W zależności od złożoności problemu, czas generowania rozwiązania wahał się od kilku sekund dla prostych scenariuszy do kilku minut dla bardziej złożonych przypadków.
- Elastyczność: Algorytm łatwo adaptował się do zmiennych warunków, takich jak dodanie nowych przedmiotów, grup czy sal.
5. Możliwości rozwoju
- Integracja z systemami uczelnianymi: Automatyczne pobieranie danych o przedmiotach, studentach i salach.
- Interfejs graficzny: Wizualizacja planu zajęć w formie interaktywnego GUI, umożliwiająca edycję ręczną.
- Dalsza optymalizacja: Ulepszenie funkcji fitness poprzez wprowadzenie bardziej szczegółowych kryteriów (np. minimalizacja luk w harmonogramie studentów).
- Rozszerzenie algorytmu: Połączenie algorytmu genetycznego z innymi metodami optymalizacyjnymi, np. algorytmem symulowanego wyżarzania (Simulated Annealing).
Projekt ten stanowi przykład zastosowania algorytmów genetycznych do praktycznych problemów optymalizacyjnych. Zaimplementowane rozwiązanie nie tylko automatyzuje proces tworzenia planów zajęć, ale także umożliwia ich dostosowanie do skomplikowanych ograniczeń i preferencji.
Polish 
English