OptaPlanner examples その6

OptaPlanner

Course timetabling


ここから「Real examples」です。要素が増えて複雑になってきます。

http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#curriculumCourse

今回は講義を時間と部屋に割り振る最適化です。

  • CourseSchedule : @PlanningSolution
    • List getPeriodList() : @ValueRangeProvider(id = "periodRange")
    • List getRoomList() : @ValueRangeProvider(id = "roomRange")
    • List getLectureList() : @PlanningEntityCollectionProperty
  • Lecture : @PlanningEntity
    • Period : @PlanningVariable
    • Room : @PlanningVariable
    • Course course;
    • int lectureIndexInCourse;

@PlanningVariable が2つになりました。search space も拡大します。講義(Lecture)とは、特定の時間(Period)と部屋(Room)で、講座(Course)を行う、という assignment です。モデリングでは語彙の把握が大事ですね。講座(Course)は講義(Lecture)に固定するので、PlanningVariableではありません。

Course は Teacher 及び Curriculum を持ちます。同じ Teacher が同時に講義を行うことはできない。同じ Curriculum を同じ時間にやってもいけない。

rule "conflictingLecturesDifferentCourseInSamePeriod"
    when
        $courseConflict : CourseConflict($leftCourse : leftCourse, $rightCourse : rightCourse)
        $leftLecture : Lecture(course == $leftCourse, $period : period, period != null)
        $rightLecture : Lecture(course == $rightCourse, period == $period, this != $leftLecture)
    then
        scoreHolder.addHardConstraintMatch(kcontext, - $courseConflict.getConflictCount());
end

おや、CourseConflict って何だ。CourseSchedule.precalculateCourseConflictList() で準備される、ルール用の便利factのようです。各2Courseの組み合わせに対して、Teacher及びCurriculumのコンフリクトがどれだけあるか、カウントして保持しておきます。で、同じ時間にぶつかった時、その conflictCount 分だけ hard score をマイナスします。ルール内でいちいち計算してたらパフォーマンスによろしくないということですね。

今回はさらに Selector もちょっと見てみよう。

  <localSearch>
    <unionMoveSelector>
      <changeMoveSelector>
        <valueSelector>
          <variableName>period</variableName>
        </valueSelector>
      </changeMoveSelector>
      <changeMoveSelector>
        <valueSelector>
          <variableName>room</variableName>
        </valueSelector>
      </changeMoveSelector>
      <swapMoveSelector>
        <filterClass>org.optaplanner.examples.curriculumcourse.solver.move.DifferentCourseSwapMoveFilter</filterClass>
      </swapMoveSelector>
    </unionMoveSelector>

今までの多くの example では、selector の設定は省略されていました。省略するとデフォルトで changeMoveSelector + swapMoveSelector の union になります。ところがこの example では省略すると以下のように怒られます。

Exception in thread "main" java.lang.IllegalArgumentException: The selectorConfig (ValueSelectorConfig(null)) has no configured variableName (null) for entityClass (class org.optaplanner.examples.curriculumcourse.domain.Lecture) and because there are multiple variableNames ([period, room]), it can not be deducted automatically.
	at org.optaplanner.core.config.heuristic.selector.SelectorConfig.deduceVariableDescriptor(SelectorConfig.java:110)
	at org.optaplanner.core.config.heuristic.selector.value.ValueSelectorConfig.buildValueSelector(ValueSelectorConfig.java:198)
	at org.optaplanner.core.config.heuristic.selector.move.generic.ChangeMoveSelectorConfig.buildBaseMoveSelector(ChangeMoveSelectorConfig.java:68)
	at org.optaplanner.core.config.heuristic.selector.move.MoveSelectorConfig.buildMoveSelector(MoveSelectorConfig.java:187)
	at org.optaplanner.core.config.heuristic.selector.move.composite.UnionMoveSelectorConfig.buildBaseMoveSelector(UnionMoveSelectorConfig.java:75)
	at org.optaplanner.core.config.heuristic.selector.move.MoveSelectorConfig.buildMoveSelector(MoveSelectorConfig.java:187)
	at org.optaplanner.core.config.localsearch.LocalSearchPhaseConfig.buildMoveSelector(LocalSearchPhaseConfig.java:143)
...

ChangeMoveSelector は、PlanningVariable がひとつだけのケースでは自動的にその variable を変更対象にするのですが、PlanningVariable が複数のケースでは決定できないので、ちゃんと config に書いてくれっていうことです。

一方 swapMoveSelector はデフォルトの だけでもちゃんと動きます。では DifferentCourseSwapMoveFilter は何をするのでしょう。

public class DifferentCourseSwapMoveFilter implements SelectionFilter<SwapMove> {
    public boolean accept(ScoreDirector scoreDirector, SwapMove move) {
        Lecture leftLecture = (Lecture) move.getLeftEntity();
        Lecture rightLecture = (Lecture) move.getRightEntity();
        return !leftLecture.getCourse().equals(rightLecture.getCourse());
    }
}

同じ Course の Lecture は swap しない、という filter です。スコア上意味が無いからですね。

では、filter ありとなしで、性能に差が出るのか。ベンチマークを走らせてみました。データは comp01 と comp02 のみ。terminationは 120 秒、late acceptance でやりました（短い時間では late acceptance の方が tabu search より好成績っぽい）。

  • Without Filter
    • comp01: 0hard/-12soft
    • comp02: 0hard/-279soft
  • With Filter
    • comp01: 0hard/-18soft
    • comp02: 0hard/-267soft

ちょっと興味深い結果になりました。データの少ない comp01 では Without Filter の方が、データの多い comp02 では With Filter の方が良い結果を出しました。もっと多くのデータ＆長時間 termination で見ないと駄目ですが、必ずしもこの Filter が有効とは限らないようです。ただ、このベンチマークの結果だけで判断するなら、データの多い方の結果を重視して Filter 採用になるでしょう。