Я планирую разработать экспертную систему, которая автоматически подстраивается под рабочую нагрузку преподавателей школы (время, учебная нагрузка и т. д.) и генерировать классные секции, комнаты, которые по крайней мере на 90% соответствуют тому, что директор определенного отдела хочет назначить расписание на определенный семестр.
Какой алгоритм использовать? Эвристика? Оптимизация? Любые предложения или помощь высоко ценятся!
Два моих друга сделали что-то подобное для классного проекта. Они использовали эвристику имитация отжига. Они пришли к выводу, что это может быть не лучший инструмент для работы.
Эй, знать, что нельзя делать, может быть полезно, верно? :)
Вот некоторые общие наблюдения:
1) Ручное планирование редко делается с нуля. Вместо этого кто-то начинает с графика за предыдущий год и изменяет его с учетом изменений в требованиях. Один из способов имитировать это с помощью компьютера — использовать алгоритм восхождения на холм, который неоднократно пытается внести ряд небольших изменений, чтобы улучшить решение на данный момент. Это может быть запущено по текущему расписанию.
2) Завершается ли когда-либо ручной процесс выводом о том, что требования в совокупности невыполнимы и что некоторые из них должны быть исключены? В этом случае ваш алгоритм должен быть достаточно прозрачным, чтобы можно было понять ошибки, или, по крайней мере, быть способным предлагать такие изменения (например, путем максимизации штрафной функции, которая позволяет получить «наименее плохое» решение, которое не удовлетворяет всем исходным ограничениям). ). Я знаю один случай, когда сложный подход, основанный на ограничениях, был заменен гораздо более простым алгоритмом, потому что сбои системы, основанной на ограничениях, не давали достаточной обратной связи с пользователем.
3) Как ни странно, система следующего поколения вообще не использовала сложное планирование. Оказалось, грубо говоря, что в то время, когда нужно было принимать решения, нельзя было предвидеть все последствия сложных решений по планированию, и в долгосрочной перспективе простой предсказуемый график, который можно было поддерживать бесконечно, был более продуктивным, чем постоянно перестраивайте графики, чтобы получить небольшие сиюминутные преимущества.
Взгляните на учебный курс планирование уроков, пример Drools Planner (с открытым исходным кодом, боюсь, Java) . Он использует метаэвристики, такие как simulated annealing и tabu search.
Вот статья о динамическом планировании с использованием генетических алгоритмов... вы можете найти некоторые идеи здесь полезными... даже если домен не тот же самый, я думаю, что эта идея применима в более общем плане.
