學(xué)分制模式下基于遺傳算法的排課系統(tǒng)的設(shè)計(jì)

33頁共計(jì)20913字

摘 要
排課問題是一個(gè)多約束、多目標(biāo)的優(yōu)化問題，其實(shí)質(zhì)是時(shí)間表問題，已經(jīng)被確認(rèn)為NP完全問題。遺傳算法作為一種隨機(jī)搜索算法，利用群體搜索技術(shù)，對(duì)解決NP問題非常有效。
本文將遺傳算法應(yīng)用于學(xué)分制模式下的排課系統(tǒng)中，通過對(duì)排課因素和約束條件的深入分析，制定了排課問題的優(yōu)化目標(biāo)，設(shè)計(jì)出了適合于遺傳操作的編碼模型，給出了合理的適應(yīng)度值的計(jì)算方法。通過對(duì)初始種群進(jìn)行選擇、交叉、變異等過程不斷進(jìn)化，取得了優(yōu)化的課表。
在排課系統(tǒng)設(shè)計(jì)中，本文采用了面向?qū)ο蟮姆椒?，設(shè)計(jì)了課表安排中的教室調(diào)度算法、基因填充算法、沖突檢測(cè)算法，使得排課得以實(shí)現(xiàn)。利用真實(shí)的數(shù)據(jù)進(jìn)行系統(tǒng)測(cè)試，并分析了各參數(shù)對(duì)遺傳操作及結(jié)果的影響。
目 錄
1 引言 1
2 遺傳算法 2
2.1 遺傳算法研究的內(nèi)容 3
2.2 遺傳算法的基本術(shù)語 4
2.3 遺傳算法的基本思想 5
2.4 遺傳算法的基本操作 6
3 排課系統(tǒng)的需求分析 8
3.1 排課系統(tǒng)的業(yè)務(wù)流程分析 8
3.2 排課因素分析 10
3.3 排課的約束條件 11
4 基于遺傳算法的排課算法的描述 12
4.1 排課問題的目標(biāo)分析 12
4.2 排課系統(tǒng)中的基本算法 15
4.2.1 排課算法的面向?qū)ο蟮膽?yīng)用 15
4.2.2 教室調(diào)度算法 17
4.2.3 基因初始化算法 18
4.2.4 沖突檢測(cè)算法 19
4.3 排課問題中遺傳算法的設(shè)計(jì) 19
4.3.1 遺傳算法的編碼 19
4.3.2 初始種群的產(chǎn)生 20
4.3.3 遺傳操作的設(shè)計(jì) 20
4.3.4 適應(yīng)度函數(shù)的設(shè)計(jì) 22
5 實(shí)驗(yàn)及結(jié)果分析 22
5.1 排課系統(tǒng)開發(fā)環(huán)境 22
5.2 參數(shù)設(shè)置對(duì)排課效率的影響 23
5.3 結(jié)果分析 26
6 總結(jié)與展望 27
參考文獻(xiàn) 29

關(guān)鍵字：學(xué)分制模式；排課系統(tǒng)；遺傳算法；多目標(biāo)優(yōu)化
參考文獻(xiàn)
[1] 薛冬梅. 充分利用資源科學(xué)合理排課. 中原工學(xué)院學(xué)報(bào), 2002, 13(7): 78-80
[2] Gotlieb. The Construction of Class-Teacher Time Tables. Proceeding IFIP Congress, 1963: 73-74
[3] 周明, 孫樹棟. 遺傳算法原理及其應(yīng)用. 長(zhǎng)沙: 國(guó)防工業(yè)出版社, 2002
[4] 吳金榮. 求解課表問題的分支定界法. 運(yùn)籌與管理, 2002, 11(1): 17-22
[5] 何永太. 二部圖再排課系統(tǒng)設(shè)計(jì)中的應(yīng)用. 安徽水利水電職業(yè)技術(shù)學(xué)院學(xué)報(bào), 2003, 9(3): 45-77
[6] 胡順仁, 鄧毅, 王錚. 基于高校排課系統(tǒng)中的圖論問題研究. 計(jì)算機(jī)工程與應(yīng)用, 2002, 10(4): 221-223
[7] 胡小兵, 魯宏偉. 基于模糊專家系統(tǒng)的排課關(guān)鍵技術(shù)研究. 長(zhǎng)沙電力學(xué)院學(xué)報(bào)(自然科學(xué)版), 2001, 16(4): 40-42
[8] 黃干平, 姚自珍, 張軼靜. 使用模擬退火算法求解排課問題. 武漢大學(xué)學(xué)報(bào)(自然科學(xué)版), 2000, 46(5): 55-59
[9] 彭超. 禁忌搜索求解排課問題的研究.
[10] 張林. 基于蟻群算法的排課系統(tǒng)研究與設(shè)計(jì). [碩士論文]. 合肥: 安徽大學(xué), 2005
[11] 鄭立平, 郝忠孝. 遺傳算法理論綜述. 計(jì)算機(jī)工程與應(yīng)用, 2003, 21: 50-54
[12] 王志美, 陳傳仁. 遺傳算法理論及其應(yīng)用發(fā)展. 內(nèi)蒙古石油化工, 2006, 9: 44-45
[13] 王小平, 曹立明. 遺傳算法：理論、應(yīng)用及軟件實(shí)現(xiàn). 西安: 西安交通大學(xué)出版社, 2002
[14] 薛華成. 管理信息系統(tǒng). 北京: 清華大學(xué)出版社, 2003
[15] 蔡淑琴. 管理信息系統(tǒng). 北京: 科學(xué)出版社, 2004
[16] 鄒躍. 人性化排課算法的構(gòu)造與設(shè)計(jì). 重慶科技學(xué)院學(xué)報(bào), 2006, 8(4): 90-93
[17] 林志雄. 排課數(shù)學(xué)模型及其算法. 龍巖學(xué)院學(xué)報(bào), 2006, 24(6): 9-12
[18] 王昊亮, 李剛. Visual C#程序設(shè)計(jì)教程. 北京: 清華大學(xué)出版社, 2003
[19] (美) Jason Price, Mike Gunderloy. Visual C#從入門到精通. 北京: 電子工業(yè)出版社, 2003
[20] 薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論. 北京: 高等教育出版社, 2002
[21] 李律松, 陳少剛, 沈剛. Visual C# 數(shù)據(jù)庫高級(jí)教程. 北京: 清華大學(xué)出版社, 2005
[22] 王晟. Visual C#.NET 數(shù)據(jù)庫開發(fā)經(jīng)典案例解析. 北京: 清華大學(xué)出版社, 2005
[23] Chris Ullman, John Kauffman and etc. Beginning ASP.NET 1.1 with Visual C# .NET 2003. Wrox Press Ltd, 2004
[24] 何鵬飛, 王政. C#實(shí)用編程百例. 北京: 清華大學(xué)出版社, 2004