Optaplanner规划引擎的工作原理及简单示例(1)

时间:2024-05-10 12:35:32

  在之前的文章中,老猿已介绍过APS及规划的相关内容,也对Optaplanner相关的概念和一些使用示例进行过介绍,接下来的文章中,我会自己做一个规划小程序 - 一个关于把任务分配到不同的机台上进行作来的小程序,并在这个小程序的基础上对Optaplanner中更多的概念,功能,及使用方法进行讲解。但在此之前,我需要先讲解一下Optaplanner在运行规则运算的原理。所以,本文是讲述一些关于寻找最优解的过程中的原理性的内容,作为后续通过示例深入讲解的基础。但这些原理知识不会涉及过分深奥的数学算法,毕竟我们的目标不是写一个新的规划引擎出来,只是理解一些概念,用于理解Optaplanner是依据什么找出一个相对优解的。好让在接下来的一系列文章中,可以快速无障碍地理解我所讲解的更细化的Optaplanner功能。

  好了,言归正传,本文主要是讲述Optaplanner是如何在用户定义的规则限制条件中,基于约束的限制,对被规划对象进行排列组合,再对比各个组合(称作解,或方案),并找出相对最优的解出来。在这个寻优过程中,Optaplanner会使用到一些相关算法,例如启发式算法(例如First Fit)和延迟接受法(例如禁忌搜索),从而提高寻找相对最优解的效率和防止嵌入局部最优解,从而可以在固定的时间内,找到尽可能优的方案。

  在理解Optapalnner是如何实现之前,我们先复习并展开一下上一篇提到的概念 - 约束。

约束(Constraint):

  也就是对事物的一种限制,规定事物的发展应该遵循什么规则,具体到Optaplanner里,就是用于表达出什么是对的,什么是错的,什么情况是最优,什么情况次优,什么情况较差。从而让引擎得到各个解的对比依据。

  在Optapalnner中的约束可以分为硬约束软约束两种,其实还有更多的约束类型 ,例如中间约束,甚至是无限层级的约束,但总结起来,其作用也就是把约束划分为不同层级,从而区分出不同的优等级而已,如果有软件开发经验的同学,可以理解不同层级的约束,分别是SQL语句里Order By子句后面的字段次序。在进行记录排序时,前面的字段排列的优先级,是从性质上优先于后面的字段的,大家理解了Order By子句,也就理解了不同层级约束的问题了。拉下来我们以最简单的软硬约束,来分析一下约束的作用。

硬约束:

  硬约束是用来规定什么情况是对的,什么情况是错的;什么组合是好的,什么组合是不好的......也就是它通常是用来对所得的解进行一些定性的状态定义。例如一个计划是否可行,例如会不会同一个机台同一个时间分配了两个不同的任务(假设每个机台同时只能做同一个任务)。一个员工所排班次是否正确(例如一个员工是否被安排了三个连续的班次)。若出现上种情况,即表示违反了硬约束,这种方案称作不可行方案。以后的文章里,会提到Optaplanner里有一个明确的概念 - Feasable Solution(可行方案,或称可行解),就是表示这个方案是完全符合硬约束的。

软约束:

  软约束规定什么情况最优,什么情况次优,什么情况是差的;它是用来定义方案优劣的定量状态。例如:一个计划的成本是否足够低;一个排班表到底有多大程度上的合理性,例如一个人正常情况下是需要5天工作制的,但如果遇到特殊情况,也可以连续工作6天,但这种情况是特殊的,需要额外付加班费(成本上升)最好不要出现这种情况。那么在编制这个排班表的时候,如果有一个方案是需要有人员连续工作6天,但如果找到另一个方案,可以令所有人均不需要连续工作6天,那么,后面这个方案就比那些有人需要连续工作6天的方案更好了。体现在软约束上,就是后面的排产表,其软约束上会比前一个排班表更好,违反的软约束更少。

  上述讲述的是两种常见约束,那么这些约束在Optaplanner里是如何生效的呢?那说需要有一种评分机制了,也是我们在使用Optaplanner里,比较难准确把握的一个内容之一。

评分机制:评分是用分数来评价事物特性的一种方法。但如果我们细心观察总结一下,会发现评份是可以通过两种方向来评价的;分别是正评分(奖励性评分)和负评分(惩罚性评分)。

正评分:通过获得分数的多少,来体现事物的优劣。例如我们在学校考试过程中,成绩是通过一种正分数来体现的,即做对一题奖励相应的分数,分数越高成绩越好;完美状态是获得满分。

负评分:通过扣除分数的多少,来体现事物的优劣。例如我们的驾驶证记分制,每违章一次就扣除相应的分数,很明显这种评份体系中,分数越低越好,也就是扣得越少越好;完美状态是扣0分。

  在对实际问题进行约束规划时,是一种封闭性约束,也就是约定事物往指定的一个方向发现,使用负评分的方式,很显然更合理。也就是一个方案有哪些不好的,我们通过对它评定一些惩罚分数标准,告诉引擎这种组合出现了一些不太好的情况。如此类推,每找到一个更佳、扣分更少的方案,就离完美就更近一步。无论是使用正方向评份还是反方向评分(或称负方向评分),在Optaplanner里都是可以实现的,只不过按我们日常的逻辑,在定义方案时,通常我们只会根据业务定义出一些规则,方案是需要守这些规则,当一个方案出现有违反规则时,就作出相应的惩罚性扣分;这种方法比当出现好的情况就加分更合理。因为我们的现实世界里,"好"是可能无限好的,当问题足够复杂,数据量足够大,即问题规模够大时,描述一个方案如何个好法,其实很难是一个定数。比描述一个方案如何个差法更难,因为前者可以是无限的,而后都就只需要我们定义好什么是差的标准,一但问题范围确定,它的最差情况(也就是最差的扣分情况)就有一个字数了。所以,在Optaplanner的世界里,常见的做法是,定义一些约束,并设定相应的惩罚分数标准(即将约束量化),用来描述这个方案的制约因素,当这个约束实打破时,就作出惩罚性记分,那么到最后,扣分越少的方案就越好。这就是Optaplanner实现寻优的最基本原理,但其实现是非常复杂的,会将问题划分为很多种类,将寻优的过程划分为多个阶段,每个阶段利用不同种类的算法来提高找到更优方案的效率,每个阶段有很多个步骤,每个步骤又有多个移动(没错,Optaplanner里就有Step与Move的概念,以后会详解);在以后的深入文章中,我会详细把这个过程分析出来。

  上面描述了硬约束、软约束和评份机制。那么如何将这两种约束与这种评分机制关联起来,令评分机制可以实现软、硬约束呢?大家可能已想到,在Optaplanner给出了软分数,硬分数的概念。在评分机制中,当出现一个方案违反了某个硬约束时,就给这个方案扣除这个约束相应的分数;同样地,当该方案违反了一种软约束时,就对该方案扣除该软约束相应的分数。这两个分数是分开处理的。因为通过它们对应的约束类别就知道,它们分别代表的性质不一样,硬分数对应的硬约束,代表的是一种定性评价;即描述方案好不好,行不行,可不可取等,一旦被记扣硬分数,那就表示这个方案的性质就变了,由可行方案变成不可行方案。理想的方案是一个硬分都不能扣的,一旦扣了就是不可行方案了。有人问,那么定义硬分数的分值有什么用?直接给一个标识出来,将方案的可用性定义为True or False,分别代表是事有硬约束被违反不就行了吗,多简单呀,因为一旦为False就是不可用了,再去讨论它扣了多少分,又有何意义呢?硬约束、硬分数不就是为了给方案定性而设立的吗?何必还要记录它的扣分量,多此一举呢?

  如果这样想,就是一种不全面的想法了。因为大家需要明白,现实世界往往是很大程度是不完美的,但而对不完美,我们是放弃这个世界,还是在不完美中进行坚持,对这个不完美的世界,朝完美的方向进行改造呢?上面的说法就比较抽象比较虚了,举个大家容易理解的例子。例如:刑法是用来惩罚犯罪的,在正常的法治社会中,犯罪对于一个人说,就相当于违反了硬约束(刑事处罚记录是终身跟随的)。也就是对于一个人来说,一生中是否触犯过刑法,是一个定性的问题。那么既然是定性问题,我们在设立刑法的时候,其对应的惩罚是不是只有一种就足够了呢?例如凡是触犯刑法,全部判死刑,那不就简单得多啦?事实上人类社会是不可能这样的,因为就算是触犯了刑法(这个已经是定性问题),但罪行也有轻重之分的、对应了刑法的不同条款,有些罪名经过对罪犯的惩戒,是可以再给他一次机会的,也说就是说触犯的刑法,是有轻重之分的,但性质不会变,他在国家司法机关的档案里,永远留有普被刑事处理的记录。所以,这可以称该种情况为定性范围内的定量问题。就是一个人做错了就是错了,其性质已经定了,但犯的错误有多大,还得是一个定量问题。因此,硬约束对应的扣除硬的分数有多有少就不难理解了。就是我们的方案如果出现了违反硬约束、被扣除了硬分数的,它在Optaplanner上就是一个不可行方案了。但是在众多的不可行方案里,其实还要区分哪个是更不可行,哪些其实只是违反了一点点,还是“稍为可行的”。回到我们的实际排程问题中,有可能客观条件限制,我们所有排出来的方案(例如生产计划、排班表、车辆调试线路图)都是不可行的,例如:我们排生产计划的时候,将交货期延误作为一种硬约束,但是现实的生产活动中,确确实实有可能无论你怎么排,因为产能、资源限制等因素,你是不可能找到一个完完全全符合交期的生产计划的,那么这个时间我们就需要找出一个违反得最小的计划出来,作为可行计划,视情况进行相应的修改并执行了。也就是说两害相遇取其轻。

  对于硬约束,除了上述讲到,当出现有可能确实需要使用不可行方案作为执行计划的情况外,在Optaplanner进行规则的过程中,其实也起到非常大作用的。先不说optaplanner引来来排程;如果让你来排,对于各种硬约束,全都不给出一个分数,而是给一个定性的标识,就是一旦出现违反了,就报一个违反硬约束的消息出来,你会怎么样?你肯定会抱怨提示的信息太简陋了,只有一个标识,最多只是知道哪里违反了,再也没有更详细的信息供你参考了。那你接下来的排产活动,其实就是一个组合一个组合逐一地去碰彩了。因为各个方案之间是否有关联,你是无法得知的,所以你根本找不到什么好的办法去将各种情况下的方案进行归类、比较进行往指定的一个方向收敛。但如果在一个硬约束被违反时,会出现一些明确的信息,是哪个硬约束被违反了。违反和程度是多少,扣了多少分,是因为哪个被规则的对象,放在哪里,或与哪个对象相邻从而导致的硬约束被违反。这样就形成了一个很明确指导方向,对于人而言,通过归纳统计就知道某些情况肯定会出现,或极大可能会出现违反硬约束的情况,那我们就可以在排列新方案时,尽力去避免这种情况了;也就是有了参考方向 。对于Optaplanner引擎来说也是同理,尽管它不像人这么聪明(但最从近的消息来看,Optapalnner团队已经着手思考人工智能引入到引擎中,从而实现如上述人类一样对这类问题进行归纳思考),但也能够作为其寻找更佳方案的过程中的一些很重要的参考,从而为寻优算法所用,进而提高寻优效率。例如遗传算法。

  软分数对应的软约束,代表的是一种定量评价;即描述方案有多好、有多差,成本有多高、有多低。它是一种优化约束,即在定义它的时候,就已经知道它必然是被违反的(也有可能完全不违反,那当然是好的,但如果是这样的话,就脱离了软约束的初充了)。所以,软件约束、软件分数的扣分值用途相对来说就容易理解得多了。

   综上所述,Optaplanner就是通过一种体现为分数的约束机制,进行寻找最优组合。当一个排产问题中,设定的软硬两种约束时,它会优先满足硬约束的要求,再满足软约束的要求,也就是说,软约束被扣为1万分,也不及硬约束被扣了1分重要,联系上面的SQL语句中的Order By子句的例子。

  Optaplanner其利用途径有以下两点:

1. 用分数来确定,一个方案是否可行,是优是劣;

2. 在决定每一步的时候,参考上一点的扣分情况,来确定下一次生成方法时,应该考虑哪此因素(想想遗传算法).

  这一篇我们先讲解一下原理,打一下基础,下一篇将用一个任务与机台的例子来说明一下这些原理在Optaplanner中是如何体现的。


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

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