1. Введение в OptaPlanner
В этом руководстве мы рассмотрим решатель удовлетворения ограничений Java под названием OptaPlanner .
OptaPlanner решает проблемы планирования, используя набор алгоритмов с минимальной настройкой.
Хотя понимание алгоритмов может дать полезную информацию, инфраструктура выполняет за нас тяжелую работу.
2. Зависимость от Maven
Во-первых, мы добавим зависимость Maven для OptaPlanner:
<dependency>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner-core</artifactId>
<version>7.9.0.Final</version>
</dependency>
Мы находим самую последнюю версию OptaPlanner из репозитория Maven Central .
3. Класс проблемы/решения
Для решения задачи нам обязательно нужен конкретный пример.
Расписание лекций является подходящим примером из-за сложности балансировки ресурсов, таких как помещения, время и учителя.
3.1. Расписание курсов
CourseSchedule содержит комбинацию наших проблемных переменных и объектов планирования, следовательно, это класс решения. В результате мы используем несколько аннотаций для его настройки.
Рассмотрим подробнее каждый в отдельности:
@PlanningSolution
public class CourseSchedule {
private List<Integer> roomList;
private List<Integer> periodList;
private List<Lecture> lectureList;
private HardSoftScore score;
Аннотация PlanningSolution сообщает OptaPlanner , что этот класс содержит данные для включения решения.
OptaPlanner предполагает наличие этих минимальных компонентов: объект планирования, факты о проблемах и оценка.
3.2. Лекция
Лекция, POJO, выглядит так:
@PlanningEntity
public class Lecture {
public Integer roomNumber;
public Integer period;
public String teacher;
@PlanningVariable(
valueRangeProviderRefs = {"availablePeriods"})
public Integer getPeriod() {
return period;
}
@PlanningVariable(
valueRangeProviderRefs = {"availableRooms"})
public Integer getRoomNumber() {
return roomNumber;
}
}
Мы используем класс Lecture в качестве объекта планирования, поэтому мы добавляем еще одну аннотацию к получателю в CourseSchedule :
@PlanningEntityCollectionProperty
public List<Lecture> getLectureList() {
return lectureList;
}
Наш объект планирования содержит устанавливаемые ограничения.
Аннотации PlanningVariable и аннотации valueRangeProviderRef связывают ограничения с фактами проблемы.
Эти значения ограничений будут позже оценены по всем объектам планирования.
3.3. Факты о проблеме
Переменные roomNumber и period действуют как ограничения аналогично друг другу.
OptaPlanner оценивает решения в результате логики с использованием этих переменных. Мы добавляем аннотации к обоим методам получения :
@ValueRangeProvider(id = "availableRooms")
@ProblemFactCollectionProperty
public List<Integer> getRoomList() {
return roomList;
}
@ValueRangeProvider(id = "availablePeriods")
@ProblemFactCollectionProperty
public List<Integer> getPeriodList() {
return periodList;
}
Эти списки являются всеми возможными значениями, используемыми в полях лекции .
OptaPlanner заполняет ими все решения в пространстве поиска.
Наконец, затем он устанавливает оценку для каждого из решений, поэтому нам нужно поле для хранения оценки:
@PlanningScore
public HardSoftScore getScore() {
return score;
}
Без оценки OptaPlanner не может найти оптимальное решение, поэтому важность подчеркивалась ранее.
4. Подсчет очков
В отличие от того, что мы рассматривали до сих пор, для класса оценки требуется больше пользовательского кода.
Это связано с тем, что калькулятор оценок специфичен для проблемы и модели предметной области.
4.1. Пользовательская Java
Мы используем простой расчет баллов для решения этой проблемы (хотя это может показаться не так):
public class ScoreCalculator
implements EasyScoreCalculator<CourseSchedule> {
@Override
public Score calculateScore(CourseSchedule courseSchedule) {
int hardScore = 0;
int softScore = 0;
Set<String> occupiedRooms = new HashSet<>();
for(Lecture lecture : courseSchedule.getLectureList()) {
String roomInUse = lecture.getPeriod()
.toString() + ":" + lecture.getRoomNumber().toString();
if(occupiedRooms.contains(roomInUse)){
hardScore += -1;
} else {
occupiedRooms.add(roomInUse);
}
}
return HardSoftScore.valueOf(hardScore, softScore);
}
}
Если мы внимательно посмотрим на приведенный выше код, важные части станут более ясными. Мы вычисляем оценку в цикле, потому что List<Lecture> содержит определенные неуникальные комбинации комнат и периодов.
HashSet используется для сохранения уникального ключа (строки), чтобы мы могли наказывать дубликаты лекций в одной и той же аудитории и периоде.
В результате мы получаем уникальные наборы номеров и периодов.
4.2. слюни
Файлы Drools дают нам быстрый способ изменить правила применения к файлам. Хотя синтаксис иногда может сбивать с толку, файл Drools может быть способом управления логикой вне скомпилированных классов.
Наше правило для предотвращения нулевых записей выглядит так:
global HardSoftScoreHolder scoreHolder;
rule "noNullRoomPeriod"
when
Lecture( roomNumber == null );
Lecture( period == null );
then
scoreHolder.addHardConstraintMatch(kcontext, -1);
end
5. Конфигурация решателя
Еще один необходимый файл конфигурации, нам нужен файл XML для настройки решателя.
5.1. XML-файл конфигурации
<solver>
<scanAnnotatedClasses/>
<scoreDirectorFactory>
<easyScoreCalculatorClass>
org.foreach.optaplanner.ScoreCalculator
</easyScoreCalculatorClass>
</scoreDirectorFactory>
<termination>
<secondsSpentLimit>10</secondsSpentLimit>
</termination>
</solver>
Из-за наших аннотаций в классе CourseSchedule мы используем здесь элемент scanAnnotatedClasses для сканирования файлов в пути к классам.
Содержимое элемента scoreDirectorFactory устанавливает наш класс ScoreCalculator , чтобы он содержал нашу логику подсчета очков.
Когда мы хотим использовать файл Drools, мы заменяем содержимое элемента на:
<scoreDrl>courseScheduleScoreRules.drl</scoreDrl>
Наша последняя настройка — завершающий элемент. Вместо бесконечного поиска оптимизированного решения, которое может никогда не существовать, этот параметр остановит поиск по истечении определенного времени.
Десяти секунд более чем достаточно для решения большинства задач.
6. Тестирование
Мы настроили наше решение, решатель и классы задач. Давайте проверим это!
6.1. Настройка нашего теста
Во-первых, мы делаем некоторые настройки:
SolverFactory<CourseSchedule> solverFactory = SolverFactory
.createFromXmlResource("courseScheduleSolverConfiguration.xml");
solver = solverFactory.buildSolver();
unsolvedCourseSchedule = new CourseSchedule();
Во-вторых, мы вносим данные в коллекцию сущностей планирования и объекты Списка фактов о проблемах.
6.2. Выполнение теста и проверка
Наконец, мы тестируем его, вызываяsolve .
CourseSchedule solvedCourseSchedule = solver.solve(unsolvedCourseSchedule);
assertNotNull(solvedCourseSchedule.getScore());
assertEquals(-4, solvedCourseSchedule.getScore().getHardScore());
Мы проверяем, что уsolvedCourseSchedule есть оценка, которая говорит нам, что у нас есть «оптимальное» решение.
В качестве бонуса мы создаем метод печати, который будет отображать наше оптимизированное решение:
public void printCourseSchedule() {
lectureList.stream()
.map(c -> "Lecture in Room "
+ c.getRoomNumber().toString()
+ " during Period " + c.getPeriod().toString())
.forEach(k -> logger.info(k));
}
Этот метод отображает:
Lecture in Room 1 during Period 1
Lecture in Room 2 during Period 1
Lecture in Room 1 during Period 2
Lecture in Room 2 during Period 2
Lecture in Room 1 during Period 3
Lecture in Room 2 during Period 3
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Lecture in Room 1 during Period 1
Обратите внимание, как повторяются последние три записи. Это происходит потому, что оптимального решения нашей задачи не существует. Мы выбрали три периода, две аудитории и десять лекций.
Есть только шесть возможных лекций из-за этих фиксированных ресурсов. По крайней мере, этот ответ показывает пользователю, что не хватает комнат или периодов для размещения всех лекций.
7. Дополнительные возможности
Наш пример для OptaPlanner, который мы создали, был простым, однако фреймворк добавил функции для более разнообразных вариантов использования. Мы можем захотеть реализовать или изменить наш алгоритм оптимизации, а затем указать структуру для его использования.
Благодаря недавним усовершенствованиям многопоточности в Java, OptaPlanner также дает разработчикам возможность использовать несколько реализаций многопоточности, таких как fork and join, инкрементное решение и многопользовательская среда.
Обратитесь к документации для получения дополнительной информации.
8. Заключение
Платформа OptaPlanner предоставляет разработчикам мощный инструмент для решения проблем удовлетворения ограничений, таких как планирование и распределение ресурсов.
OptaPlanner предлагает минимальное использование ресурсов JVM, а также интеграцию с Jakarta EE. Автор продолжает поддерживать фреймворк, и Red Hat добавила его как часть своего Business Rules Management Suite.
Как всегда, код можно найти на Github .