多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的自學習等情況，仍需要進一步的繼續研究。