以遗传演算法解决课程排课的问题.docx

1、以遗传演算法解决课程排课的问题以遺傳演算法解決課程排課的問題指導老師：謝佳琳 老師 專題小組組員：施竣卬、周士瑋、許勝富、曾昭國、陳嘉穎 梁心怡、郭佳慧、蘇哲民、湯肇文、許輝洋摘要攸關學校、老師與學生權益的排課問題，是各級學校每學期都必須會面對的問題，所以本組想藉由研究相關的排課問題，來探討其重要性及改進的可能性。排課問題是一項複雜又困難的工作，傳統人工的排課方式，既浪費時間亦浪費成本，所得到的成果卻不一定會使人滿意，常常會引起抱怨。本小組利用國內較為人知的遺傳演算法，並使用電腦程式語言撰寫其模型，將排課的相關資料轉換為染色體，在追求可行解的目標下，把排課的相關限制條件一一考量，求得最後想要的

2、排課結果。我們依照排課的目的，將排課方式(傳統人工排課、電腦排課)分為實驗組與對照組，並各自加以比較。我們以真理大學工業管理學系為參考對象，以實際課表所提供的資料，配合本組的排課模型，模擬出最後的排課結果。對排課人員而言，在思考如何加強其排課方式之時，本研究應可提供另一個參考的層面。雖然本專題尚屬初期的研究，但是擁有其獨特、可行的排課方法，值得讓有興趣的人繼續加以研究探討。關鍵詞：排課問題、遺傳演算法壹、前言排課作業問題相當繁雜，一旦發生失誤，會浪費許多的時間與人力。如何在排課中，儘可能滿足老師與學生對課表的需求，那就要有一套公正且聰明的排課制度，至少是透明的且結果是全校師生共同可以接受的，這

3、是一般的排課不易做到的。所以若能建立一套自動化排課系統，進而可以創造校方、老師與學生三方面三贏的局面。排課問題在各級學校的教務行政上是一件很重要的課題。進行排課時需考慮的因素包括老師的專長、興趣、行政兼職、個人意願、授課基本鐘點、兼課節數上限、課程性質與授課時段配合、人性化的考量.等等。然而，學校行政上的相關排課人員，通常都是在極有限的時間內需考量各方面的限制，再排出全校的課表，常弄得排課人員心力交瘁而無暇顧及老師個人意願，更遑論去評估排課結果是否符合人性化的原則，導致很多老師會有對排課結果不滿意，使部分老師自覺受到不公平現象發生。貳、文獻探討排課的問題是指針對於每一課程給予一個時段和教室，每

4、位老師有數門教授課程，而每個課程根據其學分數有不同的時數，同時每位老師可以提出哪些時段為希望排課時段或不願意排課時段。簡單的說就是把各式各樣的限制式加入排課問題中。以往使用傳統人工方式來進行排課時，排課人員需不斷地對所排定的課表進行檢核及修正，以避免一切可能不符現制式的情形，如此不僅浪費大量的時間、人力，且排定的課表須加以變動時，便得重新安排整張課表，使課務工作的效率大打折扣；根據上述理由，在近年來有許多自動化的方法或模型被提出來處理不同的排課問題。排課問題是在滿足所有必要限制條件下，將各種資源（時間、空間、人力、設備）分配給多個活動與課程。同時所有的限制式可以分成兩種，硬性限制式和軟性限制式

5、兩種，所謂硬性限制式是指限制必須被滿足，軟性限制式則是最好能被滿足，一個排課問題的可行解必須要能滿足所有硬性限制式，並儘量的滿足越多的軟性限制式越好；目前各種排課問題的解決方法大致分為作業研究（Operations Research）和人工智慧（Artificial Intelligence）兩種領域。早期的研究大多是使用作業研究的方法來處理。D.de Werra將排課問題表示成圖形著色問題，並以由弧與節點所構成網路模型來表示，藉由找出滿足相鄰節點不同顏色的方式來求出答案。 Hertz使用tabu search(搜尋法)得方法來解決排課問題。但是作業研究的方法只適合來處理小型問題，當問題之限制

6、式增多且使問題相對複雜時，求解過程就會變的非常困難。排課問題就是針對教學對象，安排所需上課的時間與地點所面臨的問題。從管理者的觀點而言，目標是希望所有課程都能排到適當的時段和教室，並且儘可能的滿足越多的條件限制越好。從教師的觀點而言，目標是希望所排課的時間都在自己所喜好的時段中。從學生的觀點而言，目標是希望所有的課程都能排在自己所喜歡的時段，並且越少衝堂越好才能更彈性的選課。所以我們根據對教師、學生的需求了解後，收集了可能影響排課問題的限制式，如下列所示：在硬性限制式方面 已排好的課不能再排入同時段 一個班級不能在同時段上兩堂課 一位老師不能在同時段上兩堂課 一間教室不能在同時段被兩個班級所使

7、用 某時段排給某特定科目不容再變在軟性限制式方面 教師1. 最低上課時數2. 任教專長3. 是否喜歡連堂上課4. 中午(12:00)儘量不要排課5. 星期六儘量不要排課 上午盡量不要排課 下午盡量不要排課 禮拜一一早盡量不要排課6. 教師上課的合適時段7. 教師喜歡的上課時段 學生8. 中午(12:00)盡量不要排課9. 星期六儘量不要排課10. 體育課完儘量不要排課11. 共同科目同班級一起上以遺傳演算法解決課程排課的問題12. 選修科目各班級分開選課13. 二學分課連上14. 三學分課 三堂連上 分成一堂、二堂上(二天) 分成二堂、一堂上(二天) 8. 衝堂課程學生自行選擇參、方法介紹與模

8、式建立一遺傳演算法的源由遺傳演算法即是由此生物進化論之論點出發，以電腦模擬自然界的演化方式，對既定問題求最佳解。而這個觀念最早是於1968年由美國芝加哥大學賀蘭(John Holland)教授所提出，並於1975年出版自然與人工系統中的適應（Adaptation in natural and artificial systems）一書，建立遺傳演算法的原型，發展了遺傳演算法的理論基礎。二、遺傳演算法的運作為了要利用電腦模擬生物演化的機制，首先是把問題變數編碼成字元(Character)，來代表生物界中的基因。而染色體(Chromosome)是由基因所組成，其又稱之為個體(Individual)

9、，故將每個問題變數所代表的字元串聯成一條字串(String)來加以模擬，並且這一條字串即是問題的可行解之一。族群(Population)則為物種之集合，也是不同字串之集合。每個物種在自然界中須面對著環境中的各項挑戰與競爭，而經由物競天則，適者生存的理論下，淘汰不適合環境的物種，留下更適合的物種。為了模擬生物界的適應的架構，將對問題建立一個適應函數(Fitness Function)，來評估每個字串的適應能力。三、排課問題模式建立其中限制函數可視為硬限制，滿足所有硬限制之解即為可行解。 一位教師在同一時段中不能上兩門課。 一個班級在同一時段中不能同時排兩門課。而適應函數可視為軟限制，其彈性較大。

10、本研究設定之軟限制為： 老師一天之中上課堂數。 老師一天之中連續上課堂數。 老師課程大部分在上午或下午。 3學分的課分段上或一次上完。 早上8點（第一節）是否排課。 下午4點以後（最後一節）是否排課。 中午12點（第五節）是否排課。首先將課表加以編碼，並輸入符合硬限制式所需之個數，且利用電腦隨機產生初始合理解；再輸入每個問題之權重，藉由軟限制式給予每個合理解（染色體）加以評分，判斷其優劣，挑選出優與最優的兩條染色體，進行複製，然後輸入遮照數使其交配，產生四個子代，再予判斷是否進行突變；再挑出優與最優的染色體，然後做抉擇，如果滿足停止條件，則輸出結果；如果不滿足，則回頭至交配處理，反覆執行。四、

11、產生初始族群初始解必須滿足訂定的硬性限制式，而產生之方式是以亂數隨機產生。因過程中填入課表之程序為隨機的方式，故實際產生初始族群中之各初始解差異十分顯著。五、定義適應函數本組把各項軟性限制式給予特別之權數，並以累加的方式，訂定適應性函數值。染色體之適應性函數越高，表示其對應之課表越優良。適應函數定義如下：ni=1P = Wi Ci 公式（1)六、亂數產生器本系統在運算交配、突變時皆會採取以亂數產生，因而本系統採用了統計學上的均勻分配法，以期可以得到隨機之亂數 。七、定義複製運算本研究所採行的方式為競爭式，其步驟為先將世代中之染色體依適應函數值之大小排序，挑選其中最大的2條染色體，依其相同之權重

12、複製至下一世代。八、定義交配運算本系統所採用的交配方法是遮罩交配。因為我們使用的編碼方式是採用真實值編碼，比起傳統二元編碼組內變異較小，故希望能夠透過遮罩交配將基因打散，且保持原有基因的特性，讓求出的解不要落入區域最佳解。九、定義突變運算為了讓染色體在演化的過程中不陷入一侷限的範圍，所以需要做突變。十、訂定停止規則本研究所採用的停止規則為下，當其中一點滿足時，則停止演算。 電腦的運算處理時間到達預設值。 到達最佳解，即染色體的適應函數值到達預設之最高值。 電腦在搜尋時間內找不到任何初始解。以遺傳演算法解決課程排課的問題肆、排課模式之評估與實驗比較一、 問卷本小組這次的排課系統研究範圍是以工業管

13、理學系為範圍。經由與受訪者的溝通蒐集資料。經過運算之後，算出每一限制式之權重，可編製其權重表如下限制項目選項權重總權重1老師一天之中希望上課幾堂課1-2堂7.577.53-4堂69.795-6堂07堂以上02一天之中對於課程連續排課的意願連續兩堂31.2562.5連續三堂31.25連續四堂03一天之中希望上午或下午上課課程大部分在上午5.2552.5課程大部分在下午5.25平均分配424若有三學分的課希望怎麼分配3堂連續上課5872.52+1堂(分兩天上完)14.5無所謂05早上8點(第一堂)是否希望排課希望067.5不希望67.5無所謂06下午4點(最後一堂)是否希望排課希望047.5不希望

14、47.5無所謂07中午12點(第五堂)是否希望排課希望070不希望70無所謂0二、 實驗設計在本實驗中我們假設不考慮教室的屬性與數量。亦就是說我們假設一個學校中有足夠的教室可供給我們排課。在課程方面，每門課分別由同一教師來教授；在學分方面，我們假定每一學分均為一堂課。希望能排出工管系四個年級，每個年級A、B、C三班，共12個班級的課表。在我們考慮的因素中，我們以工管系為例，將班級定為A、B、C三個班級，教師名稱設定為目前工管系的實際情形。三、 實驗GA Model（組）在我們所撰寫的程式中對於遺傳演算法的參數做了以下這些設計。 權數：由表4.1之權重表說明各個條件限制式的重要性與權重。我們將計

15、算出來的權數置入程式中，讓電腦作為判斷我們課表好壞之依據。 演算時間：輸入演算之時間（本實驗為50、100、150、200、250、300、1000秒）。 起始解個數：輸入所希望的起始解個數（本實驗設定為50個）。 交配率：我們必須要確實的執行交配的動作，以觀察交配之後所得到的結果，所以在這裡我們將交配率定為50%。 突變率：突變的步驟用來確定最佳解是否被侷限在部分解裡面。而我們在這裡將突變率定為 10%、20%、50%、100%，也就是 0.1、0.2、0.5、1。經過以上繁雜的設定，我們才可以利用基因演算法來求解產生課表。亂數 Model（亂數組）亂數組的程式輸入值所需變動的只有時間值，其

16、演算的方式皆為亂數隨機排入。 演算時間輸入演算之時間（本實驗為50、100、150、200、250、300、1000秒）最後我們把在各個時間點上，GA組與亂數組所得到之最佳解作一圖表(見表1)之分析，即可看出兩者最佳化之趨勢。 表1: GA組與亂數組對應時間-最佳解一覽表50秒100秒150秒200秒250秒300秒1000秒亂數82.0383.988.4590.991.493.4197.93遺傳242.6332.1372.4401.8431.1447.4497.77四、實驗差異檢定為了比較在S秒時，使用GA產生的課表之平均分數是否優於亂數所產生的課表？首先，使用亂數隨機產生NX(NX=30)

17、張課表，其NX張課表評分為X1、X2、X3、XNX，再使用GA方法隨機產生NY(NY=30)張課表，其評分為Y1、Y2、Y3、YNY，且兩組資料也為兩組獨立樣本，由於母體變異數x2與Y2無法得知，故以樣本標準差sx與sY，取代x、Y，至於左尾檢定H0X Y對H1X Y，令z =( ) /(sx2/ NXsY2/ NY)，其棄卻域為 z - z。並藉由EXCELE軟體執行檢定，其結果如下表(見表2)： 表2:檢定結果亂數GA平均數97.930191497.77449變異數34.89292317.10593觀察值個數3030z-116.72958P(Z=z) 單尾0臨界值：單尾1.6448535以

18、遺傳演算法解決課程排課的問題其中 NX=30， = 97.930191，sx2=34.89292，NY=30， = 497.77449，sx2= 317.10593，並在95信賴度下，z0.05=1.6448535，z= -116.72958 - z0.05 = -1.6448535，故有足夠證據拒絕虛無假設HO，此表示有足夠證據推論在1000秒時，GA所產生的課表是優於亂數所產生的課表。五、實驗比較 最佳（收斂後）解之比較我們把時間1000秒，突變率0.5，起始解個數50所得到的課表作為GA組的代表，而亂數組則以相同時間1000秒所得出的課表作為對照，作出下列之比較。 分數趨勢從下圖1與圖2

19、可看出，GA組課表分數隨著時間的增加，呈現著成長的趨勢；而亂數組則呈現時而成長時而下滑的無規則隨機散佈。 圖1GA組課表分數趨勢圖 圖2 亂數組課表分數趨勢圖 最佳解趨勢從下圖3與圖4可看出，GA組因則優交配，所以一直會有更加解的出現；反觀亂數組則時常會有陷入長時間找不到更加解的窘境。在1000秒之內，GA組之最佳解為334.8分，而亂數組則為99.2分。 圖3 GA組最佳解趨勢圖 圖4亂數組最佳解趨勢圖 所得課表我們以工二C之課表為例，從下圖5與圖6，我們可個別算出GA組與亂數組的分數。1.連課分數 = 連課數 連課權數G.A.連課分數 = 6 6.2 = 37.2亂數連課分數 = 3 6.

20、2 = 18.62.第一堂不排課分數 = 第一堂均不排課 不排課權數 圖5GA組工二C課表 圖6亂數組工二C課表 時間-最佳解 之比較最後我們把在各個時間點上，GA組與亂數組所得到之最佳解作一圖表(見表3)之分析，即可看出兩者最佳化之趨勢其GA組與亂數組對應之“時間-最佳解趨勢”，如圖7。 表3:GA組與亂數組對應時間-最佳解一覽表50秒100秒150秒200秒250秒300秒1000秒亂數82.0383.988.4590.991.493.4197.93遺傳242.6332.1372.4401.8431.1447.4497.77 圖7: GA組與亂數組對應時間-最佳解趨勢圖以遺傳演算法解決課程

21、排課的問題伍、結論和未來展望本章節將針對本小組所做的研究，包括研究過程、架構分析、模型設計及實驗結果等等，歸納出研究結論，並提供可以參考之建議。讓未來有興趣繼續深入此一問題的後續者，能夠參考本研究而發展出更完善、效用更為顯著的排課系統。雖然本研究是針對某一些特定的限制條件進行的研究，但是其建構出來的模型，在我們設定的情況下也可達到不錯的最合適目標之結果，亦能滿足授課老師對於排課上不同的喜好及意願。本研究的特色在於將蒐集到的相關排課資料整理齊全後，藉由電腦程式語言撰寫模型。概略的說，第一，模型雖然不是盡善盡美，但對於解決排課問題，至少還能得到一個令人可以接受的結果；第二，雖然模型排出來的不是最佳

22、的課表，但其能輔助排課人員在遵行一定的規則下，將課表排出；第三，模型可產生許多最合適的課表，可供排課人員參考；第四，本模型能將原本排課的速度加快，使得排課人員有更多的時間找出其他的問題。在傳統人工排課中，排課人員往往簡化起見，常常將課表就從第一班開始排起。接著依班級順序排出，使得第一班通常擁有較好的排課內容，而最後一班只能從授課老師其餘的時間來安排課表，這為不公平之一，老師也沒有多大的選擇性。相對於本組以遺傳演算法進行排課系統的研究，所產生出來的課表，不僅節省排課人員相當多的時間，在課表選擇性的空間相對的提高，而各班的課表同時產生，也比較公平。未來展望總結來說排課原本就是一個複雜又困難的工作。

23、既要同時滿足老師的需求又要使學生覺得滿意，幾乎是不可能的。本系統也有許多未盡完善之處，在未來可再加以深入琢磨： 加入教室因素 考慮學生意願 排入全校課表 人性化使用介面這些都是未來能進一步研究的方向，將來後續研究者可發揮的空間，進而達到真正自動化排課的資訊系統。參考文獻1. 王本耀、曾國雄，”工研院育成中心新進廠商申請進駐評審模式研究”，國立交通大學科技管理研究所，碩士論文，民國92年2月1日。2. 王怡仁，”電腦撫助之排課系統”，雲林科技大學工業工程與管理技術研究所，碩士論文，民國81年3. 王進德、蕭大全，”類神經網路與模糊控制理論入門”，全華書局，民國90年4. 包冬意，”大專院校排課自

24、動化之研究”，大業學報，第二卷，第一期，民國82年12月，第135-144頁。 5.向殿政男作/劉天祥譯，FUZZY理論入門，中國生產力出版公司，日本，民國80年6. 邱元泰，”遺傳演算在排課問題之應用”，國立中正大學數學研究所，碩士論文，民國91年月。7. 沈正慈，”電腦排課”，元智大學電機暨資訊工程研究所，碩士論文，民國88年。8. 金國忠，”依規則為基礎的排課系統之研究”，淡江大學管理科學研究所，碩士論文，民國74年6月。9. 周鵬程，遺傳演算法原理與應用-活用Matlab，全華科技圖書股份有限公司，台灣，民國91年10. 楊振興，”大專院校排課之探討以數學規劃為研究工具”，台灣，民國九

25、十一年，第10-19頁11. 戴佳恩、何秋萍、陳彥偉、宋恩生，人工智慧與類神經網路簡介，民國89年2月建置，存取於2002年10月。12. 陳志昇，”大專院校電腦化之研究”，國立成功大學工業管理學系，碩士論文，民國73年6月。 13. 駱至中、方志成，”向政治學與社會科學借法取經的新世代人工智慧(遺傳演算) ”，佛光人文社會學院資訊學研究所，民國91年5月9日14.韓復華、陳柏榮、王國琛，”應用限制規劃求解排課問題：以交通大學全校性課程排課為例”，中華民國第六屆運輸網路研討會論文集，中華民國，民國90年11月，第33-42頁。 15.A. Hertz. Findung a feasible course schedule using tabu search. Discrete Applied Mathematices, 35(3):p255-270,1992.16.D.de Werra Restriced coloring models for timetabling. Discrete Mathematics, p161-170,1997.