基于Java Web的高校排课系统的设计与实现.docx

《基于Java Web的高校排课系统的设计与实现.docx》由会员分享，可在线阅读，更多相关《基于Java Web的高校排课系统的设计与实现.docx（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘要基于 Java Web 排课系统的设计与实现摘要排课问题是一个NP完全问题,是一个多约束的、多目标的组合优化问题。而传统的手工排课的方式，不仅繁琐、极易出错，而且不能全面地考虑对教学资源的合理利用。因此，设计一个能够根据约束条件，自动安排课程的智能排课系统， 是现在高校教务管理的迫切需求。本文通过对排课系统的分析，阐述了基于Java Web平台下的排课系统的Web 解决方案。本系统采用了 B/S 结构，采用了基于 JSP Model2 的 MVC 设计模式， 大大简化了系统开发的困难。本文选用了遗传算法来解决排课问题，阐述了遗传算法的基本原理与算法流程，以及在排课问题中的具体实现。关键词：

2、排课系统；MVC；JSP Model2 ；Java WebIIAbstractCourse Arrangement System Design and Implementation Based on WebAbstractCourse timetabling problem is a NP complete problem, and is a combinatorial optimization problem with a variety of constraints and a multiobjective optimization. the traditional manual meth

3、od , is not only tedious and error-prone, and can not fully take the reasonable use of the teaching resources into consideration. Therefore, designing a course arrangement system that can arrange the course arrangement automatically according to the constraints is the urgent demand of university edu

4、cational administration management now.Through the analysis of the curriculum arrangement system, this paper expounds the web solutions of curriculum arrangement system based on Java Web platform . This system adopts B/S structure, and using the MVC design pattern based on JSP Model2,greatly simplif

5、ying the difficulties of system development. This paper use genetic algorithm to solve the course timetabling problem, and expounds the basic principle of genetic algorithm , the algorithm flow, and the concrete implementationin the problem.Keyword: Course Arrangement System； MVC； JSP Model2； Java W

6、eb目录目录摘要IAbstractII第一章 绪论11.1 课题背景与意义11.2 国内外发展现状11.3 本文的研究目标2第二章 相关开发技术32.1 网络结构32.2 JSP 技术32.3 MVC 模式介绍52.4 本章小结6第三章 排课系统分析与设计73.1 排课系统需求分析73.2 排课系统功能架构分析93.3 数据库设计12第四章 排课系统算法设计184.1 遗传算法介绍184.2 排课系统算法设计194. 3 本章小结26第五章 排课系统实现与测试275.1 登录模块实现与测试275.2 基本信息管理模块实现与测试285.3 手动排课模块实现与测试295.4 自动排课模块实现与测试

7、305.5 课表查询模块实现实现与测试305.6 本章小结31第六章 总结与展望326.1 总结326.2 展望32参考文献33致谢35III绪论第一章 绪论1.1 课题背景与意义随着我国在校大学生人数快速增长，教学资源相对紧缺，合理安排课程变得尤为重要。这不仅是保证教学质量的关键，也是充分利用教学资源的关键。在排课问题中，不仅需要消除排课过程中产生的各种冲突，如教室冲突、教师冲突等，还要考虑到单双周课时、合班课、分班课、体育课与选修课等众多因素。然而，目前国内市场很多的排课软件都是通用的，并不能满足高校个性化教学的需求。所以如何设计一个即高效又人性化的智能排课系统是一项很有意义的研究。为了适

8、应当前高校教务管理逐步趋向高效化、快捷化、方便化、人性化的管理风格，为了方便用户管理信息，查询信息，以及信息的及时反馈与沟通，本文采用了基于 Web 的应用体系结构。1.2 国内外发展现状排课问题隶属于运筹学范畴。由于排课问题涉及到教室、教师和班级等教学资源在时间片上的组合优化，排课问题被划为了时间表问题（Time Table Problems, 即 TTS）。对于排课问题首次正式地描述，是 1963 年 Gotlieb 在他所发表的The Construction of Class-Teacher Time-Tables中，他首次提出了排课问题的数学模型，但并未找出一个有效的算法。1976

9、年，S Even 用数学方法证明了排课问题是一个 NP 问题。这也就意味着该问题是找不到最优解的，只有相对最优近似解。随着对排课问题研究的不断深入，一些学者提出了许多解决该问题的算法。传统的高校排课算法有：贪婪算法、专家系统法、图论方法，这些方法只能针对个别的实际问题，没有通用性，而且关联规则很难获取，求解结果不理想 24。后来，一些学者们对利用人工智能技术来解决排课问题进行了大量的研究，提出了一些解决方法，如遗传算法、蚁群算法、模拟退火算法等等。这些算法是目前在解决排课问题时首先考虑的方法，但是这些算法也存在着一些缺陷，例如收敛速度慢、容易陷入局部最优解。我国对于排课问题的研究相对较晚。相对

10、较早的排课问题的研究成果是， 1984 年林漳希和林尧瑞发表的人工智能技术在课表编排中的应用，该成果对后续研究提供了很大的帮助。目前国内的排课系统已有很多，具有代表性的计算排课系统有南京工学院的 UTSS 系统、大连理工大学的智能教学组织管理及课程调度系统、清华大学的 TISER 系统、浙江大学的正方现代教学管理信息系统等20。21.3 本文的研究目标本文主要的研究目标是：1. 剖析排课问题，研究排课时需要考虑的问题，并提出解决方法。2. 利用遗传算法解决排课问题。3. 了解 Web 开发过程，掌握相关理论与技术。相关开发技术第二章 相关开发技术2.1 网络结构本系统采用了B/S结构，以下是对

11、B/S结构的简介。2.1.1 B/S 结构B/S结构，即Browser/Server(浏览器/服务器) 结构，是基于Web的发展而形成的。B/S结构分为三个部分：客户端、Web服务器端、数据服务器。在开发过程中，现在把B/S模式分为三个层次：表示层、业务逻辑层、和数据访问层，分别对应B/S结构中的三个部分(如图2.1所示)。客户端表示层：用于处理用户输入，以及请求处理结果的输出。WEB 服务器业务逻辑层：执行业务逻辑，向数据库发送请求。数据服务器数据存储层：运行SQL 语句。图 2.1 B/S 结构简图在 B/S 结构中，用户通过在浏览器输入 URL 地址，浏览器通过域名解析到主机 IP 地址

12、，并向Web 服务器发送 HTTP 请求。Web 服务器接收请求，连接数据服务器，并发送数据处理请求，数据服务器处理请求并将结果返回给 Web 服务器。Web 服务器接收数据处理结果，做出 HTTP 响应，浏览器接受并显示响应结果。2.1.2 B/S 结构的优缺点优点：1. 对客户端硬件要求低。2. 易于维护与升级。3. 软件重用性好。缺点：1. 响应速度相对较慢。2. 安全性相对弱。3. 服务器负荷重。2.2 JSP 技术6目前流行的三种动态页面技术有ASP（Active Server Pages），JSP(Java Server Pages)，PHP(Hypertext Preproces

13、sor)等。本文采用JSP来开发排课系统。JSP是由SUN公司倡导、许多公司参与一起建立的一种动态网页编程技术标 准15。它基于Java技术，支持跨平台、跨Web服务器技术，拥有JavaBean与扩展标记库技术，是Servlet技术的扩展。早期的Java Web层体系结构中只有Servlet， Servlet接受用户提交的请求，做出相应的业务处理，然后生成HTML页面返回给 浏览器显示。这一系列的动作均是Servlet来做的。但是Servlet中不能像PHP、ASP 等一样嵌入HTML代码，所以利用Servlet来输出HTML非常困难。为了克服Servlet的这些弱点，Sun公司推出了JSP技

14、术。JSP包含很多技术， 包括JavaBean，自定义标签，EL表达式，JSTL标准标签类库等15。JSP页面的执行过程：Web 容器服务器端2.向服务器发送浏览请求1.输入 URL 地址3.调用某个JavaBean 组件4.JavaBean 返回的数据用户客户端浏览器7.显示 HTML6.返回 HTML页面做出响应JavaBean( 基 于Java 组件)5. 读取数据库或者文件DB在HTML文件中，加入JSP指令元素、JSP脚本、JSP动作元素，这样就构成了JSP网页。当用户请求JSP页面时，web服务器接受用户访问JSP页面的请求， 如果是第一次访问该JSP页面，web容器中的JSP引擎

15、将该页面转换为Java程序， 然后进行编译为.class文件。然后执行.class文件，web容器再将生成的响应页面返回给用户客户端浏览器显示。JSP页面页面访问过程如图2.2所示：JSP的优点：图2.2 JSP页面访问过程图1. 跨平台,一处编写随处运行；2. 实现了内容生成与显示的分离；3. 可连接大多数数据库，利用 JDBC 连接数据库；4. 可复用性好，支持可重用的基于组件的设计；5. 安全性好；6. 支持分布式处理；7. 适用于大型系统的开发； JSP的缺点： 1开发周期长；2开发成本高；2.3 MVC 模式介绍2.3.1 MVC 模式简介MVC设计模式是“Model-View-Co

16、ntroller”的缩写，即“模式一视图一控制器”。在MVC模式中，应用程序被划分成模型（Model）、视图（View）和控制器（Controller）三个组件14，如图2.3所示。各个组件的定义与作用如下：Model(模型)：该组件是应用程序最核心的部分，包含了应用程序的业务数据和业务处理逻辑。View(视图)：该组件代表用户看到并与之交互的界面。视图的功能就是向用户显示数据，向用户提供输入数据的接口。Controller(控制器)：该组件用于处理用户的请求，对模型和视图进行匹配， 协同完成用户的请求。选择视图(控制器)接受用户请求 调用模型响应用户请求选择视图显示相应结果业务处理（视图）显

17、示模型状态 接受数据更新请求把用户输入数据传递给控制器用户请求状态查询通知更新数据（模型）代表应用程序状态响应状态查询 处理业务流程通知视图业务状态更调用事件2.3.2 MVC 模式的优点图 2.3 MVC 模式图1. 模型、视图、控制器三者相对独立，降低了层与层之间的依赖，便于维护。2. 模型与视图分离，提高了应用程序的重用性。3. 提高了应用程序开发的灵活性，只需在稍作改动，就可轻松地实现许多功能。2.3.3 MVC 模式的JSP Model2 实现请求控制层（Servlet）例示Web 浏览器DB模型层（JavaBean）响应视图层（JSP）选择视图在Java Web 开发中，通常把 S

18、ervlet+JSP+JavaBean 的模型称为Model2 模型， 这是一个遵循 MVC 模式的模型。其中，JSP 作为视图层，JavaBean 作为模型层， Servlet 作为控制层。JSP Model2 实现 MVC 模式的结构图如图 2.4 所示：图 2.4 MVC 的 JSP Model2 实现结构图JSP Model2 的工作流程：当用户在视图层发送请求，控制层Servlet 接受该请求，并调用模型层的业务逻辑中相应的方法，得到处理结果，再将结果放到某个域对象中，传递给 JSP 页面，由视图层显示给用户。2.4 本章小结本章主要介绍了本系统开发过程中用到的开发技术，介绍了本系统

19、的采用的服务器端脚本语言 JSP，并介绍了 MVC 设计模式以及 MVC 设计模式在 JSP Model2 中的实现。排课系统分析与设计第三章 排课系统分析与设计3.1 排课系统需求分析系统需求分析的基本任务是准确地回答“系统主要是做什么？”这个问题， 即清楚、准确、具体地描述信息系统必须具有的功能、性能、运行规格的等要求10。本排课系统的设计目的，主要就是减轻人工排课的劳动强度，并为学生、教师和管理人员提供便利，实现信息的及时发布和反馈，人性化地进行教务管理。本系统的用户共有 3 类，分别是管理员、学生和教师。对于管理员，登录后，可以实现根据教学计划导入课程，对学生、教师、教室、班级等基本信

20、息进行维护， 以及处理教师或者学生提交的调课申请或者建议。学生登录后，可以查询课表安排，及对个人信息的维护，提交意见或建议。教师登录后，可以查询课表安排， 提交调课申请，及对个人信息的维护。综上所述，本系统的主要功能有：1. 系统登入功能：对于不同的用户，登录后产生不同的用户界面；2. 基本信息管理：对教师、教室等基本数据信息的增、删、改、查操作3. 排课管理：根据教学计划以及约束条件自动排课；然后，进行手工调整课表安排并进行冲突检测；4. 课表查询显示：根据查询条件显示并打印相应课表安排；5. 系统用户管理：授权与撤销用户的权限，以及修改用户密码。6. 课表建议管理：可以提出课表建议，并且查

21、询、处理课表建议。3.1.1 排课系统数据流图数据流图（Data Flow Diagram,DFD）是描述软件系统结构中数据处理过程的一种有力的图形工具10。排课系统数据流图，如下所示：1. 顶层数据流图系统管理员输入基本信息排课系统打印课程表学生、教师图3.1 顶层数据流图9系统管理员维护基本信息自动排课课程表手工调整打印课程表学生、教师2. 第一层数据流图3. 第二层数据流图图3.2 第一层数据流图基本信息表课课程表程表表 课程课程表系统管理员事务维护基本事务信息自 动排课手 工调整产 生课表课程表学生、教师3.1.2 排课约束条件图 3.3 第二层数据流图排课问题就是根据约束条件，对教师

22、、班级、时间、教室、课程这5个元素进行排列组合。排课问题中的需要考虑的约束条件可以分为硬性约束条件和软性约束条件。其中硬性约束条件，主要是为了解决排课过程中产生的各种冲突，如教室、教师、班级冲突，是必须遵循的原则，否则将会导致排课结果无意义。硬性约束条件，用于评价排课方案是否可行，凡是可行的方案，就必须不能破坏硬性约束条件。硬性约束条件有：1. 教师约束：同一个教师在同一时间一定不能教授多门课程；2. 教室约束：同一教室不能同一时间安排多门课程；3. 班级约束：同一班级不能同一时间安排多门课程；4. 除了以上3种条件，排课时也应该满足教室容量应大于班级人数，还有课程对应的教室类型正确；排课时，

23、除了考虑硬性约束条件，还要考虑软性约束条件。软性约束条件，用于评价排课方案是否合理，衡量排课方案的合理性和人性化。一般考虑的软性约束条件有：1. 合理充分的利用教室资源，就要保证上课学生的人数与教室容量尽量相匹配；2. 同一门课一周内在节次上要均匀分布；3. 体育课一般安排在上午3、4节或者下午；4. 公共课一般安排在主教学楼上课；5. 专业课一般安排在各个学院楼上课；综上所述，各个学校应该根据自身的实际情况，制定不仅符合教学规律又可满足诸多方面要求的原则方案。3.2 排课系统功能架构分析3.2.1 排课系统体系结构本排课系统采用了 B/S 三层体系结构，关于 B/S 结构的介绍，参照第二章2

24、.1 小节。Web 三层架构Controller(Servlet)浏览器请求Model(JavaBean)JDBCSQLServer响应View(JSP)表示层业务逻辑层数据访问另外，本排课系统以MVC与三层架构相结合的模式进行开发，大大简化了web系统开发的难度。Web的三层架构将Web应用系统分为表现层（UI）、业务逻辑层(BLL)和数据访问层(DAL)。其中表示层，即展现给用户的界面，用于输入和输出等。业务逻辑层，封装了对业务逻辑的处理，即通过调用数据访问层来进行数据处理。数据访问层，封装了所有跟数据库有关的操作。这样就实现了数据访问与业务层的分离。当数据库的结构发生改变时，只需修改数据

25、层的代码即可， 不用修改其他地方的代码。本系统的架构图，如图3.4所示：图 3.4 排课系统架构图排课系统分析与设计3.2.2 排课系统功能模块整个排课系统主要有四个功能模块：基本信息的管理、排课管理、系统用户管理、课表建议管理。其中基本信息管理包括对院系、专业、班级、教师、教室、学生、课程、教学计划等信息的增、删、改、查的操作；排课管理模块分为：自动排课、手工排课、查询课表、调课申请的管理,排课管理模块是排课系统的核心部分；系统用户管理模块包括授予用户权限(即为不同用户，例如管理员和普通教师，设置不同使用权限)和修改密码等；课表建议管理模块包括查看课表建议、处理课表建议以及对课表建议信息的维

26、护。系统的主要的功能模块，如图 3.5 所示：3.2.3 排课系统用例建模图 3.5 排课系统功能模块图用例图（UseCaseOiagram）：从用户的角度来描述系统功能，并指出各个功能的操作者。本排课系统的主要用户有三种：管理员、学生、教师。根据登录用户不同的访问权限初始化用户界面及功能模块，以下图 3.6、图 3.7 和图 3.8 分别为以管理员、教师和学生身份登录的系统用例图：10排课系统分析与设计图 3.6 管理员用例图1排课系统分析与设计图 3.7 教师用例图图 3.8 学生用例图3.3 数据库设计3.3.1 数据库概念设计数据库概念结构设计阶段最常用的方法是：实体-联系方法，描述工

27、具是： E-R(Entity-Relationship)。使用 E-R 方法可以形象的描述现实世界中实体直接的抽象概念模型。通过对本系统的功能设计要求分析可知，本系统中的主要实体分别是管理员、教室、课程、教师、班级等，本系统的 E-R 图如下：12排课系统分析与设计3.3.2 数据库结构设计图 3.9 E-R 图本排课系统中数据库的关系模式，如下： 管理员（编号，名称，密码）院系（系部编号，系部名称，所属学院代码，所属学院名称）专业（专业编号，专业名称，院系编号）班级（班级编号，班级名，专业编号，班级人数，年届）课程(课程编号，课程名称，学分，课时，上课时间，教室类别，教师编号， 专业编号，开

28、课院系,周学时)教师（教师编号，教师名字，性别，年龄，职称，院系编号，密码） 教室（教室编号，教室名称，教室类型，教室容量，教室地址）学生（学生编号，学生名字，性别，年龄，班级编号，密码）排课表（编号，教室编号，班级编号，课程编号，年级范围，单双周）数据库设计的是否合理也直接影响着系统编程的效率，所以数据库的设计也是很重要的。合理的数据库发计不但能以提高本系统存储速度，还可以保证本系统数据的完整性与一致性。本系统的数据库主要的数据表包括课程表、教师表、教室表、班级表、时间表、排课表等等，如下所示：1.管理员表(Admin)13排课系统分析与设计字段名字段描述数据类型字段大小允许空说明Admin

29、_id管理员编号varchar10否主键Admin_name管理员名称varchar30否Password密码varchar30默认 123456表 3.1 管理员表(Admin)2.院系表（Deptment)表 3.2 院系表（Deptment)字段名字段描述数据类型字段大小允许空说明Dept_id系部编号varchar10否主键Dept_name系部名称varchar30否Academy_id所属学院代码char2Academy_name所属学院名称varchar303.专业表（Profession）表 3.3 专业表（Profession）字段名字段描述数据类型字段大小允许空说明Pro_

30、id专业编号varchar10否主键Pro_name专业名称varchar30Dept_id院系编号varchar104.班级表(Class)表 3.4 班级表(Class)字段名字段描述数据类型字段大小允许空说明Class_id班级编号varchar10否主键Class_name班级名称varchar30否Class_num人数int4Class_year年届int4Pro_id专业编号varchar105.学生表(Student)外键17表 3.5 学生表(Student)字段名字段描述数据类型字段大小允许空说明Sid学生编号varchar10否主键Sname学生名字varchar30Ss

31、ex性别char2Sage年龄int4Class_id班级编号varchar10外键Password密码varchar30否默认 1234566.教师表（Teacher）表 3.6 教师表（Teacher）字段名字段描述数据类型字段大小允许空说明Tid教师编号varchar10否主键Tname教师名字varchar30否Tsex性别char2Tage年龄int4Ttitle职称varchar30Dept_id院系编号varchar10外键Passpword密码varchar30默认 1234567. 教室表(Room)表 3.7 教室表(Room)字段名字段描述数据类型字段大小允许空说明Roo

32、m_id教室编号varchar10否主键Room_name教室名称varchar30Category教室类型int4capacity教室容量int4addr教室地址varchar50在教室表中，教室类型的编码是：“0”代表普通教室，“1”代表计算机机房， “2”代表语音室，“3”代表体育场8. 课程表(Course）表 3.8 课程表(Course）字段名字段描述数据类型字段大小允许空说明Cid课程编号varchar10否主键Cname课程名称varchar30否Cmark学分int4Chours课时int4Cweeks上课时间varchar10Category教室类别int4Tid教师编号v

33、archar10外键Dept_id开课院系varchar10外键WeekHours周学时int4在课程表，课程编码中第一位表示课程的性质：T 表示通识课、Z 表示专业课、J 表示学科专业课。9. 教学计划表(TeachPlan)表 3.9 教学计划表(TeachPlan)字段名字段描述数据类型字段大小允许空说明id自动编号varchar10否主键Cid课程编号varchar10Pro_id专业编号varchar10Sem_id学期号int4其中，学期号的取值范围是 1-10，分别表示大学期间的各个学期。10. 排课表(Curriculum)在排课表中，关于单双周的问题，我们分别用“0”，“1”

34、，“2”，这三个字符表 3.10 排课表(Curriculum)字段名字段描述数据类型字段大小允许空说明id自动编号varchar10否主键Cid课程编号varchar10Class_id班级编号varchar10Time_id时间代号int4Room_id教室编号varchar10Semester学期范围varchar20DSZ单双周int4分别来表示全周，单周和双周三种上课情况。3.4 本章小结本章主要是对排课系统进行了需求分析和总体分析，以及对系统数据库进行分析与设计。排课系统算法设计214.1 遗传算法介绍第四章 排课系统算法设计遗传算法（Genetic Algorithm）是模拟生物

35、在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法 19。它最初由美国 Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知。80年代由Goldberge 进行归纳总结，形成了遗传算法的基本框架。到1997年5月，IEEE的Transaction on Evolutionaly Computation创刊，遗传算法作为系统优化、自适应和学习的高性能计算和建模方法的研究日趋成熟18,19。4.1.1 遗传算法的基本思想遗传算法是

36、从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成的。每个个体实际上是染色体带有特征的实 体。染色体作为遗传物质的主要载体，即多个基因的集合，其基因型是决定了个体的外部表现18。因此，遗传算法的第一步就是实现从表现型到基因型的映射编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生越来越好的近似解。在每一代中，根据个体的适应度大小选择个体，并且利用自然遗传学中的方法、理论进行交叉和变异，产生新的种群，依次不断的进行循环操作， 直到找出个体中最优个体才终止循环。最后把末代种群中的最优个体解码，产生问题的最优解。遗传算法的流程图见图4.1：开始产生

37、初始种群个体评价终止条件结束选择运算交叉运算变异运算产生新群体图4.1 遗传算法的流程图4.2 排课系统算法设计根据实际教学情况可知，排课问题就是将教师、时间、教室和学生等资源进行合理优化安排并取得合理解的问题20。通过对排课问题的数据分析、约束条件的分析以及对遗传算法的介绍，下面就要对如何利用遗传算法来解决排课问题进行算法设计与实现。4.2.1 时间片问题本系统考虑的是周课表，一般周六、周日不安排课程，所以只需要考虑周一到周五的课程安排即可。不考虑晚上，每天有八节课(上午 4 节，下午 4 节)，上课方式一般是“连堂课”，即 2 个相邻的小节，不能在上、下午之间跨时段。把每天用于上课的时间划

38、分为 4 个时间片，每周有 5 天上课，一周可划分为 4*5=20 个时间片。分别用 T1，T2，T3T20 来表示一周中的各个时间片，则每周的时间片表分布，如下表 4.1 所示：星期一星期二表 4.1周时间片分布表星期三星期四星期五T1 T2 T3T4T5 T6 T7T8T9 T10 T11T12T13 T14 T15T16T17 T18 T19T204.2.2 染色体编码编码是应用遗传算法时要解决的首要问题，它不仅决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型到解空间的表现型时的解码方法，同时，也影响到交叉算子、变异算子等遗传的运算方法 19。故对于编码的设计需要考虑到这

39、几方面的因素。在排课系统应用中，每个染色体代表一次教学课程，其结构可表示为一个向量：(班级ID，课程ID，教师ID，教室ID，时间段)所有的教学课程就是一个可能的排课结果，其结构是一个二维的数组 17。结合排课问题的实际特点，本文采用二维数组来表示染色体编码，这样的设计可以方便遗传算子的运算。假设有M 个班级，时间片段为T1-T20，则由T1-T20中的值就是染色体基因，其中每个基因是由教师编号、课程编号和教室编号组合而成的，一个染色体是由班级编号和染色体基因组成的。一行代表一个班级的课程表，称之为“染色体”；M个染色体组成“个体”，即为一个排课方案；种群是由N个“个体”组成，设计的基本思路如

40、表4.2所示：下面介绍本文采用的基因编码：表4.2 染色体编码示意表班级1班级2T1 T1T1T2 T2T2TJ TJTJT19 T19T19T20 T20T20班级IT1T2TJT19T20T1T2TJT19T20班级M-1T1T2TJT19T20班级MT1T2TJT19T20对于基因编码的设计，本文主要考虑了两个因素：方便冲突检测、和方便解码和计算适应度函数。由于在数据库设计阶段，已经把课程与教师信息捆绑，基因编码由原来三元素，转变为了二元素（课程，教室）。但是考虑到排课过程中的冲突检测，需要将教师编号、教室类型和教室编号进行编码。由于遗传算法要求的编码原则是：一、有意义的积木块原则；二、

41、最小字符集编码原则19。所以对于基因的编码采用了与数据库数据编码相同的符号编码方法。同时，这样也有利用从基因型到表现型的解码操作。综上所述，本文采用的基因编码规则：教师编号(10)+课程编号(8)+教室编号（6）+所需教室类型（1）+是否为单双周（1），编码长度为10+8+1+6+1= 26个字符。其中教室、教师以及课程编码均与数据库中的编码相同。关于教室类型编码以及单双周编码已在数据库设计阶段已给出，此处不再赘述。例如，基因编码：6101000003 Z6101003 61A102 0 0，放在二维数组中第i行第j列，则表示教师编号为6101000003的教师，在第j个时间段给第i个班级，在

42、编号为61A102的教室上编号为Z6101003的课程，该课程占用普通教室，其是全周上课。4.2.3 产生初始种群种群中每个个体都代表了一个不同的排课方案。在初始二维数组时，从第一个班级开始，把基因编码放入该行的时间片中，用随机函数产生120个数，如果该时间片已经有数据，则重新产生，直至将该班级本学期在教学计划内的所有课程对应的基因编码都填入其中，这样就产生了一条“染色体”。继续填充下一个班级的课程表，直至所有班级的课程表都已经填充，这样就产生了一个“个体”。然后，按种群规模的大小，产生一定数量的个体，这样就组成了一个初始种群。在基因编码时，本人对于随机分配的教室进行了教室类型和容量的检测，在课表生成时排除了这几种冲突。另外，本人设计了教师时间类（Teacher