12 OptaPlanner快速开始

这是我参与更文挑战的第2天，活动详情查看： 更文挑战

内容概要

本章主要是首次入门学习OptaPlanner的一个Demo，类似于Java的HelloWorld。对于文章中“红底黑字”的内容，大家先牢记此概念，后续篇章会详细讲解。

OptaPlanner介绍

OptaPlanner是一个轻量级的、可嵌入的约束满足引擎，可求解规划问题，它巧妙的跟分数相结合，用分数来对比每一个解决方案，最高分作为最优解决方案。OptaPlanner本身支持多种算法，可扩展性和使用性都很高，社区环境在国外相对活跃，版本迭代稳定。多说无益，下面给大家看下视频介绍，可以很直观的了解OptaPlanner（字幕是我自己翻译的，不准确请谅解）

OptaPlanner视频介绍

你将要解决什么问题？

咱们今天来优化一个问题，为高中的学生和教师优化一个学校的时间表。

我们将使用OptaPlanner算法自动将课程分配到对应的教室、教室，并且要遵守硬约束、软约束的规则，如下：
硬约束

• 一个房间在同一时间最多可以有一节课。
• 一个老师在同一时间最多可以教一节课。
• 一个学生在同一时间最多可以上一节课。
• 软约束*
• 一个老师喜欢在一个房间里教每一节课。
• 一个老师喜欢教连续的课程，不喜欢课程之间有空隙。
  从数学上讲，学校的时间安排是一个NP-hard问题。简单地使用穷举算法来迭代所有可能的组合，对于一个很小的数据集，即使在超级计算机上也需要数百万年。幸运的是，像OptaPlanner这样的人工智能约束解算器拥有先进的算法，可以在合理的时间内提供一个接近最优的解决方案。

准备工作

JDK、MAVEN及编辑器：

• JDK 8 or later
• Maven 3.2+ or Gradle4+
• An IDE, such as IntelliJ IDEA, VSCode or Eclipse

工程创建和Maven配置

使用idea初始化一个应用：

• Spring Web (spring-boot-starter-web)
  MAVEN配置：

xml复制代码<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>{version-org-spring-framework-boot}</version>
    </parent>

    <groupId>com.example</groupId>
    <artifactId>constraint-solving-ai-optaplanner</artifactId>
    <version>0.1.0-SNAPSHOT</version>
    <name>Constraint Solving AI with OptaPlanner</name>
    <description>A Spring Boot OptaPlanner example to generate a school timetable.</description>

    <properties>
        <java.version>1.8</java.version>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <dependency>
            <groupId>org.optaplanner</groupId>
            <artifactId>optaplanner-spring-boot-starter</artifactId>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
            <exclusions>
                <exclusion>
                    <groupId>org.junit.vintage</groupId>
                    <artifactId>junit-vintage-engine</artifactId>
                </exclusion>
            </exclusions>
        </dependency>
    </dependencies>

    <dependencyManagement>
        <dependencies>
            <dependency>
                <groupId>org.optaplanner</groupId>
                <artifactId>optaplanner-spring-boot-starter</artifactId>
                <version>{project-version}</version>
            </dependency>
        </dependencies>
    </dependencyManagement>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
            </plugin>
        </plugins>
    </build>
</project>

对问题进行业务建模

我们的目标是将每节课分配到一个时间段和一个房间。所以需要创建课程。如下类图：

Timeslot

时间段类表示上课的时间段，例如，星期一10:30 - 11:30或星期二13:30 - 14:30。为了简单起见，所有的时间段都有相同的时间长度，在午餐或其他休息时间没有时间段。
一个时间段没有日期，因为高中的课程表只是每周重复一次。因此，没有必要添加日期属性。

java复制代码public class Timeslot {

    private DayOfWeek dayOfWeek;
    private LocalTime startTime;
    private LocalTime endTime;

    private Timeslot() {
    }
    public Timeslot(DayOfWeek dayOfWeek, LocalTime startTime, LocalTime endTime) {
        this.dayOfWeek = dayOfWeek;
        this.startTime = startTime;
        this.endTime = endTime;
    }
    @Override
    public String toString() {
        return dayOfWeek + " " + startTime.toString();
    }
    // ********************************
    // Getters and setters
    // ********************************

    public DayOfWeek getDayOfWeek() {
        return dayOfWeek;
    }
    public LocalTime getStartTime() {
        return startTime;
    }
    public LocalTime getEndTime() {
        return endTime;
    }
}

因为在求解过程中Timeslot对象不会发生变化，所以Timeslot被称为Problem Fact（问题事实）。这样的类不需要任何OptaPlanner的注解。

注意：toString()方法使输出保持简短，所以更容易阅读OptaPlanner的DEBUG或TRACE日志。

Room

房间代表授课的地点，例如，房间A或房间B。为简单起见，所有房间都没有容量限制，它们可以容纳所有课程。

java复制代码public class Room {

    private String name;

    private Room() {
    }
    public Room(String name) {
        this.name = name;
    }
    @Override
    public String toString() {
        return name;
    }
    // ********************************
    // Getters and setters
    // ********************************

    public String getName() {
        return name;
    }
}

Room对象在求解过程中不会改变，所以Room也是一个Problem Fact（问题事实）。

Lesson

在由Lesson类代表的一堂课中，教师向一组学生教授一个科目，例如，九年级的A.Turing教授的数学或十年级的M.Curie教授的化学。如果一个科目每周由同一个老师对同一个学生组进行多次授课，那么就会有多个Lesson实例，这些实例只能通过id来区分。例如，9年级的学生每周有6节数学课。

在求解过程中，OptaPlanner会改变Lesson类的timeSlot和room字段，以将每节课分配到一个时间段和一个房间。因为OptaPlanner改变了这些字段，所以Lesson是一个 Planning Entity（规划实体）。

一个课程的timeslot 和room 字段在初始化时是空的。OptaPlanner在求解过程中会改变这些字段的值。这些字段被称为Planning Variable（计划变量）。为了让OptaPlanner识别它们，timeslot 和room 字段都需要一个@PlanningVariable注解。它们的包含类Lesson，需要一个@PlanningEntity注解。

java复制代码@PlanningEntity
public class Lesson {

    private Long id;

    private String subject;
    private String teacher;
    private String studentGroup;

    @PlanningVariable(valueRangeProviderRefs = "timeslotRange")
    private Timeslot timeslot;

    @PlanningVariable(valueRangeProviderRefs = "roomRange")
    private Room room;

    private Lesson() {
    }

    public Lesson(Long id, String subject, String teacher, String studentGroup) {
        this.id = id;
        this.subject = subject;
        this.teacher = teacher;
        this.studentGroup = studentGroup;
    }

    @Override
    public String toString() {
        return subject + "(" + id + ")";
    }

    // ********************************
    // Getters and setters
    // ********************************

    public Long getId() {
        return id;
    }

    public String getSubject() {
        return subject;
    }

    public String getTeacher() {
        return teacher;
    }

    public String getStudentGroup() {
        return studentGroup;
    }

    public Timeslot getTimeslot() {
        return timeslot;
    }

    public void setTimeslot(Timeslot timeslot) {
        this.timeslot = timeslot;
    }

    public Room getRoom() {
        return room;
    }

    public void setRoom(Room room) {
        this.room = room;
    }

}

定义约束条件并计算得分

分数代表一个解决方案的质量，越高越好。OptaPlanner寻找最优解决方案，也就是在可用时间内找到的得分最高的解决方案，它可能是最优解决方案。
因为这个用例有硬约束和软约束，所以用HardSoftScore类来表示分数。

• 硬约束不能被打破。比如说，一个房间在同一时间最多可以有一节课。
• 软约束不应该被打破。比如说，一个教师更喜欢在一个房间里上课。
  硬约束与其他硬约束相加权。软约束也要加权，与其他软约束相比，不管它们各自的权重如何，硬约束总是大于软约束，两者是不同层级的。

创建一个TimeTableConstraintProvider.java 类来执行增量分数计算。它使用OptaPlanner的ConstraintStream API，其灵感来自于Java 8 Streams和SQL。

java复制代码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) {
        // 一个房间最多可以同时容纳一节课。

        // 选择一个课程...
        return constraintFactory.from(Lesson.class)
                // ......并与另一课程配对......
                .join(Lesson.class,
                        // ... 在同一时间段内 ...
                        Joiners.equal(Lesson::getTimeslot),
                        // ...在同一个房间里...
                        Joiners.equal(Lesson::getRoom),
                        // ...... 而且这一对是唯一的（不同的id，没有反向的对）。
                        Joiners.lessThan(Lesson::getId))
                //然后用一个硬权重来惩罚每一对。
                .penalize("Room conflict", HardSoftScore.ONE_HARD);
    }

    private Constraint teacherConflict(ConstraintFactory constraintFactory) {
        // 一个教师在同一时间最多可以教一门课。
        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) {
        // 一个学生在同一时间最多只能上一节课。
        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);
    }

}

创建PlanningSolution类

创建TimeTable类包装了一个单一数据集的所有Timeslot、Room和Lesson实例。此外，因为它包含了所有的课程，每个课程都有一个特定的规划变量状态，所以它是一个规划解决方案，它有一个分数。

可以把Timeable类理解成，OptaPlanner在求解过程中操作数据的入口，所有的常量数据及变量修改、分数计算都是通过这个类进行的。分数如下：

• 如果课程仍未分配，那么它就是一个未初始化的解决方案，例如，一个得分为-4init/0hard/0soft的解决方案。
• 如果它破坏了硬约束，那么它就是一个不可行的解决方案，例如，一个得分为-2hard/3soft的解决方案。
• 如果它遵守了所有的硬约束，那么它就是一个可行的解决方案，例如，一个得分为0hard/7soft的解决方案。

java复制代码@PlanningSolution
public class TimeTable {

    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    private List<Timeslot> timeslotList;
    @ValueRangeProvider(id = "roomRange")
    @ProblemFactCollectionProperty
    private List<Room> roomList;
    @PlanningEntityCollectionProperty
    private List<Lesson> lessonList;
    @PlanningScore
    private HardSoftScore score;

    private TimeTable() {
    }
    public TimeTable(List<Timeslot> timeslotList, List<Room> roomList,
            List<Lesson> lessonList) {
        this.timeslotList = timeslotList;
        this.roomList = roomList;
        this.lessonList = lessonList;
    }
    // ********************************
    // Getters and setters
    // ********************************
    public List<Timeslot> getTimeslotList() {
        return timeslotList;
    }
    public List<Room> getRoomList() {
        return roomList;
    }
    public List<Lesson> getLessonList() {
        return lessonList;
    }
    public HardSoftScore getScore() {
        return score;
    }
}

TimeTable类有一个@PlanningSolution注解，所以OptaPlanner知道这个类包含所有的输入和输出数据。
具体来说，这个类是问题的输入：

• timeslotList字段
  • 这是一个problem facts（问题事实）的列表，因为它们在解题过程中不会改变。
• roomList字段
  • 这是一个problem facts（问题事实）的列表，因为它们在解题过程中不会发生变化。
• lessonList字段
• 这是一个planning entities（计划实体）的列表，因为它们在解题过程中会改变。
• lesson
  • timeslot和room 字段的值通常还是空的，所以没有分配。它们是planning variables（规划变量）。
  • 其他字段，如subject, teacher ,studentGroup，都被填入。这些字段是problem properties（问题属性）。
    当然，这个类也是解决方案的输出。
• lessonList字段，每个Lesson实例在解决后都有非空的timeslot 和room房间字段
• score 分数字段，表示输出解决方案的质量，例如，0hard/-5soft

创建求解业务类

现在我们把所有的东西放在一起，创建一个REST服务。但是在REST线程上解决规划问题会导致HTTP超时问题。因此，Spring Boot启动器注入了一个SolverManager实例，它在一个单独的线程池中运行求解器，可以并行解决多个数据集。

java复制代码@RestController
@RequestMapping("/timeTable")public class TimeTableController {

    @Autowired
    private SolverManager<TimeTable, UUID> solverManager;

    @PostMapping("/solve")
    public TimeTable solve(@RequestBody TimeTable problem) {
        UUID problemId = UUID.randomUUID();
        // 提交问题开始求解
        SolverJob<TimeTable, UUID> solverJob = solverManager.solve(problemId, problem);
        TimeTable solution;
        try {
            // 等待求解结束
            solution = solverJob.getFinalBestSolution();
        } catch (InterruptedException | ExecutionException e) {
            throw new IllegalStateException("Solving failed.", e);
        }
        return solution;
    }
}

为了简单起见，这个实现会等待求解器完成，这仍然会导致HTTP超时。完整的实现可以更优雅地避免HTTP超时。

设置终止时间

如果没有终止设置或终止事件，解算器会永远运行。为了避免这种情况，将求解时间限制在5秒之内。这足够短，可以避免HTTP超时。

Create the src/main/resources/application.properties file:

js复制代码optaplanner.solver.termination.spent-limit=5s

启动程序

通过SpringBoot Application类启动即可。

java复制代码@SpringBootApplication
public class TimeTableSpringBootApp {
    public static void main(String[] args) {
        SpringApplication.run(TimeTableSpringBootApp.class, args);
    }
}

尝试求解

启动服务后，我们通过PostMan来进行访问。

URL：http://localhost:8080/timeTable/solve

求解数据JSON：

json复制代码{
        "timeslotList": [
                {
                        "dayOfWeek": "MONDAY",
                        "startTime": "08:30:00",
                        "endTime": "09:30:00"
                },
                {
                        "dayOfWeek": "MONDAY",
                        "startTime": "09:30:00",
                        "endTime": "10:30:00"
                }
        ],
        "roomList": [
                {
                        "name": "Room A"
                },
                {
                        "name": "Room B"
                }
        ],
        "lessonList": [
                {
                        "id": 1,
                        "subject": "Math",
                        "teacher": "A. Turing",
                        "studentGroup": "9th grade"
                },
                {
                        "id": 2,
                        "subject": "Chemistry",
                        "teacher": "M. Curie",
                        "studentGroup": "9th grade"
                },
                {
                        "id": 3,
                        "subject": "French",
                        "teacher": "M. Curie",
                        "studentGroup": "10th grade"
                },
                {
                        "id": 4,
                        "subject": "History",
                        "teacher": "I. Jones",
                        "studentGroup": "10th grade"
                }
        ]
}

大约5秒钟后，根据application.properties中定义的终止花费时间，该服务会返回一个输出。

结果输出：

json复制代码{
    "timeslotList": [
        {
            "dayOfWeek": "MONDAY",
            "startTime": "08:30:00",
            "endTime": "09:30:00"
        },
        {
            "dayOfWeek": "MONDAY",
            "startTime": "09:30:00",
            "endTime": "10:30:00"
        }
    ],
    "roomList": [
        {
            "name": "Room A"
        },
        {
            "name": "Room B"
        }
    ],
    "lessonList": [
        {
            "id": 1,
            "subject": "Math",
            "teacher": "A. Turing",
            "studentGroup": "9th grade",
            "timeslot": {
                "dayOfWeek": "MONDAY",
                "startTime": "08:30:00",
                "endTime": "09:30:00"
            },
            "room": {
                "name": "Room A"
            }
        },
        {
            "id": 2,
            "subject": "Chemistry",
            "teacher": "M. Curie",
            "studentGroup": "9th grade",
            "timeslot": {
                "dayOfWeek": "MONDAY",
                "startTime": "09:30:00",
                "endTime": "10:30:00"
            },
            "room": {
                "name": "Room A"
            }
        },
        {
            "id": 3,
            "subject": "French",
            "teacher": "M. Curie",
            "studentGroup": "10th grade",
            "timeslot": {
                "dayOfWeek": "MONDAY",
                "startTime": "08:30:00",
                "endTime": "09:30:00"
            },
            "room": {
                "name": "Room B"
            }
        },
        {
            "id": 4,
            "subject": "History",
            "teacher": "I. Jones",
            "studentGroup": "10th grade",
            "timeslot": {
                "dayOfWeek": "MONDAY",
                "startTime": "09:30:00",
                "endTime": "10:30:00"
            },
            "room": {
                "name": "Room B"
            }
        }
    ],
    "score": "0hard/0soft"
}

可以看出，程序将所有四节课分配给两个时间段中的一个和两个房间中的一个。还注意到，它符合所有的硬约束。例如，M. Curie’s 的两节课是在不同的时间段。

在服务器端，信息日志显示了OptaPlanner在这五秒钟内做了什么。

js复制代码... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4).
... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398).
... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).

日志配置

我们在ConstraintProvider中添加约束条件时，请留意信息日志中的得分计算速度，在解出相同的时间后，评估对性能的影响。

js复制代码... Solving ended: ..., score calculation speed (29455/sec), ...

要了解OptaPlanner如何在内部求解问题，在application.properties文件中或用-D系统属性改变日志记录。

js复制代码logging.level.org.optaplanner=debug

使用调试日志来显示每一个步骤：

js复制代码 ... Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
...     CH step (0), time spent (128), score (-18init/0hard/0soft), selected move count (15), picked move ([Math(101) {null -> Room A}, Math(101) {null -> MONDAY 08:30}]).
...     CH step (1), time spent (145), score (-16init/0hard/0soft), selected move count (15), picked move ([Physics(102) {null -> Room A}, Physics(102) {null -> MONDAY 09:30}]).
...

总结

给我们自己点个赞！我们刚刚用OptaPlanner开发了一个Spring应用程序。

本文章代码地址：gitee.com/yqsoftware/…

作业

通过这篇文章，我们已经能构建出一个简单的求解程序，文章中我们提到的硬约束/软约束，只有硬约束的实现，大家可以尝试给它加上软约束条件，例如：

软约束：M. Curie老师喜欢上下午课。

结束语

此次大家已经可以构建一个简单的求解程序，下一篇章我来学习各种的例子，加深对OptaPlanner的理解，再最后我们再进行系统的学习各个深层的应用。

最后编写不易，麻烦给个小小的赞，关注我，大家一起来学习~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有