OptaPlannerのガイド

投稿日: 2019-10-18 2022-11-02
タグ: Algorithms, Java

1. OptaPlannerの紹介

このチュートリアルでは、OptaPlannerと呼ばれるJava制約満足度ソルバーについて説明します。

OptaPlannerは、最小限のセットアップで一連のアルゴリズムを使用して計画の問題を解決します。

アルゴリズムを理解することで役立つ詳細が得られるかもしれませんが、フレームワークが私たちのために大変な作業を行っています。

2. Mavenの依存関係

まず、OptaPlannerのMaven依存関係を追加します。

<dependency>
    <groupId>org.optaplanner</groupId>
    <artifactId>optaplanner-core</artifactId>
    <version>8.24.0.Final</version>
</dependency>

OptaPlannerの最新バージョンは、MavenCentralリポジトリから検索されます。

3. 問題/解決策のクラス

問題を解決するには、例として特定の問題が必要です。

部屋、時間、教師などのリソースのバランスを取ることが難しいため、講義の時間割は適切な例です。

3.1. CourseSchedule

CourseSchedule には、問題変数と計画エンティティの組み合わせが含まれているため、ソリューションクラスになります。その結果、複数のアノテーションを使用して構成します。

それぞれを個別に詳しく見ていきましょう。

@PlanningSolution
public class CourseSchedule {

    @ValueRangeProvider(id = "availableRooms")
    @ProblemFactCollectionProperty
    private List<Integer> roomList;
    @ValueRangeProvider(id = "availablePeriods")
    @ProblemFactCollectionProperty
    private List<Integer> periodList;
    @ProblemFactCollectionProperty
    private List<Lecture> lectureList;
    @PlanningScore
    private HardSoftScore score;

PlanningSolution アノテーションは、このクラスにソリューションを含むデータが含まれていることをOptaPlannerに通知します。

OptaPlannerは、計画エンティティ、問題の事実、およびスコアという最小限のコンポーネントを期待しています。

3.2. レクチャー

講義、 POJOは、次のようになります。

@PlanningEntity
public class Lecture {

    @PlaningId
    private Long id;
    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は、これらの変数を使用したロジックの結果としてソリューションをスコアリングします。両方のgetterメソッドに注釈を追加します。

@ValueRangeProvider(id = "availableRooms")
@ProblemFactCollectionProperty
public List<Integer> getRoomList() {
    return roomList;
}

@ValueRangeProvider(id = "availablePeriods")
@ProblemFactCollectionProperty
public List<Integer> getPeriodList() {
    return periodList;
}

これらのリストはすべて、講義フィールドで使用される可能性のある値です。

OptaPlannerは、検索スペース全体のすべてのソリューションにそれらを入力します。

Finally, it then sets a score to each of the solutions, so we need a field to store the score:

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

スコアがないと、OptaPlannerは最適なソリューションを見つけることができないため、重要性を早期に強調しました。

4. スコアリング

これまで見てきたこととは対照的に、スコアリングクラスにはより多くのカスタムコードが必要です。

これは、スコア計算機が問題とドメインモデルに固有であるためです。

4.1. カスタムJava

この問題を解決するために、単純なスコア計算を使用します（ただし、そうではないように見える場合があります）。

public class ScoreCalculator 
  implements EasyScoreCalculator<CourseSchedule, HardSoftScore> {

    @Override
    public HardSoftScore 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.Of(hardScore, softScore);
    }
}

上記のコードを詳しく見ると、重要な部分がより明確になります。 リストがあるため、ループ内のスコアを計算します部屋と期間の特定の非一意の組み合わせが含まれています。

HashSet は、同じ部屋と期間で重複した講義にペナルティを課すことができるように、一意のキー（文字列）を保存するために使用されます。

その結果、私たちはユニークな部屋と期間のセットを受け取ります。

5. テスト

ソリューション、ソルバー、および問題のクラスを構成しました。テストしてみましょう！

5.1. テストの設定

まず、いくつかの設定を行います。

SolverFactory<CourseSchedule> solverFactory = SolverFactory.create(new SolverConfig() 
                                                      .withSolutionClass(CourseSchedule.class)
                                                      .withEntityClasses(Lecture.class)
                                                      .withEasyScoreCalculatorClass(ScoreCalculator.class)
                                                      .withTerminationSpentLimit(Duration.ofSeconds(1))); 
solver = solverFactory.buildSolver();

unsolvedCourseSchedule = new CourseSchedule();

次に、計画エンティティコレクションと問題ファクトListオブジェクトにデータを入力します。

5.2. テストの実行と検証

最後に、solveを呼び出してテストします。

CourseSchedule solvedCourseSchedule = solver.solve(unsolvedCourseSchedule);

assertNotNull(solvedCourseSchedule.getScore());
assertEquals(-4, solvedCourseSchedule.getScore().getHardScore());

solutionedCourseSchedule に、「最適な」ソリューションがあることを示すスコアがあることを確認します。

ボーナスとして、最適化されたソリューションを表示する印刷メソッドを作成します。

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

最後の3つのエントリがどのように繰り返されているかに注目してください。これは、問題に対する最適な解決策がないために発生します。 3つの期間、2つの教室、10の講義を選択しました。

これらの固定リソースのため、可能な講義は6つだけです。少なくともこの回答は、すべての講義を収容するのに十分な部屋または期間がないことをユーザーに示しています。

6. 追加機能

作成したOptaPlannerの例は単純なものでしたが、フレームワークには、より多様なユースケース向けの機能が追加されています。最適化のためにアルゴリズムを実装または変更してから、それを使用するフレームワークを指定することもできます。

Javaのマルチスレッド機能の最近の改善により、OptaPlannerは、開発者に、フォークと結合、インクリメンタルソルビング、マルチテナンシーなどのマルチスレッドの複数の実装を使用する機能も提供します。

詳細については、ドキュメントを参照してください。

7. 結論

OptaPlannerフレームワークは、スケジューリングやリソース割り当てなどの制約充足問題を解決するための強力なツールを開発者に提供します。

OptaPlannerは、最小限のJVMリソース使用量と、JakartaEEとの統合を提供します。作成者は引き続きフレームワークをサポートし、RedHatはビジネスルール管理スイートの一部としてフレームワークを追加しました。

いつものように、コードはGithubのにあります。

getdocs

13036