智能排课算法综述.doc

《智能排课算法综述.doc》由会员分享，可在线阅读，更多相关《智能排课算法综述.doc（4页珍藏版）》请在三一办公上搜索。

1、第 19卷 第 8期2009年 8月长 春 大 学 学 报JOURNAL O F CHAN GCHUN UN IV ER S ITYVo l. 19 No. 8A ug. 2009智能排课算法综述张晶 1 , 李广军 2 , 唐远翔 3( 11宜宾学院 图书馆 , 四川 宜宾644007;网络管理中心 , 四川 宜宾644007; 31宜宾学院 计算机系 , 四川21宜宾学院宜宾644007 )摘 要 :介绍了排课问题 ,分析了基于遗传算法 、蚁群算法 、模拟退火算法和免疫算法等智能排课算法的基本原理及其算法特点 ,并对智能排课算法的未来发展做了展望 。关键词 :排课 ;遗传算法 ;蚁群算法

2、;模拟退火算法 ;免疫算法中图分类号 : TP183文献标志码 : A文章编号 : 1009 - 3907 ( 2009) 08 - 0038 - 04化指标 (软约束条件 ) 。111 硬约束条件排课问题的基本任务是做到满足最根本的要 求 ,即对各种资源的安排不产生冲突 。这些基本要求称为硬约束条件 ,正确的排课算法必须满足这些 条件 。同时这些条件一般是固定不变的 ,即不随具体实际情况的不同而变化 。以下是排课问题中的硬 约束条件 :同一时间 ,一个教师不能上一门以上的课程 ;同一时间 ,一个班级不能上一门以上的课程 ; 同 一时间 ,一个教室不能上一门以上的课程 ;教室的座 位数量要不少

3、于所安排班级的学生数等 。112 软约束条件在满足硬约束条件的基础上可选的优化条件称 为软约束条件 。这种约束条件一般是实际中的一些0 引言排课问题实际是时间表问题 ,由于该问题具有 较大实用价值和问题模型的代表性 ,吸引了许多学 者对该问题进行研究 ,从各个角度对问题进行了分 析 。 20 世纪 70 年代中期 ,美国人 S. V EN 等论证了 课表问题是 N P 完全类问题 , 但同时也说明了课表 问题有其自身固有的数学模型 ,即课表问题存在解 , 并且能找到解 。N P 完全问题是指能通过有限次计 算可以解决 ,但是随着问题规模的扩大 ,计算量以指 数规模递增 ,所以排课问题只能通过一

4、些探索算法 寻找近似最优解 。早期研究主要以启发式算法和手 工模拟为主 ,人们把贪心算法 、回溯法和图论算法等 用于解决 N P 完全问题的算法应用于排课问题 , 取 得了一定的效果 。但是启发式算法缺乏智能 ,性能 受限 ,对于大量的排课任务难以推广 。随着人工智 能的发展 ,遗传算法 、蚁群算法 、模拟退火算法和免 疫算法等智能算法在排课问题 的应 用中 也 日益 广 泛 。因此 ,就有必要分析各种智能排课算法的优缺 点 ,并对智能排课算法的未来发展做以展望 。1 排课问题排课问题的实质是将班级 、教师 、课程 、教室安 排在一周内某一不发生冲突的时间 ,并且要满足一 些约束条件 ,保证课

5、表在时间和空间的分配上符合 一切共性和个性的要求 ,并尽量达到全局最优 。在 排课过程中 ,不仅要解决课程安排对时间和空间资 源的有效利用并避免相互冲突 (硬约束条件 ) ,还需特殊的需求或保证上课效果较好 ,课程安排较科学 、合理的规则 。它根据具体排课对象的实际情况不同而不同 ,是衡量排课算法优劣的标准 。例如 ,软约束 条件可以是 :课程尽量安排在教学效果较好的节次 ; 课程分布要均匀 ,如某门课程一周内的几次课应有 一定的时间间隔 ;公共课等涉及面广 、学时多的课程 应优先安排 ;对同一教师 、同一上课对象应尽量选择 相对固定的教室 ;教师提出的对上课时间和地点的特殊要求 ,既可以有时

6、间方面的要求 ,如指定某天 、指定某节次 ,也可以有教室方面的要求 ,如指定教学楼 、指定教室等 。2 智能排课算法分析211 遗传算法由于排课问题是一个多目标的优化问题 ,而遗解决各种具有难度的问题 ,很多学者提出了应用遗二次分配问题 、调度问题等组合优化问题中取得了一系列较好的实验结果 。在研究蚁群算法求解组合 优化难题的基础上 ,可以将课程表问题表示成构造 图的形式 ,提出了许多基于蚁群优化的排课算法 。21211 算法描述自然界中的蚂蚁在寻找食物源时 ,能在走过的 路径上释放一种特有的分泌物 信息素 , 使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行为 。当某路径比较短时 ,

7、在单位时间内来回 搬运食物的蚂蚁在上面通过的次数也越多 ,其留下 的信息素也越来越多 ,以致其强度不断增大 (当然 ,随时间的推移会同时逐渐减弱 ) , 后来蚂蚁选择该 路径的概率也越高 ,从而更增加了该路径的信息素 强度 ,最终所有的蚂蚁都会选择到该路径上来 。蚂 蚁算法的基本原理就是模仿生物世界中的蚂蚁这种 在没有任何可见提示下寻找从其巢穴至食物源的最短路径的能力 ,适应性地搜索问题的最优解 。21212 算法特点 蚁群算法的优点是具有较强的鲁棒性 ,蚂蚁算法的参数数目少 ,设置简单 ,易于将蚂蚁算法应用到 其它组合优化问题的求解中 ;分布式计算 ,该算法是一种基于种群的拟生态系统算法 ,

8、具有本质并行性 , 易于并行实现 ;群算法是一种本质上并行的算法 ,具 有较强的全局搜索能力 ,易于与其它方法结合 。蚁群算法的缺点是需要较长的计算时间 ,容易 出现停滞现象 ;有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增量 ; 采用了信息素 均匀分配策略 ,即对已搜索路径中的所有路段采用 同样的信息素增量 ,与路段的重要性无关 。没有考 虑当连续空间优化问题转换到有向图搜索问题时 , 信息素分配给可行解带来的尺度变化 ,对于连续解空间搜索效率的影响 。因此 ,使用蚂蚁算法需要进 行改进 ,或者与其他启发式算法相结合 。213 模拟退火算法模拟退火算法 ( sim u la te

9、d annea ling, SA )是基于传算 法 解 决 排 课 问 题 。遗 传 算 法 Gene tic A lgo2rithm ,简 记 GA ) 是 1975 年 美 国 M ich igan 大 学 J. Ho lland教授首次提出的 ,并逐渐发展成为一种迭代 自适应启发式概率性搜索算法 。近年来 ,遗传算法 在求解优化问题中得到了成功的运用 。 GA 是一种抽象于生物进化过程的 、基于自然选择和生物遗传 机制的优化技术 ,它是一种全局优化策略 ,能避免陷 入局部最优 。按照 优胜劣汰 、适者生存 的原则 , 通过快速随机搜索力求找到最优解或次优解 。遗传(算法因在解决各类非线性

10、问题时表现出的鲁棒性 、全局最优性 、可并行处理性及高效率而深受实际工 作者的喜爱 ,因此在各种智能算法中 ,该算法在排课 问题中的应用也最广泛 。21111 算法描述 遗传算法在满足排课的必要条件下产生编码 ,称为初始个体 ,编码方法一般采用十进制或二进制 方法 ;然后选择合适的适应度函数 ,计算其值以衡量 个体的优劣程度 ,值越大说明个体越优 ,被选中遗传 的几率越大 ,符合自然进化规律 。接下来 ,判断个体 是否满足约束条件对个体进行选择 、交换或变异等遗传操作 ,以得到更优良的子代种群 ,也就是排课的 更优解 。再计算新一代群体的适应性值 ,如果合适 即输出排课结果 ,否则继续做遗传操

11、作 ,以找到更优 子代 。21112 算法特点遗传算法的优点是一种快捷 、简便 、容错性强的 算法 ,它的搜索过程不直接作用在变量上 ,而是在参 数集进行了编码的个体 ,这使得遗传算法可直接对 结构对象进行操作 。搜索过程从一组解迭代到另一 组解 ,采用同时处理群体中多个个体的方法 ,降低了陷入局部最优解的可能性 ,并易于并行化 。对搜索 空间没有任何特殊要求 ,适应范围广 。该算法缺点是算法本身比较复杂 ,在变量多 ,取 值范围大或无给定范围时 ,收敛速度下降 ,排课耗时 较长 。当约束条件太苛刻时 ,可能没有可行解 。在排课过程中遗传算法的适应度函数 、种群大小 、交叉 率和变异率的选取影

12、响着排课的效率和效果 ,并要 给出了参数的选取参考范围 ,至于何时取得最佳效 果 ,都需要根据具体情况进行分析 。212 蚁群算法蚁群算法由意大利学者 M. Do rigo等人在 20 世 纪 90年代初首先提出 ,蚁群算法具有通用性 、并行 性 、鲁棒性和群体性特征 ,并在求旅行商 TSP 问题 、Mon te Ca rlo 迭 代 求 解 策 略 的 一 种 随 机 寻 优 算 法 。其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性 ( up: 退火过程中 ,固体 最终达到能量最小的状态 ,对应于优化算法最终找 到了最优解 )而设计的一种智能优化算法 。该算法 将固体的

13、退火过程与优化问题的求解过程有机地结合起来 ,因此该算法被称为模拟退火算法 。由于该 算法具有全局收敛性 、操作简单方便等特点 ,因此也 可以采用该算法进行排课 。长 春 大学 学 报第 19卷4021311 算法基本原理算法主要包括新状态产生函数 、新状态接受函 数 、退温函数 、抽样稳定准则和退火结束准则 (简称 三函数两准则 ) 。算法开始时设计一个所谓的初始 温度 。初始温度和上面的三函数两准则将是直接影 响算法优化结果的主要环节 。算法运行时是从某一较高初温开始 ,结合具有概率突跳特性的 M e tropo lis 抽样策略在解空间中随机寻找目标函数的全局最优 解 ,伴随温度参数的不

14、断下降重复抽样过程 ,最终得 到问题的全局最优解 。21312 算法特点模拟退火算法优点是该算法应用在排课问题 中 ,主要适用于具有均匀排课要求的排课问题 ,得到 排课最优解 。随机产生的可行解自然具有均匀性 , 适当选取算法的控制参数 ,能加快获得问题的整体 最优解或近似最优解的收敛速度 。模拟退火算法缺点是算法控制参数的选择比较困难 ,选择不当可能 使迭代不收敛或运行 ; 运行时需要开销更多的系统 资源 。214 免疫算法1986 年 , Fa rm e r等人在工程领域中提出了免疫 概念 ,用免疫算子代替遗传算法中的变异算子从而克服了搜索的盲目性 。利用免疫算法求解排课问题时 ,根据生物

15、免疫系统机理设计 ,将排课的目标和约 束条件作为抗原 ,将问题的解作为抗体 ,对抗体采用 二进制编码 ,对新抗体的繁殖是通过部分交叉和变异算子实现 ,对抗体产生的刺激和抑制通过抗体浓 度调节 ,而抗体浓度通过计算抗体之间的最大亲和 力获得 。对排课问题的测试表明 ,适当调整繁殖参 数 ,能快速获得最优解或近似最优解 。21411 算法原理免疫算法的原理是将抗原作为待求解的问题 , 抗体对应于问题的一个解 ,通过抗原和抗体的亲和 力来描述可行解与最优解的逼近程度 。通过抗体之 间的刺激与抑制 反 应 , 实 现 系统 对环 境 的自 适应 。 主要包括以下流程 : 1 ) 输入目标函数和约束条件

16、 ,并将其作为免疫算法的抗原 ; 2 ) 用二进制编码 , 产 生初始抗体 ; 3 )计算抗体的适应度 ,产生新抗体 ,免 疫选择 ; 4 )群体更新 。21412 算法特点获得 ,收敛速度和最优效果很难两全 。3 智能排课算法的发展方向智能优化算法凭借其简单的算法结构和突出的 问题求解能力 ,吸引了众多研究者的目光 ,并取得了 令人瞩目的成果 ,大量的研究成果证明了智能排课 算法在工程的适用性 。但是 ,由于其理论依据来源 于对生物群落社会性的模拟 ,因此其相关数学分析还比较薄弱 ,这就导致了现有研究还存在很多问题 。如 :智能算法的数学理论基础相对薄弱 ,缺乏具备普遍意义的理论性分析 ,算

17、法中涉及的各种参数设置 一直没有确切的理论依据 ,通常都是按照经验型方法确定 ,对具体问题 和 应用 环境 的 依赖 性比 较 大 。因此 ,智能排课算法的研究与应用将一直是非常有实际意义的研究课题 ,并朝着以下三个方向发展 。1 )各 种 改 进 智 能 算 法 被 应 用 到 排 课 系 统 中 。例如 ,文献 13 分别将自适应 、混合和并行遗传算法应用到排课系统中 ,并取得了较好的效果 。随 着对智能算法研究的深入 ,各种改进算法层出不穷 , 为解决排课问题提供了新的方法 。2 )各种智能算法结合起 来 使用 。虽然 可用 于解决排课问题的智能算法很多 ,由于各种智能算法 都有自己的优

18、缺点和适用范围 ,而且多年的研究表 明还没有一种算法具有绝对优势 。因此 ,有必要把 多种算法融合在一起成为一种较为有效的办法 ,这 样可以利用不同算法的优势 ,尽可能地弥补各算法 的缺陷 。例如 , 文献 4 把免疫算法和遗传算法结 合起来 ,应用到排课系统中 ,实验结果显示该方法优 于遗传算法 。文献 5 把遗传算法与局部搜索方法 禁忌算法有机结合起来 ,避免了排课中课表的两极 分化现象 ,该方法可以取得较好的排课结果 。3 )各种智能算法与启发式算法结合起来使用 。早期的排课算法广泛地使用各种启发式算法 ,例如动态规划法 、贪婪法等 ,由于这些算法的效率低 ,但 是实现简单 ,而各种智能

19、排课算法相对复杂 ,初始值对算法影响较大 。因此 ,可以把智能算法与启发式算法结合起来使用 ,并分为两个阶段解决排课问题 。第一阶段 ,利用启发式算法得到满足排课约束条件的一个解 ; 第二阶段 , 把 该 解作 为智 能 算法 的初 始 解 ,然后用智能算法优化 ,得到满足排课约束条件的 最优解 。例如文献 6 7 利用启发算 法和 模拟 退 3 A b ram son D , A be la J. A p a ra lle l gene tic a lgo rithm fo r so lving the schoo l tim e tab ling p rob lem C / /15 th

20、A u stra lian Comp u te r Sc ience Confe rence. Hoba rt, 1992: 1 - 11.韦玉 ,冯速. 免疫遗传算法在排课问题中的应用 J . 北京师范大学学报 : 自然科学版 , 2008 , 44 ( 2 ) : 168 - 173.陈守家 ,等. 基于遗传禁忌算法结合解决排课问题 J . 计算机 应用 , 2007 , 27 ( 7 ) : 1087 - 1088.罗军. 基于动态规划和模拟退火算法的排课系统 J . 计算机 与现代化 , 2007 ( 5 ) : 42 - 43.李增智 ,等. 课程表问题的一种混合型模拟退火算法 J

21、. 西安 交通大学学报 , 2003 , 37 ( 4 ) : 344 - 346.责任编辑 :钟 声4 结语本文介绍了排课算法的原理 ,阐述了遗传算法 、 蚁群算法 、模拟退火算法和免疫算法四种智能排课 算法的基本原理和算法特点 ,并对智能排课算法的 发展方向做了展望 。参考文献 : 1 张春梅. 用自适应遗传算法求解大学课表安排问题 J . 内蒙 古大学学报 , 2000 ( 4 ) : 11. 2 W ilke P, Grobne r M. A hyb rid genetic a lgo rithm fo r schoo l tim eta2 b ling C / /A dvance s

22、 in A rtific ia l In te lligence. Sp ringe r L ec tu re No tes in Comp u te r Sc ience, N ew Yo rk: Sp ringe r2V erlag, 2002: 455- 464. 4 5 6 7 A rev iew of in te ll igen t curr icu lum a rran gem en t a lgor ithm sZHAN G J ing1 , L I Guang2jun2 , TAN G Yuan2xiang3( 11L ib ra ry, Yib in Co llege, Yi

23、b in 644007, Ch ina; 21N e two rk M a ragem en t Cen te r, Yib in Co llege, Yib in 644007 , Ch ina;31Comp u te r D ep a rtm en t, Yib in Co llege, Yib in 644007 , Ch ina)A b stra c t: Th is a rtic le in troduce s cu rricu lum a rrangem en t p rob lem , ana lyze s the p rinc ip le s and a lgo rithm f

24、ea tu re s ba sed on gene tic a lgo2rithm , an t co lony a lgo rithm , sim u la ted annea ling a lgo rithm and imm une a lgo rithm and m ake s p ro sp ec ts fo r fu tu re deve lopm en t.Keyword s: cu rricu lum a rrangem en t; gene tic a lgo rithm; an t co lony a lgo rithm; sim u la ted annea ling a

25、lgo rithm; imm une a lgo rithm(上接第 5页 )除了一些专用金刚石车床配有专门的喷雾冷却系统 外 ,大多数高精密机 床都 采 用循 环液 体 冷却 系统 。 有时 ,操作者也可选择人工直接冷却方法 。在上述 冷却方法中 ,以喷雾冷却方式冷却效果最好 。同时 , 也可采用减少碎切屑在前刀面上的停留时间 ,从而 也减少了切屑嵌入划伤表面的几率 ,此法值得推广 。 在采取了上述措施之后 ,就可以基本避免在超精切 削中加工表面的划伤现象 。参考文献 : 1 袁哲俊. 精密和超精密加工技术 M . 北京 :机械工业出版社 ,2007.庞滔. 超精密加工技术 M . 北京 :

26、 国防工业出版社 , 2000.陈日曜. 金属切削原理 M . 北京 : 机械工业出版社 , 2005.B ha rat B hu shan. 摩 擦 学 导 论 M . 北 京 : 机 械 工 业 出 版 社 ,2006.C F Cheung W B . Study of fac to rs affec ting the su rface qua lity in u ltra2p rec ision d iamond tu rn ing J . M a te rials and M anufac tu ring P roce sse s , 2000 , 24 ( 1 ) : 77 - 81

27、.责任编辑 :钟 声 2 3 4 5 The scra tch in g m echan ism for u ltra 2prec is ion m a ch in in g surfa ce an d its con tro lM IAO Zhong1 , GUO Yan2m in2 , ZHOU H ang2xing3( 11M echan ica l Enginee ring In stitu te, Changchun U n ive rsity, Changchun 130022, Ch ina;21No13 O il P roduc tion P lan t, D aq ing P

28、e tro leum A dm in istra tion B u rean, D aq ing 163312 , Ch ina;31D ep a rtm en t of A via tion Theo ry, A ir Fo rce A via tion U n ive rsity, Changchun 130022, Ch ina)A b stra c t: Th is p ap e r system a tica lly ana lyze s sc ra tch ing m echan ism fo r u ltra2p rec ision m ach in ing su rface, and the p roce ss inc lude s fou r stage s such a s fric tion, in laying, sc ra tch ing and ab sc ission. It p u ts fo rwa rd som e con tro l m e thod s to avo id su rface sc ra tch ing th rough ana lyzing va riou s fac to rs.Keyword s: sup e r2p rec ision; sc ra tch ing m echan ism; con tro l