現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:基因演算法應用於大學排課最佳化系統建置之研究 [以論文名稱查詢館藏系統]
論文英文名稱:Genetic Algorithm on the optimization framework of Timetabling problem for University [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:工程學院
系所名稱:土木與防災研究所
畢業學年度:97
出版年度:98
中文姓名:張士宇
英文姓名:Shr -Yu Jang
研究生學號:96428028
學位類別:碩士
語文別:中文
口試日期:2009-07-14
論文頁數:100
指導教授中文名:宋裕祺
指導教授英文名:Yu-Chi Sung
口試委員中文名:謝尚賢;呂良正
口試委員英文名:Shang-Shian Shie;Liang-Jeng Liu
中文關鍵詞:基因演算法排課問題
英文關鍵詞:Genetic AlgorithmsSchool Timetabling
論文中文摘要:摘要
論文名稱:基因演算法應用於大學排課最佳化系統建置之研究 頁數:100
校所別:國立台北科技大學土木與防災研究所
畢業時間:九十七學年度第二學期 學位:碩士
研究生:張士宇 指導教授:宋裕祺
關鍵詞:基因演算法、排課問題
大專院校之排課一直都是教務行政人員各學期感到頭痛的問題。此問題受資
源分配限制,亦屬於NP-Complete 之問題,主要有課程、教師、教室、班級等資
源上的限制。使用傳統方法由行政人員來排課,不僅耗時耗力且不盡能滿足每位
老師的需求,常常需要透過與老師的溝通與協調來達成。
本文利用基因演算法求解排課問題,將教師課表設為染色體基因以儘量滿足
教師需求及教室分配之問題,使單一課程可在不同教室上課,增加排課較多之選
擇性。本系統利用C#撰寫程式語言,並結合資料庫之應用,方便使用者修改以及
維護資料。最後以筆者就讀之學校排課為例,結果證明本系統在多重資源限制下
可得到出令人滿意之結果。
論文英文摘要:ABSTRACT
Title:Genetic Algorithm on the optimization framework of Pages:100
Timetabling problem for University
School:National Taipei University of Technology
Time:July, 2009 Degree:Master
Researcher:Shr Yu, Jang Advisor:Yu-Chi, Sung
Keywords:Genetic Algorithms、School Timetabling
Course scheduling is a complicated problem for University which makes
administrative personnel feels puzzled in every term. This problem is limited by
resource allocation, also belonging to the NP-Complete problem, there are such
restrictions on resources as course, teacher, classroom, class, etc.Using administrative
personnel to solve course scheduling problem in traditional method does not only waste
time but also consume strength and can not satisfy all the teacher’s requires entirely, and
need to coordination with the teachers.
The thesis solves timetabling problem with Genetic Algorithm method, and set
teacher's school timetable as the chromosome gene to satisfy the teacher’s requirement
and arrange classroom assigning problem, making the single course have a class in
different classrooms to increase the option of course scheduling. This work constructs
with C# and combines the database, it helps the users revise and maintain the data
conveniently.
論文目次:目錄

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 viii
表目錄 x
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究範圍 3
第二章 文獻回顧 4
2.1 排課問題種類 4
2.2相關文獻回顧 6
2.3 排課問題的解決方法 10
2.4 小結 11
第三章 基因演算法 12
3.1 基因演算法簡介 12
3.2 基因演算法之演化流程 13
3.2.1 基因演算法流程圖 13
3.2.2 編碼及解碼方式 14
3.2.2.1 二進制編碼 14
3.2.2.2 實數編碼 15
3.2.3 適應度函數 16
3.2.3.1 目標函數與適應度函數 16
3.2.3.2 適應度函數比例轉換 17
3.2.4 選擇 20
3.2.4.1 比例選擇法 20
3.2.4.2 精英策略選擇法 21
3.2.4.3 明確採樣選擇法 22
3.2.4.4 排序選擇方法 22
3.2.4.5 隨機競賽選擇法 23
3.2.5 交配 24
3.2.5.1 單點交配 24
3.2.5.2 雙點交配 25
3.2.5.3 多點交配 26
3.2.5.4 均勻交配 26
3.2.6 突變 27
3.2.6.1 簡單突變 28
3.2.6.2 均勻突變 29
3.3 基因演算法之重要控制參數 30
3.3.1 控制參數 30
3.4 具限制條件之基因演算法 31
3.4.1 搜索空間限定法 31
3.4.2 可行解轉換法 32
3.4.3 懲罰函數法 33
3.5 本論文研發基因演算法系統之應用與驗證 34
3.5.1 二進制編碼 34
3.5.2 實數編碼 38
3.5.3 符號編碼 39
3.5.3.1 編碼方式 39
3.5.3.2 計算適應度函數 40
3.5.3.3 選擇 41
3.5.3.4 交配 42
3.5.3.5 突變 42
3.5.3.6 結果分析 43
第四章 排課系統架構及案例模擬 45
4.1 排課系統使用流程 45
4.2 資料處理 46
4.3 基因演算法求解 51
4.3.1 定義編碼方式 51
4.3.2 初始族群產生方法 53
4.3.3 計算適應度函數 56
4.3.4 建立選擇、複製機制 58
4.3.5 建立交配機制 59
4.3.6 建立突變機制 60
4.2.7 建立停止機制 61
4.4 後處理機制 62
4.5 案例模擬 65
第五章 結論與建議 70
5.1 結論 70
5.2 建議 71
參考文獻 72
附錄A 排課系統操作手冊 75
附錄B 演算結果 90
























圖目錄

圖3.1 基因演算法流程圖 13
圖3.2 染色體之基因型 15
圖3.3 線性轉換示意圖 18
圖3.4 具負值之線性轉換示意圖 19
圖3.5 單點交配示意圖 24
圖3.6 雙點交配示意圖 25
圖3.7 多點交配示意圖 26
圖3.8 均勻交配示意圖 27
圖3.9 簡單突變示意圖 28
圖3.10 均勻突變示意圖 29
圖3.11 搜索空間限定法示意圖 32
圖3.12 可行解轉換法示意圖 33
圖3.13 範例1收斂圖(一) 35
圖3.14 範例1收斂圖(二) 35
圖3.15 範例2收斂圖(一) 36
圖3.16 範例2收斂圖(二) 36
圖3.17 範例3收斂圖(一) 37
圖3.18 範例3收斂圖(二) 37
圖3.19 實數編碼收斂圖 38
圖3.20 數獨矩陣示意圖 39
圖3.21 數獨九宮格示意圖 39
圖3.22 數獨基因型示意圖 40
圖3.23 數獨適應函數示意圖 40
圖3.24 數獨問題示意圖 41
圖3.25 數獨多點交配示意圖 42
圖3.26 數獨簡單突變示意圖 43
圖3.27 數獨無拘束條件求解 43
圖3.28 數獨無拘束條條件解答…………………………………………………44
圖3.29 數獨有拘束條件求解 44
圖3.30 數獨有拘束條件解答……………………………………………………45
圖4.1 排課系統使用流程圖 45
圖4.2 教師表處理介面 48
圖4.3 教室表處理介面 48
圖4.4 班級資料表處理介面 49
圖4.5 課程資料表處理介面 49
圖4.6 教師課表及教師喜好時段表處理介面 50
圖4.7 班級課表處理介面 50
圖4.8 染色體編碼示意圖 51
圖4.9 排課系統交配示意圖 59
圖4.10 排課系統突變流程 60
圖4.11 課表備份介面 63
圖4.12 課表輸出介面 63
圖4.13 資料修改介面(一) 64
圖4.14 資料修改介面(二) 64




表目錄

表3.1 排序選擇之機率分配表 23
表4.1 教師課表 55
表4.2 教師授課意願表 58
表4.3 結果比較(一) 65
表4.4 限制次數比較表(一) 66
表4.5 結果比較(二) 67
表4.6 限制次數比較表(二) 68
論文參考文獻:參考文獻

[1] A. Schaerf, "A survey of automated timetabling", Artificial Intelligence Review, vol. 13, 1995, pp. 87-127.
[2] B. Edmund, E. David, and W. Rupert, "A Genetic Algorithm for University Timetabling", Department of Computer Science, University of Nottingham, 1994.
[3] D. E. Goldberg, Genetic Algorithms in Search, Optimisation and Machine Learning, Addison-Wesley, Reading, 1989.
[4] D. C. Wood, "A Technique for Colouring a Graph Application to Large Scale Timetabling Problem", The Computer Journal, vol. 12, 1969, pp. 317-319.
[5] E. H. Loo, T. N. Goh, and H. L. Ong, "A Heuristic Approach to Scheduling University Timetables", Compute. Education, vol. 10, no. 3, 1986, pp. 388-397.
[6] Horacio Martinez-Alfaro and Gerardo Flores-Teran, "Solving the Classroom Assignment Problem With Simulated Annealing", Center for Artificial Intelligence, ITESM, IEEE 1998.
[7] J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press,Ann Arbor,Mich.,1975.
[8] S. Even, A. Itai., and A. Shamir, "On the Complexity of Timetable and Multicommodity Flow Problems", 16th IEEE Annual Symposium on Foundations of Computer Science, 1975, pp. 184-193.
[9] S. M. Selim, "An algorithm for producing course and lecturer timetables", Compute Education., vol. 7, no. 2, 1983, pp. 101-108.
[10] W. B. Dowsland and S. Lim "Computer aided school timetabling - part1: the history of computerised timetabling", Compute Education, 1982, pp. 22-23.
[11] W. B. Dowsland and S. Lim "Computer aided school timetabling - part2: the micro-computer for school timetabling", Compute Education, 1982, pp. 2-4.
[12] 王富民,基因演算法於排課問題上之研究,碩士論文,國立臺灣師範大學資訊教育研究所,台北,2002。
[13] 王怡仁,電腦輔助之排課系統,碩士論文,國立雲林科技大學工業工程與管理研究所,雲林,1998。
[14] 吳智暉,結合人工智慧技術與群體決策支援環境的大專院校自動化排課系統-排課先期作業,碩士論文,大葉大學電機工程研究所,彰化,1993。
[15] 沈正慈,電腦排課,碩士論文,元智大學電機與資訊工程研究所,桃園,1999。
[16] 金國忠,以規則為基礎的排課系統之研究,碩士論文,私立淡江大學管理科學研究所,淡水,1986。
[17] 邱元泰,遺傳演算法在排課問題之應用,碩士論文,國立中正大學數學研究所,桃園,2002。
[18] 馬幼明,以適應性基因演算法與模糊推論為基礎之大學排課研究,碩士論文,暨南國際大學資訊管理學系,南投,2003。
[19] 唐學明,軍事院學排課自動化之研究-以國防管理學院為例,碩士論文,國防管理學院資源管理研究所,台南,1987。
[20] 陳志昇,大專院校排課電腦化之研究,碩士論文,國立成功大學工業管理研究所,台南,1986。
[21] 張獻文,運用哈普費爾德-譚克類神經網路開發自動化排課系統,碩士論文,大葉大學資訊管理研究所,彰化,1998。
[22] 張良安,運用基因演算法建置大專院校之排課系統,碩士論文,育達商業技術學院資訊管理所,台北,2004。
[23] 許武義,網頁式排課管理系統,碩士論文,暨南國際大學資訊管理學系,南投,2000。
[24] 楊正吉,模糊理論在排課系統上的研究,碩士論文,國立中興大學應用數學系,台中,2001。
[25] 劉明洲,微電腦輔助排課系統建構之研究-以大專院校系所為例,碩士論文,國立臺灣師範大學工業教育研究所,台南,1990。
[26] 盧坤勇, "電腦化排課系統指派法則探討", 聯合學報 12期. p107- 116 。民國 83.11。
[27] 賴永進,結合人工智慧技術與群體決策支援環境的大專院校自動化排課系統--排課群體協商,碩士論文,大葉大學電機工程研究所,彰化,1993。
[28] 謝正瑜,利用遺傳基因演算法進行排班最佳化之研究-以大學排課為例,碩士論文,華梵大學資訊管理學系,台北,2003。
論文全文使用權限:不同意授權