【正文】 遺傳代數(shù)、教室利用度權(quán)值、節(jié)次優(yōu)度權(quán)值、課程時間段分布均勻度權(quán)值、時間片利用度權(quán)值、課程日組合優(yōu)度權(quán)值。各參數(shù)的取值對各目標(biāo)收斂造成的影響，可以根據(jù)遺傳理論定性確定及通過實驗分析取得。在本文測試中，參數(shù)設(shè)置如表51所示。表51 實驗參數(shù)設(shè)置序號參數(shù)名稱取值及對目標(biāo)收斂的影響1種群規(guī)模取值較小時，目標(biāo)值波動大，不穩(wěn)定，不能反映優(yōu)化各個目標(biāo)。過大時，各目標(biāo)值雖然收斂，但收斂時間長，耗內(nèi)存，運行時間長。本文取2002遺傳代數(shù)取值過小，目標(biāo)并沒有收斂，各目標(biāo)沒有得到充分優(yōu)化，取值過大，各目標(biāo)早已收斂，只是在重復(fù)遺傳，且運行時間長。本文取13003交叉概率取值過小，收斂速度大大降低，收斂時間長；取值過大，目標(biāo)值波動較大，4變異概率取值過小，全局收斂速度緩慢；取值過大時，種群不穩(wěn)定，沒有收斂的趨勢。5教師利用度權(quán)值6節(jié)次優(yōu)度權(quán)值7課程時間段分布均勻度權(quán)值8時間片利用度權(quán)值9課程日組合優(yōu)度權(quán)值 (1) 種群規(guī)模對排課效率的影響本文分三次實驗，分別測試了種群規(guī)模為100、150、200時，遺傳效率的大小。我們設(shè)置一個參照值，當(dāng)種群中出現(xiàn)適應(yīng)值比參照值高的個體時，則結(jié)束遺傳操作，此時遺傳操作所用的時間為衡量遺傳效率的標(biāo)準(zhǔn)。每次實驗我們進(jìn)行5次測試，最終取平均值作為此次實驗的遺傳效率值。具體見表52。表52 種群規(guī)模對排課效率的影響(單位：秒)編號實驗一(100)實驗二(150)實驗三(200)12345平均值由上表可以看出，當(dāng)種群規(guī)模增大時，最優(yōu)個體達(dá)到一定的適應(yīng)度所需的時間越短，遺傳算法的效率越高。但是并不是說種群規(guī)模越大越好，種群越大，種群的交叉，變異所用的時間就越多。經(jīng)過多次測試，本文取種群規(guī)模為200。 (2) 交叉概率對排課效率的影響交叉操作是產(chǎn)生新個體的重要操作，交叉概率決定了交叉操作的頻率。交叉概率越大，則頻率越高。當(dāng)交叉頻率很高時，可以很快地收斂到最優(yōu)解區(qū)域。一般選擇較大的交叉概率，以盡量產(chǎn)生優(yōu)秀的個體。但交叉頻率過高時，可能造成種群早熟，得到局部最優(yōu)解。、遺傳效率的大小。結(jié)果如表53所示。表53 交叉概率對排課效率的影響(單位：秒)編號實驗一()實驗二()實驗三()12345平均值從表53可以看出，交叉概率越大，遺傳效率越高。排課問題在充分交叉的情況下，可明顯提高效率。 (3) 變異概率對排課效率的影響在自然界中，生物產(chǎn)生變異(基因突變)的概率是很小的，正是因為如此，種群在世代相傳。同樣，為了維持種群的穩(wěn)定性，遺傳操作中變異概率不能設(shè)置過大。但是當(dāng)變異概率設(shè)置過小，卻會導(dǎo)致全局搜索難于進(jìn)行，因為缺少變異，種群往往在局部搜索，很難跳出來。這就使得某些資源難以得到利用，這樣往往排不出課表或課表質(zhì)量較差。、遺傳效率的大小。表54 交叉概率對排課效率的影響(單位：秒)編號實驗一()實驗二()實驗三()12345平均值從表55可以看出，過低的變異概率導(dǎo)致遺傳效率較低，過大的變異概率導(dǎo)致種群的遺傳效率嚴(yán)重下降。(4) 遺傳代數(shù)對排課結(jié)果的影響遺傳代數(shù)決定遺傳操作的次數(shù)，遺傳代數(shù)越大，遺傳操作所用的時間相應(yīng)增加。如果遺傳代數(shù)過小，種群還沒有收斂到最優(yōu)解就結(jié)束。當(dāng)遺傳代數(shù)過高時，種群可能會出現(xiàn)大量同一個體，種群幾乎停止進(jìn)化，甚至可能出現(xiàn)退化。本文測試了遺傳代數(shù)為1000、1200、1300、1500時，所得出的最優(yōu)課表的適應(yīng)度值，如表55所示。表55 遺傳代數(shù)對排課結(jié)果的影響編號實驗一(1000)實驗二(1200)實驗三(1300)實驗四(1500)12345平均值從表55可以看出，遺傳代數(shù)并不是越大越好。本文取遺傳代數(shù)為1300。 結(jié)果分析根據(jù)表51的參數(shù)的設(shè)置，本文進(jìn)行了5次測試，結(jié)果如表56所示。表56 遺傳操作結(jié)果表編號初始種群最大適應(yīng)度值最優(yōu)課表適應(yīng)度值遺傳操作耗時12345平均值從表56可以看出，通過設(shè)計的排課算法對初始解進(jìn)行優(yōu)化，適應(yīng)度平均提高了9%，適應(yīng)度有明顯的進(jìn)化趨勢，說明本文設(shè)計的染色體編碼和適應(yīng)度函數(shù)能夠較好的反映排課的需求。與傳統(tǒng)的人工排課方式的比較如下：(1) 相似方面① 無沖突性指課程表必須滿足所有硬性約束。無論是人工編排的課程表還是排課系統(tǒng)自動編排的課程表都不存在沖突問題，即沒有同一時間一個教師上一門以上課程、一個班級同時上一門以上課程、一個教室同一時間上一門以上課程的沖突，且教室容量、類型，課程安排的校區(qū)都符合教學(xué)任務(wù)書的要求。無沖突性是一個課程表必須滿足的首要條件。② 課程的日組合優(yōu)度高周上課次數(shù)大于1的課在一周內(nèi)分散安排，不管是對于教師還是學(xué)生來說都是有必要的。教師在進(jìn)行每一節(jié)課的教學(xué)之前需要深入領(lǐng)會教學(xué)大綱的精神、仔細(xì)研究教材內(nèi)容、恰當(dāng)安排教學(xué)過程和認(rèn)真編寫教案。過于連續(xù)的課程安排會使得這些工作受到很大的影響，進(jìn)而影響到教師課堂講解。同樣，對于學(xué)生來說，每次教學(xué)內(nèi)容學(xué)習(xí)完畢后，學(xué)生需要時間來消化學(xué)習(xí)內(nèi)容，進(jìn)一步理解和鞏固所學(xué)知識。過于連續(xù)的課程安排會使學(xué)生疲于應(yīng)付新的知識，又由于進(jìn)度太快，前面知識掌握不牢，造成無法掌握新知識。另一方面，連續(xù)的課程安排之后是相對的空閑，這使學(xué)生對新學(xué)習(xí)的知識缺乏鞏固。因此，課程的日組合優(yōu)度是一個課程表優(yōu)劣的關(guān)鍵因素，這一點，不管是人工編排的課程表還是系統(tǒng)編排的課程表都具備了。③ 人性化根據(jù)老師的具體要求對課表進(jìn)行編排，體現(xiàn)排課過程中人性化的考慮。不管是人工排課還是排課系統(tǒng)排課，都會考慮老師的特殊要求。例如，在本文中，我們考慮了如果某時間段某老師不能上課，則該時間不給其安排課程。(2) 差異方面① 效率差異人工排課跟計算機系統(tǒng)排課最大的差異在于效率，在一個擁有上萬名學(xué)生，幾千門課程的學(xué)校，要想排出一個合理可行的課表，往往需要教務(wù)處工作人員忙碌十幾天甚至一個月。而利用計算機系統(tǒng)排課，在設(shè)置好相應(yīng)參數(shù)后，只需要幾分鐘最多幾小時就可以排出可行的優(yōu)化的課表。且減少了人力的消耗。② 時間安排對稱方面的差異人工排課時，對周上課次數(shù)大于1的課程的多次安排往往采用時間對稱的方式。如周學(xué)時為6的課程，安排在周一2節(jié)、周三4節(jié)、周五2節(jié)或周一4節(jié)、周三2節(jié)、周五2節(jié)。自動排課系統(tǒng)會盡量朝對稱方面優(yōu)化，但是結(jié)果往往會是周一的2節(jié)、周三4節(jié)、周五4節(jié)。③ 節(jié)次優(yōu)度方面的差異人工排課時，會盡量給課程安排較好的時間段，但是如果課程數(shù)目多，教學(xué)任務(wù)重時，排出一張可行的課表都相當(dāng)費時費力，如果再考慮節(jié)次優(yōu)度，情況將更加復(fù)雜。因此，人工排課中雖然會考慮課程的節(jié)次優(yōu)度，但最終排課時很難真正實施。計算機系統(tǒng)排課，在設(shè)置好節(jié)次優(yōu)度的參數(shù)后，在迭代過程中，會使課程逐漸安排到節(jié)次優(yōu)度高的時段上，而且不會費力。6 總結(jié)與展望(1) 對本文工作的總結(jié)排課問題的實質(zhì)是為教師，學(xué)生的教學(xué)活動合理的安排時間和教室，以保證教學(xué)計劃的順利進(jìn)行。排課工作在教務(wù)管理工作中處于十分重要的地位。本文實現(xiàn)了基于遺傳算法的排課問題解決方案。本文把編排課表分為兩步，首先根據(jù)硬性約束條件產(chǎn)生可行的排課方案，然后利用遺傳算法對排課方案進(jìn)行優(yōu)化，并得到最終的優(yōu)化的排課方案。主要成果有以下幾點：① 系統(tǒng)完整的分析了排課流程，排課問題涉及的因素，排課的約束條件及優(yōu)化目標(biāo)。② 根據(jù)排課問題的特點，設(shè)計了有利于遺傳操作的編碼模型，使排課問題易于解決。③ 根據(jù)排課問題的約束條件，設(shè)計了基因初始算法、教師調(diào)度算法、沖突檢測算法，并建立了合理的適應(yīng)度函數(shù)。最后本文利用真實的數(shù)據(jù)進(jìn)行測試，所得結(jié)果令人滿意。在教室利用度、節(jié)次優(yōu)度、課程時間段分布均勻度、時間片利用度、課程日組合優(yōu)度五個因素組成的目標(biāo)空間上進(jìn)行求解，結(jié)果比較理想。(2) 對進(jìn)一步研究的展望本文提出的基于遺傳算法的排課方案，在一定程度上可以滿足實際的需求。但是課表中蘊含著紛繁復(fù)雜的約束條件，想設(shè)計出一個滿足實際應(yīng)用的通用的排課算法，還需要做更多的分析和研究。為了完善并克服存在的問題，進(jìn)一步的研究工作主要在以下幾個方面：① 目前高校普遍存在多個校區(qū)，如何讓老師在兩次課之間盡量在同一校區(qū)上課，學(xué)生和老師的兩次課教室距離最優(yōu)，是減少教師和學(xué)生流動的關(guān)鍵。② 在排課時，如何保證每個學(xué)生每個學(xué)期的必修課在時間安排上一定不沖突，以保證學(xué)生都能按照教學(xué)計劃的要求選到必修課也是進(jìn)一步研究的一個重點。③ 本文所用的測試數(shù)據(jù)的規(guī)模偏小，不能獲得對算法和系統(tǒng)的客觀評價，下一步將針對完整的教學(xué)任務(wù)進(jìn)行測試。④ 應(yīng)用多種群的并行遺傳算法求解排課問題也是進(jìn)一步改進(jìn)排課效果的一個方向。盡管一個種群進(jìn)行遺傳已經(jīng)取得滿意結(jié)果，但如果利用多個種群同時進(jìn)遺傳操作，并在種群間進(jìn)行交叉，勢必可以更好地提高子代的適應(yīng)度，使遺傳操作更快的收斂。⑤ 進(jìn)一步改進(jìn)和完善系統(tǒng)設(shè)計的各個方面，包括界面設(shè)計、數(shù)據(jù)交換等，力爭使系統(tǒng)達(dá)到實際應(yīng)用的目標(biāo)。參考文獻(xiàn)[1] 薛冬梅. 充分利用資源科學(xué)合理排課. 中原工學(xué)院學(xué)報, 2002, 13(7): 7880[2] Gotlieb. The Construction of ClassTeacher Time Tables. Proceeding IFIP Congress, 1963: 7374[3] 周明, 孫樹棟. 遺傳算法原理及其應(yīng)用. 長沙: 國防工業(yè)出版社, 2002[4] 吳金榮. 求解課表問題的分支定界法. 運籌與管理, 2002, 11(1): 1722[5] 何永太. 二部圖再排課系統(tǒng)設(shè)計中的應(yīng)用. 安徽水利水電職業(yè)技術(shù)學(xué)院學(xué)報, 2003, 9(3): 4577[6] 胡順仁, 鄧毅, 王錚. 基于高校排課系統(tǒng)中的圖論問題研究. 計算機工程與應(yīng)用, 2002, 10(4): 221223[7] 胡小兵, 魯宏偉. 基于模糊專家系統(tǒng)的排課關(guān)鍵技術(shù)研究. 長沙電力學(xué)院學(xué)報(自然科學(xué)版), 2001, 16(4): 4042[8] 黃干平, 姚自珍, 張軼靜. 使用模擬退火算法求解排課問題. 武漢大學(xué)學(xué)報(自然科學(xué)版), 2000, 46(5): 5559[9] 彭超. 禁忌搜索求解排課問題的研究. [10] 張林. 基于蟻群算法的排課系統(tǒng)研究與設(shè)計. [碩士論文]. 合肥: 安徽大學(xué), 2005[11] 鄭立平, 郝忠孝. 遺傳算法理論綜述. 計算機工程與應(yīng)用, 2003, 21: 5054[12] 王志美, 陳傳仁. 遺傳算法理論及其應(yīng)用發(fā)展. 內(nèi)蒙古石油化工, 2006, 9: 4445[13] 王小平, 曹立明. 遺傳算法：理論、應(yīng)用及軟件實現(xiàn). 西安: 西安交通大學(xué)出版社, 2002[14] 薛華成. 管理信息系統(tǒng). 北京: 清華大學(xué)出版社, 2003 [15] 蔡淑琴. 管理信息系統(tǒng). 北京: 科學(xué)出版社, 2004[16] 鄒躍. 人性化排課算法的構(gòu)造與設(shè)計. 重慶科技學(xué)院學(xué)報, 2006, 8(4): 9093[17] 林志雄. 排課數(shù)學(xué)模型及其算法. 龍巖學(xué)院學(xué)報, 2006, 24(6): 912[18] 王昊亮, 李剛. Visual C程序設(shè)計教程. 北京: 清華大學(xué)出版社, 2003[19] (美) Jason Price, Mike Gunderloy. Visual C從入門到精通. 北京: 電子工業(yè)出版社, 2003[20] 薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論. 北京: 高等教育出版社, 2002[21] 李律松, 陳少剛, 沈剛. Visual C 數(shù)據(jù)庫高級教程. 北京: 清華大學(xué)出版社, 2005[22] 王晟. Visual C.NET 數(shù)據(jù)庫開發(fā)經(jīng)典案例解析. 北京: 清華大學(xué)出版社, 2005[23] Chris Ullman, John Kauffman and etc. Beginning with Visual C .NET 2003. Wrox Press Ltd, 2004[24] 何鵬飛, 王政. C實用編程百例. 北京: 清華大學(xué)出版社, 2004寧可累死在路上，也不能閑死在家里！寧可去碰壁，也不能面壁。是狼就要練好牙，是羊就要練好腿。什么是奮斗？奮斗就是每天很難，可一年一年卻越來越容易。不奮斗就是每天都很容易，可一年一年越來越難。能干的人，不在情緒上計較，只在做事上認(rèn)真；無能的人！不在做事上認(rèn)真，只在情緒上計較。拼一個春夏秋冬！贏一個無悔人生！早安！—————獻(xiàn)給所有努力的人.