We have tried to solve timetable scheduling problem using genetic algorithm. Main problem (of all G.A.) is how to construct individual. The solution was taken from article [1]. Individual is created from all classes arranged in defined order. For example: on 31st. place belongs to monday's Maths for group 4a. We need to create list of all classes(each hour separetly). For each element we define ranges of time and days when it can take place (predefinition oportunity). Program create all possible combination of time and day each class. In 31st. place is writen down the no. one of day and time combination for that class. G.A. has two operators: cross over and mutation. In cross over, child is created by taking identical parts of parents genome. Missing places are filled in with genes randomly taken from parents corespoding genes. Mutation randomly changes some genes (remember that mutated gene must be permited - it must by one from list of date and time combination). Fitness function value is proportional to a number of colisions like more than one class: in the room / for the group / for the teacher in the same time. Additionally, it is incrased by penalty for later hour of classes. Efects of algorithm work tells us that major influence on results has the size of population. If we have less time, we might try to solw the problem with smaller population but higher mutation probability (about 0,1). Conclusion: this metod is proper for this problem.
Problemem do rozwiązania jest ułożanie planu zajęć dla szkoły podstawowej. Problem definiowany jest przez ilość dostępnych sal, ilość nauczycieli oraz listę zajęć dla każdej z grup uczniów. Użytkownik przy podawaniu danych wejściowych może predefiniować terminy określonych zajęć. Każdy z przedmiotów powiązany jest z określonym nauczycielem, każdy przedmiot z określoną grupą.
Problemy tego typu to probelmy NP trudne, zatem nie jest możliwe znalezienie ich rozwiązania w wielomianowym czasie. Nie istnieje algorytm definiujący sposób ich rozwiązania. Problem rozpatrywany można uznać dodatkowo za problem "złożony pod zwględem kombinatorycznym". Przegląd zupełny dostępnych rozwiązań nie jest do zrealizowania z wiadomych powodów. Dla przypadku 6 roczników, 6 klas w każdym, około 26 godzin zajęć tygodniowo możliwych do umieszczenia w średnio 5 dostępnych lokalizacjach czasowych otrzymujemy 1,721567512e+654 możliwych kombinacji (bez zważania na kolizyjność). Ograniczenie do 2 klas z każdego rocznika redukuje ilość kombinacji do 1,198509147e+218.
Zdecydowno się na zastosowanie algorytmu genetycznego. Praktyka dowodzi, że algorytmy te sprawdzają się w takich przypadkach. Minusem jest brak gwarancji na znalezienie minimum globalnego funkcji celu. Problematyczne okazało się wybranie sposobu zapisu pojedyńczego osobnika populacji. Zdecydowano się na rozwiązanie zaproponowane w artykule [1]. Pojedyńczy osobnik składa się zatem z pól, które korsepondują z określonymi zajęciami. Zajęcia są dodatkowo zróżnicowane względem klasy a nawet ilości godzin danego przedmiotu. Jeśli klasa 4a ma mieć 5 godzin zajęć z matematyki, to każda z tych godzin będzie oddzielnie zapisana. Dla przykłądu mat_4a_pon, mat_4a_wt, mat_4a_sr... to oddzielne podawane dane wejściowe. Możliwe jest określenie przedziału czasowego kiedy dane zajęcia mogą się odbyć. Zrzuca to część odpowiedzialności za rozlokowanie przedmiotów na użytkownika. Przedmioty wymagające większej sprawności umysłowej można umieścić w godzinach porannych. W ten sposób upraszczane jest obliczenie funkcji celu, lecz dodawany jest problem omylności człowieka(zbyt wiele zajęć zadeklarowanych na dany przedział czasu). Mając zedfinowane dni i godziny w jakich dane zajęcia mogą mieć miejsce wyznaczamy wszystkie kombinajce dla nich. Następnie w każdym polu osobnika umieszczamy numer kobinacji danych zajęć. Ważny jest także fakt tego, iż do danego przedmiotu przydzielony jest na stałe nauczyciel. Algorym genetyczny działający na tego typu populacji korzysta z dwóch operatorów: krzyżowania i mutacji. Krzyżowanie polega na przekazaniu potomkowi wszystkich genów powtarzających się u dwojga rodziców, a geny brakujące losowo dobierane są z opowiadających im genów rodziców. Ideę przedstawiono na poniższym rysunku.
Operator mutacji natomiast z jednego rodzica na drodze zmiany genów tworzy jednego potomka. Nowe geny dobierane są losowo spośród możliwych (spośród możliwych kombinacji lokalizacji czasowej danego przedmiotu). O mutacji decyduje to, czy losowo wybrana liczba dla danego genu przekracza zdefiniowany próg. Obrazuje ją poniższy rysunek.
Ostatnim aspektem algorytmu genetycznego jest funkcja celu. W artykule [1] zaproponowano obliczanie jej w oparciu o ilość kolizji typu więcej niż jedne zajęcia odbywają się: w jednej sali / z jednym nauczycielem / z jedną klasą w tej samej chwili. Dodatkowo zalecono wartościowanie uzyskanego planu zajęć pod względem ulokowania przedmiotów we wcześniejszych godzinach. Minimalizuje to brak "okienek" w planie. Karę za pojedyńczą kolizję ustalono na wartość wyższą od sumy wszystkich możliwych kar za późność zajęc. Gwarantuje to wybór planu z "okienkiem" zamiast kolizję. W danym momencie algorytm nie zważa na "okienka" w planie zajęć nauczycieli. Zmierza także do tego, by zajęcia grup zaczynały się od najwcześniejszych godzin.
Algorytm zaimplementowano w środowisku Matlab z wykorzystanie narzędzia gatool. Zgodnie z powyższym opisem zdefiniowano funkcję obliczania operatorów oraz funkji celu. Dla obliczania kolizyjności skorzystano z tablic trójwymiarowych. Każde zajęcia lokalizowane są w przestrzeni dzień x godzina x nauczyciel / sala / grupa. Przeglądając osobnika zaznaczamy kolejne komórki. Z próby zaznaczenia komórki wcześniej oznaczonej wynika, że nastąpiła kolizja, np. w tej samej chwili nauczyciel ma więcej niż jedne zajęcia. Tablicę taką obrazuje poniższy rysunek. Kożda warstwa przedstawia tygodniowy plan zajęć jednego nauczyciela (lub grupy, lub zajętość sali).
Na czas obliczęń liniowy wpływ ma rozmiar populacji utrzymywany przez algorytm. Napotkano znaczący problem: nie da się wyłączyć warunku stopu, który polega na badaniu średniej wartości funkcji przystosowania dla całej populacji. Jeśli nie zmienia się ona przez określoną liczbę iteracji, to algorytm przerywa działanie.
Testowy przykład zbudowany został dla przypadku 1 nauczyciela, 8 grup, gdzie grupy 1 - 5 mają mieć 8 godzin zajęć w całym tygodniu (nie codziennie), natomiast grupy 6 - 8 mają mieć 7 godzin zajęć. Dotychczasowe wnioski oparto na nim. Poniższe wykresy prezentują zależność uzyskanego wyniku od rozmiaru populacji i prawdopodobieństaw mutacji.
Poniżej populacja rozmiaru 1000, prawdopodobieństwo mutacji 0,01. Końcowa wartość funkcji celu to 180 zatem nie wystąpiła żadna kolizja a zajęcia zostały ulokowane wcześnie. Wynik uzyskany po około 30 pokoleniach.
Poniżej populacja rozmiaru 100, prawdopodobieństwo mutacji 0,01. Końcowa wartość funkcji celu to 180 zatem nie wystąpiła żadna kolizja a zajęcia zostały ulokowane wcześnie. Wynik uzyskany po około 60 pokoleniach:
Poniżej populacja rozmiaru 10, prawdopodobieństwo mutacji 0,01. Końcowa wartość funkcji celu to 28962 zatem wystąpiły liczne kolizje:
Poniżej populacja rozmiaru 10, prawdopodobieństwo mutacji 0,05. Końcowa wartość funkcji celu to 21762 zatem wystąpiły liczne kolizje. Większa mutacja zaowocowała widoczną poprawą wyniku:
Poniżej populacja rozmiaru 10, prawdopodobieństwo mutacji 0,10. Końcowa wartość funkcji celu to 14569 zatem wystąpiły liczne kolizje. Dalszy wzrost mutacji ponownie pomógł:
Wraz ze wzrostem ilości osobników w populacji prędkość spadku wartości funkcji celu jest coraz większa. Okazuje się, że przy utrzymywaniu populacji o liczności 10 dla testowego przykładu częstym wynikiem jest plan z kilkoma kolizjami. Dla tego przykładu populacja winna liczyć nie mniej niż 100 osobników. Dla dużych rozmiarów populacji (np. 1000 dla tego przykładu), prawdopodobnieństwo mutacji powinno być bliskie 0,01. Wyższe wartości porządane są dla mniejszych populacji. Niestety na chwile obecną badania dla przykłądu rzeczywistego (http://www.plock.edu.pl/szkoly/sp12/plan.html) są w trakcie realizacji. Zostaną dostarczone najpóźniej przy oddaniu projektu. Na obecną chwilę uznać można, że dana metoda jest odpowiednia do rowiązania postawionego problemu.
[1] B. Sigl, M. Golub, V. Mornar, "Solving Timetable Scheduling Problem Using Genetic Algorithms", Information Technology Interfaces, 2003. ITI 2003. Proceedings of the 25th International Conference on Volume, Issue, 16-19 June 2003 Page(s): 519 - 524
[2] S. Ghaemi, M. T. Vakili, "Using a genetic algorithm optimizer tool to solve univeristy timetable scheduling problem", dostępne na stronie: www.acd-2006.cran.uhp-nancy.fr/Files/ACD/p49.pdf
[3] Z. Michalewicz, "Struktury danych + algorytmy genetyczne = programy ewolucyjne", Wydawnictwa Naukowo-Techniczne, Warszawa, 2003
