學分制模式下基于遺傳算法的排課系統(tǒng)的設計.doc
約34頁DOC格式手機打開展開
學分制模式下基于遺傳算法的排課系統(tǒng)的設計,33頁共計20913字摘 要排課問題是一個多約束、多目標的優(yōu)化問題，其實質是時間表問題，已經(jīng)被確認為np完全問題。遺傳算法作為一種隨機搜索算法，利用群體搜索技術，對解決np問題非常有效。本文將遺傳算法應用于學分制模式下的排課系統(tǒng)中，通過對排課因素和約束條件的深入分析，制定了排課問...
內容介紹
此文檔由會員 bfxqt 發(fā)布
學分制模式下基于遺傳算法的排課系統(tǒng)的設計
33頁共計20913字
摘 要
排課問題是一個多約束、多目標的優(yōu)化問題，其實質是時間表問題，已經(jīng)被確認為NP完全問題。遺傳算法作為一種隨機搜索算法，利用群體搜索技術，對解決NP問題非常有效。
本文將遺傳算法應用于學分制模式下的排課系統(tǒng)中，通過對排課因素和約束條件的深入分析，制定了排課問題的優(yōu)化目標，設計出了適合于遺傳操作的編碼模型，給出了合理的適應度值的計算方法。通過對初始種群進行選擇、交叉、變異等過程不斷進化，取得了優(yōu)化的課表。
在排課系統(tǒng)設計中，本文采用了面向對象的方法，設計了課表安排中的教室調度算法、基因填充算法、沖突檢測算法，使得排課得以實現(xiàn)。利用真實的數(shù)據(jù)進行系統(tǒng)測試，并分析了各參數(shù)對遺傳操作及結果的影響。
目 錄
1 引言 1
2 遺傳算法 2
2.1 遺傳算法研究的內容 3
2.2 遺傳算法的基本術語 4
2.3 遺傳算法的基本思想 5
2.4 遺傳算法的基本操作 6
3 排課系統(tǒng)的需求分析 8
3.1 排課系統(tǒng)的業(yè)務流程分析 8
3.2 排課因素分析 10
3.3 排課的約束條件 11
4 基于遺傳算法的排課算法的描述 12
4.1 排課問題的目標分析 12
4.2 排課系統(tǒng)中的基本算法 15
4.2.1 排課算法的面向對象的應用 15
4.2.2 教室調度算法 17
4.2.3 基因初始化算法 18
4.2.4 沖突檢測算法 19
4.3 排課問題中遺傳算法的設計 19
4.3.1 遺傳算法的編碼 19
4.3.2 初始種群的產生 20
4.3.3 遺傳操作的設計 20
4.3.4 適應度函數(shù)的設計 22
5 實驗及結果分析 22
5.1 排課系統(tǒng)開發(fā)環(huán)境 22
5.2 參數(shù)設置對排課效率的影響 23
5.3 結果分析 26
6 總結與展望 27
參考文獻 29
關鍵字：學分制模式；排課系統(tǒng)；遺傳算法；多目標優(yōu)化
參考文獻
[1] 薛冬梅. 充分利用資源科學合理排課. 中原工學院學報, 2002, 13(7): 78-80
[2] Gotlieb. The Construction of Class-Teacher Time Tables. Proceeding IFIP Congress, 1963: 73-74
[3] 周明, 孫樹棟. 遺傳算法原理及其應用. 長沙: 國防工業(yè)出版社, 2002
[4] 吳金榮. 求解課表問題的分支定界法. 運籌與管理, 2002, 11(1): 17-22
[5] 何永太. 二部圖再排課系統(tǒng)設計中的應用. 安徽水利水電職業(yè)技術學院學報, 2003, 9(3): 45-77
[6] 胡順仁, 鄧毅, 王錚. 基于高校排課系統(tǒng)中的圖論問題研究. 計算機工程與應用, 2002, 10(4): 221-223
[7] 胡小兵, 魯宏偉. 基于模糊專家系統(tǒng)的排課關鍵技術研究. 長沙電力學院學報(自然科學版), 2001, 16(4): 40-42
[8] 黃干平, 姚自珍, 張軼靜. 使用模擬退火算法求解排課問題. 武漢大學學報(自然科學版), 2000, 46(5): 55-59
[9] 彭超. 禁忌搜索求解排課問題的研究.
[10] 張林. 基于蟻群算法的排課系統(tǒng)研究與設計. [碩士論文]. 合肥: 安徽大學, 2005
[11] 鄭立平, 郝忠孝. 遺傳算法理論綜述. 計算機工程與應用, 2003, 21: 50-54
[12] 王志美, 陳傳仁. 遺傳算法理論及其應用發(fā)展. 內蒙古石油化工, 2006, 9: 44-45
[13] 王小平, 曹立明. 遺傳算法：理論、應用及軟件實現(xiàn). 西安: 西安交通大學出版社, 2002
[14] 薛華成. 管理信息系統(tǒng). 北京: 清華大學出版社, 2003
[15] 蔡淑琴. 管理信息系統(tǒng). 北京: 科學出版社, 2004
[16] 鄒躍. 人性化排課算法的構造與設計. 重慶科技學院學報, 2006, 8(4): 90-93
[17] 林志雄. 排課數(shù)學模型及其算法. 龍巖學院學報, 2006, 24(6): 9-12
[18] 王昊亮, 李剛. Visual C#程序設計教程. 北京: 清華大學出版社, 2003
[19] (美) Jason Price, Mike Gunderloy. Visual C#從入門到精通. 北京: 電子工業(yè)出版社, 2003
[20] 薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論. 北京: 高等教育出版社, 2002
[21] 李律松, 陳少剛, 沈剛. Visual C# 數(shù)據(jù)庫高級教程. 北京: 清華大學出版社, 2005
[22] 王晟. Visual C#.NET 數(shù)據(jù)庫開發(fā)經(jīng)典案例解析. 北京: 清華大學出版社, 2005
[23] Chris Ullman, John Kauffman and etc. Beginning ASP.NET 1.1 with Visual C# .NET 2003. Wrox Press Ltd, 2004
[24] 何鵬飛, 王政. C#實用編程百例. 北京: 清華大學出版社, 2004
33頁共計20913字
摘 要
排課問題是一個多約束、多目標的優(yōu)化問題，其實質是時間表問題，已經(jīng)被確認為NP完全問題。遺傳算法作為一種隨機搜索算法，利用群體搜索技術，對解決NP問題非常有效。
本文將遺傳算法應用于學分制模式下的排課系統(tǒng)中，通過對排課因素和約束條件的深入分析，制定了排課問題的優(yōu)化目標，設計出了適合于遺傳操作的編碼模型，給出了合理的適應度值的計算方法。通過對初始種群進行選擇、交叉、變異等過程不斷進化，取得了優(yōu)化的課表。
在排課系統(tǒng)設計中，本文采用了面向對象的方法，設計了課表安排中的教室調度算法、基因填充算法、沖突檢測算法，使得排課得以實現(xiàn)。利用真實的數(shù)據(jù)進行系統(tǒng)測試，并分析了各參數(shù)對遺傳操作及結果的影響。
目 錄
1 引言 1
2 遺傳算法 2
2.1 遺傳算法研究的內容 3
2.2 遺傳算法的基本術語 4
2.3 遺傳算法的基本思想 5
2.4 遺傳算法的基本操作 6
3 排課系統(tǒng)的需求分析 8
3.1 排課系統(tǒng)的業(yè)務流程分析 8
3.2 排課因素分析 10
3.3 排課的約束條件 11
4 基于遺傳算法的排課算法的描述 12
4.1 排課問題的目標分析 12
4.2 排課系統(tǒng)中的基本算法 15
4.2.1 排課算法的面向對象的應用 15
4.2.2 教室調度算法 17
4.2.3 基因初始化算法 18
4.2.4 沖突檢測算法 19
4.3 排課問題中遺傳算法的設計 19
4.3.1 遺傳算法的編碼 19
4.3.2 初始種群的產生 20
4.3.3 遺傳操作的設計 20
4.3.4 適應度函數(shù)的設計 22
5 實驗及結果分析 22
5.1 排課系統(tǒng)開發(fā)環(huán)境 22
5.2 參數(shù)設置對排課效率的影響 23
5.3 結果分析 26
6 總結與展望 27
參考文獻 29
關鍵字：學分制模式；排課系統(tǒng)；遺傳算法；多目標優(yōu)化
參考文獻
[1] 薛冬梅. 充分利用資源科學合理排課. 中原工學院學報, 2002, 13(7): 78-80
[2] Gotlieb. The Construction of Class-Teacher Time Tables. Proceeding IFIP Congress, 1963: 73-74
[3] 周明, 孫樹棟. 遺傳算法原理及其應用. 長沙: 國防工業(yè)出版社, 2002
[4] 吳金榮. 求解課表問題的分支定界法. 運籌與管理, 2002, 11(1): 17-22
[5] 何永太. 二部圖再排課系統(tǒng)設計中的應用. 安徽水利水電職業(yè)技術學院學報, 2003, 9(3): 45-77
[6] 胡順仁, 鄧毅, 王錚. 基于高校排課系統(tǒng)中的圖論問題研究. 計算機工程與應用, 2002, 10(4): 221-223
[7] 胡小兵, 魯宏偉. 基于模糊專家系統(tǒng)的排課關鍵技術研究. 長沙電力學院學報(自然科學版), 2001, 16(4): 40-42
[8] 黃干平, 姚自珍, 張軼靜. 使用模擬退火算法求解排課問題. 武漢大學學報(自然科學版), 2000, 46(5): 55-59
[9] 彭超. 禁忌搜索求解排課問題的研究.
[10] 張林. 基于蟻群算法的排課系統(tǒng)研究與設計. [碩士論文]. 合肥: 安徽大學, 2005
[11] 鄭立平, 郝忠孝. 遺傳算法理論綜述. 計算機工程與應用, 2003, 21: 50-54
[12] 王志美, 陳傳仁. 遺傳算法理論及其應用發(fā)展. 內蒙古石油化工, 2006, 9: 44-45
[13] 王小平, 曹立明. 遺傳算法：理論、應用及軟件實現(xiàn). 西安: 西安交通大學出版社, 2002
[14] 薛華成. 管理信息系統(tǒng). 北京: 清華大學出版社, 2003
[15] 蔡淑琴. 管理信息系統(tǒng). 北京: 科學出版社, 2004
[16] 鄒躍. 人性化排課算法的構造與設計. 重慶科技學院學報, 2006, 8(4): 90-93
[17] 林志雄. 排課數(shù)學模型及其算法. 龍巖學院學報, 2006, 24(6): 9-12
[18] 王昊亮, 李剛. Visual C#程序設計教程. 北京: 清華大學出版社, 2003
[19] (美) Jason Price, Mike Gunderloy. Visual C#從入門到精通. 北京: 電子工業(yè)出版社, 2003
[20] 薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論. 北京: 高等教育出版社, 2002
[21] 李律松, 陳少剛, 沈剛. Visual C# 數(shù)據(jù)庫高級教程. 北京: 清華大學出版社, 2005
[22] 王晟. Visual C#.NET 數(shù)據(jù)庫開發(fā)經(jīng)典案例解析. 北京: 清華大學出版社, 2005
[23] Chris Ullman, John Kauffman and etc. Beginning ASP.NET 1.1 with Visual C# .NET 2003. Wrox Press Ltd, 2004
[24] 何鵬飛, 王政. C#實用編程百例. 北京: 清華大學出版社, 2004
