基于遺傳算法排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

基于遺傳算法排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)【摘要】排課任務(wù)是教務(wù)管理中是比較煩瑣的一項(xiàng)，該系統(tǒng)可以通過使用遺傳算法，對(duì)課表進(jìn)行優(yōu)化。文章就遺傳算法排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)進(jìn)行了闡述?！娟P(guān)鍵詞】時(shí)間表；排課；遺傳算法；適應(yīng)度函數(shù)課程表問題又稱時(shí)間表問題，是一個(gè)多因素的整體優(yōu)化問題。1975年，S.Even等人論證了課表問題是NP完全類問題。由于課程表問題所涉及的信息較多，并且求解課程表問題最優(yōu)解的時(shí)間復(fù)雜性是課程表規(guī)模的指數(shù)級(jí)，所以一般采用求近似最優(yōu)解的算法。在現(xiàn)實(shí)生活中，人們一般也只是要一個(gè)滿足各種條件的近似最優(yōu)解，或者說“滿意解”，而不一定非要最優(yōu)解不可。因此，對(duì)于課程表問題，關(guān)鍵不是如何找到最優(yōu)解，而是如何提高解的滿意度。遺傳算法是John.H.Holland根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法，它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則和搜索算法。它從一個(gè)種群開始，利用選擇、交叉、變異等遺傳算子對(duì)種群進(jìn)行不斷進(jìn)化，最后得到全局最優(yōu)解或近似最優(yōu)解。根據(jù)其算法特點(diǎn)，遺傳算法非常適合于排課表問題。一、問題描述考查課表的約束條件，最基本的要求無外乎這樣幾個(gè)：（一）每個(gè)班級(jí)在同一時(shí)間只能上一門課；（二）每個(gè)普通教室和實(shí)驗(yàn)室在同一時(shí)間只能容納一個(gè)班上課，大教室和操場(chǎng)可以容納其容量允許的班級(jí)數(shù)上課；（三）每個(gè)教師在同一時(shí)間只能在一個(gè)地點(diǎn)上課。以上約束，稱為硬約束，因?yàn)椴蝗绱?，課表是不可行的。還有一些約束如：某個(gè)教師希望或不希望在某個(gè)時(shí)段上課；自習(xí)課和體育課最好不排每天的一二節(jié)課；同一門課在一周內(nèi)的分布盡可能均勻等，這些要求稱為軟約束，因?yàn)樗鼈兓蛘呖梢酝ㄟ^排課以外的方法，如變更其他事務(wù)的日程安排等加以解決；或者只能盡可能滿足，而不可能全部滿足。滿足硬約束的課表是合法的，但卻不一定是令人滿意的。那么如何提高一個(gè)課表的滿意度呢？可以請(qǐng)各個(gè)教師填一張“時(shí)段偏好”表，在每個(gè)上課時(shí)段上標(biāo)上相應(yīng)的數(shù)值，以確定他希望或不希望在某個(gè)時(shí)段上課――0表示不希望，1表示無所謂，2表示希望，3表示強(qiáng)烈希望。并且每個(gè)教師根據(jù)職稱，或職務(wù)，或所上課程重要性的不同確定優(yōu)先級(jí)：1，2，3級(jí)逐級(jí)遞增，這樣一張課表的滿意度就很好計(jì)算了：每個(gè)上課時(shí)段所對(duì)應(yīng)的上課老師的“時(shí)段偏好”值乘以這個(gè)老師的優(yōu)先級(jí)的積的總和。另一個(gè)決定課表好壞的度量就是同一門課在一周內(nèi)的分布盡可能均勻，即課程的分散度。如果該課程一周只上一次，分散度設(shè)為1，如果一次以上，則可以將每次間隔的時(shí)段數(shù)相乘，因?yàn)榉植荚狡骄涑朔e就越大。將所有課程的分散度相加即總的課表的分散度。定義適應(yīng)度函數(shù)：適應(yīng)度＝滿意度＋分散度。二、數(shù)據(jù)庫設(shè)計(jì)本學(xué)期課程信息表中記載了每個(gè)課程的信息，每個(gè)記錄稱為一個(gè)“課元”，包括：課程編號(hào)、課程名稱、周課時(shí)、任課教師、開課班級(jí)、教室要求。班級(jí)信息表包括：班級(jí)編號(hào)、班級(jí)名稱、人數(shù)。教師信息表包括：教師編號(hào)、姓名、時(shí)段偏好、優(yōu)先級(jí)。教室信息表包括：教室編號(hào)、教室類型、可容納學(xué)生數(shù)、已排。已排字段用來記錄該教室已排的時(shí)段。在Ｃ＃中讀入這六張表到數(shù)據(jù)集（dataset）ds1，根據(jù)“本學(xué)期課程信息表”來填充“排課表”初始值：復(fù)制“課程編號(hào)”到排課表，并根據(jù)周課時(shí)確定復(fù)制次數(shù)，“上課時(shí)段”和“教室”均為null。排課表中每條記錄稱為一個(gè)“排課元”。三、遺傳算法（一）初始化根據(jù)班級(jí)信息表以及它與本學(xué)期課程信息表的關(guān)系，找到每個(gè)班的所有課元，再根據(jù)這些課元，以及本學(xué)期課程表和排課表之間的關(guān)系，找到這個(gè)班的所有排課元。假設(shè)每星期上5天課，每天2節(jié)連上，有3個(gè)時(shí)間段，則每星期有15個(gè)上課時(shí)間段。那么將這15個(gè)時(shí)間段隨機(jī)地分配給上述某個(gè)班的所有排課元，也就是排好了一個(gè)班的課表。一個(gè)班的“排課元”的數(shù)目一定是小于或等于15的。如果小于則有時(shí)段未排到，即是自習(xí)時(shí)間?？稍凇鞍嗉?jí)信息表”新建一個(gè)臨時(shí)字段“自習(xí)”，記錄這些自習(xí)時(shí)間。再來排教室。給每個(gè)班安排一個(gè)滿足人數(shù)要求的教室作為固定教室。一般的課程就在固定教室上，如果是語音課則排語音室，如果是體育課則安排操場(chǎng)，如果是實(shí)驗(yàn)課則排實(shí)驗(yàn)室。排的時(shí)候注意比較該教室的“已排”字段，如與已排時(shí)段有沖突，則更換時(shí)段。對(duì)每個(gè)班做上述工作，則排好了一張初始課表。這張初始課表肯定有很多“硬沖突”，必須消除。由于排課時(shí)已經(jīng)注意了教室的時(shí)段不能沖突，所以只要查看教師的時(shí)間有無沖突即可。根據(jù)教師信息表與本學(xué)期課程信息表的關(guān)系，得到每個(gè)教師的課元，再根據(jù)這些課元，以及本學(xué)期課程信息表與排課表的關(guān)系得到該教師的所有排課元。檢查這些排課元的時(shí)段，如有重復(fù)，則須調(diào)課：首先考慮與自習(xí)課調(diào)，班級(jí)信息表的“自習(xí)”字段記錄了該班的自習(xí)時(shí)段。如果這些自習(xí)時(shí)段都與該老師的上課時(shí)間有沖突，則考慮能否用大教室，查看該老師在該時(shí)段所上課程的教室要求能否用大教室，如能，統(tǒng)計(jì)該老師在該時(shí)段的上課班級(jí)的總?cè)藬?shù)，安排一個(gè)能容納這么多學(xué)生的大教室。如果大教室方案不能解決問題，則只能和同班的其他老師調(diào)換，但注意只能和未檢查過沖突的老師換，以免循環(huán)調(diào)換。（二）建立初始種群計(jì)算消除了硬沖突的課表的適應(yīng)度函數(shù)，記錄在數(shù)組中。將該排課表考貝到新數(shù)據(jù)集ds2?？截愡^來的這個(gè)排課表即一個(gè)“染色體”。重復(fù)上述過程，直至染色體數(shù)目達(dá)到種群規(guī)模。（三）遺傳操作對(duì)ds2中的每張表做如下操作：1.選擇。采用“隨機(jī)競(jìng)爭(zhēng)法”。隨機(jī)選取兩張表，比較它們的適應(yīng)度，刪除適應(yīng)度小的表，復(fù)制適應(yīng)度大的表替換它。2.變異。設(shè)變異概率為Ｐm，隨機(jī)產(chǎn)生一個(gè)（0，1）范圍內(nèi)的數(shù)，如果小于Ｐm，才進(jìn)行變異操作。隨機(jī)選取兩天，讓這兩天的時(shí)段互換。這樣做的好處是不用糾錯(cuò)。3.交叉。類似地，設(shè)交叉概率為Pc，隨機(jī)產(chǎn)生一個(gè)（0，1）范圍內(nèi)的數(shù)，如果小于Ｐc，才進(jìn)行交叉操作。這里采用“單點(diǎn)交叉”。隨機(jī)選兩張表，再隨機(jī)選取一個(gè)序號(hào)，讓這兩張表中這個(gè)序號(hào)的記錄的“上課時(shí)段”值互換?；Q后這兩張表都要糾錯(cuò)，消除硬沖突。過程仿初始化時(shí)的消除沖突過程。只是要注意，如果調(diào)換的排課元涉及到大教室，須換回所在班的固定教室。重復(fù)該過程，注意每一步操作后都要更新適應(yīng)度數(shù)組，使數(shù)組值與表一致。迭代500代后，選取最大適應(yīng)度的表傳回ds1排課表。四、結(jié)論以某高職院的實(shí)際數(shù)據(jù)進(jìn)行上述操作，并記錄每一代的最大適應(yīng)度值。繪成圖表如下：

基于遺傳算法的高職院校排課系統(tǒng)的研究與實(shí)踐傅亞莉（1.江蘇無錫科技職業(yè)學(xué)院，江蘇無錫214028；2.江南大學(xué)，江蘇無錫214122）摘要：排課問題已經(jīng)被證明是一個(gè)NP完全問題，遺傳算法是一種隨機(jī)搜索算法,非常適合于解決NP問題。本文通過遺傳算法解決排課問題,從遺傳算法標(biāo)準(zhǔn)設(shè)計(jì)流程的角度分析了排課問題的基因編碼、初始化種群、確定適應(yīng)度函數(shù)、設(shè)計(jì)各遺傳算子等問題，最后形成排課的整體優(yōu)化算法。關(guān)鍵詞：遺傳算法；排課系統(tǒng)；基因編碼；適應(yīng)度函數(shù)中圖分類號(hào)：G718.5文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1008-7508（2010）011-0106-02無錫科技職業(yè)學(xué)院自2003年建院招生以來，逐年擴(kuò)大招生規(guī)模。學(xué)生人數(shù)的增加，使得各院系開課的班級(jí)越來越多；專業(yè)設(shè)置的增多，使得開設(shè)的課程名目繁多，然而教室資源的稀缺、教師要求的繁瑣等情況，使得我院教務(wù)部門的排課問題變得越來越復(fù)雜。高職院校的排課問題是根據(jù)各專業(yè)的教學(xué)計(jì)劃，匯總出需開設(shè)的課程，在給定教師資源、教室資源前提下，合理安排班級(jí)課表滿足教學(xué)要求的問題。遺傳算法是受自然選擇和進(jìn)化機(jī)制啟發(fā)而發(fā)展起來的一種隨機(jī)搜索算法，具有良好的并行性、通用性、穩(wěn)定性。遺傳算法通過選擇、交叉、變異等遺傳算子的作用對(duì)可行解進(jìn)行分析，使得種群不斷進(jìn)化，從而得到最優(yōu)解，因此遺傳算法是一種非常有效的解決排課問題的方法。一、排課的約束條件排課問題是一個(gè)帶有約束的多目標(biāo)組合優(yōu)化問題。①多目標(biāo)是指排課方案的解有多種，有約束的則是指排課過程中有一定約束條件限制。約束條件主要是指沖突，避免沖突是排課問題中要解決的核心問題，只有在所有排課方案全部不發(fā)生沖突的基礎(chǔ)上，才能保證整個(gè)教學(xué)計(jì)劃合理正常進(jìn)行，使得全校的教學(xué)工作能夠井然有序。根據(jù)排課的工作實(shí)際，我院在排課過程中的約束條件主要體現(xiàn)在以下幾個(gè)方面：(1)相同的教室在同一時(shí)間不能上兩門不同的課程；(2)相同的教師在同一時(shí)間不能在兩個(gè)教室上課；(3)相同的學(xué)生在同一時(shí)間不能上兩門不同的課程；(4)上課班級(jí)的總?cè)藬?shù)必須小于所安排的教室座位數(shù)。另外，為保證充分發(fā)揮各資源的優(yōu)勢(shì)和提高教學(xué)質(zhì)量，在排課過程中還需考慮一些盡可能優(yōu)化課表的排課規(guī)則：(1）相同班級(jí)同一門課程上課時(shí)間有間隔；(2）實(shí)踐類、體育類課程盡量安排在下午；(3）對(duì)外聘教師等教師的特殊上課時(shí)間要求優(yōu)先排課；(4)理實(shí)一體化課程需考慮四節(jié)連排的課程優(yōu)先排課；(5)公共選修或公共類等涉及面廣的課程需優(yōu)先排課，周學(xué)時(shí)多的課程優(yōu)先排課；(6)對(duì)于一些指定了教學(xué)區(qū)、不規(guī)則周次的特殊課程需要進(jìn)行合理安排。遺傳算法中根據(jù)約束條件和相關(guān)規(guī)則設(shè)定適應(yīng)度函數(shù)，并計(jì)算出相應(yīng)的適應(yīng)度值，借此檢查是否違反約束條件，如果沒有違反，則表明是可行解，否則，就是不可行解。二、遺傳算法的設(shè)計(jì)遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程求解復(fù)雜的優(yōu)化問題。②遺傳算法通過隨機(jī)選擇、交叉和變異操作，使群體不斷進(jìn)化，最后搜索到問題的最優(yōu)解。③遺傳算法具有超群的并行搜索能力，以及解決優(yōu)化問題的高度智能性。標(biāo)準(zhǔn)遺傳算法基本流程如下：〖BG(〗〖BHDWG65mm,WK50mmW〗〖BG)W〗1、基因編碼編碼就是在遺傳算法中把一個(gè)問題的可行解從其求解空間轉(zhuǎn)換到能處理的搜索空間的轉(zhuǎn)換方法。編碼方法決定了個(gè)體的染色體排列形式，也決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算。排課過程中主要是將班級(jí)、教師、課程、上課時(shí)間和教室這5個(gè)元素進(jìn)行安排，形成合理的課表。本院在課表安排過程中，每周上五天課，每天上8節(jié)課，課程采用2節(jié)連排方式，因此每2小節(jié)為1個(gè)時(shí)間段，每周共計(jì)4*5=20個(gè)時(shí)間段?？梢圆捎脤?shí)數(shù)編碼方法對(duì)每條染色體編碼，結(jié)構(gòu)如下：班級(jí)號(hào)，教師號(hào)，課程號(hào)，上課時(shí)間，教室號(hào)2、初始化種群編碼之后的任務(wù)是初始種群的設(shè)定，并以此為起點(diǎn)一代代進(jìn)化直到按進(jìn)化停止準(zhǔn)則終止進(jìn)化過程，得到最后一代群體。排課系統(tǒng)的初始化種群是先由計(jì)算機(jī)隨機(jī)生成一定數(shù)目的排課方案。對(duì)每一個(gè)班級(jí)而言，是將隨機(jī)產(chǎn)生的班級(jí)-教師-課程-時(shí)間-教室編碼，從中挑出好的不重復(fù)的個(gè)體填到數(shù)組，這樣就產(chǎn)生了一個(gè)班級(jí)的初始課程表。按班級(jí)的多少，產(chǎn)生一定數(shù)量的初始表，構(gòu)成初始種群。3、選擇適應(yīng)函數(shù)適應(yīng)度值確定了群體中每個(gè)個(gè)體的好壞程度，遺傳算法在進(jìn)化中是以每個(gè)個(gè)體的適應(yīng)度值為依據(jù)來選取下一代種群的，因此適應(yīng)度函數(shù)設(shè)定至關(guān)重要，會(huì)直接影響到遺傳算法的收斂速度和能否找到較優(yōu)解。根據(jù)排課問題的約束條件設(shè)置適應(yīng)函數(shù)，可綜合考慮排課沖突檢查、課程時(shí)間間隔、課程理想時(shí)段、教師上課要求等約束條件進(jìn)行設(shè)置。如果一個(gè)排課方案發(fā)生沖突，代表該課表不是可行解，則此時(shí)的適應(yīng)度為0。這樣，這個(gè)染色體在遺傳操作中就會(huì)被淘汰掉。同一班級(jí)相同課程時(shí)間間隔長，則適應(yīng)度值高，否則適應(yīng)度值低。專業(yè)類課程安排在上午上課，實(shí)踐類課程安排在下午上課的適應(yīng)度值高，否則適應(yīng)度值低。滿足教師上課地點(diǎn)、時(shí)間要求的則適應(yīng)度值高，否則適應(yīng)度值低。因此，適應(yīng)度函數(shù)可考慮設(shè)定如下：Fn=Y*(x1*K+x2*S+x3*J)Y為沖突檢查結(jié)果，檢查不沖突則值為1，沖突則值為0。K,S,J分別表示課表優(yōu)化中課程時(shí)間間隔、課程理想時(shí)段、教師上課要求、教室的有效利用等期望值。這里x1、x2和x3分別代表各期望值在總期望值中的權(quán)重。權(quán)重?cái)?shù)值可以根據(jù)學(xué)院實(shí)際需求，由排課人員自行設(shè)定，其中x1+x2+x3=1。通過適應(yīng)度函數(shù)的計(jì)算，如果一個(gè)排課方案適應(yīng)度值較高，則該排課方案相比而言較優(yōu)，則該染色體會(huì)遺傳保留下來。4、遺傳算子的設(shè)計(jì)（1）選擇選擇遺傳是用來確定重組或者交叉?zhèn)€體,以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。在進(jìn)行適應(yīng)度值計(jì)算之后，從種群中選擇出適應(yīng)度較高的個(gè)體,為染色體的交叉和變異做準(zhǔn)備。選擇時(shí)可采用輪盤賭選擇法，將適應(yīng)度值按比例轉(zhuǎn)化為選中概率，然后模擬輪盤賭操作，隨機(jī)生成若干個(gè)0至1之間的隨機(jī)數(shù)，與之前計(jì)算出的每個(gè)個(gè)體的概率進(jìn)行比較，確定該個(gè)體是否被遺傳到下一代種群中。一般適應(yīng)度高的個(gè)體被選中的概率大，適應(yīng)度值低的個(gè)體被淘汰的可能性大。（2）交叉交叉運(yùn)算是遺傳算法區(qū)別于其它算法的重要特征，它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。常用的交叉方法有單點(diǎn)交叉、多點(diǎn)交叉等方法，本系統(tǒng)采用的是多點(diǎn)交叉。在進(jìn)行交叉前，將眾多排課方案按照“班級(jí)-教師-課程-時(shí)間-教室”的順序排列下去，在交叉過程中，根據(jù)選擇操作的結(jié)果選取兩條染色體作為父?jìng)€(gè)體，只需交叉對(duì)應(yīng)班級(jí)的上課時(shí)間和上課教室即可得到新的染色體。（3）變異變異運(yùn)算是指將個(gè)體染色體編碼串中的某些基因值用其它等位基因來替換，從而形成一個(gè)新的個(gè)體。變異操作是為避免過早收斂，在進(jìn)化過程中加入有新遺傳基因的個(gè)體，使搜索能在盡可能大的空間中進(jìn)行，使之獲得最優(yōu)解的可能性大大加強(qiáng)。排課系統(tǒng)的變異算法主要為：在種群中隨機(jī)選取個(gè)體的時(shí)間或教室進(jìn)行改變，但必須檢查不能沖突，如發(fā)生沖突則再次變異。變異遺傳能夠較好地保持種群的多樣性和規(guī)模性。5、終止準(zhǔn)則通過上述各類遺傳操作，各代種群的優(yōu)良基因逐漸累積，種群平均適應(yīng)度值和最優(yōu)個(gè)體適應(yīng)度值不斷上升，求解的結(jié)果與目標(biāo)值接近，此時(shí)需考慮利用終止準(zhǔn)則使迭代過程趨于收斂。排課系統(tǒng)中終止準(zhǔn)則可考慮使用遺傳算法中常用的終止準(zhǔn)則的設(shè)計(jì)之一來實(shí)現(xiàn)：（1）排課問題解的種群中個(gè)體的最大適應(yīng)度超過預(yù)先設(shè)定值，則停止排課。（2）排課問題解的種群中個(gè)體的平均適應(yīng)度超過預(yù)先設(shè)定值，則停止排課。（3）排課過程中，設(shè)定的遺傳的世代數(shù)超過預(yù)先設(shè)定值，則停止排