10 pkt

Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej Nr 21

Seminarium

ZASTOSOWANIE KOMPUTERÓW w NAUCE i TECHNICE’ 2005

Oddział Gdański PTETiS

ZASTOSOWANIE ALGORYTMÓW GENETYCZNYCH

DO AUTOMATYCZNEGO GENEROWANIA PLANU ZAJĘĆ

Dominik CUBALA

, Longin STOLC

1. Politechnika Gdańska, ul. G. Narutowicza 11/12, 80-952 Gdańsk

tel: (058) 347 1226 fax: (058) 347 2487 e-mail: cubala@wp.pl

2. Politechnika Gdańska, ul. G. Narutowicza 11/12, 80-952 Gdańsk

tel: (058) 347 1420

fax: (058) 347 2487 e-mail: lstolc@ely.pg.gda.pl

Praca przedstawia zastosowanie algorytmów genetycznych do automatycznego układania
szkolnego rozkładu zajęć. Stworzono do tego celu odpowiedni program komputerowy –
PLANIX, który w kilkanaście minut potrafi poradzić sobie ze średniej klasy problemem i nie
wymaga praktycznie żadnej interwencji ze strony użytkownika. W niniejszej pracy został
zaprezentowany rdzeń tego programu, zawierający implementację odpowiedniego algorytmu
genetycznego. Opisane zostały sposoby reprezentacji, kodowania i inicjalizacji genotypu,
konstrukcja funkcji oceny (konflikty twarde i miękkie) oraz procedury selekcji i reprodukcji.
W dalszej części pracy przedstawiono wyniki przeprowadzonych badań, mających na celu
odpowiedni dobór szeregu różnego rodzaju parametrów, które w dużym stopniu wpływają na
jakość ułożonego rozkładu zajęć.

1. WSTĘP

Ręczne ułożenie planu lekcji w średniej wielkości szkole zajmuje człowiekowi od kil-

ku do kilkudziesięciu godzin. Co więcej, tak skonstruowany plan może być niedoskonały
pod pewnymi względami, np. klasa może mieć pomiędzy kolejnymi zajęciami zbyt wiele
długich przerw. Z tych powodów zwrócono uwagę na możliwość automatyzacji procesu
układania rozkładu zajęć.

Ze względu na ogromną liczbę ograniczeń i duże rozmiary zagadnienia, metoda pole-

gająca na przejrzeniu całej przestrzeni rozwiązań, nie jest w ogóle brana pod uwagę. Wtedy
konieczne jest zastosowanie jednej z wyspecjalizowanych technik obliczeniowych. Jedną
z takich metod, która w ciągu ostatnich kilkunastu lat przeżyła okres burzliwego rozwoju,
są algorytmy genetyczne. Ich sposób działania naśladuje naturalne procesy zachodzące
w przyrodzie, takie jak dziedziczenie i walkę o przetrwanie. Algorytmy te mają niewątpli-
we zalety: są niezwykle elastyczne i do rozwiązania problemu nie potrzebują zbyt obszer-
nej wiedzy dziedzinowej. Więcej na temat algorytmów genetycznych można znaleźć w [2],
[3], [4].

________________________________________________________________________________________________________________________________________________________________________________________

Recenzent: Dr inż. Mirosław Kwiesielewicz - Wydział Elektrotechniki i Automatyki

Politechniki Gdańskiej

- 46 -

2. SFORMUŁOWANIE ZAGADNIENIA

2.1. Reprezentacja genotypu i sposoby jego kodowania

Genotyp w systemie PLANIX reprezentowany jest w sposób bezpośredni. Każda sala

odpowiada jednemu chromosomowi w genotypie. Każdy gen chromosomu reprezentuje
inny przedział czasowy. Wszystkie geny chromosomów są zakodowane przyjmując warto-
ści całkowite większe bądź równe zero. Wartość zero oznacza, iż gen jest wolny od zajęć.
Pozostałe wartości odpowiadają numerowi zajęcia z zadanej przez układającego macierzy
odwzorowującej wszystkie spotkania, które muszą zostać zaplanowane.

Genotyp w systemie PLANIX wskazuje jedynie dzień, godzinę lekcyjną oraz salę,

w której odbywają się poszczególne zajęcia. Jednak korzystając z macierzy zajęć można
łatwo wywnioskować rozkłady zajęć dla poszczególnych klas oraz nauczycieli. Taki wła-
śnie wynikowy genotyp z

rozkodowanymi rozkładami zajęć dla wszystkich klas

i nauczycieli przedstawia rysunek 1. Na jego podstawie można stwierdzić np., iż klasa c

ma w poniedziałek na pierwszych trzech lekcjach w sali s

geografię z nauczycielem t

Termin

Poniedz. Wtorek Środa Czwartek

Piątek

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 11 0

6 0 0 12 0 0 0

3 0 0

2 0 0 0 1 0 0

sale

4 0 8 0 0 0 7 0 0 0 5 0 0 0 0 9 0 0

4 12 7 2 10 1

kla c

6 8 3 5 9 11

12 3 2

10 1

8 7 5 9 11

nau

Rys. 1. Przykładowy genotyp z rozkodowanymi rozkładami zajęć

2.2. Inicjalizacja genotypu

W systemie PLANIX zaimplementowano deterministyczno-losową strategię inicjali-

zacji genotypu. Każde zajęcie zostało umieszczone w jednej z przyporządkowanych temu
zajęciu sal tak, aby termin i sala, w którym ma ono zostać umieszczone nie był zabroniony
dla danej klasy, nauczyciela bądź sali. Należy zatem w odpowiedni sposób wybierać kolej-
ne zajęcia, aby nie doszło do sytuacji, w której to zabraknie miejsca w pewnych salach,
bądź niektóre terminy zostaną zablokowane. Na początku rozmieszczane są zajęcia, które
mogą odbywać się tylko w jednej sali. Spośród tych zajęć pierwszeństwo mają te, których
czas trwania wynosi 3 godziny lekcyjne. Następnie kolejno umieszczane są zajęcia
2-lekcyjne oraz 1-lekcyjne. Proces ten powtarza się dla zajęć, które mogą odbywać się
w dwóch, trzech salach itd., aż w genotypie zostaną umieszczone wszystkie zajęcia.

2.3. Funkcja oceny

Podczas konstrukcji planu musi być spełniony szereg różnych warunków. Dzieli się je

na dwie grupy [1]:

• twarde – takie, które muszą być spełnione, aby rozkład był dopuszczalny,

• miękkie – takie, które powinny być spełnione, a liczba ewentualnych niespełnionych

ograniczeń jest minimalizowana.

- 47 -

Funkcja oceny w systemie PLANIX (1) jest funkcją opartą na sumie dwóch funkcji

ważonych: funkcji kary twardej oraz funkcji kary miękkiej.

f = f

twarda

+ f

miekka

(1)

gdzie: f - funkcja oceny, f

twarda

– funkcja kary twardej, f

miekka

– funkcja kary miękkiej

Ze względu na rodzaj reprezentacji genotypu oraz sposób jego inicjalizacji większość

ograniczeń twardych jest spełnionych. Dwa różne zajęcia nigdy nie będą się odbywały
w tej samej sali, gdyż każdy chromosom w genotypie reprezentuje inną salę. Pewne jest
również, iż każdy nauczyciel ma odpowiednią liczbę zajęć z każdą klasą, ponieważ właśnie
takie pary klasa-nauczyciel umieszczane są w genotypie. Ponadto okres trwania poszcze-
gólnych zajęć jest zawsze odpowiedni, gdyż podczas inicjalizacji, zajęcia w genotypie
umieszczane są na tylu genach, ile godzin trwa dane zajęcie. Sposób inicjalizacji genotypu
zapewnia nam również, iż zajęcia odbywają się w jednej z dozwolonych sal oraz, iż nie
odbywają się w terminach, w których ze względu na odgórnie ustaloną niedostępność sal,
nauczycieli bądź terminów, nie mogą się odbywać.

Sposób reprezentacji oraz inicjalizacji genotypu nie zapewnia jednak stworzenia osią-

galnego planu. Dlatego w systemie PLANIX zaimplementowano odpowiednie algorytmy
oceniające następujące twarde konflikty:

• konflikt nauczycieli (k

nau

) – jednoczesne prowadzenie wielu zajęć w tym samym ter-

minie przez tego samego nauczyciela,

• konflikt klas (k

kla

) – jednoczesne odbywanie się wielu zajęć w tym samym terminie

przez tę samą klasę.

Po wyznaczeniu wartości konfliktów nauczycieli oraz klas dla wszystkich zajęć

w genotypie wyznacza się łączną karę twardą dla danego genotypu (2). Aby dany genotyp
reprezentował dopuszczalny plan zajęć, funkcja ta musi mieć wartość równą zero.

(

)

∑

−

kla

nau

twarda

(2)

gdzie: n

- liczba zajęć, w

nau

, w

kla

- wagi konfliktu nauczycieli oraz klas, k

nauz

, k

klaz

- liczba poszcze-

gólnych konfliktów dla danego zajęcia

Podobnie jak wśród ograniczeń twardych, również dla ograniczeń miękkich można

wyróżnić kilka rodzajów konfliktów:
• konflikt okienek klas (k

okk

) – klasy nie powinny mieć okienek,

• konflikt godzin początkowych (k

gpo

) – klasy powinny zaczynać zajęcia na pierwszej

godzinie lekcyjnej,

• konflikt równomierności (k

rów

) – zajęcia dla poszczególnych klas powinny być rów-

nomiernie rozłożone na wszystkie dni tygodnia,

• konflikt przedmiotów (k

prz

) – dla tej samej klasy zajęcia z tego samego przedmiotu

powinny być równomiernie rozłożone,

• konflikt okienek nauczycieli (k

okn

) – nauczyciele nie powinni mieć okienek,

• konflikt ilości (k

ilo

) – nauczyciel nie powinien przekraczać pewnej dziennej liczby

zajęć w ciągu dnia.

- 48 -

2.4. Selekcja i procedury reprodukcji

W systemie PLANIX zastosowano selekcję metodą rankingową. Liczba kopii każdego

osobnika wprowadzana do puli rodzicielskiej ustalana jest w następujący sposób: każdy
kolejno lepszy osobnik, ma tyle razy większe szanse wejścia od swojego słabszego po-
przednika, ile wynosi współczynnik selekcji. Wynika z tego, iż dla współczynnika selekcji
równego jeden, każdy z osobników ma taką samą szansę znalezienia się w wyselekcjono-
wanej populacji.

Poza tym w systemie PLANIX zastosowano elitarną strategię reprodukcji. Najlepszy

osobnik zawsze trafia do puli rodzicielskiej, a dodatkowo nie podlega on procesowi krzy-
żowania i mutacji, aby nie zostać zatraconym (na wypadek jakby operatorom krzyżowania
i mutacji nie udało się stworzyć lepszego osobnika). Dodatkowo osobnik ten może się zna-
leźć w puli rodzicielskiej i podlegać normalnemu procesowi ewolucyjnemu.

2.5. Operatory krzyżowania i mutacji

W systemie PLANIX zastosowano krzyżowanie równomierne, tzn. krzyżowaniu pod-

legają po kolei wszystkie zajęcia, dla danej pary rodziców, z prawdopodobieństwem 50%
znalezienia się w każdym z dwóch nowych potomków.

Algorytm mutacji oprócz właściwości zwykłego operatora mutacji, posiada cechy

operatora częściowej wymiany populacji oraz operatora inwersji. Najpierw dla poszczegól-
nych genotypów podejmowana jest losowa decyzja, czy w danym osobniku ma zajść czę-
ściowa wymiana populacji, czy też zwykła mutacja. W przypadku pierwszej opcji pewna
liczba genów (zgodnie z prawdopodobieństwem wymiany zajęcia) poddawana jest zwykłej
mutacji. Takie postępowanie zapobiega zbieżności populacji, a co za tym idzie powoduje
ucieczkę z lokalnego minimum. Jeśli jednak dany osobnik nie zostanie poddany procedurze
wymiany populacji, wtedy zajęcie po zajęciu, z pewnym prawdopodobieństwem, poddawa-
ne jest operatorowi mutacji. Dla pojedynczego zajęcia losowany jest nowy, wolny termin.
Jeżeli wylosowany termin jest już zajęty następuje inwersja dwóch zajęć, zawsze z zacho-
waniem reguł opisanych w procesie inicjalizacji.

3. STROJENIE ALGORYTMU GENETYCZNEGO

3.1. Analiza procesu tworzenia planu dla różnych parametrów ewolucji

Wszystkie eksperymenty przeprowadzone zostały na populacji stu osobników. Ewolu-

cja w każdym przypadku przebiega bardzo podobnie. Na początku następuje gwałtowny
skok średniej wartości funkcji kary. Zjawisko to bierze się zapewne stąd, iż w procesie
inicjalizacji powstają osobniki, które znacznie różnią się od siebie układem poszczególnych
zajęć. Na skutek tego, w początkowej fazie algorytmu, podczas krzyżowania dwóch do-
brych osobników, powstają osobniki o wiele słabsze. Sytuacja taka powtarza się gdzieś do
120 pokolenia, kiedy to osobniki z populacji zaczynają być do siebie coraz bardziej podob-
ne. Od tego momentu następuje poprawa wartości funkcji kary najlepszego osobnika.

Analizując wpływ poszczególnych parametrów ewolucji na przebieg ewolucji otrzy-

mano następujące wartości: współczynnik selekcji – 0,75, prawdopodobieństwo krzyżowa-
nia – 1, prawdopodobieństwo mutacji – 0,0012, prawdopodobieństwo wymiany populacji –
0, prawdopodobieństwo wymiany zajęcia – 0.

Okazuje się zatem, iż zastosowanie algorytmu wymiany populacji oraz wymiany zaję-

cia nie znalazło w tym przypadku zastosowania. Prawdopodobieństwo krzyżowania ustalo-
ne zostało na 1, jednak podobne wartości otrzymano przy wartości 0.5. Jednak zdecydowa-

- 49 -

no się na krzyżowanie wszystkich osobników ze względu na większą liczbę lepiej przysto-
sowanych osobników w wyższych iteracjach algorytmu.

3.2. Działanie algorytmu a wagi poszczególnych typów konfliktów

Na początek należy przyjrzeć się dokładnie jak zmieniają się wartości poszczególnych

konfliktów, przy jednostkowych wartościach wag. W takim przypadku liczba konfliktów
nauczycieli jest około dwa razy mniejsza od liczby konfliktów klas. Wartości obydwu tych
konfliktów bardzo szybko osiągają wartość zerową. Ponieważ te dwa konflikty są jedynymi
konfliktami twardymi, zatem można wysnuć wniosek, iż dosyć łatwo jest znaleźć plan
osiągalny. Poza tym, w czasie spadku liczby konfliktów twardych, dość znacznie wzrasta
liczba okienek klas oraz nauczycieli, natomiast maleje wartość konfliktu godzin początko-
wych. Największą wartość przez całą ewolucje utrzymuje konflikt przedmiotów. Jest to
pewien sygnał, iż waga tego konfliktu powinna mieć większą wartość. Jedynym konflik-
tem, na którego zmianę wartości nie mają wpływu zmiany wartości innych typów konflik-
tów jest konflikt ilości. Przez cały okres działania algorytmu jego wartość utrzymuje się na
stałym, bardzo niskim poziomie.

Tablica 1. Przebieg ewolucji przy dominacji poszczególnych konfliktów wraz
z ostatecznymi ich wagami

Konflikt
dominu-

jący

Różnice pomiędzy przebiegiem ewolucji

w stosunku dla jednostkowych wartości

wag poszczególnych konfliktów

Wnioski

Osta-

teczna

waga

nau

bez zmian

brak

kla

dwukrotne zwiększenie ilości oraz czasu
redukcji konfliktu nauczycieli

należy tak dobierać wagę tego konflik-
tu aby była wyższa od wagi konfliktu
nauczycieli

prz

wartość konfliktu po inicjalizacji 0;
czterokrotne zwiększenie wartości kon-
fliktów twardych; znalezienie planu
osiągalnego po 700 iteracjach; duże
wartości konfliktów okienek klas
i nauczycieli

waga tego konfliktu powinna mieć
wartość niewiele większą od pozosta-
łych wag

okk

wartość konfliktu po inicjalizacji 0; brak
planu osiągalnego po 1000 iteracjach

waga konfliktu nie powinna być więk-
sza od wag pozostałych konfliktów

gpo

brak planu osiągalnego po 1000 itera-
cjach

waga konfliktu nie powinna być więk-
sza od wag pozostałych konfliktów

rów

znalezienie planu osiągalnego zajmuje
700 iteracji; szybkie sprowadzenie do
zera wysokiej wartości konfliktu klas;

dopuszczalna dominacja tego konfliktu

okn

podobny przebieg ewolucji jak dla do-
minacji konfliktu okienek klas; również
brak planu osiągalnego

waga konfliktu powinna być większa
od wag pozostałych konfliktów

ilo

brak planu osiągalnego

waga konfliktu nie powinna być więk-
sza od wag pozostałych konfliktów

W dalszej kolejności badano jaki wpływ na ewolucję będzie miało czterokrotne

zwiększenie wagi jednego z konfliktów (pozostałe wartości jednostkowe). Opisaną sytu-
ację wraz z wnioskami i opisem ewolucji oraz ostatecznie ustalonymi wagami poszczegól-
nych typów konfliktów przedstawia tablica 1.

- 50 -

4. WNIOSKI KOŃCOWE

Podsumowując, w pełni automatyczny, oparty o algorytm genetyczny system PLA-

NIX układa plan w kilka minut. Stworzony rozkład zajęć nie łamie żadnych twardych
ograniczeń, a więc jest planem osiągalnym. Natomiast ograniczenia miękkie program stara
się jak najbardziej zminimalizować, poprawiając w ten sposób jakość ułożonego planu.

Samo oprogramowanie wymaga jeszcze pewnego dopracowania, aby można je było

stosować do układania planu lekcji w szkołach. Powinna pojawić się możliwość uczestni-
czenia klasy w więcej niż jednym zajęciu w danym czasie (lekcje dzielone) oraz możliwość
prowadzenia przez jednego nauczyciela zajęć w więcej niż jednej klasie w tym samym
czasie (fakultety). Dodatkowo w programie należy dodać opcję wydruku stworzonego
planu i to zarówno w postaci tzw. płachty jak i plany poszczególnych klas i nauczycieli.
Warto byłoby również dodać opcję eksportowania gotowego planu do formatu Microsoft
Excel oraz do formatu HTML, dającego możliwość publikacji w Internecie.

Opisana metoda z

powodzeniem może znaleźć zastosowanie w

problemach

o mniejszej skali złożoności, takich jak: planowanie dyżurów w szpitalu, harmonogramo-
wanie obłożenia obiektów w klubie sportowym, itp. Jej mocną stroną jest duża elastyczność
i spora, jak na algorytm genetyczny, szybkość działania.

5. BIBLIOGRAFIA

1. Burke E. K., Elliman D. G., Weare R.: a Genetic Algoritm Based University Time-

tabling System, Practice and Theory of Automated Timetabling, 1996, ISBN

35-406-

1794-9.

2. Goldberg D. E.: Algorytmy genetyczne i ich zastosowania, Warszawa WNT1998,

ISBN 83-204-2843-2.

3. Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne,

Warszawa WNT 1999, ISBN 83-204-2881-5.

4. Rutkowska D., Piliński M., Rutkowski L.: Sieci neuronowe, algorytmy genetyczne

i systemy rozmyte, Warszawa PWN 1997, ISBN 93-01-12304-4.

USING GENETIC ALGORITHM IN AUTOMATED SCHOOL-TIMETABLING

This paper focuses on using genetic algorithm in automated school-timetabling. We

provide PLANIX – program which compose finished schedule in several minutes. This
paper describes core of program including ways of representation, coding and initialization,
contruction of fitness function, selection and reproduction procedures. We also present
results of our resarch for choosing series of different parameters.

Document Outline