网站是灰色系的网站,c2c电子商务平台有哪些,dw软件主要做什么,怎么查网站注册时间在之前的文章中#xff0c;老猿已介绍过APS及规划的相关内容#xff0c;也对Optaplanner相关的概念和一些使用示例进行过介绍#xff0c;接下来的文章中#xff0c;我会自己做一个规划小程序 - 一个关于把任务分配到不同的机台上进行作来的小程序#xff0c;并在这个小程序… 在之前的文章中老猿已介绍过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中是如何体现的。 一个IT老农先尽力好当儿子、丈夫和父亲的责任然后做点有趣的事。
