13.3. 定义约束并计算分数
当遇到问题时,分数 代表特定解决方案的质量。分数越大。红帽构建的 OptaPlanner 会寻找最佳解决方案,这是可用时间提供的最高分数的解决方案。它可能 是最佳解决方案。
因为 timetable 示例用例有硬和软限制,因此请使用 Hard SoftScore 类来代表分数:
- 硬限制不能被破坏。例如: 一个房间可以同时有一个小时间。
- 软限制不应中断。例如: 一个公司更喜欢在单个房间参与。
硬限制会与其他硬限制进行权重。软限制会与其他软限制加权。硬限制始终超过软限制,无论它们对应的权重是什么。
要计算分数,您可以实施 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: O (n)而不是O(n)而不是 O(n)更好的 magnitude 顺序。
流程
创建以下 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");
}
}