记得两年前,因为项目需要第一次接触Drools,优秀的文档,强大的机能记忆犹新。之后一直留意Drools的发展。
这两天项目间隙,突然兴起,研究了一下Drools planner(以下简称planner) ,发现这也是一个非常实用的用于规划的开发框架。以前怎么没注意这位小兄弟? 以前看的多写的少,今天也将心得分享一下。
(一)预备知识
1) TSP(旅行者问题)
这是一个运筹学经常提及的课题,内容是这样的:旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。
咋一看,这很简单嘛,只要n确定了,城市间的距离也知道了,遍历所有的组合就行了。但是当n很大时,该组合会出现指数型增长,计算量会变得非常大,对于有限的时间和空间来说,可以认为不可计算。
这种问题在数学上就叫做 NP-complete(NPC)问题。
注:关于P/NP/NPC/NPH等概念,网上有解释很多,感兴趣的朋友可查下维基,这里不占用篇幅。
2)关于启发式算法
要解决上述问题,常规的确定性算法(如:暴力求解)就行不通了,这时需要用 不确定性算法 才能解决。
显然,planner的设计者都是这方面的行家,planner中使用了大量算法,其中重要的一类是启发算法(heuristic algorithm)。
启发式算法的发展: (以下内容转自 csdn aris_zzy的博客)
启发式算法的计算量都比较大,所以启发式算法伴随着计算机技术的发展,取得了巨大的成就。
40年代:由于实际需要,提出了启发式算法(快速有效)。
50年代:逐步繁荣,其中 贪婪算法和局部搜索 等到人们的关注。
60年代: 反思,发现以前提出的启发式算法速度很快,但是解得质量不能保证,而且对大规模的问题仍然无能为力(收敛速度慢)。
70年代:计算复杂性理论的提出,NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快,但解不好的原因主要是他们只是在局部的区域内找解,等到的解没有全局最优性。
由此必须引入新的搜索机制和策略………..
Holland的遗传算法出现了(Genetic Algorithm)再次引发了人们研究启发式算法的兴趣。
80年代以后:
模拟退火算法(Simulated Annealing Algorithm),人工神经网络(Artificial Neural Network),禁忌搜索(Tabu Search)相继出现。
最近比较热或刚热过去的:
演化算法(Evolutionary Algorithm), 蚁群算法(Ant Algorithms), 拟人拟物算法,量子算法等。
好了就到这儿吧,言归正传。
(二)什么是 Drools planner?
planner是一个轻量级,可嵌入规划引擎,优化规划问题的框架。
它适用于解决以下问题:
员工轮班:排班护士,修理工,…
议程安排:安排会议,约会,维修工作,广告,…
教学时间表:排课,课程,考试,会议介绍,…
车辆路径:规划车辆(卡车,火车,船只,飞机,……)运费和(或)人
装箱问题:灌装容器,卡车,船只和储存仓库,以及云计算机节点,…
作业车间调度:策划汽车装配线规划,机器的队列,劳动力的任务规划,…
下料问题:同时最大限度地减少浪费:剪纸,钢,地毯,…
运动计划:计划的足球联赛,棒球联盟,…
金融投资组合优化:优化,风险分散,…
。。。
(只要涉及规划计划之类的通吃啊)
planner 结合了优化算法(包括如禁忌搜索算法和模拟退火)与规则引擎提供的分数计算的能力,让Java程序员高效地解决规划问题。
注意这里提到的分数计算用到了规则引擎Drools,除此之外,应当说它是一个比较独立的应用。
(三)planner 中的算法
下面列出了planner 中涉及的算法。算法是整个框架的灵魂。
分类 | 算法名 | planner 实现情况 |
Exact algorithms(精确算法) | ||
Brute force(强力算法) | 已实现 | |
Branch and bound(分枝界限法) | 未实现 | |
Construction heuristics(建设启发式算法) | ||
First Fit(首次适应算法) | 已实现 | |
First Fit Decreasing(首次适应递减算法) | 已实现 | |
Best Fit(最佳适应算法) | 已实现 | |
Best Fit Decreasing(最佳适应递减算法) | 已实现 | |
Cheapest Insertion(增量最小插入法) | 未实现 | |
Metaheuristics(现代启发式算法) | ||
Local search(局部搜索算法) | ||
Hill-climbing(爬山法) | 已实现 | |
Tabu search(禁忌搜索算法) | 已实现 | |
Evolutionary algorithms(进化算法) | ||
Simulated annealing(模拟退火法) | 未实现 | |
Evolutionary strategies(进化策略) | 未实现 | |
Genetic algorithms(遗传算法) | 未实现 |
注:(本文使用最新版:5.4.0Final) ○ 算法已实现 × 算法未实现
由上表可见,planner还处于成长期,一些复杂算法还有待实现。
下面给出一些已实现算法的介绍:
Brute force(强力算法):
暴力的人生无需解释。。。
First Fit(首次适应算法):
从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小的空闲区,在高地址空间保留大的空闲区。
First Fit Decreasing(首次适应降序算法):
顾名思义,在First Fit 基础上加入了排序,以提高匹配效率
Best Fit(最佳适应算法):
从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法能使碎片尽量小。为适应此算法,空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区,但造成许多小的空闲区。
Best Fit Decreasing(最佳适应降序算法):
同样为Best Fit 的改良版
Hill-climbing(爬山法):
是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。 爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。
Tabu search(禁忌搜索算法):
局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。
它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试 探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选 择,指导下一步的搜索方向,这就是Tabu表的建立。
如果不是数学专业的看到这里会有压力。好在这些算法planner已经实现了,剩下的问题是如何选择的问题。 当然如何选择也不简单。
好了今天收工了,下回接着写开发流程。
相关推荐
规则引擎 用户手册 可以用于初学者学习和使用,也方便开发人员应用于实际的项目中。
drools drools drools drools drools
Jbpm的Guvnor知识库操作文档 Drools Introduction Drools Fusion Drools Flow Drools Guvnor Drools Planner
drools
Drools开发最全中文版技术指南。 Drools开发最全中文版技术指南,介绍了常见的drools如何进行开发,注意是:中文版中文版中文版! drools 中文文档 规则引擎 drools6 drools7 Java
9 Drools WorkBench使用9.1 WorkBench基本使用9.2 创建会话9.3 编译并部署9.4 执行代码10 Drools决策表入门11 Drools决策表加强12 Drools决策表整合Springboot和MybatiesPlus13 动态编译Class文件实现Drools规则调用...
drools最新版本学习资料,里面系统的介绍了drools规则引擎的简介以及集成到项目的教程内容。欢迎下载,收集不易,欢迎点赞。
drools动态生成规则文件
drools决策表模版
drools使用的jar包,运行官方drools-distribution-7.7.0.Final drools使用的jar包,运行官方drools-distribution-7.7.0.Final drools使用的jar包,运行官方drools-distribution-7.7.0.Final drools使用的jar包,运行...
Drools6.5 部署Drools Workbench和Kie Server 自己在学习drools规则引擎时候的笔记,记录了如何使用Drools Workbench和Kie Server。 我使用的版本是6.5
官网Drools5.3使用手册,有介绍与spring jbpm drools集成等内容
This book as its title suggest is for newcomers to drools. As explained in the drools tutorial, when using drools you will change the classical development paradigm you are using going from ...
Drools workbench文件及DEMO项目代码
drools calendar 使用demo
Drools是一款基于java的开源规则引擎 ,要求JDK1.5或以上版本。正所谓学习一门语言都是从环境开始。搭建环境,测试第一个HELLOWORD
Drools JBoss Rules 5.0 Developer's GuideDevelop rules-based business logic using the Drools platform
drools6的demo
jboss 规则引擎 drools库。 api,core,compiler,jsr94 drools-compiler-5.1.1.jar
english drools 6 Official document