改进蜜蜂交配算法及其在排课问题中应用 50页

DissertationSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofComputerTechnologyIMPROVEDHONEY-BEEMATINGOPTIMIZATIONALGORITHMFORCOURSETIMETABLINGPROBLEMSByLiangLiyeSupervisor:Prof.GuJunhuaNovember2012 原创性声明本人郑重声明：所呈交的学位论文,是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：日期：关于学位论文版权使用授权的说明本人完全了解河北工业大学关于收集、保存、使用学位论文的规定。同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：日期：导师签名：日期： 河北工业大学硕士学位论文改进的蜜蜂交配算法及其在排课问题中的应用摘要蜜蜂交配算法（Honey-beeMatingOptimizationAlgorithm）是由Abass于2001年提出的一类仿生优化算法，由于其基本原理简单、易于与其它算法相结合，因此得到了众多学者的关注和认同，在旅行商、函数优化、聚类问题等多个领域得到了广泛的应用。排课是学校教学管理中十分重要而且又相当复杂的管理工作之一，传统的排课方式效率较低，难以做到公平、公正，因此，研究出稳定、高效、智能的排课方法具有一定的理论意义与应用价值。本文改进了标准蜜蜂交配算法，并在排课问题方面进行了应用，主要工作如下：首先，针对标准蜜蜂交配算法中蜂群多样性不足、算法过早收敛的现象，进行了改进。通过末尾淘汰机制对雄峰个体进行替换，提升了蜂群的整体质量。在工蜂搜索方面，采用双邻域的爬山算法，通过两种邻域并集的方式寻求求解空间中的最优解。改进算法扩大了解的搜索空间，增加了蜂群的多样性，有效缓解了早熟现象的发生，提高了算法解的精度。其次，在算法求解过程中，给出了针对实数编码方式的交叉及变异算子。基于优势基因的交叉算子增大了交叉的信息量，整合了父代个体的优良基因，使子代个体的质量提到了大幅度提升，加快了算法的收敛速度。并且肯配链变异算子通过构建肯配链维护了解的可行性，减少了算法的运行时间。最后，分析了影响排课问题的主要因素、约束条件，构建了完整的排课模型，并利用改进后的蜜蜂交配算法进行求解。通过实验对比，证明了改进算法的有效性。在此基础上，设计开发了排课系统，减轻了教务工作者的负担。关键词：蜜蜂交配算法，基于优势基因的交叉算子，肯配链变异算子，排课问题i 改进的蜜蜂交配算法及其在排课问题中的应用IMPROVEDHONEY-BEEMATINGOPTIMIZATIONALGORITHMFORCOURSETIMETABLINGPROBLEMSABSTRACTHoney-beeMatingOptimization（HBMO）wasoriginallyintroducedbyabassin2001.Becauseofitsbasicprinciplesimpleandeasycombiningwithotheralgorithm.Ithasbeenattractingmoreandmoreattention.ItisusedinmanyfieldssuchasTSP、functionoptimization、clusterandotherappliedfields.Arrangingcoursestructureisessentialinacademicadministrationofuniversity,likewiseitisacomplicatedmanagementtask.Howeverthetraditionalcurriculumarrangementwayislowefficiencyandunfair.Therefore,ithasgreattheoteticalvalueandapplicationvaluetoresearchthestablehighintelligentcurriculumarrangementmethod.Thepaperisaimedatimprovingoriginalhoney-beematingoptimizationandusingtheimprovedalgorithmtosolvecoursetimetablingproblem.Themainresearchworkscanconcludeasfollows:First,duetothedroneofHBMOhasn"tchangeintheiterationprocessandtheworker"sexplorationabilityisinfficient,thecolony"sdiversityisdisappearandthealgorithmhasapoorperformanceofglobal.AnimprovedHBMOisproposedwhereusethebroodtoreplacethepeakestdroneandapplydoubleneighborhoodlocalsearchstrategy.theimprovedalgorithmeffectivellyavoidtheoccurenceofprematurephnomenonandimprovedtheprecisionofsolution.Secondly,givesthewayofrealnumbercodingforcrossoveroperatorandmutationoperator.thenewcrossoveroperatormixturetheparentsadvantagegene,produceamoreexcellentprogenyindividuals,acceleratethealgorithmconvergence.Inthemutationoperatorintroduceskemptchain,reducetherunningtimeThirdly,analyzedthemainfactorswhichinfluencethecurriculumarrangementquality.Otherwise,constructedcoursetimetablemodelandappliedtheimprovedbeesmatingalgorithmtosolvecoursetimetablingproblem.Experimentsuponsochabenchmarkshowthat,theimprovedHBMOismoreefficienttosolvethetimetablingproblemwithhigherglobalsuccessiverateandaccuracy.Atlast,designanddevelopcurriculumarrangementsystem.KEYWORDS:honey-beematingoptimization,baseonadvantagegenecrossover,kemptchainmutation,coursetimetablingii 河北工业大学硕士学位论文目录第一章绪论......................................................................................................................................1§1-1课题研究背景及意义.........................................................................................................................1§1-2国内外研究现状.................................................................................................................................21-2-1蜜蜂交配算法国内外发展现状......................................................................................................21-2-2排课问题国内外发展现状..............................................................................................................3§1-3论文的研究内容及组织结构.............................................................................................................31-3-1论文的研究内容..............................................................................................................................31-3-2论文的组织结构..............................................................................................................................4第二章基本蜜蜂交配算法的研究...........................................................................................5§2-1基本的蜜蜂交配算法.........................................................................................................................52-1-1基本蜜蜂交配算法理论介绍..........................................................................................................52-1-2基本蜜蜂交配算法描述..................................................................................................................52-1-3基本蜜蜂交配算法的实现步骤......................................................................................................8§2-2常见的改进蜜蜂交配算法概述.........................................................................................................92-2-1自组织蜜蜂交配算法......................................................................................................................92-2-2多种速度变化模式的蜜蜂交配算法............................................................................................102-2-3混合蜜蜂交配算法.........................................................................................................................112-2-4各种改进算法的比较.....................................................................................................................11§2-3蜜蜂交配算法与其它仿生算法的对比............................................................................................112-3-1共同点.............................................................................................................................................112-3-2不同点............................................................................................................................................12§2-4基本的蜜蜂交配算法缺陷分析.......................................................................................................13§2-5本章小结...........................................................................................................................................13第三章改进的蜜蜂交配算法....................................................................................................14§3-1改进算法的基本原理.......................................................................................................................14§3-2基本算子的改进...............................................................................................................................153-2-1基于优势基因的交叉算子............................................................................................................153-2-2肯配链变异算子............................................................................................................................163-2-3双邻域工蜂搜索算子....................................................................................................................17§3-3改进的蜜蜂交配算法的实现步骤...................................................................................................18§3-4本章小结...........................................................................................................................................20第四章改进的蜜蜂交配算法在排课问题中的研究....................................................21§4-1排课问题概述...................................................................................................................................21§4-2排课问题要素...................................................................................................................................21§4-3排课约束条件及数学模型...............................................................................................................22iii 改进的蜜蜂交配算法及其在排课问题中的应用4-3-1排课问题中的约束条件................................................................................................................224-3-2排课问题的数学模型....................................................................................................................22§4-4基于改进的蜜蜂交配算法的排课问题研究...................................................................................254-4-1基因编码及染色体的构造............................................................................................................254-4-2初始蜂群的产生............................................................................................................................264-4-3改进算子的应用............................................................................................................................27§4-5实验比较...........................................................................................................................................284-5-1实验环境及实验数据源................................................................................................................284-5-2实验结果........................................................................................................................................294-5-3算法性能分析................................................................................................................................30§4-6本章小结...........................................................................................................................................30第五章排课系统的设计与实现....................................................................................................31§5-1排课系统的设计...............................................................................................................................315-1-1系统总体框架设计........................................................................................................................315-1-2系统数据库设计............................................................................................................................32§5-2排课系统的实现...............................................................................................................................345-2-1开发环境........................................................................................................................................345-2-2系统主要模块的实现....................................................................................................................35§5-3本章小结...........................................................................................................................................38第六章总结与展望.........................................................................................................................39§6-1论文总结...........................................................................................................................................39§6-2论文展望...........................................................................................................................................39参考文献....................................................................................................................................................40致谢............................................................................................................................................................43攻读学位期间论文发表情况............................................................................................................44iv 河北工业大学硕士学位论文第一章绪论§1-1课题研究背景及意义组合优化理论是近二十年来运筹学最活跃的分支之一。所研究的问题是在现有满足各种约束条件的多个备选方案中寻求最优方案。由于它在解决计算机科学、计算生物学、物流和供应链管理等新兴领域中困难问题方面的成功，在过去的二十年里取得了巨大的发展。但是，随着求解问题规模的不断扩大，在时间复杂度及空间复杂度方面都呈现出指数级增长，无法在合理的时间范围内使用常规方法找出全局最优解。人们迫切的希望借助一些近似化算法解决这一问题，因此，研究开发出高效的优化算法解决大规模组合优化问题成为众多学者的研究目标。一些新型的用于求解复杂问题的优化算法（如遗传算法、蚁群算法、粒子群算法）得到了迅速发展[1]，这些算法摆脱了经典逻辑计算的束缚，通过模拟自然界中生物群体的自组织行为来解决实际的优化问题。由于这些算法来源于人们对大自然运行规律及具体问题经验、规则的总结，因此，有些专家将此类算法统称为启发式优化算法。蜜蜂交配算法（marriageinhoney-beesoptimization，简称HBMO）是由Abbass于2001年提出的一[2]种新型启发式群集智能优化算法。该算法源于对蜂群交配行为的研究，其基本原理可以概括描述为：蜂皇以特定的概率与搜索空间中的雄峰进行交配并产生受精卵，工蜂对新产生的受精卵进行培育，使其发展为新一代的蜂皇。蜂皇经过不断进化最终得到问题的近似最优解。蜜蜂交配算法利用蜜蜂在交配进化过程中的相互协作以及优胜劣汰规则来求解大规模的组合优化问题，为人们解决NP完全问题提供了一种有效的新途径。目前蜜蜂交配算法得到了越来越多学者的关注，逐步成为国际上新的研究热点。由于其在求解非线性、非连续、多峰值等较为复杂的优化问题的突出表现，己被应用于水库操作优化、生产调度（Jobshopscheduling）、随机动态规划（stochasticdynamicprogamming）、旅行商（Tsp）以及函数优化等各种科学与工程领域，大量的实际应用也证明了其有效性。虽然它被广泛应用于求解实际问题，但是，蜜蜂交配算法在理论基础以及应用推广方面仍然存在着一些不足有待研究与解决。当蜜蜂交配算法用于求解复杂优化问题时，常常会发生早熟现象，即算法在尚未找到全局最优解之前就已经汇聚为一点停滞不前。这些收敛点可能是待求解问题的局部极值点，也有可能是局部极值点附近某个临域所包含的点。早熟收敛会导致算法不能收敛至全局最优点，因而对蜜蜂交配算法早熟现象的研究可以为算法的改进提供重要的理论基础。此外，蜜蜂交配算法多采用二进制编码方式，这种编码方式相对较为抽象，不利于算法的进一步推广，因此，研究出针对实数编码的蜜蜂交配算法对于算法的发展将起到推动作用。高等院校作为传播科学文化知识的主要媒介，其重要性不言而喻。而高校对学生的培养则是通过开展各种教学活动来完成的。课程表是指导教学活动顺利展开的重要依据，一张高效的课表不仅可以缓解1 改进的蜜蜂交配算法及其在排课问题中的应用学生、教师、课程三者之间的矛盾，也可以体现出对学校公共资源的合理分配。课表编排是一项相当复杂的工作，它具有规模大、涉及因素多等特性。传统的手工排课方式，不仅在排课效率上难以满足现有要求，而且由于人为因素的影响，课表具有一定的随机性，难以做到公平、公正。利用计算机程序进行自动排课，不但能够减轻教务人员的工作负担，提高工作效率，而且能够更为合理、有效的整合各种教学资源，促使学校的教学活动及其它相关工作有序、规范地进行。排课问题就其实质而言是一个非线性的、有约束的、多目标的组合优化问题，早在上个世纪70年代就已经被证明是一种NP完全问题，对于这一问题，人们将一些解决NP完全问题的典型算法如遗传算法、蚁群算法、粒子群算法、禁忌搜索算法应用其中，取得了一定的成果，但是由于这些算法本身的缺陷使得计算机智能排课的效果并不理想。迄今为止，许多实际的课表编排工作仍然是以手工为主，计算机为辅的形式展开的。所以，研究出高效、智能、稳定的排课方法仍然具有重要意义。综上所述，本课题具有重要的实用价值和理论意义。§1-2国内外研究现状1-2-1蜜蜂交配算法国内外发展现状蜜蜂交配算法概念简单、易于实现，收敛效果好，引起了国际上众多学者的广泛关注和研究。目前，对蜜蜂交配算法的研究主要集中在两个方面：改进算法的研究以及算法的应用。1）改进算法的研究方面：2009年TaherNiknam将粒子群算法与蜜蜂交配算法相结合应用于多目标[3]配电网重构问题。这种改进方法将粒子群算法中的最优个体引入到蜜蜂交配算法中，提高了初始解的质量。但是，两种算法并行执行的方式造成算法的运行时间难以忍受。2011年YannisMarinakis,MagdaleneMarinaki,GeorgiosDounias在其名为《Honeybeesmatingoptimizationalgorithmforthe[4]Euclideantravelingsalesproblem》的论文中提出了一种具有自适应记忆功能的交叉操作。在这种交叉操作中，算法将依据一定的比例从蜂皇、雄蜂以及记忆列表中选择两个个体进行交叉。这种改进方式提高了子代个体的多样性。但是，记忆列表的建立和维护将耗费大量的系统资源。2012年JavadOlamaei[5]等人提出了改进的蜜蜂交配算法（MHBMO），在MHBMO算法中，应用了多种工蜂搜索算子，在迭代过程中依据这些算子对子代的改进程度选择应用，这样做有效地减少了无用的局部搜索，减少了不必要的消耗。同年，AritThammano和PatcharawadeePoolsamran提出了自组织蜜蜂交配算法（SMBO）[6][7]，在该算法中通过对问题空间的划分将蜂群一分为多，利用多蜂群的迭代及交叉寻求全局最优解。[8]2）算法的实际应用方面：2006年Chang应用蜜蜂交配算法求解随机动态规划问题；2007年，[9]Curkovic等人用HBMO引导移动机器人壁障；2008年Amiri、Fathian等人将HBMO应用于聚类问题[10][11][12]；2009年Haddad、Afshar等人应用HBMO求解非凸水资源，2010年Ming-HuwiHorng等人[13]将蜜蜂交配算法与参数蛇模型相结合用于求解动轮廓模型，较好的完成了分段轮廓的搜索；同年[14]Magdalene在金融分类中应用了HBMO；2012年NasserR.Sabar将基本的蜜蜂交配算法应用到排课[15]问题中，但是其过于简单的交叉、变异及局部搜索机制使得排课效果并不是十分理想。与国外相比，国内对蜜蜂交配算法的研究相对比较少。2008年北京理工大学的杨晨光、陈杰、涂2 河北工业大学硕士学位论文[16]序彦在交配概率、速度和能量参数方面对标准蜜蜂交配算法进行了改进，并将其应用于地面防空武[17]器组网系统优化布阵。2010年杨进、马林在《解决复杂优化问题的一个有效工具——蜂群优化算法》一文中对蜜蜂交配算法进行了介绍。2011年张超群、邓建国等人对蜜蜂交配算法的基本原理和缺陷进[18]行了分析。1-2-2排课问题国内外发展现状从20世纪50年代末期，国际上就开始有学者对排课问题的进行研究。1962年，C.C.Gotlieb教授[19]发表了一篇关于课程表构建问题的文章，他在文章中对课程表问题进行了形式化描述，提出了排课问题的数学模型。到了上世纪70年代，另一名学者S.Even发表了一篇关于时间表和多物流复杂性的文[20]章，该文首次证明了课表问题属于NP完全问题，把排课问题提高到理论高度。由于NP完全问题难以找到多项式算法，若采用穷举法寻找答案，当问题的规模增大时，解的数目呈指数函数增长，在有限的时间内难以求出最优解。随着排课理论的完善，人们不再将研究重点放在理论研讨上，而是更多的转向实际应用角度。这使得上世纪80年代的排课系统缺乏普遍的适用性。进入上世纪90年代，Burke等人提出了一种图着色的方法，他们将课表问题抽象为邻接区域的图着色问题，但是由于图着色问题本身就难以求解，所以实验结果并不理想。到了二十一世纪，能够得到较好解的近似算法的研究得到了越来越多的重视，出现了一系列智能优化算法，如遗传算法、粒子群算法、蚂蚁算法、模拟退火以及禁忌搜索等。这些智能优化算法成功应用于诸多领域，排课问题的研究也随着这些算法的提出展现出了崭新面貌，至今仍然存在巨大的发展潜力。国内对排课问题的研究相对较晚，直到1984年林漳希、林尧瑞在清华大学学报的自然科学版上发[21]表了课表编排问题的研究结果，国内的各个高校才对课表编排问题展开大量的研究，先后推出了各种版本的排课系统，如清华大学UTPS自动排课系统、浙江大学的现代教学管理信息系统、山西大学推出的基于知识推理的排课系统等。但是，国内现有的排课软件都不是十分成熟，大多依然需要人工辅助，排课智能性不足。§1-3论文的研究内容及组织结构1-3-1论文的研究内容本文对蜜蜂交配算法进行了深入的研究和改进，并将改进后的算法应用于排课系统，主要进行了以下几个方面的工作：首先，深入研究了蜜蜂交配算法的基本理论、算法流程，总结了常见的改进算法的基本原理并对各种改进算法进行了比较。对蜜蜂交配算法与其它仿生类算法进行了对比分析。概括归纳了基本蜜蜂交配算法的主要缺陷。其次，对改进算法的基本思路进行了介绍，详细阐述了改进算法的关键技术。提出了基于优势基因的交叉算子，并对交叉算子的基本执行步骤进行了较为细致的说明；给出了肯配链变异算子的构建过程，3 改进的蜜蜂交配算法及其在排课问题中的应用详细讲解了双邻域爬山算法的执行过程。再次，分析了影响排课问题的主要因素，构建了排课的数学问题，运用改进的蜜蜂交配解决了排课问题，通过实验对比分析，证明了改进算法的有效性。最后，对排课系统的的设计与实现进行了详细的阐述，展示了系统的主要界面，介绍了系统的主要功能。1-3-2论文的组织结构全文共分为六章，其具体的结构如下:第一章绪论。主要阐述了该课题的研究背景及意义，蜜蜂交配算法及排课问题的国内外研究现状。第二章蜜蜂交配算法的研究。首先较为系统地分析了蜜蜂交配算法的基本理论，总结了一些常见的改进算法的基本原理，对各种改进算法进行了比较。然后，将蜜蜂交配与常见的仿生算法进行了对比分析，概括了蜜蜂交配算法的不足。第三章蜜蜂交配算法的改进。首先提出了改进的思路，然后详细说明了改进算法中基本算子的改进。最后，介绍了改进算法的具体实现步骤及主要流程。第四章改进的蜜蜂交配算法在排课问题中的应用。这一部分首先对排课问题的基本理论进行了详细阐述并构建了数学模型。其次，给出了算法的编码方式及初始解构建的基本流程。再次，将本文提出的改进蜜蜂交配算法应用于排课问题中。最后，将改进算法与基本蜜蜂交配算法、HBMO-EPT算法进行了实验对比测试，证明了采用改进的蜜蜂交配算法进行课程编排具有更高的效率和稳定性。第五章排课系统的设计与实现。这一部分给出了排课系统的需求分析，设计了排课系统数据库，讲解了代码实现的基本原理，对各个功能界面进行了讲解与测试。第六章总结及展望。对全文的研究内容进行了概括和总结，对下一步的研究工作提出展望。4 河北工业大学硕士学位论文第二章基本蜜蜂交配算法的研究§2-1基本的蜜蜂交配算法本章首先对蜜蜂交配算法的基本理论、算法主要实现步骤等内容进行了详尽的阐述，然后，概括总结了常见的改进的蜜蜂交配算法，最后，将蜜蜂交配算法与其它仿生算法进行了对比分析，并总结了基本蜜蜂交配算法的不足。本章为后续知识的展开奠定了理论基础。2-1-1基本蜜蜂交配算法理论介绍由于蜜蜂交配算法效法于蜂皇的进化过程，因此下面先给出自然界蜂群的几个基本概念与术语，这对理解蜜蜂交配算法是十分重要的。基因（gene）：DNA或RNA分子上具有某种特性、能够决定后代性状的特定核苷酸序列。基因通过复制把遗传信息传递给下一代，使后代出现与亲代相似的性状。染色体（chromosome）：生物细胞内具有遗传性质的物体，易被碱性染料染成深色。它由携带各种不同信息的多个基因组合而成，是遗传物质的主要载体。蜂皇（queen）：蜜蜂群体中具有生殖能力、繁殖后代的雌性蜂称为蜂皇。通常每个蜂群只有1只。由于生殖率逐渐下降，常常被后继蜂皇所淘汰。雄蜂(drone)：蜜蜂群体中由未受精的卵发育而成的雄性蜜蜂。工蜂（worker）：蜜蜂群体中一种缺乏生殖能力的雌性蜜蜂。因年龄的不同可以将同一蜂巢中的工蜂分为三类——保育蜂、筑巢蜂和采蜜蜂。蜂群（population）：带有某种特征的染色体个体（包括蜂皇、雄蜂、工蜂）集合称为蜂群，该集合内三种蜜蜂个体的数目的总和称为蜂群的大小。受精囊（spermatheca）：蜂皇在交尾过程中，从雄蜂个体得到的精子，贮存于直到受精时的小囊。受精囊主要功能是存储雄蜂的精子，使精子与卵细胞结合产生卵。交叉（crossover）：蜂皇与雄蜂繁殖下一代时，父代与母代同源染色体相互交叉重组，即将父代与母代染色体在同一位置切断，切断前后的两组基因串相互交叉组合形成两条新染色体。变异（mutation）：生物体子代与亲代之间、子代个体之间基因组成及表现性状差异的现象。在形成子代的过程中，受某种因素的影响，染色体某个基因变异，产生不同于亲代的染色体类型。2-1-2基本蜜蜂交配算法描述蜜蜂交配算法是以蜂群的交配行为模型而设计的一种智能算法，它通过模拟蜂后的进化过程，来解决实际的优化问题。一个典型的蜂群主要是由蜂皇、雄蜂、工蜂及幼蜂四种类型的蜜蜂组成。蜂群中的各种蜜蜂各司其职，共同维护蜂巢的繁荣壮大。蜂皇是蜂巢中所有蜜蜂的母代，它的主要职责在于产生子代；雄蜂是蜂群个体的父代，其主要责任是与蜂皇交配，并将精子存储在蜂皇的受精囊中。雄峰的寿5 改进的蜜蜂交配算法及其在排课问题中的应用命是有限的，在完成交配过后，它的生命周期也将结束；工蜂主要负责照顾幼蜂及修复蜂巢，经过工蜂的培植，优秀的幼蜂个体将进化为蜂皇，其余的则褪变为工蜂或雄蜂；对应于实际的优化问题，蜂皇即当前的最优解，雄蜂代表求解问题的候选解，工蜂相当于局部搜索算法，幼蜂则是蜂皇与雄峰交叉形成的子代个体。在自然界中，每逢交配季节，蜂皇都会远离蜂巢摆动飞舞。一旦蜂皇出现，雄蜂群起追赶。在飞行的过程中，蜂皇的速度越来越快,体弱的雄蜂渐渐无法追上蜂皇相继掉落地面。只有速度最快、飞的最高的雄蜂才能与蜂皇交配。交配过后雄蜂将精子留在蜂皇的受精囊中，而其自身则会因为交接器拔断而立即死去。蜂皇继续飞舞，继续与其它雄蜂交配直至受精囊满纳精子飞归蜂巢。返回蜂巢之后蜂皇开始产卵，在产卵过程中，蜂皇随机的从它的受精囊中选取精子与卵细胞结合，产生受精卵。优秀的受精卵经过工蜂的培育进化为新的蜂皇，其余个体则被蜂群淘汰。从上述过程可以看出，蜂皇在整个蜂群中的地位至关重要，它对蜂群的繁殖进化发挥着主导作用。而雄蜂和工蜂起到辅助作用。雄峰通过相互竞争获得与蜂皇的交配机会,为蜂皇的进化提供优良基因；工蜂通过对幼蜂进行培育增强子代的适应性。通过对上述自然现象的抽象、模拟，产生出了基本的蜜蜂交配算法。它从代表问题潜在解集的蜂群开始，而组成蜂群的每个个体都是一条经过基因编码的染色体。初始蜂群产生之后，蜂皇按照优胜劣汰的原则，逐代进化产生出质量越来越好的近似解。在每一次迭代过程中，按照模拟退火的方式挑选雄峰个体，并借助于交叉算子和变异算子，产生出代表新解集的幼蜂群体，并对现有蜂皇进行替换。这个过程不断重复，对最后一代蜂皇个体经过解码操作就得求解问题的近似最优解。其整体过程可以分为四个主要阶段，如图2.1所示。第一阶段参数及蜂群的初始化算法参数的组成直接影响算法的整体效率，在基本蜜蜂交配算法中主要需要设置以下五个参数：雄蜂的数量，雄峰代表问题的候选解，它的数量直接影响了算法的求解空间大小；幼蜂的数量，幼蜂的数量关系到算法中交叉及变异的次数，它的大小直接影响了算法的多样性；蜂皇受精囊的大小，蜂皇的受精囊大小反应了单次飞行中蜂皇可以进行的交配次数，其值过大会使精子选择过程失去意义。相反，过小会使精子过于单一，容易造成早熟现象；蜂皇外出飞行的次数，它反映了算法整体的迭代次数，其值过大，算法的运行时间会加长，过小，收敛性不足；蜂皇能量的临界值，该参数关系到模拟退火执行的程度，一般设置为0。在基本蜜蜂交配算法中，初始蜂群一般采用随机的方式产生，这样做的原因在于随机的方式简单易行且能保证解的多样性，然而这样做并不能保证解的可行性，可能会对算法的整体性能产生影响。第二阶段交配阶段此阶段主要完成雄峰精子的选择。蜂皇单次出巢交配之前，会被赋予一定的能量和速度，随着飞行时间的增长，交配次数的增多，其能量和速度会依照一定的规则进行递减。在飞行期间蜂皇依照（2.1）式选择雄峰进行交配(f)s(t)Prob(Q,D)e(2.1)其中Prob(Q,D)代表蜂皇Q与雄蜂D进行交配的概率，()f代表蜂皇Q与雄蜂D适应值差的绝对值，S(t)为蜂皇在时刻t的飞行速度。从（1）式中可以看出当雄蜂与蜂皇的适应度差距很小或者蜂皇6 河北工业大学硕士学位论文的飞行速度很高时，雄蜂被蜂皇选中的概率就会增大。一旦雄蜂被蜂皇选中，它的染色体会存储在蜂皇的受精囊中。每次交配完成后，蜂皇的速度和能量的递减规则如（2.2）式和（2.3）式所示。S(t1)*S(t)(2.2)E(t1)E(t)(2.3)其中是速率因子，在0~1之间取值。是能量因子，其取值可以用（2.4）式表示。0.5*E(0)(2.4)MM代表蜂皇卵巢的大小。开始初始化参数初始化蜂群设定初始蜂皇i=1交配过程幼蜂的产生i=i+1幼蜂的培育更新蜂皇Yesi<飞行次数No结束图2.1蜜蜂交配算法的四个阶段Fig.2.1ThefourstepofHBMOalgorithm7 改进的蜜蜂交配算法及其在排课问题中的应用第三阶段幼蜂的产生及培育阶段这一阶段主要是受精卵（幼蜂）的产生与维护。当蜂皇的能量达到临界值或雄蜂的数量达到受精囊容量的最大值时，蜂皇将返回蜂巢，算法进入第三阶段。类似于遗传算法，在幼蜂的生成过程中也存在着三个基本操作：选择、交叉和变异。在选择阶段，蜂皇从自身的受精囊中随机选出一只雄蜂与其进行单点交叉操作，形成一个子代个体。随后变异操作将作用于新产生的子代以增加个体的多样性。在幼蜂的培育阶段，工蜂将采用启发式算法（贪心算法，随机游走算法等）对幼蜂进行局部搜索，产生适应值更好的可行解。当幼蜂的数量达到预先设置的幼蜂值时，该阶段结束。第四阶段蜂皇的更新阶段在第四个阶段，上一阶段适应值最小的幼蜂将与蜂皇进行比较，如果适应值好于蜂皇，则进行替换操作，并将其余的子代幼蜂全部摒弃。新的蜂皇飞出蜂巢开始下一轮的交配活动。整个过程将持续至交配次数参数达到所设临界值。2-1-3基本蜜蜂交配算法的实现步骤基本蜜蜂交配算法的实现步骤如下所示：步骤1初始化。初始化各个参数及初始蜂群；步骤2评价蜂群。计算蜂群中每个个体的适应度值。将蜂群中适应值最小的个体设置为蜂皇，其余个体设置为雄蜂；步骤3当交配次数小于设置时转入步骤4，否则转入步骤11；步骤4初始化蜂皇的能量和速度，判断蜂皇当前的能量值及受精囊的容量，如果满足条件进入步骤5，否则转入6；步骤5从公蜂中任取一个个体按式（2.1）计算出其被选中的概率并将该概率与0-1之间的随机数进行比较，若小于则将此个体加入至蜂皇的卵巢中。蜂皇的速度、能量分别按照式（2.2）和式（2.3）进行递减；步骤6判断幼蜂的数量是否达到设定值，如果没有达到进入步骤7，否则转向步骤9；步骤7从蜂皇的受精囊中随机选择一个公蜂，应用交叉及变异操作产生幼蜂，进入步骤8；步骤8应用局部搜索算法对幼蜂进行培育并将其加入后备蜂皇集合，幼蜂数量增1，返回步骤6；步骤9评价后备蜂皇，计算后备蜂皇中的个体适应值，选择适应值最好的个体与当前蜂皇的适应值进行比较，如果优于后者则进行替换操作，否则不进行任何操作。进入步骤10；步骤10清空后备蜂皇集合，交配次数增1，返回步骤3；步骤11返回蜂皇，蜂皇即是问题的最优解；单次执行过程可以用图2.2表示。8 河北工业大学硕士学位论文图2.2蜜蜂交配算法单次执行过程Fig.2.2SingleimplementationprocessofHBMOalgorithm§2-2常见的改进蜜蜂交配算法概述2-2-1自组织蜜蜂交配算法基本的蜜蜂交配算法的一个主要缺陷就是算法易于陷入局部最优。为了提高原有算法的局部搜索能力，减少算法的运行时间。2012年AritThammano和PatcharawadeePoolsamran两名研究人员对基本的蜜蜂交配算法进行了改进，提出了自组织蜜蜂交配算法（SMBO）。自组织蜜蜂交配算法的一个重要思想是能够自适应的设定蜂皇数量，依靠多蜂群共同推进蜂皇的进化，避免算法陷入局部最优。具体而言，它主要从四个方面对原有算法进行了改进：首先，SMBO将问题空间划分为多个蜂群，每一个蜂群都设有一个蜂皇。蜂群的大小取决于其蜂皇的适应度，适应度越高的蜂皇分配到的蜂群规模越大；其次，引进了一个控制新蜂群产生的参数，它有效的阻止了蜂皇的过度相似。当蜂皇完成交配产下幼蜂的时候，当前蜂皇和所有新生成的幼蜂会依照适应值进行排序。适应值最好的个体直接进化为蜂皇，剩余个体依次依照式（2.5）对它们进行判断，如果待选个体与第N个蜂群的蜂皇的距离小于，该候选解就被认为是蜂群N中的成员。如果大于，候选解就被认为是新蜂皇即开辟一个新的蜂群。d(C,qN)(2.5)N=argmind(C,qN)(2.6)1nS4(5.8257410)A0.58878(2.7)mmaxminA(xixi)(2.8)i19 改进的蜜蜂交配算法及其在排课问题中的应用其中d(C,qN)代表待选个体C与第N个蜂皇的欧几里得距离。S代表以前所选的蜂皇数量；N代表maxmin与待选个体最接近的蜂皇所在的蜂群标号；代表蜂群的边界值；xi，xi分别代表xi的上下边界，m是求解问题空间的维度。再次，为所有的雄蜂分配一定时限的生命周期，无论雄蜂是否与蜂皇进行了交配，在其生命周期结束时雄峰会立即死亡。减少的雄峰数量依靠新产生的幼蜂进行补给。除此之外在交配时，蜂皇会尽量选择与其它蜂群中的雄蜂进行交配以扩充当前蜂群的多样性。最后，在对雄峰进行分配的时候，引进了基于模糊逻辑聚类技术。由于在算法执行过程中产生了新的蜂群，因此在每次飞行结束后，都要为现有雄蜂分配新的蜂群。SMBO算法采用聚类技术为雄蜂分配蜂群。如式（2.9）所示雄蜂dp将被分配到与其近似度最高的蜂群中，在该算法中判断与蜂群的近似度转化为判断与蜂群中蜂皇的近似度。K=argmax[(dp,qn)](2.9)k2dpqn()2(dp,qn)eqn(2.10)f(qn)qnmax[d(qn,qk)](2.11)kf(qn)f(qk)其中(dp,qn)代表雄蜂dp与第n个蜂群中蜂皇qn的近似度；qn代表第n个蜂群的大小，它的取值取决于蜂皇qn的适应度；k代表大于0且小于蜂皇数量的整数；f(qn)代表适应度函数。2-2-2多种速度变化模式的蜜蜂交配算法[22]2012年SeyedJafarSadjadi,RoyaSoltani在文献中对基本蜜蜂交配算法中蜂皇的速度变化模式进行了改进，蜂皇可以随机的选择四种模式改变速度。这四种模式如图2.3所示，其中，（a）中蜂皇的速度呈线性递减模式；（b）中蜂皇的速度在交配早期下降较快，随着时间的推移日趋变慢；（c）中蜂皇的速度在交配早期和晚期的时候下降较慢，在中间时段内下降较快；（d）中速度的变化模式与（b）中相反，早期较慢，晚期急剧递减。通过四种模式的速度变化模式使雄蜂的选择范围得到了扩充，避免了蜂群的过度相似。四种模式所对应的速度表达式如式（2.12）至（2.15）所示。图2.3改进算法的速度变化模型Fig.2.3Theimprovedalgorithmspeedchangemodel(S0Sf)SiS0i(2.12)N10 河北工业大学硕士学位论文(S0Sf)(N1)(S0Sf)(N1)SiS0(2.13)N(i1)N110iSi(S0Sf)(1tanh(5))Sf(2.14)2Nln(S0Sf)ln(N)SiS0i(2.15)其中i代表蜂皇飞行开始之后所选的雄蜂数量，N代表受精囊的容量，S0和Sf分别代表蜂皇的初始速度和最终速度。2-2-3混合蜜蜂交配算法2009年TaherNiknam提出了一种混合蜜蜂交配算法（DPSO&HBMO），他将粒子群算法引入到蜜蜂交配算法中，这种优化模型结合了蜜蜂交配算法勘探能力强和粒子群优化算法收敛速度快的特点，从而增大了蜂群的多样性，避免了算法陷入局部最优。提高了算法整体的收敛速度和精度。在生成初始种群后，算法会将当前适应值最好的个体作为初始极值ghest和初始蜂皇分别代入粒子群算法和蜜蜂交配算法，随后，粒子群算法产生的N个粒子将加入到候选雄蜂中，这时候选雄蜂由两部分组成，一部分是由粒子群算法产生的，另一部分是算法初始形成的。蜂群在进行下一轮飞行的时候会从候选蜂群中选择N个适应值最好的个体作为初始雄蜂。这样做在保留了高适应度雄蜂个体的同时，进一步确保了蜂群的多样性，从而预防了算法停滞的发生。2-2-4各种改进算法的比较与基本蜜蜂交配算法相比，SBMO与DPSO&HBMO改进算法的共同点是增加了雄蜂的替换策略，提高了蜂群的多样性。但是，二者在雄蜂个体的替换策略上有所不同。SBMO算法提出了生命周期概念，在初始蜂群形成之后，为蜂群中的每一个雄峰个体都设置一个生命值，一旦雄蜂个体的生命值达到设定的上限，就用新产生的幼蜂对其进行替换，并对新产生的雄蜂个体分配相应的生命值。DPSO&HBMO改进算法则采用末位淘汰制，通过对比雄蜂个体适应值，选择适应度最差的雄峰个体进行淘汰操作。尽管两种算法在一定程度上解决了算法易于陷入局部最优的缺陷，但是这种改进是有限的，算法的勘探能力没有得到本质的提高。另外，二进制编码方式造成的编码解码困难、单点交叉信息量少等问题都没有得到有效的解决。相反，SBMO由于采用了多蜂群策略，每次迭代后都要重新分配雄蜂，反而增大了算法的运行时间，而且在迭代后期，蜂群的无限增大也会影响到算法的收敛速度。而DPSO&HBMO算法引进了粒子群算法，增加了算法的参数，不利于算法的整体控制。多速度变化模式的改进算法在不同的速度模式下切换，最坏情况下，速度的变化模式会一直为线性，算法运行到后半程，速度如果仍然成线性下降，会减少交配次数，不利于保持蜂群的多样性。§2-3蜜蜂交配算法与其它仿生算法的对比2-3-1共同点蜜蜂交配算法是一种仿生优化算法，它同其它主流的仿生算法（如遗传算法、蚁群算法、粒子群算11 改进的蜜蜂交配算法及其在排课问题中的应用法)一样，通过对自然界生物系统无意识的寻优行为的模拟求得问题的近似最优解。因此，蜜蜂交配算法与其它仿生化算法之间具有许多的共同点：l)具有不确定仿生类优化算法的不确定性是由算法本身的随机性引起的，在算法迭代的过程中，事件发生的概率是由随机元素所决定的，因此算法具有很强的不确定性2)具有较强的鲁棒性，广泛应用于求解各种寻优问题仿生类优化算法在优化过程中对问题本身并没有严格的数学要求，该问题是否具有连续性、可导性并不影响算法的执行效率。因此，只需针对现有问题对算法稍加改动就可以将其应用于其它优化问题的求解，算法具有良好的鲁棒性。3)具有智能型及适应性仿生类优化算法中的各个成员具有一定的智能性和适应性，能够通过相互协作适应当前生存环境。同时，它们具有高度的敏感性，一旦环境发生改变，会立即调整自己的行为做出相应的反应。这有利于算法获得质量较高的近似最优解。4)具实现有本质并行性，易于并行仿生类优化算法主要在两个方面体现出其本质的并行性：一是内在并行性，仿生类优化算法允许大规模并行执行，其执行过程类似于操作系统中多线程。算法的并行执行提升了其整体的运行效率;二是内含并行性，仿生类优化算法的内含并行性能够以较少的时间、计算代价换得较大的收益。5)易于和其它算法相结合，提高算法的整体性能仿生类优化算法具有很强的包容性，易于与其他算法相结合，产生搜索能力更强的新型算法。2-3-2不同点虽然蜜蜂交配算法同其它仿生类优化算法在算法机理、实现模式等多方面存在共性，但是它们之间仍然存在着许多不同。1)蜜蜂交配算法蜜蜂交配算法模拟自然界蜂群的交配过程，通过蜂皇的不断进化寻求问题的最优解。蜂群中的个体依照自己的职责采用不同的搜索策略，通过相互间协作共同完成寻优工作，具有较强的全局寻优能力[23][24]。但是，由于它是一种新兴的仿生算法，其数学基础相对薄弱，目前对它的理论分析还不是十分完备。2)粒子群优化算法粒子群算法（ParticleSwarmOptimization）是Kennedy和Eberhart于2001年提出的仿生类优化算[25]法。该算法来源于对鱼群及鸟群觅食行为的研究。在算法中，用粒子代表待优化问题的候选解且群体中的每个粒子都具有一个用来决定它们运动方向和距离的速度值。粒子通过对个体极值pbest和全局极值ghest的跟踪来更新自己的位置，在当前最优微粒的指导下对解空间进行搜索。粒子群优化算法需要设置的参数数量较少，并且求解问题的维数对算法的影响也非常小，收敛速度较快，但是其在迭代后期容易陷入局部最优解，且在求解复杂多峰值问题时搜索精度低，难以求得全局最优解。3)遗传算法12 河北工业大学硕士学位论文遗传算法的思想来源于达尔文的自然选择学说，它模拟生物的遗传进化机理，通过反复应用选择、[26-28]交叉和变异算子推进种群的不断进化。虽然在蜜蜂交配算法中也应用了交叉、变异算子，但其相较于遗传算法主要有两点不同：一是在蜜蜂交配算法的交叉操作中，蜂皇默认被选择为父本。由于蜂皇个体是蜂群中适应值最好的个体，其适应值最接近最优解，因此在搜索的过程中，算法能够迅速定位问题空间的最优区域。相较而言，遗传算法中进行交叉操作的两个个体都是通过选择机制（如轮盘赌选择机制）产生的，具有一定的随机性，算法会浪费大量的时间寻求最优空间；二是蜜蜂交配算法中引进了局部搜索机制，在每一次迭代过程中，算法都应用工蜂搜索算法对候选解进行局部搜索，而在标准的遗传算法并没有局部搜索机制。4)蚁群算法[29]蚁群算法模拟蚁群的觅食行为，利用了蚂蚁觅食过程中的正反馈机制，解决最优化问题。尽管蚁群算法的寻优能力很强，但是它的收敛性能对初始化参数的设置要求比较高，而且在迭代过程中信息素更新能力有限，算法搜索时间较长，容易出现停滞现象。§2-4基本的蜜蜂交配算法缺陷分析由于蜜蜂交配算法是一种随机搜索算法，因此它也不可避免的具有一些随机搜索算法常见的缺点，而其中最主要的缺陷在于算法易于陷入局部最优解，难以获得全局最优解。这一现象是由三种原因造成的：一是算法用于局部搜索的启发式算法邻域设置过于单一，导致其搜索能力不足，算法勘探能力弱，难以收敛至全局最优点；二是蜂群变异算子的设计不合理，且在整个迭代过程中雄蜂始终没有得到替换，蜂群的多样性不足，出现早熟现象；三是待优化问题函数的性质过于复杂。许多函数都是多峰值函数，形状不规则，而蜜蜂交配算法理论上并非收敛于所有类型函数的全局最优点，因此对于过于复杂的求解函数，很可能难以得到理想的结果;蜜蜂交配算法的另一个主要缺点是算法收敛速度慢，在求解实际问题时，通常是在指定的时间范围内获得满足一定精度的解，如果耗费大量的计算时间得到一个可行解，很多情况是不可取的。产生这种现象的原因是蜜蜂交配算法需要设置的参数过多，另外其初始解的不可行性也影响了算法的寻优时间。另外，由于蜜蜂交配算法的编码方式多采用二进制形式，因此，面对实数编码问题时，其原有的交叉及变异算子不在适用。综上所述，对蜜蜂交配算法在优化过程中所表现出来的各种不足概括如下：l)参数设置问题：过多的参数导致算法运行时间过长；2)交叉及变异算子问题：缺乏针对实数编码的交叉、变异算子，交叉算子携带信息量少；3)早熟收敛：算法过早收敛，导致寻优停滞；§2-5本章小结本章较为系统地分析了基本蜜蜂交配算法的基本原理、算法流程并列举分析了一些常见的改进蜜蜂交配算法。对蜜蜂交配算法与一些仿生优化算法进行了较为细致的对比分析。最后，概括了基本蜜蜂交配算法的不足之处。13 改进的蜜蜂交配算法及其在排课问题中的应用第三章改进的蜜蜂交配算法本章在第二章基本理论分析的基础上，针对蜜蜂交配算法算法的易于早熟收敛、收敛精度低的缺点，主要从五个方面对基本算法进行了改进：减少算法中参数的设置，用速度参数取代能量参数；改变原有算法的交叉操作，提出针对实数组合编码的交叉操作；采用多邻域的局部搜索策略；利用肯配链对现有变异操作进行了改进；提出雄蜂的替换策略，增大蜂群的多样性。这些改进措施虽然增加了一定的计算量，但是它们对提高蜜蜂交配算法的搜索性能，避免算法过早收敛而言是非常有实际意义的。§3-1改进算法的基本原理标准蜜蜂交配算法中，速度参数用于控制雄峰的选择概率，从式（2.2）可以看出它是非线性递减函数且其变化趋势为前快后慢。而能量参数的大小与交配次数密切相关，从式（2.3）可以看出能量参数的变化曲线是一条线性递减函数。线性递减函数的递减趋势在整个迭代过程中保持不变。然而，在算法迭代初期，蜂皇能量过强，难以选拔出与之相匹配的雄峰个体。因此我们期望加快能量的递减趋势，从而提高蜂皇与雄峰的交配率。而在迭代后期，能量降低过快，蜂皇中的受精囊可能还没有装满迭代就已经结束，受精囊不饱和使得后代个体过度相似，降低了单次飞行的效率。除此之外，放缓蜂皇能量的递减趋势可以给蜂群中适应值较差的雄峰个体提供更多的交配机会，丰富蜂皇受精囊中精子的类型。正是出于这种考虑，这里将能量参数的表达式设置为与速度参数表达式相同的形式。这就是参数改进的基本原理。标准的蜜蜂交配算法没有对雄峰进行替换操作，随着算法迭代次数的增加，蜂群多样性减少，算法陷入局部最优。蜂皇交配后所产生的幼蜂集合继承了蜂皇的优秀基因，相对于原有的雄峰集合具有更好的适应度，如果用其替换现有的雄峰集合能够加快算法的收敛速度。但是，由于雄峰的选择具有一定的随机性，在受精卵形成的过程中，原有雄峰中的优秀个体可能没有被选中，如果将其替换会错失全局最优解。因此在改进的算法中，主要采用末位淘汰制，用幼蜂个体替换当前的最差雄峰个体。另外，在替换的过程中，为了避免幼蜂个体与蜂群其它个体的过度相似，采用肯配链的方式对幼蜂个体进行了变异操作。蜜蜂交配算法的基本算子主要包括交叉算子、变异算子、工蜂搜索算子。算法中基本算子的选用直接影响了算法的执行效率，由于标准蜜蜂交配算法采用二进制编码方式，其交叉算子采用单点交叉，单次交叉所产生的子代个体的数量为1。然而，单点交叉携带信息量少，且交叉点的选择具有较大的随机性，没能充分的考虑到基因中的相互联系。在改进的算法中，提出了一种基于优势基因的交叉算子，该算子首先定义一组优势基因，通过互换父代与母代的优势基因产生两个子代个体，提高了交叉后子代的质量。标准算法中的变异算子选用反转方式，这种变异方式极易改变解的可行性，增大了算法的运行时间。在改进算法中采用肯配链变异方式，通过构建肯配链维护解的可行性，减少了算法的运行时间。标14 河北工业大学硕士学位论文准算法中的工蜂搜索算子临域设置过于简单，不利于维护蜂群的多样性，因此，在改进算法中采用双邻域的搜索算子，扩大了搜索范围，增大了算法的勘探能力。§3-2基本算子的改进3-2-1基于优势基因的交叉算子采用二进制对求解问题进行编码时，执行交叉操作后所产生的子代个体与父代差别不明显，而且编码所表示物理意义不明确，而采用十进制实数编码时，每个十进制数都被看做一个基因个体，由于个体本身就是解空间的点，所以它所表达的物理意义相对明确。在实际求解复杂优化问题的过程中多是采用十进制组合编码，因此，在蜜蜂交配算中提出一种针对十进制组合编码的交叉操作是十分必要的。另[30][31]外，由于交叉操作的目的是将父代与母代的优势基因进行组合，产生优于前代的基因类型。因此合理的利用父代的优势基因对于提升整个群体的适应度是十分重要的。本节提出了一种基于优势基因的交叉方法。为了说明交叉算子的具体操作过程，假定待求解问题为简单排课问题。Queen代表蜂皇染色体，Drone代表雄蜂染色体，X1，X2，X3为待安排课程的时隙。如图3.1所示，设置染色体的长度为11，其中前四位代表X1，表示在X1时刻可以安排四门课；中间三位代表X2，即X2时刻可以安排三门课；后四位代表X3，表示X3时刻可以安排4门课。数字1-9代表课程的编号，0代表空白位，表示在该时隙可以插入课程。不同的求解问题有不同的优势基因，在本问题中假定编号为1,3的课程为优势基因（如图中黑色边框所示）。由于交叉操作会产生两个子代个体，在此仅以子代一作为示例进行说明，子代二只需交换蜂皇与雄蜂的位置。描述过程中涉及的变量定义如下：对t{X1,X2,X3},r{1,2,3,4}，设child1（t，r）表示在子代个体中时间段t第r个位置上分配的课程情况，其取值可以用（3.1）式表示c分配了课程c(cC)child1(t,r)(3.1)0没有分配课程同理，drone（t,r）表示在雄蜂个体中，时间段t第r个位置上的分配情况；交叉的整个过程可描述如下：步骤1以蜂皇（Queen）为母本进行染色体的拷贝操作，形成初始的子代child1(子代二是以雄蜂为母本进行染色体的拷贝操作)；"步骤2将优势基因1,3加入到交叉集合C中；"步骤3对于C中的每一门课程c执行步骤4；步骤4找出课程c在雄蜂个体中分配的时隙ti、位置号ri，用drone(ti,ri)c,表示；找出课程c在子代child1中分配的时隙tj、位置号rj，用child1(tj,rj)c,表示。如果child1(ti,ri)c，不进行任何操作；如果child1(ti,ri)g(gc)执行步骤5；如果child1(ti,ri)0执行步骤7。15 改进的蜜蜂交配算法及其在排课问题中的应用对于优势基因1，如图3.1所示drone（X2,2）=1，child1（X1，2）=1，由于child1（X2,2）=3，所以进入步骤5。对于优势基因3，如图3.1所示，drone（X3,2）=3，child1（X2，2）=3，由于child1（X3,2）=0，所以进入步骤7。步骤5进行检测，如果时隙ti中不存其它的优势基因且有空白位，执行步骤6，否则，不进行任何操作；由于在child1中的X2时隙存在优势基因3，因此优势基因1停止了交叉操作。步骤6利用修复函数为课程g寻找相匹配的时隙和位置。如果能够找到符合条件的时隙tk和位置rk，则令child1(ti,ri)c，child1(tj,rj)0,child1(tk,rk)g；否则不进行任何操作；步骤7进行检测，如果时隙ti中的不存在其它优势基因，则令child1(ti,ri)c，child1(tj,rj)0；如果存在，不进行任何操作；由于在child1中的X3时隙不存在其它优势基因，因此令child1（X3,2）=3，child1（X2,2）=0，算法完成了交叉操作，其结果如图3.1中的child1所示，同理交叉形成的子代2，如图3.1中的child2所示。其中步骤6的修复函数可以简单概括如下：保持课程g在时隙中的相对位置不变，遍历所有的时隙，寻找符合条件的时隙，如果不存在，就将相对位置向后移动一位，再次遍历所有的时隙，重复这个过程直至找到合适的时隙和位置。X1X2X3Queen71208359046Child171208059346Child271248359060Drone70248159360X1X2X3图3.1交叉过程Fig.3.1Theprocessofcrossover3-2-2肯配链变异算子变异操作模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。变异的主要目的是扩大种群的多样性，避免个体的过度相似。在基本的蜜蜂交配算法中主要采用16 河北工业大学硕士学位论文反转技术实现染色体的变异.然而，这种技术主要是针对二进制编码的求解问题，难以在十进制编码中[32]发挥作用。肯配链又称二色图，主要应用于图着色问题的求解。在图着色问题中，任意两种颜色的节点以及它们之间的相互连接的边构成图G的子图G"，图G中任意的一个连通分支构成一条Kempe链。在求解实际优化问题时，常常将染色体上的各个基因看做是图中的节点，而基因之间的相互关联组成了边，待求解问题转化为图着色问题。因此利用肯配链对染色体进行变异是十分可行的。在此，仍然以上述排课问题来说明整个变异过程。在排课问题中，将每条染色体抽象为一张图，染色体上的课程基因表示图中的节点，具有相同学生或教师的课程之间用边相连，颜色表示可分配的时段。Kempe交换变异就是通过交换两个时间段中的课程基因达到对现有染色体的改变，而这些课程属于两条特定的肯配链。更进一步形式化的表示，假定k1、k2是时隙t1和t2中构成的两条Kempe链，按照t1(t1(K1K2))(t2(K1K2))和t2(t2(K1K2))(t1(K1K2))两个准则，交换两个时隙里的课程就完成了一次Kempe交换变异。如图3.2所示的例子，假定在子代个体中随机的选取一对时隙t1和t2，在t1时隙安排的课程为c1,c2,c3,c4,c5,c6，在t2时隙安排的课程为c7,c8,c9,c10,c11,c12。其中课程c2与c7，c5与c8，c4与c12之间享有共同的学生。c1与c7，c2与c8，...，c6与c12之间享有共同的老师，用一条直线将享有共同学生或共同老师的课程连接起来，那么相互连接不中断的课程将构成一条肯配链。如图3.2中（a）所示我们可以构建出三条肯配链Ka={c1，c2，c5，c7，c8，c11}，Kb={c3，c9}，Kc={c4，c6，c10，c12}。选取Ka和Kc两条肯配链，交换两个时隙里的课程,那么有t1(t1(KaKc))(t2(KaKc))={c7，c8，c3，c10，c11，c12}，t2(t2(KaKc))(t1(KaKc))={c1，c2，c9，c4，c5，c6},如图3.2中（b）所示。如果选取的两条肯配链中有一条为，即K，则按照t(tK)(tK)，t(tK)(t(K)d11dd222dd1两个准则交换两个时隙里的课程。图3.2肯配链构建及交换示意图Fig.3.2Kemptchainconstructionandexchangeschematicdiagram3-2-3双邻域工蜂搜索算子在蜜蜂交配算法中，工蜂培植子代个体是为了增加算法的勘探能力。本节对原有的工蜂搜索策略进17 改进的蜜蜂交配算法及其在排课问题中的应用行了改进，采用双邻域爬山法对空间进行搜索，并利用德尔塔评价对现行解进行评估。加快了算法收敛[33]速度，提高了解的精度。爬山法一种邻域搜索算法，而邻域定义是邻域搜索算法中最重要的一个特征。经典爬山法主要是选用一种邻域对现有解进行改进。但是，单邻域方法对问题求解空间的探索很有限，容易错失全局最优。因此采用多邻域对于空间的搜索是至关重要的。本节采用简单移动和简单交换两种形式的距离移动，这两种方式产生的邻域N1、N2定义如下：简单移动N1：通过移动染色体中一个基因到一个新的位置而产生的邻域。简单交换N2：通过交换染色体中两个基因的位置产生的邻域。在应用爬山法对幼蜂进行局部搜索的过程中，从初始解Brood0出发，首先采取简单移动邻域N1的方式进行m"次移动，得到N1邻域下的候选解Brood1"，在从Brood1"出发，应用简单交换邻域N2进行m次移动，得到当前迭代的最优解Brood1，增加迭代次数。逐步增加次数，实行邻域移动，直至得到局部最优值。爬山算法的流程如图3.3所示："I0:Brood0N1（m"）Brood1N2（m）Brood1"I1:Brood1N1（m"）Brood2N2（m）Brood2…………"In1:Broodn1N1（m"）BroodnN2（m）Broodn图3.3爬山法示意图Fig.3.3Climbingmethodschematicdiagram§3-3改进的蜜蜂交配算法的实现步骤依据改进算法的基本原理，可以概括出改进算法的具体执行步骤：步骤1初始化。初始化各个参数及初始蜂群；步骤2评价蜂群，计算蜂群中每个个体的适应度值。将蜂群中适应值最小的个体设置为蜂皇，其余个体设置为雄蜂；步骤3当交配次数小于设置时转入步骤4，否则转入步骤11；步骤4初始化蜂皇的能量和速度，判断蜂皇当前的能量值及受精囊的容量，如果满足条件进入步骤5，否则转入6；步骤5从雄蜂中任取一个个体按式（2.1）计算出其被选中的概率并将该概率与0-1之间的随机数进行比较，若小于则将此个体加入至蜂皇的卵巢中。蜂皇的速度、能量分别按照式（2.2）和式（2.3）进行递减；步骤6判断幼蜂的数量是否达到设定值，如果没有达到进入步骤7，否则转向步骤9；步骤7从蜂皇的受精囊中随机选择一个雄蜂，应用基于优势基因的交叉操作产生两个幼蜂，进入步骤8；步骤8比较两个子代的适应值，对较好的子代个体应用双邻域爬山搜索算法进行培育并将其加入18 河北工业大学硕士学位论文后备蜂皇集合，另一个子代个体进行肯配链变异操作形成后备雄蜂。进入步骤9；步骤9评价后备蜂皇，计算后备蜂皇中的个体适应值，选择适应值最好的个体与当前蜂皇的适应值进行比较，如果优于后者则进行替换操作，否则不进行任何操作。转向步骤10；步骤10后备雄蜂与原有雄蜂群体的适应值进行比较，替换其中最差个体。幼蜂数量增1，返回步骤6；步骤11交配次数增1，返回步骤3；步骤12返回蜂皇，蜂皇即是问题的最优解；根据算法的具体执行步骤，算法的流程图如图3.4所示。开始产生初始蜂群选择蜂皇初始化蜂皇的速度、能量N按照模拟退火的方式选择雄蜂加入受精囊受精囊是否已满Y选择雄蜂，进行交叉产生两个子代个体依据适应度选择个体较差个体较好个体NN应用K对肯陪链变异操作应用双邻域爬山算法优于当前优于当前蜂皇最差雄蜂YY替换雄蜂替换蜂皇NN幼蜂数量增1幼蜂数量是否满足设定值Y交配次数增1交配次数是否满足设置Y输出蜂皇结束图3.4改进的蜜蜂交配算法流程图Fig.3.4TheflowchartofHBMOalgorithm19 改进的蜜蜂交配算法及其在排课问题中的应用§3-4本章小结本章阐述了改进算法的基本思想，对算法中基本算子的改进进行了较为详细的说明，给出了基于优势基因交叉算子的基本实现步骤，为下一章检验改进算法的有效性及其在排课问题中的应用提供了理论基础。20 河北工业大学硕士学位论文第四章改进的蜜蜂交配算法在排课问题中的研究本章利用排课问题中的经典算例对第三章提出的改进算法进行了测试，实验结果表明本文提出的算法相较于标准的蜜蜂交配算法有了较大的提高,具有一定的可行性。§4-1排课问题概述[34]排课问题就其实质而言是一种涉及多因素的组合优化问题,在理论上又可以称为课程时间表问题。它的主要任务是在满足一定约束的条件下,将一定数量的课程安排到指定的时间和房间中,形成符合各方面要求的课表。由于问题本身具有的较大的复杂性和难度,它引起了许多专家学者的关注。[35]大学课程依据授课形式的不同可以分为两类,一类是某一专业某一年级的学生根据教学计划及教学大纲要求，必须修习的课程，通常包括公共课、基础课和专业课；另一类为学生选择修习的课程，这类课程摆脱了班级、专业、年级的限定，教务科直接根据选修人数安排课程。第一类课程每个学生某一学期开设的课程种类及数量是固定的，并且授课教师也是基本确定的，排课问题的解决重点是把教师所讲课程安排到周课表的合适时间；第二类课程教务科对其进行管理，全校学生依据教务科发配的开课计划进行选课。为了利用排课问题中的经典算例测试改进蜜蜂算法的有效性，本章主要是针对第二类课程进行排课。§4-2排课问题要素通过对手工排课过程的观察可以看出，在解决排课问题时需要考虑多方面的影响因素。学校是由许多不同职能的部门有机组合而成的整体，各个部门之间既各司其职，又密切协调合作，共同推进日常教务工作的正常运转和教学任务的顺利完成。排课过程是对各部门之间各种资源的重新规划，从排课过程[36]可能引起的潜在冲突方面来看，排课问题需要考虑以下5个必要要素：l)时间要素：排课问题中的时间要素主要包括学年、学期、周、星期、天、节次。由于每个学期的课程种类、学生人数、教室配备都不相同，因此，在每个学年的每个学期开始前都要进行一次排课，学期以周为单位，一般来说从开学第一周到最后一周每周的课表是相同的。每个教学周内含有5-6天教学日，每个教学日由9个时间段也就是节构成，一般来说，一门课程的安排是按一节课来进行，但也有某些课程是按两节课来进行。2)校区要素：一个学校可能有多个校区，每个校区都有相应的教学资源。当校区之间共享教师时，教师在不同校区上课时需要一定的赶赴时间。3)教室要素：教室具有许多属性，包括所在教学楼编号、楼层、类型、拥有的设备、支配使用状况。21 改进的蜜蜂交配算法及其在排课问题中的应用每个教室在同一时间段内只能安排一门课程，并且教室所能容纳的学生人数应该大于或等于上课的人数。另外，教室的类型也要符合课程的要求。4)课程要素：每门课程都拥有特定的编号、名称和所属学院以及排课优先级。每门课程可以拥有多名教师，也可以指定一名教师甚至可以没有教师。每门课程都有与之相匹配的教室类型，如语音室、多媒体教室、机房教室、普通教室等。每门课程可以依据自身的授课计划，设定开课起始周、结束周以及学时数。具有较多上课人数，较少与之相匹配教学资源的课程应该设置较高优先级，排课时优先考虑。5)学生要素：学生拥有独立的编号，每名学生隶属于一个学院，在一个时间段内只能上一门课程。只能出现在一个教室中。§4-3排课约束条件及数学模型4-3-1排课问题中的约束条件排课的主要任务是根据不同的约束条件将课程与学生在时间、空间上进行排列组合，以达到组合优[37]化，保证教学工作正常有序的进行。制定这些约束条件的主要目的是避免冲突。冲突的含义十分广泛，既可以发生在一种排课因素中，也可以涉及多个排课因素。是否合理解决冲突问题直接关系到排课质量的好坏，只有在避免所有冲突并且满足全部规则的基础上，才能确保教学计划顺利的进行。因此避免冲突是解决排课问题的关键所在。另外，为了保证排课任务的顺利完成以及各资源充分发挥各自优势，还需要对学生、课程、教室以及时间等几部分资源进行最优化组合配置。按照规则程度的不同可以将约束条件划分为两类：硬约束和软约束，硬约束是排课过程中必须满足的条件，是指在排课过程中各因素在时空概念上不可能发生的情况，它是衡量排课方案是否切实可行的标准；软约束通常是指那些可以不满足，但是希望满足的条件，它是衡量排课质量优劣的重要指标，通常在一个排课方案中判断方案优劣的标准有多个。一般来说，硬约束条件主要包括：H1：在一个时间段一名学生只能安排一门课程；H2：在一个时间段一间教室只能安排一门课程；H3：教室能够容纳的学生数不能超过上课的学生数；H4：教室的配备应符合课程的要求；软约束条件主要包括：S1：在一天的最后一个时段不给学生安排课程；S2：学生不能连续参加两门以上的课程；S3：一天之内，学生不能只在一个时间段参加课程；4-3-2排课问题的数学模型4-3-2-1排课求解目标排课问题通过实现相应的约束条件来寻找最优解，然而，对于某些排课问题，找到足够的约束条件22 河北工业大学硕士学位论文是十分困难的，而且由于课表组合方案的差异，能够找到的可行解并不唯一。因此，在排课过程中往往放弃寻找绝对最优的目标而转向寻找近似最优。一般认为，在满足基本的硬约束条件下，能够最大程度的满足传统手工排课中“合理、实用”的要求，实现最少软性冲突的课表安排是可行且最优的。无任何硬约束违反的课表，是排课问题的基本要求，也是课表可行的最低限度。而一套可行的课表在软性冲突上的表现，是我们衡量课表优劣的重要依据。根据上述分析，以及对人工排课的过程的研究，我们可以确定自动编排课表的目标。（1）课表是可行的，即符合硬约束条件，不存在无法执行的冲突。（2）课表质量较高。所谓高质量的课表，是指课表在时间、课程组合、教室安排等多方面都应符合各方面的需求，并且具有人性化的考虑。解决课表问题的主要难点在于如何在符合硬约束的条件下尽量减少软约束的违反，从而使排课方案在各个目标上尽量达到全局最优。4-3-2-2排课数学模型根据上述对排课求解目标的分析可以看出排课模型的建立与硬约束及软约束的数学模型息息相关。因此我们先给出约束条件的数学模型，从而推出整个排课问题的数学模型。为了表示排课问题的数学模型，我们假定排课问题中涉及的实体集合包括：课程、时间、教室、学生、类型。令课程集合：C={c1,c2,...,cn}，ci表示待排的第i门课程，n为课程总数量。时隙集合：T={t1,t2,...,tp}（p=45，一周五天，每天9个时隙），其中ti表示第i个可以进行排课的时间段，如ti代表某学期某周第p/9个教学日内的p%9节次。教室集合：R={r1,r2,...,rm}，ri代表可用于排课的第i个教室，m为教室总量。学生集合：S={s1,s2,...,sq}，si代表申请上课的第i个学生，q为学生总数。类型集合：RF={rf1,rf2,...,rfl}.rfi与教室或课程相匹配的第i中类型，l代表类型总量。设函数sktj(ci)表示学生sk在时刻tj安排的课程情况，那么硬约束1可以用式（4.1）表示。H1：n0sktj(ci)1hf1(sk,tj)i0(4.1)nsktj(ci)否则i01学生sk在tj时刻安排了课程ci其中，sktj(ci)0否则设函数tirj(ck)表示在时刻ti、教室rj中课程的安排情况，那么硬约束2可以用式（4.2）表示。H2:n0tirj(ck)1hf2(ti,rj)k0(4.2)ntirj(ck)否则k023 改进的蜜蜂交配算法及其在排课问题中的应用1在ti时隙，rj教室安排了课ck其中，tirj(ck)0否则设函数ri(sj)表示教室ri内学生的上课情况，a表示教室ri的容量，那么硬约束3可以用式（4.3）表示。H3:q0ri(sj)ahf(r)j0(4.3)3iqri(sj)-a否则k01学生sj在ri教室安排了课程其中，ri(sj)0否则设函数ricj(rfk)表示教室ri与课程cj的匹配情况，那么硬约束4可以用式（4.4）表示。H4:l0ricj(rfk)1hf4(ri,cj)k0(4.4)1否则1教室ri与课程ck的rfk类型相匹配其中，ricj(rfk)0否则设函数sk(tj)表示学生sk在tj(0j<45)时段是否安排了课程，如果安排了课程函数值为1，否则为0。则上述软约束可用公式（4.5）至（4.7）进行表示。S1：sk(tj)当j%98f1(sk,tj)(4.5)0其它S2:j2sk(tj)j%90jj1sk(tj)j%97(4.6)j1f2(sk,tj)j2j1sk(tj)||sk(tj)j%91jj1j2jj1sk(tj)||sk(tj)||sk(tj)2j%96jj2j1S3:81当sk(tj)1f3(sk,tj)j%90(4.7)0其它根据硬约束及软约束的要求可以定义排课问题的目标函数，其表达式如（4.8）式所示。即在满足24 河北工业大学硕士学位论文硬约束的条件下，尽可能减少硬约束或软约束的违反。pmmmnlpF(C,S,T,R,RF)minhf2(ti,rj)hf3(ri)hf4(ri,cj)(f1(sk,tj)f2(sk,tj)f3(sk,tj)hf1(sk,tj))(4.8)i1j1j1i0j1k1j1§4-4基于改进的蜜蜂交配算法的排课问题研究4-4-1基因编码及染色体的构造利用蜜蜂交配算法求解问题时，需要确定编码和解码运算，所谓的编码和解码就是在目标问题实际表示与算法的染色体位串结构之间建立联系。由于蜜蜂交配算法计算过程的鲁棒性，它对编码的要求并不苛刻。实际上，大多数问题都可以采用基因呈一维排列的定长染色体表示形式，尤其是基于{0,1}符号集的二进制编码形式，然而，编码的策略或方法对于算法中的基本算子，尤其是对交叉及变异算子的功能和设计有很大的影响。由此可见，编码方法在很大程度上决定了算法基本算子的设计，算法的运行形式以及运算效率。二进制编码方式具有简单、易于操作的特性，应用范围十分广泛，然而由于排课问题的特殊性，采用传统的二进制编码方式很难表达出所有的排课信息，而实数编码具有精度高，便于大空间搜索的优点，因此本文采用实数编码方式。以周为单位编排课表，假设每周有5个教学日，每个教学日上9节课，这样一周共有5*9=45个上课时隙。对于所有课程来说，一周共有45个时隙可以安排上课，同样对于每间教室来说每周也有45个时间段可以安排课程。两者是一致的，以45个时隙为基础设置编码来编排周课表。如下图所示每个基因由教室编号、课程编号、教师编号组成，分别对应位宽为3+4+4=11位.其中可供上课的教室百间左右，待编排的课程为千门左右，授课教师千名左右。虽然在选修课程编排中并不过多考虑授课教师的概念，但考虑到排课问题的通用性，在基因中留有4位教师编号。如果不考虑教师因素，可以删除该位码。基因构成如图4.1所示。教室编号课程编号教师编号图4.1课表染色体基因组成示意图Fig.4.1Chromosomesgeneticconstitutionofcoursetimetable例如00100990326代表编号为0326的教师在编号为1的教室教授序号为0099的课程，这样，由11位编码的基因表示了教室编号，所上课程及教师编号。每间教室由45个时间段组成一行就包括11*45=300个字符，这300个字符表示了一间教室一周所安排的上课方案。所有r间教室行，时间段列就形成了一个二维表记为T[r，300]，这个二维表也就相当于整个课表编排的一个方案，即一条染色体，包含所有学生的课程安排。其基本结构如表4.1所示。25 改进的蜜蜂交配算法及其在排课问题中的应用表4.1课表染色体基本组成Table4.1Schedulechromosomebasiccomponents时隙T1T2T3T4T5T6T7T8T9教室1c2c11c8c19c7c14c16c10c72c3c6c9c4c1c17c12c183c7c15c13c20c54c12c18c214-4-2初始蜂群的产生初始蜂群的质量对计算结果及计算效率会产生影响。在基本蜜蜂交配算法中，一般采用随机方法产生初始解，但是这种生成初始解的方式难以保证初始解的质量及可行性，影响算法的执行效率。因此，[38]在本节主要采用图着色的方式产生初始解以保证解的可行性。将排课问题对应到图中，课程用节点表示，共有相同学生或教师的两门课程之间用边连接，一个时间段表示一种颜色。每门课程可以安排的时隙数量用对应节点的饱和度表示，课程的冲突度用对应节点的度表示。初始蜂群个体的形成过程主要包括两步：一是，为所有待排课程分配时间段。二是，为安排了时隙的课程分配教室。其具体过程可描述如下：输入：未安排的课程列表E步骤一应用SD+LD+LE对整个课程列表进行排序。其中，SD表示最小饱和度优先，LD表示最大度优先，LE表示最多注册人数优先。排课开始时课程列表会先依据饱和度递增的顺序进行排列，当饱和度相同时，依据度递减的顺序进行排序，当度相同时，课程依据注册人数递减的顺序进行排序。经过排序之后，可安排时隙最少、易于和其他课程发生冲突且具有最多注册人数的课程会具有较高优先级，优先安排时隙和教室；步骤二判断列表的长度，如果大于等于1，对于列表中的每门课程e执行步骤三至步骤七；否则，转至输出；步骤三判断课程e的饱和度，如果等于0，执行步骤四，否则转入步骤六；步骤四随机的选择一个时隙t，将t内所有与课程e存在冲突的课程移至重排列表E’,并将课程e的时隙设为t。对于E’中的每门课程e’执行步骤五；步骤五判断e’的饱和度，如果大于0，在e’的可用时隙中随机的为其分配一个时间段并重新计算E’中课程的饱和度；否则，将其移至未排列表E。执行步骤七；步骤六在e的可用时隙中随机的为其分配一个时间段，将其从未排列表中移除，重新计算E中节点的饱和度，执行步骤七；步骤七为课程分配教室；输出：可行解重复蜂群个体的形成过程，直至达到初始蜂群的规模就形成了排课问题的初始蜂群。26 河北工业大学硕士学位论文4-4-3改进算子的应用对于基本蜜蜂交配算法在排课过程中存在的交叉算子信息量少、变异算子耗费时间过长、工蜂搜索算子易于陷入局部最优且整个算法收敛速度过慢的不足之处，本节将第三章提出的改进算子应用其中。1）交叉算子蜜蜂交配算法中最主要的一种操作就是交叉操作。标准的交叉是单点交叉，它在个体编码串中随机的选择一个交叉点，然后相互交换两个个体在该点之后的基因。采用这种算子，染色体上临近的等位基因不会发生变化，而相距较远的等位基因则会被分开。这种交叉算子有利于维护个体形状，但其基因位置有偏且携带信息量少，收敛速度较慢。本文采用的是无偏的二项式交叉(binomialcrossover)，由其生成的两个后代，一个与父本相似，另一个与母本相似。以十进制编码为基础，将排课问题中相互存在冲突的课程设为一组优势基因。Queen代表蜂皇染色体，Drone代表雄蜂染色体，Queen作为子代一的父本，子代二的母本，Drone作为子代一的母本，子代二的父本。父本和母本进行交叉操作，其具体操作步骤见第三章。2）变异算子蜂群的多样主要依靠变异操作实现，尽管变异发生的概率很低，但是其在抑制早熟现象发生、防止陷入局部最优解方面功效显著。变异使蜜蜂交配算法具有一定的随机搜索能力，为新个体的产生提供了机会。目前为止，有多种类型变异操作如反转型变异、移位变异等。在这里我们采用k对肯配链变异。K对肯配链首先选取k对时隙，对于每对时隙以课程及教室之间的冲突为基准建立肯配链，随机选取两条肯配链，交换两条肯配链中的课程。如时隙一编码为001009903260020101001000300000000，时隙二编码为001000703260020000000000300560010，两条肯配链为ka={0099,0007,0101}，kb为空。变异之后时隙一编码为001000703260020101001000300560010，时隙二编码为001000000000020000000000300560010。这种变异操作维护了课表的可行性，相较单次变异来说降低了冲突的可能性。变异操作中的K值初始设定为1，在蜂群进化过程中，根据当前的蜂群状况自适应的调整k值大小。为了确定k值的大小，需要对当前幼蜂进行个体相似性的计算，其具体定义如下：n1个体相似性：是指个体间的相似程度，定义为：|f(brood)f(dronei)）|，其中n代表当前蜂群ni1n中雄峰的数量。当幼蜂的适应值与当前雄峰群体的平均适应值差的绝对值小于10.5*f(dronei)时，将ni11n|f(brood)f(dronei)|k值增大为tni1，其中t为时隙总数。即对染色体中的一半基因进行*(1)21nf(dronei)ni11n变异操作。否则，设置k值为|f(brood)f(dronei)|tni1。*(1)21nmax{f(brood),f(dronei)}ni127 改进的蜜蜂交配算法及其在排课问题中的应用§4-5实验比较4-5-1实验环境及实验数据源4-5-1-1实验环境为了比较改进的蜜蜂交配算法在排课问题上的有效性及执行效率，本文采用原始的蜜蜂交配算法，HBMO-EPT以及本文提出的改进算法对每个数据集独立运行20次，实验的软硬件环境如下：（1）硬件环境实验机器：LenovoSL400处理器：Inter奔腾4处理器2.8GHZ内存：1GB（2）软件环境开发语言：C++开发平台：VisualStudio20084-5-1-2实验数据源说明[39]本文使用苏哈数据集中的11个实例进行了排课实验。苏哈数据集中包括小型（small）、中型（medium）、大型（large）三种类型的数据。其中小型和中型数据各包括五个实例，分别命名为small1，small2，…，small5，medium1，mediu2，…，medium5。三种类型数据的具体参数如表4.2所示。表4.2苏哈数据集的基本参数Table4.2Thesochabenchmarkcoursetimetablingdataset小型中型大型课程数量100400400教室数量51010特征数量5510每个教室符合的特征335数量已用的特征数目708090学生数目80200400学生可参加的最多课202020程数课程可容纳的最多学2050100生数28 河北工业大学硕士学位论文4-5-2实验结果本实验中相关的参数设置如表4.3所示。实验对比分析了三种算法的最优值以及平均值。为了检测算法的稳定性，对于中型和大型数据集比较了偏差值。其中，偏差值=|最优值-平均值|/平均值。实验结果如表4.4所示。从表4.4可以看出，对于小型数据small1至small5来说，HBMO-EPT算法和本文算法的目标函数值都为0，而原始算法的平均值均略高于这两种算法，说明在解的精度方面，二者较原有算法都有所提高；对于中型数据medium1至medium5来说，本文算法的目标函数值较HBMO-EPT算法更小，课表违反的软约束更少，课表质量较高。在稳定性方面，通过偏差值可以看出，20次运行中的最优值与平均值之间的差异较小，算法较为稳定；对于大型数据，也得到了与中型数据相类似的结果。表4.3算法基本参数设置Table4.3Theimprovealgorithmparameters参数名称参数取值蜂群规模40交配次数10000受精囊大小10幼蜂数量10工蜂搜索次数3000表4.4算法处罚值比较Table4.4ResultsobtainedfromimprovealgorithmcomparedtooriginaloneandHBMO-EPT数据类型原始蜜蜂交配算法HBMO-EPT本文算法偏差平均值最好值平均值最好值平均值最好值Small1200000-Small2200000-Small3100000-Small4300000-Small5400000-Medium110198797571667%Medium2140133938882758.5%Medium32172011341291231165.6%Medium41591398174625412.9%Medium5190178736467619%Large8408275315235265171.7%另外，为了检测算法的收敛速度，以Medium1型数据测试了三种算法的收敛性。medium1型数据初始可行解的处罚值为760，对其进行10000次迭代，其结果如图4.2所示。从图中可以看出，到2000次的时候，本文算法的处罚值已经由760降至150，而HBMO-EPT算法在200左右，本文算法的收敛29 改进的蜜蜂交配算法及其在排课问题中的应用速度较后者更快，到了8000次的时候两者基本都收敛至最低值，但是本文算法比HBMO-EPT算法具有更好的精度，可以说，本文算法更为有效。图4.2三种算法收敛速度对比Fig.4.2Threekindsofalgorithmconvergencevelocitycontrast4-5-3算法性能分析从表4.4的实验结果可以看出对于小型数据、中型数据及大型数据，无论是在平均值还是最好值本文算法都要优于前两种算法，在全局最优性上有了更进一步的提高。从偏差值来看，改进算法的最优值与平均值比较接近，说明改进算法较为稳定。从图4.2中可以看出改进后的蜜蜂交配算法相较于其它两种算法，在收敛速度上更快。综上所述，本文算法在求解排课问题的时候较前两种算法更为有效。§4-6本章小结本章分析了影响排课问题的主要因素，依据约束条件建立了排课问题的数学模型，明确了排课问题的主要目标，通过图着色方式构建了初始蜂群并将改进后的算法应用于排课问题。通过实验对比证明了改进算法的有效性，为下一章构建排课系统奠定了理论基础。30 河北工业大学硕士学位论文第五章排课系统的设计与实现本章将改进后的蜜蜂交配算法应用到实际的排课问题中，建立了排课系统。详细分析了系统的主要需求；给出了系统的主要功能模块，并对各模块进行了讲解；对系统数据库的数据库进行了设计并对系统的开发环境进行了讲解，最后，对系统中的主要界面进行了展示。§5-1排课系统的设计5-1-1系统总体框架设计5-1-1-1排课系统需求分析随着电子信息技术的高速发展，计算机在教学活动管理中的作用日益凸显。它以直观、快速的效果、简单的操作方式，给人以耳目一新的感觉。计算机自动排课不仅能替代传统的手工排课手段，而且能够达到传统排课方法无法达到的排课效果。由于计算机排课具有严格的工作步骤，减少了排课过程中的随机性，使排课结果更直观、更科学。因此不论从排课效率还是排课质量来看，计算机智能排课都能达到良好的排课效果，它能使排课密度达到饱和的程度，这是传统排课方法所无法比拟的。以课表的形成流程作为系统需求分析的依据，需要使排课系统的功能满足所有用户各阶段的要求。根据排课系统功能的不同可以将用户分为四类：管理员、教务科、教师、以及学生。管理员主要负责一些日常事务的管理，主要包括学生、教师用户信息的导入与删除，学校的组织管理、角色管理以及用户信息的查询等，管理员用户拥有系统最大的权限。教务科主要负责教室资源的管理、授课计划的导入、申请周数的设置、学生申请课程的审批以及课表的生成与调整。学生进入系统主要进行课程选择、课表查询及打印。教师进入系统主要进行课表的查询与打印操作。5-1-1-2系统功能模块设计根据对排课系统的需求分析，可以设计出本系统的主要功能模块如图5.1所示。排课系统主要包括七个模块，分别为维护用户信息、维护教学资源、导入授课计划、选定课程、审批课程、生成课表、查看课表。其主要功能可以概括如下：1）维护用户信息：管理员对用户进行统一管理，可以导入、添加、删除学生或教师的用户信息。2）维护教学资源：这一部分主要是对教室资源的管理和维护，设置当前学期可用的教室资源。3）导入授课计划：教务科导入各学院的授课计划。4}选定课程：学生根据本学期课程列表选择课程进行学习。5）审批课程：教务科根据当前的教学资源及学生的申请情况，审批学生的上课申请。6）生成课表：系统依照当前教务科的审批情况，生成课表。7）查看课表：学生或老师可以依照选定的周次、校区查看本学期的课表安排。31 改进的蜜蜂交配算法及其在排课问题中的应用维护用户信息维护教学资源智能导入授课计划排课选定课程系统审批课程生成课表查看课表图5.1智能排课系统系统功能结构图Fig.5.1Intelligentcoursesystemthefunctionstructureofthesystem5-1-2系统数据库设计数据库表的建立是系统程序开发过程中的一个重要环节，建立数据表前必须理清数据的流向以及数据间的相互关系，明确各个模块需要操纵的数据类型。本系统的数据库设计主要分为两类，一类是针对排课主题的信息，另一类是基本信息。下面分别介绍一下系统中用到的两类表的结构。排课主题的数据表包括：教室信息表（CT_ROOM）、授课计划表（CT_PLAN）、时隙信息表（CT_TIMEINFO）、排课关系表（CT_APPRELATION）、课程申请表（CT_APPLICATION），各表的主要字段如表5.1至表5.5所示。基本信息表包括以下信息表：用户信息表（User），该表记录了用户的基本信息，包括用户编号、用户名称、密码、电子邮箱、注册时间等；学生信息表（Student），该表记录了学生的基本信息资料，如用户编号、学号、所属班级、所属院系等；教师信息表（Teacher），该表存放教师的基本信息；包括用户编号、教师编号、教师职称。表5.1教室信息表CT_ROOMTable5.1Roominformation名称类型长度主键备注CT_ROOMIDNUMBER19Y教室编号CT_ROOMNAMEVARCHAR500N教室名称CT_XQNUMBER19N校区编号CT_ROOMNUMINT4N教室容量CT_ROOMTYPEVARCHAR50N教室种类CT_ROOMSTATEINT4N教室状态32 河北工业大学硕士学位论文表5.2授课计划表CT_PLANTable5.2Courseoutlineandschedule名称类型长度主键备注CT_PLANIDNUMBER19Y主键授课计划编号CT_COURSEIDVARCHAR100N课程编号CT_COURSENAMEVARCHAR500N课程名称CT_YXIDNUMBER19N院系编号课程类型（0：普通，1：CT_COURSETYPEINT4N选修）CT_COURSETIMEVARCHAR500N课程周次考试方式（0：考查1：考CT_EXAMTYPEINT4N试）CT_TEAIDNUMBER19N授课教师编号CT_ROOMTYPENUMBER19N教室类型编号CT_XQNUMBER19N校区编号CT_XLNUMBER19N校历编号CT_BZNUMBER19N备注表5.3时隙信息表CT_TIMEINFOTable5.3Timeslotinformation名称类型长度主键备注CT_TIMEIDNUMBER19Y主键CT_TIMEWEEKVARCHAR500N星期名称CT_TIMEJCVARCHAR500N节次名称CA_IDNUMBER19N校历编号CT_TIMECDVARCHAR500N课时长度CT_TIMESTATEINT4N时隙状态表5.4排课关系表CT_APPRELATIONTable5.4Courserelationship名称类型长度主键备注CT_APPIDNUMBER19Y申请编号CT_ROOMIDNUMBER19N分配房间编号CT_TIMEIDNUMBER19N分配时间编号33 改进的蜜蜂交配算法及其在排课问题中的应用表5.5课程申请表CT_APPLICATIONTable5.5Courseapplication名称类型长度主键备注CT_APPIDNUMBER19Y申请编号CT_STUIDNUMBER19N学生编号CT_PLANIDNUMBER19N授课计划编号CT_APPDATEVARCHAR500N申请时间CT_XQNUMBER19N所属校区编号CT_XLNUMBER19N校历编号CT_APPSTATEINT4N审批状态CT_APPRESULTVARCHAR500N审批结果在SQL数据库中，SQLServer用户定义函数是接受参数、执行操作（例如复杂计算），并将操作结果以值的形式返回的例程。它具有执行速度快，网络流量少的优点。用户定义函数可接受零个或多个输入参数，返回标量值或表。SQLServer2008支持三种用户定义函数，标量函数、表值函数和内置系统函数。标量函数返回在RETURNS子句中定义的类型的单个数据值。表值函数返回table。表值函数又可以分为两类：内嵌表值函数和多语句表值函数。内嵌表值函数，没有函数主体，表是单个select语句的结果集；多语句表值函数，可以定义函数主体可以包含多条T-SQL语句。在本系统中由于授课计划中上课周次的存储方式为多字符串连接方式，例如6-9,10。为了区分出单周的授课计划，在数据库中建立了多语句表值函数，利用该函数实现了周授课计划的快速查找。综合以上各种因素以及实际应用，该系统数据库设计结构合理，可以较好地配合蜜蜂交配算法实现排课，系统效率高。§5-2排课系统的实现5-2-1开发环境本系统的主体开发环境为WindowsXP操作系统，采用关系型数据库SQLServer2008以及Eclipse开发平台，使用SSH（Spring，Struts，Hibernate）架构，MVC设计模式。MVC设计模式将Web应用[40]程序分割成若干逻辑部件，使得程序开发编程变得更加容易，降低了程序的耦合性。MVC主要由三部分组成——数据模型层（业务逻辑处理层）、视图层（交互界面）和控制器层（事务分配器）。模型层主要负责设置各种业务规则以及处理业务产生的各项数据。模型层接受控制层转发过来的数据请求，与数据库进行交互并将处理后的结果返回给视图层。应用于模型的代码可以被多个视图重复使用，有效减少了代码的冗余性;视图层是用户与系统进行交互的界面层，它从模型中获取数据，将数据展示给用户；控制器负责从客户端接受用户请求，通过调用模型和视图将这些请求转换成某种行为，完成用户需求。控制器工作机制的十分明显，控制器接受用户请求后，将决定调用哪个模型构件去处理请求，然后确定使用哪个视图来显示模型处理返回的数据，但是在整个过程中，控制器不会对模型层数据做任何处理工34 河北工业大学硕士学位论文作。MVC设计模式中三个部件间的关系结构如图5.2所示。1、页面请求控制器浏（Controller）3、选择View2、业务处理览器查询模型状态数视图层数据模型层据（View）（Model）库更改状态图5.2MVC三部件关系Fig.5.2TherelationshipofMVCthreeparts5-2-2系统主要模块的实现（1）用户登录模块为了保证系统的安全性，用户在输入用户名、密码后方可登录，只有在两者与数据库中数据相一致时，才可以进入排课系统。用户录界面如图5.3所示。图5.3用户登录界面Fig.5.3Userlogininterface（2）学生选定课程模块学生用户登录系统后，如果当前处于选课阶段，点击“选定课程”，系统会显示当前已选课程。学35 改进的蜜蜂交配算法及其在排课问题中的应用生的选课页面如图5.4所示。页面中的操作栏显示了当前选课的结果，如果选课成功会显示已通过；如果选课失败会显示未通过；如果教务员还没有对其进行处理，那么学生可以修改或者删除已选课程。点击“新选课程”可以重新进行选课如图5.5所示。图5.4学生选课页面Fig.5.4Students"courseselectionpage图5.5新选课程页面Fig.5.5Choosenewcoursepage（3）审批模块教务员对学生申请课程情况进行审批，合格的人员表示选课成功，不合格人员给出审批意见，如图5.6所示，点击申请人姓名，可以查看申请人的详细信息；点击课程名称，可以查看课程的详细信息。36 河北工业大学硕士学位论文图5.6审批课程申请页面Fig.5.6Examinationandapprovalcourseapplicationpage（4）课表生成及管理模块该模块主要完成课表的生成与修改。如图5.7所示，为计算机学院一次的课表生成情况，点击相应的课程名称，可以对课程所在教室及时间进行更改。图5.7生成课表页面Fig.5.7Generationcoursetimetablingpage（5）学生查看课表模块学生点击“查看课表”，可以对生成的课表进行查看如图5.8所示。课表查看可以具体到周，也可以查看整个学年的课表安排情况。点击“打印”可以对课表进行打印。37 改进的蜜蜂交配算法及其在排课问题中的应用图5.8查看课表页面Fig.5.8Checkschedulepage§5-3本章小结本章给出了排课系统的需求分析，系统的功能框架，对设计系统中涉及的设计模式、数据库构造进行了详尽的阐述，最后给出了系统的实现界面。38 河北工业大学硕士学位论文第六章总结与展望§6-1论文总结本论文对蜜蜂交配算法的基本理论和基本性质进行了深入的研究，通过对比，分析了现有算法的主要缺陷，针对这些缺点提出了相应的改进措施，并通过实验验证了改进算法的有效性。此外将算法应用于实际排课问题的求解中，取得了良好的排课效果。回顾本文对蜜蜂交配算法的研究与应用，本文的研究的内容是：1）系统的介绍了蜜蜂交配算法的基本理论、执行步骤，通过与其他改进算法及仿生算法的比较，得出了算法的主要缺陷。2）提出了基于优势基因的交叉操作并给出了其具体的实现步骤，有效利用了基因之间的内在联系。提出了肯配链变异操作，通过建立肯配链避免破坏解的可行性，减少了算法的运行时间。提出了雄峰的部分替换策略，采用末位淘汰机制增大了蜂群的多样性。3）分析了影响排课的主要因素、约束条件、构建了完整的数学模型，并应用改进的蜜蜂交配算法求解了排课问题的经典算例，通过实验对比，证明了改进算法的有效性。4）将改进的蜜蜂交配算法应用于实际的排课问题中，构建了排课系统，实现了智能排课。§6-2论文展望尽管本文提出的改进算法在排课问题上取得了较好的实验结果，但是改进算法是否具有通用性没有得到有效的验证。拓展算法的应用领域对于证明蜜蜂交配算法的通用性是十分必要的。此外，针对不同问题适应度函数的设置问题，算法中参数的设计与选择，以及对算法模型本身的研究都需要进行更深入的研究。39 改进的蜜蜂交配算法及其在排课问题中的应用参考文献[1]R.S.Parpinelli,H.S.Lopes.Newinspirationsinswarmintelligence:asurvey[J].Bio-InspiredComputation,2011,3(1):1-16.[2]Abbass,H.A.Amonogenousmboapproachtosatisfiability[C].ProceedingoftheInternationalConferenceonComputationalIntelligenceforModeling,ControlandAutomation.CIMCA’2001,LasVegas,NV,USA,2001.[3]TaherNiknam.AnefficienthybridevolutionaryalgorithmbasedonPSOandHBMOalgorithmsformulti-objectiveDistributionFeederReconfiguration[J].EnergyConversionandManagement,2009,50(8):2074–2082.[4]YannisMarinakis,MagdaleneMarinaki,GeorgiosDounias.HoneybeesmatingoptimizationalgorithmfortheEuclideantravelingsalesproblem[J].InformationSciences,2011,181(1):4684-4698.[5]JavadOlamaei,TaherNiknam,sirousbadali,Arefia.Distributionfeederreconfigurationforlossminimizationbasedonmodifiedhoneybeematingoptimizationalgorithm[J].EnergyProcedia,2012,(14):304-311.[6]AritThammano,PatcharawadeePoolsamran.SMBO:Aself-organizingmodelofmarriageinhoney-beeoptimization[J].ExpertSystemswithApplications,2012,39(5):5576-5583.[7]PatcharawadeePoolsamran,AritThammano.Amodifiedmarriageinhoney-beeoptimizationforfunctionoptimizationproblems[J].ProcediaComputerScience,2011,(6):335-342.[8]ChangHS.Convergingmarriageinhoney-beesoptimizationandapplicationtostochasticdynamicprogramming[J].JournalofGlobalOptimization,2006,35(3):423-441．[9]Curkovicp,Jerbic.Honey-beesoptimizationalgorithmappliedtopathplanningproblem[J].InternationalJournalofSimulationModelling,2007,6(3):154-165.[10]AmiriB,FathianM.Integrationofselforganizingfeaturemapsandhoneybeematingoptimizationalgorithmformarketsegmentation[J].JournalofTheoreticalandAppliedInformationTechnology,2007,3(3):70-80.[11]FathianM,AmiriB.Ahoneybee-matingapproachforclusteranalysis[J].InternationalJournalofAdvancedManufacturingTechnology,2008,38(7-8):809-821.[12]HaddadOB,AfsharA,MarinoMA.Optimizationofnonconvexwaterresourceproblemsbyhoney-beematingoptimization(HBMO)algorithm[J].EngineeringComputations,2009,26(3):267-280.[13]Ming-HuwiHorng,Ren-JeanLiou,JunWu.Parametricactivecontourmodelbyusingthehoneybeematingoptimization[J].ExpertSystemswithApplications,2010,37(10):7015-7025.[14]Magdalenem,YannisM,ConstantinZ.Honeybeesmatingoptimizationalgorithmforfinancialclassificationproblems[J].Appliedsoftcomputing,2010,10(3):806-812.[15]NasserR.Sabar,MasriAyob,Grahamkendalletal.Ahoney-beematingoptimizationalgorithmforeducationaltimetablingproblems[J].EuropeanJournalofOperationalResearch,2012,216(3):533-543.[16]杨晨光,陈杰,涂序彦.基于方向概率和改进蜂群算法的地面防空武器组网系统优化布阵[J].兵工学40 河北工业大学硕士学位论文报,2008,29(2):221-226.[17]杨进,马良.解决复杂优化问题的一个有效工具——蜂群优化算法[J].计算机应用研究,2010，27(12):4410-4413.[18]张超群,郑建国,王翔.蜂群算法研究综述[J].计算机应用研究,2011,28(9):3201-3204.[19]Gotlieb.Theconstructionofclass-teachertimetables[C].ProceedingIFIPCongress,Amsterdam,1963:73-74.[20]S.Even,A.Itai,A.Shamir.On.Thecomplexityoftimetableandmulticommodityflowproblems[J].SIAMJournalonComputing,1976,(5):691-703.[21]林漳希,林尧瑞.清华大学学报（自然版）[J].1984,24[2]:1-8.[22]SeyedJafarSadjadi,RoyaSoltani.Alternativedesignredundancyallocationusinganefficientheuristicandahoneybeematingalgorithm[J].ExpertSystemswithApplications,2012,39(1):990-999.[23]TaherNiknam,HasanDoagouMojarrad,HamedZeinoddiniMeymand,BahmanBahmaniFirouzi.Anewhoneybeematingoptimizationalgorithmfornon-smootheconomicdispatch[J].Energy2011,36(2):896-908.[24]A.Afshar,O.BozorgHaddad,M.A.Mariño,B.J.Adams.Honey-beematingoptimization(HBMO)algorithmforoptimalreservoiroperation[J].JournaloftheFranklinInstitute,2007,344(5):452-462.[25]于蕾.粒子群算法的改进及其在人工神经网络中的应用:[硕士论文].西安:西安电子科技大学,2010.[26]卢雪艳,周永权.蜜蜂双种群进化型遗传算法[J].计算机工程与设计,2008,29(13):3422-3428.[27]吴迪,姜永增,宋广均.基于蜂群遗传算法的0-1背包问题[J].计算机工程与科学,2011,33(5):102-105.[28]谭跃,谭冠政,叶勇,伍雪冬.具有混沌局部搜索策略的双种群遗传算法[J].计算机应用研究,2011,28(2):469-471.[29]杨剑锋.蚁群算法及应用研究:[博士论文].浙江:浙江大学，2007.[30]R.Lewis,B.Paechter.Newcrossoveroperatorsfortimetablingwithevolutionaryalgorithms[C].TheFifthInternationalConferenceonRecentAdvancesinSoftComputingRASC2004Nottingham,England,2004,189–194.[31]KusumDeep,ManojThakur.Anewcrossoveroperatorforrealcodedgeneticalgorithms[J].AppliedMathematicsandComputation2007,188(1):895–911.[32]ZhipengLu,JinKaoHao.Adaptivetabusearchforcoursetimetabling[J].EuropeanJournalofOperationalResearch,2010,200(1):235-244.[33]AnmarAbuhamdah.ExperimentalResultofLateAcceptanceRandomizedDescentAlgorithmforSolvingCourseTimetablingProblems[J].InternationalJournalofComputerScienceandNetworkSecurity,2010,10(1):895-911.[34]陈守家,付霞,周欣.基于遗传禁忌算法结合解决排课问题[J].计算机应用,2007,27(7):1806-1808.[35]彭复明,吴志健.基于多种群算法的排课方法[J].计算机工程与设计,2010,31(22):4877-4908.[36]于国莉.基于遗传算法的排课问题的研究:[硕士论文].河北:河北工业大学,2007.[37]SafaaiDeris,SigeruOmatub,HiroshiOhtab,PutehSaada.Incorporatingconstraintpropagationingeneticalgorithmforuniversitytimetableplanning[J].EngineeringApplicationsofArti®cialIntelligence1999,(12):241-253.[38]Burke,E.K.,McCollum,B.,Meisels,A.,Petrovic,S.,Qu,R.Agraph-basedhyper-heuristicforeducationaltimetablingproblems[J].OperationalResearch,2007,176(2):177–192.41