10.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,它被 Java 8 Streams 和 SQL 实现。ConstraintProvider 扩展一个比 EasyScoreCalculator: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.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);
}
}
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);
}
}