«Руководство по OptaPlanner» - Spring на русском

«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

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. Lecture

Lecture, 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;
}

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

OptaPlanner заполняет ими все решения в пространстве поиска.

Наконец, затем каждому решению присваивается оценка, поэтому нам нужно поле для хранения оценки:

@PlanningScore
public HardSoftScore getScore() {
    return score;
}

Без оценки OptaPlanner не может найти оптимальное решение, поэтому его важность подчеркивается ранее.

4. Оценка

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

Это связано с тем, что калькулятор оценок специфичен для проблемы и модели предметной области.

4.1. Custom 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\u003cLecture\u003e содержит определенные неуникальные комбинации комнат и периодов.

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

В итоге получаем уникальные наборы комнат и периодов.

4.2. Drools

Файлы 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.baeldung.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());

Мы проверяем, имеет ли решаемыйCourseSchedule счет, который говорит нам, что у нас есть «оптимальное» решение.

В качестве бонуса мы создаем метод печати, который будет отображать наше оптимизированное решение:

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 и join, инкрементное решение и многопользовательская среда.

Дополнительные сведения см. в документации.

8. Заключение

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

OptaPlanner предлагает минимальное использование ресурсов JVM, а также интеграцию с Jakarta EE. Автор продолжает поддерживать фреймворк, и Red Hat добавила его как часть своего Business Rules Management Suite.

Как всегда, код можно найти на Github.

«Руководство по OptaPlanner»