基于高職院校課程改革系統(tǒng)應(yīng)用設(shè)計(jì)的研究

張競予，王 偉

（1.陜西鐵路工程職業(yè)技術(shù)學(xué)院 陜西 渭南 714000；2.中鐵一局集團(tuán)有限公司 陜西 西安 710054）

目前隨著高職院校改革的推進(jìn)，其辦學(xué)規(guī)模和學(xué)生數(shù)量日益擴(kuò)大增多，高校課程設(shè)置安排這一基本工作的重要性凸顯，其實(shí)質(zhì)是根據(jù)教學(xué)計(jì)劃中所設(shè)置的課程安排合理的時(shí)間和地點(diǎn)，特別在教師、教室和時(shí)間等教學(xué)資源有限的條件下，對課程進(jìn)行有效的優(yōu)化組合，保證教學(xué)工作順利進(jìn)行，涉及因素多，是一項(xiàng)復(fù)雜多元化的系統(tǒng)問題工程。高校排課問題已被證明是一個(gè)NP完全問題，由于其具有多元復(fù)雜難解性，一直未得到很好的合理性解決[1]。

排課在各項(xiàng)高校教務(wù)工作中的地位處于重中之重，主要體現(xiàn)在課程編排的合理性不僅自接關(guān)系到每個(gè)學(xué)生的學(xué)習(xí)效率高低，而且教師教學(xué)效果的好壞以及教室等教學(xué)資源充分合理的利用率等都與其息息相關(guān)。此外排課又是所有教務(wù)工作中最繁雜的，不僅要考慮教師、學(xué)生、教室在排課時(shí)間約束下的要求，還要考慮各排課約束元因子之間的合理性，具體表現(xiàn)在課程存在著如分階段、分合班、單雙周、前后節(jié)、教師多課頭、大小教室、特殊教室等諸多復(fù)雜要素的影響，使得排課工作的繁復(fù)性激增，所以借助計(jì)算機(jī)自動排課是必須的。許多學(xué)者就排課問題進(jìn)行了廣泛的研究，并且提出了多種解決問題的算法。傳統(tǒng)的排課算法主要有專家系統(tǒng)法、圖論和貪婪算法等等[2]，而這些方法僅僅針對個(gè)別實(shí)際問題并不具備通用性，同時(shí)由于其關(guān)聯(lián)規(guī)則較難獲取而導(dǎo)致求解的結(jié)果并不十分理想。由于隨著近幾年智能技術(shù)的飛速發(fā)展，模擬退火算法、遺傳算法等效果較好的啟發(fā)式算法成為當(dāng)前排課問題的主要解決方法。為了進(jìn)一步降低沖突，提高排課效率和成功率，提出一種基于自衍生遺傳算法的排課系統(tǒng)，在傳統(tǒng)遺傳算法的基礎(chǔ)上進(jìn)行編碼方式的改善，針對其交互、演變性算法進(jìn)行自衍生操作從而加快其收斂速度，將其應(yīng)用于高校排課問題求解，實(shí)驗(yàn)結(jié)果表明，自衍生遺傳算法提高了高校排課效率和成功率，降低排課沖突率，滿足了排課問題的約束元條件，很好的解決了排課問題。

1 排課系統(tǒng)問題分析

1.1 排課系統(tǒng)需求目標(biāo)

教學(xué)任務(wù)的安排是一個(gè)充滿矛盾沖突的過程，主要矛盾沖突表現(xiàn)在任課教師、開設(shè)課程、授課時(shí)間、班級和地點(diǎn)等多方面需求對某一教學(xué)資源的需求，產(chǎn)生矛盾沖突，進(jìn)而導(dǎo)致教學(xué)工作不能正常合理的進(jìn)行。概括來講排課的目標(biāo)就是根據(jù)教學(xué)進(jìn)度任務(wù)計(jì)劃，來將教師、教室、課程和班級合理地安排在一周內(nèi)某一個(gè)不產(chǎn)生矛盾沖突的時(shí)間段中，并能保證排課系統(tǒng)正常工作，所以排課問題實(shí)質(zhì)上是一個(gè)在多約束元制約條件下的資源合理分配的問題。

1.2 排課系統(tǒng)的約束元

1）剛性約束元。在具體排課工作中必須要遵尋滿足的約束機(jī)制包括：在同一時(shí)間段內(nèi)同一教師只能夠安排一門課程；在同一時(shí)間段內(nèi)同一學(xué)生只能夠安排一門課程；在同一時(shí)間段內(nèi)同一教室只能夠安排一門課程；被安排的教室座位數(shù)應(yīng)大于該門課程上課時(shí)總?cè)藬?shù)。此外個(gè)別班級人數(shù)差別較大，且存在著許多班級組合與拆分的情況，例如具有實(shí)驗(yàn)環(huán)節(jié)的課程的實(shí)驗(yàn)部分為分班課，而基礎(chǔ)類課程則為多班合上的大課，一些專業(yè)基礎(chǔ)課為兩三個(gè)專業(yè)合上的小合班課等。所以高校排課系統(tǒng)除了要考慮按基本班排課外，還要考慮合班上課與分班上課情況的情形，另外還包括按班級公共選修課排課的情形。高校一般沒有班級的固定教室，并且教室具有多樣性，如階梯教室、大小教室，多媒體教室、機(jī)房和專業(yè)實(shí)驗(yàn)實(shí)訓(xùn)室等。教師存在著一個(gè)教師上多門課和多個(gè)教師合上一門課的情況。某些課程的周學(xué)時(shí)存在著單數(shù)的情況，前后節(jié)組合的問題解決，某些專業(yè)還存在一段時(shí)間連續(xù)上課的情況。

2）柔性約束元。如上所述可以看出排課中不僅排課剛性約束元的繁雜性強(qiáng)，最主要的對排課原則性要求是必須遵循的，即剛性約束元不能沖突這一排課必要條件。此外排課時(shí)還應(yīng)考慮剛性約束元內(nèi)部和相關(guān)聯(lián)性的一些非必要性的原則，即合理性柔性約束元。具體表現(xiàn)為：班級的課程在一周時(shí)間安排上要盡量分布均勻；同一教師的課程，在總體分布均勻合理且日課程量不超過四節(jié)的前提下，盡量安排在同一天以利于保證教師的授課效果，同時(shí)減少教師多次和返學(xué)校所耗費(fèi)的時(shí)間；保證同課程時(shí)間間隔的均勻性，避免一門課程連續(xù)上兩天或三天的情況；由于高校班級上課地點(diǎn)不固定，如果一個(gè)班的課程大多數(shù)被安排在相對固定的教室，不但可以減少學(xué)生課間換教室所耗費(fèi)的時(shí)間，還能增強(qiáng)學(xué)生的班級歸宿感；鑒于班級人數(shù)小等和教室容量小一的實(shí)際情況，還應(yīng)避免小班課程占用大教室的情況，優(yōu)先保證多班的合班課程對大教室的需求，以充分有效得利用教室資源[3]；體育類高強(qiáng)度活動課程應(yīng)避免安排在理論類講授課程之后，所以其應(yīng)安排在下午或上午3、4節(jié)。

2 排課系統(tǒng)設(shè)計(jì)

2.1 排課系統(tǒng)工作流程

排課工作每學(xué)期末首先由教務(wù)處根據(jù)各院系制定的學(xué)期教學(xué)任務(wù)進(jìn)度計(jì)劃，根據(jù)上課的剛?cè)峒s束元條件生成下一學(xué)期的教學(xué)任務(wù)，然后下發(fā)給系部教研室各教學(xué)單位，再根據(jù)教學(xué)單位返回的具體教學(xué)任務(wù)，制定全校各班級的課表及教師課程任務(wù)單。

2.2 剛?cè)嵝约s束元數(shù)據(jù)庫設(shè)計(jì)

1）模型結(jié)構(gòu)設(shè)計(jì)

圖1 排課系統(tǒng)模型圖Fig.1 Course scheduling system model diagram

2）邏輯關(guān)系設(shè)計(jì)。根據(jù)上述模型結(jié)構(gòu)設(shè)計(jì)所得到的系統(tǒng)模型，該排課系統(tǒng)主要涉及到的數(shù)據(jù)庫主要包括班級信息、教師信息、教室信息、時(shí)間信息、課程信息以及教學(xué)任務(wù)進(jìn)度計(jì)劃信息。

2.3 遺傳算法設(shè)計(jì)

根據(jù)系統(tǒng)的具體情況文中采用的遺傳算法設(shè)計(jì)，對傳統(tǒng)算法的做了適當(dāng)?shù)母倪M(jìn)，具體設(shè)計(jì)步驟如下。

1）排課問題編碼:由于傳統(tǒng)遺傳算法是采用二進(jìn)制來進(jìn)行編碼的，結(jié)合高校排課問題的特殊性再采用傳統(tǒng)二進(jìn)制編碼方式已使排課信息難以正確表達(dá)。因此本文采用一種改進(jìn)的編碼方式——自然編碼，如圖2所示，其中L表示課程，T表示時(shí)間，C表示教室。

2）初始族群的生成:因?yàn)閭鹘y(tǒng)遺傳算法采用的是隨機(jī)方式來產(chǎn)生初始族群，所以較容易的得到局部最優(yōu)排課方案，產(chǎn)生早熟現(xiàn)象，為此本文根據(jù)課程多少來動態(tài)安排族群的大小，采用均布設(shè)計(jì)方案來產(chǎn)生初始族群，使排課方案的初始解盡可能均勻分布在解的空間中，這樣不僅保證了遺傳算法得到全局最優(yōu)排課方案，而且在加快尋優(yōu)時(shí)間提高收斂速度和排課效率的同時(shí)，很好避兔了局部最優(yōu)排課方案過早出現(xiàn)。

圖2 遺傳算法單體表示Fig.2 Genetic algorithm monomer said

3）適應(yīng)度值計(jì)算:按照適應(yīng)度函數(shù)計(jì)算適應(yīng)度值，排課問題的實(shí)質(zhì)就是在滿足多種約束元的情況下得到最佳教學(xué)資源分配利用效果的排課方案。由于在遺傳算法的進(jìn)化過程中，其是由適應(yīng)度函數(shù)來確定進(jìn)化的發(fā)展方向的，所以適應(yīng)度函數(shù)就直接決定了排課方案的尋優(yōu)速度和找出最優(yōu)排課方案的成功率。由于排課問題具有多個(gè)目標(biāo)的特性，其適應(yīng)函數(shù)應(yīng)該滿足各個(gè)目標(biāo)從而達(dá)到最優(yōu)化。

式中α、β和γ分別為系統(tǒng)各目標(biāo)的權(quán)重值。

4）選擇操作：系統(tǒng)排課時(shí)選擇操作采用如圖3所示的輪盤賭選擇法[4]，即將輪盤根據(jù)各單體適應(yīng)度值的大小進(jìn)行區(qū)域分配，按其不同比例劃分區(qū)域，單體的適應(yīng)度數(shù)值越高，則其相應(yīng)所占的比例就越大，其存活的概率就更大，進(jìn)而進(jìn)入下一代族群的機(jī)率也就越大。

圖3 單體輪盤賭選擇方法Fig.3 Monomer roulette wheel selection method

5）自衍生交叉和變異操作：首先交叉操作主要是針對兩個(gè)單體通過交叉組合從而產(chǎn)生更加優(yōu)異的單體，而變異操作則主要是對研究單體進(jìn)行變異而得到新一代更加優(yōu)秀的單體，所以不難看出，交叉和變異操作在遺傳算法的收斂速度以及解的質(zhì)量方面起著核心控制作用，而由于傳統(tǒng)的遺傳算法交叉和變異操作在概率的方面采用固定方式，導(dǎo)致使單體在進(jìn)化后階段的豐富多樣率大大降低，從而使局部最優(yōu)解過早出現(xiàn)[5]。針對這一問題為了提高排課問題求解的效率，消除局部最優(yōu)解的現(xiàn)象的發(fā)生，本文主要針對對傳統(tǒng)遺傳算法中交叉和變異方式進(jìn)行了改良，提出采用適應(yīng)的交叉和變異操作，以下為其具體操作運(yùn)行方式。

式中Pi、Pj——分別為交叉和變異概率；g——變異單體的適應(yīng)度值；g′——交叉中適應(yīng)度值較大的單體；k1、k2——分別為（0，1）的隨機(jī)性。

通過以上操作方式的改進(jìn)，不但增強(qiáng)種群中單體的豐富多樣性，而且很好的避免了局部最優(yōu)解過早出現(xiàn)的現(xiàn)象。

6）沖突檢測消除:經(jīng)過交叉和變異操作后可能仍會會產(chǎn)生沖突，所以還需要進(jìn)行沖突再檢測并解決沖突已獲得最優(yōu)解[6]。

2.4 自衍生遺傳算法系統(tǒng)求解流程

根據(jù)遺傳算法各種操作改良后的自動排課系統(tǒng)工作過程主要為:首先進(jìn)行排課問題解的初始化過程，也就是產(chǎn)生遺傳算法初始族群；接著以自然編碼方式對排課問題進(jìn)行編碼操作；計(jì)算出每一排課方案的適應(yīng)度值；運(yùn)用輪盤賭方式選擇出更為優(yōu)良好的單體產(chǎn)生排課方案下一代族群；接著對族群中的單體通過交叉和變異操作產(chǎn)生新的單體，計(jì)算其適應(yīng)度值對判斷其是否進(jìn)入下一代[7]；判定全局最優(yōu)排課方案是否滿足要求，如果找到則進(jìn)化結(jié)束并輸出，如果不滿足再回轉(zhuǎn)至第三步系統(tǒng)操作過程。系統(tǒng)操作主要流程如圖4所示。

3 計(jì)算機(jī)排課系統(tǒng)實(shí)現(xiàn)與結(jié)果

3.1 排課系統(tǒng)實(shí)現(xiàn)

圖4 排課系統(tǒng)工作流程圖Fig.4 Course scheduling system work flow chart

為了進(jìn)一步檢驗(yàn)本文算法的可靠性通過將其與模擬退火算法和傳統(tǒng)的遺傳算法進(jìn)行了對比試驗(yàn)，通過運(yùn)用VC++編程方法來進(jìn)行實(shí)現(xiàn)[8]。排課系統(tǒng)各約束元素分布如表1所示，系統(tǒng)遺傳算法的控制要素設(shè)置情況如表2所示。

表1 排課系統(tǒng)約束元素表Tab.1 Course scheduling system constraint element table

表2 系統(tǒng)控制要素設(shè)置表Tab.2 System control factors set the table

3.2 結(jié)果分析

從表3所示3種方法的運(yùn)行結(jié)果不難看出，本文改進(jìn)的遺傳算法比模擬退火算法和傳統(tǒng)遺傳算法效果好，對比結(jié)果表明不僅在最優(yōu)排課方案所需時(shí)間要少，而且在矛盾沖突率和成功率方面優(yōu)于其他方法，解決排課問題總體效果好。總之通過采用本文算法進(jìn)行排課不僅提高了排課效率，排課的成功率達(dá)到100%，而且在提高教室利用率充分運(yùn)用教學(xué)資源方面也有很好的效果，說明了本文算法是一種成功率高、綜合性好的排課方法。

表3 系統(tǒng)運(yùn)行結(jié)果對比表Tab.3 The contrast table of systematic operation result

4 結(jié)束語

計(jì)算機(jī)技術(shù)為現(xiàn)代化教育帶來了方便、快捷，通過采用計(jì)算機(jī)排課系統(tǒng)，不但大大節(jié)省人力、物力，而且也減少了課程沖突。本文針對排課特點(diǎn)，結(jié)合遺傳算法的優(yōu)點(diǎn)，對遺傳算法又進(jìn)行了一些改良，結(jié)果表明，自衍生遺傳算法在一定程度上能夠解決高校排課難題。通過本文系統(tǒng)算法較大程度上減少教務(wù)人員的工作量，而且進(jìn)一步優(yōu)化解決了傳統(tǒng)排課算法效率低，課程沖突率高，影響教學(xué)效率等問題，具有一定的借鑒使用價(jià)值。

[1]張長庚.基于遺傳算法的浙江水利水電?？茖W(xué)校排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].成都：成都電子科技大學(xué)，2010.

[2]Rxghu Ramakrishnxn，Johxnnes Gchrkc.數(shù)據(jù)庫管理系統(tǒng)原理與設(shè)計(jì)[M].北京：清華大學(xué)出版社，2004.

[3]胡世清.高校排課多元優(yōu)化策略與自動實(shí)現(xiàn)方法的研究[J].現(xiàn)代教育技術(shù)，2011（7）:105-109.HU Shi-qing.Research of university course arrangement multivariate optimization strategy and automatic realization method[J].Modern Educational Technology，2011（7）:105-109.

[4]張小紅.高校排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].電子科技，2012（7）:45-47.ZHANG Xiao-hong.Design and realization of college course scheduling system[J].Electronic Science and Technology，2012（7）:45-47.

[5]張立巖，張世民，秦敏.基于改進(jìn)粒子群算法排課問題研究[J].河北科技大學(xué)學(xué)報(bào)，2011，3 （2）:265-268.ZHANG Li-yan，ZHANG Shi-min，QIN Min.Research in improved particle swarm optimization for schedule arrangement[J].Journal of Hebei University of Science and Technology，2011，3（2）:265-268.

[6]閏保權(quán).改進(jìn)的遺傳算法在排課系統(tǒng)中的應(yīng)用研究[J].信息技術(shù)，2011（9）:125-127.YAN Bao-quan.Application of improved genetic algorithm incourse scheduling system[J].Information Technology，2011（9 ）:125-127.

[7]李梅云.基于遺傳算法的排課編碼設(shè)計(jì)[J].漳州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2011（3）:22-27.LI Mei-yun.The course code design based on genetic algorithms[J].Journal of Zhang zhou Institute of Technology，2011（3）:22-27.

[8]董冬，張少博，劉曉.試驗(yàn)狀態(tài)信息管理軟件設(shè)計(jì)[J].火箭推進(jìn) ，2013（6）:72-77.DONG Dong，ZHANG Shao-bo，LIU Xiao.Design of information management software for test status[J].Journal of Rocket Propulsion，2013（6）:72-77.