23. czerwca 2008
Krzysztof Sroka
Sztuczna inteligencja — Instytut Informatyki UWr
Problem optymalizacji planu zajęć to problem kombinatoryczny polegający na przydzieleniu zasobów, reprezentowanych przez trójki:
pewnemu zbiorowi zajęć Z. Przyporządkowanie to jest poprawne jeżeli dla dwóch różnych zbiorów, których przyporządkowane przedziały czasowe pokrywają się, przyporządkowane im elementy zbiorów N i P są różne. Dodatkowo wprowadza się także różne ograniczenia na takie przyporządkowania, np.: możliwość przyporządkowania tylko pewnego podzbioru zbioru nauczycieli do danego zajęcia lub zabronienie kojarzenia ze sobą pewnych nauczycieli i przedziałów czasowych.W ogólnym wypadku można wprowadzić także dodatkowo zbiór uczniów, którzy również muszą być przyporządkowani rozdzielnie względem czasu, jednak w opisywanej poniżej realizacji problemu optymalizacji planu zajęć nie jest to konieczne.
Problem optymalizacji planu zajęć sprowadza się do znalezienia takiego przyporządkowania (planu zajęć) Popt, który minimalizuje wartość pewnej funkcji celu F. (Oczywiście minimalizację można bez przeszkód zastąpić maksymalizacją odwrotnej funkcji, ale w dalszej częłści raportu będzie mowa o minimalizacji).
Prezentowane poniżej rozwiązanie opiera się o zastosowanie algorytmu genetycznego. Algorytmy genetyczne to grupa algorytmów opartych na biologicznej zasadzie ewolucji, w których rozwiąznie problemu reprezentuje struktura zwana chromosomem. Każdy taki chromosom może być poddawany pewnym operacjom, wśród których wyróżnia się dwa typy:
Przebieg działania algorytmu genetycznego można przedstawić następująco:
algorytm(N) {
P := losowa_populacja(N);
while (! warunek_końca) {
P := operator1(P);
P := operator2(P);
...
P := operatorK(P);
}
}
Algorytmy genetyczne sprawdzają się w różnorakich zastosowaniach, także w optymalizacji zagadnień NP-trudnych. Również w wypadku problemu optymalizacji planu zajęć przestawiają dość dobre rezultaty. Nota bene także w Instytucie Informatyki UWr powstał projekt wykorzystujący algorytm genetyczny w optymalizacji planu zajęć.
Chromosom w rozpatrywanym problemie to zbiór czwórek składających się z: opisu zajęć, przydzielonego pokoju, przydzielonego nauczyciela oraz przedziału czasowego. Dane są także dodatkowe właściwości określające poprawność takich piątek:
W zrealizowanym algorytmie genetycznym użyte zostały trzy operatory mutacji, które z zadanym prawdopodobieństwem zmieniały przedział czasu, nauczyciale lub pokój. Zostały one zaimplementowane w taki sposób, aby przez cały przebieg procesu optymalizacji generowane były tylko poprawne rozwiązania Populacja powstała na bazie tych operatorów zawiera zawrówno oryginalne chromosomy jak i zmutowane. Ocena każdego z chromosomów polega na sumowaniu (ważonych) wartości zdefiniowanych trzech funkcji kar:
Inicjalizacja algorytmu polega na wygenerowaniu 100 poprawnych rozkładów zajęć, następnie do każdej kolejnej iteracji algorytmu brane jest 25% najlepszych osobników względem tak zdefiniowanej funkcji celu. Oprócz wybranych osobników do kolejnej populacji trafiają także osobnicy wygenerowani na podstawie mutacji z istniejących rozwiązań. Mutacja występuje w trzech wariantach:
Algorytm kończy działanie po 250 wykonanych iteracjach. Przy takiej wartości algorytm nie poprawia już znacząco wyników pod koniec działania.
Powyzej zaprezentowany algorytm został zaiomplementowany w języku Java (JavaSE 6). Poniżej zaprezentowany jest diagram głównych klas wykorzystywanych w algorytmie: struktur danych.
Na chromosom poddawany ocenie składa się pewien (poprawny) zbiór obiektów instancji
Assignment, z których też każda jest poprawna względem ograniczeń reprezentowanych
w obiektach typów Room, TeacherPrefs i ClassConstraints.
Aby poprawnie uruchomić program należy zainicjalizować go poleceniem: java zplan.optimization.Algorithm <dane> wykonanym z katalogu zawierającego skompilowane pliki projektu. Parametr dane musi wskazywac na katalog z danymi wykładowców i zajęć. Domyślnie przyjmowany jest sztywno ustalony zbiór pokoi, bazowany na rzeczywistych pomieszczeniach instytutu informatyki UWr. Archiwum załączone do raportu zawiera także przykładowe dane inicjalizacyjne bazowane na rzeczywistych danych instytutu informatyki z lat 2003-2006.
Program podczas przebiegu działania algorytmu wypisuje na strumień stderr pomocnicze komunikaty:
Loaded 61 teachers Loaded 18 rooms Loaded 44 classes Generating 100 random schedules ....................................................................................................Generated random population in 47004 milliseconds Size: 100 New best in iteration #0 : 67.6 New best in iteration #1 : 67.35 New best in iteration #2 : 66.85 New best in iteration #3 : 65.19999999999999 New best in iteration #5 : 64.94999999999999 New best in iteration #6 : 63.35 New best in iteration #8 : 62.699999999999996 New best in iteration #10 : 61.1 New best in iteration #11 : 60.85 New best in iteration #12 : 60.25...
New best in iteration #194 : 47.599999999999994 New best in iteration #205 : 47.099999999999994 New best in iteration #222 : 46.849999999999994 Final best note: 46.849999999999994
Po zakończeniu działania algorytmu na standardowe wyjście (stderr) wypisywany jest najlepszy ułożony plan zajęć w formacie:
dzień godzina Zajęcia Typ-zajęć Prowadzący Sala
Poniżej zaprezentowany jest fragment takiego planu:
pn 1200 Politologia Pracownia Michał Załęski p137 pn 1200 Algorytmy tekstowe Ćwiczenia Przemysława Kanarek c104 pn 1200 Rownania w slowach Ćwiczenia Antoni Kościelski c103 pn 1200 Matematyka dyskretna Ćwiczenia Maciej M. Sysło c106 pn 1200 Analiza numeryczna Wykład Paweł Keller x4 pn 1200 Zlozonosc obliczeniowa Ćwiczenia Krzysztof Loryś x141 pn 1400 Analiza numeryczna Wykład Paweł Keller w135 pn 1400 Logika dla informatykow Ćwiczenia Witold Charatonik c139 pn 1400 Rachunek prawdopodobienstwa i statystyka Wykład Witold Karczewski w24
...
Eksperymenty zostały przeprowadzone na następujących wartościach wag:
Przy powyższych wagach dość dobrze sprawowały się wykonania lgorytmu przy ustalonych prawdopodobieństwach mutacji na poziomie 0.1 (przeciętnie dawały one wartości na poziomie 45.0-48.0 punktów).