（计算机软件与理论专业论文）基于蚁群算法的排课问题的研究.pdf

中文摘要 摘要 为了保证教学质量，学校必须制定一套规范的教学计划，而课表编排是教学 计划得以顺利执行的重要一环。随着高校学生数量猛埔，数据规模大、各种约束 复杂，在教学资源一定的情况下排课越来越繁难。人丁排课已经雉以完成课表编 排的工作要求。因此，利用计算机解决排课问题成为当务之急。 蚁群算法是近十几年才提出来的种新型模拟进化算法，通过候选解组成的 群体的进化过程来寻求最优解。该过程包括适应阶段和协作阶段。在适应阶段， 各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息 交流以期产生性能更好的解。蚁群算法通过正反馈和负反馈相结合的机制使算法 朝着最优解方向发展，又保持搜索范围避免过早停滞。从而得到一定程度上的满 意解。 本文对基本蚁群算法的思想及原理进行了分析，结合排课问题的自身特点提 出一种适于排课问题的改进的蚁群算法。在此，对排课问题进行了抽象，将解决 排课问题转化为寻求二部图的昂人匹配问题，由于排课问题可以描述为图结构， 这给蚁群算法介入排课问题提供了一个契机。而如何满足排课问题中的多种约束 条件是排课问题的关键问题，在此算法中引入个体启发信息等笫略。考虑把这些 约束具体抽象成一些合适的数宁，适当时候用这些数字来修i f 二部图中边上的权 值，达到间接修改蚁群算法的期望启发因子，配合蚁群寻求课表最优解。 本文不仅存理论_ e = 论述了蚁群算法解决排课问题的方法。而日存此基础上使 用v b 实现了一个基于蚁群算法解决排课问题的实验测试程序。测试结果表明蚁群 算法能够很好地解决排课问题，排出商质量的课表。文中还通过采集实验数据对 文中所述案例的参数选择提出了建议。本文旨在拓宽排谦算法解决方案，同时推 广蚁群算法的应用面。 关键词：排课问题；二部图；蚁群算法 英文摘要 r e s e a r c ho fc o u r s e sa r r a n g e m e n tb a s e do na n tc o l o n y a l g o r i t h m a b s tr a c t i no r d e rt oe n s u r et h eq u a l i t yo ft u i t i o n ，au n i v e r s i t ym u s te s t a b l i s has e to fn o r m a l t e a c h i n gp l a n s ，w h i l ea r r a n g i n gc o u r s e si sa ni m p o r t a n ts t e po fc a r r y i n go u tt h et e a c h i n g p l a ns u c c e s s f u l l y w i t ht h ei n c r e a s i n gq u a n t i t yo fc o l l e g es t u d e n t s ，t h es c a l eo fd a t aa r e h u g e ，a n da l lk i n d so fc o n s t r a i n t sa r ec o m p l e x ，c o u r s e sa r r a n g e m e n tb e c o m e sm o r ea n d m o r ed i f f i c u l ti nt h el i m i t e d t e a c h i n gr e s o u r c e s a r r a n g i n g c o u r s e s b yh a n di s i m p o s s i b l et of i n i s ht h ew o r k t h e r e f o r e ，i t su r g e n tt os o l v et h ec o u r s e sa r r a n g e m e n t w i t hc o m p m e r a n tc o l o n ya l g o r i t h mi san e wk i n do fs i m u l a t e de v o l u t i o na l g o r i t h mw h i c hi sp u t f o r w a r di nn e a rd e c a d ey e a r s i ts e e k st h eo p t i m a la n s w e rf r o mt h ec o l o n ye v o l u t i o n p r o c e s sw h i c hi n c l u d e sa l lp o s s i b l ea n s w e r s t h ep r o c e s si n c l u d e sa d a p t a t i o np e r i o da n d c o l l a b o r a t i o np e r i o d i na d a p t a t i o np e r i o d ，a l la n s w e r sa d j u s tt h es t r u c t u r ei t s e l f a c c o r d i n gt ot h ea c c u m u l a t e di n f o r m a t i o n ；i nc o l l a b o r a t i o np e r i o d ，a l la n s w e r se x c h a n g e t h ei n f o r m a t i o nt og e tt h eb e t t e ro n e s a n tc o l o n ya l g o r i t h md i r e c t st h ea l g o r i t h mt o t h em o s to p t i m a ld i r e c t i o nw i t hc o m b i n a t i o no fp o s i t i v ef e e d b a c ka n dn e g a t i v ef e e d b a c k ， a n dk e e p st h es e a r c h i n gr a n g ef r o ms t o p p i n ge a r l i e r , i nt h i ss i t u a t i o ng e t st h es a t i s f i e d a n s w e ri ns o m ed e g r e e t h i st h e s i sa n a l y z e st h et h o u g h ta n dt h et h e o r yo fb a s i sc o l o n ya l g o r i t h m ，a n dp u t s f o r w a r da ni m p r o v e da n tc o l o n ya l g o r i t h mw h i c hi sa d a p t e dt oc o u r s e sa r r a n g e m e n t a c c o r d i n gt ot h ef e a t u r e si t s e l f t h i st h e s i sa b s t r a c t st h ec o u r s e sa r r a n g e m e n tp r o b l e m ， a n dt r a n s f o r m st h ep r o b l e mt oe x p l o r i n gt h eb i g g e s tm a t c hp r o b l e mo fb i p a r t i t eg r a p h b e c a u s et h ec o u r s e sa r r a n g e m e n tp r o b l e mc a nb ed e s c r i b e di ng r a p hs t r u c t u r ei nt h i s w a ya n tc o l o n ya l g o r i t h mc a ns o l v ee f f i c i e n t l y h o wt os a t i s f yt h ec o n s t r a i n t si st h ek e y o fc o u r s e sa r r a n g e m e n t ，s ot h i st h e s i sb r i n g ss t r a t e g i e ss u c ha si n d i v i d u a le n l i g h t e n m e n t t om i sa l g o r i t h m t h i st h e s i st r i e st oa b s t r a c tt h e s ec o n s t r a i n t si n t os o m es u i t a b l e n u m b e r s ，m o d i 自t h ee d g e sw e i g h t so fb i p a r t i t eg r a p hw i t h t h e s en u m b e r si n a p p r o p r i a t et i m et om o d i f yt h ee x p e c t e de n l i g h t e n m e n tf a c t o ro fa n tc o l o n ya l g o r i t h m i n d i r e c t l y , a n dh e l pt h ea n tc o l o n ya l g o r i t h mf i n dt h eo p t i m a la n s w e ro f c o u r s et a b l e s i n st h e s i sn o to n l yd i s c u s s e st h em e t h o do fs o l v i n gt h ec o u r s e sa r r a n g e m e n tw i t h a n tc o l o n ya l g o r i t h mt h e o r e t i c a l l y , a l s oi m p l e m e n t sat e s ts y s t e mb a s e do na n tc o l o n y a l g o r i t h ms o l v i n gt h ec o u r s e sa r r a n g e m e n ti n v b 7 l h er e s u l t so ft e s ts h o wt h a ta n t c o l o n ya l g o r i t h mc a nd e a lw i t l lc o u r s e sa r r a n g e m e n ta n da r r a n g et h ec u r r i c u l u ms c h e d u l e e f f i c i e n t l y t h i st h e s i sg i v e ss o m ea d v i c ea b o u tc h o i c eo ft h ep a r a m e t e rb yc o l l e c t i n g d a t a t h i st h e s i s sp u r p o s ei st ob r o a d e nt h em e t h o d so fs o l v i n gt h ec o u r s e sa r r a n g e m e n t a n dt op o p u l a r i z et h ea p p l i c a t i o no f a n tc o l o n ya l g o r i t h m k e yw o r d s ：c o u r s e sa r r a n g e m e n tp r o b l e m ：b i p a r t i t eg r a p h ；a n tc o l o n y a l g o r r h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：基王蝗登簋选殴拄逯闷壁曲盟盔：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：起惠船硼年月叩日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密( 请在以上方框内打“”) 论文作者签名：赵癸忱导师签名：微袤一 日期：砷年；月冲日 基于蚁群算法的排课问题的研究 第1 章绪论 1 1 引言 自然界中的许多自适应优化现象不断给人以启示，2 0 世纪5 0 年代中期创立 了仿生学，人们从生物进化中得到启发，提出解决复杂优化问题的新方法：遗传 算法、进化策略等。后来，社会性动物( 蚂蚁、蜜蜂、鸟等) 的自组织行为也引 起了人们的广泛关注，学者们开始对这种群体行为进行数学建模和计算机仿真， 出现了蚁群算法、粒子群优化算法【1 。2 l 、人工鱼群算法 3 1 等优秀的群智能算法。这 些群智能算法也在解决许多优化问题中起到核心作用，而且其应用领域也逐渐扩 大。所有这些仿生优化算法在解决n p c 类问题中显示出巨大的生命力和无限的发 展空f 司t 4 1 。 生物学家通过对蚂蚁的长期观察研究发现，单只蚂蚁的能力非常有限，但当 这些简单的蚂蚁组成蚁群时，却能完成像筑巢、觅食、任务分配、构造墓地等复 杂行为。蚂蚁依靠群体能力发挥出超出个体的智能。其中最引发人们关注的是蚁 群在觅食过程中总能找到一条从蚁穴到食物源的最短路径。就是这种对蚁群觅食 过程的模拟产生了蚁群算法。蚁群算法由意大利学者d o r i g om 等人在2 0 世纪9 0 年代初首先提出来，并用该方法求解旅行商问题( t s p ) 睁】、指派问题( a s s i g n m e n t p r o b l e m ) 6 1 、车间调度i h 题( j s p ) t r l 等，取得了一系列较好的实验结果。受其影响， 蚁群算法逐渐引起了其他研究者的注意，并用该方法来解决一些实际问题【5 1 。蚁 群算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法相结合等优 点。目前对蚁群算法的研究已经由单一的t s p 问题渗透到多个应用领域，由解决 一维静态优化问题发展到解决多维动态优化问题【幡m ，由离散域范围内的研究逐 渐拓展到连续域1 8 】范围内的研究0 9 】。虽然对此方法的研究刚刚起步，但是这些初 步的研究己经显示出蚁群算法在求解复杂优化问题方面的一些优越性，证明它是 一种很有发展前景的方法。 排课问题是典型的涉及多种因素的多目标组合优化问题，既要考虑学生学习 效果，也要照顾教师合理的工作安排，还要充分利用教学设备。对高校教务处来 说排课表是一项十分重要而且非常繁杂的工作。由于现在各个学校课程的量太大， 第1 章绪论 手工排课不可避免地会出现各类冲突，其缺点越来越突出。随着计算机科学技术 的发展，如果能够使用计算机进行排课将解决手工排课的缺点。它是在传统排课 经验的基础上，利用计算机模拟人脑，探讨编排课表的思维规律和抉择方案方法 的计算机方法。自动排课具有排课时间短、质量高，节省人力等优点。 本文对基本蚁群算法的思想及原理进行了分析，并结合排课问题的自身特点 提出一种适于排课问题的改进的蚁群算法。本文主要研究内容就是如何将蚁群算 法应用于排课问题中，优化排课算法、拓宽排课算法解决方案，同时推广蚁群算 法的应用面。 1 2 研究的目的和意义 排课是高校教学管理中一项十分重要而且非常繁杂的常务性工作，其实质是 为使学校在现有教学资源情况下，对教师、学生、课程在时间和空间上进行合理 安排，以使教学工作能够有计划、有秩序地进行。近年来，随着高校新生扩招力 度加大，各高校都面l 晒着教室资源和教师资源紧张的问题。由于数据规模大、各 种约束复杂以及教学在执行过程中的动态性，使得排课问题成为令人困扰的难题 之一。人工排课已经难以完成高校课表编排的工作要求。所以，利用计算机排课 受到人们越来越广泛的关注，并且成为迫切需要解决的实际问题。 排课问题早在7 0 年代就证明是一个n p 完全问题，即排课算法的计算时间是 呈指数增长的，这一论断确立了排课问题的理论深度。对于n p 完全问题目前还没 有一个通用的算法能够很好地解决，然而很多n p 完全问题又具有很重要的实际意 义【2 0 】。例如，t s p 问题就是很典型的n p 完全问题。t s p 具有广泛的代表意义和应 用前景，许多现实问题均可抽象成t s p 来求解。目前对n p 完全问题研究的主要 想法是如何降低其计算复杂度，即利用一种近似算法使求解的时间从指数增长化 简到多项式增长。也就是要为所需解决的问题建立一个合适的模型，利用该模型 能够大大降低算法的复杂度，便于程序实现。 ： 1 3 排课问题的研究现状 计算机排课问题是一个多目标、有限资源、带有约束条件的组合规划问题。排 课系统已经成为国内外众多高校及软件公司的研究课题，取得了许多方面的理论 基于蚁群算法的排课问题的研究 成果和实现方法。国外从二十世纪5 0 年代末就对课表问题开展了研究。1 9 6 3 年 o o t l i e b 在他的文章中就对课表问题做了形式化的描述【2 1 1 ，提出了排课问题的数学 模型。1 9 7 6 年s e v e n 和c o o p e r 等人证明了排课问题是n p 完全问题 2 2 之3 】。这一论 证确立了排课问题的学术地位，把排课问题的复杂性提高到理论的高度。 自从1 9 6 3 年g o t l i e b 提出数学模型后，人们对排课问题展开了探索，但由于排 课问题是n p 完全问题，易受实际问题边界的影响，大多数求解都不理想。进入九 十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度v a s t a p u r 大学管理学院的a r a b i n d a t r i p a t h y 、加拿大m o n t r e a l 大学的j e a na u b i n 和j a c q u e s f e r l a n d 等【2 4 】。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈 增大。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的， 而利用运筹学中分层规划的思想将问题分解，将是一个有希望获得成功的办法。 国外的排课软件大多没有考虑教室这一约束条件，不适合我国教室资源紧张的 实际情况，国内很多高校都参与到此项研究工作。在国内，对课表问题的研究开 始于8 0 年代初期，具有代表性的有：南京工学院的u t s s ( au n i v e r s i t y t i m e t a b l e s c h e d u l i n gs y s t e m ) 系统、清华大学的t s e r ( t i m e t a b l e s c h e d u l e r ) 系统、 大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工 排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些课表编排 系统往往比较依赖于各个学校的教学体制，不宣进行大量推广1 2 0 。 目前，解决排课问题的方法有：遗传算法【2 ”7 1 、专家系统1 2 8 - 2 9 、二分图及着色 理论1 3 ”、模拟退火算法【3 2 - 3 3 1 、回溯法3 5 1 等。从实际使用的情况来看，现已开 发的排课软件不具有普遍的实用性。一方面是因为排课系统实在是一个很复杂的 系统，要想解决所有约束、面面俱到是一件相当困难的事；另一方面因为每一类 学校甚至每个学校都有其特殊性，排课软件很难普遍使用。所以目前的做法还是 要对于不同类型的学校开发不同的排课软件，对于不合适的排法再个别采取手工 调整的办法。 1 4 本文研究内容 本文旨在在基本蚁群算法原理的基础上提出一种适用于排课问题的优化解决 方案。通过研究基本蚁群算法的优势与不足，为排课问题建立相应的模型，并提 第1 章绪论 出一种改进的蚁群算法，将其应用于解决排课问题中。另外，通过一个实验测试 程序，从实验角度论证算法的可行性，测试蚁群算法在解决排课问题时的性能。 同时，由于参数对蚁群算法的性能有很大影响，故文中还将通过采集实验数据对 特定案例的参数选择进行分析。最终达到既为排课算法的解决提供一种新的思路， 又为蚁群算法提出一个新的应用的目的。 基于蚁群算法的排课问题的研究 第2 章排课问题分析 2 1 排课问题概述 排课是将教师、学生和相应的课程在时间和空问上根据不同的约束条件进行合 理的安排，避免冲突，以使教学工作顺利进行。对教师、班级、课程、时间、教 室等几部分资源进行最优化配置，符合教学规律，才能保证充分发挥各个资源的 优势，提高教学质量。 随着高校教学规模的扩大，排课涉及的因素越来越多，问题越来越复杂，使得 手工操作逐渐无法胜任排课工作，总的来说人工排课存在如下困难： ( 1 ) 数据量大，耗费较多时间和人力且极易出错； ( 2 )涉及问题多，要做到考虑全面、没有任何冲突很困难； ( 3 ) 细小数据的调整会牵涉很广，增加很多工作量； ( 4 )最终课表手工录入工作量大( 此属重复工作) 。 为了提高教务管理工作效率，改善教学管理质量，合理高效地利用有限资源， 使课表编排更合理、科学、快速，自动排课系统的设计被人们所广泛关注。 为了编排出令各方面都满意的课程表，在课程编排过程中应遵循一定的规则， 尽量满足各种约束条件。排课中所涉及的有两种约束：硬约束( 排课过程中必须 满足的约束) 和软约束( 排课过程中尽量给予满足的约束，不满足也不会出现冲 突) 。硬约束可以用来衡量排课可行与否，在硬约束的基础上的软约束可以用来衡 量排课优劣。下面列出了部分排课问题所涉及的约束条件，( 1 ) ( 6 ) 为硬约束， ( 7 ) ( 1 4 ) 为软约束： ( 1 ) 一个班级在同一时间只能安排一门课； ( 2 ) 一个老师在同一时间只能安排一门课； ( 3 ) 一个教室在同一时间只能安排一门课； ( 4 ) 教室容量必须满足上课学生人数； ( 5 ) 教室总数要大于同一时间安排的课程总数； ( 6 ) 课程要安排在它所需要类型的教室中( 如：多媒体教室、机房、物理实 验室等) ； 第2 章排课问题分析 ( 7 ) 教师和学生在上午1 2 节课和3 - 4 节课、或下午5 - 6 节课和7 8 节课的教 室距离不能太远； ( 8 ) 同一个班级上的同一门课程在一周之内应间隔排列； ( 9 ) 繁难课程应尽量排在精力充沛的上午1 2 节； ( 1 0 ) 体育课应该排在下午或者上午3 - 4 节，体育课后面避免安排讲授课； ( 1 1 ) 实验、操作课应排在下午： ( 1 2 ) 教师一天的活动尽量安排在一个校区； ( 1 3 ) 尽可能满足个别教师的特殊上课时间要求； ( 1 4 ) 各个班级每天的课时总量尽量按天均匀分布。 排课问题实质上是一个多目标的组合规划问题，而要对课表在多资源上实现 最优的配置实际上是不可能的。因此，我们放弃了寻求“绝对最优”的企图，无 任何硬性冲突的课表，是我们的基本要求，在此基础上课表能够满足尽量多的软 性冲突，我们就认为这个课表是可行并且较优的。 2 2 排课问题的数学描述 2 2 1 排课问题中的因素 在排课问题中，我们的主要任务是将课程、教师、班级安排在一周内相应的时 间和教室内且不发生冲突。可见，在排课问题中存在五个因素。设 ( 1 ) 课程集合：l = l i ，l 2 ，l3 ，l m ) ( 2 ) 教师集合：t = t l ，t 2 ，t 3 ，t ，1 ) ( 3 ) 班级集合：c = c l ，c 2 ，c3 ，c 。 ( 4 ) 时间集合：p = p 1 ，p 2 ，p 3 ，p ) p i 表示可排课的第i 个时间段，如p l 表示周一1 2 节、p l l 表示周三5 6 节 ( 5 )教室集合：r f r l ，r 2 ，r 3 ，r 。 五个元素的笛卡尔积l c t p r 就构成了排课问题的解空间，而排课 也就是在这个解空间中找到一个满足各种约束的解【3 6 】。教学规模太大，这个解空 间的规模也就可想而知了。总校在排课之前，各院系要先从教学计划中把院系内 基于蚁群算法的排课问题的研究 各个年级专业下学期开设的课程筛选出来，安排教师签写教学任务书，整理完毕 后交与总校教务处。换句话说， 的关系在总校排课之前就已 经明确，这些数据及其之间的关系是来源于各院系教务科的。易见， 之间的关系绝不是l x c x t 的满映射关系；又因为每个教学时间段、每 个教室都可以安排课程，所以 可以看成是p x r 的满映射。 则排课问题可以表示为映射：f - l - - p r 。即为每门课寻找一个合适的时 间和教室。其中l 是课程实体，它与教师实体和班级实体有关，即每门课程有其 对应的任课教师和学习班级( 周两次以上的课看成是不同的课程) ：p x r 表示时 间和教室的笛卡尔积： p xr 2 ( p 1 皿1 ) ，( p l ，r 2 ) ，0 , 1 ，r 0 ，0 , 2 ，r i ) ，o 、，r g , ，a p 2 ，r o ，( p p r l ) ，以p r 2 ) ，p 可知f ( l 。) = ( p x ，r y ) p x r ，且p x p ，r y er 2 2 2 排课问题的数学描述 根据2 2 1 节中的元素定义，排课问题目标函数为：满足各种约束的前提下， 获得 m i n c o s t p ( 2 1 ) l 田 其中，q 表示l x c t 笛卡尔积中相关联的课程的集合；，p x r ；c o s t o 表 示给i 课程分配j 对需要付出的代价。 2 2 3 排课问题中约束的描述 我们已经清楚排课实质上是将教师、学生和相应的课程在时间和空间上根据 不同的约束条件进行合理的安排。2 2 1 节中对排课问题中涉及的五大因素采用集 合形式表示，并据此对排课结果的解空间和课程与 对的匹配问题都 予以介绍。在此基础上，我们可以清晰的将2 1 节所提及的几个硬性约束描述如下： ( 1 ) 一个班级在同一时间只能安排一门课。设c “表示l i 这门课的班级主体 设坟l m ) = ( p 。，r y m ) ，f ( l n ) = o ，r 蜘) ，且m a n ， 则当c l m = c l a 时，必有p 。p x a ( 2 ) 一个老师在同一时间只能安排一门课。设t l i 表示l i 这门课的任课教师 设f ( l 。) = 。，r y m ) ，f 【k ) = 口。，r y 。) ，且m a n ， 第2 章排课问题分析 则当1 0 = t in 时，必有p 。p 。 ( 3 ) 一个教室在同一时间只能安排一门课。 设f ( l 。) = ( p 。，r 娜) ，f 【l m ) = ( p 。，r ) ，且m ；e n ， 则当r 。= r 。时，必有p 。p 柚 ( 4 )教室容量必须满足上课学生人数。 设c a p a c i t y 是教室主体的一个属性，r 1 c a p a c i t y 表示r i 教室所能容纳 的学生数， c o u n t 是班级主体的一个属性，c l i c o u n t 表示l i 这门课对 应班级的学生人数。 如果f ( l m ) = ( p x m ，r 珊) ，则c h l l c o u n t 一 r y m c a p a c i t y ( 5 ) 教室总数要大于同一时间安排的课程总数。 设坟l 。t o = ( p i n t 。】，i t y l l l 【。】) ，且p 。【j 1 - p m 【2 】= p 一【n 】，同时 设c o u n t ( r ) 表示全校可用教室数，则c o u n t ( r ) n ( 6 ) 课程要安排在它所需要类型的教室中。 设c l a s s r o o m _ t y p e 是课程主体的一个属性，l 1 c l a s s r o o m _ t y p e 表示l i 课程所需的教室类型； t y p e 是教室主体的一个属性，r ，t y p e 表示教室r 的教室类型 则若f 【l m ) = ( p m ，r ) 必有l m c l a s s r o o m _ t y p e = r y m t y p e 满足这六个约束条件的映射f 就是排课问题的可行解。上述只对6 种硬性约 束进行了描述，还没有考虑到软性约束的问题。这些约束的解决只能得到满足基 本约束条件的排课问题的可行解，并不一定能得到排课问题的最优解或次优解。 当然，对于排课问题来讲，我们没必要非得得到面面俱到的排课最优结果， 如果真的这样固执，排课问题将可能出现无解的情况，只要最终课表排得实 用、合理、不存在无法忍受的约束即可。 - 8 - 基于蚁群算法的排课问题的研究 3 1 蚁群算法原理 第3 章基本蚁群算法 3 1 1 蚁群算法的生物原型 蚁群算法是近些年才提出来的一种仿生优化算法，是受自然界中真实蚁群觅 食行为的启发而产生的。自然界中蚁群能通过相互协作找到从蚁穴到食物的最短 路径，并且能随环境变化( 如突然出现障碍物) 而变化，很快地重新找到最短路 径。根据仿生学家长期研究发现：蚂蚁在寻找食物的行进过程中会沿途留下一种 叫信息素的挥发性物质，其他蚂蚁能根据这种物质浓度的大小选择路径前进，并 且沿途又留下这种信息素，使这条路径上的信息素浓度加强，于是又吸引更多的 蚂蚁沿此路前进。在一段时间后，较短路径上信息素由于挥发的少，同时访问的 蚂蚁多，使其浓度远远超过较长路径上的信息素，此过程持续进行直到所有蚂蚁 都选择最短路径。 假定障碍物周围有两条路a b - c 和a d - c 从蚁穴到达食物源( 如图3 1 ) d 图3 1 蚂蚁觅食模拟 f i g 3 1s i m u l a t i o no f a n t ss e e k i n gf o o d 由图可见，既然蚂蚁可以从蚁穴由a b c 或a d c 路径到达食物源，那么蚂蚁 同样也可以从食物源由c b a 或c d a 两条路径中的任意一条回到蚁穴处。从图3 1 明显可见a b c 路径比a d c 路径短。开始时，当蚂蚁从蚁穴出发到达a 点时，因 为路径上没有任何信息素，蚂蚁只好随机选择路径，从概率论角度看，一半蚂蚁 第3 章基本蚁群算法 走a b c ，另一半蚂蚁走a d c 路径去往食物源。显然，经由a b c 的蚂蚁将先到达 食物源，取完食物即可返回。因为c b a 路径比c d a 路径短，所以蚂蚁们由食物 源返回蚁穴的过程中同样是经过c b a 路径的蚂蚁会先期到达。可见，在同样时间 内、等概率情况下，蚂蚁们在a b c 路径上释放的信息素比在a d c 路径上释放的 信息素要多，其浓度增长得也快。因为蚂蚁是根据路径上的信息素的浓度高低选 择来路径，信息素浓度越高，路径被选择的概率就越大。信息素的多少为后来的 蚂蚁选择路径提供了依据。这样经由a b c 路径上的蚂蚁越来越多，信息素也越来 越多，后来的蚂蚁选择的可能性也越来越大。很快，几乎所有的蚂蚁都会选择a b c 和c b a 路径在蚁穴和食物源之间移动了。这样就找到由蚁穴到食物源的最短路径。 因此，在整个寻径的过程中，虽然单个蚂蚁的选择能力有限，但信息素使整 个蚁群具有很高的自组织性，蚂蚁之间交换着路径信息，相互协作，最终通过蚁 群的集体行为找出蚁穴到食物源的最短路径。 3 1 2 蚁群算法模型 从蚁群算法灵感产生的源头一蚂蚁觅食行为可知，蚁群算法模型的建 立及蚁群算法的实现必须从以下几个方面进行抽象： 1 蚂蚁个体的抽象 蚁群算法是对真实蚂蚁觅食行为的一种计算机模拟，是一种机理上的行为。 因此蚁群算法中的“蚂蚁”是对真实蚂蚁的抽象，而不可能也没必要对真实蚂蚁 个体完全再现 3 7 1 。抽象出来的蚂蚁被称为人工蚂蚁。人工蚂蚁可以看作是一个简 单的智能体，能够完成所求问题简单解的构造过程，可以通过一种手段与其他智 能体进行对话。 人工蚂蚁和真实蚂蚁存在如下共同点【1 9 】； ( 1 ) 都存在一个群体中个体相互交流通信的机制：信息素 ( 2 ) 都要完成一个相同的任务：寻找最短路径 ( 3 ) 都是利用当前信息进行路径选择的随机选择策略：概率选择策略 抽象出来的人工蚂蚁不完全等同于真实蚂蚁，它有自己的特性： ( 1 ) 人工蚂蚁存在于一个离散空间。 ( 2 ) 人工蚂蚁有记忆能力。 基于蚁群算法的排课问题的研究 ( 3 ) 人工蚂蚁具有相应的启发信息。 人工蚂蚁正是因为有了这些特性才使蚁群算法具有更高的智能，使算法更高 效。 2 问题空间的描述 自然界中的真实蚂蚁虽然存在于一个三维环境中，但我们完全可以把蚂蚁的觅 食路线抽象地看成在一个平面或曲面上。换句话说，可以把这种三维环境看成是 一种特殊的二维平面。另外，要想在计算机上使用蚁群算法，抽象出来的人工蚂 蚁必须在离散的二维平面上运动。而真实蚂蚁是在连续的路径上觅食的，所以蚁 群算法必须把这种连续性抽象成离散性这种抽象也是无可厚非的。到此，一 个很熟悉的数据结构就出现在我们面前图。如果实际问题能够用图来描述， 就可以考虑是否可以使用蚁群算法来解决。 3 寻找路径的抽象 人工蚂蚁是在离散在二维平面上的各个节点之间移动的，那么从当前节点通过 哪个路径到达下一个节点呢? 又该如何选择? 这里，可以将路径上的信息素大小 抽象成图边上的权值。在每一个节点，人工蚂蚁根据路径上的权值的大小来选择 下一节点。也就通过此方法从初始节点最终走到目标节点，得到问题的一个可行 解。 4 信息素挥发的抽象 自然界中蚂蚁总是在路径上连续留下信息素，这种信息素会随着时间的逝去逐 渐挥发。由于计算机处理离散事件，在此可以考虑对人工蚂蚁的信息素( 即边的 权值) 进行离散时间的挥发，即适时有规律地减小图中所有边上的权值( 即信息 素) 。 5 启发信息的引入 以上的抽象只是对真实蚁群觅食行为的一个计算机式再现，体现了蚁群觅食行 为极高的自组织性。但是这种自组织性需要耗费相当长的时间，往往这种耗时是 不能被容忍的，我们必须提高时间的利用率。根据问题空间的具体特征，给蚁群 算法一个引导。在决定蚂蚁行走方向的概率策略内引入启发信息，即赋予所有蚂 蚁一种对路径长短的先验知识。 第3 章基本蚁群算法 3 1 3 蚁群算法的系统特征 1 蚁群算法是一个系统 ( 1 ) 多元性：蚂蚁个体的行为是系统的元素。 ( 2 ) 相关性：蚁群行为的相互影响。 ( 3 ) 整体性：蚁群可以完成个体完成不了的任务。 2 蚁群算法具有分布特性 人工蚂蚁在问题空间的不同节点同时开始相互独立地构造解，整个问题的求 解不会因为某只蚂蚁无法成功获得解而受到影响。 3 蚁群算法具有自组织性 如前所说，蚂蚁个体之间相互协作，共同完成寻找最优解的任务。在算法初 期，单只蚂蚁盲目地构造，经过一段时间的适应阶段，人工蚂蚁通过相互的交流 协作，越来越趋向于寻找接近最优解，体现了算法从无序到有序的自组织过程。 4 蚁群算法的反馈方式 ( 1 ) 正反馈：算法刚开始时，图中各边上的信息素量相同，而在蚁群的适应 阶段将在较优解的路径上留下更多的信息索，更多的信息素又吸引了更 多的蚂蚁进入蚂蚁之间的协同工作，引导整个系统向最优解方向进化。 ( 2 ) 负反馈：负反馈是对正反馈的一种平衡，有助于蚁群求解趋于稳定。蚁 群算法通过使用概率搜索技术增加了解的随机性。使得解的搜索范围在 一段时间内保持足够大。避免算法过早收敛“9 1 。 所以，蚁群算法就是通过正反馈和负反馈相结合的机制一方面使算法朝着最 优解方向发展，另一方面又要保持一定的搜索范围以避免算法过早收敛于不好的 解，从而得到一定程度上的满意解。 3 1 4 蚁群算法的应用 前文已经介绍过，自从d o f i g om 将蚁群算法提出来以后，许多研究人员做了 大量的研究工作，并使蚁群算法的应用领域不断拓宽。 蚁群算法首先解决了t s p 问题，这为解决组合优化问题提供了新的思路，很 快被应用到网络路由优化【3 8 捌、二次指派1 4 0 l 、机器人路径规划1 4 1 l 等组合优化问题 中。而且蚁群算法己成为解决实际二次规划问题的重要算法之一。蚁群算法也被 基于蚁群算法的排课问题的研究 应用于武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自 动分配等应用优化问题。还有学者提出蚁群算法在图着色问题中的应用，并取得 了可与其他启发式算法相比的效果。国内学者将蚁群算法成功地应用在配电网规 划、物流配送、生产调度等领域中。 对蚁群算法理论的应用研究证明，虽然相对于各种比较成熟的智能方法来说蚁 群算法的研究还处于初级阶段，但它代表了以后计算机研究发展的一个重要方向 【4 】。 3 2 基本蚁群算法分析 3 2 1 基本蚁群算法的数学模型 设有m 只蚂蚁，n 表示问题规模( 即图中的节点数) ，b i ( t ) 表示t 时刻位于 节点的蚂蚁数目，则m = 6 ( r ) ，t i ；( t ) 为t 时刻路径( i ，j ) 上的信息量。在 i = 1 初始时刻各条路径上信息量相等，并设 r 0 ( o ) = c ( c 为常数) 。用禁忌表t a b u k ( k = 1 ，2 ，m ) 来记录蚂蚁k 当前所走过的城市，禁忌表的内容随蚂蚁的运 行状态要随时作动态调整。在寻优过程中，蚂蚁从当前节点转移到哪个节点是根 据各条边上的信息量和启发信g ( 一般是与边长有关的函数) 来计算状态转移概 率确定的。若z ( f ) 表示在t 时刻蚂蚁k 由i 节点转移到j 节点的概率，则基本蚁群 算法的状态转移概率公式为： 露( ，) = 毒拦警芒可萄“d 。 1 甄而1 石歹捌刨“删阳( 3 1 ) 0 ，否则 其中，a l l o w e d k = 0 ，1 ，n - 1 - t a b u k ( k = 1 ，2 ，m ) 表示蚂蚁k 下一 步允许选择的节点，人t 蚂蚁具有记忆能力就体现在这里：t a b u l k 记录蚂蚁k 当前 走过的所有节点，t a b u k 集合里面的元素随着算法的演化过程作动态调整。啦是启 发函数，表示边( i ，j ) 的能见度，一般取2 万1 ，d l j 表示i 节点和j 节点之间的 距离。a 是表示边上信息素残留量的重要程度的参数，b 是表示能见度重要程度的 第3 章基本蚁群算法 参数。为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一 步或者完成对所有n 个节点的遍历后，各路径上的信息量要根据以下公式作调整： ( ，+ ，o = ( 1 一力勺( f ) + f p ( 3 2 ) 乃= ( 3 3 ) k = l 式中，p 表示信息素挥发系数，则1 - p 表示信息素残留因子，a r u 表示本次循 环中( i j ) 路径上的信息素增量，r ：表示第k 只蚂蚁在本次循环中残留在路径( i j ) 上的信息量。 有3 种不同版本的基本蚁群算法模型：a n t - d e n s i t y 、a n t - q u a n t i t y 和a n t - c y c l e 。 其差别在于f ：的求法不同。 ( 1 ) 在a m 栅i t y 模型牡：= 需炽暾租釉+ 1 加鲋o 。 ( 2 ) 在胁q 啪t i t y 模型中c ：垮若第k 只蚂蚁榔t + l 之间经过( i j ) t o ，否则 +。+ 。f 譬，若第k 只蚂蚁在本次循环中经过( i ，j ) ( 3 ) 在a n t - c y c l e 模型中f ：= 厶一”7 【o ，否则 a n t - d e n s i t y 和a n t - q u a n t i t y 模型利用的是局部信息，而a n t - c y c l e 模型利用的 是全局信息。在求解t s p 问题时a n t - c y c l e 模型性能较好，所以通常采用这种模型 作为蚁群算法的基本模型。【博3 7 4 “习 基丁二蚁群算法的排课问题的研究 3 2 2 基本蚁群算法描述 为便于理解，下面以n 个城市的t s p 问题为例描述基本蚁群算法的实现流程： 一1 5 第3 章基本蚁群算法 3 2 3 基本蚁群算法的复杂度分析 以求解t s p 的基本蚁群算法为例，来分析基本蚁群算法的复杂度。如前所述， 设问题规模为n 。 1 时间复杂度 按如下所示分析： 参数初始化( 迭代次数变量n c 2 0 ；时间t 2 0 ；设置最大迭代次数n c m “；设为常数 a r n ( o ) = 0 ) o ( n 2 ) w h i l e ( 未达到最大迭代次数) o c 嘣) n 刮斗- 一o ( 1 ) 清空禁忌表o ( m n 每个蚂蚁一个列表，每个列表长度为n 将m 只蚂蚁置位o ( m ) 把m 只蚂蚁的初始节点放入禁忌表o ( m ) f o r0 = 2t on ) ，每只蚂蚁寻找自己的回路o ( n ) t + 卜o ( 1 )