多Agent通信协商技术在高职院校排课系统的应用研究

杜冬霞

（山西通用航空职业技术学院，山西 大同 037300）

0 引言

排课是高职院校教学管理中重要且复杂的工作之一，目标就是为学校开设的课程分配合适的教学资源，使整个教学过程能够有序的按计划开展。由于高职院校排课工作涉及较多资源且高职院校存在学生合班上课、实训课程较多需考虑实训资源等情况，如何解决资源冲突、合理分配资源进行排课是非常复杂的。高职院校排课目前常用的人工排课方法存在工作量大、效率低等问题，在用的计算机排课软件有效性较低且未能考虑教师对课表的满意度问题。

随着分布式人工智能技术的发展，Agent理论技术的研究也成为一个热点，由异构、动态、分布、自治的Agent构成的系统，称为多Agent系统（Multi-Agent System， MAS），各个Agent之间的协商可以消除规划中的目标冲突，解决资源分配中约束限制。因此，本文尝试将多Agent通信协商技术应用于排课系统的设计。

1 排课问题

一些作者对排课问题进行了不同算法应用的尝试，如黄阿新提出了基于蚁群算法的高校排课系统设计[1]，林敏军将改进的免疫遗传算法应用到了排课系统的设计中[2]，陈未央等人重点分析与探讨了研究生排课系统的因素[3]，侯若楠等人将蚁群算法与目前大部分高校现行的学分制进行结合进行了应用研究[4]，还有其他学者从各个方向对排课问题进行研究。

原始的排课问题是涉及班级、课程、时间段、教师和教室五个因素的五维决策优化问题，同时存在教师约束（如个别教师某时间段不可以上课）、课程约束（如体育课秋季学期下午需排在5/6节，春季学期需排在7/8节）、班级约束（如高职院校需根据班级确定理论和上课的时间分配）、校级约束（如学院周三下午进行集体学习，不进行课程安排）、教室/实训室容纳人数约束等多个约束条件，目标是解决班级、课程、时间、教师和教室五个因素之间的冲突，是典型的动态规划问题。

本应用研究首先将排课问题进行优化，优化后的排课问题，以班级为核心，将课程、任课教师与班级绑定，合为“班课师”一个因素，将五维决策优化问题优化为班课师、时间段和教室的三个因素的三维决策优化问题，将院校级约束等统一约束条件在排课资源中提前去除，尽量将资源范围精确，目标是在解决班课师、时间和教室的三个因素之间的冲突并能提升教师、学生满意度。优化后的排课问题涉及的因素归纳如下：

（1）教室（classroom）：每个教室都有自己的编号或名称及容量，每个教室同一时间段只能有一个“班课师”。

（2）时间段（time）：也就是节次，高职院校的上课时间可以由学年分解为2个学期，每学期分解为N周，周课表也可分为单周课表与双周课表。每周有D天（根据学院统一排课安排，D≤6），每天也可分为5个节次Pi（高职院校一般为2课时连续授课，i为Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ，其中Ⅰ为1/2节课，Ⅱ为3/4节课，Ⅲ为5/6节课，Ⅳ为7/8节课，Ⅴ为9/10节课）。

（3）班课师（Class-Course-Teacher， CCT）：每个班级有自己的名称，且同一时间段只能上一门课程；也可能多个班级合班（Multi-class）同一时间段上同一门课程；班级上的课程是固定的，教师任教的课程是固定的，所以可绑定为一个因素。

优化后的排课约束条件归纳如下：

（1）教师约束（Teacher Constraints， TC）：如个别教师一周中某天、某时间段不可以上课；

（2）课程约束（Course Constraints， CC）：如体育课秋季学期下午需排在5/6节，春季学期需排在7/8节；

（3）班级约束（Class Constraints， CC）：如高职院校需根据班级的课程安排确定理论和上课的时间分配；

（4）校级约束（Department Constraints， DC）：如学院周三下午进行集体学习，不进行课程安排，校级约束提前剔除不放进资源库中；

（5）其他资源约束（Other Constraints）：教室/实训室可用设备数量等多个约束条件。

2 多Agent通信协商技术

随着分布式人工智能技术的发展，Agent技术得到了广泛的应用，什么是Agent？目前在人工智能研究领域最广为接受的是1995年Wooldridge和Jennings提出的定义[5]，翻译为：Agent是处在某个环境中的计算机系统，该系统有能力在这个环境中自主行动以实现其设计目标。在Wooldridge和Jennings的定义中，Agent具有如下基本特性：

（1）自治性（Autonomy）：Agent能根据外界环境的变化，接受外界的刺激而自动地对自己的行为进行调整，具有自我管理和调节的能力。

（2）反应性（Reactive）：具有能对外界的刺激作出反应的能力。

（3）主动性（Proactive）：对于外界环境的改变，Agent能主动采取活动的能力。

（4）社会性（Social）：Agent之间具有合作的能力，不同的Agent可根据各自的意图与其他Agent进行交互，以达到解决问题的目的。

多Agent系统是由异构、分布、动态、大规模及自治Agent构成的系统，其中每个Agent是一个物理或抽象的实体，可作用于自身并与其他的Agent通信。通信为Agent间的交互打下基础，协商是MAS实现协作、解决冲突的关键。所以，多Agent通信协商技术可以让各Agent之间协作完成目标任务。

3 多Agent通信协商技术在排课系统中的应用

在MAS中，Agent之间因竞争行为出现资源冲突、目标冲突等情况时，Agent之间可以通过通信协商进行交互，将其部分或全部任务委托其他Agent来完成，通信协商技术的应用是保障Agent之间有序进行交互的关键。

结合高职院校排课工作的特点，本研究建立班课师、教室、时间及排课四个Agent，各自的任务主要如下：

（1）班课师Agent（CCTA）：确认班级课程安排及教师排课期望，将确认信息传递至排课Agent。

（2）教室Agent（CR Agent）：确认教室容量信息传递至排课Agent并与其进行通信协商。

（3）时间段Agent（T Agent）：确认排课时间信息，传递至排课Agent并进行通信协商。

（4）排课Agent（SA）：代表教务处进行排课，尽可能的产生满足班课师的需求，进行资源分配协商；生成排课结果。

四个Agent独自及之间通信协商完成的工作机制如下：

流程1：管理员启动“班课师”Agent（CCTA），输入班级对应的课程及班级与课程对应的教师，并输入教师的意向上课时间及约束上课时间。

流程2：CCTA将信息传递给排课Agent（SA）；SA判断CCTA传递的信息。

流程3：SA传输教室信息至教室Agent（CRA），CRA分配教室，传递至SA。

流程4：SA传输教师期望上课信息至时间Agent（TA），TA分配教室，传递至SA。

如果SA在排课的过程中发现与教室、时间信息有冲突，按照时间优先的方式与CRA通信进行协商，向CRA传输新的信息。

重复流程1-4，直至所有课程排完，SA将排课传递至CCTA，完成排课。排课流程如图1所示。

图1 排课流程

4 排课系统建模仿真

AnyLogic是惟一一款支持多Agent仿真的商业软件，它支持基于智能体（Agent）的建模，目前已进入市场多年，在物流、制造、市场、医疗、交通、军事、应急等诸多领域已有成熟的应用且软件功能日益完善。

软件基于Java开发，具有强大的二次开发功能，支持实验、库资源等的自定义开发与封装。支持基于智能体、离散事件、系统动力学、Petri网、行人和交通仿真，可以根据需要任意组合。可视化的开发环境，支持模块拖拽操作及脚本编辑，简单灵活丰富的外部数据接口，可直接读取数据库、GIS地图库、文本、图片等文件。具备仿真和优化功能。专业辅助开发功能，支持自动代码补全、语法高亮等。专业模型调试功能，实时监测事件，进行代码级别跟踪调试。丰富的实验框架，具有人工智能、优化、蒙特卡洛、敏感性分析、校准比较等实验。丰富的库资源，根据流程、交通、流体等常规领域建有丰富的模型资源库。

AnyLogic软件的智能体建模以个体为中心的建模、确定智能体（人、建筑物、产品等），定义其行为（驱动力、状态、行为等），将其放到一个中心环境中，或可建立连接。则系统层（整体）行为就展现为很多个体行为交互的结果。鉴于AnyLogic软件的特性，本研究使用基于主体的建模来模拟排课任务执行，伪代码段如下：

5 结束语

分布式人工智能的多Agent系统是一个重要的研究领域，其中Agent之间的通信协商技术成为目前研究的热点，并已应用于动态规划及冲突解决多个场景。文章研究了将多Agent的通信协商技术应用于排课系统的设计，但是研究仍不够深入，没有研究系统的真正实现、投入使用及Agent的自学习等情况，仍需要进一步的继续研究。