多Agent通信協(xié)商技術(shù)在高職院校排課系統(tǒng)的應(yīng)用研究

杜冬霞

（山西通用航空職業(yè)技術(shù)學(xué)院，山西 大同 037300）

0 引言

排課是高職院校教學(xué)管理中重要且復(fù)雜的工作之一，目標(biāo)就是為學(xué)校開(kāi)設(shè)的課程分配合適的教學(xué)資源，使整個(gè)教學(xué)過(guò)程能夠有序的按計(jì)劃開(kāi)展。由于高職院校排課工作涉及較多資源且高職院校存在學(xué)生合班上課、實(shí)訓(xùn)課程較多需考慮實(shí)訓(xùn)資源等情況，如何解決資源沖突、合理分配資源進(jìn)行排課是非常復(fù)雜的。高職院校排課目前常用的人工排課方法存在工作量大、效率低等問(wèn)題，在用的計(jì)算機(jī)排課軟件有效性較低且未能考慮教師對(duì)課表的滿意度問(wèn)題。

隨著分布式人工智能技術(shù)的發(fā)展，Agent理論技術(shù)的研究也成為一個(gè)熱點(diǎn)，由異構(gòu)、動(dòng)態(tài)、分布、自治的Agent構(gòu)成的系統(tǒng)，稱(chēng)為多Agent系統(tǒng)（Multi-Agent System， MAS），各個(gè)Agent之間的協(xié)商可以消除規(guī)劃中的目標(biāo)沖突，解決資源分配中約束限制。因此，本文嘗試將多Agent通信協(xié)商技術(shù)應(yīng)用于排課系統(tǒng)的設(shè)計(jì)。

1 排課問(wèn)題

一些作者對(duì)排課問(wèn)題進(jìn)行了不同算法應(yīng)用的嘗試，如黃阿新提出了基于蟻群算法的高校排課系統(tǒng)設(shè)計(jì)[1]，林敏軍將改進(jìn)的免疫遺傳算法應(yīng)用到了排課系統(tǒng)的設(shè)計(jì)中[2]，陳未央等人重點(diǎn)分析與探討了研究生排課系統(tǒng)的因素[3]，侯若楠等人將蟻群算法與目前大部分高?，F(xiàn)行的學(xué)分制進(jìn)行結(jié)合進(jìn)行了應(yīng)用研究[4]，還有其他學(xué)者從各個(gè)方向?qū)ε耪n問(wèn)題進(jìn)行研究。

原始的排課問(wèn)題是涉及班級(jí)、課程、時(shí)間段、教師和教室五個(gè)因素的五維決策優(yōu)化問(wèn)題，同時(shí)存在教師約束（如個(gè)別教師某時(shí)間段不可以上課）、課程約束（如體育課秋季學(xué)期下午需排在5/6節(jié)，春季學(xué)期需排在7/8節(jié)）、班級(jí)約束（如高職院校需根據(jù)班級(jí)確定理論和上課的時(shí)間分配）、校級(jí)約束（如學(xué)院周三下午進(jìn)行集體學(xué)習(xí)，不進(jìn)行課程安排）、教室/實(shí)訓(xùn)室容納人數(shù)約束等多個(gè)約束條件，目標(biāo)是解決班級(jí)、課程、時(shí)間、教師和教室五個(gè)因素之間的沖突，是典型的動(dòng)態(tài)規(guī)劃問(wèn)題。

本應(yīng)用研究首先將排課問(wèn)題進(jìn)行優(yōu)化，優(yōu)化后的排課問(wèn)題，以班級(jí)為核心，將課程、任課教師與班級(jí)綁定，合為“班課師”一個(gè)因素，將五維決策優(yōu)化問(wèn)題優(yōu)化為班課師、時(shí)間段和教室的三個(gè)因素的三維決策優(yōu)化問(wèn)題，將院校級(jí)約束等統(tǒng)一約束條件在排課資源中提前去除，盡量將資源范圍精確，目標(biāo)是在解決班課師、時(shí)間和教室的三個(gè)因素之間的沖突并能提升教師、學(xué)生滿意度。優(yōu)化后的排課問(wèn)題涉及的因素歸納如下：

（1）教室（classroom）：每個(gè)教室都有自己的編號(hào)或名稱(chēng)及容量，每個(gè)教室同一時(shí)間段只能有一個(gè)“班課師”。

（2）時(shí)間段（time）：也就是節(jié)次，高職院校的上課時(shí)間可以由學(xué)年分解為2個(gè)學(xué)期，每學(xué)期分解為N周，周課表也可分為單周課表與雙周課表。每周有D天（根據(jù)學(xué)院統(tǒng)一排課安排，D≤6），每天也可分為5個(gè)節(jié)次Pi（高職院校一般為2課時(shí)連續(xù)授課，i為Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ，其中Ⅰ為1/2節(jié)課，Ⅱ?yàn)?/4節(jié)課，Ⅲ為5/6節(jié)課，Ⅳ為7/8節(jié)課，Ⅴ為9/10節(jié)課）。

（3）班課師（Class-Course-Teacher， CCT）：每個(gè)班級(jí)有自己的名稱(chēng)，且同一時(shí)間段只能上一門(mén)課程；也可能多個(gè)班級(jí)合班（Multi-class）同一時(shí)間段上同一門(mén)課程；班級(jí)上的課程是固定的，教師任教的課程是固定的，所以可綁定為一個(gè)因素。

優(yōu)化后的排課約束條件歸納如下：

（1）教師約束（Teacher Constraints， TC）：如個(gè)別教師一周中某天、某時(shí)間段不可以上課；

（2）課程約束（Course Constraints， CC）：如體育課秋季學(xué)期下午需排在5/6節(jié)，春季學(xué)期需排在7/8節(jié)；

（3）班級(jí)約束（Class Constraints， CC）：如高職院校需根據(jù)班級(jí)的課程安排確定理論和上課的時(shí)間分配；

（4）校級(jí)約束（Department Constraints， DC）：如學(xué)院周三下午進(jìn)行集體學(xué)習(xí)，不進(jìn)行課程安排，校級(jí)約束提前剔除不放進(jìn)資源庫(kù)中；

（5）其他資源約束（Other Constraints）：教室/實(shí)訓(xùn)室可用設(shè)備數(shù)量等多個(gè)約束條件。

2 多Agent通信協(xié)商技術(shù)

隨著分布式人工智能技術(shù)的發(fā)展，Agent技術(shù)得到了廣泛的應(yīng)用，什么是Agent？目前在人工智能研究領(lǐng)域最廣為接受的是1995年Wooldridge和Jennings提出的定義[5]，翻譯為：Agent是處在某個(gè)環(huán)境中的計(jì)算機(jī)系統(tǒng)，該系統(tǒng)有能力在這個(gè)環(huán)境中自主行動(dòng)以實(shí)現(xiàn)其設(shè)計(jì)目標(biāo)。在Wooldridge和Jennings的定義中，Agent具有如下基本特性：

（1）自治性（Autonomy）：Agent能根據(jù)外界環(huán)境的變化，接受外界的刺激而自動(dòng)地對(duì)自己的行為進(jìn)行調(diào)整，具有自我管理和調(diào)節(jié)的能力。

（2）反應(yīng)性（Reactive）：具有能對(duì)外界的刺激作出反應(yīng)的能力。

（3）主動(dòng)性（Proactive）：對(duì)于外界環(huán)境的改變，Agent能主動(dòng)采取活動(dòng)的能力。

（4）社會(huì)性（Social）：Agent之間具有合作的能力，不同的Agent可根據(jù)各自的意圖與其他Agent進(jìn)行交互，以達(dá)到解決問(wèn)題的目的。

多Agent系統(tǒng)是由異構(gòu)、分布、動(dòng)態(tài)、大規(guī)模及自治Agent構(gòu)成的系統(tǒng)，其中每個(gè)Agent是一個(gè)物理或抽象的實(shí)體，可作用于自身并與其他的Agent通信。通信為Agent間的交互打下基礎(chǔ)，協(xié)商是MAS實(shí)現(xiàn)協(xié)作、解決沖突的關(guān)鍵。所以，多Agent通信協(xié)商技術(shù)可以讓各Agent之間協(xié)作完成目標(biāo)任務(wù)。

3 多Agent通信協(xié)商技術(shù)在排課系統(tǒng)中的應(yīng)用

在MAS中，Agent之間因競(jìng)爭(zhēng)行為出現(xiàn)資源沖突、目標(biāo)沖突等情況時(shí)，Agent之間可以通過(guò)通信協(xié)商進(jìn)行交互，將其部分或全部任務(wù)委托其他Agent來(lái)完成，通信協(xié)商技術(shù)的應(yīng)用是保障Agent之間有序進(jìn)行交互的關(guān)鍵。

結(jié)合高職院校排課工作的特點(diǎn)，本研究建立班課師、教室、時(shí)間及排課四個(gè)Agent，各自的任務(wù)主要如下：

（1）班課師Agent（CCTA）：確認(rèn)班級(jí)課程安排及教師排課期望，將確認(rèn)信息傳遞至排課Agent。

（2）教室Agent（CR Agent）：確認(rèn)教室容量信息傳遞至排課Agent并與其進(jìn)行通信協(xié)商。

（3）時(shí)間段Agent（T Agent）：確認(rèn)排課時(shí)間信息，傳遞至排課Agent并進(jìn)行通信協(xié)商。

（4）排課Agent（SA）：代表教務(wù)處進(jìn)行排課，盡可能的產(chǎn)生滿足班課師的需求，進(jìn)行資源分配協(xié)商；生成排課結(jié)果。

四個(gè)Agent獨(dú)自及之間通信協(xié)商完成的工作機(jī)制如下：

流程1：管理員啟動(dòng)“班課師”Agent（CCTA），輸入班級(jí)對(duì)應(yīng)的課程及班級(jí)與課程對(duì)應(yīng)的教師，并輸入教師的意向上課時(shí)間及約束上課時(shí)間。

流程2：CCTA將信息傳遞給排課Agent（SA）；SA判斷CCTA傳遞的信息。

流程3：SA傳輸教室信息至教室Agent（CRA），CRA分配教室，傳遞至SA。

流程4：SA傳輸教師期望上課信息至?xí)r間Agent（TA），TA分配教室，傳遞至SA。

如果SA在排課的過(guò)程中發(fā)現(xiàn)與教室、時(shí)間信息有沖突，按照時(shí)間優(yōu)先的方式與CRA通信進(jìn)行協(xié)商，向CRA傳輸新的信息。

重復(fù)流程1-4，直至所有課程排完，SA將排課傳遞至CCTA，完成排課。排課流程如圖1所示。

圖1 排課流程

4 排課系統(tǒng)建模仿真

AnyLogic是惟一一款支持多Agent仿真的商業(yè)軟件，它支持基于智能體（Agent）的建模，目前已進(jìn)入市場(chǎng)多年，在物流、制造、市場(chǎng)、醫(yī)療、交通、軍事、應(yīng)急等諸多領(lǐng)域已有成熟的應(yīng)用且軟件功能日益完善。

軟件基于Java開(kāi)發(fā)，具有強(qiáng)大的二次開(kāi)發(fā)功能，支持實(shí)驗(yàn)、庫(kù)資源等的自定義開(kāi)發(fā)與封裝。支持基于智能體、離散事件、系統(tǒng)動(dòng)力學(xué)、Petri網(wǎng)、行人和交通仿真，可以根據(jù)需要任意組合?？梢暬拈_(kāi)發(fā)環(huán)境，支持模塊拖拽操作及腳本編輯，簡(jiǎn)單靈活豐富的外部數(shù)據(jù)接口，可直接讀取數(shù)據(jù)庫(kù)、GIS地圖庫(kù)、文本、圖片等文件。具備仿真和優(yōu)化功能。專(zhuān)業(yè)輔助開(kāi)發(fā)功能，支持自動(dòng)代碼補(bǔ)全、語(yǔ)法高亮等。專(zhuān)業(yè)模型調(diào)試功能，實(shí)時(shí)監(jiān)測(cè)事件，進(jìn)行代碼級(jí)別跟蹤調(diào)試。豐富的實(shí)驗(yàn)框架，具有人工智能、優(yōu)化、蒙特卡洛、敏感性分析、校準(zhǔn)比較等實(shí)驗(yàn)。豐富的庫(kù)資源，根據(jù)流程、交通、流體等常規(guī)領(lǐng)域建有豐富的模型資源庫(kù)。

AnyLogic軟件的智能體建模以個(gè)體為中心的建模、確定智能體（人、建筑物、產(chǎn)品等），定義其行為（驅(qū)動(dòng)力、狀態(tài)、行為等），將其放到一個(gè)中心環(huán)境中，或可建立連接。則系統(tǒng)層（整體）行為就展現(xiàn)為很多個(gè)體行為交互的結(jié)果。鑒于AnyLogic軟件的特性，本研究使用基于主體的建模來(lái)模擬排課任務(wù)執(zhí)行，偽代碼段如下：

5 結(jié)束語(yǔ)

分布式人工智能的多Agent系統(tǒng)是一個(gè)重要的研究領(lǐng)域，其中Agent之間的通信協(xié)商技術(shù)成為目前研究的熱點(diǎn)，并已應(yīng)用于動(dòng)態(tài)規(guī)劃及沖突解決多個(gè)場(chǎng)景。文章研究了將多Agent的通信協(xié)商技術(shù)應(yīng)用于排課系統(tǒng)的設(shè)計(jì)，但是研究仍不夠深入，沒(méi)有研究系統(tǒng)的真正實(shí)現(xiàn)、投入使用及Agent的自學(xué)習(xí)等情況，仍需要進(jìn)一步的繼續(xù)研究。