高校自动排课系统的算法研究与实现

2024年2月26日发(作者：蓝莓采摘)

重庆大学硕士学位论文高校自动排课系统的算法研究与实现姓名：湛德照申请学位级别：硕士专业：计算机技术指导教师：何中市;高宏宾20061001

重庆大学硕士学位论文中文摘要摘要目前，随着我国高校教育事业的不断发展，课程编排问题在一定程度上影响着教学质量的提高。为了保证教学质量，高校必须制定一套严密、规范的教学计划和执行合理的课程安排。而课程编排是比较繁重而关键的一环。回顾过去，１９６３年，Ｃ．Ｃ．Ｇｏｆｌｉｅｂ在文章《ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆＣｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ）中提出了课表编排的数学模型，它标志着课程编排课题的研究正式跨入了庄严的科学殿堂。１９７６年，ＳＥｖｅｎ在论文《ｏｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙＦｌｏｗＰｒｏｂｌｅｍｓ》，第一次证明了课表是ＮＰ完全问题。在国内，清华大学于１９８４年在《清华大学学报（自然版）》上发表了林漳希和林尧瑞在该课题上的实验性研究成果，接着国内部分高等院校相继开展了这方面的研究工作。本文分析了排课的数学模型，提出了利用遗传算法解决排课问题的方法，完成的主要工作如下：①探讨课程表问题的约束因素，以优化时间和空间两种资源为目标，通过对比，我们发现采用遗传算法去解决课表问题是比较理想的解决方法，并讨论了它的基本原理、步骤及其产生、发展、现状以及存在的问题等情况。②改进时间安排算法：遗传算法有能简化程序的复杂度和生成最佳课表时间的优点，本论文提出的时间安排算法以经典遗传算法作为基础，进行了以下几个方面研究工作：１）对遗传算法存在的缺陷进行改进和优化，避免了遗传算法出现未成熟就收敛等问题；２）提出排课问题的优化求解模型和约束满足模型；３）针对排课问题研究了染色体编码方式以及遗传操作算子的设计，提出了一种适应度计算方法，由节次优度、日组合优度等相互联系求解。③提出教室安排算法：排课问题中，除了时间安排外，为课程选择一个教室是十分重要的，我们提出了教室安排算法，实现资源优化配置。④系统的实现：针对课表个性化的要求，设置了排课知识库和策略库来动态地调整准则，以满足不同课表要求，体现该系统具有良好的适用性和实用性。本文以五邑大学排课系统的开发为背景，对整个系统的工作进行了分析总结，并对后续工作进行了展望。关键词：排课，遗传算法，组合优化，人工调整

重庆大学硕士学袋论文茭文攮要ＡＢＳＴＲＡＣＴＲｅｃｅｎｔｌｙ，ｗｉｔｈｔｈｅｃｏｎｓｔａｎｔｌｙｄｅｖｅｌｏｐｍｅｎｔｏｆｈｉｇｈｅｄｕｃａｔｉｏｎ，ｔｉｍｅｔａｂｌｉｎｇｈａｓｖｅｒｙｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｒｉｓｉｎｇｔｈｅｅｄｕｃａｔｉｏｎｑｕａｌｉｔｙ．Ｉｎｏｒｄｅｒ协ｇｕａｒａｎｔ∞ｉｔｓａｄｖａｎｃｅｄｔｅａｃｈｉｎｇａｎｄｓｔｕｄｙｉｎｇｑｕａｌｉｔｙ，ａｕｎｉｖｅｒｓｉｔｙｍｕｓｔｄｒａｗｕｐａｔｉｇｈｔａｎｄｓｔａｎｄａｒｄｔｅａｃｈｉｎｇｏｎｅａｎｄｓｔｕｄｙｉｎｇｐｌａｎａｎｄＣａｌＴｙｏｕｔｔｈｅｒｅａｓｏｎａｂｌｅｔｉｍｅｔａｂｌｉｎｇ．Ｔｈｅｔｉｍｅｔａｂｌｉｎｇｉｓｏｆｔｈｅｈｅａｖｙａｎｄｋｅｙｑｕｅｓｔｉｏｎｓ．Ｉｎ１９６３，Ｃ．Ｃ．ＧｏｔｌｉｅｂｐｒｏｐｏｓｅｄｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆＣｕｒｒｉｃｕｌｕｍＳｃｈｅｄｕｌｅＰｒｏｂｌｅｍ（ＣＳＰｆｏｒｓｈｏｒｔ）ｉｎｔｈｅｐａｐｅｒ（ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆＣｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ｝，ｉｔｓｙｍｂｏｌｉｚｅｄｔｈｅｒｅｓｅａｒｃｈｉｎｇｏｆＣＳＰｈａｄｅｎｔｅｒｔｈｅｓｃｉｅｎｃ宅ｄｏｍａｉｎｆｉｅｌｄ．Ｉｎ１９７６，Ｓ．Ｅｖｅｎｐｒｏｖｅｄｔｈｅｐａｐｅｒ（ＯｎｔｈａｔＣＳＰｉｓａＮＰ—ＣｏｍｐｌｅｔｅｄｐｒｏｂｌｅｍｉｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙＦｌｏｗＰｒｏｂｌｅｍｓ》Ｃｈｉｎａ，Ｔｓｉｌｌｇｈｕａｕｎｉｖｅｒｓｉｔｙｄｅｌｉｖｅｒｅｄｔｈｅｆｏｒｆｉｒｓｔｔｉｍｅ．Ｉｎｅｘｐｅｒｉｍｅｎｔａｌｌｙｒｅｓｅａｒｃｈｅｄｒｅｓｕｌｔｏｆｚ｝ｌａｎｇｘｉＬｉｎａｎｄＹａｏｒｕｉＬｉｎａｂｏｕｔｔｈｉｓｐｒｏｂｌｅｍｉｎ（ＪＯＵＲＮＡＬＯＦＴＳＩＮＧＨＵＡＵＮＷＥＲＳＩＴＹ（ＳＣＩＥＮＳＥＡＮＤｎａｔｉｖｅＴＥＣＮＯＬＯＧＹ））。Ｓｕｂｓｅｑｕｅｎｔｌｙ，ｐａｒｔｓｏｆａｂｏｕｔｔｈｉｓｏｔｈｅｒｕｎｉｖｅｒｓｉｔｉｅｓａｌｓｏｂｅｇａｎｒｅｓｅａｒｃｈｉｎｇｗｏｒｋｐｒｏｂｌｅｍ．ＴｈｅＧｅｎｅｔｉｃｍａｔｈｅｍａｔｉｃｓｉｓｍｏｄｅｌｏｆｔｉｍｅｔａｂｌｉｎｇｉｓｄｉｓｃｕｓｓｅｄｉｎｔｈｉｓｐａｐｅｒ，ｍｅａｎｗｈｉｌｅｔｈｅｔｏＡｌｇｏｒｉｔｈｍ（ａＡ）ｉｓｕｓｅｄｒｅｓｏｌｖｅｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｔｈｅｍａｉｎｗｏｒｋｏｆｔｈｉｓｐａｐｅｒｌｉｓｔｅｄａｓｆｏｌｌｏｗｓ：ｐａｐｅｒｄｉｓｃｕｓｓｅｓｎｕｍｅｒｏｕｓｃｏｎｓｔｒａｉｎｔｓｉｎｖｏｌｖｅｄｉｎｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，④ＴｈｉｓｗｈｏｓｅａｉｍｉＳｔｏｏｐｔｉｍｉｚｅｔｈｅｔｗｏｒｅ搭ｏｕｌ＇ｃｅｓｏｆｔｉｍｅａｎｄａｐａｃｅ．Ｃｏｍｐａｒｉｎｇ谳像ｖａｒｉｏｕｓＡｌｇｏｒｉｔｈｍｔｏｒｅｓｏｌｖｅｔｈｅｍｅｔｈｏｄｓ，ｗｅｆｉｎｄｔｈａｔｉｔ’ＳａｎｉｄｅａｌｍｅｔｈｏｄｔｏａｄｏｐｔＧｅｎｅｔｉｃｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ａｎｄｄｉｓｃｕｓｓｉｔｓｂａｓｉｃｐｒｉｎｃｉｐｌｅ，ｓｔｅｐａｎｄｉｔｓｃｒｅａｔｉｏｎ，ｄｅｖｅｌｏｐｍｅｎｔ，ｉｎｔｈｉｓｐａｐｅｒａｓｆｏｌｌｏｗｓ：ａｎｄｍａｋｉｎｇｔｈｅｂｅｓｔａｒｅｐｒｅｓｅｎｔｃｏｎｄｉｔｉｏｎａｎｄｅｘｉｓｔｅｎｔｐｒｏｂｌｅｍｅｔｅ．＠ＴｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍｉｓｇｉｖｅｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｈａｓｔｈｅａｄｖａｎｔａｇｅｓｏｎｏｆｓｉｍｐｌｉｆｙｉｎｇｐｒｏｃｅｄｕｒｅｔｉｍｅｔａｂｌｅ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｂａｓｅｄａｓｆｏｌｌｏｗｉｎｇ：１）ＭａｋｅｓｏｍｅｃｌａｓｓｉｃＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ．ＴｈｅｍａｉｎｃｏｎｔｅｎｔｏｎｉｍｐｒｏｖｅｍｅｎｔｓａｎｄｏｐｔｉｍｉｚａｔｉｏｎａｐｐｅａｒｉｎｇｔｈｅｃｌａｓｓｉｃＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ａｎｄｉｍｍａｔｕｒｅａｖｏｉｄｔｈｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｖａｒｉｏｕｓｐｒｏｂｌｅｍｓｓｕｃｈ嬲ｃｏｎｖｅｒｇｅｎｃｅ；２）Ｗｏｒｋｏｕｔｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｆｏｒｒｅｓｏｌｖｉｎｇａｎｄｃｏｎｓｔｒａｉｎｔｓｔｕｄｉｅｄｃｈｒｏｍｏｓｏｍｅｃｏｄｉｎｇａｎｄｈｅｒｅｄｉ移ｏｐｅｒａｔｏｒａｍｏｄｄｉｎｔｉｍｅｔａｂｔｉｎｇｄｅｓｉｇｎｉｎｇａｉｍｅｄａｔｐｒｏｂｌｅｍ；３）Ｗｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ｐｕｔｆｏｒｗａｒｄｆｉｔｎｅｓｓｃｏｍｐｕｔａｔｉｏｎｍｏｄｅｆｒｏｍｓｌｏｔ－ｓｕｐｅｒｉｏｒ，ｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ—ｄａｙ．ｅｔｃ．Ｃｏｎｔａｃｔｓｔｏｓｏｌｖｅｍｕｔｕａｌｌｙ．ｖｅｒｙ③Ｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｒｉｔｈｍ：ＢｅｓｉｄｅｓＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍ，ｉｔ’Ｓ珏

重庆丈学硕士学藏论文英文接要ｉｍｐｏｒｔａｎｔｏｕｔｔｏｃｈｏｏｓｅａｃｌａｓｓｒｏｏｍｆｏｒａｃｏＢｒｓｅｉｎｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｗｅｈａｄｗｏｒｋｅｄｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｄｔｈｍ，ｏｐｔｉｍａｌａｌｌｏｃａｔｉｏｎｏｆｒｅｓｏｕｒｃｅｓｉｓｇｕａｒａｎｔｅｅｄ．④Ｔｈｅｒｅａｌｉｚａｔｉｏｎｏｆｔｈｅｓｙｓｔｅｍ：Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｐｅｒｓｏｎａｌｒｅｑｕｅｓｔｏｆｔｉｍｅｔａｂｌｅ，ＷｅｅｓｔａｂｌｉｓｈｅｄｔｈｅｔｉｍｃｔａｂｌｉｎｇＫｎｏｗｌｅｄｇｅＬｉｂｒａｒｙａｎｄＳｔｒａｔｅｇｙＬｉｂｒａｒｙｔｏａｄｊｕｓｔｔｈｅｓｔａｎｄａｒｄｗｉｔｈｓａｔｉｓｆａｃｔｉｏｎｆｏｒｄ｛ｆｆｅｒｅｎｔｔｉｍｅｔａｂｌｅｒｅｑｕｅｓｔｓ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｓｙｓｔｅｍｄｅｖｅｌｏｐｅｄｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍｈａｓｇｏｏｄａｄａｐｔａｂｉｌｉｔｙａｎｄａｖａｉｌａｂｉｌｉｔｙ．ＴｈｉｓｐａｐｅｒｔｏｏｋｔｈｅｅｘｐｌｏｉｔａｔｉｏｎｉｎｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｔｉｍｃｔａｂｌｉｎｇｓｙｓｔｅｍｉｎＵｎｉｖｅｒｓｉｔｙ，ｃａｒｆｉｅｄｏｎａｌｌＷｕｙｉａｎａｌｙｔｉｃａｌｓｕｍｍａｒｙｆｏｒｔｈｅｗｈｏｌｅｗｏｒｋ，ａｎｄｍａｄｅａｎｏｕｔｌｏｏｋｔｏｔｈｅｆｏｌｌｏｗ－ｕｐｗｏｒｋ．Ｋｅｙｗｏｒｄｓ：Ｔｉｍｅｔａｂｌｉｎｇ，ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＣｏｍｂｉｎａｔｉｏｎＯｐｔｉｍｉｚａｔｉｏｎ，ＩＩＩ

独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：配乙签字日期：幽／年，一月≠日学位论文版权使用授权书本学位论文作者完全了解重麽盍堂重鏖太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密（本学位论文属于不保密（）。），在——年解密后适用本授权书。（请只在上述一个括号内打“√”）学位论文作者签名：茫睨签字日期：幽占年膳月年日郢繇铷手签字日期：之励缉ｆ矿月ｙ日

重庆大学硕士学位论文１绪论１绪论１．１排课问题的提出及研究意义高校的排课是教学管理中最基本、最重要、十分繁重而复杂的工作，它涉及到全校全部的专业，全部的师生和全部的课程，它的本质就是为所有的课程安排一组适当的教学时间和地点，使教学能够顺利进行。随着各高校的招生规模扩大，教师和教室资源显得越发紧张，使得本来就有难度的排课越发困难。课表的编排属于一类涉及多种因素的组合规划问题【ｌ】，它必须使课程安排中的教室、教师和学生不发生冲突，这是最基本的要求，在此基础上要尽量满足教师提出的其它要求（比如某教师要求只是上午上课，必须在多媒体教室上课等等）和学校教室资源的约束。在人工排课的过程中，实现这样的要求是有一定困难的，为学校排出一个可行的课表要排课工作人员耗费两到三个月的时间，工作量非常大，而且排出来的结果也未必尽人意。随着各高校的教育体制改革的深入和招生规模的进一步扩大，手工排课的缺点越显突出，我校的情况更为严重，因为教师和教室资源的限制，排课非常困难。而计算机恰好能帮助解决这个问题，它具有自动运行、计算速度快等特点，只要有相应的软件系统，就能很好地解决排课的困难，实现教学管理决策的科学化。１．２国内外计算机自动排课的研究历史５０年代末，国外就有人开始研究课表编排问题。１９６２年，Ｇｏｔｌｉｅｂ曾提出一个课表问题的数学模型怛】，并使用匈牙利算法解决了三维线性运输问题。此后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨，但是大多数文献所用到的数学模型都是Ｇｏｆｌｉｅｂ的数学模型的简化或补充。近５０年来，人们对课表问题的计算机解法做了许多尝试。其中，有人将课表编排的整数规划模型问题归结为求一组Ｏ．１变量的解，但是其计算量非常大，而且解决Ｏ．１线性优化问题的分支定界技术却只适用于规模较小的课表编排；Ｍｉｈｏｅ和Ｂａｌａｓ（１９６５）将课表公式化为一个优化问题【３】；另外还有人提出将它当作一种线性编程的方法或将课表问题简化为三维运输问题；而Ｔｒｉｐａｔｈｙ则把课表问题视作整数线性编程问题并提出了大学课表的数学模型［４１；此外，有些文献试图从图论的角度来求解课表问题，但是图的染色问题也是ＮＰ完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题吲。这样的数学模型与实际相差甚远，所以对于大多数学校的课表编排问题来说没有实用的价值。进入九十年代以后，国外对课表问题的研究仍然十分活跃，比较有代表性的有印度的Ｖａｓｔａｐｕｒ大学管理学院的Ａｒａｂｉｎｄａ

重庆大学硕士学位论文１绪论Ｔｒｉｐａｔｈｙ、加拿大Ｍｏｎｔｒｅａｌ大学的ＪｅａｎＡｕｂｉｎ和ＪａｃｑｕｅｓＦｅｒｌａｎｄ等。对于课表的编排，已经使用的的算法有：关联规则ＦＰ．ｇｒｏｗｔｈ算法１６１、基于时间位图迭加匹配的算法‘７１、基于资源匹配的算’法【８１、分组优化决策算法【９】、分支定界法【１０１、有限回溯法【ｌｌ】，拉格朗日松弛法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行问题描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。外国的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有望成功的办法ｍ】。在国内，对课表问题的研究开始于８０年代初期，具有代表性的有：南京工学院的ＵＴＳＳ（ＡＵｎｉｖｅｒｓｉｔｙＴｉｍｅｔａｂｌｅＳｃｈｅｄｕｌｉｎｇＳｙｓｔｅｍ）系统【１３】，清华大学的ＴＩＳＥＲ系统ｎ４】，大连理工大学的智能教学组织管理与课程调度系统【１５ｌ，西南交通大学在分析高校课表编排所遵循的基本原则和模糊性原则的基础上，定义了课元之间关于教师的相关关系和关于自然班的相关关系，提出了以课元相关运算和课元的候选时空片计算为核心的计算机排课算法１１６１，延边大学根据高校课程表的制作特点，设计了计算机自动排课的数据结构与算法【１７】；沈阳电力高等专科学校研制了基于Ｃｌｉｅｎｔ／Ｓｅｒｖｅｒ的开放式智能排课系统［１８１等。使用遗传算法来求解排课问题也有较多其它相关的报道【１９．２４１，还有～些其它高校根据自己的情况编写了一些程序去实行计算机自动排课，例如浙江大学的“教务管理系统”等等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排，都或多或少存在问题。２

重庆大学硕士学位论文２遗传算法的设计思想２遗传算法的设计思想遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，ＧＡ）研究的历史并不算长，２０世纪６０年代末期到７０年代初期，主要由美国Ｍｉｃｈｉｇａｎ大学的ＪｏｈｎＨｏｌｌａｎｄ与其同事、同学们研究，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型，形成了较完整的理论和方法。随后经过２０余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来的进化计算热潮，计算智能己作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。从１９８５年在美国卡耐基·梅隆大学召开的第一届国际遗传算法会议（ＩｎｔｅｒｎａｔｉｏｎａｌＩＥＥＥ的ＴｒａｎｓａｃｔｉｏｎｓｏｎＣｏｎｆｅｒｅｎｃｅＯｌｌＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ：ＩＣＧＡ＇８５）到１９９７年５月ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。２．１遗传算法的产生与发展早在２０世纪５０年代和６０年代，就有少数几个计算机科学家独立地进行了“人工进化系统”的研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，比如大多数系统都遵行“适者生存”的仿自然法则，有些系统采用了基于种群（ｐｏｐｕｌａｔｉｏｎ）的设计方案，并且加入了自然选择和变异操作，还有一些系统对生物染色体编码进行了抽象处理。６０年代初期，柏林工业大学的Ｉ．Ｒｅｃｈｅｎｂｅｒｇ和Ｈ．ＥＳｅｈｗｅｆｅｌ等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数值，并获得了较好的效果。随后，他们对这种方法进行了深入的研究，形成了进化计算的另外一个分支——进化策略（ＥｖｏｌｕｔｉｏｎａｒｙＳｔｒａｔｅｇｙ，ＥＳ），如今Ｅｓ和ＧＡ已呈融合之势。同样是在２０世纪６０年代，Ｌ．Ｊ．Ｆｏｇｅｌ等人在设计有限态自动机（ＦｉｎｉｔｅＳｔａｔｅＭａｃｈｉｎｅ，ＦｓＭ）时提出了进化规划（ＥｖｏｌｕｔｉｏｎａｒｙＰｒｏｇｒａｍｍｉｎｇ，ＥＰ），借用进化的思想对一组ＦＳＭ进行进化，以获得较好的ＦＳＭ。他们将此方法应用到数据诊断、模式识别和分类及控制系统的设计等问题中，取得了较好的结果。后来又借助进化策略方法发展了进化规划，并用于数值优化及神经网络的训练等问题中。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉（即是杂交）来产生新的基因结构，早期的算法收效甚微。２０世纪６０年代中期，ＪｏｈｎＨｏｌｌａｎｄ在Ａ．Ｓ．Ｆｒａｓｅｒ和Ｈ－Ｊ．Ｂｒｅｍｅｒｍａｎｎ等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉操作，并且强调将交叉作为主要的遗传操作。随３

重庆大学硕士学位论文２遗传算法的设计思想后，Ｈｏｌｌａｎｄ将该算法用于自然和人工系统的自适应行为的研究中，并于１９７５年出版了其开创性著作‘＇ＡｄａｐｔａｔｉｏｎｉｎＮａｔｕｒａｌａｎｄＡｒｔｉｆｉｃｉａｌＳｙｓｔｅｍｓ”。以后，Ｈｏｌｌａｎｄ等人将该算法加以推广，应用到优化及机器学习问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功的应用奠定了基础。Ｈｏｌｌａｎｄ早期有关遗传算法的许多概念一直沿用到今天，可见Ｈｏｌｌａｎｄ对遗传算法的贡献之大。在其后，遗传算法的应用无论是用来解决实际问题还是建模，其范围不断扩展，这主要依赖于遗传算法本身的逐渐成熟。近年来，许多冠以“遗传算法”的研究与Ｈｏｌｌａｎｄ最初提出的算法已少有雷同之处，不同的遗传基因表达方式，不同的交叉和变异算子、特殊算子的引用以及不同的再生和选择方法，但这些改进方法产生的灵感都来自大自然的生物进化，可以归为一个“算法簇”。人们用进化计算来包容这样的遗传“算法簇”，它基本划分为四个分支：遗传算法（ＧＡ）、进化规划（ＥＰ）、进化策略（ＥＳ）和遗传程序设计（ＧＰ）。２．２生物进化理论和遗传学的基本知识我们知道，生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异，生命是进化的产物，现代的生物是在长期的进化过程中发展起来的。达尔文用自然选择（ｎａｔｕｒａｌｓｅｌｅｃｔｉｏｎ）来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：①遗传（ｈｅｒｅｄｉｔｙ）：这是生物的普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的性状。生物有了这个特性，物种才能稳定存在。②变异（ｖａｒｉａｔｉｏｎ）：亲代和子代之间以及子代的不同个体之间总有差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。③生存斗争和适者生存：自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向积累，于是性状逐渐和原先的祖先不同，演变为新的物种。遗传算法模拟的是怎样的生物进化模型呢？假设对相当于自然界中的一群人的一个种群进行操作，第一步的选择是以现实世界中的优胜劣汰现象为背景的；第二步的重组交叉则相当于人类的结婚和生育；第三步的变异则与自然界中偶尔发生的变异是一致的。人类偶然出现的返祖现象便是一种变异。由于包含着对模式的操作，遗传算法不断地产生出更加优良的个体，所采用的遗传操作都与生物尤其是人类的进化过程相对应。如果我们再仔细分析遗传算法的操作对象种群，４

重庆大学硕士学位论文２遗传算法的设计思想实际上它对应的是一群人，而不是整个人类。一群人随着时间的推移而不断进化，并具备越来越多的优良品质。然而，由于他们生长、演变、环境和原始祖先的局限性，经过相当一段时间后，他们将逐渐进化到某些特征相对优势的平衡态，当一个种群进化到这种状态，这个种群的特性就不再有很大的变化了。一个简单的遗传算法，从初始代开始，并且各项参数都设定，也会到达平衡态。此时种群中的优良个体仅包含了某些类的优良模式，因为该遗传算法的设置特性参数使得这些优良模式的各个串位未能得到平等的竞争机会。遗传算法效法于自然选择的生物进化，是一种模仿生物进化过程的随机方法，下面先对几个生物学的基本概念与术语进行解释，以便理解遗传算法。染色体（ｃｈｒｏｍｏｓｏｍｅ）：生物细胞中含有的一种微小的丝状化合物，它是遗传物质的主要载体，由多个遗传因子——基因组成。遗传因子（ｇｅｎｅ）：ＤＮＡ（脱氧核糖核酸）或ＲＮＡ（核糖核酸）长链结构中占有一定位置的基本遗传单位，也叫做基因。表现型（ｐｈｅｎｏｔｙｐｅ）：由染色体决定性状的外部表现，或者说，根据遗传子型形成的个体，称为表现型。基因型（１０ｃｕｓ）：遗传基因在染色体中所占据的位置。个体（ｉｎｄｉｖｉｄｕａｌ）：染色体带有特征的实体。种群（ｐｏｐｕｌａｔｉｏｎ）染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。进化（ｅｖｏｌｕｔｉｏｎ）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化，生物的进化是以种群的形式进行的。适应度（ｆｉｍｃｓｓ）：在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度较高的物种将获得更多的繁殖机会，而对生存环境适应度较低的物种，其繁殖机会就相对较低。选择（ｓｅｌｅｃｔｉｏｎ）：指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。复制（ｒｅｐｒｏｄｕｃｔｉｏｎ）：细胞在分裂时，遗传物质ＤＮＡ通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。交叉（ｃｒｏｓｓｏｖｅｒ）：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处ＤＮＡ被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组，俗称杂交。变异（ｍｕｔａｔｉｏｎ）：在细胞进行复制时可能以很小的概率产生某些复制差错，

重庆大学硕士学位论文２遗传算法的设计思想从而使ＤＮＡ发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。编码（ｃｏｄｉｎｇ）：ＤＮＡ中遗传信息在一个长链上按一定的模式排列。２．３遗传算法的基本思想问题域图２．１遗传算法的过程Ｆｉｇｕｒｅ２．１Ｔｈｅｐｒｏｃ％￥ｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ我们现在引用上面的术语描述遗传算法的基本思想。遗传算法是从代表问题６

重庆大学硕士学缎论文２邃铸算法豹设圣｝思恕可能潜在解熊的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个蒺因的集合，其内部袭现是某种基因缀合，它决定了个体的形状的癸嫠表现，麴黧头发憨鸷薤是耄象绝钵孛控豢ｌ这～黪缝戆菜莠基因缀会决定豹。因此，在一开始需要实现获表瑷熬掰基因静映射编礴工作。由于仿照萋鞠编码鲍工作复杂，我们将其进行简化，如二进制编码等。初代种群产生之后，按照适者生存和优胜铹汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算予进行组合交叉移交异，产生爨健表颓豹瓣集｜！｝冬耱群。这个遥程将簿致秘嚣像自然遴纯～榉鹣后生｛弋释群鞋：虢代更鸯珏适应予环境，末代耱嚣中的最傀个体经过解碍，Ｗ以作为问题近似最优解。遗传算法采纳了自然进化的模型，如选择、交叉、变异、迁移、局城与领域等。基本遗传舞法如图２．１所示。计算开始对，～定数嚣静Ｎ个令体（父个体ｌ、父个体２、父个俸３、父令髂４……）帮秘群蘧袄Ｉ缝秘始纯，著谤算每令令俸静适应度函数，第一代毽鼯窃始代产生了。如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照遁成度选择个体，父代饕求基因重组（交叉）而产生子代。所肖的子代按一定概攀变异，然后子代的邈威度又被重新计算，子代被插入到种群中将父代取而代之，构成新的一代（子个体ｌ、子个体２、予个体３、子个体４……）。这撵熬过程德环执行，壹翼瀵是钱纯准籍为壹。２．４遗传算法的特点我们知邋，传统的优化方法童娶有三种：枚举法、启发式算法和搜索算法：①枚举法；枚举出可以解集仑内的所有可以解，以求出精确最优嬲。对手连续函数，该方法要求先对箕逡行薅散亿处理，这撵藏霹缝嚣离教楚理瑟汰远这蚕至《最优解。鼗岁｝，当枚举空间院较大时，该方法的求解效率比较低，有时候甚至在目前最先谶计算机上也无法求解。②启发试算法：寻求一种能产生可以解的启发式规则，以找到一个最优解或者近似最优解。该方法的求解效帮比较高，但对每一个需求解的闯题必须找出其特毒夔寝发式羧照，这令建发式黢翅一般无逶爱蠖，零逶会手其毽翅题。③羧索黪法：寻求一种援索舞法，该算法在可行解集合的一个予集内送行援索操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了～定能够得到问题的最优解，但若适当地利用一些启发知识，就Ｗ在近似解的质量和效率上达到一种较好的乎衡。７

重庆大学硕士学位论文２遗传算法的设计思想随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决搜索和优化问题的通用方法，遗传算法正为我们提供了一个有效的途径，它不同于传统的搜索和优化方法。主要区别在于：①自组织、自适应和自学习性（智能性）。应用遗传算法求解问题时，在编码方案、适应度函数及遗传算法确定后，算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为“适者生存，不适应者被淘汰”，因而适应度大的个体具有较高的生存概率，通常它们具有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化问题。排课问题恰恰就是这样的问题，所以用遗传算法去排课是最好的方法。②遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即遗传算法本身非常适合大规模并行。最常见的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信（独立的种群之间若有少量的通信一般会带来更好的结果），等到运算结束时才通信比较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率没有太大影响。二是遗传算法的内含并行性。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模ｎ成比例的计算，但实质上已进行了大约Ｏ（ｎ３）次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。③遗传算法不需要求导或者其他的辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。④遗传算法强调概率转换规则，而不是确定的转换规则。⑤遗传算法可以更加直接地应用。⑥对给定的问题，遗传算法可以产生许多潜在解，最终选择可以由使用者确定。２．５遗传算法的基本操作遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多不同的方法，如下面所述。①选择选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。首

重庆大学硕士学位论文２遗传算法的设计思想先计算适应度：１）按比例的适应度计算；２）基于排序的适应度计算。适应度计算之后是实际的选择，按照适应度进行父代个体的选择。可以挑选以下算法：１）轮盘赌选择；２）随机遍历抽样；３）局部选择；４）截断选择；５）锦标赛选择；在选择操作时会出现几个问题：乱在遗传进化的初期，通常会产生一些超常的个体，这些异常个体竞争力很ｂ．在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小上述的问题，我们通常称为遗传算法的欺骗问题，而适应度函数的设置就是遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用１）直接以待求解的目标函数转化为适应度函数。即：若目标函数为最大化问题Ｆｉ“ｆ【ｘ））＝ｆ【Ｘ）若目标函数为最小化问题Ｆｉ“ｆ（ｘ））＝一ｆ（ｘ）这种适应度函数简单直观，但存在两个问题，其一是可能不满足常用的轮盘２）若目标函数为最小化问题，则：蹦鞴＿［ｃ：嚣㈣姐一９突出，从而控制了选择过程，影响算法的全局优化性能。时，继续优化的潜能降低，可能获得某个局部最优解，这不是我们所期待的。为了避免这些问题的产生。因此，适应度函数的设计是遗传算法的一个重要方面。种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。适应度函数基本有以下三种：赌选择中概率非负的要求，其二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，从而影响算法的性能。其中Ｃ。。是舡）的最大值估计。若目标函数为最大化问题，则

重庆大学硕士学经论文２遗传雾法麴设诗愚恕Ｆｉｔ（ｆ（ｘ）产ｆ婀一Ｇ一，取）＞ｃｍ“。０，其像这秘方法燕瓣第一静方法懿改遴，霹敦髂为“爨隈羧造法”，毽寿时存凌爨限篷预先信诗露蕊、不精确的目逶。３）若目标函数为最小化问题：Ｆｉｔ（ｆｉｘ））＝１，（１＋ｃ＋ｆ（ｘ”Ｃ≥Ｏ，ｃ＋ｆ（ｘ）－兰。若目标函数为最大化问题：Ｆｉｔ（ｆ（ｘ））＝ｌ／（１＋Ｃ一援ｘ））Ｃ≥瓴Ｃ－ｆ（ｘ）≥Ｏ这耪方法与第二静方法类酝，Ｃ海嚣括函数雾陵豹僳孝继诗篷。适应度瞬数设计应该满足以下几个条件，它应该非负、连续、最大化、单值的：能够反映解的优劣程度；应该尽量简单，计算爨尽量小。②交叉藏簇邈重组基毽羹缀楚结合来童父戎交熬耱嚣孛戆覆塞产囊灏煞今薅。依据令髂缓鹃表示方法的不丽，可以有以下的算法；１）实值煎组·离散爨组；●中闻黧缀；·线缝鬟缀；●扩展线馁重组。２）二遴制交叉·单点交叉；·多点交叉；●均匀交义；·洗簿交叉；●缩小代理交叉。③变异交叉之餍予代经历的变异，嶷际上是子代基因按小概率扰动产生的变化。依据兮薅编羁袭零方法戆不嚣，霹鞋蠢以下豹算法：１）实俊交雾；２１二进制变异。另外的操作觎括：扎交叉概率（Ｐｃ）和变异概率（Ｐｍ）

重庆大学矮士学像论文２蘧姥雾法豹竣诗思想交叉操作和变异操作并不是对所有个体都发生，而是根据相应的概帮。交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，Ｐｃ越大，新个体产生的速度就越快，然而，遗传模式被破坏的Ｗ能性也越太，搜褥其蠢意适应疫戆令傣缝掏缀抉裁菝破坏。艇蹩麴栗Ｐｅ过夺，会傻羧索过程缓慢，醵麓停滞不藏。对予变弊概率Ｐｍ，强聚遥小，裁不易产生赣靛个俸结构，如果Ｐｍ取值过大，那么遗传算法就变成了纯粹的随机搜索算法。针对不同的优化问题，鬻簧反复实验来确定Ｐｃ和Ｐｍ。ｂ．编码（Ｅｎｃｏｄｉｎｇ）遗传算法孛进化过程是建立农编码辊割基础上的，编码对于算法盼黢鼹懿搜索爱力秘秘群多样往等影穗攫丈。如何将问题的解转换为编码袭达的染色体是遗传算法的关键问题。Ｈｏｌｌａｎｄ的编码方法是二进制０．１串表达，熊优点是编码、解码操作简单，交叉、变弗等遗传操作便于实现，而且便于利用模裁定理进行理论分析锌；其缺点是不便于反映所求问题的特定知识，对于一些连续溺数的优化问题，潮子遗传算法的ｌ媳机特性使萁最熬搜索黢力较差，对于一整多缓、离穗度要求熬逡续函数髋纯，二滋裁缡玛存在着连续薮数离敖亿时静映射误爱，个俸编码串较斑时，可能这不至ｌ耪发要求，个体编码串较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩大，从而造成遗传算法的性能降低。后来许多学者对遗传算法的编码方式进行了多种改进，例如，为提黼局部搜索能力，提出的Ｇｒｅｙ码等。遗传算法黪一般流程匿如麓２＋２所示。第ｌ多；夔秘产生令体数嚣～定豹裙始静饕，褥个令俸表示受染色髂懿基毽编码：第２步；计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代袭的最优解，并结束计算，否则转向第３步；第３步；依攒适应度选择再缴个体，适应度高的个体被选中的概率搿，相反，适应度低鹣令侮霹辘谈海汰；第４步：按照一定的交叉概率鞍交叉方法，生成藏稳个体；第５步：按照一定的变异概率和变异方法，生成新的个体；第６步：豳交叉和变异产生新一代的种群，返回到第２步。遗传算法中的优化准则，一般依据问题的不同肖不同的确定方式。例如，可班采用以下的准嬲之一幸＃为判断祭终；１）释群审今俸熬最丈适应发怒避预先设定篷；２）种群中个体的平均适应度越过预先设定值；３）世代数超过预先设定值。

重痰大学硕士学爱论交２遗传舞渡瓣设计愚怒翻２．２遗黄算法的漉穰翻Ｆｉｇｕｒｅ２．２Ｔｈｅｆｌｏｗｃｈｍｔｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ２．６经典遗传算法存在的缺陷及改进随着理论和应用研究的日益深入，研究者们己经意识到，简单采用网定不变的进化策略的遗传算法对复杂的暾爝场合效果并不理想，传统的遗传算法逐渐暴露窭一些缺杰。为提褰遗转算法戆投戆，诲多磅究者恐经致宠予这些趣嚣戆繇究，并提出了一系列有效的解决方案。２．６．１初始种群的均匀化改进初始种群的特性对遗传算法的计算结果和计算效率均有重要影响，臻窟现全局最优，初始种群在解空间中应尽爨分散。而经典的遗传算法中，初始种群是随机产生豹，这季中缒壤缝裁可麓导致鹚媲黪群在磐空窝分蠢熬不均匀，簌露影拣算法的往麓。霞魏，在产生裙始弹群鞋雩，应尽量使它筠麓分布在整个磐空蓠审。一种方法楚，为初始种群中的个体之间设置一个距离限制，要求入选柳始种群的各个体之间的距离必须大予这个限制距离，这样就能保证初始种群的个体之间有较明显的麓别，使它们能较均匀地分布在解空间中，保证了初始种群禽有较１２

重庆大学硕士学位论文２遗传算法的设计思想为丰富的模式，从而增加搜索收敛于全局最优解的可能．另一种方法是，首先将解空间分割成若干个子空间，对每个子空间进行初始种群选择，然后将每个子空间的初始种群进行合并，生成总的初始种群，那么这个种群中至少包含了来自不同子空间的个体。２．６．２自适应交叉概率和变异概率的改进前面我们说到了交叉概率和变异概率的选择对遗传算法非常重要，无论取值过大和过小都对算法产生不利影响，但是我们很难对一个优化问题确定一个合适的交叉概率和变异概率，因为遗传环境在不断的动态变化，所以，Ｐｃ和Ｐｍ应该能够随适应度自动改变，当种群各个体适应度趋于一致或者趋于局部最优时，使Ｐｃ和Ｐｍ增加，以增强新个体产生的能力；当群体适应度比较分散时，使Ｐｃ和Ｐｍ减小，加快群体的收敛。适应值高于平均适应值的个体，对应于较低的Ｐｃ和Ｐｍ，使该解得以保护进入下一代；适应值低于平均适应值的个体，对应于较高的Ｐｃ和Ｐｍ，使该解被淘汰掉。交叉概率和变异概率的这种自适应调整在保持了群体多样性的同时，也保证了遗传算法的收敛性。２．６．３选择算子的改进在各种ＧＡ选择策略中，基于个体适应度的比例选择最为常用，该策略算法简单，但是比较容易引起“未成熟收敛”和“搜索缓慢”等问题。“未成熟收敛”就是连续的几代种群中的最优染色体没有任何进化，或者各染色体之间过于近似等。在求解多峰值函数的优化计算时，经常只能找到个别的几个最优解，甚至往往得到的是局部最优解，而我们希望的是得到全局最优解。解决这个问题的一种方法是采用基于小生境技术的选择操作。在生物学上，小生境（Ｎｉｃｈｅ）是指特定环境中的一种组合功能。小生境技术就是将每一代个体划分为若干类，每个类中选出适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过交叉和变异产生新的种群。小生境的模拟方法主要建立在对常规选择操作的改进基础上。Ｃａｖｉｃｈｉｏ在１９７０年提出了基于预选择机制的选择策略，其基本做法是：当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代个体才能代替其父代个体而遗传到下一代种群中，否则父代个体仍保留在下一代种群中．由于子代个体和父代个体之间编码结构具有相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效地维持种群的多样性，从而避免产生局部最优解，改善未成熟收敛。另一种方法是引入“遗传一灾变”算法，在ＧＡ的基础上，进一步模拟自然界中的灾变现象，以提高遗传算法的性能，尤其是解决重要的未成熟收敛问题。当判断可能发生了未成熟收敛时，施以灾变来改变现状。灾变的形式很多，可以突然增大Ｐｍ，或对不同个体实施不同规模的突变，以产生大量的后代。用灾变的方

重庆大学硕士学位论文２遗传算法的设计思想法可以打破旧有基因的垄断优势，增加基因的多样性，创造有生命力的新个体。第三种改进方法是引入浓度选择机制，与适应度比例选择机制相结合，采用加权平均的方式来进行选择。这个方法由下面的式子来表示，其中Ｐ表示个体选择的概率，Ｐｆ表示适应度概率，Ｐｄ表示浓度概率，ａ表示适应度概率所占的比重。Ｐ＝ａｘＰｆ＋（１一ａ）×Ｐｄ这个式子可以确保适应度高的个体，又抑制浓度高的个体，以保证个体的多样性，改善未成熟收敛。２．６．４交叉和变异算子的改进遗传算法通过交叉和变异这一对相互配合又相互竞争的算子，使自身的搜索能力得到快速提高，交叉操作在遗传算法中起全局搜索的作用，它是遗传算法的核心遗传操作。变异操作在遗传算法中起局部搜索的作用，当搜索陷入局部解而不能由交叉解决时，配合有效的变异可以使之跃出局部解。但是后期的变异可能破坏已经建立起来的最优解的雏形。因此，交叉和变异应很好的配合，不能盲目的进行操作，例如，采用自适应的算子，将进化过程分为渐进和突变两个不同的阶段，渐进阶段强交叉，弱变异，强化优势型选择算子：突变阶段弱交叉，强变异，弱化优势型选择算子。一种方法是：建立一个收敛程度参数ｂ，ｂ＝Ｆ仃。一Ｆ其中：Ｆ一为某代中最优个体适应度，Ｆ为此代种群平均适应度。因此ｂ近似反映了种群的收敛程度，ｂ越小，个体间适应度相差越小。ｂ越大，个体特性越分散，Ｐｃ，Ｐｍ应与ｂ成反比．同时为防止破坏全局最优解，对不同个体，Ｐｃ和Ｐｍ应不同。遗传算法能够很快地找到最优解的９０％，但是剩下的寻找最优解的工作却要花费相当长的时间。２．６．５并行遗传算法尽管单一种群的遗传算法很强大，可以很好的解决相当广泛的问题，但采用多种群（子种群）的算法往往会获得更好的结果。每个子种群象单种群遗传算法一样独立地演算若干代后，在种群之间进行个体交换。这种多种群遗传算法更加贴近于自然中种族的进化，称为并行遗传算法（ＰａｒａｌｌｅｌｉｎｇＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ．ＰＧＡ）。遗传算法发展的二十年里，针对各种不同领域，不同模式的优化问题，出现了很多变形和改进，经典的遗传算法为我们提供了一个平台，在这个平台上可以搭建各种各样的模型。随着遗传算法应用领域的扩大，相信更多的改进和变形会出现，遗传算法家族将越来越壮大。介绍完遗传算法，以及遗传算法的各种改进后，下面我们就来介绍遗传算法在课表问题中的应用，以及针对课表问题，对遗传算法做的变形和改进。１４

重庆丈学矮圭学经论文３辩瀚安撄箨法３时间安排算法毫校熬瓣潆是～顼费酵费力懿繁琐工终，它牵涉至ｇ全搜熬颊生巍掰露谖程、所有教室。摊漾在整个过程孛充满了矛詹运魂，其审惫疆上课班缓、耩殍谍程、任课教师一ｋ课时间、地点这个赢个方面在排列组龠中所发生的冲突和矛盾现象。课程门类多、教师少、教室少是摊课时发生冲突和矛盾的主要因素，丽溅缀多、教室少则是矛盾的重要方面，摊课就是要处理教学环节中的各种矛盾。接误牵涉瀚因素缀多，毽都遵循这样鲍原煲｜ｊ：谖袋装寿秘于教学设餐熬充分蠢瘸，要骛会教学瘫律。３．１排课需要考虑的约束因素排课是将教师与学优在时间和空间上根据不同的约束条件进行排列缀合，以搜教学正常避彳予，这里约束条件象要是为了避免冲突。冲突，包含的痰容缀多，蔻乎发生在矮露嚣令或多令攘漂渗及煞嚣素之闯。避兔狰突是箨谦楚题审黉缎决的核心问题。只有在满足全部约窳条件和避免所有冲突的基础上，才熊僳证整个教学计划正常进行，而对教师、激室、学生及时间镣几部分资源进行最优化组合配置，才能保证充分发挥各资源的优势。我们把摊漾过程中的约束条件分为三类：基本磁约柬、硬约束和软约荣。其孛基奉疆终塞蔫海羧簿、学生秘教室在嚣空土不藐发象狰突，宅是赫潆怼缓孛最基本盼约束条伴；硬约束是根掭学校的实际情况，捺谦时必须遵循的原刚（如：我校中午和周米不排课，星期二下午不排课等习惯）；软约束是指排课过稷中满足更佳但不满足又无妨的约束条件，它们的违反与否往徒与排课实际情况相笑。在三类约束条件之中，前两者是衡熬摊课方案是否切实Ｗ行的标准，软约束是衡量ｌ萋漂方案襞劣熬耩准。荬羲；毽分捌翔下：①基本硬约束：１）在同一时间同一学生不能上两门不同的课程；２）在同～时间同一教室不能寂排两门不同的课稷；３）在嗣一时间同一教师不能上两门不同的课程。②硬豹絮；１）上课绞犬爷为单位诗舞（铡斑：上午分ｌ、２犬第）；２）星期二下午不排课，星期六、日全天不排课；３）课程的学时在周分布上有～定的规律（例如：每周上３次的课程，一般是星期一、三、旋这三天安排上课镣）；１５

重痰大学硬士学襞论文３孵麓安镖算法４）某些课程有自己的特定资源（例如：英语专此课程必须有独立的听力系统等等）；５）教室空间必须足够大，能够容纳上课（包括禽班）的学生；③软约窳；１１班级谍稷袭在周安排上瑟瑟鳖分布均匀；２）一周课袭中每个时间有一定的优度；３）教师不推荐在时间上连续上课；４）教师对上课时间存在一定的喜好（例如：某老师喜欢下午上课等镩）５）班级躐巍上潆建煮尽可笈避。怒要接激簸为理想静谋表，熬躲须注意每震一次镶繇我捧谦擎往时藤攫，学生的最佳用脑时间以及师生在教与学过程中的心理因索等，坚持合理间隔，充分利用教室空间。每个班的每门课程在一周内要间隔开上，让学生分散理解和记忆，因为按照记忆——遗忘规律，一次记忆太多相似的内裙并不能记住，所以，要注意蛙质不司焱，强调个性，才能识率。医既，应该改燹整个接捌，恕那黧个性强静，与众不醚瓣方嚣，巧妙黧醵安摊，班瑟作秀记忆鹣奖壤，胃浚稷姆镳箍嵩学生的学习效率，是一种比较好的摊谍方法。在以往的管理中，传统的排课经验很值得继承和发扬，它反映了教学涌动的特点，遵循了教学规律，具有酱谪的实用性。判定一令漾表是否科学台理，除了继承传统编摊外，还应该按照教学心理学懿基本藩理，辩有效薅闯痰入箍熬记忆特点、舞生懿教学心理特熹耧瀑纛鑫隽戆特点，进行科学豹综合分析，选择鬣优的方案。摊课方案是否最优有下麟的评判标准：①时间间隔大脑对“弹头”和“结尾”的事物识褥最清楚，我们可以运用这个规律来安摊学习懿嚣，毽藏怒褥潆翟安接在歪鬻戆５转分铮内，不要港续主，毒逶当豹潆潮傣怠，以增加“开头”鄹“结尾”，以晓来掇麓学习效果。②时间冗的选择早上是～必中最好的学习时间，人经过一夜的睡眠，紧张的精神得到放松，神经系统的疲惫也随之消失，上午入的思想最集中，容易接受和记忆知识。蔗下午效率会穗慰辫鬣，酝鞋上午戆辩麓俊予下午，教忿，疲器量跨重要帮羧赡静潆程安排在上午＋③时间元顺序以每周需隳安排两次课的课稷为例，从星期一到凝期五中选择两天泉进行安排，这两天中可以任意安排两节谍，有银多种安排方式，但不同的安排方式之间

重庆大学硕士学位论文３时间安排算法也是存在优劣差异的，在安排时要选择一个较为合适的时间。３．２人工排课的工程分析和模拟人类思维过程是非常复杂的行为至今仍未能被完全解释，但我们可以按照人类的思维过程来编制计算机程序，从而实现计算机模仿人类的行为。计算机对课表的求解实际上是对人工排课过程的模拟。根据我们学校的实际情况，作如下设定：每日最多上５次课，其中上午２次（第一、二大节），下午２次（第三、四大节），晚上１次（第五大节），如表３．１所示。表３．１一周上课安排表Ｔａｂｌｅ３．１Ｔｈｅｔｉｍｅｔａｂｌｅｆｏｒａｗｅｅｋ星期一上午第二大节第三大节下午第四大节晚上第五大节第一大节星期二星期三星期四星期五每课次２学时，不分单双周。教学计划中有的课程每周上１次，有的每周上２次，有的每周上３次，我们分别将它们叫做１类、２类和３类课程。举例如下：当前课表如表３．２所示，现在需要将一门３类课Ｃ填入其中。表３．２当前课表安排情况Ｔ｛｜ｂｌｅ３．２Ｔｈｅｃｕｒｒｅｎｔｔｉｍｅｔａｂｌｅｆｏｒａｗｅｅｋ星期一上午第一大节第二大节下午第三大节第四大节星期二星期三星期四星期五晚上第五大节排课人员根据要求，认真分析课表后将课程Ｃ填入表中，如表３．３所示：１７

重庆大学硕士学位论文３时间安排算法表３．３课程ｃ的一种排法Ｔａｂｌｅ３．３ＯｎｅｏｆｔｈｅａｒｒａｎｇｅｍｅｎｔｆｏｒｃｏｕｒｓｅＣ星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节课程Ｃ星期二星期三星期四星期五课程Ｃ课程Ｃ我们知道，３类课在课表中的编排方案有很多种，在众多的方案之中，排课工作人员会记住一些比较成功的典型方案，当开始排３类课程时，他们第一时问所考虑到就是那些典型方案（如表３．４）：表３．４课程Ｃ的另一种排法Ｔａｂｌｅ３ＡＡｎｏｔｈｅｒａｒｒａｎｇｅｍｅｎｔｆｏｒｃｏｕｒｓｅＣ星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节课程Ｃ旱期二星期三课程Ｃ星期四星期五瀑程Ｃ。一但是表３．４的方案是无法实施的，因为星期五的位置已经排课，这会引起冲突，必须放弃这个方案，然后继续找其它方案，这个过程不断重复，直到找到如表３．３的成功方案。该方案没有时间冲突，而且符合最优时间。分析人工排课的过程，可以得出如下其特点和结论，其特点为：扎无冲突性。按照上述人工排课的步骤，编排的课表不存在冲突，即没有～个教师同时上一门以上课程、一个班级同时上一门以上课程、一个教室同时上一门以上课程的冲突。．ｂ．较好的局部最优搜索能力。人工排课过程中，对于当前的排课课程，在班级课表、教师课表和教室课表中，能够搜索出目前最好的排课时间和教室，即较好的教学效果时间、合理的教室、满足教师的需求等ｃ．缺乏全局最优搜索能力。排课问题属组合优化问题，排课班级、排课课程

重痰大学醺士擎使论文３蜡麓安撰舅法和任课教师的数量较多，所有的谍程都在教师、教室等资源上共享，前期排课与后期的课程安排有着密切的联系，人工排课在局部范围内能够将课程安排在最佳的时间和教巍凝，但在全局范围璧菇不具有这种能力，即前期的排课对于羼期的接漂壤嚣没蠢宠分夔舔诗，霉憩逡成瓷源在整转分繇上熬不平鸯，会逢羧爱蘩｛錾的谋程可孬德不合理。结论为：乱方案的选择过程不是按课液的空间顺序，而怒按照方案的优劣顺序选择。ｂ．课表的编排方案具有多样化的特点，可以同时有好几种方案供选撵，最后只是选择了襞貔戆一秘方案露基。ｃ．在摊漾辩除了考虑方案零鸯豹优劣程度之强，述要考虑谋程的娥荔程度等其它因素。ｄ．方案的好坏除了一些公认的规律之外，有些魁童观上的喜好而已。￡人工排漾的标准是“可行、☆理’’，一般没有定义最优方案的标准。３．３镰表的不确定性和维会游题根据分析人工排课的过程，灾际上是一种数学上的组合问题，主要依靠约束条件来实现，如果约束条件充分，组合数就唯一被确定，但在实际工作中，随着组合方案数的增加，问题变得十分复杂。我们前面说过课程有ｌ类、２类和３类，为了数学上袭达方便，我｛『ｊ将谍类定义如下：１类为ｘ炎，２类为Ｙ类，３类为ｚ类，全蜀鹣漾袋空鞲ｒｌ共有５×５＝２５穆（每溺按星麓～至星麓五诗雾），闲忿产生的组合数如下：Ｘ（ｎ）＝Ｉ‰１Ｙ（ｎ）＝Ｃ，Ｚ（ｎ）《搿其串ｎ＝ｌ，２…。，２５扶上面可娃褥出：①如果课类相同（譬如都为每周１次课的ｘ擞），则课表空格越多，相应的编排方案也越多；②如果瀑类越高（譬如每周３次课的ｚ类比每周１次课的ｘ类离），则随课表熬空貉增麓，壤捧方案数迄瀵熬德越侠；③如栗漾裘空格数相两，刚谍类越高，裙应的编摊方案也就越多。编排方索越多，从中选择最优方案时需要的约束条件就越多，求解就越难。如果约束条件不充分，解就可能不是唯一解，而是一个集合，并且各个方案之间的差异将被忽略，这种忽略称为方案优劣差异的融合，藏是这种融合，使得课表

重痰大学硬士学攮论文３嚣重麓安接算法出现不确定性。课表集怒矢量集，计算公式为：Ｆ＝Ｃ。＊－－ｍ！／（ｎＩｘ（ｒｎ—ｎ）！）其中Ｆ为方案数，ｎｌ为空间向量数，Ｎ为每周的谍次数。计算结果如袭３．５获示：袭３．５课表方案数Ｎｌ２３４５Ｆ（ｍ＝１５）１５１０５４５５１３６５３００３Ｆ（ｍ＝３ｍ３０４３５４０６０２７４０５１４２５０６麸上表可鞋餐蹬：当Ｎ＝ｌ时，Ｆ（ｍ＝３０是Ｆ（ｍ＝１５）的２倍，Ｎ＝３时，Ｆ（ｍ＝３０）是Ｆ（ｍ＝ｌＳ）的９倍，但当Ｎ＝５时，Ｆ（ｍ＝３０）是Ｆ（ｍ＝１５）的４７倍。Ｎｌ蝴时，Ｆｌ＝１０５．Ｎ２ｍ５时，Ｆ１－－－－－１４２５０６；所以，Ｎ２是Ｎ１的２．５倍，而Ｆ２是ＦＩ的１３５７倍。这秘空嬲；惫璧数稍徽增期，或密漂程震次数稍微增宓曩就弓ｌ起课表编攘方案数量急尉增燕鹣凌象，称为‘‘缀合攥盔擘”，在解决深表阕簇辩是无法霞逶“缀会爆炸”的，因此，怎样解决这个问题是课袋编排中一个重骚经务。同时，排课空间向量数少量减少（或者课程周次数少爨减少）会引起组合方案的急剧减少的现象称为“组合塌陷”。上面这两种情况都要想孙法解决。由翦嚣的分辑褥知，课表阀艨实质上是一个组会艘划润题，如果怒找剿浸挠解，必须存懋够戆终束象｛孛，餐瓣学部分属于天文藏耱翁潆表竭踅，不爵熊我囊充足的约束条件，而且由于课表方案优劣差异的融合，能够找到的解将会怒～个解的集合，并熙这个集合中所有的解都是可行的。因此，我们必须放弃“绝对最优”解的方案，除了最基本的“教师、学生、教室在任一时间的安排只能出现一次’’的硬性约束条件强，课表只要能满足“Ｗ行，合理’’的要求魏行了。受｜筵，我雾】霹辍确定诗算蘩‘簿谍饔嶷凌豹死令基标：①课袭怒没有冲突的，是可行的；它表示课袭符合基本的原则骚求，没有无法执行的冲突，不会出现诸如一个教室同时上两门以上的课程的情彤。②课裘鼹青较高的质量；２０

重痰大学硕士学像论文３酵鞫蜜捺算法课表的斌量高低根据下面几个标准来评判：１１各门谍程在一周之内应间隔安排；动重要的、繁难的课程应安摊在上午１，２节遴纾，次之豹课程安排其它时瘸；３）俸育谍应安排在上午的３、４节或者下午，两鼹体育谋之屡不宣孬安排上谋：４、避免綮难的课程连续上，成间隔和穿插安排；５）对连续的课程安排豹教室不能问隔太远，以方便师生及时到达教室；国实验、童覆等实黢毪漯瑕旋该安撵在下午或浚上进辱；乃对令羽老师盼酶殊要求要器量满足。③课袭中不存在或仅有很少的“漏课”。所谓“漏课”是指因教室安排问题使得某课程没有办法安排教室上课。３。４萎｝课阉题的数学模型排课藏瑟楚～令寄约束豹多瓣标健纯霹题，嚣藏撵漾蠲逶貔穰鍪是蠢约束鳆多目标优他横嬲，其中约束条件可以通过约束满足模溅来说明。３．４．１排课问题的优化求解横型假设排课问题中，有ｎ个决策变量参数、ｋ个目标函数和ｍ个约束条件，目标蘧数、约束祭传籁决蓑交量之淘爨缀数关系。刘赫谖翊题的最优纯模型麴下：ＭａｘｉｍｉｚｅＳｕｂｊｅｃｔｔｏＦ嚷ｘ两《ｘ＞是￡ｘ），．．。，ｆｋ（ｘ）啾）＝（ｅｌ（ｘ），ｅ２（ｘ），．．．‰（ｘ））９《３．１）（３．２）其中ｘ＜ｘｌ渤，¨．，ｘｎ）∈）（＇ｙ＝（ｙｌ，ｙ２＇…，ｙｋ）∈Ｙ。这里ｘ滏示排课问题的决策向量，ｘ表示决策向凝Ｘ形成的决策空间。ｘ的元素ｘ，，Ｘ２…。，ｘ赫出影响捧课方寨饯劣的因素的各个变量组成。主要是融闯和教室嚣方嚣熬掰豢，爨翔在薅凌方瓣，踅栗蒋薅舞接瀑凌缝织形式来麓分，爨ｌｌ皴安排时间所处的节ｈｉ，时段ｐｉ、天ｄｉ釉周次ｗｉ等，都Ｗ作为决策向量的元索；再例如在教室方丽，教室的类型鹏、襻蕊ｒｑ、所在的校区域碣等也都是决策向量的元素。决策向爨的元素个数是变化的，一般来说，随着嗣标向量维数的增加，决策向量的元素个数也增加。由上面可以看出，由于ｊ｛｝课黢素之间的关联导数了ｘ的维鼗霉零｛爨大。终衷条磐《ｘ）反获了接涤蘑题懿壤接娥潮，礁定７决策随爨豹霉行的取值范围。Ｙ表示目标向量ｙ形成的目标空间。维数随实际对乏解问题情况以及课袭评定准则的变化而变化。

重庆大学矮±学鼹论文３黠麓安捧算法３．４．２排课问题的约束满足模型教师集合Ｔ－－｛Ｔｌ，Ｔ２，．．．，Ｔｔ）班级集合Ｃ＊｛Ｃｉ，Ｃ２，…Ｉｃｃ）诗翻集会ｌ产｛珏，ｂ，…，ｂ）（３．３）（３。４）《３．５）（３．６）（３．７）教室集合舡ｌＲｌ，Ｒ２，…，＆＇合班集合Ｇ＝（Ｇｌ，Ｇ２，．．．，Ｇｇ）一般地，如果教师Ｔｉ被指定绦合班集合中的Ｇｉ授课，则定义粕＝１，否则ａｌｊ－－０；同样，如果教９ｉｌｉＴｊ被指定给班级ｃｉ授课，贝１ｊｂ矿ｌ，磷则定义ｂ霉＝０。定义礴个需求矩蓐。ａｌｌａ２１撑１２ａ２２…ｇｋ…４２，Ａ＝（３．８）ａ西ａ９２…口掣ｂｌ｛ｂ１２…气…％…ｋ◇．劣‰如ｋ钆：上面的Ａ、Ｂ矩阵可以确定班缀的合班情况和教师的授课情况，也就怒猩数学豹意义上说明了当前所有的教师麓班级之闻的关系。懿采簇交漂袭土豹王雩筝天数凳ｄ，一天黟节数秀ｓ，骥褥弓｜入漂表冬ｙｌｌ痨哟矮薄Ｍ§而１Ｘ１２蔗就…‘ｄ…Ｘ２ｄＭｓ＝Ｘ２１（３，１０）＂ｇｓｌＸｓ２…Ｚ括其中Ｘｉ３滚承在ｊ’周的第ｉ’节蠢漾，否剡税为空闲·如果按照矩阵Ａ中开课计划进行排课，在课表矩阵中实时记录当前教师、班级和教师的时间段占用情况，则埘得教室安排矩阵№和教师—班级安排缀阵ＭｔＸｔｌｌ—Ｉ：…而博鼍２１萎２２…而“ｘｔｎｘＩ｜２…ｘｔｄ尚（３．１１）Ｓ，

重痰大学颈士学位论文３瓣怒定｛嚣算法Ｘｌｌｌ２…嚣‘ｌｉｄ五１２２…Ｘｌｌ２ｄＳ１２···５＇１－Ｍｔｃ＝Ｘ｜１ｊ２￥２１···Ｘｔｌｓｄ（３．１２）ｓ赶…Ｓ２ｔＳｃｌ其中Ｍ，中ｘｉｌｆ－１表示教室Ｒｉ在周ｊ’的第ｉ’节已经被占用，否则认为空鬣。Ｍ。中苟《一１袭承教师弓绘班级ｃｉ豹授课安排时间中有周ｊ’的第ｉ’节，否则认为没有。毒了上甏瓣撬透，裂教努每繇令舞藏（周ｊ’豹第ｌ’蔫）至多安蓑｝一次援潆霉以表达为：∑ｘ∥，茎ｌ同理，班级ｃｊ谯时间（ｊ’周的第－ｉ，节）至多安排一次Ｊ：课可表达为（３．１３）∑ｘ∥，’ｓｌ对手教室戳凌辩阉≈，羯魏第ｉ一嗲≥楚多安撵一次上漾逡骞ｘｎ蟠＿ｌ（３．１４）（３。１５）（３．１３）、（３．１４）、（３．１５）式给出的只是排课问题中最朴素的数学模型，宦们的满足仅仅是保诞丁教师、学生和教庭不发生冲突。其中（３．１４）保证每个班级在每个时间最多上一次课的同时也杜绝了当有多个班级参加嗣一次授课时可能襻猩冲突熬现象。网３．１排课算法图Ｆｉｇｕｒｅ３．１Ｔｈｅｔｉｍａａｂｌｉｎｇａｌｇｏｒｉｔｈｍ

重庆大学硕士学位论文３时间安排算法有了上面的情况介绍，我们可以设计课表的编排方法，其主要分两步，先是对课程进行时间分配，然后对课程进行教室分配，算法见图３．１根据排课算法图可以看到，排课算法的作用就是将无序的原始数据（也就是教学任务）进行一系列加工操作，进而生成有序的最终课表，在这其中包括了两个主要算法：教室安排算法和时间安排算法，正是这两个算法分别把时间和教室的约束加入到教学任务中。从而使生成的课表有效。同时我们看到，基础数据库、排课知识库和策略库都为排课算法提供了有效的策略依据，其中排课知识库和策略库是排课工作人员的长期排课经验的结晶。３．５课表问题中的遗传算法设计课表问题中，遗传算法应用在了两个层面，第一个层面是局部上，基于某一单门课程的时间安排，它的工作是从所有的课节空间中选取近似最优的组合解，我们称这个层面上的问题为局部课表问题。对一门课程找到了近似最优的组合安排方案以后，并不能代表为整套课表找到了近似最优的安排方案，课程安排的先后次序同样决定了整套课表的质量，因此，第二个层面就是基于整套课表，按照怎么的顺序来排课，能够得到一套满意度最大的课表，我们称它为全局课表问题。３．５．１局部课表问题的遗传算法设计：计算公式为：Ｆ＝Ｃｍ＂－－ｍ！／（ｎｉｘ（ｍ—ｎ）！）其中Ｆ为方案数，Ｍ为空间向量数，Ｎ为每周的课次数表３．６组合数随周课次的变化Ｔａｂｌｅ３．６ＴｈｅｃｏｍｂｉｎａｔｉｏｎｎｕｍｂｅｒｗｉｔｈｔｈｅｃｌａｓｓｃｈａｎｇｅｆｏｒａｗｅｅｋＮ１２３４５Ｆ（ｍ＝２５）２５３００２３００１２６５０５３１３０对于局部课表问题，就是在每周的课节空间（天数Ｘ节次：５ｘ５＝２５个课节）中，寻找一种合理的、满意度较高的课节组合。表３．６列出了全部组合数。从上表可以看到，当Ｎ达到５时，组合数Ｆ达到了５ｘ１０４，这个规模会随着Ｎ的增长极度膨胀，在如此庞大的搜索空间中寻求最优解，对于常规方法而言，存

重痰夫学颈圭学经论文３封瓣安撰箨法在着诸多的计算困难，而遗传算法的搜索能力可以解决课表问题，因此，我们引入了遗传算法。①编码（Ｅｎｃｏｄｉｎｇ）绽码方式必缓毙够毽含这转镶慧。垂于漂表超嚣瓣独特缝，采惩砖绫逡传算法中的二遴制编码并不是缀适合，嚣为课表空间是二缭鲍，包含星期和节次，焉一个二进制串很难表示出这两种信息，因此，需要一种新的编码方式来袭豕遗传基因。我们采用了一种叫做布尔缀阵的表示方法来对课表基因进行编码，如表２，这个布尔矩阵袭示对一门课程的一种分配方式。矩降掇坐标为星期，纵嫩标为节次，萁串０凌零没有安簿课程，ｌ凌示安嚣潆程。表３．７谋表染色体编码Ｔａｂｌｅ３．７ＯＯＯＯ０１Ｏ０Ｏ０ＯＯ０ＯＯＣｈｒｏｍｏｓｏｍｅｃｏｄｉｎｇｏｆｔｉｍｅｔａｂｌｅ１ＯＯ０Ｏ０ＯＯＯＯｌ０Ｏ０ＯＯＯＯ０它表示，该门课程安排在了周：第一节、周四第一节和周六第二节。出糍尔矩瘁囊表示豹缓璐空藏与解空瓣怒一一对应豹，任露一耪漾表静舞鬻安接方案繇可以在这个编码空间中找到一个对应。②适应魔函数（ＦｉｔｎｅｓｓＦｕｎｃｔｉｏｎ）课表问题中，对一种安排方寨优劣的判定很复杂，其中包含众多来自课程、教师、教室的舰她和要求，一类为规则，另一类为要求。适应度函数的设计是课表露逶邃簧雾浚设诗夔关键，嚣隽它走法象受藤撵瓣遴那么燕擎瓣惩一令凌达式就可以表示，谦表方案的适应度体现在很多方面。大多数缀合优化问题中，适威膨函数都是固定的，但是在课表问题中，固定的适应度函数鼹然是不能适用的，因为随着排课的进行，遗传环境（课表黧间）在不断变化，同样一个个体，放在不阏的环境中，它的适艨程度是不同完全的，甚至稳差缦大，黧魏，磐露设诗一令荚蠢鑫逶应瞧熬适黩发嚣数裁是最关键戆。①适应度溺数中的参数适应度函数中需要包含的参数信息包括：节次优魔ａ、日组合优度ｂ、带缀合优度ｃ、组合可行性ｄ、分布优化度ｅ、资源优化度ｆ等。这些信息都保存在课表知识库中。

重庆大学硕士学位论文３时间安排算法１）节次优度ａ节次优度是对一节课“有多好”的量化表示，是大部分同学愿意上这节课的程度，或者上这节课效率的高低。表９则是由一份社会调查得到的节次优度结果，当然这个结果含有一定的人为因素，每个人的评价可能有些差别，这也正是为什么课表千差万别的原因之一。在我们的排课算法中，该信息是由排课人员自己维护的，它可以实时地体现不同人、不同学期的要求。表３．８节次优度Ｔａｂｌｅ３．８ｓｌｏｔ－ｓｕｐｅｒｉｏ星期一上午第一大节第二大节下午第三大节第四大节晚上第五大节Ｏ．９５Ｏ．８５Ｏ．６５０．５５Ｏ．３５星期二０．９８０．８９Ｏ．６９０．５９０．３９星期三０．９７０．８７０．６７Ｏ．５７Ｏ．３７星期四０．９４０．８４０．６１０．５ｌ．０３１星期五０．９２Ｏ．８２０．６２Ｏ．５２Ｏ．３２节次优度是将大部分同学愿意上这节课的程度，或者上这节课的效率的高低进行量化的结果。上例中，周一第１节课的优度为０．９５比较高，表示这节课效率较高。２１日组合优度ｂ日组合优度，是日组合方案优劣程度的量化表示。假如某门课一周上两次课，那么哪两天的组合比较好？每周上两次课（一天只能上一次课），五天中所有的两天组合数为Ｃ５２＝１０，例如：周一和周二的组合为：表３．９日组合情况一Ｔａｂｌｅ３．９Ｐａｒｔ１ｉｎｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ－ｄａｙｆ星期三目目＊———。。。Ⅲ日——．——＿ｌ＿＿目＿目目Ｈ＿＿日目＿目日＿嘲ｌ零期一ｌ星期二星期四星期五周三和周四的组合为：表３．１０日组合情况二Ｔａｂｌｅ３．１０Ｐａｒｔ２ｉｎｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ—ｄａｙＩ星期一星期二早期三旱期四星期五圈一对每种组合进行优度判定，例如：周１周２组合（１１０００）的优度为１．０，周３周

重庆大学硕士学位论文３时间安排算法４组合（００１１０）的优度为０．８，等等。３）节组合优度Ｃ。节组合优度Ｃ，表示这两天中的哪种节次组合比较好。在日组合的基础上，进行课次的安排组合。上面的例子中己经确定了每周两次课，假如按照传统的大课（２小节）安排，那么所有的课排组合数应为５ｘ５＝２５，例如：表３．１ｌ节组合情况一１ｈｂｌｅ３．１１Ｐａｒｔｌｉｎｓｌｏｔ－－ｅｏｍｂｉｎａｆｉｏｎ星期一星期二星期三星期四星期五上午第一大节第二大节下午第三大节第四大节晚上第五大节表３．１２节组合情况二ｍｆｂｌｅ３．１２Ｐａｒｔ２ｉｎｓｌｏｔ－ｅｏｍｂｉｎａｔｉｏｎ星期一星期二星期三星期四星期五上午第一大节第二大节下午第三大节第四大节隧隧翻黼隧晚上第五大节对上面每种组合进行优度判定：第一天的第２大节和第二天的第４大节组合，优度为１．０，第一天的第２大节和第二天的第３大节组合，优度为Ｏ．８，等等。４）组合可行度ｄ。组合可行度表示当前的安排是否存在班级或教师的冲突，如：是否有的班级在当前时间已经安排了其它课程。它只有０和１两个取值。５）分布优化度ｅ。分布优化度ｅ是以Ｏ～１之间的浮点数来表示的。分布优化度是指当前的安排是否满足课表的一些要求，如难度间隔，文理间隔，以及是否满足上课教师或者课程本身的一些特殊要求等等，它是Ｏ～１之间的浮点数，因为事实上，一套课表肯定无法保证全部的难度间隔和文理间隔，因此我们设置分布优化度来表示问隔程度。

重庆大学硕士学位论文３时间安排算法６）资源优化度ｆ资源优化度ｆ也是介于Ｏ～１之间的浮点数，它的目的是为了追求排课的第三个目标而设置的，是对付“漏课”的第一道防线。我们在前面介绍过，“漏课”的问题是课表问题中的难点。为了更好的理解资源优化度ｆ，首先，我们来分析一下，由于课程无法安排教室而造成的“漏课”是怎么产生的，这其中的原因有很多种，其中与时间安排有关的原因之一是对有限的某种教室过度集中使用，而造成某个时间该类教室负荷过重，使后面待安排的课程在这个时间无法获得足够的教室选择空间。资源优化度的判定相对复杂一些，它涉及到教室资源分布图的计算，削峰填谷等方面的内容，简单的说就是判定是前的安排否当会导致某一类教室在一个时间的使用过于集中，而其它的时间空闲很多，继而使后面的课程在安排教室资源的时候过度紧张，从而不得不进行教室范围扩展，浪费了本来就很有限的教室资源。在自动排课算法中，资源优化判定是避免出现“漏课”的第一道防线，它就是为了阻止对某一类教室在一个时间过度使用。教室数星期一（第１节）时间图３．２有波峰非均匀的教室资源分布曲线Ｆｉｇｕｒｅ３．２ＴｈｅｄｉｓｔｒｉｂｕｔｉｎｇＣＵＩ、，ｅｏｆａｓｙｍｍｅｔｒｉｃｃｌａｓｓｒｏｏｍｎ№ｕｒｃｅｓｗｉｔｈｗａｖｅｃｒｅｓｔ教室资源分布曲线图直观地表示了一种教室（适合多少学生一起上课的教室），在各个时间段的使用分布情况，从这种图上，我们可以看出哪个时间的负荷过重（失去平衡），在排课过程中（而不是排课结束后）及时地发现并进行纠正。事实上，这是一种在安排教室之前就进行的预防手段，它并不能绝对避免“漏课”出现。当“漏课”出现后，我们还会有可选的几个方法来自动称补，这些方法将在后

重庆大学硕士学位论文３时间安排算法面介绍。在图３．２中，在周三出现了非常高的峰值，它导致了后面人数相近的课程在周三没有足够的教室选择余地，而其它时间该类教室却有很多空闲。假如这时有一门课程需要在周三第１节课从该类教室中选择，那么就会出现无法安排的问题，那么系统将会自动降低时间组合优度，转而向其它时间段进行搜索以期避开周三第１节这个时间，如果能找到则可以解决这个问题，可是时间组合优度是会否降低很多呢？是否会有其它冲突产生呢？例如：难度大的课程没有得到较高的时间优度，或者违反了其它常规规则等，这些问题我们都无法保证不出现。因此，通过在排课过程中动态的计算资源分布优度，及时地发现并摒弃这种不合理安排，可以在很大程度上避免“漏课”出现。教室数星期一（第ｌ节）时间图３．３相对平均的教室资源分布曲线Ｆｉｇｕｒｅ３．３ＴｈｅｄｉｓｔｒｉｂｕｔｉｎｇｇＵＩ＂ＶＣｏｆａｖｅｒａｇｅｃｌａｓｓｒｏｏｍ“∞ｕｎ：ｅｓａｂｓｏｌｕｔｅｌｙ在图３．３中没有明显的波峰和波谷，表示教室的分配比较均匀。类似的课程在任意时间都可以安排，这是比较理想的状态。资源优化度ｆ的计算公式为：仁（Ｔ－－Ｍａｘ）／（Ｔ－－Ｍｉｎ）其中，Ｔ为全部教室总数，Ｍａｘ是组合产生的峰值，ＭｉＩｌ是谷值。当资源分布曲线越趋平缓，即Ｍａｘ与Ｍｉｎ越接近的时候，ｆ就越大，最大值为１，出现在Ｍａｘ＝Ｍｉｎ的时候，即曲线是一条水平线。②适应度函数基于以上参数，我们设置单门课程的课表问题遗传算法的适应度函数如下：Ｆ＝（Ａｘｗｌ＋ｒｂ。ｑ１＋ｃｘｑ２）ｘｗ２）ｘｄｘｅｘｆ

重庆大学硬圭学爱论文３酵鞠安接簧法其中Ａ袭永当前组合方案的带次优度的平均值，Ａ＝（（ａｘｂＩｃｌ）＋（ａｘｂｌｃ２）＋（ａｘｂ２ｑ）＋（ａＸｂ２ｃ２））／ｎ，公式是以上述的每周两次课为例，其中ｎ表示上课的次数（这里ｎ＝２），ｂｌ是第一次课的目组合优殿，ｂ２是第二次课的豳组合优度，ｃＩ是第一次课豹：箨组合魏度，ｃ２是第二次瀑戆蓼缍合筑度，锤秘琏２袋苯基缓会魏度黟繁缀合钱度所占的投黧，ｑｌＩ＋ｑｆｌ，嚣ｖｒｌ秘ｗ２表示节次优度和缀合优度各占的权熏，ｗｌ＋ｗ２＝ｌ；适应皮函数Ｆ的最高值为ｌ。③选择操作（Ｓｅｌｅｃｔｉｏｎ）在局部课袭闯题中，我们采用了轮盘赌豹方法来进彳子选择操作，并对此做了撰投夺生境豹羧送。轮鑫赔方法交琢圭是莰蕹蒙特豢罗（ＭｏｎｔｅＣａｒｌｏ）方法浚谤熬。蒙特卡罗方法，或称计算税随梳模撅方法，蔗一静基于“随梳数”熬计算方法，它的基本思想很早以前就被人们所发现和利用。早在１７世纪，人们就知ｊ鳆用事件发生的“频率”，来决定事件的“概率”。１９世纪人们用投针试验的方法来决定圆周率，本世纪４０年代电子计算机的出现，特别是近年来离速电子计算机的出现，使褥躅数学方法凌诗算辊上大量、俊速遣模苏这样兹试验藏为霉能。铡如，考虑平瑟上懿一个逡长免ｌ静正方形及箕内部的一个形状零麓煲｝ｌ静“图形”，魏谤求澎这个“图形”的面秘睨？蒙特卡罗方法怒这样一种“随机化”的方法：向该正方形“随机地’’投掷Ｍ个点，落于“图形”内的点为Ｎ，则该“图形”的丽积近似为Ｎ；Ｍ。露３．４不阉令体戆逶痤痍Ｆｉｇｕｒｅ３．４ＴｈｅｆｉｍｃｓｓｏｆｄｉｆｆｅｒｅｎｔＩｎｄｉｖｉｄｕａｌｓ轮盘赌方法类似于博彩游戏中的轮盘赌，轮盘被划分为不同比例的区域。这里的比例是根据个体适应度大小分配的，适应度高的个体由于在轮盘中矗攒较大

重痰大学硕士学经论文３辩弱安接算法比例的区域，阁此被选中的概率就犬，得以生存的概洙大，相反，适应殿较低的个体则被淘汰的概率较大。选择算法的过程是随机的程轮盘中投下落在的区域所代表的个体将被选中并得以生存，虫Ｈ圈３．４所示。翔嚣瑟奔缓熬，基于夺生境技术夔选择操薛将受瓣予健令搏与父霞令傣逶厅适应度醴：较，如栗父代个体遥应度离，刚复皋ｌ父代个体劐当前子代释群中，否则不复制。前面我们融经讨论过了遗传算法的缺陷，其中一个缺陷是初始种群的不均匀分布。在这爨，为了改进它，我们采用了分区域的初始种群选择，即，将整个解空闯划分或ｎ令嚣域，袭魏纯耪群辩，分裂在每令小区域孛疆瓿选择１／ｎ接个个体，最后将ｎ个小释群合并残橱始耪群，这样产生静静群麓本覆盖了整个熬空阉，保证了初始种群的均匀分布．④交叉擞作（Ｃｒｏｓｓｏｖｅｒ）课表问题中，每个个体需要遵键的规则是周课次数是固定的，无论怒交叉还是变异都不麓造鹜该怒赠。嚣致，我髑设计豹交叉摄传必须要考虑这个缀索，毙舞矩薄夔交攥髂或者并操终裁蠢无法满足这个魏嚣ｆｌ瑟举缆采瘸。我们这熙采用的交叉操作类似乎二迸制串中的单点交叉操作，单点交叉是随机产生一个交义点，然后将两个父个体在交叉点右侧的部分相互交换，从而产生两个不同的乎个体。对于课表问题的矩阵表示，我们将随机交换两个父个体的第ｒ１个‘ｌ’位，箕巾ｎ随规产生，对于繇蠲三课次豹课程，假设ｎ＝ｌ，鄹交换父个俸ｌ与父令薅２戆第一令霞进孬交叉缀会残子令体。镶懿：袭３．１３父个体１ＯＯｅＯＯ１Ｏ８ＯＯＯＯＯＯｌＯＯＯ０００ｌＯＯＯＯ００ＯＯ０Ｏ００袭３．１４父个体２０ＯＯＯＯＯｌＯ０００ｅＯＯＯＯＯｌ０Ｏ０ｌＯ§０ＯＯＯＯ００Ｏ００

重庆大学硕士学位论文３时间安排算法交叉产生两个子个体：表３．１５子个体１Ｔａｂｌｅ３．１５０ＯＯ００Ｏ１００Ｏ０００Ｏ０ｌ００００ＯＯＯＳｏｎＩｎｄｉｖｉｄｕａｌ１００ｌＯＯ０Ｏ０ＯＯ０表３．１６子个体２Ｔａｂｌｅ３．１６Ｏ０００Ｏ１０００Ｏ０ＯＯＯＯＯ０ｌ００Ｏ００ＳｏｎＩｎｄｉｖｉｄｕａｌ２０ｌＯＯ００００Ｏ０Ｏ两个子个体分别保留了来自父个体的部分特征。⑤变异操作（Ｍｕｔａｔｉｏｎ）变异操作相对比较简单，由于我们设计的矩阵为布尔矩阵，而且矩阵中的‘ｌ点个数不能变化，因此，我们采取了“１点跳转”的变异方法，即矩阵中的某个‘ｌ＇点由原来的位置随机跳动到另外一个一０点上，而原来的‘１’点自动变为‘ｏｔ。例如：表３．１７父个体Ｔａｂｌｅ３．１７０ＯＯＯＯ１Ｏ００ＯＯ００Ｏ０１０ＯＯＯ０ＯＯＦａｔｈｅｒＩｎｄｉｖｉｄｕａｌＯ０１００Ｏ０Ｏ００Ｏ变异为：表３．１８子个体Ｔ曲ｌｅ３．１８Ｏ１０ＯＯＯＯ０ＯＯ０Ｏ０ＯＯ１００ＯＯＯＯ０ＳｏｎＩｎｄｉｖｉｄｕａｌＯＯ１００００ＯＯＯ０

重痰大学硕士掌经论文３孵溺安接舞法３．５．２局部课表问题遗传算法的结束条件假如我们不考虑遗传算法的结束问题，那么遗传算法将无限地执行下去，因为算法本身弗不知道该怎样结束，所以，我们必须设鼹遗传算法的停止谶纯条件。骞三秘较黪懿逅窭逮煲算法戆方式，善竞，当耱瓣墨不毒骞交纯对，羧霹敦决定退出，这黉要一个专门餍来稔凌释群差冥的模块，它耨对任意两个个体进行差异检查。第＝种方式是，如果达到了适应度的目标，也可以退出，这需婺适应度函数设嚣的非常好，它基本上能够体现个体的绝对适应度，或者需要缀历一定次数的测试，了解了适应度的情况之后，就可以设鬣翻标适应度。第三，在迭代了一定豹次数袋者说经历了一定数嚣熬“鼗’，之嚣，瑶叛退出。在基予荦门谦程静捧谋算法巾，由于适应度瓣镶与当前遗传环境毒穰灭静关系，不能够纵向进行比较。例如，对于空的课表空间，适应度为Ｏ．９８的安排方案是最好的，但魑当课表空间已经被占用了很多的时候，适应度为０．８的安排方案是当前环境中最好的，而且是可以被接受的，因此我们不能设置一个统一的目标适应度来衡量。程这里我髓采取了努三秘方式来终止遗传算法，鄯设置一个“代”数，达妥该“鼠”数之嚣，箨壹遽簧避纯，并置取当藏最饶虢ｎ（ｎ由用户鑫蠢镶定）今个体为最终解，之所以取ｎ个最终个体是因为教室安排会对时间安排产嫩回溯调整，可能最优的个体并不能和教意安排很好的合作，因此必须存在多个候选个体，这些会在后面详细介绍。３。５．３全局谍表问题的遗传算法设计经逑鼹帮漾表闫蘧戆算法运移，辩每门谍程我辩舔甏数我鹫一个遥钕袋傥我谋表安排，假是这却无法确保整套谍表就是近似最优的，因为课表空间和教室空间都是一定的，先安排的课程无疑会抢夺最优，后安排的课程则只好选撵次优，这就是优度抢夺的问题，即，无论怎样编排，都不可能使各个课程的安排在优度上绝对平衡。这是课表编排的主要灏难之一，也是慕本艘锋之一。在漂表瀚瑟夔藤弱孛毒蔻条涉及鬟次彦勰题，魄黧先撰燕麦寒懿课纛、先｛霎公共谋等，健怒仅仅有这几条嘏则楚远远不够的，蔡中还涉及至４课程对教鲞和时间的要求问题，要求严格的课程威该先排，或者条件姆刻的课程应先排，由于～个学期的课稷很多，所以这些条件很难在排课之前就能够确定，这里我们采用遗传算法来寻找～条近似最优的课稷安排序列。课表闽题属于ＮＰ完全问题，它的搜索空阕夔誊渫糕数纛豹瑷麓瑟惫测瀵大，瑟有夔课程撵磺数走（》１）！／２，麴魏凌大的援索空闻需要用遗传算法来解决，下面我们分橱鞠设计在全局课表阔趱中遗传算法的应用。①编码采用路径袭示法。路径表示法是表示旅程对应的簇圆编码最自然，最简单的

重庆大学硕士学经论文３辩溺蜜撵莠法表示方法，窀是把旅程依次经过的城市的顺序记录下来。这种编码方式必须保证编码中不能有重复的因子出现。例如：设置顺序表Ｃ＊（１，２，３，４，５，６，７，８，９），旅程顺序为５一ｌ一７—８—９—４—６—２—３，用路径表示法就可以直接袭示为：５１７８９４６２３。②选簿撩作帮适应度函数在这里我们仍然采用与局部课表问题的选择操作榴类似的选择策略——基于小生境技术的轮盘赌方法。适应度聪数的设计问题是全鲻漾表闯题中的一个难题，为此，我们采用了一耱霪单一点熬方法，藏是将每一门漾程在弱部安捧貉瑰豹最终适应度避纾警均，由毙来对整令路径进行评价。仅仪～门课程安终褥好，并不能健表整个渫袭安｛菲得好，而所肖课程安排得好的话，那么整个课表安排樗就一定好，所以，所有课程适应度的平均值基本可以体现熬套课表的适应度函数。因此，Ｆ。（Ｆ１＋Ｆ２＋…＋Ｆｎ）／ｎ，１１是种群中课程的门数。③交叉搽侮采用鼹衽袭示黪编璐方式决定了在逮传算法中逡符交叉揉馋生成豹令棒染色体中不允许肖熬复的基因码。这样，基本的遗传算法的交叉操作生成的个体～般就不能满足这～约束条件，在这嫩我们采用顺序交叉。顺序交叉是在１９８５年由Ｄａｖｉｓ等针对经典的货郎担问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，ＴＳＰ翘题）提出豹基予路径表示静颞序交叉操作，它能保密排列菸融合不同捧捌兹蠢澎缝莱蕈元，秀令父令钵交叉懿，逶避选择父个俸ｌ熬一帮分，僳存父个体２中基因码的相对顺序辙成子个体，这样就继承了来自两个父个体的部分特征。例如，对下面两个父个体的袭示，随机的选择两个交叉点“ｌ”Ｐｌ：１２３｛４５６７ｌ８９Ｐ２：４５２｜１８７６｜粥首先，两个交叉点之闻的中间段保持不变，得到：Ｓ１：ＸＸＸＳ２：ＸＸＸＩＩ４５６７１８７６ｘＸｌＸｘ其中ｘ袭示暂时没有定义基裰码。然囊，诞瑕父令落２软第二令交哭赢嚣始款基嚣褥豹蓑｝裂ｊ矮｜亭，姿嬲达表遑时，返回袭头继续记录基因码，赢到至《达第二个交叉熙结束，这样就获褥了父个体２从第二个交叉点开始的基因排列顺序：９３４５２１８７６。对于父个体ｌ，融有的基因码为４、５、６、７，将它们从个体２的基因码排列顺序中去掉，得到排列顺降９３２１８，再将这个排列顺序复制给父个体ｌ，复制起点也是从籀二个交叉点开始，以此决定

重庆大学硕士学位论文３时间安排算法子个体１对应位置的未知码ｘ，这样子个体１生成为：Ｓ１：２１８４５６７９３调换父个体ｌ和２的顺序，同样可以生成子个体２Ｓ２：３４５１８７６９２④变异操作变异操作有很多种适用于顺序表达法，比如反转变异、插入变异、移位变异等等。这里我们使用反转变异。反转变异是在染色体上随机地选择两点，并将两点之间的子串反转：１２３４５６７８９一１２３６５４７８９３．５．４全局课表问题遗传算法的问题和改进①染色体编码过长如果单纯地把课表问题简化成ＴＳＰ问题，会产生一个很大的问题，一个学期的全部课程有１０００多门，如果把它们当作一个整体看待，每条染色体基因将有１０００多位，虽然有的理论认为编码应该符合实际变化，但是这样庞大冗长的编码表示，违反了编码灵活的原则，而且给理解和操作都带来了困难。这个问题的解决方案是划分子群体。事实上，仔细观察之后可以发现，一个学期的课程中，各个系之间存在着很强的独立性（除少数的公共课以外，而这些少数的公共课程具有最高的优先级，他们并不应该参与普通个体的选拔），每个系的课程参与的教师、班级和教室往往是相互独立的，不同系的课程之间并不存在优度抢夺。而且单个系在一个学期中的课程在２０门以内，这样的基因编码就合理很多。因此，我们采取的解决方法是，将种群分割成不同的子种群，遗传算法分别在各个子种群中独立的进化，各个子种群之间不进行任何通信，当各个子种群都已经搜索到了局部近似最优的个体，然后在子种群之间进行比较和合并，选取出全局最优的个体。这种方法恰恰发挥了遗传算法的并行性优势。②适应度函数计算量过大全局课表问题中遗传算法的另一个问题是适应度函数的计算费时太大，假如一个子种群中包含２０门课程，那么对于任一个体，计算其适应度需要执行２０次局部遗传算法，这种适应度计算方法需要的计算量过大，会影响整个算法的运行效率，目前我们能够采用的缓解方法是采用并行遗传算法的思想。并行遗传算法的实现方案大致有三种：１）主从式（Ｍａｓｔｅｒ－ＳｌａｖｅＭｏｄｅｌ）在这种模型下，并行系统分成一个主进程和若干个从进程．主进程监控整个染色体种群，并荃于全局统计执行选择操作，各个从进程接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算其适应度，再把计算结果传给主

重庆大学硕士学位论文３时间安排算法进程。这种模型在适应度计算很费时并且远远超过通信时间的情况下才有效，否则通信时间超过计算时间，反而会降低速度。而且这种方法要求有进程同步机制，这就会导致主进程忙而子进程闲或者相反，引起负载不平衡，效率不高。２）分布式（ＤｉｓｔｒｉｂｕｔｅｄＧｅｎｅｔｉｃＡｌｇｏｄｔｈｍｓ，ＤＯＡ）这种方式是将种群分成若干个子群并分配给各自对应的进程，每个进程不仅独立计算适应度，而且独立进行选择，重组交叉和变异操作，并定期地相互传送适应度最好的个体，从而加快满足终止条件的要求。分布式遗传算法是目前采用最多的并行遗传算法。３）分散型（Ｆｉｎｅ．ＧｒａｉｎｅｄＭｏｄｅｌ）分散型遗传算法是为种群中的每一个个体分配一个进程，每个进程进行适应度计算，而选择、重组交叉和变异的操作仅在与相邻的一个进程之间传递个体中进行。我们最后采用了分布式的并行遗传算法来解决适应度计算量过大这个问题。将种群划分成相互独立并且相差较大的若干个子群，每个子群中都独立的进行选择、交叉、变异等操作，达到一定代数之后，相互之间进行最优个体交换，以达到全局最优收敛。３．５．５全局课表问题遗传算法的结束条件图３．５遗传算法停止条件Ｆｉｇｕｒｅ３．５ＳｔｏｐｃｏｎｄｉｔｉｏｎｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

重庆大学硬±学拯论文３黠鹚蜜罄算法在局部渫表问题中，遗传算法的结束条件是达到了进化的代数，就停止算法，那是因为局部课袭问题的适应度澈法纵向的进行比较，因而无法设置一个统一的适应度尺度来衡量是否可以停止遗传。在全是潆凌窝惩孛，事实上麓嚣耱方法罄可以掺麓筹法续震愆条｛譬。我秘这里采爝了两荦孛方式相结合的方法，先进行适应度条馋橡查，如果找到了达剿指定适应度的个体，则停止进化，否则，如果进化代数爵经超过了指定的代数限制，但还没有找到符合适应度要求的个体，则也停止进化，从最后一代种群中选择最优个体作为最艏的解，如图３．５所承。３．６算法褪絮从宏观上看，我们所设计的谍袭问题解决方案怒两层的遗传算法嵌套运行，内层遗传算法的运行结果传递给外层遗传算法作为邋皮度函数的一部分，外层遗传算法以此为依据来搜索近似最优解。图３．６就体现了整个算法结构。

重庆大学硕士学位论文３时间安排算法图３．６遗传算法流程图Ｆｉｇｕｒｅ３．６ＦｌｏｗｃｈａｒｔｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

重褒大学硕士学缱论文４教室安搀算法４教室安排算法教室安攥舞法豹基豹是为谍糕选择一个教室，它是簿渫软传豹一令獯点，这个算法静优劣楚整个簿谋算法成功豹一今关毽，因为瓣翡高校课表安舞｝的～个最突出的矛盾怒不断增长的学生入数和有限的教室资源之间的矛盾。很多ｊｊ｝谍软件在这个问题上都没有找到很好的解决方法，出现太多光法安排教室的课程，是造成“漏课”现象的最重要的一个因索。如何有效的安排使用这些固定的教室资源，在技术上是一令鼹题，嚣在实际应嬲巾其有缀重要匏意义。４．１教室安排流程教室安排算法的流程图如图４．１所示，其中ｎ为优先教室的个数。教室安排算法的输入数据包耩；课程ｃ、上课人数ｇ、课程要求和教窳类型ｈ。首先，麸知识黪Ｋ中取出当前谖程豹优先教室表Ｒ，默认情况下，ｋ书所包含的教室集合荛溧戆掰藩系掰在熬系褛教室，蕉户可颤菇漾鹱缝套一个更漆确豹范围。在这个教室范潮中，对教室座位数燕和教室类型避彳予过滤，得出符合当瀚谍程要求的更小的教勰范围。其中教室魔位数ｅ：ｇ＋Ｍｉｎ＿＜ｅ＿＜ｇ＋Ｍａｘ其中Ｍ如ｊ鞫Ｍａｘ分别是座缀数多于人数的下限觏上限，系统默认２０釉５０，著霉更改维护。这辩蔟懿教室表甏孛黪每令教室箨熊壤壤骜会当蘸漾蘸鹣簧求，当Ｔ口中的教燕没有可利用的时候，系统将首先采用教室扩展来解决这个觏遂。这里的扩臌包括两步，首先对教室座位数的扩展，即对上面式子中的Ｍｍ和Ｍａｘ之间的范围进行扩大，使符含器求的教室范围增犬，从这个扩展后的教室范围中寻找目标教室．第２步是对教窳类型的扩展，即，爱求酱通教室的课瑕可以扩震弱多媒薅教嶷，或者授影教室，这嚣弹霉强健嚣据数蹇蓬垂壤太，毽怒攀实主往往多媒体教室和投影教室数量黧绷有限，因ｊ鞋：，势举攘荐使用第二静扩越。在两种扩腰都无法找到符合隳求的目标教室的时候，“漏课”问题就出现了，下面将讨论如何解决“漏课”问题。

重庆夫学硕圭学靛论文４教室安簿算法图４．１Ｆｉｇｕｒｅ４．１教室安排算法的流稷圈Ｆｌｏｗｃｈａｒｔｏｆｃｌａｓｓｒｏｏｍ－ａｒｒａｎｇｅｄａｌｇｏｒｉｔｈｒａ４．２“漏课”翡三种解决算法前面已经介绍了“漏课”问题，以及这个问题的产缴原因。如果理论上学校的教室资源是可以满足教学任务的要求的话，那么则一定存在一种课表解决方案可以没有‘‘漏课”阿题，可是，追求绝对没有“漏课”闽题将逃成算法的无限期运行，或者４０

重痰大学硬士学缎论文４教室安接算法死循环产生，湖此，我们放弃绝对追求，而追求力争将“漏课”问题减少到鼹低限度。排课算法中，我们运用了３种算法来避免和排除‘漏课”问题，第一种辣法运用在对间安排冀法中，也就是说，农时阅安排时期则己缀野始考虑教室安排的情况。算法一：旋懿蠲嚣安萎｝过程巾，尽量遗受嚣要类秘教室熬漂程过爱集串在菜个时闻，这裁怒在时闻安捧算法巾笑子资源分布优纯度判定部分的内容。这令算法首先能够从底层避免“漏课”，它属于一种预防手段。由于算法一仅仅是一种预防乎段，它只能够降低“漏课”出现的几率，似并不能够阻止“漏课”阅题的出现。例如，即使时间分布很均匀，可是对于那些本来就很有羧熬特豫教囊，仍然可能由予握骜馒爰，瑟导致那壁必须壤习它静漂覆炙浚安搀教室。当出现这样静情况的时媛，我ｌｆｊ采蘑７“强溺”髑熬筋方式来解决这个闯蘧，以求尽量满足课程对教室的要求。排课的过程也是对有限资源使用的过程，开始的时候资源相对丰富，可以择“最优”进行安排，随着排课的进行，资源慢慢变得很紧张，可选择的余地巍越来越小，当出瑷茏浃安接熬“死蹙”的对候，摊漂过程遇至ｌ了簿薅，这个漳碍势嚣一定是因为教室资源没窍了造戒懿，露瑟多建是垂手“美键”爨潦羧提兹使矮７，这嚣重候，向前寻找可以将“关键”资源释放的地方，撤销其现有蜜排，以非关键资源替代关键资源，那么前顾遇到的障碍则会得到排除。这个过程就是我们所采用的“回溯”调整，简单的说，“阐溯”就是当匹配遇到障碍的时候，撤销以前的决定，重新进杼～次新豹选择。由予摊课中豹试探具有一定的盲目性，产生不合理安排是不可避兔的，瑟“强溺”能够楚系统壳骚这令袋杰，嚣瑟“瑟溯’’在这受馨鬻重簧，是鼹狭翊遴豹一个重要手段。算法二和算法三分别是回溯调整的两种不同方式。算法－－宅回溯改变当前课稷融经确定了的时间安排，来寻找可满足教室要求的时间组含，这个改变有可能会降低时间组合的优殿，但是如果优度降低范围在认可黥范滋叛疼，那么班较小熬拜尊藏爨度来换取教窳安接上豹空闫，媳鼹霹取豹一穗方案。算法二将从时间排课算法所产生的ｎ个候选个体（时间分配方案）中，按照适应度由大Ｎｄ，的顺序对个体进行试撵，这里的试探不仅黉进行组合可行性、分布优化度、资源优化度的判定，还要谶行当前的时间组合怒否能够进行教室蜜排的判定，只有能够进行教室安排的个体才是符合要求的搜索结果。致交爨阙缀会葳造成熬霹蠲臻发下簿是这静算法瓣一令弊囊，一般壤滋下我们只允许较小瓣优度下降，当下降游常大的时候，蹩个谍表的质量也将下降很多。因此，对算法麓，我们加入了一个优度降低限制参数ＤｅｃＬｉｍｉｔ，它将监视每次时间组合改变所造成的优度降低是荫在限制之内，如果一旦超过该限制，则放弃算法二。４１

重庆大学硕士学位论文４教室安排算法图４．２回溯算法二流程图Ｆｉｇｕｒｅ４．２ＦｌｏｗｃｈａｒｔｏｆＢａｃｋｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｉｃ．－２算法二的流程图如图４．２所示。按照算法二的思路，较大的时间优度往往不能够获得足够的教室可安排空间，回溯的成功率则不会很高，可是如果保证该算法一定回溯成功，则必定会造成时间组合的优度过低，而导致课表质量的下降，因此，我们准备了第三个算法。算法三也是一种“回溯”方式，它将在算法二仍然无法成功的基础上触发，与算法二不同的是，它的回溯对象不是当前课程的时间安排，而是其它已排课程，调整其时间或者教室安排。流程图如图１３．算法三有两种“回溯”算法，第一种是回溯调整已排课程的教室安排，第二种是回溯调整已排课程的时间安排。当出现“漏课”的时候，暂时保留当前课程的时间安排，而向前回溯己排课程，

重庆夫学硕士学髓论文４教室蜜攘算法查找可以进行很小调整则能满足当前课程教室要求的已排课程。第一步，计算调整目标课程集合。要搜索娃：鞠当前课程在当前辩间具有冲突交集的嬲标课程集合，该集合中的谖程辑占矮熬教室郝篷含在当蠢萋漾毽弱霞先教室集会巾，繇改交这些潆耧懿安接受４会改变当前课程静安排空闯，虢有可能会产生可利用豹教室。这个算法就楚在目标课程集会中寻找－－ｆ－］课程，改变它的安排（时间或者教室），而使当前谍程可以在不改变时间安排的情况下获得Ｗ用教室。第二步，鲇每门目标课程计舞“波及范围”在这里，势苓是蓬辊熬获己接涤程孛选择一门谖凝※终镶整，嚣是蔹鬃一个计算“波及范丽”静佶值丞数ｆｆ镭饿丞数ｆ为每门已稀谍翟计算出一个俊，它代表若改变该课程的安排整套课表中将会有多少门课程受到波及影响，他们都宵可能要作出相应的改变。第三步，依“波及范围”从小黧犬的顺序对目标课耩避行试探调整。一般壤况下，调整菜一门楣荚漾程之磊，裁链够鳞决“瀑苗Ｐ’，毽是在莱焦情琵下，需要霹辩谖整－ｆ－ｊ甚至更多瓣谍程，才可敬“挪懑”一个可震教室空阕。继篷丞数对多于两门课程的计算为：ｆ（ｅｌ，ｃ２）＝ｆ（ｃＯ＋ｆ（ｃ９－Ｏ（ｃ，ｃ２）其中函数Ｏ（ｅｌ，吩为课程ｅｌ和ｃ２之间波及范围的激叠部分。回溯的原则是，依次选择波及范围最小的课程进行试探调整，直到调熬成功或者所有嚣栎谦程全都试探完毕为止。由予调熬嚣标谋程耱辩麓缀念会雩｜莛嚣闼霞褒瓣鬻低，因筵，冀法将营先试图调整目标课程的教室，来寻找Ｗ安排空间。每次试阁调整都检查是否可以满足当前课程的教黧安排，如果能，则玛上退出，进入第四步。如果在搜索究全部目标课程后，发现仅调整教室无法满足要求，那么算法将从头开始进行调熬时间安接的试探，这～步与算法二相似，瞬样要进行时闯优璇降低限度的检查，一个原翔是，课程懿溪整凌不盎诲辩窝缀会饯度降低虱霜产瑟求戆嚣瘦疆下。第四步，对由第三步产生的Ｗ调整目标课程避行调整，同时对当前谍程进行教室安排。

重庆大学磋七学技论文４教室安撵舞法强４．３靼溯算法三滚程强Ｆｉｇｕｒｅ４．３ＦｌｏｗｃｈａｌｔｏｆＢａｃｋｔｒａｃｋｉｎｇａｌｇｏｒｉｔｈｍｉｃ·３