开源线性规划器optaplanner

发表于 | 分类于 阅读次数:

前言

optaplanner为一个开源的整数规划求解器，不仅可以计算N皇后等经典算法问题，还可以解决目前很多现实问题，例如：

  • 最短路线

  • 服务器负载

  • 课表安排
    等等

    • 其有着相对较快的求解速度以及多种约束编写方式。

    软件更新速度相对较快并且文档丰富特别的perfect。

    模型及约束基本设计流程

    1.基本流程

    设计一个结果载体及各种决策变量，开始计算前，我们先初始化所有决策变量及结果变量，计算时由解法器解法器根据规则具体决定填充到哪个将决策变量田中到结果中的哪个位置，例如在一个课表编排中，决策变量可以是时间，结果变量是一个课程，课程上边有空着的时间槽，用来填充时间，当计算完成时，时间也就被填充到了课表变量上，那么，我们就得到了一个课程具体上课的时间。

    2.模型

    解法器要求使用@PlanningSolution标记的类来作为模型存放及各种变量的类，使用@PlanningEntity作为被计算的类，@PlanningEntity中需要解法器填充的变量来自于@PlanningSolution，也就是解法器中的 @ValueRangeProvider(id = "times")和
    @ProblemFactCollectionProperty标记的变量提供者集合，而@PlanningEntity的变量需要通过@PlanningVariable(valueRangeProviderRefs = "times")来指定需要采用哪个变量提供者

    在初始化中，需要将@PlanningSolution中的所有变量初始化，@PlanningEntity中的三件套和其他基本属性初始化，变量无需初始化，这些变量将由解法器填充

    有时候也可以在初始化的时候将变量也初始化到@PlanningEntity中，减少解法器的计算时间

    @Score为解法器为结果打分的载体

    3.约束文件

    约束文件有一种特殊的语言来编写，drl

    科目的规则文件（约束）通过drl文件来编写，drl有特殊的语法，rule为具体的规则名称，when中为需要匹配的对象，then为匹配成功后需要执行的操作(在本模型中使用扣分的方式来约束最终的结果)，then内的代码为JAVA代码

    当when的代码返回为true时，执行then内的代码，也就是说会对模型进行扣分，本排课模型采用Hard/Soft打分机制来打分（@PlanningSoluton中的@PlanningScore），当分数为0/0是为最佳结果，当分数为0/-10是也是可行解，分数为-1/-10时为不可行解

    扣分类型为Hard还是Soft可以通过then内的代码控制，原则上将必须满足的条件归类为Hard约束，目标型的条件归类为Soft约束

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //同年级同班级的科目不在一块上
    rule "basicConstraint"
        when
            ClassSubjectEntity($id : id, $gradeInfo : gradeInfo , time != null, $time : time)
            ClassSubjectEntity(id != $id, gradeInfo.isSameGradeClass($gradeInfo), time == $time)
        then
            scoreHolder.addHardConstraintMatch(kcontext, -1);
    end

    //教师同一时间只上一节课
    rule "basicConstraint2"
        when
            ClassSubjectEntity($id : id, $teacherID : teacherID , time != null, $time : time)
            ClassSubjectEntity(id != $id, teacherID == $teacherID, time == $time)
        then
            scoreHolder.addHardConstraintMatch(kcontext, -1);
    end

    当然，约束文件也可以利用JAVA代码实现，具体详见文档。

    4.配置文件

    一个好的解法器当然离不开配置文件，optaplanner的配置文件细分的十分详细
    配置文件中可以指定计算所关联的类，约束的具体方式，每个计算步骤，计算步骤的具体规则，打分的方式和计算什么时候该停止等等。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    <?xml version="1.0" encoding="UTF-8"?>
    //解法器的具体设置
    <solver>
      <!--<environmentMode>FULL_ASSERT</environmentMode>--><!-- To slowly prove there are no bugs in this code -->
      <!--<moveThreadCount>AUTO</moveThreadCount>--><!-- To solve faster by saturating multiple CPU cores -->

    //结果承载类
    <solutionClass>org.optaplanner.examples.machinereassignment.domain.MachineReassignment</solutionClass>
      
    //结果类
    <entityClass>org.optaplanner.examples.machinereassignment.domain.MrProcessAssignment</entityClass>

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>org.optaplanner.examples.machinereassignment.solver.score.MachineReassignmentIncrementalScoreCalculator</incrementalScoreCalculatorClass>
        <!--<scoreDrl>org/optaplanner/examples/machinereassignment/solver/machineReassignmentScoreRules.drl</scoreDrl>-->
      </scoreDirectorFactory>
      //解法器停下来的规则
      <termination>
        <minutesSpentLimit>5</minutesSpentLimit>
      </termination>
      
      //具体使用哪些解法器的计算规则
      <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
      </constructionHeuristic>
      //自定义计算阶段
      <customPhase>
        <customPhaseCommandClass>org.optaplanner.examples.machinereassignment.solver.solution.initializer.ToOriginalMachineSolutionInitializer</customPhaseCommandClass>
      </customPhase>
      //本地搜索计算阶段
      <localSearch>
        <unionMoveSelector>
          <changeMoveSelector/>
          <swapMoveSelector/>
        </unionMoveSelector>
        <acceptor>
          <entityTabuSize>7</entityTabuSize>
          <!--<lateAcceptanceSize>2000</lateAcceptanceSize>-->
        </acceptor>
        <forager>
          <acceptedCountLimit>2000</acceptedCountLimit>
          <!--<acceptedCountLimit>500</acceptedCountLimit>-->
        </forager>
      </localSearch>
    </solver>