Efektywne planowanie kursów uniwersyteckich

Question

Obecnie pracuję nad stroną internetową, która pozwoli studentom z mojej uczelni automatycznie generować ważne harmonogramy w oparciu o kursy, które chcą wziąć.

Zanim przystąpiłem do pracy nad samą stroną, postanowiłem poruszyć kwestię efektywnego planowania kursów.

Kilka wyjaśnień:

1. Każdy kurs na naszej uczelni (i zakładam na każdym innym uniwersytetu) składa się z jednej lub więcej części. Na przykład: Rachunek I ma obecnie 4 sekcje. Oznacza to, że w zależności od ilości sekcji i tego, czy kurs ma laboratorium, ma to znaczący wpływ na proces planowania.

2. Kursy na naszej uczelni są reprezentowane za pomocą kombinacji skrótu do przedmiotu i kodu kursu. W przypadku rachunku różniczkowego I: MATH 1110.

3. CRN to kod unikalny dla sekcji.

4. Uczelnia, na której się uczę, nie jest mieszana, co oznacza, że ​​mężczyźni i kobiety studiują w (prawie) oddzielnych kampusach. Chodzi mi o to, że kampus dzieli się na dwie części.

5. Dices baz danych i dyktafonów mają na celu zmniejszenie liczby wywołań datetime.datetime.strptime(), co było prawdziwym wąskim gardłem.

Moja pierwsza próba polegała na tym, że algorytm zapętlał w sposób ciągły, aż znaleziono 30 harmonogramów. Harmonogramy zostały utworzone przez losowe wybieranie sekcji z jednego z wprowadzonych kursów, a następnie próby umieszczenia sekcji z pozostałych pól w celu utworzenia prawidłowego harmonogramu. Jeśli nie wszystkie kursy pasują do harmonogramu, np. Wystąpiły konflikty, harmonogram został złomowany, a pętla kontynuowana.

Oczywiście, powyższe rozwiązanie jest wadliwe. Algorytm trwał zbyt długo i polegał zbytnio na losowości.

Drugi algorytm działa dokładnie przeciwnie niż stary. Po pierwsze generuje kolekcję wszystkich możliwych kombinacji harmonogramów za pomocą itertools.product(). Następnie przechodzi przez harmonogramy, wykreślając wszelkie nieważne. Aby zapewnić różne sekcje, kombinacje zestawów są przetasowane (random.shuffle()) przed sprawdzeniem poprawności. Ponownie, w grę wchodzi nieco losowości.

Po odrobinie optymalizacji udało mi się uruchomić program planujący w czasie poniżej 1 sekundy dla przeciętnego harmonogramu składającego się z 5 kursów. To świetnie, ale problem zaczyna się po dodaniu kolejnych kursów.

Aby dać wyobrażenie, kiedy dostarczyć pewien zestaw wejść, ilość możliwych kombinacji jest tak duża, że ​​itertools.product() nie kończy w rozsądnym czasie i zjada 1GB RAM w tym procesie.

Oczywiście, jeśli mam zamiar zrobić to usługa, potrzebuję szybszego i bardziej wydajnego algorytmu. Dwa, które pojawiły się w Internecie i na IRC: dynamiczne programowanie i algorytmy genetyczne.

Programowanie dynamiczne nie może być zastosowane do tego problemu, ponieważ, jeśli dobrze rozumiem tę koncepcję, polega ona na rozbiciu problemu na mniejsze części, rozwiązaniu tych elementów indywidualnie, a następnie doprowadzeniu rozwiązań tych elementów do siebie w celu stworzenia kompletnego rozwiązania . O ile widzę, nie ma tu zastosowania.

Jeśli chodzi o algorytmy genetyczne, nie rozumiem ich zbyt wiele i nie mogę nawet pojąć, jak je zastosować w takiej sytuacji. Rozumiem również, że GA może być bardziej wydajne w przypadku bardzo dużej przestrzeni problemowej, a to nie jest duże.

Jakie mam alternatywy? Czy istnieje dość zrozumiałe podejście, które mogę podjąć, aby rozwiązać ten problem? Czy powinienem po prostu trzymać się tego, co mam i mam nadzieję, że niewiele osób zdecyduje się na 8 kursów w następnym semestrze?

Nie jestem świetnym pisarzem, więc przepraszam za wszelkie niejasności w pytaniu. Proszę poprosić o wyjaśnienia, a dołożę wszelkich starań, aby pomóc.

Oto kod w całości.

http://bpaste.net/show/ZY36uvAgcb1ujjUGKA1d/

Uwaga: Przepraszam za korzystanie mylący tag (harmonogramu).

Answer 1

Czy kiedykolwiek czytałeś coś o programowaniu genetycznym? Pomysł polega na tym, że pozwalasz, aby "rzecz", którą chcesz rozwiązać, ewoluowała, sama przez się, dopóki nie rozwinęła się do najlepszego możliwego rozwiązania.

Generujesz tysiąc harmonogramów, z których zazwyczaj zero jest w dowolnym miejscu we właściwym kierunku. Następnie losowo zmieniasz "niektóre" kursy. Z tych nowych harmonogramów wybierasz jedne z najlepszych na podstawie ocen, które podajesz zgodnie z "dobroci" harmonogramu. Następnie pozwalasz im się rozmnażać, łącząc niektóre kursy z obu harmonogramów. Kończy się tysiącem nowych harmonogramów, ale wszystkie one są odrobinę mniejsze od tych, które miałeś. Niech się powtórzy, dopóki nie będziesz zadowolony, i wybierz harmonogram z najwyższą oceną z ostatniego tysiąca, który wygenerowałeś.

W grę wchodzi losowość, ale harmonogramy są coraz lepsze, bez względu na to, jak długo można uruchomić algorytm. Podobnie jak w prawdziwym życiu i organizmach istnieje przetrwanie najsilniejszych i możliwe jest oglądanie różnych ogólnych "wątków" tego samego rodzaju harmonogramu, który jest tak dobry, jak inny wygenerowany. Dwa bardzo różne harmonogramy mogą wreszcie "walczyć" poprzez krzyżowanie.

Projekt obejmujący harmonogram szkolnych i programowania genetycznego: http://www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm

myślę, że całkiem dobrze wyjaśnić, co trzeba.

Moja ostatnia uwaga: Myślę, że to bardzo ciekawy projekt. Jest to dość trudne do zrobienia, ale gdy już to zrobimy, to po prostu świetnie jest widzieć, jak twoje rozwiązanie ewoluuje, tak jak w prawdziwym życiu. Powodzenia!

Answer 2

To jest trudny problem. W Google coś takiego jak "papier do planowania zadań kursu" znajdziesz wiele referencji. Algorytm genetyczny - nie, programowanie dynamiczne - tak. GA są znacznie trudniejsze do zrozumienia i wdrożenia niż standardowe algos DP. Zwykle ludzie, którzy używają GA po wyjęciu z pudełka, nie rozumieją standardowych technik. Zrób trochę badań, a znajdziesz różne algorytmy. Być może uda Ci się znaleźć jakieś implementacje. Wymyślanie własnego algorytmu jest znacznie trudniejsze niż wkładanie wysiłku w zrozumienie DP.

Answer 3

Scheduling to bardzo znany constraint satisfaction problem, który jest ogólnie NP-Complete. Wykonano wiele prac na ten temat, nawet w tym samym kontekście, co Ty: Solving the University Class Scheduling Problem Using Advanced ILP Techniques. Istnieje nawet textbooks na ten temat.

Ludzie podjęły wiele podejść, w tym:

• Dynamic programming
• Genetic algorithms
• Neural networks

Trzeba zmniejszyć przestrzeń problemów i komplikacji. Podaj jak najwięcej założeń, jak to możliwe (maksymalna ilość zajęć, czas blokowy, itd.). Dla tego problemu nie ma srebrnej kuli, ale powinno być możliwe znalezienie prawie optymalnego rozwiązania.

Niektóre półfabrykaty niedawne publikacje:

• QUICK scheduler a time-saving tool for scheduling class sections
• Scheduling classes on a College Campus

Answer 4

Sposób aktualnie generowania kombinacji sekcji jest zapewne rzuca się ogromnej liczby kombinacji, które są wyłączone przez konflikty pomiędzy więcej niż jednym kursem. Myślę, że możesz zmniejszyć liczbę kombinacji, z którymi musisz się uporać, generując najpierw produkt z sekcji tylko dla dwóch kursów. Wyeliminuj konflikty z tego zestawu, a następnie wprowadź sekcje dotyczące trzeciego kursu. Wyeliminuj ponownie, następnie wprowadź czwartą i tak dalej. Powinno to spowodować bardziej liniowy wzrost czasu przetwarzania, ponieważ liczba wybranych kursów wzrasta.

Answer 5

Problem, który opisujesz, to problem z ograniczeniem ograniczeń. Moje podejście byłoby następujące:

• Sprawdź, czy nie ma żadnych uncompatibilities pomiędzy kursami, a jeżeli tak, zapisz je jako ograniczenia lub łuków
• ile nie zostanie znalezione rozwiązanie:
  • Wybierz kurs z mniej więzów (czyli ma mniej uncompatibilities z innych kursów)
  • uruchomić algorytm AC-3, aby zmniejszyć przestrzeń poszukiwań

Próbowałem tego podejścia z rozwiązywaniem sudoku i działało (rozwiązało najtrudniejsze sudoku na świecie w mniej niż 10 sekund)