《调度系统的禁忌算法研究与实现毕业设计答辩.ppt》由会员分享，可在线阅读，更多相关《调度系统的禁忌算法研究与实现毕业设计答辩.ppt（15页珍藏版）》请在三一办公上搜索。
1、指导教师：,调度系统禁忌搜索算法研究与实现,班级：学生：学号：,背景 调度系统遍及与生产、生活中的各个领域之中，它的存在有效的减少了时间、资源的浪费，提高了生产上的效率。然而众多的调度系统所采用的调度算法也是各种各样的，不同的算法间有着各自的优点与缺点。意义 禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，建立Tabu表,避免l了陷入局部最优解。它的运算方式在解决复杂的网状联系问题是效
2、果显著。,系统的背景及意义,研究的方向与欲达成的目标,研究目标本课题的研究主要要达成的目标是实现禁忌搜索算法，并对此算法有一定的了解，可以通过它解决一些问题。在解决问题的同时可以比较数据的执行结果，便于方案的选定。研究问题通过此算法完成TSP,即Traveling Saleman Problem,也就是旅行商问题,给出一组合理的解。tsp问题的十分经典的智能搜索问题之一。,论文的结构,第一部分系统的研究背景第二部分禁忌搜索算法原理与实现第三部分系统需求分析第四部分系统概要设计第五部分系统展示及代码实现,论文主要内容,第一部分系统的研究背景 现有的调度系统是存在有一定的缺陷的，以在多个相连地点中
3、寻求任意两点相连的最短路径为例，当地点数较少时，我们可以挨个尝试进而进行比较得出最优解，可是当地点数大到一定程度的时候，穷举法就不现实了。这正是调度系统也存在的问题，我们既要求调度系统做出正确的路径，同时要求它在有效的时间做出，这就显然成为了矛盾的所在。没有穷举过自然就无法说某条路径是最优的，因此折中的办法就是在有限的时间里，找到一条较优的路径，而这些正是本课题所研究的。,论文主要内容,第二部分禁忌搜索算法原理与实现什么是禁忌算法TS是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值减少最多的
4、移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。Tabu表中保存了最近若干次迭代过程中所实现的移动的反方向移动，凡是处于Tabu表中的移动，在当前迭代过程中是不允许实现的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解群，从而防止了循环，帮助算法摆脱局部最优解。另外，为了尽可能不错过产生最优解的“移动”，TS搜索还采用“释放准则”的策略。,禁忌搜索算法原理与实现,禁忌算法的伪码实现procedure tabu search;begininitialize a string vc
5、 at random,clear up the tabu list;cur:=vc;repeatselect a new string vn in the neighborhood of vc;if va,禁忌搜索算法原理与实现,以上程序中的关键在于：禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当前值在同一“等高线”上的都放进tabu list。为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太大容易陷入“局部极优解”。上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于b
6、est_to_far的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。,终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终止搜索；邻域：由伪码 select a new string vn in the neighborhood of vc,可以看出,系统总是在初始点的邻域搜索可能的解的,因而必须定义适合的邻域定义,如果解空间的存在一个最优解X*,初始搜索点为S0,那么如果S0不存在到达X*的通路,就会使搜索陷入S0的邻域的局部最优解。可以证明
7、如果邻域满足对称性条件，则在假设禁忌表足够长的情况下必然可搜索到全局最优解。,禁忌搜索算法原理与实现,禁忌搜索算法的实现步骤（1）给定算法参数，随机产生初始解x，置禁忌表为空。（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。（3）利用当前解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。（5）判断候选解对应的各对象的
8、禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。（6）转步骤（2）。,禁忌搜索算法原理与实现,禁忌搜索算法中的一些名词解释(1)移动TS搜索过程由“移动”来实现，一次“移动”产生一个实验解。现已有多种“移动”方法。(2)Tabu表Tabu表中允许储存的Tabu“移动”的最大数目称为Tabu表规模。如何给定Tabu表的规模对寻优过程有重要的影响。一般而言，应随问题规模的增大而增大，但如何给定其最优数值仍是一个有待研究的问题。(3)释放水平TS对Tabu表中的Tabu“移动”都赋予一个释放水平。如果一个Tabu“移动”达到了释
9、放水平，则该“移动”不被限制，可以实现，即可作为下一步的搜索方向。释放水平的作用是为了在每次迭代中能实现最有价值的“移动”，从而可更有效地找到最优解。,禁忌算法的优缺点,优点：对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.缺点：TS对于初始解的依赖性较强。一个好的初始解可使TS在解空间中搜索到更好的解，而一个差的初始解则会降低TS的收敛速度，搜索到的解也相对较差。TS的另一个缺点是搜索只是单-单操作，即搜索过程中初始解只能有一个，在每代也只是把一个解移动到另一解。,系统实现的内容,系统的主要模块数据执行模块实现城市数量
10、、运行代数、每次搜索邻居个数、禁忌长度的自由设置，点击查询按钮可以实现结果数据的页面显示。数据源配置模块点击文件导入，可实现文件的寻找并将城市数量、备注等一些必要的信息录入，上传到数据库中。数据执行结果查询模块将历史记录结果从数据库中取出并显示，它可以实现对结果的不同条件的组合查询，便于数据的分析。,全文总结,在这个ppt中我简要的介绍了毕业设计论文的一些模块，重点介绍了禁忌搜索算法的概念及一些要点知识。最后简要描述了本系统的构成。为了这次的毕业设计，我通过阅读大量的书籍，浏览互联网查找资料等方式，学习了禁忌搜索这一先进的搜索算法，对调度系统的调度方法等有了较为全面的了解，同时也掌握了一定的学习方法。,大学本科的学习生活即将结束。在此，我要感谢所有曾经教导过我的老师和关心过我的同学，他们在我成长过程中给予了我很大的帮助。最后向所有关心和帮助过我的人表示真心的感谢。,致谢,
