10.3. 定义限制并计算分数
当解决问题时,分数 代表特定解决方案的质量。得分越高。红帽构建的 OptaPlanner 寻找最佳解决方案,这是可用时间获得最高分数的解决方案。这可能是 最佳解决方案。
因为可时间的示例用例具有硬和软约束,因此请使用 HardSoftScore
类来代表分数:
- 硬限制不得被破坏。例如: 一个房间可以有以上时间。
- 软限制不应该被破坏。例如: 更喜欢在单个房里的教学方式。
硬约束的加法是相对于其他硬约束的权重。软限制会高于其他软限制。硬限制始终大于软限制,无论其对应的权重如何。
要计算分数,您可以实施 EasyScoreCalculator
类:
public class TimeTableEasyScoreCalculator implements EasyScoreCalculator<TimeTable> { @Override public HardSoftScore calculateScore(TimeTable timeTable) { List<Lesson> lessonList = timeTable.getLessonList(); int hardScore = 0; for (Lesson a : lessonList) { for (Lesson b : lessonList) { if (a.getTimeslot() != null && a.getTimeslot().equals(b.getTimeslot()) && a.getId() < b.getId()) { // A room can accommodate at most one lesson at the same time. if (a.getRoom() != null && a.getRoom().equals(b.getRoom())) { hardScore--; } // A teacher can teach at most one lesson at the same time. if (a.getTeacher().equals(b.getTeacher())) { hardScore--; } // A student can attend at most one lesson at the same time. if (a.getStudentGroup().equals(b.getStudentGroup())) { hardScore--; } } } } int softScore = 0; // Soft constraints are only implemented in the "complete" implementation return HardSoftScore.of(hardScore, softScore); } }
不幸的是,这个解决方案无法进行很好的扩展,因为它是非增量:每次分配给不同的时间段或房间,都会重新评估所有课程来计算新分数。
更好的解决方法是创建一个 src/main/java/com/example/solver/TimeTableConstraintProvider.java
类来执行增量分数计算。此类使用 OptaPlanner 的 ConstraintStream API,它由 Java 8 Streams 和 SQL 产生。ConstraintProvider
缩放比 EasyScoreCalculator
更好的度量:O(n)而不是 O(n)。
流程
创建以下 src/main/java/com/example/solver/TimeTableConstraintProvider.java
类:
package com.example.solver; import com.example.domain.Lesson; import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore; import org.optaplanner.core.api.score.stream.Constraint; import org.optaplanner.core.api.score.stream.ConstraintFactory; import org.optaplanner.core.api.score.stream.ConstraintProvider; import org.optaplanner.core.api.score.stream.Joiners; public class TimeTableConstraintProvider implements ConstraintProvider { @Override public Constraint[] defineConstraints(ConstraintFactory constraintFactory) { return new Constraint[] { // Hard constraints roomConflict(constraintFactory), teacherConflict(constraintFactory), studentGroupConflict(constraintFactory), // Soft constraints are only implemented in the "complete" implementation }; } private Constraint roomConflict(ConstraintFactory constraintFactory) { // A room can accommodate at most one lesson at the same time. // Select a lesson ... return constraintFactory.from(Lesson.class) // ... and pair it with another lesson ... .join(Lesson.class, // ... in the same timeslot ... Joiners.equal(Lesson::getTimeslot), // ... in the same room ... Joiners.equal(Lesson::getRoom), // ... and the pair is unique (different id, no reverse pairs) Joiners.lessThan(Lesson::getId)) // then penalize each pair with a hard weight. .penalize("Room conflict", HardSoftScore.ONE_HARD); } private Constraint teacherConflict(ConstraintFactory constraintFactory) { // A teacher can teach at most one lesson at the same time. return constraintFactory.from(Lesson.class) .join(Lesson.class, Joiners.equal(Lesson::getTimeslot), Joiners.equal(Lesson::getTeacher), Joiners.lessThan(Lesson::getId)) .penalize("Teacher conflict", HardSoftScore.ONE_HARD); } private Constraint studentGroupConflict(ConstraintFactory constraintFactory) { // A student can attend at most one lesson at the same time. return constraintFactory.from(Lesson.class) .join(Lesson.class, Joiners.equal(Lesson::getTimeslot), Joiners.equal(Lesson::getStudentGroup), Joiners.lessThan(Lesson::getId)) .penalize("Student group conflict", HardSoftScore.ONE_HARD); } }