18.3. 定义限制并计算分数
在解决问题时,分数 代表特定解决方案的质量。分数越高。红帽构建的 OptaPlanner 寻求最佳解决方案,这是在可用时间内获得最高分数的解决方案。这可能是 最佳解决方案。
因为 timetable 示例用例具有硬和软限制,所以请使用 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); } }
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,该 API 由 Java 8 Streams 和 SQL 推进。ConstraintProvider
比 EasyScoreCalculator 增加了一个比 EasyScoreCalculator
更强的 magnitude 顺序:O(n)而不是 O(nbusybox)。
流程
创建以下 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.forEach(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(HardSoftScore.ONE_HARD) .asConstraint("Room conflict"); } private Constraint teacherConflict(ConstraintFactory constraintFactory) { // A teacher can teach at most one lesson at the same time. return constraintFactory.forEach(Lesson.class) .join(Lesson.class, Joiners.equal(Lesson::getTimeslot), Joiners.equal(Lesson::getTeacher), Joiners.lessThan(Lesson::getId)) .penalize(HardSoftScore.ONE_HARD) .asConstraint("Teacher conflict"); } private Constraint studentGroupConflict(ConstraintFactory constraintFactory) { // A student can attend at most one lesson at the same time. return constraintFactory.forEach(Lesson.class) .join(Lesson.class, Joiners.equal(Lesson::getTimeslot), Joiners.equal(Lesson::getStudentGroup), Joiners.lessThan(Lesson::getId)) .penalize(HardSoftScore.ONE_HARD) .asConstraint("Student group conflict"); } }
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.forEach(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(HardSoftScore.ONE_HARD)
.asConstraint("Room conflict");
}
private Constraint teacherConflict(ConstraintFactory constraintFactory) {
// A teacher can teach at most one lesson at the same time.
return constraintFactory.forEach(Lesson.class)
.join(Lesson.class,
Joiners.equal(Lesson::getTimeslot),
Joiners.equal(Lesson::getTeacher),
Joiners.lessThan(Lesson::getId))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Teacher conflict");
}
private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
// A student can attend at most one lesson at the same time.
return constraintFactory.forEach(Lesson.class)
.join(Lesson.class,
Joiners.equal(Lesson::getTimeslot),
Joiners.equal(Lesson::getStudentGroup),
Joiners.lessThan(Lesson::getId))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Student group conflict");
}
}