基于智能规划与矩阵运算的智能排课系统设计

基于智能规划与矩阵运算的智能排课系统设计（共3篇）

基于智能规划与矩阵运算的智能排课系统设计 篇1

基于智能规划与矩阵运算的智能排课系统设计

为解决目前高校自动排课系统设计复杂、排课效率低的问题,提出了一种基于智能规划和矩阵运算的.排课算法.该算法能高效、快速、优化地实现自动排课,并简化了程序的复杂性.

作 者：宋建强 钱雪忠 作者单位：江南大学信息工程学院,江苏无锡,214122刊 名：科技资讯英文刊名：SCIENCE & TECHNOLOGY INFORMATION年，卷(期)：“”(31)分类号：P20关键词：自动排课 智能规划 智能排课

基于智能规划与矩阵运算的智能排课系统设计 篇2

1.1 智能化选课排课系统在教务综合管理系统中的地位作用

近年来,为了适应教育改革和推进素质教育的发展,学校的招生规模不断扩大,学生数量随之急剧增加。我国大多数高校开始实施弹性的选课学习制度,这种方式要求学生在规定的学习年限中完成所有课程(或全部学分)。从而增大了学生选课的不均匀性,使高校教务管理者的工作量日益繁重,手工管理已无法满足学校管理者对管理的需要,这就要求必须有一个完整的、智能化的选课排课管理系统来实现这种功能,选课排课系统只是学籍管理的部分,但却在教务综合管理系统中占有很重要的地位,其是否能正常准确运行保证着教学、实验课程的具体实施,目前由于该系统的难度和各学校资源情况的差异,大多数学校实行的半智能化、半手工化的混合管理,这不仅消耗大量的人力、物力、财力,还在管理过程中存在着大量的不可控因素,造成了管理不规范、不科学、工作效率低,甚至难以达到预期目的。如何更好的进行选课排课系统管理,成为学校管理者面前的一个亟待解决的问题。

本文通过大量的数据信息的调查和汇总,对学生智能化选课排课管理信息系统进行了详细的可行性研究,基本上可以解决上述存在的问题。通过这样的系统,可以做到信息的规范管理、科学的统计和快速的查询,从而减少管理方面的工作量,提高学校管理者的工作效率。

1.2 智能化选课排课系统在教务综合管理中的主要内容

智能化选课排课系统主要内容包括:(1)主修课程信息注册;(2)选修、辅修课程的注册;(3)教室资源信息注册;(4)教师资源信息注册;(5)班级信息注册;(6)学年信息注册;(7)选课排课功能的实现;(8)智能化调整;(9)结果输出、校验等九个部分的内容。

为实现智能化选课排课系统,必须调动教师、学生、教室管理者的积极性,加强业务培训,并结合学校的实际情况,制定选课排课系统实施细则,从而保证该系统的准确运行。

2 总体设计

2.1 系统功能设计

智能化选课排课系统的总体任务是:实现智能化选课排课系统管理信息的系统化、规范化、自动化、科学化、智能化。系统开发设计的思想是:尽量采用现有的软硬件环境及先进的管理系统开发方案,提高系统开发水平和应用效果;符合学校管理的规定和实际情况,满足对学生、教师、教室等的需要,并达到操作过程的直观、方便、实用、安全等要求;采用模块化程序设计方法,便于系统功能的各种组合和修改;具备数据库维护功能,及时根据学校管理者需求进行数据的添加、删除、修改、备份等操作。

系统功能设计是在系统开发的总体任务和系统开发设计思想的基础上完成的,本系统的主要任务是用于收集学生、教师、教室、课程等资源的基本信息,以便集中进行管理。因此,该系统的功能主要有:(1)学生基本信息管理,包括:学生信息的输入、查询和修改等;(2)学生班级信息管理,包括班级信息的输入、查询和修改等;(3)课程信息管理,课程信息的输入、查询和修改等;(4)教师信息的管理,包括教师信息的录入、查询和维护等;(5)教室信息的管理,包括教室信息的录入、查询和维护等;(6)智能化选课排课的管理,包括选课、选课、优先级处理等;(7)系统维护:包括数据查询、修改(调整)和统计、输出、备份等。

另外,还应该考虑到系统的安全性、稳定性,该系统应在登录窗口对使用者进行身份的识别,加入权限的控制。如使用者是管理员,则拥有修改、插入、追加、删除、保存数据的权利,并可对其他使用本系统的人员进行管理。如使用者是数据管理员,则不能够对其他使用本系统的人员进行管理,而普通用户则只能进行查询、统计等简单功能。

根据系统功能要求,可以将系统按照功能模块进行分解,设计了如图1所示的系统功能模块图。

2.2 数据库的设计

数据库结构设计的好坏将直接对应用系统的效率以及实现的效果产生影响,最佳的数据库结构会减少数据库的存储量,而且还能使数据的完整性和一致性比较高,系统具有较快的响应速度,简化基于此数据库应用程序的实现等。在数据库系统开始设计时应尽量考虑全面,尤其应仔细考虑用户的各种需求,避免浪费不必要的人力和物力。

2.2.1 数据库需求分析

数据库需求分析是数据库结构设计的第一个阶段,这个阶段主要的任务是收集基本数据、数据结构以及数据处理的流程,组成一份详尽的数据字典,为以后进一步设计打下基础。在仔细分析和调查选课排课管理工作过程的基础上,得到本系统所处理的数据流程如图2所示。

在本步骤中,规范化的构建课程库信息表是最关键的,因为不管是学生、教师,都是以课程为出发点,学生以选某课程为中心,教师以上某课程为落脚点,课程的合理构建,将为年级教学计划、学期开课计划打下良好的基础,鉴于此,须将课程进行以下处理:

(1)拆分课程:拆分对所有学生必修的公共课程,如大学英语、体育、高等数学等,课程代码可相同。(2)定义课程:若课程的教学大纲、课程名称、学分与总学时等属性相同时(不区分文理科),可归纳为同一课程,系统只需要采集一次。(3)控制课程的修改与删除权限:课程环节是本管理软件基础数据的核心之一,与学生的成绩、选课与排课等密切关联,比如删除或修改课程信息,若系统未关联到位,将直接导致历史的成绩、选课等相关数据丢失,因此必须控制。(4)冗余课程数据处理:随着使用时间的增长,有很多历史的课程对现在的在校学生来说,已经不再开设。若直接删除,将直接导致历史数据的全部丢失。我们独特的设计原则是:尊重历史,满足现状,适应发展。对于这些多余的课程,只需要改变该课程的使用状态即可(设置为不可用),系统将自动对这些课程进行屏蔽,但是并不从系统中进行删除。这样不管回溯到哪个时间,都能够准确的查询到历史的状态。

2.2.2 数据库表结构

针对本系统,并通过对选课排课工作管理的内容和数据流程分析,该系统数据项和数据结构如图3。

将数据库的概念结构转化为数据库系统所支持的实际数据类型,就是数据库的逻辑结构。通过规划,需要设计6个数据表来保存选课排课系统需要的基础信息:学生个人基本信息表、班级信息表、课程基本信息表、年级课程设置信息表、教师信息表、教室资源信息表、系统用户表。1个选课排课结果记录表以及其它中间数据表等。

3 选课排课管理系统的实现

3.1 数据库的实现

在需求分析、结构设计的基础上,得到数据库的逻辑结构后,就可以在具体的数据库系统中实现该逻辑结构。

目前主流的数据库系统有很多,如ORACLE,SYBASE,SQL Server,INFORMIX,DB2等,各有千秋,根据“选课排课管理系统”对数据量的要求,本系统采用了SQL Server 2000数据库管理系统。

在需求分析、概念结构设计的基础上得到数据库的逻辑结构后,就可以在SQL Server 2000数据库系统中实现该逻辑结构。下面是利用SQL Server 2000数据库系统软件中的“企业管理器”工具实现student_Info表格创建的SQL语句,其它表格的创建方法与此相同:

其它数据信息表的创建与学生基本信息表的创建方式相同,在此不再赘述。

3.2 各应用模块和功能模块的设计

系统的编码实现用到了JAVA中的JSP和Servlet技术。使用该项技术开发出的本系统具有界面直观、操作简单、开发维护简便等特点。

在编程中,为了充分利用学校的教学资源,按照教学大纲、教学任务,对教学时间(课时)、实践时间(课时)进行了相应的数据处理,使以前某一课程独占某一教学资源(教室)的情况大为改观,即某课程在某一时间段内有实践环节时,不使用的教室可继续上其它课程,是资源合理充分的得到利用。

为保证学生的自主选课,系统采用多口径、多层次选课的办法,如可根据教师、专业、学年学期、开课课程等进行自主选课,系统根据教室资源的情况和教学大纲或教学方案以及设定的优先级等进行智能化排课,保证资源利用的最大化和教师任课即课时任务的公平化,既保证教授们的授课课时,也促进了青年教师工作量的合理分配,为学校的可持续化发展和青年教师的培养、锻炼等提供了有力保障。

4 结束语

本系统使用JAVA、SQL sever语言等技术完成了基于web的选课排课管理信息系统,不但使系统保持了强大的数据库操作特性,而且使系统容易在web上发布,做到了信息的规范管理、科学的统计和快速的查询,较好的满足了学校管理者对学生学籍管理的需求,提高了学校管理者的工作效率。

摘要：智能化选课排课系统是学校教务综合管理信息系统的一项重要功能,为适应教育改革和素质教育的要求,学生自主选课和学校的日常标准化选课的信息量成倍增长,排课的工作量、复杂程度将随之增大,传统的手工管理模式无法满足管理者的需求。本文利用SQL Server数据库系统强大的数据管理特性和JAVA开发技术设计了一个基于WEB的智能化选课排课系统,较好的满足了学校管理者对选课排课管理的需求,提高了教学管理的效率。

基于智能规划与矩阵运算的智能排课系统设计 篇3

关键词：旅游行程规划,ACO算法,百度地图,Android平台

0 引言

合理的行程规划对自助游客拥有轻松愉快的旅游体验是必要的。进行行程规划的一般过程包括在各种旅游网站上搜集大量的旅游信息,然后决定去游玩哪些景点、景点游玩顺序、游玩时间和景点之间转移的交通路线等,通常需要花费大量的时间和精力,最终得到的结果却往往不尽如人意。因此,开发一种能够帮助自助游客规划合理行程路线的工具显得非常重要。

互联网和新一代通信技术的出现和迅速发展为在线动态规划行程提供了可能,同时也促进很多学者对如何规划合理的行程路线进行了大量研究,大致可分为两类。一类是从数学理论角度进行分析,旅游行程规划属于NP难题,其解决方法有原始的精确求解法和新兴的启发式算法、智能优化算法等。如文献[1]提出采用遗传算法求解最短路问题,文献[2]在此基础上,对大城市内具有时间约束的行程规划问题进行了分析,提出基于嵌套结构的行程规划方法,主程序和子程序中都采用遗传算法去寻找优化路线,最后根据游客需求和选择的旅游景点自动生成一条相关的旅游行程路线;文献[3,4]在蚁群算法基础上分别结合2-opt算法和模拟退火算法优化旅游路线,从而为该问题的研究积累了十分丰富的经验。

另一类研究从应用分析角度进行,这类研究着重于在优化算法的支撑下,实现一个旅游行程规划系统,如文献[5]利用数学模型和交互式多目标技术设计了个人旅游路线规划系统,可以生成一条基于用户选择的行程路线;文献[6]实现了一个基于网络和手机端的个性化旅游路线推送系统,系统可根据用户一天可以游玩的景点数量、景点游玩时间和开放时间等参数,采用改进的启发式搜索方法推荐出一条近似优化的行程路线;文献[7]从团队定向问题角度对行程规划进行分析,把搜索优化解的过程分成两个阶段,预处理阶段采用MapReduce框架探索出多个一日游路线,下一阶段从中选择优秀的行程路线进行组合排序,推荐给自助游客;文献[8]开发了一个为游客提供城市旅行规划的系统。然而,这些研究大部分是通过理论实验进行的,并没有基于真实的数据进行实验。在实际情况中,通常包括大量的景点和复杂的交通网络,潜在解空间的搜索范围广而且复杂。

本文通过对旅游行程规划和蚁群优化算法的研究,设计了城市区域内能满足自助游客多方面需求、可以进行多景点路线规划的Android智能终端旅游行程规划系统。系统采用三层体系架构,集成了行程规划模型、蚁群优化算法、Web Service、JSON、Android平台开发和百度地图API等理论与技术。相对于传统的旅游服务内容,该系统旨在为游客提供智能行程规划服务,属于智慧旅游[9]建设的智慧服务体系中不可缺少的一部分,能够更好满足游客个性化的旅游需求。

1 行程规划系统设计

1.1 系统体系架构设计

行程规划系统基于一云多屏的智慧旅游公共服务平台理念,采用结构清晰、明确的三层架构体系,如图1所示。该架构可以降低系统各层之间的依懒,减轻系统后期的维护成本和维护时间,整体具有较强的扩展性、易用性和开放性。其中,表现层包括少部分的逻辑代码,主要负责与用户进行交互,接受用户的请求及数据返回;业务逻辑层属于系统架构的核心,是连接用户端和数据库的桥梁,主要负责按照业务逻辑对数据库进行操作,并将数据结果传给表现层;数据库层主要负责解决大数据存储、数据高并发访问、数据分类、加工、封装和数据服务问题。

图1 系统架构图

系统应用服务器采用Tomcat部署Web Service服务,提供行程规划和用户信息管理等服务。应用逻辑被封装到了应用服务器中,当应用逻辑发生变化时,仅需修改服务器中的程序,用户端的应用程序不必更新。用户端与数据库服务器通过应用服务器进行连接,降低系统资源的开销,进而提高系统的可靠性和安全性。

系统数据库采用My SQL构建,存储从云端获取的兴趣点基础数据信息、兴趣点间的交通数据和用户数据信息,并提供数据备份和安全管理等功能。

该系统面向游客提供包括电脑、Android/i OS智能手机、PAD等多种形式的服务终端。用户端通过访问开放的应用程序接口,从兴趣点数据库获取景点信息展示给用户,并从云端或交通信息数据库搜集用户偏好的景点交通信息,采用蚁群优化算法智能生成旅游行程路线,最后在百度地图上将规划结果直观、友好地展示给用户,极大地提升了用户体验。

1.2 数据库设计

根据系统架构分析,建立了“TRPData”数据库,主要包括景点信息、交通信息、用户信息和城市信息等多个实体。下面仅对景点信息和交通信息中主要的表进行说明。景点信息表用于存储景点的基本属性信息,字段包括身份id、景点名称name、地址address、电话tel、星级star、门票价格price、开放时间timeframe、经度lonx、纬度laty和最佳游玩时间playtime。交通信息表用于存储景点之间的交通信息,字段包括起点from、目的点to、旅途时间traveltime和旅途费用travelcost。

2 行程规划功能详细设计和算法实现

2.1 系统体系架构设计

业务逻辑层承载着系统主要功能模块的实现,行程规划模块作为系统的核心功能,主要向用户提供行程规划服务,其详细设计也是针对业务逻辑层展开。如图2所示是行程规划模块的数据流图,系统根据用户输入的基本信息和从交互平台搜集的用户偏好信息,采用行程规划算法进行行程规划,最后将规划结果展示给用户。

图2 行程规划数据流图

2.2 行程规划模型分析

旅游行程规划是指根据游客的旅游需求和个人偏好,搜索旅游综合信息数据库中满足条件的相关信息要素,并对偏好景点进行规划排序,生成一条合理的行程路线。

为了使用计算机或移动终端进行旅游行程规划,有必要把行程规划所涉及到的元素及元素之间的关系转化成完全图G={S,E}进行分析,其中S={si|i=1,2,…,n}代表游客偏好的景点集合,E={eij|i,j∈S}代表两个景点间的旅游交通路线构成的边集合。对于任意顶点si,t(i)表示在景点i的游玩时间,c(i)表示对应的游览费用;对于任意边eij,t(eij)表示从景点i到景点j的旅途时间,c(eij)表示对应的旅途费用c(eij)。

用R={s1,s2,…,sn-1,sn}表示一条满足要求的行程路线,行程所需的旅游花费C和旅游时间T分别如式(1)、式(2)所示:

其中d(i)表示提前到达目的地景点时产生的等待时间,如式(3)所示:

其中tp(i)为景点关闭时间。

以旅游时间最小化和旅游花费最小化的联合来评价可选行程路线R的优劣,目标函数Φ(R)的表达式如下:

其中ω0是衡量旅游时间与旅游费用之间关系的一个权重系数。Tmax代表游客可支配的旅游时间,Cmax代表根据游客需求所得的费用预算。式(5)是对旅游时间的约束;式(6)是对旅游花费的约束;式(7)是对每个景点游玩时间的约束,以确保为游客提供的行程安排落在景点开放时间的范围之内。

2.3 行程规划算法设计

根据上述分析可知,行程规划实质上是一类含有多个约束条件的组合优化问题,高效、科学、强壮的算法是解决问题的关键[10]。为生成合理的行程路线,本系统采用ACO算法进行路线寻优。

ACO算法是一种基于蚂蚁群体觅食行为的启发式优化算法[11,12],通过模拟蚂蚁群体使用信息素轨迹进行交流判断,成功找到较短觅食路线的过程,对问题可能的解空间进行搜索优化。算法实现的过程主要包括:蚂蚁群体构建问题解和路径上的信息素更新两个步骤。首先,蚂蚁个体会根据路径上的信息素浓度和启发式信息,并结合相应的状态转移规则,判断每一步的转移方向。然后算法根据问题的目标函数对每个蚂蚁形成的路线进行评价,更新路径信息素。经过反复迭代搜索,算法最终收敛于最优的蚂蚁个体,也就找到了问题的优化解。

使用蚂蚁个体模拟游客进行旅游行程路线选择的过程中,把游客通常关心的旅游时间、景点开放时间、费用预算等需求参数设计到算法模型中去,对ACO算法进行改进。

(1)行程路线的构建

假设蚂蚁k(k=1,2,…,m)在当前节点i选择下一个游览景点j,所有可选的景点存放在集合Rk中。改进的算法模型中,蚂蚁个体不仅感知路径上的信息素强度τ(i,j)和路径启发式信息η(i,j),而且还会判断景点j开放时间段的约束ω(u)对其吸引度,ω(u)的表达式为如式(8)所示:

其中,C是一个常数。

蚂蚁个体计算可选景点的选择概率时采用改进的状态转移规则,如式(9)所示:

其中,参数α、β、ν分别表示信息素浓度、启发式信息和开放时间约束的相对重要性。显然,在相同条件下,景点开放时间较短的景点将会被优先选择进行游览。

同时,为了兼顾游客的多重需求,将路径启发式信息η(i,j)从时间和费用两个方面重新设计,改进后的启发式信息计算模型如式(10)、式(11)所示:

式中参数γ1、γ2分别表示时间和花费的重要程度,管理员可以根据游客的需求对其取值进行调节。显然,由于各景点的最佳游览时间和旅游费用不同,路径(i,j)和(j,i)上启发式信息也相应不同。蚂蚁群体在构建行程路线时交替使用两种启发式信息,旨在寻找到一条满足时间和费用联合最小化的行程线路。

目标节点j的确定方式采用伪随机比例规则,首先根据式(9)求得各景点的选择概率,然后产生一个[0,1]内均匀分布的随机变量q,与控制参数q0(q0∈[0,1])进行比较。如果q≤q0,下一个目标景点j采用确定性方式进行选择,由式(12)确定;如果q>q0,根据已有的选择概率,采用轮盘赌的选择方法确定下一个目的景点j。

(2)路径信息素的更新

蚂蚁群体构建完成各自的行程路线后,进行路径信息素的更新,用ρ(0<ρ≤1)表示路径信息素衰减度,具体更新规则为:

式中Δτ(i,j)表示蚂蚁个体构建的行程路线R上信息素增量,计算公式为:

式中Φ(R)为上一节行程规划模型分析得出的评价路线R的目标函数。

根据行程规划算法设计,算法实现的流程如图3所示。

图3 行程规划算法流程图

3 智能终端行程规划软件实现

Android操作系统[13]是一个开放的平台,近年来得到了快速发展,在市场份额中占有很大比重。因此,本文以Android开发平台为例,实现杭州市内旅游行程规划系统的用户端,设计出一款界面布局合理、简洁大方、功能完整、符合用户体验的软件,方便用户随时随地规划行程。软件的结构如图4所示,主要包括需求交互功能和地图展示功能两个模块。

图4 客户端软件结构

3.1 需求交互功能模块实现

需求交互功能包括输入基本需求、景点信息展示两个界面,主要由界面组件Activity、列表组件List View和通信组件Intent及相关技术开发实现。界面展示信息通过Android客户端软件访问远程景点数据库获取。由于平台本身没有提供直接调用Web Service服务的库,开发时采用第三方的类库Ksoap2实现调用Web Servie服务,服务器以JSON对象形式返回数据结果给客户端。JSON对象具有数据量小、可读性强等特点,客户端解析时也不必用额外的类进行处理。

此外,服务器端处理数据时通过在内存中分页来提高运行效率,将结果快速展示到用户界面,并采用缓存技术来提高用户的使用体验。

基本需求确定界面运行效果如图5所示,用户输入基本需求后,点击“选择景点”按钮,提交需求信息,系统跳转至景点信息展示交互界面,运行效果如图6所示,界面上的“选择”和“已选”按钮用来记录用户的偏好选择。点击界面右上角的“查看线路”按钮,客户端向系统服务端发送行程规划的请求,服务器根据请求内容,从系统数据库搜集行程规划所需的偏好景点游玩时间、开放时间、经纬度位置、景点间旅途时间和旅途费用等信息,并调用行程规划算法模块进行路线规划,在地图上显示返回的行程路线结果。

图5 输入基本需求

3.2 地图展示功能模块实现

地图展示功能模块主要用于展示行程规划结果和提供景点间交通线路搜索功能。该模块的实现需要调用百度地图Android SDK,它是一套开放给开发者的应用程序接口,用于Android系统移动设备的地图应用开发,可提供基础地图、地图覆盖物、POI检索、线路规划等功能。地图控件的引入及所有相关操作均在Ditu Activity类中实现。

其中,为景点添加图形覆盖物是显示行程路线详情的重点,首先根据用户与系统的交互结果获取行程规划的路线信息,然后依次对各个景点添加自定义的覆盖物图标,最后根据添加顺序在地图上实现多点划线。重写自定义图标的点击事件onMarker Click,当用户点击时,可以获取对应景点的信息,运行效果如图7所示。

景点间线路搜索功能采用地图搜索模块Route Plan Search开发实现,将线路搜索的城市区域设置为杭州市,并分别提供了公交、驾车和步行线路搜索功能,运行效果如图8所示。

图7 行程规划结果

图8 公交路线信息

在该功能模块实现时,根据需求对百度地图功能做了以下改进:

(1)行程路线绘制:由于百度地图SDK提供的多边形覆盖物是一个封闭的几何图形,在使用多边形覆盖物选项类Polygon Options绘制行程线路时,改进该类方法对多边形闭合边框的设置,按照行程规划结果,将起点到终点的景点线路绘制出来。

(2)更改地图中心位置:由于百度地图在移动设备屏幕中心显示的默认位置是北京市,而本文是以杭州市的行程规划为例。为了调用地图模块时可以直观地看到杭州市内的行程路线结果,首先获取行程规划结果起点的经纬度坐标值,然后使用Map Status Update将地图中心状态位置设置为行程路线起点。

4 结语

目前市场上的一些旅游网站可以提供基本行程规划功能,但类似于本系统综合考虑游客出游时间、费用和景点开放时间等多种需求的行程规划模型还不多见。另外,本系统采用蚁群智能优化算法规划行程路线,可以承受问题规模不断扩大带来的计算压力,这也是其他优化算法不具备的优势。