1.2 OptaPlanner快速开始

1.2 OptaPlanner快速开始

技术杂谈小彩虹2021-07-16 15:40:01130A+A-

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

内容概要

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

OptaPlanner介绍

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

OptaPlanner视频介绍

你将要解决什么问题?

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

image.png

我们将使用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 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>

对问题进行业务建模

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

image.png

Timeslot

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

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。为简单起见,所有房间都没有容量限制,它们可以容纳所有课程。

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类的timeSlotroom字段,以将每节课分配到一个时间段和一个房间。因为OptaPlanner改变了这些字段,所以Lesson是一个 Planning Entity(规划实体)

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

@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。

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类包装了一个单一数据集的所有TimeslotRoomLesson实例。此外,因为它包含了所有的课程,每个课程都有一个特定的规划变量状态,所以它是一个规划解决方案,它有一个分数。
可以把Timeable类理解成,OptaPlanner在求解过程中操作数据的入口,所有的常量数据及变量修改、分数计算都是通过这个类进行的。分数如下:

  • 如果课程仍未分配,那么它就是一个未初始化的解决方案,例如,一个得分为-4init/0hard/0soft的解决方案。
  • 如果它破坏了硬约束,那么它就是一个不可行的解决方案,例如,一个得分为-2hard/3soft的解决方案。
  • 如果它遵守了所有的硬约束,那么它就是一个可行的解决方案,例如,一个得分为0hard/7soft的解决方案。
@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
    • timeslotroom 字段的值通常还是空的,所以没有分配。它们是planning variables(规划变量)
    • 其他字段,如subject, teacher ,studentGroup,都被填入。这些字段是problem properties(问题属性)

当然,这个类也是解决方案的输出。

  • lessonList字段,每个Lesson实例在解决后都有非空的timeslot 和room房间字段
  • score 分数字段,表示输出解决方案的质量,例如,0hard/-5soft

创建求解业务类

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

@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:

optaplanner.solver.termination.spent-limit=5s

启动程序

通过SpringBoot Application类启动即可。

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

尝试求解

启动服务后,我们通过PostMan来进行访问。
URL:http://localhost:8080/timeTable/solve
求解数据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中定义的终止花费时间,该服务会返回一个输出。

image.png 结果输出:

{
    "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在这五秒钟内做了什么。

... 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中添加约束条件时,请留意信息日志中的得分计算速度,在解出相同的时间后,评估对性能的影响。

... Solving ended: ..., score calculation speed (29455/sec), ...

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

logging.level.org.optaplanner=debug

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

 ... 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的理解,再最后我们再进行系统的学习各个深层的应用。
最后编写不易,麻烦给个小小的赞,关注我,大家一起来学习~~~

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1

联系我们