OptaPlanner的新约束表达方式 Constraint Streams

  有好些时间没有写过关于OptaPlanner的东西了,其实近半年来,OptaPlanner还是推出了不少有用、好用的新特性。包括本文讲到的以Stream接口实现评分编程。关于OptraPlanner的约束详细用法,可以参考官方资料.

  最近几个版本推出的新功能、特性中,有不少功能还处于初始探索阶段,甚至有些功能还未成体系,包括我在上一篇文件中推出的SolverManger实现批量异步规划。此功能尚未支持ProblemChanged接口,从而无法实现Realtime Planning. 因此,若需要将这些功能应用于项目实践,还请自行作详细调查分析,以免在项目中处于进退两难境地。

PS. 任何技术都一样,功能、版本越新,带来的收益越高,当然需要面对的风险也越高。

  对OptaPlanner有初步认识都清楚,我们使用OptaPlanner规划建模时,需要在模型中表达一系列约束,以描述各个业务实体的约束和规划的优化目标。以往通常有两种方式实现评分逻辑(详细可分为3种)。分别是:

1. 通过Drools脚本中的Rule来描述约束并进行评分;

2. 通过Java编写评分逻辑,通过Java编辑评分逻辑又分为:

   2.1. Java简易评分 - Easy Java score calculation

   2.2. Java增量评分 - Incremental Java score calculation

  从7.31版本开始提供的constraint streams属于Java增量评分的一种。在普通的Java增量评分中,我们需要针对各个约束逻辑,编辑相应的判断,并在满足一定条件后,通过ScoreHolder对象进行记分。引擎会将各个层次的分数进行累加,成为当前方案的总分。Constraint Streams的原理也一样,只是通过强大的Stream特性,令评分逻辑更为简洁,使用更短的代码即可实现更丰富的逻辑描述。

  关于Java的Stream特性(Java1.8及以后的版本才出现)的使用方法,可自行通过其它网络资源学习,本文假设读者熟悉Java Stream的各种用法。

我们先以一个简单的示例说明Constraint streams接口的使用方法:

private int doNotAssignAnn() {
        int softScore = 0;
        schedule.getShiftList().stream()
                .filter(Shift::isEmployeeAnn)
                .forEach(shift -> {
                    softScore -= 1;
                });
        return softScore;
    }

  通过上述代码块是一Java简易评分的示例,从方法名doNotAssignAnn就很容易理解到,该约束的作用是“使得任务不要分配给Ann”。我们知道在OptaPlanner里,评分通常都是负数,表示惩罚一个行为,令引擎找出尽可能规避这种行为的方案。示例中使用了Java的Stream功能进行判断和过滤。其逻辑是:从班次列表中找出所有分配给了Ann的班次,对每一个满足这个条件的班次进行扣分,并把分数加总作为方法的返回值。

  那么同样的约束要求,使用Constraint Stream应该如何实现呢?见以下代码:

private Constraint doNotAssignAnn(ConstraintFactory factory) {
        return factory.from(Shift.class)
                .filter(Shift::isEmployeeAnn)
                .penalize("Don't assign Ann", HardSoftScore.ONE_SOFT);
    }

  先要提醒一下,与Java简单评分法类似(评分类需要实现EasyScoreCalculator接口),OptaPlanner的Constraint Stream提供一个名为ConstraintProvider的接口,实现评分的类需要实现这个接口,这个接口只有一个需要实现的方法 - defineConstraints,它传入ConstrantFactory类,返回一个Constraint数组,数组的元素就是已进行了评分和惩罚的各个约束对象。上面的代码中可以看到,doNotAssignAnn方法返回一个Constraint对象,这个对象表示了对Ann被分配到的班次数的惩罚分数。上述代码可以看到,我们只需要对ConstraintFactory的对象factory进行Stream操作,一步即可完成判断、过滤和惩罚三个操作,完成这些操作后会得到一个操作过的Contraint对象,返回该对象即可。上述代码中,对于factory的三步操作也相当明了,大家可以自己理解。

  但是对于一些更复杂的判断,其实现步骤与模式也一样,只不过需要编写一些更复杂的Lambda表达式来进行判断、过滤和各种运算。如下代码:

  private Constraint requiredCpuPowerTotal(ConstraintFactory factory) {
        return factory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
                .filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
                .penalize("requiredCpuPowerTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower());
    }

  该代码是CloudBalance中用于,计算限制一台计划机被分配超出其CPU运算能力的约束。大家可以回想,或从官方示例中看一下CloudBalance的其中一个最基本约束 - 每台计算机所分得的CPU需求,不可超过该计算机的可用CPU能力。

  因此,可以看到,factory除了过from操作获得所有Process对象,通过filter对Process进行过滤,通过penalize进行计分外。factory对象还有一个groupBy方法,用于对所有Process中的Computer进行分组并加总每一组(即每个Computer)的所有CPU计算能力需求量。因此,在filter方法中,就找出那些超出CPU能力的Computer(即分组),在penalize方法中,对整所有超出CPU需求中的计算进行扣分,扣分值是超出部分。

  由此可能,OptaPlanner提供的Constraint Stream可以进行更复杂的条件判断,至于这种方法是否更好用,就取决于大家对Stream(类似C#中的Linq)的熟悉程度。

  至于整个Constraint Stream代码的结果方式,即上面提到的实现ConstraintProvider接口的代码如下(摘自官方示例CloudBalance):

public class CloudBalancingConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                requiredCpuPowerTotal(constraintFactory),
                requiredMemoryTotal(constraintFactory),
                requiredNetworkBandwidthTotal(constraintFactory),
                computerCost(constraintFactory)
        };
    }

    // ************************************************************************
    // Hard constraints
    // ************************************************************************

    private Constraint requiredCpuPowerTotal(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
                .filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
                .penalize("requiredCpuPowerTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower());
    }
.
.
.

  重复提示一下,Constraint Stream功能是7.31版才开始提供的功能,从功能接口上应该是未够成功的,如果需要在项目中实现一些更为复杂的约束描述,建议暂时还是不要直接使用。在OptaPlanner的用户手册中,也有相关的提示;大家看情况而用。

OptaPlanner的新约束表达方式 Constraint Streams

  最近一段时间OptaPlanner更新算比较频繁,但从网站上的更新内容看到,很多版本尽管隔了很长时间,但接口上的更新内容却不多。我向Geoffrey查询过,他表示这些版本更多的情况是在实现一些引擎内部的优化和一些新的内部运算功能,但这些功能不一定反映到API上,因此对于我们使用者来说,并没有太大的变化。可是如果大家也跟进将OptaPlanner的程序包也更新到最新版本,就会发现,很多一些常用的接口、方法,都已经被标准为将为放弃,从Javadocs上可以看到一些当前版本被标识为@Deprecated的方法、成员,已明确说明将在8.x中停止使用。

  上述功能希望可以帮大家理解并应用OptaPlanner的第四种评分方式。

有好些时间没有写过关于OptaPlanner的东西了,其实近半年来,OptaPlanner还是推出了不少有用、好用的新特性。包括本文讲到的以Stream接口实现评分编程。关于OptraPlanner的约束详细用法,可以参考官方资料:

Constraint streams score calculation​docs.optaplanner.org

最近几个版本推出的新功能、特性中,有不少功能还处于初始探索阶段,甚至有些功能还未成体系,包括我在上一篇文件中推出的SolverManger实现批量异步规划。此功能尚未支持ProblemChanged接口,从而无法实现Realtime Planning. 因此,若需要将这些功能应用于项目实践,还请自行作详细调查分析,以免在项目中处于进退两难境地。

PS. 任何技术都一样,功能、版本越新,带来的收益越高,当然需要面对的风险也越高。

对OptaPlanner有初步认识都清楚,我们使用OptaPlanner规划建模时,需要在模型中表达一系列约束,以描述各个业务实体的约束和规划的优化目标。以往通常有两种方式实现评分逻辑(详细可分为3种)。分别是:

  1. 通过Drools脚本中的Rule来描述约束并进行评分;
  2. 通过Java编写评分逻辑,通过Java编辑评分逻辑又分为:
    1. Java简易评分 - Easy Java score calculation
    2. Java增量评分 - Incremental Java score calculation

从7.31版本开始提供的constraint streams属于Java增量评分的一种。在普通的Java增量评分中,我们需要针对各个约束逻辑,编辑相应的判断,并在满足一定条件后,通过ScoreHolder对象进行记分。引擎会将各个层次的分数进行累加,成为当前方案的总分。Constraint Streams的原理也一样,只是通过强大的Stream特性,令评分逻辑更为简洁,使用更短的代码即可实现更丰富的逻辑描述。

关于Java的Stream特性(Java1.8及以后的版本才出现)的使用方法,可自行通过其它网络资源学习,本文假设读者熟悉Java Stream的各种用法。

我们先以一个简单的示例说明Constraint streams接口的使用方法:

private int doNotAssignAnn() {
        int softScore = 0;
        schedule.getShiftList().stream()
                .filter(Shift::isEmployeeAnn)
                .forEach(shift -> {
                    softScore -= 1;
                });
        return softScore;
    }

通过上述代码块是一Java简易评分的示例,从方法名doNotAssignAnn就很容易理解到,该约束的作用是“使得任务不要分配给Ann”。我们知道在OptaPlanner里,评分通常都是负数,表示惩罚一个行为,令引擎找出尽可能规避这种行为的方案。示例中使用了Java的Stream功能进行判断和过滤。其逻辑是:从班次列表中找出所有分配给了Ann的班次,对每一个满足这个条件的班次进行扣分,并把分数加总作为方法的返回值。

那么同样的约束要求,使用Constraint Stream应该如何实现呢?见以下代码:

private Constraint doNotAssignAnn(ConstraintFactory factory) {
        return factory.from(Shift.class)
                .filter(Shift::isEmployeeAnn)
                .penalize("Don't assign Ann", HardSoftScore.ONE_SOFT);
    }

先要提醒一下,与Java简单评分法类似(评分类需要实现EasyScoreCalculator接口),OptaPlanner的Constraint Stream提供一个名为ConstraintProvider的接口,实现评分的类需要实现这个接口,这个接口只有一个需要实现的方法 - defineConstraints,它传入ConstrantFactory类,返回一个Constraint数组,数组的元素就是已进行了评分和惩罚的各个约束对象。上面的代码中可以看到,doNotAssignAnn方法返回一个Constraint对象,这个对象表示了对Ann被分配到的班次数的惩罚分数。上述代码可以看到,我们只需要对ConstraintFactory的对象factory进行Stream操作,一步即可完成判断、过滤和惩罚三个操作,完成这些操作后会得到一个操作过的Contraint对象,返回该对象即可。上述代码中,对于factory的三步操作也相当明了,大家可以自己理解。

但是对于一些更复杂的判断,其实现步骤与模式也一样,只不过需要编写一些更复杂的Lambda表达式来进行判断、过滤和各种运算。如下代码:

  private Constraint requiredCpuPowerTotal(ConstraintFactory factory) {
        return factory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
                .filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
                .penalize("requiredCpuPowerTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower());
    }

该代码是CloudBalance中用于,计算限制一台计划机被分配超出其CPU运算能力的约束。大家可以回想,或从官方示例中看一下CloudBalance的其中一个最基本约束 - 每台计算机所分得的CPU需求,不可超过该计算机的可用CPU能力。

因此,可以看到,factory除了过from操作获得所有Process对象,通过filter对Process进行过滤,通过penalize进行计分外。factory对象还有一个groupBy方法,用于对所有Process中的Computer进行分组并加总每一组(即每个Computer)的所有CPU计算能力需求量。因此,在filter方法中,就找出那些超出CPU能力的Computer(即分组),在penalize方法中,对整所有超出CPU需求中的计算进行扣分,扣分值是超出部分。

由此可能,OptaPlanner提供的Constraint Stream可以进行更复杂的条件判断,至于这种方法是否更好用,就取决于大家对Stream(类似C#中的Linq)的熟悉程度。

至于整个Constraint Stream代码的结果方式,即上面提到的实现ConstraintProvider接口的代码如下(摘自官方示例CloudBalance):

public class CloudBalancingConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                requiredCpuPowerTotal(constraintFactory),
                requiredMemoryTotal(constraintFactory),
                requiredNetworkBandwidthTotal(constraintFactory),
                computerCost(constraintFactory)
        };
    }

    // ************************************************************************
    // Hard constraints
    // ************************************************************************

    private Constraint requiredCpuPowerTotal(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
                .filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
                .penalize("requiredCpuPowerTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower());
    }
.
.
.

重复提示一下,Constraint Stream功能是7.31版才开始提供的功能,从功能接口上应该是未够成功的,如果需要在项目中实现一些更为复杂的约束描述,建议暂时还是不要直接使用。在OptaPlanner的用户手册中,也有相关的提示;大家看情况而用。

OptaPlanner的新约束表达方式 Constraint Streams

最近一段时间OptaPlanner更新算比较频繁,但从网站上的更新内容看到,很多版本尽管隔了很长时间,但接口上的更新内容却不多。我向Geoffrey查询过,他表示这些版本更多的情况是在实现一些引擎内部的优化和一些新的内部运算功能,但这些功能不一定反映到API上,因此对于我们使用者来说,并没有太大的变化。可是如果大家也跟进将OptaPlanner的程序包也更新到最新版本,就会发现,很多一些常用的接口、方法,都已经被标准为将为放弃,从Javadocs上可以看到一些当前版本被标识为@Deprecated的方法、成员,已明确说明将在8.x中停止使用。

 

本系列文章在公众号不定时连载,请关注公众号(让APS成为可能)及时接收,二维码:

 

OptaPlanner的新约束表达方式 Constraint Streams


如需了解更多关于Optaplanner的应用,请发电邮致:kentbill@gmail.com
或到讨论组发表你的意见:https://groups.google.com/forum/#!forum/optaplanner-cn
若有需要可添加本人微信(13631823503)或QQ(12977379)实时沟通,但因本人日常工作繁忙,通过微信,QQ等工具可能无法深入沟通,较复杂的问题,建议以邮件或讨论组方式提出。(讨论组属于google邮件列表,国内网络可能较难访问,需自行解决)

 

上述功能希望可以帮大家理解并应用OptaPlanner的第四种评分方式。

上一篇:Zoey.Dapper--Dapper扩展之把SQL语句放到文件中


下一篇:Vehicle routing with Optaplanner graph-theory