基于高職院校課程改革系統應用設計的研究

張競予，王 偉

（1.陜西鐵路工程職業技術學院 陜西 渭南 714000；2.中鐵一局集團有限公司 陜西 西安 710054）

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

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

1 排課系統問題分析

1.1 排課系統需求目標

教學任務的安排是一個充滿矛盾沖突的過程，主要矛盾沖突表現在任課教師、開設課程、授課時間、班級和地點等多方面需求對某一教學資源的需求，產生矛盾沖突，進而導致教學工作不能正常合理的進行。概括來講排課的目標就是根據教學進度任務計劃，來將教師、教室、課程和班級合理地安排在一周內某一個不產生矛盾沖突的時間段中，并能保證排課系統正常工作，所以排課問題實質上是一個在多約束元制約條件下的資源合理分配的問題。

1.2 排課系統的約束元

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

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

2 排課系統設計

2.1 排課系統工作流程

排課工作每學期末首先由教務處根據各院系制定的學期教學任務進度計劃，根據上課的剛柔件約束元條件生成下一學期的教學任務，然后下發給系部教研室各教學單位，再根據教學單位返回的具體教學任務，制定全校各班級的課表及教師課程任務單。

2.2 剛柔性約束元數據庫設計

1）模型結構設計

圖1 排課系統模型圖Fig.1 Course scheduling system model diagram

2）邏輯關系設計。根據上述模型結構設計所得到的系統模型，該排課系統主要涉及到的數據庫主要包括班級信息、教師信息、教室信息、時間信息、課程信息以及教學任務進度計劃信息。

2.3 遺傳算法設計

根據系統的具體情況文中采用的遺傳算法設計，對傳統算法的做了適當的改進，具體設計步驟如下。

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

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

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

3）適應度值計算:按照適應度函數計算適應度值，排課問題的實質就是在滿足多種約束元的情況下得到最佳教學資源分配利用效果的排課方案。由于在遺傳算法的進化過程中，其是由適應度函數來確定進化的發展方向的，所以適應度函數就直接決定了排課方案的尋優速度和找出最優排課方案的成功率。由于排課問題具有多個目標的特性，其適應函數應該滿足各個目標從而達到最優化。

式中α、β和γ分別為系統各目標的權重值。

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

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

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

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

通過以上操作方式的改進，不但增強種群中單體的豐富多樣性，而且很好的避免了局部最優解過早出現的現象。

6）沖突檢測消除:經過交叉和變異操作后可能仍會會產生沖突，所以還需要進行沖突再檢測并解決沖突已獲得最優解[6]。

2.4 自衍生遺傳算法系統求解流程

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

3 計算機排課系統實現與結果

3.1 排課系統實現

圖4 排課系統工作流程圖Fig.4 Course scheduling system work flow chart

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

表1 排課系統約束元素表Tab.1 Course scheduling system constraint element table

表2 系統控制要素設置表Tab.2 System control factors set the table

3.2 結果分析

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

表3 系統運行結果對比表Tab.3 The contrast table of systematic operation result

4 結束語

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

[1]張長庚.基于遺傳算法的浙江水利水電專科學校排課系統設計與實現[D].成都：成都電子科技大學，2010.

[2]Rxghu Ramakrishnxn，Johxnnes Gchrkc.數據庫管理系統原理與設計[M].北京：清華大學出版社，2004.

[3]胡世清.高校排課多元優化策略與自動實現方法的研究[J].現代教育技術，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]張小紅.高校排課系統的設計與實現[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].河北科技大學學報，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]閏保權.改進的遺傳算法在排課系統中的應用研究[J].信息技術，2011（9）:125-127.YAN Bao-quan.Application of improved genetic algorithm incourse scheduling system[J].Information Technology，2011（9 ）:125-127.

[7]李梅云.基于遺傳算法的排課編碼設計[J].漳州職業技術學院學報，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]董冬，張少博，劉曉.試驗狀態信息管理軟件設計[J].火箭推進 ，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.