簡易檢索 / 詳目顯示

回結果列表
研究生： 王富民
論文名稱： 基因演算法於排課問題上之研究
指導教授： 葉耀明
學位類別： 碩士
Master
系所名稱： 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年： 2002
畢業學年度： 89
語文別： 中文
論文頁數： 136
中文關鍵詞： 排課問題 、基因演算法 、基因代理人計算
論文種類： 學術論文
相關次數： 點閱：236  下載：54 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 排課問題是一個NP-Complete的問題，一直都沒有很好的解決方法。但是此問題又是毎一個學校在毎個學期都會碰到的一個必要行政作業，其問題的條件限制包括課程、教師、教室、班級、以及設備等複雜因素。很不容易將其轉換成電腦可以解決的程式系統。本論文提出一種改良後的基因演算法運算機制來解決此限制條件非常複雜的排課問題。我們改良後的運算機制可以自然地將排課問題在課程、教師、教室、班級以及設備等複雜的限制條件下融入基因演算法中有效地求解。為了提高此系統的執行效率，我們進而將此基因演算法運算機制導入可以做並行處理的基因代理人計算的概念，並提出兩種基因代理人運算模式：Message Queue、Collection。經過效率執行評估後，我們發現多執行緒和多處理程序下的基因演算法程式確實可以提高本系統的執行效率。 Course Scheduling Problem is an NP-Complete Problem, however, it is also a necessary administration task for every school in every semester. The constraints of a Course Scheduling Problem include complicated parameters such as courses, teachers, classrooms, classes and facilities in a school. It is very difficult to develop an efficient computer system to solve this kind of problem. This paper proposes a modified genetic algorithm to solve the Course Scheduling Problem, which can adapt these complicated parameters very easily and solve the problem efficiently. In order to improve the execution performance of the system, we also introduce genetic agent computing concept into our computing mechanism, which can provide concurrency computation through distributed system. We propose two genetic agent computing models: Message Queue and Collection. We find that the multi-thread and multi-process versions of genetic agent computing indeed can improve the execution performance of our system.

    Course Scheduling Problem is an NP-Complete Problem, however, it is also a
    necessary administration task for every school in every semester. The
    constraints of a Course Scheduling Problem include complicated parameters such
    as courses, teachers, classrooms, classes and facilities in a school. It is
    very difficult to develop an efficient computer system to solve this kind of
    problem. This paper proposes a modified genetic algorithm to solve the Course
    Scheduling Problem, which can adapt these complicated parameters very easily
    and solve the problem efficiently. In order to improve the execution
    performance of the system, we also introduce genetic agent computing concept
    into our computing mechanism, which can provide concurrency computation
    through distributed system. We propose two genetic agent computing models:
    Message Queue and Collection. We find that the multi-thread and multi-process
    versions of genetic agent computing indeed can improve the execution
    performance of our system.

    附表目錄............................................... ii 附圖目錄.............................................. iii 第一章　緒論............................................ 1 第一節　研究背景........................................ 1 第二節　文獻探討........................................ 1 第三節　研究目標........................................ 5 第二章 基本定義與問題描述................................7 第一節　基因演算法.......................................7 第二節　排課問題....................................... 11 第三節　排課問題融入基因演算法..........................12 第四節　改良的基因演算法................................16 第三章　基因演算求解排課問題............................21 第一節　如何以基因演算法求解排課問題....................21 第二節　單一族群和多族群下的基因演算法..................35 第四章　系統的架構與分析................................45 第一節　系統架構....................................... 45 第二節　排課作業的運作方式..............................61 第五章　系統評估與分析..................................75 第一節　系統的執行效能..................................75 第二節　系統執行的滿意度................................82 第六章　結論與未來發展方向..............................89 第一節　結論............................................89 第二節　未來發展方向與應用..............................90 參考文獻............................................... 91 附錄一：DTD格式及XML範例............................... 95 附錄二：輸入數據資料...................................111 附錄三：系統畫面...................................... 123

    [1] 唐學明,"軍事學校電腦排課問題之探討",復興崗學報59期，1996。
    [2] 劉明淵,"電腦在排課作業上的應用-問題的性質與幾個系統的作法", 資訊與教育雜誌
    1993.4。
    [3] 包冬意,賴永進,吳智輝, "大專院校排課自動化之研究",大葉學報2（1）： p.135-
    144,1993。
    [4] 盧坤勇, "電腦化排課系統指派法則探討", 聯合學報12期.
    p107- 116 。民國83.11。
    [5] 邱孟佑,廖鴻圖,"植基於Intranet上之電腦輔助排課系統",德明學報12期,頁1-13, ,民
    86.3。
    [6] H.Shimodaira,"A New Genetic Algorithm Using Large Mutation Rates and
    Population-Elitist Selection(GALME)", Proceesings of the 8th International
    Conference on Tools with Artificial Intelligence(ICTAI'96).
    [7] K.D.Jong,"Genetic Algorithms: A 30 Year Perspective", Festschrift
    Conference in Honor of John H. Holland, 15-18 May, 1999. http://www.pscs.umich.
    edu//jhhfest/schedule-closed.html.
    [8] N.Chaiyaratans and A.M.S.Zalzala, "Recent Developments in Evolutionary and
    Genetic Algorithm:Theory and Applications", Genetic Algorithms in Engineering
    Systems: Innovations and Applications,2-4 September 1997, Conference
    Publication No.446, @IEEE,1997.
    [9] H.R.Bethesda, "Cooperative Model for Genetic Operators to Improve GAs",
    IEEE International Conference on Intelligence, Information and Systems Nov. 1-
    3, 1999.
    [10] M.Schwehm, "Parallel Population Models for Genetic Algorithms",
    Copyright © 1997-2001 NEC Research Institute. http://citeseer.nj.nec.com/
    schwehm96parallel.html.
    [11] T.Mastsumura, M.Nakamura, J.Okech ,"Effects of Chromosome Migration on a
    Parallel and Distributes Genetic Algorithm", Proceedings of the 1997
    International symposium on Parallel Architectures, Algorithm, and Network,
    1997. (I-SPAN '97).
    [12] K.Kojima, W.Kawamata, H.Matsuo and M.Ishigame , "Network Based Genetic
    Algorithm", Proceedings of the Seventh International Conference on Parallel
    and Distributed Systems: Workshops (ICPADS'00 Workshops) Copyright (c) 2000
    Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
    [13] N.Barnier, P.Brisset, "Optimization by hybridization of a genetic
    algorithm with constraint satisfaction techniques", 1998 IEEE
    http://iciis99.cs.unr.edu/schedule.html.
    [14] Selim,SM,"An algorithm for constructing a University faculty timetable".
    Comput. Edue., 6. pp.323-332. 1982.
    [15] Selim,SM, "An algorithm for producing course and lecture timetable".
    Comput. Edue., 6. pp.323-332. 1983.
    [16] Dowsland,W.B. and Lim,s"Computer aided school timetabling - part1: the
    history of computerised timetabling", Compute Education,pp22-23. 1982,Nov.
    [17] Dowsland,W.B. and Lim,s,"Computer aided school timetabling - part2: the
    micro-computer for school timetabling", Compute Education,pp2-4. 1982,Nov
    [18] Loo,E.H. Goh,T,N. and Ong, H.L., " A heuristic approach to scheduling
    university timetables.", Comput. Edue. 10(3),pp.397-388.1986.
    [19] N.L.Lawrie, "An Integer Linear Programming Model of a School Timetabling
    Problem", The Computer Journal, Vol.12, pp307-316. 1969.
    [20] D.C.Wood, "A Technique for Colouring a Graph Applicable to Large Scale
    Timetabling Problem", The Computer Journal, Vol.12, p317-319. 1969.
    [21] S.Even, A.Itai, A.Shamir, "On the Complesity of Timetable and
    Multicommodity Flow Problems", 16th IEEE Annual Symposium on Foundatiions of
    Computer Science, pp.184-193, 1975.
    [22] Caroline C.Hayes, ”Agents in a Nutshell-A Very Brief Introduction”,
    IEEE Transactions on Knowledge and Data Engineering, VOL 11, NO.1,January/
    FEBRARY 1999.
    [23] W3C Recommendation 10-February-1998, "Extensible Markup Language (XML)1.
    0", http://www.w3.org/TR/1998/REC-xml-19980210
    http://www.twtec.org.tw/XML_spec.htm
    [24] M.Gen , R.Cheng, "Genetic Algorithm & Engineer Design", Willey-
    Interscience Publication,pp.2-4,1997.
    [25] P.Ciancarini, R.Tolksdorf, F.Vitali, D.Rossi, A.Knoche ”Coordinating
    Multiagent Applications on the WWW: A Reference Architecture”, IEEE
    Transactions on Software　Engineering, VOL 24, NO.5,MAY 1998.
    [26] M.Gen , R.Cheng,"Genetic Algorithm & Engineer Design", Willey-Interscience
    Publication, pp.182-183,1997.

    QR CODE