当前位置:首页>软件介绍>基于蚁群算法的排课系统研究与设计内容 查询:
     
基于蚁群算法的排课系统研究与设计内容

            本文先分析了课程表编排问题中的各种原则和要求,接着说明了课表问题是一个组合优化问题,并给出了课表问题是一个完全NP问题的说明。为了能够有效地解决课表问题,我们采用了现在较为流行的群体智能算法一一蚁群算法。它是通过模拟蚁群在觅食过程中寻找最短路径的方法来求解优化问题,目前在旅行商问题等组合优化问题中有成功的应用。

            蚁群算法目前有As、AcS、MMAs等三种常用的模型,但是在排课问题上这三种蚁群算法都有易于陷入局部最优解的缺陷,从而使得排课问题求解过程停止了。本文根据排课问题自身的要求和特点,提出了基于二分图原理的排课算法;并揉和蚁群算法三个不同模型的优点,提出了一种面向排课问题的改进型蚁群算法。在算法中,对已经搜索到的合理子解,最大限度增强其信息素的增量;对那些有冲突的子解则尽可能扩大其搜索空间,从而加快了问题求解的速度。在算法中给出了排课问题种种冲突的解决方法。实验结果表明改进后的算法可以明显改善排课问题的求解速度,提高解的质量。

            该算法已在、Windows2000操作平台上实现,具体使用的开发方法是c拌可视化程序设计方法。

            第一章绪论

            1.1排课问题的概述

            排课即排课程表是学校教学管理中十分重要,又相当复杂的、不可缺少的管理工作之一,其实质就是为学校所设置的课程安排一组适当的教学时间与空间,从而使整个教学能够有计划有秩序地进行。

            如何使课表的编排更准确、合理、快速、高效就成为教务中的一个难题?计算机的普及,以及计算机具有运算速度快,处理能力强等自身的特点,很自然地进入到这一应用领域中。一方面用计算机进行排课能够快速地得到满足约束条件的可行结果,具有排课时间短、人力省和质量高的优点,不但能使教务人员从复杂的排课任务中解脱出来,而且对于推动教学的发展也起到非常重要的作用!另~方面随着网络的普及,计算机也可以直接在网上发布其排课结果,使得学校的学生和教师可以快速有效地查询到自己的课程安排,实现了局域网内网上办公,节省了手工排课后人工输入的时间,提高了教学管理方面的质量和效率。排课问题本身具有规模较大(学生多,教师多,教室多)、约束条件(如单双周、选修课、多媒体的需求、教室能够容纳的学生数等)比较复杂以及问题本身是完全NP问题等特点,从而使得探讨排课的高效算法以及设计一个能够具有较强实用性的排课系统,成为令人感兴趣的课题之一。

            摊课的主要功能是把各院系等授课部门的课程申请进行汇总,然后根据教学计划或教学环节制定全校各班级的课表。随着我国教育体制改革深入,大学的快速扩招,学生人数的不断上升,学校的班级越来越多、课程门数增加的也比较多,再加上选修课程的开设,使得课程设置不断向深度和广度发展。每门课又涉及很多信息,课程之间差异性很大,如果用手工进行排课,不可避免地出现教室资源冲突或教师资源冲突的情况手工排课的缺点就越来越突出,而且越来越难以实现。

            排课是~个涉及多种因素的组合规划问题,它要保证在课程安排中教师、学生、教室不能产生冲突(所谓冲突,就是将需上不同课程的两个或多个班安排在了同一时间、同一教室、或为同一个教师或同一个班级在同一时间段安排了多门课程等情况),并且要满足教师的要求和教室资源等约束条件。

            1.2自动排课发展历程

            在国内,对课表问题的研究开始于20世纪80年代初期。国内一些高等院校也进行了很多相关算法的开发研制工作。例如,西南交通大学在分析高校课表编排所遵循的基本原则和模糊性原则的基础上,定义了课元之间关于教师的相关关系和关于自然班的相关关系,提出以课元相关运算和课元的候选时空片计算为核心的计算机排课算法;延边大学根据高校课程表的制作特点,设计了计算机自动排课的数据结构与算法”i沈阳电力高等专科学校研制了基于cIie州server的开放式智能排课系统16i山西大学在总结排课工作经验的基础上提出了一种解决问题的形式化描述,在这种想法上实现了基于知识推理的排课系统PJ等等。具有代表性的软件系统有:南京工学院的UTSsfAuniversitvTimetableschedulingsystem)系统,清华大学的TIsER(TimetableScheduIer)系统,大连理工大学的智能教学组织管理与课程调度系统等。这些系统大都是模拟手工排课过程,以“班”为单位,运用启发式函数来进行编排的。但是这些课表编排系统往往依赖于各个学校的教学体制,不宜于进行大量推广。另外,国内也有一些小规模的排课软件,如:排课高手、智能排课系统、明达轻松排课表、丁香智能排课系统、园丁排课系统等等。

            20世纪50年代末,国外就有人开始研究课表编排问题。1962年,Gotlieb曾提出一个课表问题的数学模型…。近40年来,人们对课表问题的计算机解决方法做了许多尝试。其中,课表编排的整数规划模型12l将问题归结为求一组O.1变量的解,但是其计算量非常大。解决0.1线性规划问题的分支.定界技术只适用于规模较小的排课。此外,有些文献试图从图论的角度来求解课表问题,但是图的染色体问题也是N王,完全问题。进入20世纪90年代以后,国外对课表问题的研究仍然十分活跃。比较有代表性的有印度的vastapur大学管理学院的ArabindaTripathyⅢ、加拿大Momreal大学的JeanA.ubin和JacquesFerIand等。

            从实际使用情况来看,国内外研制开发的这些软件系统在实用性上仍然差强人意。一方面问题本身是完全NP问题,算法比较复杂,想得到~个合适的解,都是很困难的事,更不要说得到~个高质量的,最优解了;另一方面由于学校众多,每个类型的学校均有各自的特殊性,自动排课软件很难普遍适用,特别是一旦在调课的过程中产生一个很小的变动,很可能要引起全部排课结果的大调整,这意味着课程的大变动,也是一个规模较小的排课了。从上面两个方面来看,现有软件的适用性很差,因此只能根据不同类型的学校,开发其对应的自动排课系统。

            1.3蚁群算法的生物原銎

            经过观察研究,仿生学家发现,蚂蚁能够在食物和巢穴之间发现最短路径,不是什么可见的线索,而是根据其释放的称为信息素(pheromone)的物质。当蚂蚁在地面上爬行时,就在其爬行的路径上释放信息素。当然,如果有其它蚂蚁也曾经在这个路径上爬行,也会留下其它蚂蚁释放的信息素。图1,显示了自然界中蚂蚁如何在两点之间发现最短路径? 

            图la:蚂蚁到达路口,如何选择前进方向?由于现在只有两条路径,选择上边的路径还是下边的路径?没有任何线索可以暗示哪条路径才是最短的,因此蚂蚁就随机的选择。一些蚂蚁选择上边的路径,~些蚂蚁选择下边的路径。(从概率角度上看,这时候基本是50%对50%的比例)。图1b、图1c:为了方面讨论,假设所有蚂蚁的速度是一样的,虚线表示蚂蚁释放的信息索。则短路径上的蚂蚁先期到达,当L1、R2到达路径分叉口的时候,L2、R1在上边的路径上,这样在下边路径上的短路径上的被释放的信息素多,其浓度增长的也要快一些。由于蚂蚁是根据信息素的浓度的高低选择路径,面路径上的信息素就是线索,也就为以后的蚂蚁选择路径提供了信息。图ld:这样下边的路径上蚂蚁越来越多,信息索也越来越多,蚂蚁选择可能性也就越来越大。很快,所有的蚂蚁都选择下边的路径,这样最短路径就被发现了。

            自然界中,诸如蚂蚁、蜜蜂等群居昆虫,虽然个体昆虫的行为极其简单,但由单个简单的个体所组成的群体却表现出非常复杂有序的集体行为,如在食物和巢穴之间找到最短路径。随着仿生学的发展,这种群体智能引起了科学工作者的注意和兴趣。

            下面图2cI…,是图l的~个试验。图2b,横坐标是时间(分),纵坐标是蚂蚁的个数,上边的线表示通过图2a“下边”路径上的某个时刻蚂蚁个数,下边的路径表示通过图2a“上边”路径上的某个时刻蚂蚁的个数。

            但是真实蚁群除了信息素外不会去学习任何关于路径长短的先验知识,蚂蚁也没有记忆力,这使得蚁群的行为体现出一定的盲目性,缺乏效率。这是蚁群算法需要进行改进的方面。

            “蚁群算法(aIltc010nyalgorithm)”是近年来出现的一种新型的模拟进化算法。它是由意大利学者于20世纪90年代初M Dorigo等人首先提出来的|lIJ,其充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,对丁sP问题进行求解,并取得了很好的结果。随后,蚁群算法被用来求解分配问题、武器.目标分配(weapon-tafgetass培nment)问题、指派问题、频率分配问题㈣、电力系统故障诊断11q等NP完全问题,均获得了较好的结果。近10年来的研究结果已经表明:蚁群算法用于组合优化具有很强的发现较好解的能力,具有分布式计算、易于与其他方法相结合、鲁棒性强等优点,在动态环境下也表现出高度的灵活性和健壮性。1.4本文主要研究内容一个具有高质量的课程表应有助于教学活动的顺利开展,有助于教师教学效果优化,有助于学生学习质量的提高。如果课程安排不合理,如教师或者学生课程相对比较集中,这就无法有效地保障教学的效果,教师和学生疲于奔命。计算机排课,教学的信息可以一目了然,对于优化学生四年的学习过程,评估每位教师对教学的贡献,以及对当前教学的课程建设等都具有重要的意义。

            这只是两个蚂蚁的实验。可以看出,如果有更多的路径提供给蚂蚁选择,根为便表现出一种信息正反馈现象,即某一路径上走过的蚂蚁越多,则后来者选食物的目的。同时这种信息素也会随着时间的推移而自然减弱甚至消失,没有据上述的原理,仍然可以发现最短的路径。这样由大量蚂蚁组成的蚁群集体行择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到集体搜索被选择的路径上的信息素就会越来越弱,最终被彻底淘汰。单个弱小的蚂蚁通过群体就有了令人惊讶的高智能。蚂蚁群体的集体行为实际上构成一种学习信息的正反馈现象,蚂蚁之间通过这种信息交流寻求通向食物的最短路径。蚁群算法正是模拟了这样的优化机制,即通过个体之间的信息交流与相互协作最终找到最优解。

            本文主要研究内容是利用蚁群算法的原理来解决排课问题,以及蚁群算法和其它几种排课算法之间的比较。首先,蚁群算法作为新近出现的一种启发式算法,它具有正反馈、分布式计算和具有建设性的贪婪启发式等特点,在许多领域中已经取得了成功的,对组合优化问题的研究有很高的实用价值。希望我们的研究既可以丰富该算法的应用研究和完善蚁群算法的理论,又可以为求解排基于蚁群算法的排课系统研究和设计课问题的求解增加一种新的途径。

            在第一章中,介绍了排课问题的国内外发展情况,并对此问题作了简要的概述。简单的介绍了蚁群算法的仿生原型,以及蚁群算法的发展历程及应用。

            在第二章中,主要介绍了排课系统中一些冲突,和为了解决这些冲突而提出的相应的要求。排课系统是属于组合规划的范畴,并且说明排课系统是一个NP完全问题。

            在第三章中,主要对排课系统进行功能性和数据性的建模,并以二分图作为理论基础,分析排课算法的二分图的模型。在本章的最后,解释了如何在排课问题中检测和处理各种冲突问题。最后根据蚁群算法中常用的三种模型分别实现了排课系统算法,并用具体实验数据来说明其优缺点,最后根据这三种算法,提出了~种EncAcs算法,较好的实现了排课系统的算法。

            在第四章中,主要以货郎担问题TSP为例介绍了蚁群算法中三种重要的变形:cAS算法,cAcS算法和cMMAs算法。并且介绍了蚁群算法的特性、及其时间复杂度和空间复杂度,最后简要的描述了蚁群算法的在当前的一些应用领域。

            第二章排课问题的基本要求

            2.1课程表编排的原则和要求

            在时间、教师、班级、教室、课程这五维关系中,教师、班级、教室在时间上三者之间存在着紧密的关系,但是同时这也是排课系统中最容易出现冲突的方法,下面几条是关于冲突的说明:

            1)教师冲突问题

            同…教师在同一时间不能安排两门课程。随着现在学校的扩招,教师资源相对紧张,工作任务较重,因此这个问题越来越在排课问题中占据重要的地位。

            2)班级冲突问题同一班级的学生在同一时间不能安排两门或多门课程。

            现在大学普遍开设了大量的公共选修课,因此同一个班级(按注册为单位的自然班)的学生可能选择两门甚至更多的不同课程。但是对同一位学生,不能再同一时间安排两门或多门课程。处理方法可以是设置一些特定的选修课时间,在这个时间内对班级打破自然班级形式,重新组合成新的班级,在这个时间内排课。并且在这个时间内,不再安排其它课程。这样可以对这些非自然班在特定时间内单独进行排课。

            3)教室冲突问题

            教室和前面两个资源的不一样,它不涉及到人的问题。它可以持续性的是使用。但是这个问题相对而言是比较复杂的。主要有三种形式:

            (1)某一课程参加学习的总人数不应大于所安排教室的座位数。实际上,也就是说根据某个课程学习的人数<自然班、合班或者选修的组台班)以及教室能够容纳人数选择一个合适的教室。教室大而学生少则浪费教室资源i教室小而.专.基于蚁群算法的排课系统研究和设计学生多则无法上课。

            (2)同一时间安排的课程总数不能大于所能提供的教室总数。这在总量上对课程安排的规模进行了约束。特别是在大中专院校,~般在总量上课程总数一定要远小于教室总数和周次的乘积,为学生留下足够的地点自习。

            (3)同一教室在同一时间不能安排两门课程。

            这三个冲突在排课系统中是必须避免的,绝对不能发生是排课系统中,这最基本的要求。一旦发生必然会影响教学任务和教学的质量。课程的安排不是任意的、随机的,为了达到最好的教学效果,获得一个高质量的课程表除了要避免上述三个硬性冲突,还有下面一些其它较为重要的软性要求:

            1)课程在一周上多次时,要有一定的间隔性。同~课程连排教学单位时间以上时,相同或相近的教学内容极易引起学生大脑皮层的抑制,从而降低学习效率。课程一般不在连续的两个教学单位时间重复出现。这样教师的教学时间保持了适当的间隔,以便教师有时间备课、辅导和批改作业。学生也有时间复习、消化。

            2)要尽量为所排课程安排上该类课效果最好的时间。时间生物学理论认为,每个人在一天中的精力和注意力如潮汐般起落。人体内部的节律感对课堂学习能力有直接影响。学生在一天里各段时间的学习效果是有差异的。上午是学习的重要时刻,因此在安排教学工作时,应把难度大的课程安排在神经活动的兴奋高潮期;其它实践课一般安排在下午教学时间。具体到编排周课表,应该注意:

            (1)繁难课程应尽量安排在上午第一大节117J。

            (2)实验、操作、训练、演示课应排在下午。

            3)对年老体弱、上课有特殊困难的教师以及有特殊需要的教师,排课时应适当予以照顾考虑。为了减少排课算法的复杂性,对极个别现象,可以作手工处理。

            4)同一个班或同一个教师在连续两个教学单位时间的间隔(比如一个上午的教学时间段)更换教学地点的距离不宜过远。特别是现在大学的教学区较多,如果跨区上课,则必然对于教学单位时间的间隔有一定的时间要求,特别是同一个上午(下午)如果有连续的课程,则会带来交通、教学质量下降等问题。

            2.2排课问题是组合规划问题

            排课问题是一个多目标优化的组合规划问题。下面是对排课问题做~个简单的分析:

            第二章排课问题的基本要求

            设集合Teache产f全体教师1C1assroom=f全部教室class=f所有的班级)Lesson_f所有的课程)Time=f每周上课的次数l则排课问题可以归约为:£P耶。聆七C肠锘mD坍7渤e。即为每门课寻找一个合适的教室和合适的时间。这样描述是不全面的,没有满足上小节的要求。

            设Timel。。。表示1esson这门课的上课时间,其中lesson∈Lesson,Timele咖。∈Time。

            Lessont。ach。,表示teacher这个教师的所有教授的课程,其中teacher∈Teacher,Lessontc卸her量Lesson。Lessollcl船。表示class这个班级所有上的课程,其中class∈Class,Lessorlcl耻《Lesson。CountI。n表示lesson这门课的上课人数,其中lesson∈Lesson。coumd。Ⅷ表示classroom这个教室的座位数,其中classroom∈Classroom。f:LessonjCl∞sroomxnme约束条件:

            满足五个约束条件的C就是排课问题的可行解。直观上来看,其解不是唯一的,应该有多个解。而且上述的模型只是考虑到解决硬冲突问题,还没有解决软的问题。当然,一个高质量的课程表应该是一个多目标优化的。多目标优化是指课表在多个资源上追求最优(这就涉及到软性的要求了)的配置,即教室资源、时间资源、教师资源、班级资源等都要求一个最优的。实际上这是不可能的,在实际中一般是求得一个相对较优的一个可行解就行了。因此,我们放弃了寻求“绝对最优”方案的企图,除了基本的“教室、教师、学生在任一时间的安排只能出现一次”的硬性约束条件外,课表只要能够满足人工排课中的“合理、实用、有特色”的要求,就可以认为是可行的了。在可行解集合中,得到“相对最优”的解则是我们的目标之一。一套完整的课表,包含有所有年级,所有课程,所有班级的信息组合,那么单对一门课程所找到的“相对最优”解,放进全套课表集中并不一定是一个很优的解,它有可能会导致其它的课程安排的困难和失败。

            2.3排课问题是NP一完全类问题

            前文已经提到,从上个世纪六七十年代,国外计算机界对计算机辅助课程表编排作了大量理论上的研究和探索。对此作出突出贡献的是七十年代中期,美国S.Eve等人在SIAMJ.COMPUⅡL杂志上发表题为《关于时间表和杂物流问题的复杂性》一文,首次论证了排课问题是NP一完全类的,将排课问题理论化。目前还没有解决NP一完全类问题的多项式算法它意味着在一个多项式时间内无法找到排课问题的解。而且理论和实践表明,在满足各种要求和限制的前提下,只要课程表编排所涉及的信息稍有变化,就有可能造成课程表编排选择方案的剧烈变动,尽管当前的硬件发展比较迅速,但是由于算法本身没有突破性的进展,寻找合适的解是很困难的。当然根据具体的排课系统这个问题的自身特点,还是有一些较好的方法可以给出问题的一些较高质量的解。

            下面的内容译自这篇论文的第一部分。这里将要讨论的排课问题是学校安排教学过程中的一个数学模型。在论文中,是对时间表这一普遍事物考察的,在本文中,具体讨论课程表的问题。 

            1.NM阶非负整数矩阵R氓U是第i个老师在第j个班级上课的课程数)那么这个问题就可以归结为,是否存在~个交函数珩

            2集合fTl,T2,…,Ti,T。),其中Ti∈TimecIassroom(n是老师数,Ti是第i个老师的有效课时集)

            3集合{C1,c2,…,ci,…,Cm),其中ci∈Timexclassroom(m是班级数,cj是第j个班级的有效课时集)

            4.有限集H.TimeClassroom(一周总课时)

            上述四个公式含义如下:

            1)确保一位老师不在同一课时为两个或者两个以上课程,或者不同的班级上基于蚁群算法的排课系统研究和设计课。

            2)确保仅当老师和班级均有效时,才出现交汇空间。

            3)确保在一周中老师i和班级j之间的交汇课时等于所需课时数。

            4)确保各班级同一时间不多于一位老师。

            这实际上是类似sAT问题。

            sAT问题的描述如下:k个变量x1,X2,讯的m个布尔表达式Al,A2一,A。。如果存在各布尔变量x.(1<i鱼)的赋值,使每个布尔表达式Ai(11i!m)都取值l,则称为布尔表达式是可以满足的。把公式(3)和公式(4)看作是“布尔表达式”,需要满足这些表达式为真,实际上就是求每个Ki的值(由于非负,其值只能是。或者1,否则公式(3)和公式(4),必然不能满足),对NM阶矩阵进行着色问题(两种颜色集:Time、CIassroo。

            这个论证确立了排课问题的学术地位,把人们对排课问题复杂性的认识提高到了理论的高度。实际上,这是~个相当简化的模型,因为它忽略了一些在实际中确实起作用的因素。然而,需要说明的是即使再给它增添约束条件,它仍然是一个NP完全问题。 

            第三章蚁群算法的基本原理

            3.1算法模型的建立

            人们模拟自然界的蚁群是如何觅食的行为,建立了人工蚁群系统。人工蚁群系统从以下几个方面进行模拟和抽象:

            (1)对蚂蚁个体的抽象

            人工蚁群算法是对自然界真实蚂蚁的一种模拟,是~种机理上的应用,因此首先必须对真实的蚂蚁进行一个抽象,而不可能也不必要对蚂蚁的个体进行完全的再现。抽象的目的,就是为了能够更加有效的刻画出真实蚂蚁群体中能够为算法借鉴的原理,抽象的原则则是抛弃和算法无关的因素。

            抽象出的蚂蚁被称为人工蚂蚁,一个人工蚂蚁可以看作是一个简单的agent,能够完成简单的解的构造过程,也能通过一种通信手段相互影响。和真实蚂蚁相比,有以下几点不同: 

            (1)人工蚂蚁“生活”在一个离散时间的环境中,而其实蚂蚁生活在连续时间的环境中。这一点对于解决分步骤的优化问题是十分重要的。在计算机模拟系统中,可以用变量或者对象等实体来实现,其离散的特性,也有利于人工蚂蚁保持自己的特性。

            (2)人工蚂蚁不像真实蚂蚁那样是完全盲目的。人工蚂蚁可以根据一些启发信息来确定自己如何选择。

            (3)人工蚂蚁具有记忆能力,而真实蚂蚁没有记忆能力。人工蚂蚁可以记住曾经走过的路径或访问过的节点,这样可以提高算法效率。

            (4)阀题空间的描述

            自然界蚂蚁的存在于一个三维立体的环境中,而问题空间的求解一般是在一个抽象的平面内进行,所以首先需要将蚂蚁觅食的空间抽象成一个平面。由于蚂蚁寻找食物所走的路径本来就是一条曲线,可以抽象存在于一个二维空间f平面或者曲面)上。真实蚂蚁是在一个连续的二维平面中行走的,而我们无法用计算机来完整的描述一个连续的平面,因为计算机处理的是离散事件。所以我们必须把连续的平面离散化成一组点组成的离散平面,而人工蚂蚁只能在抽象出来的点上行动。这个抽象的过程的可行性在于,尽管蚂蚁是在连续平面行动,但其行动经过的总是一个一个的点,因而抽象过程只是提高了平面点离散分布的粒度,与觅食行为的机理是没有冲突的。

            基于以上的认识,很容易得到蚁群算法可求解的问题空间可以用图来描述。也就是说如果问题的解空间可以用图来描述的,则蚁群算法就有求解的可能性。在工程中有很多问题是可以用图来描述的,这就给蚁群算法提供了广泛的应用前景。

            (3)外激素挥发的抽象

            自然界蚂蚁总是在走过的路径中连续的留下外激素,而这种挥发性的化学物质也是在时间上不断挥发的。由于计算机处理的事件只能是离散事件,所以必须使得人工轨迹的挥发是离散发生的。通常的做法是,让蚂蚁每~个单位时间从一个结点走向下一个结点,而当蚂蚁完成一次移动,也就是一个单位时间后,进行一次轨迹的挥发。和把连续的平面抽象成离散的可以用图描述的问题空间一样,在离散时间点进行轨迹挥发的方式与蚂蚁觅食过程的机理是相符的,而通过这个抽象使得闼题可以用计算机来处理。

            (4)寻找路径过程的抽象

            真实蚂蚁在寻找食物的过程中是按照环境中的激素的量来决定前进的方向的,而人工蚂蚁是在平面图的结点上行走的,因而可以把寻找食物的过程抽象成蚁群算法中解的构造过程。将外激素抽象成存在于图的边上的轨迹(权),在每一个结点,人工蚂蚁感知连接该节点与相邻结点边上的轨迹浓度,根据这个浓度的大小决定走向下一个节点的概率。

            (5)自启发因子的引入

            以上几点是对蚂蚁群体行为的抽象,整个过程体现了蚁群系统的自组织性,其有很多独特的优点,但自组织系统同样存在一个缺陷,那就是系统的演化需要耗费更多的资源一一时间。而作为~种算法的应用,对算法运行时间的要求也是必不可少的。于是在蚁群算法模型建立时引入了~个随机搜索的过程。具体的做法是,在决定蚂蚁行走方向的概率时,引入了自启发因子,即是根据问题空间的具体特征,给算法一个初步的引导,这个过程极大的增加了算法的有效性,给算法的具体应用带来了可能性。

            不难看出,通过以上描述的一些抽象过程,可以简单的建立一个蚁群算法的模型。其问题的空间是用图来描述的,解的获得是具有构造性的,而且在解的构造过程中人工蚂蚁没有接受任何全局的指导信息,因而求解过程是自组织的。在定义了一些规则后,蚁群系统可以用来求解那些用图来描述的问题。人工蚁群系统正是有了这些不同千真实蚁群的特性,才使得该系统具有更高的智能性,在寻优过程中具有更高的效率,适合于解决更多类型的问题

            3.2蚁群算法的几种算法形式

            自从1991年M.Do堍。等人首先提出蚁群算法以来,吸引了许多研究人员对该算法进行研究,并提出了许多相关算法的框架,S(Antsystem)是最早提出的算法,它首先被成功的应用于TsP问题中。虽然和一些发展比较完备的算法。如遗传算法(GA)比起来,基本蚁群算法计算量较大,但是它的成功应用还是激起了人们的研究兴趣。As的优点在于它的正反馈特性和强启发性能,这使得在早期的寻优中就可以迅速找到合适的解决方案。

            随后人们又提出了ACS算法(AntColonysystem)ACS和As的主要区别在于;ACs算法中,除了对信息素浓度进行局部调整外,在所有蚂蚁结束寻优后,根据全局信息进行对信息素浓度再一次调整。

            (1)AS算法

            As算法是所有蚁群算法的原型。它首先应用于求解TSP问题。为了便于理解,下面以求解平面上n个城市的TsP问题为例,来解释As算法。

            基于蚁群算法的排课系统研究和设计

            设所有城市的集合矿表示所有城市的之间的边的集合,而且每个边上的权是J(,s),其中(,J)∈G。这儿边考虑是无向的,因此占。TSP问题就是求经过所有的城市但不重复,且权和最小的环路。    

            其中:n“为先验知识,在TSP问题中为城市i转移到城市j的启发信息,一般取叩口2寺’。为在路径q上残留信息的重要程度;B为启发信息的重要i

            程度;与实际蚁群不同,人工蚁群系统具有记忆功能,用以记录蚂蚁k当前所走过的城市,称为禁忌表(下一步不允许选择的城市)。集合tabuk随着进化过程作动态调整。

            经过n个时刻,所有蚂蚁都完成了一次周游。它们本次周游的禁忌表将满,此时应清空,将当前蚂蚁所在城市置入tab,准备下一次周游。这时,计算每一只蚂蚁所走过的路径Lk,并保存最短路径。

            蚂蚁完成~次循环以后,各路径上的信息量要根据式

            (2)作调整。

            而且随着时间的推移,以前留下的信息素逐渐减弱,用参数p表示信息消逝程度,环中所走过的路径的长度。∽其中,△彳:表示第k只蚂蚁在本次循环中留在路径D上的信息量,△死表示本次循环中路径日上的信息量的增量,Q为常数,Lk表示第k只蚂蚁在本次尽管对于30城市以下的小规模的TSP问题,AS算法可以获得一个很好的解,但是对于大规模的TsP问题,算法需要的时间是很长的。为了提高AS算法的性能,可以从三个方面进行改进,这就直接导致了ACs算法诞生。

            (2)ACS算法

            ACs算法(图4)和As算法主要有三个方面的区别:

            (1)转移函数不同,提供新的转移策略,希望能够在新边的探索和原有边的启发信息中寻找一个平衡点。(j订全局修改信息素不同,不是全部修改,而是精英策略,只修改在最短路径上信息素; 

            如果随机数q小于初始值q。,则根据启发信息选择最大的一个;如果大于,则根据公式(4),根据概率的大小来选择下一个城市。这样既保证了搜索的收敛性性能好,又增强了搜索策略的多样性,以避免过早地陷于搜索停滞。

            (2)信息素全局更额策略

            当所有蚂蚁走完全部城市以后,采用精英策略,只有经过那些最佳路径的边上蚂蚁才被允许释放信息素,按公式(5)进行更新。那些不是最佳路径上的路径则降低信息素浓度。

            这种策略的目的就是为了增强那些属于最佳路径上的边的信息素,可以大大增加这些边上的信息素。h表示当前第k次迭代的最佳路径,这样方法称为迭代最佳更新策略,如果当前全局最佳的L来替换k,则称为全局最佳更新策略,当然其修改的边也就是属于全局最佳的边了。根据经验和实践,这两种策略产生的实际效果,应该是不同的。

            (3)信息素局部更新。

            当每只蚂蚁都选择一个城市(走完一个边)以后,按公式(6)或者公式(7)更新该边上的信息素。 

            这两种公式分别对应的是也就是仅仅是△f:的计算方法不同。模型中,蚂蚁在路径上留下的信息素量是一个与路径长度无关的常量,对路径长短的信息没有使用,硬磁在探索初期不易找到好的路径;在am-qu姐tity模型中,蚂蚁留下的信息素量与局部路径长度成反比,强化了路径长短的信息,但是这只是提供了局部路径优劣的信息,和ant—density一样无法反映全程范围的路线的长短。全局信息修改策略就提供了全局的信息了。在这个算法中,一般参数设置如下:其,也中n表示点的规模,L表示最短距离。这些数据只是根据实践的经验得到了,在理论上并没有证明。

            (3)MMAS系统算法

            通过从最初的AS的研究,经过ACS等方法的一步步的改进,对~些组合优化问题的搜索空间特征研究,提出了MMAS在三个方面和AS不同:

            (1)为了避免在搜索中过早的陷入次优解,信息素的范围被限制在。信息素更新无论怎么选择,都有可能陷入次优解,因为在这样的情况下,某一种解的信息素比其他的显著的要多,这样会迸一步加强信息素的更新,通过这样的正反馈会使得陷入次优解。

            很明显,这种陷入次优解的情况可以避免。方法之一就是通过限制信息素,可以很容易的避免在算法的运行过程中信息素变的过大或者过小的情况。为了达到这个目标。

            (2)在每一次迭代之后,只有在这次迭代中取得最优路径的那一个蚂蚁增加信息素,这一个蚂蚁更新信息素迹的公式如下: 

            者是全局的最优解。但是使用前者,一般算法收敛的速度较慢;使用后者,则算法容易收敛到次优解。因此,一般把前者作为缺省,而在一定概率下使用后者,这是一种动态的混合策略。

            (3)把信息素的初值设置为丁一。把信息素的初始值设置为f。可以使得在丁算法开始迭代中增加解的搜索范围。因为信息素的挥发,经过第一次迭代之后,信息素的量就不同,第二次不同的程度加剧,如果信息素的初始值很小,甚至小于丁。。,这种信息素迹之间的不同会很快的增加。一开始把初始值设置为彳。。可以使得进化的速度变慢,对解的搜索是有利的。

            3.3蚁群算法的时间复杂度和空间复杂度

            下面我们以求解TsP的As算法为例,来分析蚁群算法的复杂度。如图5所示:

            l瑚始化;即设置元素数目为n2的路径信息表,即给每个边相应的权,时间复杂度为

            2)。2和一般的智能计算类似,算法可能永远都找不到一个解,或者计算的次数太多,无法在有效地时间内完成。因此应该出一个最大的计算次数上限,防止计算无法终结。而计算次数的上限,也只能粗略估计。根据经验或者具体实践给出一个估算法的次数N。。如果超过了Nc次数,一般得到的为解,也许这个解不是最好的。则这一步的时间复杂度为O(Nc)。

            21清空禁忌列表:m只蚂蚁,每个蚂蚁均有自己的禁忌列表,而每个禁忌列表的长度为n。则时间复杂度:O(mn)

            22m只蚂蚁随机放置到不同的城市当中需要时间0(m),并把这m个城市放入禁忌列表中,需要时间O(m)。

            23.每个蚂蚁都需要周游完所有城市需要n步,时间复杂度为

            2.3lm个蚂蚁根据公式(1)的计算结果选择自己的未来,需要判断n.1个城市是否属于禁忌列表,时间复杂度为。

            232把该城市加入到禁忌列表中,需要时间0(1)。

            3.4蚁群算法的特性

            蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。众多的研究结果己经证明,蚁群算法具有很强的发现好解的能力,这是因为该算法不仅利用了正反馈原理、在一定程度上可以加快进化过程,而且是一种本质的并行的算法,不同个体之间不断的进行信息的交流和传递,从而能够相互协作,有利于发现较好的解。蚁群算法可以解释为一种特殊的强化学习算法。它具有如下优点:

            基于人工蚁群系统,蚁群算法被提了出来,它最主要的特性是例

            (1)分布式计算:分布式计算要求个体独立地搜索最优解,而个体之间互不干扰,这对于避免过早收敛有一定的效果:

            (2)正反馈:正反馈机制能够扩大解的质量对个体选择路径的影响,使得算法能够快速地发现较好的解或最优解:

            (3)通用性:它可以解决同一问题的不同版本,比如在旅行商问题中,既可以解决对称旅行商问题(TSP),也可以解决不对称的旅行商问题(ATSP)。

            (4)鲁棒性:它通过稍加修改,就可以应用到其他类型的问题当中

            (5)启发性:人工蚂蚁能够利用反映可行解质量的启发信息,借以指导自己的搜索方向,这使得算法在搜索过程的早期就能发现质量较好的解,而完全随机的选择路径,会造成早期搜索到的解的质量不商。

            (6)需要较长的搜索时间:算法的计算量比较大,算法的计算复杂度主要在解构造过程,比如对TSP问题,其复杂度为O州Cnj)。

            (7)并行性:由于每个蚂蚁个体是独立地搜索可行解,容易实现该算法的并行化,从而提高算法效率。

            (8)局部收敛:和其他进化算法一样,蚁群算法存在着早熟现象,即容易陷入

            局部最优解,这是算法设计过程中应力求避免的。

            (9)容易出现停滞现象(stagnationbehavior):即在搜索进行到一定程度后,所有个体发现的解完全一样,不能对解空间进一步进行搜索,不利于发现更好解。当然,这个缺点可以通过与其他方法结合来改进。

            总的来说,蚁群算法是一种设计思想独特,拥有较多优良特性的优化算法。近年来对这种算法的研究逐渐多了起来。

            3.5蚁群算法的应用

            然而,蚁群算法存在搜索时间过长的问题,而且当运算一定次数后就容易因为较优解的信息量不断强化使得蚂蚁大量聚集于较少的几条路径上,出现早熟、停滞现象,使得到的最优解是局部最优的。为了克服这些缺点,不少学者提出了改进算法。例如,文献f2q则提出了一种新的改进的信息素更新策略;其一,局部信息素修改时,挥发系数动态改变;其二,全局信息素更新时,则将蚂蚁所走路的较短的那些路径上的信息加强,而较差的那些路径上的信息减弱。文献129提出了~种基于蚂蚁进化规则的算法。文献f3钟主要提出了~种相遇算法,其基本思想是在求解TSP问题中,用两只蚂蚁共同完成对一条路径的搜索,以使搜索速度提高。文献13JJ提出了~种变异策略,以加快局部搜索。文献‘32’提出了一种基于最近邻居选择、动态信息素更新和变异策略的高速收敛算法。

            由上述可知,只要在相应的问题中能实现用一个图表来表示将要解决的问题,能定义一种正反馈过程,问题结构本身能提供解题用的启发式信息,并建立一定的约束机制。这样的机制使得蚁群算法具有很强的发现较好解的能力。对于演化算法的关键问题之一,就是在“探索”和“利用”(eXploratlon&唧lohtion)之间建立一个平衡点,也就是说既要使得该算法的搜索空间尽可能的大,以寻找那些可能存在最优解的解区间;同时充分利用群体内当前具有的有效信息,使得算法搜索的侧重点放在那些可能具有较高适应值的个体所在的区间内,从而以大概率收缩到全局最优解。

            法以最近的邻届节点选择和动态信息更新策略来加速全局收敛,以一种独特的变异策略来加快局部寻优,使收敛速度大幅度地提高。W J-Gutjahr等人提出一种以图为基础构建的蚁群系统框架来解决组合优化问题,在一定的条件下,每次迭代所得到的解能以近似于l的概率向最优解收敛。L M GambardeJla等人提出了一种混合型蚁群算法H,在每次循环中蚂蚁建立各自的解后,再以各自的解为起点用某种局部搜索算法求局部最优解,作为相应蚂蚁的解,这样可以迅速提高解的质量。H M Botee等人对参数m,Q,9,p的选择进行了深入的研究,用遗传算法求得这些参数最优组合。还有不少其他文献都谈论如何改进以提高效率,例如,引入交叉算子以提高搜索多样性、引入分支因子r作为衡量群体多样性的指标,当r低于某一值时,对各路径上的信息作动态调整,以期望克服停滞现象。

            蚁群算法的模型己成功应用于求旅行商问题,二次指派问题,排序问题等NP困难的组合最优化问题,结果可与模拟退火,遗传算法等通用的启发式算法相媲美。下面是蚁群算法在具体问题中的应用:

            (1)蚁群算法在电信中的应用

            蚁群算法在电信路由中的应用有比较成功的例子,I押公司和英国电信公司在90年代中后期都开展了这方面的研究,在所采用的蚁群路由算法fAntcolonvR.outing,ACR)中,蚂蚁根据它在网络上的经验与性能,动态地更新路由表项(R0uting-TableEntries)。如果蚂蚁因为它经过了网络中堵塞的路段,而导致了比较大的延迟,那么就对相应的表项做较小的增强,如果某条路段比较顺利,那么就对该表项做较大的增强川。同时应用挥发机制,就可以做到系统信息的更新,使得那些过期的路由信息不再保留。在当前壤优路径出现阻塞时,ACR算法能很快找到另~条可替代的最优路径,从而提高网络的均衡性、网络负载量以及网络的利用率基于蚁群算法的排课系统研究和设计

            (2)蚁群算法在经济领域的应用

            蚁群算法在经济领域也有很好的应用前景,比如利用它对内河航道提供科学合理的规划,解决集装箱的集散问题美国大平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件,结果每年至少节约jOoo万美元费用开支。英国联合利华公司己率先利用这种蚂蚁的群体智能技术改善了其一家牙膏厂的运转状况。 

            (3)蚁群算法在组合优化问题中的应用

            蚁群算法在旅行商(TSP)、作业调度问题(JSP)等组合优化问题当中均有较好的应用。其中在旅行商问题(TsP)中的研究是最普遍的,也是首先用于解决TsP问题的。国内在对蚁群算法的研究上,大多是基于旅行商问题进行理论探索和仿真实验的

            第四章排课系统的模型分析

            4.1系统基本功能

            系统主要有以下功能:

            一、自动生成课程表。在准备好排课有关数据后,系统可以自动安排课程的时间,自动分配合适的教室。在安排课程时问时,可以一次将所有课程安排完毕,也可以分若干次安排,每次安排后,可以利用系统提供的其它功能对安排结果进行查询调整,然后再安排其它课程。

            二、基本数据的输入和维护。将教学调度过程中所涉及的基本信息,如教师、班级、教室、授课任务等,输入到相应的数据文件中,对这些信息可以进行维护,如:查询,修改和删除等工作。具体数据的输入可以人工输入,也可以直接从各院系上交的文件中导入。

            三、形成课表的网页文件。系统可以把安排好的课表形成可以上网查询的文件,通过它们可以实现网上公布课表。学生和教职工可以在网上查询其课程,以及某些教室的上课情况。

            四、课表的维护。对于形成的课表可以进行增加、修改、查询、删除和打印操作。对于一些死锁课程进行人工调整等。在修改过程中,系统提供教师,班级,教室空闲情况的信息。

            上述四个功能,其中自动排课是核心部分,也是排课系统中最难的,程序中最耗费空间和时间的部分。

            最关键是当基本信息已经输入的前提下,管理员可以发出让计算机排课的指令(coursesarrangement),这是排课系统的核心。

            4.2数据模型

            根据系统需求分析,本系统共需要四类数据文件,这些数据文件包含了22种数据,它们分别是: 

            第一类教学计划,教学任务数据文件。每个学期的教学计划都不一样,因此其相应的数据每学期都要改变。教学任务则是根据教学计划排出的具体课程。

            第二类包括系,职称,教师,班级等数据文件。这类数据的特点是,~旦建立好,不用每学期进行输入等处理。只在有变化时,才须进行相应的操作。

            第三类是教室数据,包括教学楼,教室,教室特性(如有无多媒体等)等3种数据。它们是排课的基本信息的~部分,输入~次后,只要不变化一般都是不需要修改的。

            具体数据字典如下:

            本数据用来存放学校有学生的院系及承担课程单位的信息。某个院系或单位在文件中是一条记录。每条记录由下述信息组成:

            1)编号:O-99中的任一个;

            2)系名:最多10个汉字。

            职称:本数据用来存放学校有关职称的信息。一个职称是~条记录。每条记录由下述信息组成:

            1)编号:01.99中的任一个。

            2)职称名:最多3个汉字。

            教师:本数据用来存放学校教师的信息。每位教师是一条记录,每条记录由下述信息组成;

            1)编号:6位数码,头两位数码为该教师所在的系号,后4位按照教师数自动生成;

            2)姓名:最多4个汉字:

            3)职称:职称编号;

            4)出生年:日期型;

            5)开始工作时间:日期型

            6)性别:男或女。

            7)系别:院系编码

            班级:本数据文件用来存放学校学生班级的信息。每个班级是一条记录,每条记录需要下述信息:

            1)编号:8位编码,前两位是班级所属院系的编码,中间四位是班级入学的时间,后两位是班级在院系中的编码;

            2)班名:最多10个字符;

            3)人数:2位数字,是该班的总人数;

            教学计划:用于存放教学计划信息,在一个学期所设的一门课是一条记录,每条记录需要下述信息:

            1)教学计划编号:10位编码,自动生成;2)课号:课程编号;

            课程:本数据用于存放全校所有开设课程的字典文件。每类课程是一条记录,每个记录由两部份组成:

            1)课程编号:最多10位字符,头两位是这门课的开课系的编号,其它几位由系统自动生成;

            2)课程名称:最多10个汉字。

            3)学时:是讲课、实验、上机的总学时;

            4)周学时:两位整数,是理论教学的周学时;

            5)学分:两位整数;

            6)是否必修:1个字符,如:选修,限选,必修等;

            7)是否考试:1个字符,如:考试,考察等;

            8)是否需要多媒体;

            第四章排课系统的模型分析

            3)教师:教师编号;

            4)班级:班级编号。

            基于蚁群算法的排课系统研究和

            1)教学任务编号:和教学计划编号是一样的

            2)课号:课程编号

            3)教师:教师的编号

            4)班级:班级的编号

            5)教室:教室的编号

            6)时间:定义一周内上课时间片

            教室:教室信息存放在教室文件中,每个教室是一条记录,由下述四部分组成:

            1)编号:四位数码,即该教室所在的教学楼编号;

            2)教室名:至多6个字符,该教室的名称;

            3)人数:3位数字,即该教室容纳人数;

            4)类型:1位数字;

            教学任务:教学任务文件用于存放某年度某学期排课后的所有课程情况,是可以让学生和教职工直接查阅的文件。每个课程任务需要记录以下信息:

            4.3二分图模型分析

            通过上面的分析,可以看到,在排课系统中存在着五个的因素,分别是:教师、班级、课程、上课时间以及上课的地点。排课算法可以描述为给某个课程选择一个合适的时间和地点,但是这里要受到教师和班级的约束,教师、班级和教室不能再相同时间内上课。

            直接去搜索这个解空间,问题的规模太大(公式)。这个空间实际上可以简化,毕竟这五个因素之间的关系都不是一种满映射的,问题恰恰是在这个关系表中,各种关系是比较稀疏的,如:教师、班级和课程之间。教师只和几个班级有关系,班级也只有十数门或数十门课,每个教师也只要教几门课。

            这五个因素的笛卡尔乘积就构成了问题的解空间,排课也就变成了在问题空间搜索一个解;lLesson1个节点,这些节点只要满足:教师、班级、教室在时间上没有冲突就可以,也就是没有在同一时间安排两门课。这里把课程也作为~个因素考虑,主要因为一个教师可能为一个班级教授多门课,这样如果不考虑课程因素,就可能无法处理多门课的问题了,而且在处理中,如果一门课一周之内要安排几次,也可以看成是若干门课。下面的排课算法中,通过平衡策略也可以保障一门课有一定的时间间隔。那么问题的解空间实际上就是构成了~个五元组:<教室,时间,教师,班级,课程>的关系表。设这个关系表为R,则问题的节点数为: 

            对R这个关系进行改造。分别以RTc。和RcT两个关系袁中的关系为节点,这样形成一个新的图形G={N,s),其中N表示G中的所有节点,s表示边。则G的节点数是INl=1R。l叫心,I。并设GTc。表示来源于RTc。的节点,G。。表示来源于R。,的节点。

            任何属于G讯部分的两个节点之间是独立的,而属于G。,中的节点也是彼此独立的,都不会产生联系。图8就是一个二分图了。一部分是属于GTc。的节点,另一部分是属于G。,的节点。

            教师和时间之间实际上是个满射,每个教室在每个时间上都可以安排课程。而且这比较符合实际问题的求解过程,每个院系在向教务部门提供教学计划的时候,也只需要提交<教师,班级,课程>这个三元关系,由教务部门来具体安排

            图G两部分节点映射是一对一的关系,这样我们首先解决教室冲突的问题:每个教室在同一时间只有一个节点,而且这个节点只安排给某一个课程,因此不会出现同~个教室被安排给两门课的问题。但是这个模型无法解决教师或者班级在同一个时间上课的问题,也就是说不是一个普通的二分图,在匹配的时候,除了一一映射外,还存在着其他的约束条件:教师和班级的冲突的约束,因此这是一个增强的二分图。G。的元素之间存在着部分排斥的现象。教师或班级上课的时间是不能重复的,否则就冲突了。这个现象处理,在下一小节。

            在这个二分图中,还有以下要说明的:

            1)在G。;中的关系是可以重复的。如果菜一门课需要上2次或这2次以上,可以在RTcL中重复出现。

            2)G。,中的关系是不能出现重复的。

            3)需要满足:fG。f≤IG。f,否则就不可能存在解可能性了。实际问题中,应远远小于,这样可以有足够的教室提供给学生自学。

            4.4算法模塑

            把蚂蚁的这样的一个回路的结束,看作是蚂蚁的一次周游。蚂蚁在边上释放信息素,信息素量也随着时间的逐渐减少。这样随着蚂蚁的移动,对于某个边上的信息素就逐渐增多。每次周游结束,选取相应的边,考察是否满足要求。如对于点N。我们选取以其为起点的所有边信息素量最大那个边的另一端点,作为N。在二分图中的匹配点。这样就把所有的伪匹配点(即伪匹配边)找到,但是这里存在一些冲突,如:教师时间可能冲突,班级时间可能冲突,已经同一个教室同一时间内可能被多个课程匹配等。

            有了上面的二分图,F面根据蚁群算法的理论来设计一个基于蚁群算法的排课算法模型。

            设存在cJG丁c。1个蚂蚁,它们散落在GTc。中各个节点中。其中c为一个常数值。G的每条边初始化一个浓度钒。每个蚂蚁在二分图之间进行移动。也就是说蚂蚁始终在二分图中的两个部分中来回移动,直到问题得到解决。蚂蚁按照某种策略从GTcL中的节点出发,到达G。,中的节点,然后在按照某种策略返回,我们把这样一个过程看作一个闭合的回路(图10:从N。斗N。。N。)。有些情况下,特别是开始的时候,一般按照策略返回后,不能回到出发点,这个也看作一个回路,一个不闭合的回路。

            第四章排课系统的模型分析

            IsResuI“):检测当前运行结果是否满足要求,如果满足,则返回值为真,否则为假。是否满足要求,也就是看班级和教师有没有冲突,已经是否出现了某个课程连续上的问题。

            init():构建基本数据模型,并初始化数据:主要有根据上节模型构建二分图,采用一个二维数组保存边上的信息素,并赋上初始的信息素。

            P1aceAnt():把蚂蚁散落在研℃L各个节点上。比如可以使用随机策略,随机把蚂蚁放在节点上,蚂蚁的个数不需要太多,以l~5只适宜。并把这个节点放入蚂蚁的列表中。

            selectPat}lFromcTLTbcTO和selectPat}l寸omcTT0cTLO:为每个蚂蚁选择路径,前者是从(hcL到G。,后者相反,选取的策略是相同的,但是由于二分图的存储格式,具体实现有所不同。在选取中,根据三种不同类型算法,选取不同的公式。

            Nc表示约定的次数。如果始终不能找到一个好的解,则运行的一定的次数就中止了,当然再次运行有可能发现好的答案。

            GlobechangePhor():全局修改信息素。As根据公式(2),Asc根据公式(5),MMAs根据公式(8)。

            LocalChangePhor0:修改本地信息素,只有算法ASC和MMAs才有效,对As算法此函数没有意义。

            4.5冲突的检测和处理

            在前面的分析中,排课系统存在着硬性冲突:教师冲突、班级冲突、教室的冲突。其中教室的冲突包括:同一教室在同一时间不能安排两门课程、同一时间安排的课程总数不能大于所能提供的教室总数、某一课程参加学习的总人数不应大于所安排教室的座位数。也存在这软性冲突:要尽量为所排课程安排上该类课效果最好的时间、课程在一周上多次时,

            (1)班级冲突的检查

            班级冲突的产生和教师冲突产生的原因是一样的,因此班级冲突的检查方法和教师冲突的检查是类似的。

            对每个班级设置一个表ClassTimetable,保存该位教师上课时间。具体设置

            为~个数组,每个数组元素也对应着一个时间片,数组元素的值表示这个班级在这个时间上课的次数。公式如下:

            Clas订imetaMe妇产(酬表示i时间,class上课的次数)显然,在CIassTimetable这个表格中元素值只能是O或者1,如果某个tti大于1,则冲突了。类似教师冲突的解决办法,也是取消后面出现的教室时间安排。

            (2)教师冲突的检查要有一定的间隔性。

            每次周游后,首先为每个GkL中的节点选择对应的G。中的节点。也就是每个课程都选择一个时间和教室。

            对每个教师设置一个表TeacherTimetable,保存该位教师上课时间。具体设置为~个数组,每个数组元素对应着一个时间片,数组元素的值表示这个教师在这个时间上课的次数。公式如下:

            冲突的解决办法就是直接对后出现的这个选择取消。由于教师绝对不允许同时出现上两门课的问题,因此这两个冲突的安排,必须取消某一个。在预处理的时候根据课程的所需资源的紧缺程度进行排序,因此先出现的课程就难以满足,为了能够找到合适的解,我们取消后面的课程时间教室的安排。

            (3)教室冲突

            教室冲突产生的原因不同,也分剐处理。

            (a)某一课程参加学习的总人数不应大于所安排教室的座位数t首先对Gn中的节点按照教室容纳的人数进行降序排列,对GwL的节点按照课程上课的人数进行降序排列。则满足下面的公式(10),有解;否则无解。对于这个预处理,也可以直接带入数据模型,那些不满足的边就可以直接取消,从而也可以简化问题的解空间。

            (b)同一教室在同一时间不能安排两门课程。这个在问题模型构造的时候,就已经解决了,只要同一个Gn中的节点不对应多个6rcL中的节点,同一个教室就对应一门课程了。

            (c)同一时间安排的课程总数不能大于所能提供的教室总数。这个问题可以首先对教学计划中的课程所需要的某种类型的教室数和实际教室数比较,如果小于,则不存在解的可能性,任务失败。降低某些课程的需求,使上述问题得到解决。

            (4)要尽量为所排课程安排上该类课效果最好的时间。这个问题可以在初始信息素赋值的时候,对于某些课效果较好的时间片段给与其较高的信息素,以增加其启发信息。

            (5)教师和班级在一周上多次时,要有一定的间隔性。尽量避免连堂的情况。这个可以在全局信息素修改的时候,加入~定的肩发信息,增强信息素减弱的程度。在实际处理中,某门课程的选择后,发现某个教师的前个时间片或者后个时间片存在着课程,就直接取消。

            4.6案例的分析

            选取三类数据进行测试和比较算法优劣性

            三类测试数据分别选取如下:

            为了数据能够普遍适用,算法不和特例有关系。测试数据选择某个教师对某个班级上某门课进行随机选择。这样根据上述数据E(教师)=4,即平均起来每个教师上四门课程; 

            下面是某一组数据的教师冲突、班级冲突、课程连堂次数。  

            2.关于cMMAS算法的数据显示 

            在处理其他的问题上,cMMAs是三种算法效果最好的。但是,在排课系统中,由于最先选择的课程一般都是认为是可选的,因此希望被选中的边上的信息素能够大大加强,而不希望被消弱,因此有了上限后,这个信息素加强的程度就不够,后期蚂蚁探索的特性,就会表现出来,也就使得冲突个数比其他两种蚁群算法

            3.关于cAcs算法的数据显示:

            从图形中,可以看出,CAsC算法的收敛要比CAs速度快,但是后期波动比较大。这是因为由于cAsc部分情况下直接选取最大值,不需要计算下一城市选取的概率,时间上是高效率的,同时直接选取,有利于当前信息素最大边的信息强化,因此效率高。但是到了后期,由于冲突存在,而直接选取最大值,使得算法的探索性较差,因此造成其波动较大,且最后的冲突数大于cAs中的 

            4.关于EnCAs算法的数据显示:和参数的选择

            基于以上三种算法的特性,并根据排课系统自身的特点,设计一种EncAs算法。与cAS算法不同之处有:

            (1)每个边上有最小的信息素,设为MiflPhor。每个边初始化为MilPhor,信息素随着时间逐渐减少时,最少应为MiIlPhor。这个思想来自于CMMAS。

            MjnPhor和教室与时间片数是成反比的,以MinPhor不影响全局的选择为宜,

            程序中选择; 

            (2)全局信息素修改规则,应用公式(5),这样可以强化被选中的边上的强度,对于那些没有被选中的,就不增加其强度。使强者愈强,思想来源与cAcS。

            (3)边的选择,如果边无冲突,则直接选择最大的信息素量的边为目标;否则就探索,即应用随机选择策略,选择~个边作为目标。没有冲突标志着这个课程的安排是合理的,因此就不需要探索了;有冲突,就是不合理,应夸大探索的范围。(随机,可以探索全部的。)

            横坐标表示运行次数,以百次作为一个单位,纵坐标表示在该范围内有几次从图形可以看出,尽管都得到解,但是需要的次数差别是很大的,其中还有一次没有得到解。

            第五章结论

            本文回顾了排课系统的当前发展,以及蚁群算法的发展历程。并介绍了蚁群算法的三种模式。把二分图原理应用于排课系统中,提出了一种基于二分图的排课问题模型,并把这种模型分别用三种蚁群算法实现。通过试验的数据结果分析了这三种蚁群算法对排课问题的优劣。最后根据排课问题本身的特点提出了~种适合排课问题的蚁群算法变种一EncAs算法。在算法中,通过设置最小信息素量使得尽可能提高解的搜索范围:通过使用无上限的信息素量使得已经找到的解尽可能保持;这些较好的解决了常见的蚁群算法中容易陷入局部最优解的问题。算法中先把大部分课程都安排好,再根据前文中提出的排课问题冲突解决方法,解决所遇到的冲突,这样一步步的接近最优解。在实践中,取得了较好的效果。

            编程所采用的数据类似与高校的教学安排,没有考虑到其他的如中小学、进修等课程安排的问题,因此本算法还有待于进一步的完善,使之能够是应用各种排课问题。蚁群算法的理论与应用研究方兴未艾,有很多的领域需待研究。

            


基于Java的学生成绩管理系统的设计C++学生信息管理系统课程设计报告
学生成绩管理系统c程序设计报告分析名易MyVMS汽车综合管理系统解决方案
名易MyTMS物流运输管理软件系统解决方案信贷管理软件解决方案
银行贷款有效发放系统新一代信贷管理系统业务需求
名易PM项目管理之项目预算管理名易PM项目管理之项目模板设计
名易PM项目管理之项目管理、项目实施过程管理学生信息管理系统项目开发
校园学生排课系统的设计与实现基于Web的学校宿舍管理系统设计与开发
基于UML银行管理系统分析与设计ERP系统操作手册
信息发布:广州名易软件有限公司 http://www.myidp.net
  • 名易软件销售服务
  • 名易软件销售服务
  • 名易软件技术服务

  • 基于蚁群算法的排课系统研究与设计内容