高校排课系统分析与设计

本科生毕业论文(设计)河南财经政法大学排课系统分析与设计 姓名学号专业指导教师2011年5月25日IV摘 要近年来，随着高校教育事业的不断发展，课程编排问题在一定程度和深度上影响着学生培养与教学质量的提高。随着学生人数的不断增加，排课成为比较繁重而重要的教学工作。如何科学合理地编排课程表是每个教学管理的一项重要工作。课程表是一个学校日常教学工作的“指挥表”，是具体实施教学计划的重要组成部分，是教学管理的关键环节。通过手工排课，不仅费时、费力，而且在较短时间内用人工编制一份令人满意且使学校现有资源得到充分利用的课表也不是一件容易的事。因而开发一套符合实际需求的高校排课系统是非常必要的。经过对河南财经政法大学教务工作全面的调查和研究，结合其教务管理中的实际要求，设计出了河南财经政法大学排课系统。具体来说，该系统的设计必须考虑到本校自身的教学管理特点和特殊性。本系统采用自动排课和手工调课相结合，整个系统根据功能划分为系统管理、资源管理、排课管理和输出管理等四大功能模块。该排课系统区分管理员、教师和班级三者的不同身份，给出不同的权限，在页面中根据身份判断来实现其相应具有的功能。它根据班级的课程设置、课程每周内的次数、现有的教室资源、以及现有的教师资源进行科学的合理安排，实现了对教师资源、教室资源、时间资源、课程资源的综合管理。通过建立排课系统的数学模型，利用遗传算法进行问题求解，然后生成课程表。本排课系统采用Visual Studio 2005为开发环境，采用ASP.NET 2.0+SQL Server 2005开发技术，利用C#语言进行编程求解，系统设计简单易懂，界面友好，操作方便。关键词：排课系统；遗传算法；ASP.NET 2.0 AbstractWith the constantly development of high education, timetabling has very important role in training students and rising the education quality. Along with the increasing number of students the lesson arrangement is becoming a particularly hard and key teaching task. How to arrange curriculum schedule reasonably is a key job of each schools teaching management. As being conductor form of daily teaching work, the curriculum schedule plays an important part during the specific teaching plans carrying out, and also is the key that links teaching management. As achieving a perfect Curriculum Schedule in a short time by manual work is not only takes great deal of time, but also is absolutely impossible to make full use of current resources, it is vital significance to develop a set of actually automatic Course Scheduling system.After the investigation and research of academic work of Henan University of Economics And Laws and combining the actual demand in the teaching management, the Course Scheduling System of Henan University of Economics And Laws is designed. Specifically, the design of the system must consider the universitys own teaching management characteristics and particularity. The System combines automatic course arrangement and manual adjustment. According to function, it is divided into system management, resource management, courses arranging management and output management and so on .The System distinguishes system administrators, teachers and classes of these three different roles. Different permissions are given in the page in accordance with the identity function to determine its corresponding use of such systems. It is based on class curricula, the number of weekly sessions, the existing classroom resources and teacher resources to make the scientific and reasonable arrangement. This paper presents the integrated management of teachers, classroom resources, time resources and curriculum resources. The System makes a mathematical model, uses the genetic algorithm, and finally generates the curriculum schedule.The Course Scheduling System uses Visual Studio 2005 as the development environment, adopts the development technology of ASP.NET 2.0 and SQL Server 2005 and uses the programming language of C# to programme, which is designed to be easily understood, friendly interface and easy to operate.Key words：Course Scheduling System ,Genetic Algorithm ,ASP.NET 2.0目 录1 引 言11.1 课题的背景11.2 课题的目的和意义11.3 本文的主要工作21.4 本文的内容安排22 系统环境与开发工具的介绍32.1 系统的B/S结构简述32.2 ASP.NET简述32.3 SQL Server 2005简述42.4 C#简述52.5 本章小结63 系统分析73.1 需求分析73.1.1 功能需求73.1.2 性能需求73.1.3 出错处理需求83.2 系统流程分析83.3 可行性分析113.3.1 经济可行性分析113.3.2 操作可行性分析113.3.3 技术可行性分析113.4 遗传算法的分析113.4.1 遗传算法的一般算法123.4.2 遗传算法的原理133.4.3 遗传算法在排课问题中的应用153.5 本章小结174 系统设计184.1 功能设计184.2 数据库设计204.3 E-R图224.4 本章小结245 系统实施255.1 系统的登录界面255.2 班级登录的主界面275.3 教师登录主界面285.4 管理员主界面285.4.1 系统设置的功能实现295.4.2 资源管理的功能实现315.4.3 排课管理的功能实现345.5 本章小结396 系统测试406.1 测试目的406.2 软件测试的内容406.3 本章总结417 结 论42参考文献43致 谢44附 录45 1 引 言1.1 课题的背景从计算机的出现直到今天，计算机的应用已经涉及到各个层次功能，其强大的功能已为人们深刻认识，它已进入人类社会的各个领域并发挥着越来越重要的作用。学校排课系统是一个非常实用的功能软件，在学校的管理方面会起到一个很大的作用，是利用计算机来解决日常问题的标准体现。新世纪的开端，学习和教育成为全人类关注的焦点。只有率先认识到信息技术在现代教育中的重要作用，用它解决教育中的问题，把它作为现代教育的基本工具，才能在全球教育竞争中立于不败之地。学校排课系统作为学校的信息基础设施重要工具之一，使现代教育能突破传统的教育模式进入到全新的境界，使素质教育成为未来教育的制高点。课程的安排是学校教学系统中的一个重要环节，是维护学校教学秩序正常进行的重要保证。随着学院规模扩大，招生人数增加，必然会导致教师增加、新课程开设以及新教学设施的增设等问题出现。所有这些都将增加学校教务方面制定课程以及学院各系教学负责人对课程安排工作的负担，如果教学负责部门仍旧处于现有人工方式管理排课，必然会进一步加重教学负责人员在排课时的负担，诸如：课程冲突、任课教师冲突；随机性不足等。课程的安排工作日益复杂和繁琐使得学校课程安排的合理与否直接体现了教务部门的工作效率和学校的教学质量。现在学校迫切需要一种自动化程度相当高的计算机软件来进行排课，并进行课程信息的管理。在这种背景下，我们需要开发一种排课系统。1.2 课题的目的和意义学校自动排课系统将使学校的课程计划管理工作更加规范化，系统化，程序化，提高信息处理的速度和准确性，能够及时、准确、有效的查询和修改课程情况。目前人工排课浪费了许多人力和物力，在信息时代这种传统的管理方法必然被计算机为基础的信息管理所取代。采用排课自动生成系统已成为学校管理科学化和现代化的重要标志，它给学校管理带来了明显的经济效益和社会效益。主要体现在：极大提高了排课管理工作人员的工作效率，大大减少了以往排课时各学科排课流程繁琐，杂乱，周期长的弊端。使用计算机进行自动排课，可以使教务管理人员迅速掌握全校教学情况，提高教务管理工作的效率，加快其现代化进程。排课自动生成系统管理的操作自动化和信息的电子化，全面提高了学校课程安排的管理水平。因此，针对我们学校的管理的具体要求，我设计并开发了河南财经政法大学排课系统。1.3本文的主要工作传统的人工排课，最令人担心的问题就是出现教师资源冲突或教师资源冲突的情况，而且工作繁琐，工作量巨大，尤其是在给大学校园进行排课时出现的问题更多。由于各个高校的教学安排都不相同，我根据河南财经政法大学自身教学的特点，设计了河南财经政法大学排课系统，并编写了河南财经政法大学排课系统分析与设计的论文。在本论文中，首先论述了高校排课系统的研究背景及其意义；然后对要开发的河南财经政法大学排课系统所需要的开发环境和开发工具进行了简单的介绍；对该系统进行了较为详细的分析（包括需求分析、系统流程分析、可行性分析以及遗传算法分析）；对该系统进行了功能模块设计（包括系统管理模块、资源管理模块、排课管理模块以及输出管理模块）；在对系统分析与设计的基础上，运用ASP.NET 2.0和SQL Server 2005开发了河南财经政法大学排课系统；最后对已经开发的系统进行了测试。1.4 本文的内容安排本论文的内容安排如下：第一章引言，其中介绍了课题研究的背景，课题的目的和意义。第二章系统开发环境及开发工具介绍，其中包括对B/S结构、ASP.NET、SQL Server 2005以及C#的简单介绍。第三章系统分析，其中包括需求分析、可行性分析、河南财经政法大学排课系统所运用的遗传算法分析等。第四章系统设计，其中包括功能设计、数据库设计等。第五章系统实施，主要是对系统中各功能模块的详细设计。第六章系统测试，其中包括测试目的、软件测试的内容以及测试时间等。第七章总结，对在写整篇论文过程中的感受进行总结。 2 系统环境与开发工具的介绍河南财经政法大学排课系统是基于B/S模式设计的，它选择的前台开发工具为ASP.NET 2.0，后台数据库管理工具为SQL Server 2005，开发环境为Microsoft Visual Studio 2005，其Web服务器为IIS 5.1及以上版本。2.1 系统的B/S结构简述B/S结构（Browser/Server，浏览器/服务器模式）是WEB兴起后的一种网络结构模式，WEB浏览器是客户端最主要的应用软件。这种模式统一了客户端，将系统功能实现的核心部分集中到服务器上，简化了系统的开发、维护和使用。 客户机上只要安装一个浏览器（Browser），如Netscape Navigator或Internet Explorer，服务器安装Oracle、Sybase、Informix或 SQL Server等数据库。B/S模式体系结构的原理如图2-1所示，浏览器通过Web Server 同数据库进行数据交互。图2-1 B/S模式体系结构原理图B/S结构的优点：具有分布性特点，可以随时随地进行查询、浏览等业务处理；业务扩展简单方便，通过增加网页即可增加服务器功能；维护简单方便，只需要改变网页，即可实现所有用户的同步更新；开发简单，共享性强。2.2 ASP.NET简述简单的说，ASP.NET是一种服务器端动态网页开发技术。目前，存在许多动态网页的开发技术，ASP.NET的前身ASP（Active Server Pages）以其简单的语法、嵌入HTML方式等特性，在动态Web技术领域取得了成功，成为Windows平台上的霸主。后来又出现了PHP、JSP等技术。PHP由Zend公司出品，JSP由SUN公司出品，两者在执行效率、安全性等特性上均优于ASP。它们免费使用，并可以跨平台，在Windows、UNIX、Linux服务器上均可构建动态Web系统。二者的出现，占有了ASP大部分的市场使ASP的统治地位受到了挑战。在这种情况下，在ASP的基础上，微软公司于2000年11月发布了ASP.NET，并于2005年正式发布了功能更为强大、使用更为简单的ASP.NET 2.0刘乃丽，2007。在ASP.NET 2.0中，重新设计和实现了其中的很多类。为了实现更高的开发效率，还增加了一些新的控件。对于Web应用设计和开发人员而言，ASP.NET 2.0是Web开发史上一个重要的里程碑。ASP.NET 2.0在继承了传统优点之后有了新的跨越。总体来说，ASP.NET 2.0的新特征主要体现在新的服务器控件、页面框架、服务与接口3个方面。更丰富的服务器控件：ASP.NET 1.x的内置服务器控件数量有限、功能覆盖面窄，ASP.NET 2.0新增了数十个服务器控件，包括数据控件、登录系列控件、Web部件、站点导航控件和其他控件等。这些服务器控件对于提高工作效率，降低开发成本有着重要作用。页面框架：ASP.NET 2.0新特征在页面上的体现包括：母版页、主题和皮肤、编译机制和本地化。母版页特性能够帮助用户建立具有统一布局和外观的页面。主题和皮肤使ASP.NET可以一次性设置一种类型的服务器控件外观样式。在应用程序编译方面，ASP.NET 2.0提供了几种替代方案，从而扩大了编译的选择范围，开发人员可以根据特定需要进行选择。服务与接口：服务与接口包括成员资格管理、角色管理、用户配置、数据缓存、配置与管理工具等。利用这些功能，可以快速实现用户和角色管理、个性化用户配置、数据缓存、应用程序可视化配置等任务。2.3 SQL Server 2005简述SQL Server是一个功能完备的数据库管理系统。它包括支持开发的引擎、标准的SQL语言、扩展的特性（如数据复制、OLAP分析）等功能，支持存储过程、触发器等特性。SQL Server 2005除了在性能、处理能力方面比SQL Server 2000提高之外，SQL Server 2005还带来了许多新的特性，例如对XML的支持、在SQL语言中嵌入高级语言的支持、在企业环境中，更注重安全性、高可用性、集成的管理工具等刘乃丽，2007。下面是SQL Server 2005的新特性和重要改进之处。支持XML。作为一种标准数据交换格式，XML主要用于在不同系统中交换数据，以及在网络上传递大量的结构化数据。虽然XML具有广泛的应用和巨大的影响，但目前主流的数据库管理系统还是以支持关系型数据为主。相对而言，SQL Server 2005对XML提供了目前最强大的支持。用高级语言编写数据库对象。除了使用SQL语言之外，SQL Server 2005还支持直接使用高级编程语言编写数据库对象。这带来的优点有两个，一是SQL语言本身的功能还比较弱，使用高级语言可以实现更强大的功能；二是高级编程语言如C#等已经拥有非常庞大的开发队伍，直接使用高级语言开发数据库对象降低了程序开发和维护的难度。自定义数据类型。SQL Server 2005真正开始支持自定义数据类型（UDT），使用UDT将大大提高数据库的数据存储和处理能力。与ADO.NET 2.0紧密结合。伴随着ADO.NET 2.0新的改进，如对多种异构数据库之间实现分布式事务的支持、新的连接提供程序模型、对异步编程的支持等，SQL Server 2005与之紧密结合，实现最佳的数据支持。增强的SQL。除了一些功能更强的SQL函数，SQL Server 2005还增加了包括支持异常处理等一些新的内容。数据库镜像。数据库镜像功能可以大大提高SQL Server的安全性，能在数据库发生故障几秒钟内切换到备用系统上。全文索引增强。全文索引提供了将大量文档存储在数据库中，而又能够快速搜索这些文档的支持。SQL Server 2005在全文索引的存储、搜索性能上比旧版本有了明显的增强。管理、监控、开发工具的集成和增强。SQL Server 2005将管理、监控、开发工具集成在一起，方便使用。存储引擎的改进。在数据库核心的存储引擎部分，SQL Server 2005做了大量的改进，因而整体性能、稳定性和可靠性都比SQL Server 2000有明显增强。2.4 C#简述20世纪70年代，人们设计出了高效灵活的C语言，后来又在C语言中加入了面向对象的技术形成C+语言。C+为我们带来了强大的功能和高度的灵活性，但正是由于C+的复杂和灵活，使我们必须忍受艰苦的学习过程和漫长的开发周期，而且内存泄露和缓冲区溢出的痼疾也使很多初学者头痛不已。因此，许多程序员一直在寻求一种新的语言，以图在开发能力和学习难度之间取得更好的平衡。C#语言的出现解决了这种问题。C#语言源于C+，吸取了C+的长处，摒弃了C+的缺点，增加了很多易用的新特性，同时剔除了C+中一些复杂和容易出错的语法，让碍事的东西统统走开，这使C#在功能强大的同时保持简单易学，鱼和熊掌兼得。C#语言的特点如下：简洁流畅的语法。随着C+的不断扩充和发展，语法冗余成了C+挥之不去的弊端。C#进行了大刀阔斧的改革，相似的功能只保留最常用的一种，让鸡毛蒜皮的东西走开。简洁流畅成了C#吸引人们目光的资本，易学易用成了C#鹤立鸡群的特征。精心的面向对象设计。C#是一种完全的、纯粹的面向对象语言，不但支持封装、继承、多态性等面向对象技术的关键特征，而且增加了特性（Attribute）、属性（Property）、委托（Delegation）、可容类型（Nullable Type）等强大功能。同时C#也是一种传统的面向对象语言，只支持标准的单一继承，避免了C+中因多继承而带来的复杂性。与Web结合紧密。C#语言既适合传统编程，也适合Web编程，它与ASP.NET技术紧密结合，无缝支持各种分布式应用。因此，C#使创建丰富的Web网站变得很容易。严格的安全性与强大的错误处理能力。C#的许多特性为构建强壮的应用程序提供了保证。比如：垃圾回收机制（Garbage Collection）自动回收无用对象占用的内存；异常处理（Exception Handing）提供了结构化的、可扩展的错误检测和处理方法；安全类型（Type-safe）避免了引用未初始化的变量、数组索引越界、执行未经检查的强制类型转换等问题。这些都可以使您的编程更有效率，少一些因为不明错误而抓狂的时间。优秀的版本处理技术。为了缩短开发周期，增强可靠性，软件一般会调用他人已经编写好的久经考验的组件。但是软件的开发者会不断地改进软件，组件的设计者也会不断地升级组件，同一名称的组件可能会有多个版本，如果一个旧程序调用了新版本的组件，就可能产生意想不到的问题。为此，C#设计了优秀的版本处理技术，确保软件能调用到匹配的组件。C#语言还有很多优点，比如良好的灵活性和兼容性、统一的类型系统等。C#拥有的众多优点能使我们快速地融入开发过程，不费吹灰之力编写出需要的应用程序。2.5 本章小结本章主要介绍了河南财经政法大学排课系统所用的开发工具、开发环境，对系统所运用的B/S结构进行了介绍，并对将要使用的ASP.NET 2.0、SQL Server 2005和C#语言进行了简单介绍。3 系统分析 系统分析对于河南财经政法大学排课系统的设计至关重要，在本章中对河南财经政法大学排课系统进行了需求分析、系统流程分析、可行性分析，同时还对河南财经政法大学排课系统所采用的遗传算法进行了分析。3.1 需求分析3.1.1 功能需求河南财经政法大学排课系统的设计理念是以解决实际问题出发，所以，应用其功能方面要求简单、流畅、清晰易懂，基本的功能需求是可以进行手工调整课表，课表需要有按照班级为基准进行课表安排的功能，有按照教室为参考条件为基准进行排课的功能，还可以按照教师的课表进行安排修改。课表的安排应该以每周为基本课时，有统计周课时量的功能，统计功能分为教师周课时统计和班级周课时统计，课程表可以存储，可以根据用户的权限，按照教室，教师，班级等不同条件进行查询检索。可以对教师信息、教室信息、班级信息等进行修改、添加、删除。排课系统的自动进行排课部分是不可取少的，本排课系统应该以实现自动排课为最终目的，因此要求自动排课的方式简单、迅速，排出的课表合理，当出现错误时提示报错，要求教师的每周课时大至相同，课时安排平均，班级每节课程安排合理。本排课系统的主要功能是把各系别，班级或各授课部门的课程进行了汇总，然后根据学校的教学计划制订各班级的课程编排表。随着学校每年的扩招和专业的不断细化，学校班级，课程门数越来越多，每门课又涉及很多信息，如果仍然采用人工排课，则不可避免地会出现教室资源冲突或教师资源冲突的情况。我们竭力借助计算机通过自动排课功能、手工调课功能来避免教室资源冲突或教师资源冲突。3.1.2 性能需求河南财经政法大学排课系统的性能要求在稳定的基础上快速反应，操作平台以Windows XP专业版为标准，硬件配置以RAM：2.00GB为标准。基本信息的添加，修改部分反应时间应控制在3秒以内，查询部分应控制在5秒以内，课表部分的信息由于工作量较大，处理的方法较多响应时间会较慢，添加、修改部分的响应时间不应该太长。总的系统占用硬盘空间尽量不要超过50MB，系统运行过程中占用内存不可以过多，在功能运行其间CPU利用率达70%以上时间不可以连续太长时间，课程表在数据库存储中单条记录不要超过0.5KB。自动排课功能方面，要求尽快生成一个可供查询的完整课程表单。排课问题需要满足一些约束条件，分为保证不冲突的硬约束条件和使排课结果更满意的软约束条件。鉴于本系统的思路，约束条件表达如下：硬约束条件：必须根据教学计划所规定的学时数排课，不得任意增减；教室的类型要能满足课程需求；教室容量大于上课班级人数之和；同一教学班级、教学场地及教师在同一时间均只能进行一次教学安排；学生、教师跨校区、跨教学楼上课的情况下，要拥有足够的时间到达下一门课上课地点石俊萍，2010。软约束条件：同一课程的教学时间间隔必须合理；各个班级、教师乃至学校整体的课程密度尽可能平均；班级课表文理课程交叉搭配排课；减少教师连续两门课情况下教学场地之间的路程；一门课程尽量安排在同一教室内；学生同一半天尽量不跨校区；上课班级总人数应尽量接近教师容量，使全部班级离差的平方和最小；繁难课程应尽量排在精力充沛时间，如上午1-2节。体育课尽量排在下午或者上午3-4节；教师的其他特殊要求石俊萍，2010。3.1.3 出错处理需求系统的可用性方面，河南财经政法大学排课系统需要强大的容错能力，要求程序运行的稳定，并且对逻辑错误的判断提示功能必须准确无误。当程序运行出现错误的时候应该有一定的报错功能，程序的每个功能模块的返回值应为正确无误的所需值，当出现错误的时候应给出相应的错误代码提示。各个接口部分出现错误的时候会弹出错误提示以便于跟踪。系统可以给出提示为操作人员提供部分解决方案，如重新启动程序、重新录入数据、检查有无逻辑错误等方法。软件开发的目的是开发出一个真实可用的正确的系统而不是无休止的利用出错处理代码来掩盖自己的错误，应该利用自己可以掌握的资源来对错误进行跟踪处理，以达到程序的可用成度。3.2 系统流程分析河南财经政法大学排课系统的系统流程简单，主要是安排各部分之间的数据相互读取存储。数据首先由系统操作人员输入，通过资源管理模块分别存入教师信息表、教室信息表、班级信息表、课程信息表几个表中。在自动排课方面，对几个数据表不做修改，自动生成一个新的数据表，存入数据库。然后根据教师调课申请以及其他因素通过手工调课对产生的新课表进行完善。经过自动排课及手工调课操作的处理，最终生成一个新的数据存入课程表。河南财经政法大学排课系统的系统流程图可以分为三个部分，即从班级、教师、管理员的角度画出各自的系统流程图。班级用户需要查询本班的班级课表，如果需要打印，可以完成课表打印。图3-1表示河南财经政法大学的班级权限的业务流程图。图3-1 班级权限的业务流程图教师用户可以查询自己的课程表，如果需要，还可以完成其课程表的打印。同时，如果教师对排课问题有异议，需要进行调课，可以申请调课。图3-2表示河南财经政法大学教师权限的业务流程图。图3-2 教师权限的业务流程图管理员用户需要完成基本信息（教师信息、教室信息、班级信息、课程信息等）的操作，如添加信息、删除信息、修改信息等。根据基本信息的录入，管理员要完成自动排课和手工调课，最终生成课程表。图3-3表示河南财经政法大学管理员权限的业务流程图。图3-3 管理员权限的业务流程图数据流图是对系统调研的业务流程图进行分析的基础上，从系统的科学性，管理的合理性，实际运行的可行性角度出发，将信息的处理功能和彼此之间的关系在逻辑上精确地描述新系统应具有的功能、数据输入、数据输出、数据存储及数据来源和去向。图3-4是河南财经政法大学排课系统在排课管理模块中的数据流程图。 管理员P1班级信息P2课程信息P3教师信息P4教室信息教室信息教师信息课程信息班级信息P4-2教室验证P3-2教师验证P2-2课程验证P1-2班级验证确认教室信息确认教师信息确认课程信息确认班级信息F1 班级信息表F2 课程信息表F3 教师信息表F4 教室信息表验证过的信息验证过的信息验证过的信息验证过的信息P5排课班级信息课程信息教师信息教室信息F5 课程表课程表信息图3-4 排课管理模块的数据流程图3.3 可行性分析3.3.1 经济可行性分析经济可行性是对将要开发的系统的成本效益进行的量度，可以说是可行性分析中最重要的一个，以低成本追求高效率是我们的目标。河南财经政法大学排课系统是通过计算机来自动地解决各种教学资源如教室、教师的合理有效利用问题，避免教师、班级在上课时间、地点上的冲突，使排课时间分配均匀，这就大大的节省了时间，提高了工作效率，避免了人力、物力、财力的浪费，由此可见，开发此系统在经济上是完全可行的。3.3.2 操作可行性分析如今的计算机已经走进千家万户，硬件成本的下降导致计算机购买成本的降低。我所开发的河南财经政法大学排课系统是利用微软的集成开发环境Microsoft Visual Studio 2005作为软件的开发平台，运用ASP.NET 2.0语言和SQL Server 2005数据库进行开发。所开发出来的系统有直观的用户界面、有良好的安全性设置、有详细的操作说明书，这样使各类用户很快地掌握系统的使用方法和操作，因此在操作上是可行的。3.3.3 技术可行性分析从目前IT业界比较流行的数据库开发、管理软件来看，运用ASP.NET 2.0和SQL Server 2005的结合无疑是在实际应用中较为成功的一种解决方案。该技术为用户提供了操作简单的用户界面，完善强大的数据库操作功能和简洁明了的数据库接口。所以技术实行起来相对会容易。综上所述，开发河南财经政法大学排课系统是可行的，可以进行开发。3.4 遗传算法的分析 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授本人所提出的GA通常被称为为简单遗传算法（SGA）业宁，梁作鹏，董逸生，2003。遗传算法是从代表问题可能潜在的解集的一个种群(population)而逐步开始的，而一个种群则由经过基因(gene)编码的拥有一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码的工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度(fitness)大小选择(selection)个体，并借助于自然遗传学的遗传算子(genetic operators）来进行组合交叉(crossover)和变异(mutation)，产生出代表新的解集的种群体。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于数据环境，末代种群中的最优个体经过解码（decoding），可以作为问题解集的近似最优解。由于遗传算法的整体搜索策略和优化搜索方法在计算中不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体的领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。3.4.1 遗传算法的一般算法遗传算法基本流程如图3-5所示。图 3-5 遗传算法流程图遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：1 创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。2 评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。3 繁殖(包括子代突变)带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。4 下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代衍化下去，直到达到期望的解为止。5 并行计算非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。3.4.2 遗传算法的原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，逐步地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解唐勇，唐雪飞，王玲，2002。1 遗传算法的目的典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：考虑对于一群长度为L的二进制编码bi，i1，2，n，且bi0,1；给定目标函数f，有f(bi)，并且0f(bi) 遗传算法的基本原理长度为L的n个二进制串bi(i1，2，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：(1) 选择(Selection)这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。(2) 交叉(Crossover)这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。(3) 变异(Mutation)这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反之亦然。3遗传算法的步骤和意义(1) 初始化选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。通常以随机方法产生串或个体的集合bi，i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。(2) 选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。适应度较高的个体，繁殖下一代的数目较多。适应度较小的个体，繁殖下一代的数目较少，直至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。(3) 交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换，目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体S1=100101，S2=010111选择它们的左边3位进行交叉操作，则有S1=010101，S2=100111。4 变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。例如有个体S101011。对其的第1，4位置的基因进行变异，则有S=001111。单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。5 全局最优收敛(Convergence to the global optimum)当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。3.4.3遗传算法在排课问题中的应用排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一个NP完全问题。根据学校课表的特点，采用遗传算法，给出染色体编码和适应度函数，提供了利用遗传算法解决排课问题的方法。排课的冲突异常复杂，对于这些冲突的复杂度我们进行分析给出了分析的过程。过程1：将模型中的五个集合降维为一个给定四维空间V(S，T，R，C)，称之为：课表，四维分别代表了：S（教师）：全校所有课程的任课教师；T（时间）：上课的时间段，每天分为1-2、3-4、5-6、7-8、9-10，总共五个时间段，每学期18周，每周五天，合计每学期有450个上课时间段；R（教室）：全校所有的可用教室，包括不同的教室属性，如：教室大小、是否为多媒体或语音教室等等；C（班级）Class：当前学期的所有教学班级，包括班级属性，如：班级人数、是否合班。过程2 ：在课表V中求解存在着子空间L。过程3 ：在课表V中求解存在着四维向量l (Sr，Tm，R，C)，且lL，那么称l为：课。过程4 ：在课表编排过程中，对于P( liVljL，i，jN)，li (Tr，Tm，R，C)与lj (Tr，Tm，R，C)，没有冲突，认为V是：有效课表。通过对四维向量li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)的简化。在排课过程中的所有关系情况TmR + Tm RC。那么：由过程1、过程2 可以推导出，在课表空间中，恒有f (Tr，Tm，R，C)，那么V就是有效的课表。最后为了简化，再给出过程5。过程5 ：在课表V中，对于li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、jN，没有冲突，记为：lilj ；对于Li、Lj没有冲突，记为：LiLj。这样有对于P( liVljL)，li (Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、jN，没有冲突，就可以得到VL。基于这样的约束条件，排课的具体操作需要逐一设计约束及判断函数。课表的编排，简单地说就是给课程分配时间和教室。河南财经政法大学排课问题中课程安排最重要的是时间、课程、教室没有冲突。排课问题包含的相互制约的因素有：时间、教室、课程、教师、班级。一张正确的课表应至少满足以下条件：1 一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程；2 分配的教室可容纳人数应该大于学生数；3 对于任意班级，某门课程一周内的授课时间数固定。除了上述的硬性约束，还些软约束，这些软约束有助于使得课表更加合理，更加人性化。这些软约束条件可能是：1 尽量在早上安排必修课，而下午安排选修课；特殊的课尽量安排在上午，体育课一类户外的课，尽量安排在下午；2 尽可能满足个别教师的特殊上课时间要求；3 一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化；4 一个教师的课不能排满一整天；5 学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况；6 资源利用率，即教室容量与上课人数的关系等。这些软约束条件各院校有所不同，在我这次设计中我将依据我个人定义的约束来解决冲突问题并进行优化操作。可以认为，在符合约束条件的情况下，能最大限度满足经验要求的课表安排方案是优良的。遗传算法的优化求解方式在软件工程中是一个代表性的领域。一个完整的遗传算法应用于河南财经政法大学排课系统是十分繁琐复杂的。排课问题在很早就是一个国内外软件研究机构的研究关键而真正投入使用的很少，因为排课的关键问题就是算法的选择。遗传算法的优越性是无可替代的，在本次系统设计中遗传算法的应用并没有达到这样的高度，只是简单的借鉴。3.5 本章小结软件开发过程中系统分析是最重要的部分，为了开发出真正满足用户需求的软件产品，本章对系统进行了详细的分析，其中包括对系统的需求分析、流程分析以及可行性分析，从而能够更全面的掌握整个系统的设计流程并且判断系统是否可行。在本章还特别对河南财经政法大学排课系统所要采用的遗传算法进行了分析。 4 系统设计 对河南财经政法大学排课系统进行详细的系统分析之后，需要对其进行