2024年2月26日发(作者:蓝莓采摘)
重庆大学硕士学位论文高校自动排课系统的算法研究与实现姓名:湛德照申请学位级别:硕士专业:计算机技术指导教师:何中市;高宏宾20061001
重庆大学硕士学位论文中文摘要摘要目前,随着我国高校教育事业的不断发展,课程编排问题在一定程度上影响着教学质量的提高。为了保证教学质量,高校必须制定一套严密、规范的教学计划和执行合理的课程安排。而课程编排是比较繁重而关键的一环。回顾过去,1963年,C.C.Goflieb在文章《TheConstructionofClass-TeacherTime-Tables)中提出了课表编排的数学模型,它标志着课程编排课题的研究正式跨入了庄严的科学殿堂。1976年,SEven在论文《onTheComplexityofTimetableAndMultiCommodityFlowProblems》,第一次证明了课表是NP完全问题。在国内,清华大学于1984年在《清华大学学报(自然版)》上发表了林漳希和林尧瑞在该课题上的实验性研究成果,接着国内部分高等院校相继开展了这方面的研究工作。本文分析了排课的数学模型,提出了利用遗传算法解决排课问题的方法,完成的主要工作如下:①探讨课程表问题的约束因素,以优化时间和空间两种资源为目标,通过对比,我们发现采用遗传算法去解决课表问题是比较理想的解决方法,并讨论了它的基本原理、步骤及其产生、发展、现状以及存在的问题等情况。②改进时间安排算法:遗传算法有能简化程序的复杂度和生成最佳课表时间的优点,本论文提出的时间安排算法以经典遗传算法作为基础,进行了以下几个方面研究工作:1)对遗传算法存在的缺陷进行改进和优化,避免了遗传算法出现未成熟就收敛等问题;2)提出排课问题的优化求解模型和约束满足模型;3)针对排课问题研究了染色体编码方式以及遗传操作算子的设计,提出了一种适应度计算方法,由节次优度、日组合优度等相互联系求解。③提出教室安排算法:排课问题中,除了时间安排外,为课程选择一个教室是十分重要的,我们提出了教室安排算法,实现资源优化配置。④系统的实现:针对课表个性化的要求,设置了排课知识库和策略库来动态地调整准则,以满足不同课表要求,体现该系统具有良好的适用性和实用性。本文以五邑大学排课系统的开发为背景,对整个系统的工作进行了分析总结,并对后续工作进行了展望。关键词:排课,遗传算法,组合优化,人工调整
重庆大学硕士学袋论文茭文攮要ABSTRACTRecently,withtheconstantlydevelopmentofhigheducation,timetablinghasveryimportantroleinrisingtheeducationquality.Inorder协guarant∞itsadvancedteachingandstudyingquality,auniversitymustdrawupatightandstandardteachingoneandstudyingplanandCalTyoutthereasonabletimetabling.Thetimetablingisoftheheavyandkeyquestions.In1963,C.C.GotliebproposedthemathematicalmodelofCurriculumScheduleProblem(CSPforshort)inthepaper(TheConstructionofClass-TeacherTime-Tables},itsymbolizedtheresearchingofCSPhadenterthescienc宅domainfield.In1976,S.Evenprovedthepaper(OnthatCSPisaNP—CompletedprobleminTheComplexityofTimetableAndMultiCommodityFlowProblems》China,Tsillghuauniversitydeliveredtheforfirsttime.Inexperimentallyresearchedresultofz}langxiLinandYaoruiLinaboutthisproblemin(JOURNALOFTSINGHUAUNWERSITY(SCIENSEANDnativeTECNOLOGY))。Subsequently,partsofaboutthisotheruniversitiesalsobeganresearchingworkproblem.TheGeneticmathematicsismodeloftimetablingisdiscussedinthispaper,meanwhilethetoAlgorithm(aA)isusedresolvethetimetablingproblem.Themainworkofthispaperlistedasfollows:paperdiscussesnumerousconstraintsinvolvedinthetimetablingproblem,④ThiswhoseaimiStooptimizethetwore搭oul'cesoftimeandapace.Comparing谳像variousAlgorithmtoresolvethemethods,wefindthatit’SanidealmethodtoadoptGenetictimetablingproblem,anddiscussitsbasicprinciple,stepanditscreation,development,inthispaperasfollows:andmakingthebestarepresentconditionandexistentproblemete.@TheimprovementofTime-ArrangedAlgorithmisgivenGeneticAlgorithmhastheadvantagesonofsimplifyingproceduretimetable.Thisalgorithmisbasedasfollowing:1)MakesomeclassicGeneticAlgorithm.ThemaincontentonimprovementsandoptimizationappearingtheclassicGeneticAlgorithm,andimmatureavoidtheGeneticAlgorithmvariousproblemssuch嬲convergence;2)Workouttheoptimizationmodelforresolvingandconstraintstudiedchromosomecodingandheredi移operatoramoddintimetabtingdesigningaimedatproblem;3)Wetimetablingproblem,putforwardfitnesscomputationmodefromslot-superior,combining-superior-on—day.etc.Contactstosolvemutually.very③Classroom—arrangedalgorithm:BesidesTime-ArrangedAlgorithm,it’S珏
重庆丈学硕士学藏论文英文接要importantouttochooseaclassroomforacoBrseintimetablingproblem.Wehadworkedclassroom—arrangedalgodthm,optimalallocationofresourcesisguaranteed.④Therealizationofthesystem:Consideringthepersonalrequestoftimetable,WeestablishedthetimctablingKnowledgeLibraryandStrategyLibrarytoadjustthestandardwithsatisfactionford{fferenttimetablerequests.Itisprovedthatthesystemdevelopedwiththealgorithmhasgoodadaptabilityandavailability.ThispapertooktheexploitationinbackgroundofthetimctablingsysteminUniversity,carfiedonallWuyianalyticalsummaryforthewholework,andmadeanoutlooktothefollow-upwork.Keywords:Timetabling,GeneticAlgorithm,CombinationOptimization,III
独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得重麽盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名:配乙签字日期:幽/年,一月≠日学位论文版权使用授权书本学位论文作者完全了解重麽盍堂重鏖太堂有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密(本学位论文属于不保密()。),在——年解密后适用本授权书。(请只在上述一个括号内打“√”)学位论文作者签名:茫睨签字日期:幽占年膳月年日郢繇铷手签字日期:之励缉f矿月y日
重庆大学硕士学位论文1绪论1绪论1.1排课问题的提出及研究意义高校的排课是教学管理中最基本、最重要、十分繁重而复杂的工作,它涉及到全校全部的专业,全部的师生和全部的课程,它的本质就是为所有的课程安排一组适当的教学时间和地点,使教学能够顺利进行。随着各高校的招生规模扩大,教师和教室资源显得越发紧张,使得本来就有难度的排课越发困难。课表的编排属于一类涉及多种因素的组合规划问题【l】,它必须使课程安排中的教室、教师和学生不发生冲突,这是最基本的要求,在此基础上要尽量满足教师提出的其它要求(比如某教师要求只是上午上课,必须在多媒体教室上课等等)和学校教室资源的约束。在人工排课的过程中,实现这样的要求是有一定困难的,为学校排出一个可行的课表要排课工作人员耗费两到三个月的时间,工作量非常大,而且排出来的结果也未必尽人意。随着各高校的教育体制改革的深入和招生规模的进一步扩大,手工排课的缺点越显突出,我校的情况更为严重,因为教师和教室资源的限制,排课非常困难。而计算机恰好能帮助解决这个问题,它具有自动运行、计算速度快等特点,只要有相应的软件系统,就能很好地解决排课的困难,实现教学管理决策的科学化。1.2国内外计算机自动排课的研究历史50年代末,国外就有人开始研究课表编排问题。1962年,Gotlieb曾提出一个课表问题的数学模型怛】,并使用匈牙利算法解决了三维线性运输问题。此后,人们对课表问题的算法、解的存在性等问题做了很多深入探讨,但是大多数文献所用到的数学模型都是Goflieb的数学模型的简化或补充。近50年来,人们对课表问题的计算机解法做了许多尝试。其中,有人将课表编排的整数规划模型问题归结为求一组O.1变量的解,但是其计算量非常大,而且解决O.1线性优化问题的分支定界技术却只适用于规模较小的课表编排;Mihoe和Balas(1965)将课表公式化为一个优化问题【3】;另外还有人提出将它当作一种线性编程的方法或将课表问题简化为三维运输问题;而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型[41;此外,有些文献试图从图论的角度来求解课表问题,但是图的染色问题也是NP完全问题,只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题吲。这样的数学模型与实际相差甚远,所以对于大多数学校的课表编排问题来说没有实用的价值。进入九十年代以后,国外对课表问题的研究仍然十分活跃,比较有代表性的有印度的Vastapur大学管理学院的Arabinda
重庆大学硕士学位论文1绪论Tripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。对于课表的编排,已经使用的的算法有:关联规则FP.growth算法161、基于时间位图迭加匹配的算法‘71、基于资源匹配的算’法【81、分组优化决策算法【9】、分支定界法【101、有限回溯法【ll】,拉格朗日松弛法,二次分配型法等多种方法。由于课表约束复杂,用数学方法进行问题描述时往往导致问题规模剧烈增大,这已经成为应用数学编程解决课表问题的巨大障碍。外国的研究表明,解决大规模课表编排问题单纯靠数学方法是行不通的,而利用运筹学中分层规划的思想将问题分解,将是一个有望成功的办法m】。在国内,对课表问题的研究开始于80年代初期,具有代表性的有:南京工学院的UTSS(AUniversityTimetableSchedulingSystem)系统【13】,清华大学的TISER系统n4】,大连理工大学的智能教学组织管理与课程调度系统【15l,西南交通大学在分析高校课表编排所遵循的基本原则和模糊性原则的基础上,定义了课元之间关于教师的相关关系和关于自然班的相关关系,提出了以课元相关运算和课元的候选时空片计算为核心的计算机排课算法1161,延边大学根据高校课程表的制作特点,设计了计算机自动排课的数据结构与算法【17】;沈阳电力高等专科学校研制了基于Client/Server的开放式智能排课系统[181等。使用遗传算法来求解排课问题也有较多其它相关的报道【19.241,还有~些其它高校根据自己的情况编写了一些程序去实行计算机自动排课,例如浙江大学的“教务管理系统”等等。这些系统大都是模拟手工排课过程,以“班”为单位,运用启发式函数来进行编排,都或多或少存在问题。2
重庆大学硕士学位论文2遗传算法的设计思想2遗传算法的设计思想遗传算法(GeneticAlgorithms,GA)研究的历史并不算长,20世纪60年代末期到70年代初期,主要由美国Michigan大学的JohnHolland与其同事、同学们研究,从试图解释自然系统中生物的复杂适应过程入手,模拟生物进化的机制来构造人工系统的模型,形成了较完整的理论和方法。随后经过20余年的发展,取得了丰硕的应用成果和理论研究的进展,特别是近年来的进化计算热潮,计算智能己作为人工智能研究的一个重要方向,以及后来的人工生命研究兴起,使遗传算法受到广泛的关注。从1985年在美国卡耐基·梅隆大学召开的第一届国际遗传算法会议(InternationalIEEE的TransactionsonConferenceOllGeneticAlgorithms:ICGA'85)到1997年5月EvolutionaryComputation创刊,遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。2.1遗传算法的产生与发展早在20世纪50年代和60年代,就有少数几个计算机科学家独立地进行了“人工进化系统”的研究,其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形,比如大多数系统都遵行“适者生存”的仿自然法则,有些系统采用了基于种群(population)的设计方案,并且加入了自然选择和变异操作,还有一些系统对生物染色体编码进行了抽象处理。60年代初期,柏林工业大学的I.Rechenberg和H.ESehwefel等在进行风洞实验时,由于设计中描述物体形状的参数难以用传统方法进行优化,因而利用生物变异的思想来随机改变参数值,并获得了较好的效果。随后,他们对这种方法进行了深入的研究,形成了进化计算的另外一个分支——进化策略(EvolutionaryStrategy,ES),如今Es和GA已呈融合之势。同样是在20世纪60年代,L.J.Fogel等人在设计有限态自动机(FiniteStateMachine,FsM)时提出了进化规划(EvolutionaryProgramming,EP),借用进化的思想对一组FSM进行进化,以获得较好的FSM。他们将此方法应用到数据诊断、模式识别和分类及控制系统的设计等问题中,取得了较好的结果。后来又借助进化策略方法发展了进化规划,并用于数值优化及神经网络的训练等问题中。由于缺乏一种通用的编码方案,人们只能依赖变异而非交叉(即是杂交)来产生新的基因结构,早期的算法收效甚微。20世纪60年代中期,JohnHolland在A.S.Fraser和H-J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作,又适用于交叉操作,并且强调将交叉作为主要的遗传操作。随3
重庆大学硕士学位论文2遗传算法的设计思想后,Holland将该算法用于自然和人工系统的自适应行为的研究中,并于1975年出版了其开创性著作‘'AdaptationinNaturalandArtificialSystems”。以后,Holland等人将该算法加以推广,应用到优化及机器学习问题中,并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功的应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用到今天,可见Holland对遗传算法的贡献之大。在其后,遗传算法的应用无论是用来解决实际问题还是建模,其范围不断扩展,这主要依赖于遗传算法本身的逐渐成熟。近年来,许多冠以“遗传算法”的研究与Holland最初提出的算法已少有雷同之处,不同的遗传基因表达方式,不同的交叉和变异算子、特殊算子的引用以及不同的再生和选择方法,但这些改进方法产生的灵感都来自大自然的生物进化,可以归为一个“算法簇”。人们用进化计算来包容这样的遗传“算法簇”,它基本划分为四个分支:遗传算法(GA)、进化规划(EP)、进化策略(ES)和遗传程序设计(GP)。2.2生物进化理论和遗传学的基本知识我们知道,生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异,生命是进化的产物,现代的生物是在长期的进化过程中发展起来的。达尔文用自然选择(naturalselection)来解释物种的起源和生物的进化,其自然选择学说包括以下三个方面:①遗传(heredity):这是生物的普遍特征,“种瓜得瓜,种豆得豆”,亲代把生物信息交给子代,子代按照所得信息而发育、分化,因而子代总是和亲代具有相同或相似的性状。生物有了这个特性,物种才能稳定存在。②变异(variation):亲代和子代之间以及子代的不同个体之间总有差异,这种现象称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。③生存斗争和适者生存:自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行,其结果是适者生存,具有适应性变异的个体被保留下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,物种变异被定向着一个方向积累,于是性状逐渐和原先的祖先不同,演变为新的物种。遗传算法模拟的是怎样的生物进化模型呢?假设对相当于自然界中的一群人的一个种群进行操作,第一步的选择是以现实世界中的优胜劣汰现象为背景的;第二步的重组交叉则相当于人类的结婚和生育;第三步的变异则与自然界中偶尔发生的变异是一致的。人类偶然出现的返祖现象便是一种变异。由于包含着对模式的操作,遗传算法不断地产生出更加优良的个体,所采用的遗传操作都与生物尤其是人类的进化过程相对应。如果我们再仔细分析遗传算法的操作对象种群,4
重庆大学硕士学位论文2遗传算法的设计思想实际上它对应的是一群人,而不是整个人类。一群人随着时间的推移而不断进化,并具备越来越多的优良品质。然而,由于他们生长、演变、环境和原始祖先的局限性,经过相当一段时间后,他们将逐渐进化到某些特征相对优势的平衡态,当一个种群进化到这种状态,这个种群的特性就不再有很大的变化了。一个简单的遗传算法,从初始代开始,并且各项参数都设定,也会到达平衡态。此时种群中的优良个体仅包含了某些类的优良模式,因为该遗传算法的设置特性参数使得这些优良模式的各个串位未能得到平等的竞争机会。遗传算法效法于自然选择的生物进化,是一种模仿生物进化过程的随机方法,下面先对几个生物学的基本概念与术语进行解释,以便理解遗传算法。染色体(chromosome):生物细胞中含有的一种微小的丝状化合物,它是遗传物质的主要载体,由多个遗传因子——基因组成。遗传因子(gene):DNA(脱氧核糖核酸)或RNA(核糖核酸)长链结构中占有一定位置的基本遗传单位,也叫做基因。表现型(phenotype):由染色体决定性状的外部表现,或者说,根据遗传子型形成的个体,称为表现型。基因型(10cus):遗传基因在染色体中所占据的位置。个体(individual):染色体带有特征的实体。种群(population)染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。进化(evolution):生物在其延续生存的过程中,逐渐适应其生存环境,使得其品质不断得到改良,这种生命现象称为进化,生物的进化是以种群的形式进行的。适应度(fimcss):在研究自然界中生物的遗传和进化现象时,生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度较高的物种将获得更多的繁殖机会,而对生存环境适应度较低的物种,其繁殖机会就相对较低。选择(selection):指决定以一定的概率从种群中选择若干个体的操作。一般而言,选择的过程是一种基于适应度的优胜劣汰的过程。复制(reproduction):细胞在分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因。交叉(crossover):有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组,亦即在两个染色体的某一相同位置处DNA被切断,其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组,俗称杂交。变异(mutation):在细胞进行复制时可能以很小的概率产生某些复制差错,
重庆大学硕士学位论文2遗传算法的设计思想从而使DNA发生某种变异,产生出新的染色体,这些新的染色体表现出新的性状。编码(coding):DNA中遗传信息在一个长链上按一定的模式排列。2.3遗传算法的基本思想问题域图2.1遗传算法的过程Figure2.1Theproc%¥ofgeneticalgorithm我们现在引用上面的术语描述遗传算法的基本思想。遗传算法是从代表问题6
重庆大学硕士学缎论文2邃铸算法豹设圣}思恕可能潜在解熊的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体,即多个蒺因的集合,其内部袭现是某种基因缀合,它决定了个体的形状的癸嫠表现,麴黧头发憨鸷薤是耄象绝钵孛控豢l这~黪缝戆菜莠基因缀会决定豹。因此,在一开始需要实现获表瑷熬掰基因静映射编礴工作。由于仿照萋鞠编码鲍工作复杂,我们将其进行简化,如二进制编码等。初代种群产生之后,按照适者生存和优胜铹汰的原理,逐代演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小挑选个体,并借助于自然遗传学的遗传算予进行组合交叉移交异,产生爨健表颓豹瓣集|!}冬耱群。这个遥程将簿致秘嚣像自然遴纯~榉鹣后生{弋释群鞋:虢代更鸯珏适应予环境,末代耱嚣中的最傀个体经过解碍,W以作为问题近似最优解。遗传算法采纳了自然进化的模型,如选择、交叉、变异、迁移、局城与领域等。基本遗传舞法如图2.1所示。计算开始对,~定数嚣静N个令体(父个体l、父个体2、父个俸3、父令髂4……)帮秘群蘧袄I缝秘始纯,著谤算每令令俸静适应度函数,第一代毽鼯窃始代产生了。如果不满足优化准则,开始产生新一代的计算。为了产生下一代,按照遁成度选择个体,父代饕求基因重组(交叉)而产生子代。所肖的子代按一定概攀变异,然后子代的邈威度又被重新计算,子代被插入到种群中将父代取而代之,构成新的一代(子个体l、子个体2、予个体3、子个体4……)。这撵熬过程德环执行,壹翼瀵是钱纯准籍为壹。2.4遗传算法的特点我们知邋,传统的优化方法童娶有三种:枚举法、启发式算法和搜索算法:①枚举法;枚举出可以解集仑内的所有可以解,以求出精确最优嬲。对手连续函数,该方法要求先对箕逡行薅散亿处理,这撵藏霹缝嚣离教楚理瑟汰远这蚕至《最优解。鼗岁},当枚举空间院较大时,该方法的求解效率比较低,有时候甚至在目前最先谶计算机上也无法求解。②启发试算法:寻求一种能产生可以解的启发式规则,以找到一个最优解或者近似最优解。该方法的求解效帮比较高,但对每一个需求解的闯题必须找出其特毒夔寝发式羧照,这令建发式黢翅一般无逶爱蠖,零逶会手其毽翅题。③羧索黪法:寻求一种援索舞法,该算法在可行解集合的一个予集内送行援索操作,以找到问题的最优解或者近似最优解。该方法虽然保证不了~定能够得到问题的最优解,但若适当地利用一些启发知识,就W在近似解的质量和效率上达到一种较好的乎衡。7
重庆大学硕士学位论文2遗传算法的设计思想随着问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化问题的通用方法,遗传算法正为我们提供了一个有效的途径,它不同于传统的搜索和优化方法。主要区别在于:①自组织、自适应和自学习性(智能性)。应用遗传算法求解问题时,在编码方案、适应度函数及遗传算法确定后,算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为“适者生存,不适应者被淘汰”,因而适应度大的个体具有较高的生存概率,通常它们具有更适应环境的基因结构,再通过基因重组和基因突变等遗传操作,就可能产生更适应环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍,即需要事先描述问题的全部特点,并要说明针对问题的不同特点算法应采取的措施。因此,利用遗传算法的方法,我们可以解决那些复杂的非结构化问题。排课问题恰恰就是这样的问题,所以用遗传算法去排课是最好的方法。②遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点,而不是单点。它的并行性表现在两个方面,一是遗传算法是内在并行的,即遗传算法本身非常适合大规模并行。最常见的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算,运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果),等到运算结束时才通信比较,选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求,可以说,遗传算法适合在目前所有的并行机或分布式系统上进行并行处理,而且对并行效率没有太大影响。二是遗传算法的内含并行性。由于遗传算法采用种群的方式组织搜索,因而可同时搜索解空间内的多个区域,并相互交流信息。使用这种搜索方式,虽然每次只执行与种群规模n成比例的计算,但实质上已进行了大约O(n3)次有效搜索,这就使遗传算法能以较少的计算获得较大的收益。③遗传算法不需要求导或者其他的辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数。④遗传算法强调概率转换规则,而不是确定的转换规则。⑤遗传算法可以更加直接地应用。⑥对给定的问题,遗传算法可以产生许多潜在解,最终选择可以由使用者确定。2.5遗传算法的基本操作遗传算法包括三个基本操作:选择、交叉和变异。这些基本操作又有许多不同的方法,如下面所述。①选择选择是用来确定重组或交叉个体,以及被选个体将产生多少个子代个体。首
重庆大学硕士学位论文2遗传算法的设计思想先计算适应度:1)按比例的适应度计算;2)基于排序的适应度计算。适应度计算之后是实际的选择,按照适应度进行父代个体的选择。可以挑选以下算法:1)轮盘赌选择;2)随机遍历抽样;3)局部选择;4)截断选择;5)锦标赛选择;在选择操作时会出现几个问题:乱在遗传进化的初期,通常会产生一些超常的个体,这些异常个体竞争力很b.在遗传进化的后期,即算法接近收敛时,由于种群中个体适应度差异较小上述的问题,我们通常称为遗传算法的欺骗问题,而适应度函数的设置就是遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用1)直接以待求解的目标函数转化为适应度函数。即:若目标函数为最大化问题Fi“f【x))=f【X)若目标函数为最小化问题Fi“f(x))=一f(x)这种适应度函数简单直观,但存在两个问题,其一是可能不满足常用的轮盘2)若目标函数为最小化问题,则:蹦鞴_[c:嚣㈣姐一9突出,从而控制了选择过程,影响算法的全局优化性能。时,继续优化的潜能降低,可能获得某个局部最优解,这不是我们所期待的。为了避免这些问题的产生。因此,适应度函数的设计是遗传算法的一个重要方面。种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言,适应度函数是由目标函数变换而成的。适应度函数基本有以下三种:赌选择中概率非负的要求,其二是某些待求解的函数在函数值分布上相差很大,由此得到的平均适应度可能不利于体现种群的平均性能,从而影响算法的性能。其中C。。是舡)的最大值估计。若目标函数为最大化问题,则
重庆大学硕士学经论文2遗传雾法麴设诗愚恕Fit(f(x)产f婀一G一,取)>cm“。0,其像这秘方法燕瓣第一静方法懿改遴,霹敦髂为“爨隈羧造法”,毽寿时存凌爨限篷预先信诗露蕊、不精确的目逶。3)若目标函数为最小化问题:Fit(fix))=1,(1+c+f(x”C≥O,c+f(x)-兰。若目标函数为最大化问题:Fit(f(x))=l/(1+C一援x))C≥瓴C-f(x)≥O这耪方法与第二静方法类酝,C海嚣括函数雾陵豹僳孝继诗篷。适应度瞬数设计应该满足以下几个条件,它应该非负、连续、最大化、单值的:能够反映解的优劣程度;应该尽量简单,计算爨尽量小。②交叉藏簇邈重组基毽羹缀楚结合来童父戎交熬耱嚣孛戆覆塞产囊灏煞今薅。依据令髂缓鹃表示方法的不丽,可以有以下的算法;1)实值煎组·离散爨组;●中闻黧缀;·线缝鬟缀;●扩展线馁重组。2)二遴制交叉·单点交叉;·多点交叉;●均匀交义;·洗簿交叉;●缩小代理交叉。③变异交叉之餍予代经历的变异,嶷际上是子代基因按小概率扰动产生的变化。依据兮薅编羁袭零方法戆不嚣,霹鞋蠢以下豹算法:1)实俊交雾;21二进制变异。另外的操作觎括:扎交叉概率(Pc)和变异概率(Pm)
重庆大学矮士学像论文2蘧姥雾法豹竣诗思想交叉操作和变异操作并不是对所有个体都发生,而是根据相应的概帮。交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在,直接影响算法的收敛性,Pc越大,新个体产生的速度就越快,然而,遗传模式被破坏的W能性也越太,搜褥其蠢意适应疫戆令傣缝掏缀抉裁菝破坏。艇蹩麴栗Pe过夺,会傻羧索过程缓慢,醵麓停滞不藏。对予变弊概率Pm,强聚遥小,裁不易产生赣靛个俸结构,如果Pm取值过大,那么遗传算法就变成了纯粹的随机搜索算法。针对不同的优化问题,鬻簧反复实验来确定Pc和Pm。b.编码(Encoding)遗传算法孛进化过程是建立农编码辊割基础上的,编码对于算法盼黢鼹懿搜索爱力秘秘群多样往等影穗攫丈。如何将问题的解转换为编码袭达的染色体是遗传算法的关键问题。Holland的编码方法是二进制0.1串表达,熊优点是编码、解码操作简单,交叉、变弗等遗传操作便于实现,而且便于利用模裁定理进行理论分析锌;其缺点是不便于反映所求问题的特定知识,对于一些连续溺数的优化问题,潮子遗传算法的l媳机特性使萁最熬搜索黢力较差,对于一整多缓、离穗度要求熬逡续函数髋纯,二滋裁缡玛存在着连续薮数离敖亿时静映射误爱,个俸编码串较斑时,可能这不至l耪发要求,个体编码串较长时,虽然能提高精度,但却会使算法的搜索空间急剧扩大,从而造成遗传算法的性能降低。后来许多学者对遗传算法的编码方式进行了多种改进,例如,为提黼局部搜索能力,提出的Grey码等。遗传算法黪一般流程匿如麓2+2所示。第l多;夔秘产生令体数嚣~定豹裙始静饕,褥个令俸表示受染色髂懿基毽编码:第2步;计算个体的适应度,并判断是否符合优化准则,若符合,输出最佳个体及其代袭的最优解,并结束计算,否则转向第3步;第3步;依攒适应度选择再缴个体,适应度高的个体被选中的概率搿,相反,适应度低鹣令侮霹辘谈海汰;第4步:按照一定的交叉概率鞍交叉方法,生成藏稳个体;第5步:按照一定的变异概率和变异方法,生成新的个体;第6步:豳交叉和变异产生新一代的种群,返回到第2步。遗传算法中的优化准则,一般依据问题的不同肖不同的确定方式。例如,可班采用以下的准嬲之一幸#为判断祭终;1)释群审今俸熬最丈适应发怒避预先设定篷;2)种群中个体的平均适应度越过预先设定值;3)世代数超过预先设定值。
重痰大学硕士学爱论交2遗传舞渡瓣设计愚怒翻2.2遗黄算法的漉穰翻Figure2.2Theflowchmtofgeneticalgorithm2.6经典遗传算法存在的缺陷及改进随着理论和应用研究的日益深入,研究者们己经意识到,简单采用网定不变的进化策略的遗传算法对复杂的暾爝场合效果并不理想,传统的遗传算法逐渐暴露窭一些缺杰。为提褰遗转算法戆投戆,诲多磅究者恐经致宠予这些趣嚣戆繇究,并提出了一系列有效的解决方案。2.6.1初始种群的均匀化改进初始种群的特性对遗传算法的计算结果和计算效率均有重要影响,臻窟现全局最优,初始种群在解空间中应尽爨分散。而经典的遗传算法中,初始种群是随机产生豹,这季中缒壤缝裁可麓导致鹚媲黪群在磐空窝分蠢熬不均匀,簌露影拣算法的往麓。霞魏,在产生裙始弹群鞋雩,应尽量使它筠麓分布在整个磐空蓠审。一种方法楚,为初始种群中的个体之间设置一个距离限制,要求入选柳始种群的各个体之间的距离必须大予这个限制距离,这样就能保证初始种群的个体之间有较明显的麓别,使它们能较均匀地分布在解空间中,保证了初始种群禽有较12
重庆大学硕士学位论文2遗传算法的设计思想为丰富的模式,从而增加搜索收敛于全局最优解的可能.另一种方法是,首先将解空间分割成若干个子空间,对每个子空间进行初始种群选择,然后将每个子空间的初始种群进行合并,生成总的初始种群,那么这个种群中至少包含了来自不同子空间的个体。2.6.2自适应交叉概率和变异概率的改进前面我们说到了交叉概率和变异概率的选择对遗传算法非常重要,无论取值过大和过小都对算法产生不利影响,但是我们很难对一个优化问题确定一个合适的交叉概率和变异概率,因为遗传环境在不断的动态变化,所以,Pc和Pm应该能够随适应度自动改变,当种群各个体适应度趋于一致或者趋于局部最优时,使Pc和Pm增加,以增强新个体产生的能力;当群体适应度比较分散时,使Pc和Pm减小,加快群体的收敛。适应值高于平均适应值的个体,对应于较低的Pc和Pm,使该解得以保护进入下一代;适应值低于平均适应值的个体,对应于较高的Pc和Pm,使该解被淘汰掉。交叉概率和变异概率的这种自适应调整在保持了群体多样性的同时,也保证了遗传算法的收敛性。2.6.3选择算子的改进在各种GA选择策略中,基于个体适应度的比例选择最为常用,该策略算法简单,但是比较容易引起“未成熟收敛”和“搜索缓慢”等问题。“未成熟收敛”就是连续的几代种群中的最优染色体没有任何进化,或者各染色体之间过于近似等。在求解多峰值函数的优化计算时,经常只能找到个别的几个最优解,甚至往往得到的是局部最优解,而我们希望的是得到全局最优解。解决这个问题的一种方法是采用基于小生境技术的选择操作。在生物学上,小生境(Niche)是指特定环境中的一种组合功能。小生境技术就是将每一代个体划分为若干类,每个类中选出适应度较大的个体作为一个类的优秀代表组成一个种群,再在种群中以及不同种群之间通过交叉和变异产生新的种群。小生境的模拟方法主要建立在对常规选择操作的改进基础上。Cavichio在1970年提出了基于预选择机制的选择策略,其基本做法是:当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代个体才能代替其父代个体而遗传到下一代种群中,否则父代个体仍保留在下一代种群中.由于子代个体和父代个体之间编码结构具有相似性,所以替换掉的只是一些编码结构相似的个体,故它能够有效地维持种群的多样性,从而避免产生局部最优解,改善未成熟收敛。另一种方法是引入“遗传一灾变”算法,在GA的基础上,进一步模拟自然界中的灾变现象,以提高遗传算法的性能,尤其是解决重要的未成熟收敛问题。当判断可能发生了未成熟收敛时,施以灾变来改变现状。灾变的形式很多,可以突然增大Pm,或对不同个体实施不同规模的突变,以产生大量的后代。用灾变的方
重庆大学硕士学位论文2遗传算法的设计思想法可以打破旧有基因的垄断优势,增加基因的多样性,创造有生命力的新个体。第三种改进方法是引入浓度选择机制,与适应度比例选择机制相结合,采用加权平均的方式来进行选择。这个方法由下面的式子来表示,其中P表示个体选择的概率,Pf表示适应度概率,Pd表示浓度概率,a表示适应度概率所占的比重。P=axPf+(1一a)×Pd这个式子可以确保适应度高的个体,又抑制浓度高的个体,以保证个体的多样性,改善未成熟收敛。2.6.4交叉和变异算子的改进遗传算法通过交叉和变异这一对相互配合又相互竞争的算子,使自身的搜索能力得到快速提高,交叉操作在遗传算法中起全局搜索的作用,它是遗传算法的核心遗传操作。变异操作在遗传算法中起局部搜索的作用,当搜索陷入局部解而不能由交叉解决时,配合有效的变异可以使之跃出局部解。但是后期的变异可能破坏已经建立起来的最优解的雏形。因此,交叉和变异应很好的配合,不能盲目的进行操作,例如,采用自适应的算子,将进化过程分为渐进和突变两个不同的阶段,渐进阶段强交叉,弱变异,强化优势型选择算子:突变阶段弱交叉,强变异,弱化优势型选择算子。一种方法是:建立一个收敛程度参数b,b=F仃。一F其中:F一为某代中最优个体适应度,F为此代种群平均适应度。因此b近似反映了种群的收敛程度,b越小,个体间适应度相差越小。b越大,个体特性越分散,Pc,Pm应与b成反比.同时为防止破坏全局最优解,对不同个体,Pc和Pm应不同。遗传算法能够很快地找到最优解的90%,但是剩下的寻找最优解的工作却要花费相当长的时间。2.6.5并行遗传算法尽管单一种群的遗传算法很强大,可以很好的解决相当广泛的问题,但采用多种群(子种群)的算法往往会获得更好的结果。每个子种群象单种群遗传算法一样独立地演算若干代后,在种群之间进行个体交换。这种多种群遗传算法更加贴近于自然中种族的进化,称为并行遗传算法(ParallelingGeneticAlgorithms.PGA)。遗传算法发展的二十年里,针对各种不同领域,不同模式的优化问题,出现了很多变形和改进,经典的遗传算法为我们提供了一个平台,在这个平台上可以搭建各种各样的模型。随着遗传算法应用领域的扩大,相信更多的改进和变形会出现,遗传算法家族将越来越壮大。介绍完遗传算法,以及遗传算法的各种改进后,下面我们就来介绍遗传算法在课表问题中的应用,以及针对课表问题,对遗传算法做的变形和改进。14
重庆丈学矮圭学经论文3辩瀚安撄箨法3时间安排算法毫校熬瓣潆是~顼费酵费力懿繁琐工终,它牵涉至g全搜熬颊生巍掰露谖程、所有教室。摊漾在整个过程孛充满了矛詹运魂,其审惫疆上课班缓、耩殍谍程、任课教师一k课时间、地点这个赢个方面在排列组龠中所发生的冲突和矛盾现象。课程门类多、教师少、教室少是摊课时发生冲突和矛盾的主要因素,丽溅缀多、教室少则是矛盾的重要方面,摊课就是要处理教学环节中的各种矛盾。接误牵涉瀚因素缀多,毽都遵循这样鲍原煲|j:谖袋装寿秘于教学设餐熬充分蠢瘸,要骛会教学瘫律。3.1排课需要考虑的约束因素排课是将教师与学优在时间和空间上根据不同的约束条件进行排列缀合,以搜教学正常避彳予,这里约束条件象要是为了避免冲突。冲突,包含的痰容缀多,蔻乎发生在矮露嚣令或多令攘漂渗及煞嚣素之闯。避兔狰突是箨谦楚题审黉缎决的核心问题。只有在满足全部约窳条件和避免所有冲突的基础上,才熊僳证整个教学计划正常进行,而对教师、激室、学生及时间镣几部分资源进行最优化组合配置,才能保证充分发挥各资源的优势。我们把摊漾过程中的约束条件分为三类:基本磁约柬、硬约束和软约荣。其孛基奉疆终塞蔫海羧簿、学生秘教室在嚣空土不藐发象狰突,宅是赫潆怼缓孛最基本盼约束条伴;硬约束是根掭学校的实际情况,捺谦时必须遵循的原刚(如:我校中午和周米不排课,星期二下午不排课等习惯);软约束是指排课过稷中满足更佳但不满足又无妨的约束条件,它们的违反与否往徒与排课实际情况相笑。在三类约束条件之中,前两者是衡熬摊课方案是否切实W行的标准,软约束是衡量l萋漂方案襞劣熬耩准。荬羲;毽分捌翔下:①基本硬约束:1)在同一时间同一学生不能上两门不同的课程;2)在同~时间同一教室不能寂排两门不同的课稷;3)在嗣一时间同一教师不能上两门不同的课程。②硬豹絮;1)上课绞犬爷为单位诗舞(铡斑:上午分l、2犬第);2)星期二下午不排课,星期六、日全天不排课;3)课程的学时在周分布上有~定的规律(例如:每周上3次的课程,一般是星期一、三、旋这三天安排上课镣);15
重痰大学硬士学襞论文3孵麓安镖算法4)某些课程有自己的特定资源(例如:英语专此课程必须有独立的听力系统等等);5)教室空间必须足够大,能够容纳上课(包括禽班)的学生;③软约窳;11班级谍稷袭在周安排上瑟瑟鳖分布均匀;2)一周课袭中每个时间有一定的优度;3)教师不推荐在时间上连续上课;4)教师对上课时间存在一定的喜好(例如:某老师喜欢下午上课等镩)5)班级躐巍上潆建煮尽可笈避。怒要接激簸为理想静谋表,熬躲须注意每震一次镶繇我捧谦擎往时藤攫,学生的最佳用脑时间以及师生在教与学过程中的心理因索等,坚持合理间隔,充分利用教室空间。每个班的每门课程在一周内要间隔开上,让学生分散理解和记忆,因为按照记忆——遗忘规律,一次记忆太多相似的内裙并不能记住,所以,要注意蛙质不司焱,强调个性,才能识率。医既,应该改燹整个接捌,恕那黧个性强静,与众不醚瓣方嚣,巧妙黧醵安摊,班瑟作秀记忆鹣奖壤,胃浚稷姆镳箍嵩学生的学习效率,是一种比较好的摊谍方法。在以往的管理中,传统的排课经验很值得继承和发扬,它反映了教学涌动的特点,遵循了教学规律,具有酱谪的实用性。判定一令漾表是否科学台理,除了继承传统编摊外,还应该按照教学心理学懿基本藩理,辩有效薅闯痰入箍熬记忆特点、舞生懿教学心理特熹耧瀑纛鑫隽戆特点,进行科学豹综合分析,选择鬣优的方案。摊课方案是否最优有下麟的评判标准:①时间间隔大脑对“弹头”和“结尾”的事物识褥最清楚,我们可以运用这个规律来安摊学习懿嚣,毽藏怒褥潆翟安接在歪鬻戆5转分铮内,不要港续主,毒逶当豹潆潮傣怠,以增加“开头”鄹“结尾”,以晓来掇麓学习效果。②时间冗的选择早上是~必中最好的学习时间,人经过一夜的睡眠,紧张的精神得到放松,神经系统的疲惫也随之消失,上午入的思想最集中,容易接受和记忆知识。蔗下午效率会穗慰辫鬣,酝鞋上午戆辩麓俊予下午,教忿,疲器量跨重要帮羧赡静潆程安排在上午+③时间元顺序以每周需隳安排两次课的课稷为例,从星期一到凝期五中选择两天泉进行安排,这两天中可以任意安排两节谍,有银多种安排方式,但不同的安排方式之间
重庆大学硕士学位论文3时间安排算法也是存在优劣差异的,在安排时要选择一个较为合适的时间。3.2人工排课的工程分析和模拟人类思维过程是非常复杂的行为至今仍未能被完全解释,但我们可以按照人类的思维过程来编制计算机程序,从而实现计算机模仿人类的行为。计算机对课表的求解实际上是对人工排课过程的模拟。根据我们学校的实际情况,作如下设定:每日最多上5次课,其中上午2次(第一、二大节),下午2次(第三、四大节),晚上1次(第五大节),如表3.1所示。表3.1一周上课安排表Table3.1Thetimetableforaweek星期一上午第二大节第三大节下午第四大节晚上第五大节第一大节星期二星期三星期四星期五每课次2学时,不分单双周。教学计划中有的课程每周上1次,有的每周上2次,有的每周上3次,我们分别将它们叫做1类、2类和3类课程。举例如下:当前课表如表3.2所示,现在需要将一门3类课C填入其中。表3.2当前课表安排情况T{|ble3.2Thecurrenttimetableforaweek星期一上午第一大节第二大节下午第三大节第四大节星期二星期三星期四星期五晚上第五大节排课人员根据要求,认真分析课表后将课程C填入表中,如表3.3所示:17
重庆大学硕士学位论文3时间安排算法表3.3课程c的一种排法Table3.3OneofthearrangementforcourseC星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节课程C星期二星期三星期四星期五课程C课程C我们知道,3类课在课表中的编排方案有很多种,在众多的方案之中,排课工作人员会记住一些比较成功的典型方案,当开始排3类课程时,他们第一时问所考虑到就是那些典型方案(如表3.4):表3.4课程C的另一种排法Table3AAnotherarrangementforcourseC星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节课程C旱期二星期三课程C星期四星期五瀑程C。一但是表3.4的方案是无法实施的,因为星期五的位置已经排课,这会引起冲突,必须放弃这个方案,然后继续找其它方案,这个过程不断重复,直到找到如表3.3的成功方案。该方案没有时间冲突,而且符合最优时间。分析人工排课的过程,可以得出如下其特点和结论,其特点为:扎无冲突性。按照上述人工排课的步骤,编排的课表不存在冲突,即没有~个教师同时上一门以上课程、一个班级同时上一门以上课程、一个教室同时上一门以上课程的冲突。.b.较好的局部最优搜索能力。人工排课过程中,对于当前的排课课程,在班级课表、教师课表和教室课表中,能够搜索出目前最好的排课时间和教室,即较好的教学效果时间、合理的教室、满足教师的需求等c.缺乏全局最优搜索能力。排课问题属组合优化问题,排课班级、排课课程
重痰大学醺士擎使论文3蜡麓安撰舅法和任课教师的数量较多,所有的谍程都在教师、教室等资源上共享,前期排课与后期的课程安排有着密切的联系,人工排课在局部范围内能够将课程安排在最佳的时间和教巍凝,但在全局范围璧菇不具有这种能力,即前期的排课对于羼期的接漂壤嚣没蠢宠分夔舔诗,霉憩逡成瓷源在整转分繇上熬不平鸯,会逢羧爱蘩{錾的谋程可孬德不合理。结论为:乱方案的选择过程不是按课液的空间顺序,而怒按照方案的优劣顺序选择。b.课表的编排方案具有多样化的特点,可以同时有好几种方案供选撵,最后只是选择了襞貔戆一秘方案露基。c.在摊漾辩除了考虑方案零鸯豹优劣程度之强,述要考虑谋程的娥荔程度等其它因素。d.方案的好坏除了一些公认的规律之外,有些魁童观上的喜好而已。£人工排漾的标准是“可行、☆理’’,一般没有定义最优方案的标准。3.3镰表的不确定性和维会游题根据分析人工排课的过程,灾际上是一种数学上的组合问题,主要依靠约束条件来实现,如果约束条件充分,组合数就唯一被确定,但在实际工作中,随着组合方案数的增加,问题变得十分复杂。我们前面说过课程有l类、2类和3类,为了数学上袭达方便,我{『j将谍类定义如下:1类为x炎,2类为Y类,3类为z类,全蜀鹣漾袋空鞲rl共有5×5=25穆(每溺按星麓~至星麓五诗雾),闲忿产生的组合数如下:X(n)=I‰1Y(n)=C,Z(n)《搿其串n=l,2…。,25扶上面可娃褥出:①如果课类相同(譬如都为每周1次课的x擞),则课表空格越多,相应的编排方案也越多;②如果瀑类越高(譬如每周3次课的z类比每周1次课的x类离),则随课表熬空貉增麓,壤捧方案数迄瀵熬德越侠;③如栗漾裘空格数相两,刚谍类越高,裙应的编摊方案也就越多。编排方索越多,从中选择最优方案时需要的约束条件就越多,求解就越难。如果约束条件不充分,解就可能不是唯一解,而是一个集合,并且各个方案之间的差异将被忽略,这种忽略称为方案优劣差异的融合,藏是这种融合,使得课表
重痰大学硬士学攮论文3嚣重麓安接算法出现不确定性。课表集怒矢量集,计算公式为:F=C。*--m!/(nIx(rn—n)!)其中F为方案数,nl为空间向量数,N为每周的谍次数。计算结果如袭3.5获示:袭3.5课表方案数Nl2345F(m=15)1510545513653003F(m=3m30435406027405142506麸上表可鞋餐蹬:当N=l时,F(m=30是F(m=15)的2倍,N=3时,F(m=30)是F(m=lS)的9倍,但当N=5时,F(m=30)是F(m=15)的47倍。Nl蝴时,Fl=105.N2m5时,F1-----142506;所以,N2是N1的2.5倍,而F2是FI的1357倍。这秘空嬲;惫璧数稍徽增期,或密漂程震次数稍微增宓曩就弓l起课表编攘方案数量急尉增燕鹣凌象,称为‘‘缀合攥盔擘”,在解决深表阕簇辩是无法霞逶“缀会爆炸”的,因此,怎样解决这个问题是课袋编排中一个重骚经务。同时,排课空间向量数少量减少(或者课程周次数少爨减少)会引起组合方案的急剧减少的现象称为“组合塌陷”。上面这两种情况都要想孙法解决。由翦嚣的分辑褥知,课表阀艨实质上是一个组会艘划润题,如果怒找剿浸挠解,必须存懋够戆终束象{孛,餐瓣学部分属于天文藏耱翁潆表竭踅,不爵熊我囊充足的约束条件,而且由于课表方案优劣差异的融合,能够找到的解将会怒~个解的集合,并熙这个集合中所有的解都是可行的。因此,我们必须放弃“绝对最优”解的方案,除了最基本的“教师、学生、教室在任一时间的安排只能出现一次’’的硬性约束条件强,课表只要能满足“W行,合理’’的要求魏行了。受|筵,我雾】霹辍确定诗算蘩‘簿谍饔嶷凌豹死令基标:①课袭怒没有冲突的,是可行的;它表示课袭符合基本的原则骚求,没有无法执行的冲突,不会出现诸如一个教室同时上两门以上的课程的情彤。②课裘鼹青较高的质量;20
重痰大学硕士学像论文3酵鞫蜜捺算法课表的斌量高低根据下面几个标准来评判:11各门谍程在一周之内应间隔安排;动重要的、繁难的课程应安摊在上午1,2节遴纾,次之豹课程安排其它时瘸;3)俸育谍应安排在上午的3、4节或者下午,两鼹体育谋之屡不宣孬安排上谋:4、避免綮难的课程连续上,成间隔和穿插安排;5)对连续的课程安排豹教室不能问隔太远,以方便师生及时到达教室;国实验、童覆等实黢毪漯瑕旋该安撵在下午或浚上进辱;乃对令羽老师盼酶殊要求要器量满足。③课袭中不存在或仅有很少的“漏课”。所谓“漏课”是指因教室安排问题使得某课程没有办法安排教室上课。3。4萎}课阉题的数学模型排课藏瑟楚~令寄约束豹多瓣标健纯霹题,嚣藏撵漾蠲逶貔穰鍪是蠢约束鳆多目标优他横嬲,其中约束条件可以通过约束满足模溅来说明。3.4.1排课问题的优化求解横型假设排课问题中,有n个决策变量参数、k个目标函数和m个约束条件,目标蘧数、约束祭传籁决蓑交量之淘爨缀数关系。刘赫谖翊题的最优纯模型麴下:MaximizeSubjecttoF嚷x两《x>是£x),..。,fk(x)啾)=(el(x),e2(x),...‰(x))9《3.1)(3.2)其中x<xl渤,¨.,xn)∈)('y=(yl,y2'…,yk)∈Y。这里x滏示排课问题的决策向量,x表示决策向凝X形成的决策空间。x的元素x,,X2…。,x赫出影响捧课方寨饯劣的因素的各个变量组成。主要是融闯和教室嚣方嚣熬掰豢,爨翔在薅凌方瓣,踅栗蒋薅舞接瀑凌缝织形式来麓分,爨ll皴安排时间所处的节hi,时段pi、天di釉周次wi等,都W作为决策向量的元索;再例如在教室方丽,教室的类型鹏、襻蕊rq、所在的校区域碣等也都是决策向量的元素。决策向爨的元素个数是变化的,一般来说,随着嗣标向量维数的增加,决策向量的元素个数也增加。由上面可以看出,由于j{}课黢素之间的关联导数了x的维鼗霉零{爨大。终衷条磐《x)反获了接涤蘑题懿壤接娥潮,礁定7决策随爨豹霉行的取值范围。Y表示目标向量y形成的目标空间。维数随实际对乏解问题情况以及课袭评定准则的变化而变化。
重庆大学矮±学鼹论文3黠麓安捧算法3.4.2排课问题的约束满足模型教师集合T--{Tl,T2,...,Tt)班级集合C*{Ci,C2,…Icc)诗翻集会l产{珏,b,…,b)(3.3)(3。4)《3.5)(3.6)(3.7)教室集合舡lRl,R2,…,&'合班集合G=(Gl,G2,...,Gg)一般地,如果教师Ti被指定绦合班集合中的Gi授课,则定义粕=1,否则alj--0;同样,如果教9iliTj被指定给班级ci授课,贝1jb矿l,磷则定义b霉=0。定义礴个需求矩蓐。alla21撑12a22…gk…42,A=(3.8)a西a92…口掣bl{b12…气…%…k◇.劣‰如k钆:上面的A、B矩阵可以确定班缀的合班情况和教师的授课情况,也就怒猩数学豹意义上说明了当前所有的教师麓班级之闻的关系。懿采簇交漂袭土豹王雩筝天数凳d,一天黟节数秀s,骥褥弓|入漂表冬yll痨哟矮薄M§而1X12蔗就…‘d…X2dMs=X21(3,10)"gslXs2…Z括其中Xi3滚承在j’周的第i’节蠢漾,否剡税为空闲·如果按照矩阵A中开课计划进行排课,在课表矩阵中实时记录当前教师、班级和教师的时间段占用情况,则埘得教室安排矩阵№和教师—班级安排缀阵MtXtll—I:…而博鼍21萎22…而“xtnxI|2…xtd尚(3.11)S,
重痰大学颈士学位论文3瓣怒定{嚣算法Xlll2…嚣‘lid五122…Xll2dS12···5'1-Mtc=X|1j2¥21···Xtlsd(3.12)s赶…S2tScl其中M,中xilf-1表示教室Ri在周j’的第i’节已经被占用,否则认为空鬣。M。中苟《一1袭承教师弓绘班级ci豹授课安排时间中有周j’的第i’节,否则认为没有。毒了上甏瓣撬透,裂教努每繇令舞藏(周j’豹第l’蔫)至多安蓑}一次援潆霉以表达为:∑x∥,茎l同理,班级cj谯时间(j’周的第-i,节)至多安排一次J:课可表达为(3.13)∑x∥,’sl对手教室戳凌辩阉≈,羯魏第i一嗲≥楚多安撵一次上漾逡骞xn蟠_l(3.14)(3。15)(3.13)、(3.14)、(3.15)式给出的只是排课问题中最朴素的数学模型,宦们的满足仅仅是保诞丁教师、学生和教庭不发生冲突。其中(3.14)保证每个班级在每个时间最多上一次课的同时也杜绝了当有多个班级参加嗣一次授课时可能襻猩冲突熬现象。网3.1排课算法图Figure3.1Thetimaablingalgorithm
重庆大学硕士学位论文3时间安排算法有了上面的情况介绍,我们可以设计课表的编排方法,其主要分两步,先是对课程进行时间分配,然后对课程进行教室分配,算法见图3.1根据排课算法图可以看到,排课算法的作用就是将无序的原始数据(也就是教学任务)进行一系列加工操作,进而生成有序的最终课表,在这其中包括了两个主要算法:教室安排算法和时间安排算法,正是这两个算法分别把时间和教室的约束加入到教学任务中。从而使生成的课表有效。同时我们看到,基础数据库、排课知识库和策略库都为排课算法提供了有效的策略依据,其中排课知识库和策略库是排课工作人员的长期排课经验的结晶。3.5课表问题中的遗传算法设计课表问题中,遗传算法应用在了两个层面,第一个层面是局部上,基于某一单门课程的时间安排,它的工作是从所有的课节空间中选取近似最优的组合解,我们称这个层面上的问题为局部课表问题。对一门课程找到了近似最优的组合安排方案以后,并不能代表为整套课表找到了近似最优的安排方案,课程安排的先后次序同样决定了整套课表的质量,因此,第二个层面就是基于整套课表,按照怎么的顺序来排课,能够得到一套满意度最大的课表,我们称它为全局课表问题。3.5.1局部课表问题的遗传算法设计:计算公式为:F=Cm"--m!/(nix(m—n)!)其中F为方案数,M为空间向量数,N为每周的课次数表3.6组合数随周课次的变化Table3.6ThecombinationnumberwiththeclasschangeforaweekN12345F(m=25)2530023001265053130对于局部课表问题,就是在每周的课节空间(天数X节次:5x5=25个课节)中,寻找一种合理的、满意度较高的课节组合。表3.6列出了全部组合数。从上表可以看到,当N达到5时,组合数F达到了5x104,这个规模会随着N的增长极度膨胀,在如此庞大的搜索空间中寻求最优解,对于常规方法而言,存
重痰夫学颈圭学经论文3封瓣安撰箨法在着诸多的计算困难,而遗传算法的搜索能力可以解决课表问题,因此,我们引入了遗传算法。①编码(Encoding)绽码方式必缓毙够毽含这转镶慧。垂于漂表超嚣瓣独特缝,采惩砖绫逡传算法中的二遴制编码并不是缀适合,嚣为课表空间是二缭鲍,包含星期和节次,焉一个二进制串很难表示出这两种信息,因此,需要一种新的编码方式来袭豕遗传基因。我们采用了一种叫做布尔缀阵的表示方法来对课表基因进行编码,如表2,这个布尔矩阵袭示对一门课程的一种分配方式。矩降掇坐标为星期,纵嫩标为节次,萁串0凌零没有安簿课程,l凌示安嚣潆程。表3.7谋表染色体编码Table3.7OOOO01O0O0OO0OOChromosomecodingoftimetable1OO0O0OOOOl0O0OOOO0它表示,该门课程安排在了周:第一节、周四第一节和周六第二节。出糍尔矩瘁囊表示豹缓璐空藏与解空瓣怒一一对应豹,任露一耪漾表静舞鬻安接方案繇可以在这个编码空间中找到一个对应。②适应魔函数(FitnessFunction)课表问题中,对一种安排方寨优劣的判定很复杂,其中包含众多来自课程、教师、教室的舰她和要求,一类为规则,另一类为要求。适应度函数的设计是课表露逶邃簧雾浚设诗夔关键,嚣隽它走法象受藤撵瓣遴那么燕擎瓣惩一令凌达式就可以表示,谦表方案的适应度体现在很多方面。大多数缀合优化问题中,适威膨函数都是固定的,但是在课表问题中,固定的适应度函数鼹然是不能适用的,因为随着排课的进行,遗传环境(课表黧间)在不断变化,同样一个个体,放在不阏的环境中,它的适艨程度是不同完全的,甚至稳差缦大,黧魏,磐露设诗一令荚蠢鑫逶应瞧熬适黩发嚣数裁是最关键戆。①适应度溺数中的参数适应度函数中需要包含的参数信息包括:节次优魔a、日组合优度b、带缀合优度c、组合可行性d、分布优化度e、资源优化度f等。这些信息都保存在课表知识库中。
重庆大学硕士学位论文3时间安排算法1)节次优度a节次优度是对一节课“有多好”的量化表示,是大部分同学愿意上这节课的程度,或者上这节课效率的高低。表9则是由一份社会调查得到的节次优度结果,当然这个结果含有一定的人为因素,每个人的评价可能有些差别,这也正是为什么课表千差万别的原因之一。在我们的排课算法中,该信息是由排课人员自己维护的,它可以实时地体现不同人、不同学期的要求。表3.8节次优度Table3.8slot-superio星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节O.95O.85O.650.55O.35星期二0.980.89O.690.590.39星期三0.970.870.67O.57O.37星期四0.940.840.610.5l.031星期五0.92O.820.62O.52O.32节次优度是将大部分同学愿意上这节课的程度,或者上这节课的效率的高低进行量化的结果。上例中,周一第1节课的优度为0.95比较高,表示这节课效率较高。21日组合优度b日组合优度,是日组合方案优劣程度的量化表示。假如某门课一周上两次课,那么哪两天的组合比较好?每周上两次课(一天只能上一次课),五天中所有的两天组合数为C52=10,例如:周一和周二的组合为:表3.9日组合情况一Table3.9Part1incombining-superior-on-dayf星期三目目*———。。。Ⅲ日——.——_l__目_目目H__日目_目日_嘲l零期一l星期二星期四星期五周三和周四的组合为:表3.10日组合情况二Table3.10Part2incombining-superior-on—dayI星期一星期二早期三旱期四星期五圈一对每种组合进行优度判定,例如:周1周2组合(11000)的优度为1.0,周3周
重庆大学硕士学位论文3时间安排算法4组合(00110)的优度为0.8,等等。3)节组合优度C。节组合优度C,表示这两天中的哪种节次组合比较好。在日组合的基础上,进行课次的安排组合。上面的例子中己经确定了每周两次课,假如按照传统的大课(2小节)安排,那么所有的课排组合数应为5x5=25,例如:表3.1l节组合情况一1hble3.11Partlinslot--eombinafion星期一星期二星期三星期四星期五上午第一大节第二大节下午第三大节第四大节晚上第五大节表3.12节组合情况二mfble3.12Part2inslot-eombination星期一星期二星期三星期四星期五上午第一大节第二大节下午第三大节第四大节隧隧翻黼隧晚上第五大节对上面每种组合进行优度判定:第一天的第2大节和第二天的第4大节组合,优度为1.0,第一天的第2大节和第二天的第3大节组合,优度为O.8,等等。4)组合可行度d。组合可行度表示当前的安排是否存在班级或教师的冲突,如:是否有的班级在当前时间已经安排了其它课程。它只有0和1两个取值。5)分布优化度e。分布优化度e是以O~1之间的浮点数来表示的。分布优化度是指当前的安排是否满足课表的一些要求,如难度间隔,文理间隔,以及是否满足上课教师或者课程本身的一些特殊要求等等,它是O~1之间的浮点数,因为事实上,一套课表肯定无法保证全部的难度间隔和文理间隔,因此我们设置分布优化度来表示问隔程度。
重庆大学硕士学位论文3时间安排算法6)资源优化度f资源优化度f也是介于O~1之间的浮点数,它的目的是为了追求排课的第三个目标而设置的,是对付“漏课”的第一道防线。我们在前面介绍过,“漏课”的问题是课表问题中的难点。为了更好的理解资源优化度f,首先,我们来分析一下,由于课程无法安排教室而造成的“漏课”是怎么产生的,这其中的原因有很多种,其中与时间安排有关的原因之一是对有限的某种教室过度集中使用,而造成某个时间该类教室负荷过重,使后面待安排的课程在这个时间无法获得足够的教室选择空间。资源优化度的判定相对复杂一些,它涉及到教室资源分布图的计算,削峰填谷等方面的内容,简单的说就是判定是前的安排否当会导致某一类教室在一个时间的使用过于集中,而其它的时间空闲很多,继而使后面的课程在安排教室资源的时候过度紧张,从而不得不进行教室范围扩展,浪费了本来就很有限的教室资源。在自动排课算法中,资源优化判定是避免出现“漏课”的第一道防线,它就是为了阻止对某一类教室在一个时间过度使用。教室数星期一(第1节)时间图3.2有波峰非均匀的教室资源分布曲线Figure3.2ThedistributingCUI、,eofasymmetricclassroomn№urceswithwavecrest教室资源分布曲线图直观地表示了一种教室(适合多少学生一起上课的教室),在各个时间段的使用分布情况,从这种图上,我们可以看出哪个时间的负荷过重(失去平衡),在排课过程中(而不是排课结束后)及时地发现并进行纠正。事实上,这是一种在安排教室之前就进行的预防手段,它并不能绝对避免“漏课”出现。当“漏课”出现后,我们还会有可选的几个方法来自动称补,这些方法将在后
重庆大学硕士学位论文3时间安排算法面介绍。在图3.2中,在周三出现了非常高的峰值,它导致了后面人数相近的课程在周三没有足够的教室选择余地,而其它时间该类教室却有很多空闲。假如这时有一门课程需要在周三第1节课从该类教室中选择,那么就会出现无法安排的问题,那么系统将会自动降低时间组合优度,转而向其它时间段进行搜索以期避开周三第1节这个时间,如果能找到则可以解决这个问题,可是时间组合优度是会否降低很多呢?是否会有其它冲突产生呢?例如:难度大的课程没有得到较高的时间优度,或者违反了其它常规规则等,这些问题我们都无法保证不出现。因此,通过在排课过程中动态的计算资源分布优度,及时地发现并摒弃这种不合理安排,可以在很大程度上避免“漏课”出现。教室数星期一(第l节)时间图3.3相对平均的教室资源分布曲线Figure3.3ThedistributinggUI"VCofaverageclassroom“∞un:esabsolutely在图3.3中没有明显的波峰和波谷,表示教室的分配比较均匀。类似的课程在任意时间都可以安排,这是比较理想的状态。资源优化度f的计算公式为:仁(T--Max)/(T--Min)其中,T为全部教室总数,Max是组合产生的峰值,MiIl是谷值。当资源分布曲线越趋平缓,即Max与Min越接近的时候,f就越大,最大值为1,出现在Max=Min的时候,即曲线是一条水平线。②适应度函数基于以上参数,我们设置单门课程的课表问题遗传算法的适应度函数如下:F=(Axwl+rb。q1+cxq2)xw2)xdxexf
重庆大学硬圭学爱论文3酵鞠安接簧法其中A袭永当前组合方案的带次优度的平均值,A=((axbIcl)+(axblc2)+(axb2q)+(aXb2c2))/n,公式是以上述的每周两次课为例,其中n表示上课的次数(这里n=2),bl是第一次课的目组合优殿,b2是第二次课的豳组合优度,cI是第一次课豹:箨组合魏度,c2是第二次瀑戆蓼缍合筑度,锤秘琏2袋苯基缓会魏度黟繁缀合钱度所占的投黧,qlI+qfl,嚣vrl秘w2表示节次优度和缀合优度各占的权熏,wl+w2=l;适应皮函数F的最高值为l。③选择操作(Selection)在局部课袭闯题中,我们采用了轮盘赌豹方法来进彳子选择操作,并对此做了撰投夺生境豹羧送。轮鑫赔方法交琢圭是莰蕹蒙特豢罗(MonteCarlo)方法浚谤熬。蒙特卡罗方法,或称计算税随梳模撅方法,蔗一静基于“随梳数”熬计算方法,它的基本思想很早以前就被人们所发现和利用。早在17世纪,人们就知j鳆用事件发生的“频率”,来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率,本世纪40年代电子计算机的出现,特别是近年来离速电子计算机的出现,使褥躅数学方法凌诗算辊上大量、俊速遣模苏这样兹试验藏为霉能。铡如,考虑平瑟上懿一个逡长免l静正方形及箕内部的一个形状零麓煲}l静“图形”,魏谤求澎这个“图形”的面秘睨?蒙特卡罗方法怒这样一种“随机化”的方法:向该正方形“随机地’’投掷M个点,落于“图形”内的点为N,则该“图形”的丽积近似为N;M。露3.4不阉令体戆逶痤痍Figure3.4ThefimcssofdifferentIndividuals轮盘赌方法类似于博彩游戏中的轮盘赌,轮盘被划分为不同比例的区域。这里的比例是根据个体适应度大小分配的,适应度高的个体由于在轮盘中矗攒较大
重痰大学硕士学经论文3辩弱安接算法比例的区域,阁此被选中的概率就犬,得以生存的概洙大,相反,适应殿较低的个体则被淘汰的概率较大。选择算法的过程是随机的程轮盘中投下落在的区域所代表的个体将被选中并得以生存,虫H圈3.4所示。翔嚣瑟奔缓熬,基于夺生境技术夔选择操薛将受瓣予健令搏与父霞令傣逶厅适应度醴:较,如栗父代个体遥应度离,刚复皋l父代个体劐当前子代释群中,否则不复制。前面我们融经讨论过了遗传算法的缺陷,其中一个缺陷是初始种群的不均匀分布。在这爨,为了改进它,我们采用了分区域的初始种群选择,即,将整个解空闯划分或n令嚣域,袭魏纯耪群辩,分裂在每令小区域孛疆瓿选择1/n接个个体,最后将n个小释群合并残橱始耪群,这样产生静静群麓本覆盖了整个熬空阉,保证了初始种群的均匀分布.④交叉擞作(Crossover)课表问题中,每个个体需要遵键的规则是周课次数是固定的,无论怒交叉还是变异都不麓造鹜该怒赠。嚣致,我髑设计豹交叉摄传必须要考虑这个缀索,毙舞矩薄夔交攥髂或者并操终裁蠢无法满足这个魏嚣fl瑟举缆采瘸。我们这熙采用的交叉操作类似乎二迸制串中的单点交叉操作,单点交叉是随机产生一个交义点,然后将两个父个体在交叉点右侧的部分相互交换,从而产生两个不同的乎个体。对于课表问题的矩阵表示,我们将随机交换两个父个体的第r1个‘l’位,箕巾n随规产生,对于繇蠲三课次豹课程,假设n=l,鄹交换父个俸l与父令薅2戆第一令霞进孬交叉缀会残子令体。镶懿:袭3.13父个体1OOeOO1O8OOOOOOlOOO000lOOOO00OO0O00袭3.14父个体20OOOOOlO000eOOOOOl0O0lO§0OOOO00O00
重庆大学硕士学位论文3时间安排算法交叉产生两个子个体:表3.15子个体1Table3.150OO00O100O000O0l0000OOOSonIndividual100lOO0O0OO0表3.16子个体2Table3.16O000O1000O0OOOOO0l00O00SonIndividual20lOO0000O0O两个子个体分别保留了来自父个体的部分特征。⑤变异操作(Mutation)变异操作相对比较简单,由于我们设计的矩阵为布尔矩阵,而且矩阵中的‘l点个数不能变化,因此,我们采取了“1点跳转”的变异方法,即矩阵中的某个‘l'点由原来的位置随机跳动到另外一个一0点上,而原来的‘1’点自动变为‘ot。例如:表3.17父个体Table3.170OOOO1O00OO00O010OOO0OOFatherIndividualO0100O0O00O变异为:表3.18子个体T曲le3.18O10OOOO0OO0O0OO100OOOO0SonIndividualOO10000OOO0
重痰大学硕士掌经论文3孵溺安接舞法3.5.2局部课表问题遗传算法的结束条件假如我们不考虑遗传算法的结束问题,那么遗传算法将无限地执行下去,因为算法本身弗不知道该怎样结束,所以,我们必须设鼹遗传算法的停止谶纯条件。骞三秘较黪懿逅窭逮煲算法戆方式,善竞,当耱瓣墨不毒骞交纯对,羧霹敦决定退出,这黉要一个专门餍来稔凌释群差冥的模块,它耨对任意两个个体进行差异检查。第=种方式是,如果达到了适应度的目标,也可以退出,这需婺适应度函数设嚣的非常好,它基本上能够体现个体的绝对适应度,或者需要缀历一定次数的测试,了解了适应度的情况之后,就可以设鬣翻标适应度。第三,在迭代了一定豹次数袋者说经历了一定数嚣熬“鼗’,之嚣,瑶叛退出。在基予荦门谦程静捧谋算法巾,由于适应度瓣镶与当前遗传环境毒穰灭静关系,不能够纵向进行比较。例如,对于空的课表空间,适应度为O.98的安排方案是最好的,但魑当课表空间已经被占用了很多的时候,适应度为0.8的安排方案是当前环境中最好的,而且是可以被接受的,因此我们不能设置一个统一的目标适应度来衡量。程这里我髓采取了努三秘方式来终止遗传算法,鄯设置一个“代”数,达妥该“鼠”数之嚣,箨壹遽簧避纯,并置取当藏最饶虢n(n由用户鑫蠢镶定)今个体为最终解,之所以取n个最终个体是因为教室安排会对时间安排产嫩回溯调整,可能最优的个体并不能和教意安排很好的合作,因此必须存在多个候选个体,这些会在后面详细介绍。3。5.3全局谍表问题的遗传算法设计经逑鼹帮漾表闫蘧戆算法运移,辩每门谍程我辩舔甏数我鹫一个遥钕袋傥我谋表安排,假是这却无法确保整套谍表就是近似最优的,因为课表空间和教室空间都是一定的,先安排的课程无疑会抢夺最优,后安排的课程则只好选撵次优,这就是优度抢夺的问题,即,无论怎样编排,都不可能使各个课程的安排在优度上绝对平衡。这是课表编排的主要灏难之一,也是慕本艘锋之一。在漂表瀚瑟夔藤弱孛毒蔻条涉及鬟次彦勰题,魄黧先撰燕麦寒懿课纛、先{霎公共谋等,健怒仅仅有这几条嘏则楚远远不够的,蔡中还涉及至4课程对教鲞和时间的要求问题,要求严格的课程威该先排,或者条件姆刻的课程应先排,由于~个学期的课稷很多,所以这些条件很难在排课之前就能够确定,这里我们采用遗传算法来寻找~条近似最优的课稷安排序列。课表闽题属于NP完全问题,它的搜索空阕夔誊渫糕数纛豹瑷麓瑟惫测瀵大,瑟有夔课程撵磺数走(》1)!/2,麴魏凌大的援索空闻需要用遗传算法来解决,下面我们分橱鞠设计在全局课表阔趱中遗传算法的应用。①编码采用路径袭示法。路径表示法是表示旅程对应的簇圆编码最自然,最简单的
重庆大学硕士学经论文3辩溺蜜撵莠法表示方法,窀是把旅程依次经过的城市的顺序记录下来。这种编码方式必须保证编码中不能有重复的因子出现。例如:设置顺序表C*(1,2,3,4,5,6,7,8,9),旅程顺序为5一l一7—8—9—4—6—2—3,用路径表示法就可以直接袭示为:517894623。②选簿撩作帮适应度函数在这里我们仍然采用与局部课表问题的选择操作榴类似的选择策略——基于小生境技术的轮盘赌方法。适应度聪数的设计问题是全鲻漾表闯题中的一个难题,为此,我们采用了一耱霪单一点熬方法,藏是将每一门漾程在弱部安捧貉瑰豹最终适应度避纾警均,由毙来对整令路径进行评价。仅仪~门课程安终褥好,并不能健表整个渫袭安{菲得好,而所肖课程安排得好的话,那么整个课表安排樗就一定好,所以,所有课程适应度的平均值基本可以体现熬套课表的适应度函数。因此,F。(F1+F2+…+Fn)/n,11是种群中课程的门数。③交叉搽侮采用鼹衽袭示黪编璐方式决定了在逮传算法中逡符交叉揉馋生成豹令棒染色体中不允许肖熬复的基因码。这样,基本的遗传算法的交叉操作生成的个体~般就不能满足这~约束条件,在这嫩我们采用顺序交叉。顺序交叉是在1985年由Davis等针对经典的货郎担问题(TravelingSalesmanProblem,TSP翘题)提出豹基予路径表示静颞序交叉操作,它能保密排列菸融合不同捧捌兹蠢澎缝莱蕈元,秀令父令钵交叉懿,逶避选择父个俸l熬一帮分,僳存父个体2中基因码的相对顺序辙成子个体,这样就继承了来自两个父个体的部分特征。例如,对下面两个父个体的袭示,随机的选择两个交叉点“l”Pl:123{4567l89P2:452|1876|粥首先,两个交叉点之闻的中间段保持不变,得到:S1:XXXS2:XXXII45671876xXlXx其中x袭示暂时没有定义基裰码。然囊,诞瑕父令落2软第二令交哭赢嚣始款基嚣褥豹蓑}裂j矮|亭,姿嬲达表遑时,返回袭头继续记录基因码,赢到至《达第二个交叉熙结束,这样就获褥了父个体2从第二个交叉点开始的基因排列顺序:934521876。对于父个体l,融有的基因码为4、5、6、7,将它们从个体2的基因码排列顺序中去掉,得到排列顺降93218,再将这个排列顺序复制给父个体l,复制起点也是从籀二个交叉点开始,以此决定
重庆大学硕士学位论文3时间安排算法子个体1对应位置的未知码x,这样子个体1生成为:S1:218456793调换父个体l和2的顺序,同样可以生成子个体2S2:345187692④变异操作变异操作有很多种适用于顺序表达法,比如反转变异、插入变异、移位变异等等。这里我们使用反转变异。反转变异是在染色体上随机地选择两点,并将两点之间的子串反转:123456789一1236547893.5.4全局课表问题遗传算法的问题和改进①染色体编码过长如果单纯地把课表问题简化成TSP问题,会产生一个很大的问题,一个学期的全部课程有1000多门,如果把它们当作一个整体看待,每条染色体基因将有1000多位,虽然有的理论认为编码应该符合实际变化,但是这样庞大冗长的编码表示,违反了编码灵活的原则,而且给理解和操作都带来了困难。这个问题的解决方案是划分子群体。事实上,仔细观察之后可以发现,一个学期的课程中,各个系之间存在着很强的独立性(除少数的公共课以外,而这些少数的公共课程具有最高的优先级,他们并不应该参与普通个体的选拔),每个系的课程参与的教师、班级和教室往往是相互独立的,不同系的课程之间并不存在优度抢夺。而且单个系在一个学期中的课程在20门以内,这样的基因编码就合理很多。因此,我们采取的解决方法是,将种群分割成不同的子种群,遗传算法分别在各个子种群中独立的进化,各个子种群之间不进行任何通信,当各个子种群都已经搜索到了局部近似最优的个体,然后在子种群之间进行比较和合并,选取出全局最优的个体。这种方法恰恰发挥了遗传算法的并行性优势。②适应度函数计算量过大全局课表问题中遗传算法的另一个问题是适应度函数的计算费时太大,假如一个子种群中包含20门课程,那么对于任一个体,计算其适应度需要执行20次局部遗传算法,这种适应度计算方法需要的计算量过大,会影响整个算法的运行效率,目前我们能够采用的缓解方法是采用并行遗传算法的思想。并行遗传算法的实现方案大致有三种:1)主从式(Master-SlaveModel)在这种模型下,并行系统分成一个主进程和若干个从进程.主进程监控整个染色体种群,并荃于全局统计执行选择操作,各个从进程接受来自主处理器的个体进行重组交叉和变异,产生新一代个体,并计算其适应度,再把计算结果传给主
重庆大学硕士学位论文3时间安排算法进程。这种模型在适应度计算很费时并且远远超过通信时间的情况下才有效,否则通信时间超过计算时间,反而会降低速度。而且这种方法要求有进程同步机制,这就会导致主进程忙而子进程闲或者相反,引起负载不平衡,效率不高。2)分布式(DistributedGeneticAlgodthms,DOA)这种方式是将种群分成若干个子群并分配给各自对应的进程,每个进程不仅独立计算适应度,而且独立进行选择,重组交叉和变异操作,并定期地相互传送适应度最好的个体,从而加快满足终止条件的要求。分布式遗传算法是目前采用最多的并行遗传算法。3)分散型(Fine.GrainedModel)分散型遗传算法是为种群中的每一个个体分配一个进程,每个进程进行适应度计算,而选择、重组交叉和变异的操作仅在与相邻的一个进程之间传递个体中进行。我们最后采用了分布式的并行遗传算法来解决适应度计算量过大这个问题。将种群划分成相互独立并且相差较大的若干个子群,每个子群中都独立的进行选择、交叉、变异等操作,达到一定代数之后,相互之间进行最优个体交换,以达到全局最优收敛。3.5.5全局课表问题遗传算法的结束条件图3.5遗传算法停止条件Figure3.5StopconditionofGeneticAlgorithm
重庆大学硬±学拯论文3黠鹚蜜罄算法在局部渫表问题中,遗传算法的结束条件是达到了进化的代数,就停止算法,那是因为局部课袭问题的适应度澈法纵向的进行比较,因而无法设置一个统一的适应度尺度来衡量是否可以停止遗传。在全是潆凌窝惩孛,事实上麓嚣耱方法罄可以掺麓筹法续震愆条{譬。我秘这里采爝了两荦孛方式相结合的方法,先进行适应度条馋橡查,如果找到了达剿指定适应度的个体,则停止进化,否则,如果进化代数爵经超过了指定的代数限制,但还没有找到符合适应度要求的个体,则也停止进化,从最后一代种群中选择最优个体作为最艏的解,如图3.5所承。3.6算法褪絮从宏观上看,我们所设计的谍袭问题解决方案怒两层的遗传算法嵌套运行,内层遗传算法的运行结果传递给外层遗传算法作为邋皮度函数的一部分,外层遗传算法以此为依据来搜索近似最优解。图3.6就体现了整个算法结构。
重庆大学硕士学位论文3时间安排算法图3.6遗传算法流程图Figure3.6FlowchartofGeneticAlgorithm
重褒大学硕士学缱论文4教室安搀算法4教室安排算法教室安攥舞法豹基豹是为谍糕选择一个教室,它是簿渫软传豹一令獯点,这个算法静优劣楚整个簿谋算法成功豹一今关毽,因为瓣翡高校课表安舞}的~个最突出的矛盾怒不断增长的学生入数和有限的教室资源之间的矛盾。很多jj}谍软件在这个问题上都没有找到很好的解决方法,出现太多光法安排教室的课程,是造成“漏课”现象的最重要的一个因索。如何有效的安排使用这些固定的教室资源,在技术上是一令鼹题,嚣在实际应嬲巾其有缀重要匏意义。4.1教室安排流程教室安排算法的流程图如图4.1所示,其中n为优先教室的个数。教室安排算法的输入数据包耩;课程c、上课人数g、课程要求和教窳类型h。首先,麸知识黪K中取出当前谖程豹优先教室表R,默认情况下,k书所包含的教室集合荛溧戆掰藩系掰在熬系褛教室,蕉户可颤菇漾鹱缝套一个更漆确豹范围。在这个教室范潮中,对教室座位数燕和教室类型避彳予过滤,得出符合当瀚谍程要求的更小的教勰范围。其中教室魔位数e:g+Min_<e_<g+Max其中M如j鞫Max分别是座缀数多于人数的下限觏上限,系统默认20釉50,著霉更改维护。这辩蔟懿教室表甏孛黪每令教室箨熊壤壤骜会当蘸漾蘸鹣簧求,当T口中的教燕没有可利用的时候,系统将首先采用教室扩展来解决这个觏遂。这里的扩臌包括两步,首先对教室座位数的扩展,即对上面式子中的Mm和Max之间的范围进行扩大,使符含器求的教室范围增犬,从这个扩展后的教室范围中寻找目标教室.第2步是对教窳类型的扩展,即,爱求酱通教室的课瑕可以扩震弱多媒薅教嶷,或者授影教室,这嚣弹霉强健嚣据数蹇蓬垂壤太,毽怒攀实主往往多媒体教室和投影教室数量黧绷有限,因j鞋:,势举攘荐使用第二静扩越。在两种扩腰都无法找到符合隳求的目标教室的时候,“漏课”问题就出现了,下面将讨论如何解决“漏课”问题。
重庆夫学硕圭学靛论文4教室安簿算法图4.1Figure4.1教室安排算法的流稷圈Flowchartofclassroom-arrangedalgorithra4.2“漏课”翡三种解决算法前面已经介绍了“漏课”问题,以及这个问题的产缴原因。如果理论上学校的教室资源是可以满足教学任务的要求的话,那么则一定存在一种课表解决方案可以没有‘‘漏课”阿题,可是,追求绝对没有“漏课”闽题将逃成算法的无限期运行,或者40
重痰大学硬士学缎论文4教室安接算法死循环产生,湖此,我们放弃绝对追求,而追求力争将“漏课”问题减少到鼹低限度。排课算法中,我们运用了3种算法来避免和排除‘漏课”问题,第一种辣法运用在对间安排冀法中,也就是说,农时阅安排时期则己缀野始考虑教室安排的情况。算法一:旋懿蠲嚣安萎}过程巾,尽量遗受嚣要类秘教室熬漂程过爱集串在菜个时闻,这裁怒在时闻安捧算法巾笑子资源分布优纯度判定部分的内容。这令算法首先能够从底层避免“漏课”,它属于一种预防手段。由于算法一仅仅是一种预防乎段,它只能够降低“漏课”出现的几率,似并不能够阻止“漏课”阅题的出现。例如,即使时间分布很均匀,可是对于那些本来就很有羧熬特豫教囊,仍然可能由予握骜馒爰,瑟导致那壁必须壤习它静漂覆炙浚安搀教室。当出现这样静情况的时媛,我lfj采蘑7“强溺”髑熬筋方式来解决这个闯蘧,以求尽量满足课程对教室的要求。排课的过程也是对有限资源使用的过程,开始的时候资源相对丰富,可以择“最优”进行安排,随着排课的进行,资源慢慢变得很紧张,可选择的余地巍越来越小,当出瑷茏浃安接熬“死蹙”的对候,摊漂过程遇至l了簿薅,这个漳碍势嚣一定是因为教室资源没窍了造戒懿,露瑟多建是垂手“美键”爨潦羧提兹使矮7,这嚣重候,向前寻找可以将“关键”资源释放的地方,撤销其现有蜜排,以非关键资源替代关键资源,那么前顾遇到的障碍则会得到排除。这个过程就是我们所采用的“回溯”调整,简单的说,“阐溯”就是当匹配遇到障碍的时候,撤销以前的决定,重新进杼~次新豹选择。由予摊课中豹试探具有一定的盲目性,产生不合理安排是不可避兔的,瑟“强溺”能够楚系统壳骚这令袋杰,嚣瑟“瑟溯’’在这受馨鬻重簧,是鼹狭翊遴豹一个重要手段。算法二和算法三分别是回溯调整的两种不同方式。算法--宅回溯改变当前课稷融经确定了的时间安排,来寻找可满足教室要求的时间组含,这个改变有可能会降低时间组合的优殿,但是如果优度降低范围在认可黥范滋叛疼,那么班较小熬拜尊藏爨度来换取教窳安接上豹空闫,媳鼹霹取豹一穗方案。算法二将从时间排课算法所产生的n个候选个体(时间分配方案)中,按照适应度由大Nd,的顺序对个体进行试撵,这里的试探不仅黉进行组合可行性、分布优化度、资源优化度的判定,还要谶行当前的时间组合怒否能够进行教室蜜排的判定,只有能够进行教室安排的个体才是符合要求的搜索结果。致交爨阙缀会葳造成熬霹蠲臻发下簿是这静算法瓣一令弊囊,一般壤滋下我们只允许较小瓣优度下降,当下降游常大的时候,蹩个谍表的质量也将下降很多。因此,对算法麓,我们加入了一个优度降低限制参数DecLimit,它将监视每次时间组合改变所造成的优度降低是荫在限制之内,如果一旦超过该限制,则放弃算法二。41
重庆大学硕士学位论文4教室安排算法图4.2回溯算法二流程图Figure4.2FlowchartofBacktrackingalgorithmic.-2算法二的流程图如图4.2所示。按照算法二的思路,较大的时间优度往往不能够获得足够的教室可安排空间,回溯的成功率则不会很高,可是如果保证该算法一定回溯成功,则必定会造成时间组合的优度过低,而导致课表质量的下降,因此,我们准备了第三个算法。算法三也是一种“回溯”方式,它将在算法二仍然无法成功的基础上触发,与算法二不同的是,它的回溯对象不是当前课程的时间安排,而是其它已排课程,调整其时间或者教室安排。流程图如图13.算法三有两种“回溯”算法,第一种是回溯调整已排课程的教室安排,第二种是回溯调整已排课程的时间安排。当出现“漏课”的时候,暂时保留当前课程的时间安排,而向前回溯己排课程,
重庆夫学硕士学髓论文4教室蜜攘算法查找可以进行很小调整则能满足当前课程教室要求的已排课程。第一步,计算调整目标课程集合。要搜索娃:鞠当前课程在当前辩间具有冲突交集的嬲标课程集合,该集合中的谖程辑占矮熬教室郝篷含在当蠢萋漾毽弱霞先教室集会巾,繇改交这些潆耧懿安接受4会改变当前课程静安排空闯,虢有可能会产生可利用豹教室。这个算法就楚在目标课程集会中寻找--f-]课程,改变它的安排(时间或者教室),而使当前谍程可以在不改变时间安排的情况下获得W用教室。第二步,鲇每门目标课程计舞“波及范围”在这里,势苓是蓬辊熬获己接涤程孛选择一门谖凝※终镶整,嚣是蔹鬃一个计算“波及范丽”静佶值丞数ff镭饿丞数f为每门已稀谍翟计算出一个俊,它代表若改变该课程的安排整套课表中将会有多少门课程受到波及影响,他们都宵可能要作出相应的改变。第三步,依“波及范围”从小黧犬的顺序对目标课耩避行试探调整。一般壤况下,调整菜一门楣荚漾程之磊,裁链够鳞决“瀑苗P’,毽是在莱焦情琵下,需要霹辩谖整-f-j甚至更多瓣谍程,才可敬“挪懑”一个可震教室空阕。继篷丞数对多于两门课程的计算为:f(el,c2)=f(cO+f(c9-O(c,c2)其中函数O(el,吩为课程el和c2之间波及范围的激叠部分。回溯的原则是,依次选择波及范围最小的课程进行试探调整,直到调熬成功或者所有嚣栎谦程全都试探完毕为止。由予调熬嚣标谋程耱辩麓缀念会雩|莛嚣闼霞褒瓣鬻低,因筵,冀法将营先试图调整目标课程的教室,来寻找W安排空间。每次试阁调整都检查是否可以满足当前课程的教黧安排,如果能,则玛上退出,进入第四步。如果在搜索究全部目标课程后,发现仅调整教室无法满足要求,那么算法将从头开始进行调熬时间安接的试探,这~步与算法二相似,瞬样要进行时闯优璇降低限度的检查,一个原翔是,课程懿溪整凌不盎诲辩窝缀会饯度降低虱霜产瑟求戆嚣瘦疆下。第四步,对由第三步产生的W调整目标课程避行调整,同时对当前谍程进行教室安排。
重庆大学磋七学技论文4教室安撵舞法强4.3靼溯算法三滚程强Figure4.3FlowchaltofBacktrackingalgorithmic·3
本文发布于:2024-02-26 15:35:15,感谢您对本站的认可!
本文链接:https://www.wtabcd.cn/zhishi/a/170893291551577.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文word下载地址:高校自动排课系统的算法研究与实现.doc
本文 PDF 下载地址:高校自动排课系统的算法研究与实现.pdf
留言与评论(共有 0 条评论) |