王海波

（南通科技職業(yè)學院，江蘇 南通 226007）

1 引言

當前，隨著全國各高校的擴招及合并，使得學生在數(shù)量上激增，同時也增加了很多班級和專業(yè)。那么，伴隨人工智能技術的發(fā)展，智能排課技術的研究已經(jīng)成為高校信息化建設改革的熱點?？茖W地編排課表可以穩(wěn)定教學秩序，提高教學效率及質(zhì)量，因此對智能排課技術的研究勢在必行。

2 智能排課模型構建

在高校的教學過程中，主要有理論教學、實驗教學、課內(nèi)實踐、課外實踐、實習教學等。在課程的設置上有公共課、專業(yè)基礎課、專業(yè)技能課等。那么，如何使得高校有限的教室、實驗室及教師這些資源得以合理高效地分配和調(diào)度，是智能排課需研究的首要問題。

2.1 模型描述

高校的排課需考慮的要素有：班級，課程，時間，教師，教室。基本原則是：在同一時間段內(nèi)，教師、學生和教室沒有沖突，同時又要保證這些教學資源能夠高效、合理被使用、分配。這里，針對高校智能排課，我們來構建其數(shù)學模型。

高校排課問題的解是周課時表，我們設某高校有M個班級，M={mm︱m=1,2,3…M}，其中每個班級的人數(shù)分別為{km︱m=1,2,3…M}；該校的課程總數(shù)是U，U={uu︱u=1,2,3…U}；每周從周一到周五上課，設連續(xù)兩節(jié)課為一時間片，這樣每天有4個時間片可以上課。每周可以有20個時間片?？梢詫⑦@些時間片表示為：n1,n2,n3,……,n19,n20。共有R名專兼職教師，則 R={rr︱r=1,2,3…R}；且有T 個教室，T={tt︱t=1,2,3…T}，每個教室能夠容納學生的人數(shù)分別為{xt︱t=1,2,3…T}；那么在時間片nn，教師rr在教室tt中給班級mm教授uu課程，則nnrrttmmuu=1，反之nnrrttmmuu=0。

2.2 模型中約束條件

硬約束條件：

(1)在某教室上課的班級，其學生人數(shù)應小于或等于該教室所能容納的最大人數(shù)，即km<=xt。

(2)在同一個時間內(nèi)，同一行政班最多只允許安排一門課程，即

(3)在同一個時間內(nèi)，同一教師最多只允許安排一門課程，即

(4)在同一個時間內(nèi)，同一教室最多只允許安排一門課程，即

軟約束條件：

軟約束條件是指為了達到較好的教學效果，讓課程的安排滿足科學合理的要求，現(xiàn)考慮如下幾項原則：

(1)教師在同一天內(nèi)相鄰時間片內(nèi)的課程所安排的教室要盡可能相同或相近。

(2)學生在同一天內(nèi)相鄰時間片內(nèi)的課程所排教室要盡可能相同或相近。

(3)同一行政班的同一門課每周安排兩次，兩次課之間的時間間隔要合理，最好相隔兩天。均勻分配每班每天的課時總數(shù)。

(4)滿足教師對教室及時間的一些特殊要求。

(5)針對不同課程的特點，合理安排上課的時間及教室，以達到最佳教學效果。

(6)在安排教室時，盡量達到教室所能容納的最多人數(shù)與班級人數(shù)相匹配，達到最大化地利用教室資源。

2.3 模型的優(yōu)化

智能排課就是如何將上述軟約束條件進行最優(yōu)組合的問題，我們設函數(shù)為f。

(1)對于有特殊要求的教師，優(yōu)先安排好其上課地點及時間，依據(jù)教授、副教授、講師這些職稱來設相應權值ai(i=1,2,3)，相應的值為2、1、1。 f1=∑ai。

(2)如果某天的課時總數(shù)多于平均課時數(shù)的30%，其權值設為2，否則設為10。設相應權值di，則 f2=∑di。

(3)周學時多的課程要均勻合理分配，每周4學時的課也要均勻合理分配，設分配權值為yi，則 f3=∑yi。

(4)針對課程類型做合理劃分，可分為：記憶理解型、推理邏輯型、操作實踐型、綜合型、體育類這五類。為每一類設定一個分值ei，則 f4=∑ei。

(5)設某行政班mm在某教室tt上課，該班上課的人數(shù)km與該教室能夠容納的最大人數(shù)xt的比值同教室的利用率成正比。則

通過上述對排課問題的分析討論，得到目標的優(yōu)化函數(shù)：

其中，pi(i=1,2,3,4,5)為約束條件權值，可以由工作人員根據(jù)經(jīng)驗來確定，這里，我們令 pi(i=1,2,3,4,5)的值分別為

3，9，6，4，5。

3 基于改進遺傳算法的排課

3.1 遺傳算法

遺傳算法是一種隨機搜索算法，通過對生物進化過程的模仿，在種群中的個體之間的重組、交叉和變異等遺傳操作算子來實現(xiàn)優(yōu)勝劣汰，進而完成搜索。遺傳算法的基本運算過程為初始化，個體評價，選擇運算，交叉運算，變異運算，得到下一代種群，終止條件判斷。

3.2 遺傳算法存在的缺陷及改進

(1)初始種群的均勻化改進

在一些遺傳算法中，往往是隨機產(chǎn)生初始種群，這就使得在解空間中初始種群的分布可能不均勻，進而算法的性能受到影響。所以，我們在初始種群產(chǎn)生時，就盡量使其在解空間中滿足均勻分布。即，針對初始種群中的每個個體，為其設定一個限制距離，這樣，初始種群中的每個個體之間的距離需大于這個距離限制，因而保證了在初始種群的個體在解空間中較均勻地分布，個體間有顯著的差別，使得初始種群的模式豐富，進而得到最優(yōu)收斂的全局解，使算法的性能得到提高。

(2)適應度函數(shù)的改進

在遺傳算法中，適應度函數(shù)的選取非常重要，若選取不合理，可能會出現(xiàn)下述問題：

在遺傳算法的應用前期，一些超常個體可能會出現(xiàn)，其有較強的競爭力，那么選擇操控過程可能會依據(jù)概率選擇法來進行，進而對算法的全局優(yōu)化性能產(chǎn)生影響。

在遺傳算法的應用后期，當種群個體間的適應度值差異較小時，其會接近收斂狀態(tài)，這使得種群的優(yōu)化潛能被降低，從而得到的算法最優(yōu)解可能是局部的。

因此，適應度函數(shù)是否合理選取，對算法的收斂速度及能否得到最優(yōu)解影響較大。

適應度函數(shù)需滿足如下條件：

fitness(f(x))為適應度函數(shù)；

fitness(f(x))是一個是非負的連續(xù)的實函數(shù)，對是否可導無要求；

fitness(f(x))內(nèi)的每個點與之相匹配的適應度值和染色體的好壞成反比；

fitness(f(x))函數(shù)不要復雜，簡單為好；

fitness(f(x))函數(shù)要滿足通用性，盡量參數(shù)少些。

所以我們給出適應度函數(shù)的定義：

當 β=1時，fitness(f(x))在[0.5，1]是線性的；當 β=0.5時，可使得在算法的后期，有效拉開最優(yōu)解附近點的適應度值，可以讓我們更有效地做出選擇。當β=1.5時，可使得在算法的早期，有效拉近最優(yōu)解附近點的適應度值，這樣算法就可以較快搜索到最優(yōu)解區(qū)域。

對于m，將其調(diào)小，就可使fitness(f(x))函數(shù)的曲線變陡，將其調(diào)大，則可使fitness(f(x))函數(shù)的曲線變緩。這里，可以將n設為當代的最小值，它隨遺傳算法的進化而改變。

(3)變異算子的改進

在遺傳算法搜索最優(yōu)解的質(zhì)量和收斂性方面，變異和交叉算子起到了決定性的作用。通常，遺傳算法中交叉概率的選取很盲目，變異算子在尋優(yōu)過程中，可以有效阻止過早的收斂。這里，我們對一些基因進行變異操作。

在當代群體中，對個體適應度較小的部分基因（約占90%左右），首先優(yōu)化變量，然后再迭代計算，隨著迭代數(shù)目的增加，每次得到的值也不停地發(fā)生改變，逐漸接近最優(yōu)解。

變異操作的改進，能夠產(chǎn)生比另外10%適應度基因更好的基因，這樣算法的搜索解空間變小，尋優(yōu)速度變快，進而解決了原來遺傳算法的早熟問題和易陷入局部最優(yōu)解的問題，且遺傳算法的進化代數(shù)也可相應減少，更早得到最優(yōu)解。

3.3 智能排課改進遺傳算法流程

智能排課改進遺傳算法流程圖如圖1所示。

圖1 智能排課改進遺傳算法流程

3.4 算法的實現(xiàn)與分析

通過對以上遺傳算法的改進，我們將其應用到智能排課問題上，實驗使用Matlab R2010對使用遺傳算法TGA和改進后的遺傳算法IGA進行編程，在內(nèi)存4.0GB，CPU 3.8GHz的電腦上運行。以某高校信息工程學院2016-2017學年下學期的排課數(shù)據(jù)作為測試，種群數(shù)設為120，實驗考察算法的平均運行時間及算法較優(yōu)解出現(xiàn)的次數(shù)這兩個指標。

實驗結(jié)果：

在排課方案應用兩種算法，假設我們采用同樣的方法確定兩種算法的適應度函數(shù)，設迭代的次數(shù)分別為60，120，180，240，300，330，360，每次進行60次進行測試，記錄運行結(jié)果，如圖2、圖3所示。

圖2 TGA和IGA迭代數(shù)目與平均較優(yōu)解個數(shù)

圖3TGA和IGA迭代數(shù)目與平均運行時間

這里我們首先從出現(xiàn)較優(yōu)解的數(shù)目分析，當?shù)鷶?shù)目逐漸增加時，IGA和TGA兩種算法出現(xiàn)較優(yōu)解的數(shù)目都是逐漸趨于穩(wěn)定的，但當我們固定迭代次數(shù)，IGA明顯優(yōu)于TGA，在數(shù)據(jù)上看，出現(xiàn)較優(yōu)解的個數(shù)IGA要高出TGA兩倍多。其次，我們來分析算法的收斂速度，當TGA出現(xiàn)較優(yōu)解達到平穩(wěn)時，所需時間較多，而IGA出現(xiàn)較優(yōu)解趨于平穩(wěn)時，所需時間較少，由此，對改進遺傳算法的收斂速度比遺傳算法的收斂速度明顯高很多。

通過上述分析，本文中采用的IGA改進遺傳算法具有收斂速度較快、易趨于全局最優(yōu)解等特點。這源于：其一，IGA適應度函數(shù)的改進；其二，初始種群的均勻化改進，使得IGA的初始種群比TGA質(zhì)量優(yōu)秀；其三，IGA變異算子的改進及優(yōu)化操作有效加速了后代個體的收斂性。

4 總結(jié)

高校的排課問題涉及較多因素，受很多條件的約束，是一個典型的組合優(yōu)化問題。而很多高校的排課系統(tǒng)僅僅針對解決本校的排課問題，希望本文的改進算法能夠為高校的智能排課問題提供一種新的思路。

[1]潘以鋒．高校智能排課系統(tǒng)的算法[J]．上海師范大學學報(自然科學版)，2006，35(5)：31-37．

[2]宗薇．高校智能排課系統(tǒng)算法的研究與實現(xiàn)[J]．計算機仿真，2011(12)，28(12)：389-392．

[3]于標．排課問題的一種近似算法[J]．揚州職業(yè)大學學報，2001，5(1)：30-34．

[4]張晶，李廣軍，徐娟．智能排課算法綜述[J]．西南民族大學學報(自然科學版)，2009，19(3)：38-41．