基于LAMP的學(xué)分制選排課繳費(fèi)系統(tǒng)的研究

李 碩，張新明

（1.南通大學(xué) 財務(wù)處，江蘇南通226019；2.南通大學(xué) 人事處，江蘇 南通226019）

一、前言

近年來隨著教育部對于學(xué)分制改革推進(jìn)的要求和高校規(guī)模繼續(xù)不斷擴(kuò)大的現(xiàn)狀，我國高校的教育教學(xué)管理體制正緩慢地由學(xué)年制向?qū)W分制的轉(zhuǎn)變。因此，對能夠適應(yīng)學(xué)分制教學(xué)管理、學(xué)生按照各自經(jīng)濟(jì)情況和學(xué)習(xí)目標(biāo)自主選擇學(xué)習(xí)方向和進(jìn)度，支付多樣化，選排課算法優(yōu)異的，符合財務(wù)管理規(guī)定的高效安全的學(xué)分制選排課繳費(fèi)系統(tǒng)進(jìn)行設(shè)計和研究是十分必要的。

在平臺選擇方面，系統(tǒng)的安全性和健壯性的要求極為重要，LAMP（Linux＋Apache＋MyS QL＋PHP）架構(gòu)的數(shù)據(jù)吞吐性能，穩(wěn)定性安全性較W indows系統(tǒng)更高，對高校這種規(guī)模的應(yīng)用來講，系統(tǒng)投入的成本也在承受范圍之內(nèi)，所以系統(tǒng)選擇采用基于PHP的LAMP體系來研究和構(gòu)建。

在排課方面，排課問題屬于運(yùn)籌學(xué)中的時間表（TTP）問題,高校排課問題很早就成為了眾多軟件開發(fā)者做關(guān)注的問題之一，研究人員對排課算法進(jìn)行了大量的研究和改進(jìn)，國內(nèi)的研究主要選用了目前性能公認(rèn)較為優(yōu)良的遺傳算法，所以本系統(tǒng)選用遺傳算法來解決排課的課題。

在網(wǎng)絡(luò)自主繳費(fèi)方面，系統(tǒng)主要根據(jù)合作銀行網(wǎng)銀系統(tǒng)的數(shù)據(jù)接口定義，編制了和銀行直接通信的前置系統(tǒng)，能夠達(dá)到即時結(jié)算，準(zhǔn)實時數(shù)據(jù)更新的水平。

二、系統(tǒng)主要問題的實施策略和設(shè)計

1.競爭性選課

目前高校在少量的選修課上試點(diǎn)應(yīng)用了網(wǎng)絡(luò)選課的方式，但即使在這種極少選課量的情況下，學(xué)生爭奪教學(xué)資源卻變成了拼搶硬件資源，為了保證公平性，本系統(tǒng)采用在學(xué)生選課初始化時，賦予每個學(xué)生同樣的分值或者稱為“虛擬貨幣”，出價可以反映學(xué)生選擇此課程的意愿程度，競價過程不公開，相當(dāng)于投標(biāo)書，然后根據(jù)課程開設(shè)的規(guī)模進(jìn)行排名，同時可以開放進(jìn)行多輪選課，解決競價失敗的問題。

2.排課算法

排課問題其實是一種調(diào)度問題（Scheduling Problem），是一個非線性的，需要滿足各種軟硬約束條件的，模糊多目標(biāo)優(yōu)化的，N-P完全的時空組合問題。其復(fù)雜性來源于要達(dá)到排課的目標(biāo)其需要滿足的軟硬約束條件非常之多，為了編排出合理人性化的課程表，還必須考慮到課程重要程度、課程優(yōu)先級、教師時間安排等，多校區(qū)教學(xué)還要避免出現(xiàn)密集跨校區(qū)問題。所以自動排課方案已經(jīng)成為當(dāng)今諸多研究者感興趣的課題。主要排課算法包括遺傳算法,禁忌搜索,蟻群算法，進(jìn)化算法或者上述幾種的混合。其中遺傳算法正在越來越廣泛地得到應(yīng)用。這是由于這種方法是能夠在元素級條件下找到最優(yōu)解決方案的強(qiáng)大算法，所以以這種算法為基礎(chǔ)的改進(jìn)能夠在可控的時間范圍完成目標(biāo)工作。

遺傳算法的基本步驟：（1）對問題的可行進(jìn)行編碼，使之形成一條染色體；（2）對最大代數(shù)、種群規(guī)模、選擇概率、交叉概率、變異概率等參數(shù)進(jìn)行初始化；（3）根據(jù)設(shè)定的參數(shù)和編碼方案生成初始種群P；（4）使用交差概率對種群進(jìn)行交叉操作，產(chǎn)生新的染色體并構(gòu)成子種群P；（5）使用變異概率對子種群進(jìn)行變異操作，形成P；（6）使用選擇概率對種群集合P∪P進(jìn)行選擇操作，生成P；（7）使用適應(yīng)度函數(shù)對P進(jìn)行評價，若種群P是最優(yōu)解，則算法結(jié)束，若不是則選擇適應(yīng)度較強(qiáng)的染色體形成種群P轉(zhuǎn)第4步。遺傳算法流程如圖1所示。

圖1 遺傳算法流程

在學(xué)分制管理體系下，公共必修課的教學(xué)安排仍然按照學(xué)年制的方式有計劃地進(jìn)行，方式仍然為按照行政班級，年級等進(jìn)行排課，學(xué)生不選課。在其他課程包括專業(yè)必修課，專業(yè)選修課，公共選修課方面，將“班級”和“年級”在學(xué)分制體系下合并體現(xiàn)為“所學(xué)專業(yè)”，則算法的約束條件主要有：

（1）遺傳算法在公共必修課的排課業(yè)務(wù)中的約束條件。本文采用的是對公共必修課按照班級和周課表的形式進(jìn)行預(yù)排課。公共必修課排課的具體約束條件包括硬性條件和軟性條件，其中：

1）硬性條件

a.同一個現(xiàn)實世界中的實體對象（學(xué)生，老師，教室）不能同時處于兩件以上的事務(wù)中；

b.一個教室安排的人數(shù)不能超過教室能容納的最大人數(shù)；

c.教師半天內(nèi)不能跨校區(qū)授課；

d.教室（場地）設(shè)備配備。

2）軟性條件

a.課程類型對時間的要求，繁重的課程應(yīng)放在精神狀態(tài)比較好的上午；

b.體育課、實習(xí)課應(yīng)安排在下午；

c.課程在時間片上應(yīng)合理均勻地分布；

d.為了避免教學(xué)資源浪費(fèi)，盡量避免教室內(nèi)空出大片座位；

e.教師在一天內(nèi)最好不要跨校區(qū)教學(xué)；

f.個別教師具體要求。

這些條件也就是適應(yīng)性函數(shù)構(gòu)成的要素。

（2）遺傳算法在公共必修課的排課業(yè)務(wù)中的算法設(shè)計

1）編碼

遺傳算法中第一個要考慮的問題是如何對染色體進(jìn)行編碼，一條染色體中應(yīng)包含課程、教師、教室、班級、時間片、校區(qū)等相關(guān)的信息，采用二維表的形式，以時間片作為基準(zhǔn)資源使用，假設(shè)每周可供開課的時間片數(shù)5×5=25，為每兩小節(jié)為一個時間片，設(shè)時間片集合為：T= {11,12,13,14….53,54,55},11表示周一的第一二節(jié)課，以此類推，教室集合為：R={R1,R2,R3……Rn},時間片和教室的笛卡爾積，也就是可供使用的時空資源為 G=T×R= {(11,R1),(12,R1),….(55,Rn)},那么資源一共55×n個，排課所求解的目標(biāo)就是為每一個教學(xué)任務(wù)找到合適的資源。

2）生成初始種群

首先要在初始種群生成前進(jìn)行一些設(shè)置操作，比如體育課等要安排在下午等，之后可以開始進(jìn)行初始種群，首先確定公共必修課教學(xué)任務(wù)的條數(shù)M,并將教學(xué)任務(wù)進(jìn)行編號，然后用$L=ran d（0,M－1,1）；shuffle（$L）生成一個隨機(jī)的0～M-1的不重復(fù)的隨機(jī)數(shù)字序列F1，依次將數(shù)組F的元素代表的教學(xué)任務(wù)的信息提取出來生成初始種群。

因為教學(xué)任務(wù)序列F1經(jīng)由系統(tǒng)隨機(jī)產(chǎn)生，僅僅循環(huán)M次，導(dǎo)致教學(xué)任務(wù)所使用的時空資源差異不夠，對于后面的再生、交叉、編譯操作不利，所以再取隨機(jī)數(shù)列F2,F3,可產(chǎn)生足夠數(shù)量染色體的初始種群。

3）適應(yīng)度函數(shù)設(shè)計

系統(tǒng)重點(diǎn)考慮課程類型對時間片的合理安排和避免教師跨校區(qū)教學(xué)，則單個基因適應(yīng)度設(shè)計見公式（1）

變量a代表困難課程安排的優(yōu)劣度評價，權(quán)重為0.3，變量b代表體育、實習(xí)類課程安排的優(yōu)劣度評價，權(quán)重為0.1變量c代表教學(xué)任務(wù)在一周內(nèi)分布的優(yōu)劣度評價，權(quán)重為0.3，同樣的一個教學(xué)任務(wù)，如果相隔太近甚至在同一天安排，則容量太大，如果相隔太長，則容易遺忘。變量d代表教室座位的利用率優(yōu)劣度評價，權(quán)重為0.1，變量e代表教師在同一天內(nèi)在/不在一個校區(qū)內(nèi)教學(xué)，權(quán)重為0.3。這樣，每條染色體的適應(yīng)度的值為每個基因的適應(yīng)度值之和。每個染色體有M個基因，設(shè)每個基因的適應(yīng)度為f（k）（0≤k≤M－1）,則每條染色體的適應(yīng)度見公式（2）

4）選擇操作

選擇操作的主要方法有:輪盤賭，局部選擇等。輪盤賭選擇操作完全依賴于系統(tǒng)生成的隨機(jī)數(shù)，容易丟失極為優(yōu)良的染色體，系統(tǒng)采用直接對每個染色體的適應(yīng)度值進(jìn)行排名，選擇最大的20%直接復(fù)制到下一代，則可得到全局最優(yōu)解。

5）交叉操作

交叉操作的主要方法有：單點(diǎn)交叉、均勻交叉等，但由于多校區(qū)的因素存在，使得產(chǎn)生硬性沖突的幾率極高，所以系統(tǒng)將每對染色體中的部分進(jìn)行交叉，這樣產(chǎn)生沖突的幾率大為降低。具體的方法是，設(shè)教學(xué)任務(wù)為TM,TM有三個維度，分別為（Teacher x,Class y,Course z）,而時空資源表有兩個維度，分別為教室和時間。根據(jù)生成的初始種群，采取二維資源片編碼十進(jìn)制方式混合編碼，假設(shè)一個基因是TM01000111，表示TM教學(xué)任務(wù)在01校區(qū)0001教室周一上午一二節(jié)課上課，依次生成開課的數(shù)據(jù)，形成一個染色體，交叉操作如圖2所示。

圖2 排課交叉操作示意

選取一對染色體，隨機(jī)選擇交叉點(diǎn)，將其中的教學(xué)任務(wù)相同的基因中時空資源部分進(jìn)行交換。在交叉的過程中既交叉點(diǎn)作為參考點(diǎn)，既可以選擇交叉點(diǎn)的前后的基因都進(jìn)行交叉，也可以單獨(dú)對交叉點(diǎn)前或者后的基因進(jìn)行交叉，在對交叉點(diǎn)前后的基因進(jìn)行交叉時，交叉分步進(jìn)行，交叉時進(jìn)行判斷，如果有沖突，交叉取消，另隨機(jī)取交叉點(diǎn)。

6）變異操作

變異操作采用相應(yīng)的時空資源變異操作，根據(jù)變異概率選出一個染色體，隨機(jī)選擇變異點(diǎn)，在變異點(diǎn)前方或者后方選擇基因中的時空資源片，變換資源，并檢測變異沖突，發(fā)現(xiàn)有沖突變異取消，基本過程如圖3所示

圖3 排課交叉操作示意

7）沖突處理的步驟

在交叉變異的過程中，采用教學(xué)任務(wù)的時空資源進(jìn)行交叉，大大減少了沖突發(fā)生的情況，但是畢竟沖突是無法避免的，所以應(yīng)該在進(jìn)行各種遺傳操作之前進(jìn)行沖突檢測，檢測到?jīng)_突則取消操作，基本方法是：

a.教師沖突的處理：假設(shè)總共有T位教師，對教師進(jìn)行編碼，編碼范圍是0～T-1，并依次讀出每個教師可以執(zhí)教的教學(xué)任務(wù)，再檢測時間片表，如果存在重復(fù)的行，則表明沖突，取消遺傳操作，沒有則表明正常，可以遺傳。

b.教室沖突的處理：假設(shè)某校區(qū)共有R個教室，編碼范圍是0～R-1,遺傳檢測同教師沖突

c.班級沖突的處理：假設(shè)共有C個班級，編碼范圍是0～C-1,遺傳檢測同教師沖突

d.校區(qū)沖突的處理：這里系統(tǒng)的交叉操作不會產(chǎn)生學(xué)生跨校區(qū)上課的情況，因為在生成初始種群時就已經(jīng)排除了學(xué)生跨校區(qū)上課的情況，所以同班級要完成的教學(xué)任務(wù)都在同一個校區(qū)內(nèi)進(jìn)行，對班級來說，只有時空資源片可能會發(fā)生改變，所以系統(tǒng)只需要對教師遍歷，如果搜索出多個校區(qū)編號的情況，則說明有沖突，則需要恢復(fù)到交叉前的狀態(tài)，進(jìn)行下一對染色體的交叉操作。

系統(tǒng)采用這樣的遺傳算法，能夠保留遺傳的每一代最好的個體，隨著遺傳代數(shù)的增高，不斷丟棄最差的個體，在初始進(jìn)化的數(shù)百代中，適應(yīng)度呈波動變化，隨著遺傳代數(shù)的增大，適應(yīng)度值平穩(wěn)增高，逐漸趨近最優(yōu)解。

（3）遺傳算法在其他課程排課業(yè)務(wù)中的算法設(shè)計

其他課程系統(tǒng)采用先選課，后排課的模式進(jìn)行，同公共必修課排課算法不同的是班級的概念消失了，取而代之的是選課結(jié)束以后產(chǎn)生臨時的修習(xí)同一門課程的學(xué)生集，在數(shù)據(jù)庫中必須建立臨時教學(xué)集合表，代替班級表行使職責(zé)。在初始化種群的時候，讀取待排課專業(yè)的“專業(yè)課程樹”，一個專業(yè)一個專業(yè)的按照硬約束初始化種群，當(dāng)然，占用的時空資源，包括教室占用表，時間片占用表是在專業(yè)之間來說公用的。初始化種群時選擇專業(yè)的先后次序也采用隨機(jī)抽取的方式，以求專業(yè)之間的公平性。

3.網(wǎng)銀支付

學(xué)生在本系統(tǒng)選課完畢，確認(rèn)繳費(fèi)后，使用URL參數(shù)傳遞的方式將信息傳至合作行網(wǎng)銀系統(tǒng)：繳費(fèi)成功后，網(wǎng)銀系統(tǒng)向本系統(tǒng)發(fā)送的信息，本系統(tǒng)接受URL,并通過讀取URL參數(shù)的方式獲取參數(shù)信息，并進(jìn)行相應(yīng)的數(shù)據(jù)庫操作。

4.安全

Linux為增加系統(tǒng)安全性提供了防火墻保護(hù)。系統(tǒng)使用系統(tǒng)內(nèi)置的軟件iptables定制適合自己的“數(shù)據(jù)包處理策略”。iptables的防火墻策略主要有三種，包過濾（Packet Filter），代理（Proxy），狀態(tài)分析（Stateful Inspection）。本系統(tǒng)將這三種技術(shù)混合使用建立了較為穩(wěn)固的L inux防火墻系統(tǒng)。

對于惡意攻擊，系統(tǒng)選用了Linux平臺下廣泛使用的PSAD程序，可以和系統(tǒng)防火墻合作，可根據(jù)行為判斷并防范幾乎所有的針對Linux網(wǎng)絡(luò)的惡意企圖，能夠深入到應(yīng)用層對內(nèi)容進(jìn)行分析，并對用戶進(jìn)行警告。本系統(tǒng)采用此方法檢測入侵和濫用效果良好。

三、系統(tǒng)測試

1.競價方式選課測試

在現(xiàn)有的選課系統(tǒng)中，采用競價選課方式的極少，系統(tǒng)對競價方式選課進(jìn)行了長時間大量數(shù)據(jù)的測試，發(fā)現(xiàn)還有如下問題需要改善。

（1）需要事先對教學(xué)安排有一定的規(guī)劃和估算，在進(jìn)行一定的選課導(dǎo)向教育的同時要科學(xué)設(shè)定授課規(guī)模，否則極容易導(dǎo)致選課失敗，在邀請學(xué)生進(jìn)行測試的過程中，選課鏈斷裂出現(xiàn)的幾率有時候高達(dá)13%。

（2）虛擬貨幣的設(shè)定一定要科學(xué)，數(shù)額最好要大一點(diǎn)，否則容易導(dǎo)致排名的末尾出現(xiàn)多個相同出價的學(xué)生，系統(tǒng)無法決策哪個競價有效，需要人工干預(yù)。

2.排課測試

公共必修課排課適應(yīng)度代數(shù)二維圖如圖4所示。

圖4 公共必修課排課適應(yīng)度示意

非公共必修課排課適應(yīng)度代數(shù)二維圖如圖5所示。

可見公共必修課排課為了應(yīng)對多校區(qū)的因素對傳統(tǒng)遺傳算法排課進(jìn)行了改良，性能良好，非公共必修課因為采用先選課后排課的方式，按照數(shù)據(jù)初始化時設(shè)定的課程優(yōu)先級，預(yù)先搶占一些時空資源片，再進(jìn)行排課操作，性能較公共必修課排課略差。

圖5 非公共必修課排課適應(yīng)度示意

四、總結(jié)

系統(tǒng)將選課、排課、自助繳費(fèi)這三個學(xué)生在校期間的主要活動結(jié)合起來協(xié)同運(yùn)作系統(tǒng)，對排課、選課、自助繳費(fèi)這三大系統(tǒng)進(jìn)行了較為深入地整合，采用的對公共必修課預(yù)排課，其余課程開放學(xué)生選課的方式，應(yīng)用改進(jìn)遺傳算法，較好地解決了完全學(xué)分制教學(xué)管理體制下的選排課問題，最后的排課結(jié)果也比較符合系統(tǒng)設(shè)計的目標(biāo)。

但是，由于完全學(xué)分制管理體系下的選排課工作極其復(fù)雜，系統(tǒng)在先排后選算法方面仍然有很大的改進(jìn)余地，應(yīng)該在提高算法效率，穩(wěn)定排課結(jié)果適應(yīng)度值方面進(jìn)一步開展研究。

[1]黃干平,劉娟.解“時間表問題”的啟發(fā)式算法[J].武漢大學(xué)學(xué)報（自然科學(xué)版）,1996,42(1):71-74.

[2]Nakayama.M,Hoshito.J.Development of A Support System for University Course Selection Using Semantic Web Technology[R].5th InternationalConference on W eb Information Systemsand Technologies,2009:389-392.

[3]Chinnasri.W,Sureerattanan.N.Comparison of performance between different selection strategies on genetic algorithm w ith course timetabling problem[R].Advanced M anagement Science(ICAMS),2010 IEEE International Conference on.2010(2):105.

[4]李敏強(qiáng),寇紀(jì)淞,林丹等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社,2002:316-317.

[5]M en-Shen.Tsai,Fu-Yuan.Hsu.Comparison of genetic algorithm reproduction methods for distribution system loss m inim ization [R].International Conference on Machine Learning and Cybernetics.2004(1-7):4113-4118.

[6]李建喜,舒仲遠(yuǎn),陳文生.多校區(qū)排課遺傳算法設(shè)計[J].南昌航空工業(yè)學(xué)院學(xué)報,2006,20(2):61-64.