Какие классы алгоритмов можно использовать для хронометража?

Question

Да, таких вопросов много на SO.Я видел генетические алгоритмы были наиболее распространенные ответы.

Составление расписания расписания и

Алгоритм создания расписания школы

---

Однако меня беспокоят эти характеристики условия завершения программы GA

• , которые трудно определить
• не может легко избежать локальных максимумов

Я ожидаю, что пользователи столкнутся с противоречивыми критериями и невозможными решениями слишком легко пользователями.

Поэтому я хочу метод, который

• является решающим - гарантированно достигнет почти оптимальной ситуации или сообщит, что алгоритм не достигнет решения
• может принять оба решения (нерушимые) пределы и мягкие пределы
• элегантно принимает ограничения пользовательского ввода;если пользовательский ввод не работает, его можно добавить в код, не нарушая его

Существует 100000 возможных вариантов расписаний.

---

Я искал и увидел, что метаэвристические алгоритмы как имитация отжига являются хорошим кандидатом.А как насчет алгоритмов динамического программирования?

Можно ли использовать метод грубой силы для такого набора данных?

Какой хороший алгоритм может соответствовать критериям?

Answer 1

Для небольшого ввода , с только 100 000 возможностей - я бы выбрал простое решение перебор : просто проверьте все возможности и выберите лучший из них.Для современных машин запуск функции оценки на входе размером 100 000 не сложен в вычислительном отношении и, скорее всего, займет всего несколько секунд.

GA и другие алгоритмы ИИ обычно используются для намного большего ввода [миллиарды и больше возможностей], поэтому они могут быть не лучшим решением в вашем случае.

В отличие от любого другого решения, решение с использованием грубой силы обеспечит вам оптимальное решение и будет прекращено после исчерпания всех возможных решений.

(*) Примечание: вы можете изменить GA и крутое восхождение восхождение на гору чтобы преодолеть вторую проблему, о которой вы упомянули [выход из локальных максимумов] путем принудительного выполнения случайного перезапуска , когда решение не улучшается за k шагов, но опять же - вы не будете знать, насколько вы близки к оптимальномурешение в каждой точке.