调度系统的禁忌算法研究与实现毕业设计答辩.ppt
《调度系统的禁忌算法研究与实现毕业设计答辩.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; begin initial
5、ize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va,禁忌搜索算法原理与实现,以上程序中的关键在于: 禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu list,也可以把和当前值在同一“等高线”上的都放进tabu list。 为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太大容易陷入“局部极优解”。 上述程序段中对best_to_far的操作是直接赋值为最优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 调度 系统 禁忌 算法 研究 实现 毕业设计 答辩
链接地址:https://www.31doc.com/p-5190737.html