Решение проблем планирования: введение в решение Drools

Задумывались ли вы о том, как они планируют поезда? Они должны минимизировать общение между любыми двумя соответствующими железнодорожными станциями, соблюдая при этом ограничения своих ресурсов: размеры поездов, скорость поездов, физическое местоположение поездов, рабочие часы сотрудников, квалификация сотрудников, занятость платформ железнодорожных станций, еженедельное техническое обслуживание, … ,

Вы когда-нибудь пытались спланировать встречу, просто чтобы обнаружить, что в один день, когда все участники могут присутствовать, все комнаты для собраний заняты? Или нет доступного бимера?

Мир полон проблем планирования.

В этой статье я сосредоточусь на решении очень простого графика урока:

• В школе есть учителя, ученические группы и куча уроков (которые объединяют 1 учителя с 1 ученической группой). Эти уроки должны соответствовать ограниченному количеству временных интервалов.

• Цель состоит в том, чтобы избежать конфликтов: учитель не может преподавать 2 урока в одном и том же временном интервале, а ученическая группа также не может посещать 2 урока в одном и том же временном интервале.

Размер имеет значение

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

Например, давайте возьмем среднюю школу с 30 ученическими группами, 40 учителями и 33 временными интервалами. Каждая группа студентов имеет урок в каждом временном интервале, который составляет 990 уроков. Во сколько разных способов можно запланировать эти 990 уроков в 33 временных интервала? Другими словами, сколько у него возможных решений? Ну, этот пример имеет 33 ^ 990 или чуть более 2e1503 возможных решений. Да, для средней школы это число 2 с 1503 нулями за ним!

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

Алгоритмы планирования

Существуют разные способы решения проблемы планирования:

• Случайно: Там нет всеобъемлющей сущности, которая планирует систему. Например, трафик решается почти случайным образом: каждый выбирает свой маршрут и время отправления по своему усмотрению. Если вы когда-либо ездили по крупному городу, один раз в час пик и один раз в час после часа пик, вы знаете, что это далеко не оптимально.

• Исчерпывающий: с помощью грубой силы каждое возможное решение оценивается для определения оптимального решения. На практике это просто не работает: если бы мы могли оценивать миллиард возможных решений каждую миллисекунду, все равно потребовалось бы более 611483 лет, чтобы оценить все возможные решения для нашей средней школы. Даже умные исчерпывающие алгоритмы, такие как ветвление и связывание, занимают много времени.

• Детерминированный: ресурсы вкладываются в планирование на основе простых правил. Решение далеко от оптимального, но иногда оно «достаточно хорошее». Например, пациенты в клинике проходят лечение в очереди FIFO (первым пришел, первым обслужен), но пациенты неотложной помощи перемещаются в начало очереди. В нашем примере расписания занятий мы могли бы запланировать один урок за раз, назначив ему временной интервал, в котором еще нет урока с тем же учителем или группой учащихся. Однако, скорее всего, мы получим уроки, которые нельзя назначить.

• Метаэвристический: алгоритм анализирует возможные решения интеллектуальным способом и запоминает лучшее решение, с которым он сталкивается. Он решает, какие решения посетить, руководствуясь оценкой уже встреченных решений. Существуют различные метаэвристические алгоритмы, такие как поиск по табу, имитированный отжиг, оптимизация колоний муравьев, генетические алгоритмы … Например, жадный алгоритм начинается со случайного решения и оценивает каждое решение, которое перемещает 1 урок в другой временной интервал, и принимает лучшее из этих решений в качестве нового решения, чтобы продолжить с.

На практике обычно рекомендуется начинать с детерминированного алгоритма и улучшать его с помощью метаэвристического алгоритма.

Представляем Drools Solver

Drools Solver — это библиотека Java с открытым исходным кодом, которая поможет вам решать задачи планирования с помощью метаэвристических алгоритмов. API еще не полностью стабилен, но уже есть полное руководство и 5 обширных примеров.

Расчет балла

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

rule "multipleLessonsPerTeacherPerTimeslot"
  when
    $l : Lesson($id : id, $t : teacher, $ts : timeslot);
    exists Lesson(id > $id, teacher == $t, timeslot == $ts);
  then
    insertLogical(new UnweightedConstraintOccurrence(
        "multipleLessonsPerTeacherPerTimeslot", $l
    ));
end

Обратите внимание, что правило обнаружения групповых конфликтов студентов не смешивается с этим: оно полностью разделено. И поскольку правила не определяют, как они должны быть обнаружены, механизму правил Drools остается использовать циклы for, хэш-таблицы или что-то гораздо более эффективное (например, сеть ReteOO).

Табу поиск

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

<localSearchSolver>
  <scoreDrl>.../lessonScheduleScoreRules.drl</scoreDrl>
  <finish>
    <maximumSecondsSpend>300</maximumSecondsSpend>
  </finish>
  ...
  <accepter>
    <completeSolutionTabuSize>1000</completeSolutionTabuSize>
  </accepter>
</localSearchSolver>

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

Начиная

Хотите узнать больше о Drools Solver? Взгляните на руководство или запустите примеры пакета загрузки. Ваша обратная связь всегда приветствуется в списке рассылки пользователей Drools.

• Справочное руководство: http://users.telenet.be/geoffrey/tmp/solver/manual/html_single/

• Загрузить: http://www.jboss.org/drools/downloads.html

• Список рассылки через Gmane: http://dir.gmane.org/gmane.comp.java.drools.user

Об авторе

Он занял 4- ^е место на экзаменационной трассе Международного конкурса хронометража 2007 года с ранней версией Drools Solver.