algorytm genetyczny do kompozycji rozkładu zajęć - algorytm, optymalizacja, genetyka

Piszę wniosek o automatyczny rozkład zajęć uniwersyteckich i używam tego algorytmu genetycznego, ale teraz miałem pewne problemy z realizacją.

Na samym początku założyłem, że mamyklasy z czasem trwania 1 przedziału czasowego (przedział czasowy = 1 godzina) i możemy po prostu umieścić go w tablicy (reprezentuje harmonogram siatki: tablica 1-d z pojemnością numberOfRooms * numberOfDays * numberOfTimeslots) i może wykonywać mutację i zwrotnicę, jak również bez problemy.

Ale wiem, że chcę poprawić aplikację i pozwolić na zajęcia z czasem trwania kilku przedziałów czasowych. Tutaj przychodzi wiele problemów:

Jak możemy umieścić jeden obiekt klasy w tablicy iwypełnić wszystkie gniazda (kilka komórek tablicowych), które klasa musi zająć (jeden obiekt - kilka komórek)? I w jaki sposób umieścimy to w szyku, jak można przeprowadzić mutację i zwrotnicę? Z góry dziękuję! Doceniam twoją pomoc!

Odpowiedzi:

Dobrą zasadą może być przekroczenie tylko klas, które mają równe przedziały czasowe. Możesz na przykład przejść przez klasę, która zajmuje dwa miejsca z dwiema klasami, które zajmują jeden przedział czasowy.

Reprezentować klasy mające czas trwania wieluAutomaty do gry, najprostszym, ale trudnym sposobem jest posiadanie flagi, która dla każdego przedziału czasowego powie ci, czy przedział czasowy jest zajęty przez nową klasę, czy tylko kontynuacją klasy, która rozpoczęła się wcześniej. Po przejściu na drugą stronę obejrzysz tę flagę, aby upewnić się, że nie przekraczasz części klas.

Innym (lepszym) sposobem jest tworzenie bardziej złożonej struktury danych: DailyRoomOccupation. Ta struktura danych będzie zawierać:

• dzienna pojemność pomieszczenia, wyrażona w liczbie przedziałów czasowych;
• a (podwójnie połączona) lista zajęć zaplanowanych na ten dzień w tym pokoju;
• funkcja, która oblicza, czy klasy na liście zmieszczą się w przedziałach czasowych;
• funkcja, która pozwala na krzyżowanie dwóch różnych DailyRoomOccupations, dbając o przekroczenie tylko równych ilości przedziałów czasowych.