以遗传演算法解决课程排课的问题.docx
《以遗传演算法解决课程排课的问题.docx》由会员分享，可在线阅读，更多相关《以遗传演算法解决课程排课的问题.docx（16页珍藏版）》请在冰点文库上搜索。
以遗传演算法解决课程排课的问题
以遺傳演算法解決課程排課的問題
指導老師：
謝佳琳老師
專題小組組員：
施竣卬、周士瑋、許勝富、曾昭國、陳嘉穎梁心怡、郭佳慧、蘇哲民、湯肇文、許輝洋
摘要
攸關學校、老師與學生權益的排課問題，是各級學校每學期都必須會面對的問題，所以本組想藉由研究相關的排課問題，來探討其重要性及改進的可能性。
排課問題是一項複雜又困難的工作，傳統人工的排課方式，既浪費時間亦浪費成本，所得到的成果卻不一定會使人滿意，常常會引起抱怨。
本小組利用國內較為人知的「遺傳演算法」，並使用電腦程式語言撰寫其模型，將排課的相關資料轉換為染色體，在追求〝可行解〞的目標下，把排課的相關限制條件一一考量，求得最後想要的排課結果。
我們依照排課的目的，將排課方式（傳統人工排課、電腦排課）分為實驗組與對照組，並各自加以比較。
我們以真理大學工業管理學系為參考對象，以實際課表所提供的資料，配合本組的排課模型，模擬出最後的排課結果。
對排課人員而言，在思考如何加強其排課方式之時，本研究應可提供另一個參考的層面。
雖然本專題尚屬初期的研究，但是擁有其獨特、可行的排課方法，值得讓有興趣的人繼續加以研究探討。
關鍵詞：
排課問題、遺傳演算法
壹、前言
排課作業問題相當繁雜，一旦發生失誤，會浪費許多的時間與人力。
如何在排課中，儘可能滿足老師與學生對課表的需求，那就要有一套「公正」且「聰明」的排課制度，至少是透明的且結果是全校師生共同可以接受的，這是一般的排課不易做到的。
所以若能建立一套自動化排課系統，進而可以創造校方、老師與學生三方面三贏的局面。
「排課問題」在各級學校的教務行政上是一件很重要的課題。
進行排課時需考慮的因素包括老師的專長、興趣、行政兼職、個人意願、授課基本鐘點、兼課節數上限、課程性質與授課時段配合、人性化的考量….等等。
然而，學校行政上的相關排課人員，通常都是在極有限的時間內需考量各方面的限制，再排出全校的課表，常弄得排課人員心力交瘁而無暇顧及老師個人意願，更遑論去評估排課結果是否符合人性化的原則，導致很多老師會有對「排課結果」不滿意，使部分老師自覺受到不公平現象發生。
貳、文獻探討
排課的問題是指針對於每一課程給予一個時段和教室，每位老師有數門教授課程，而每個課程根據其學分數有不同的時數，同時每位老師可以提出哪些時段為希望排課時段或不願意排課時段。
簡單的說就是把各式各樣的限制式加入排課問題中。
以往使用傳統人工方式來進行排課時，排課人員需不斷地對所排定的課
表進行檢核及修正，以避免一切可能不符現制式的情形，如此不僅浪費大量的時間、人力，且排定的課表須加以變動時，便得重新安排整張課表，使課務工作的效率大打折扣；根據上述理由，在近年來有許多自動化的方法或模型被提出來處理不同的排課問題。
排課問題是在滿足所有必要限制條件下，將各種資源（時間、空間、人力、設備）分配給多個活動與課程。
同時所有的限制式可以分成兩種，硬性限制式和軟性限制式兩種，所謂硬性限制式是指限制必須被滿足，軟性限制式則是最好能被滿足，一個排課問題的可行解必須要能滿足所有硬性限制式，並儘量的滿足越多的軟性限制式越好；目前各種排課問題的解決方法大致分為作業研究（OperationsResearch）和人工智慧（ArtificialIntelligence）兩種領域。
早期的研究大多是使用作業研究的方法來處理。
D.deWerra將排課問題表示成圖形著色問題，並以由弧與節點所構成網路模型來表示，藉由找出滿足相鄰節點不同顏色的方式來求出答案。
Hertz使用tabusearch（搜尋法）得方法來解決排課問題。
但是作業研究的方法只適合來處理小型問題，當問題之限制式增多且使問題相對複雜時，求解過程就會變的非常困難。
排課問題就是針對教學對象，安排所需上課的時間與地點所面臨的問題。
從管理者的觀點而言，目標是希望所有課程都能排到適當的時段和教室，並且儘可能的滿足越多的條件限制越好。
從教師的觀點而言，目標是希望所排課的時間都在自己所喜好的時段中。
從學生的觀點而言，目標是希望所有的課程都能排在自己所喜歡的時段，並且越少衝堂越好才能更彈性的選課。
所以我們根據對教師、學生的需求了解後，收集了可能影響排課問題的限制式，如下列所示：
在硬性限制式方面
●已排好的課不能再排入同時段
●一個班級不能在同時段上兩堂課
●一位老師不能在同時段上兩堂課
●一間教室不能在同時段被兩個班級所使用
●某時段排給某特定科目不容再變
在軟性限制式方面
●教師
1.最低上課時數
2.任教專長
3.是否喜歡連堂上課
4.中午（12:
00）儘量不要排課
5.星期六儘量不要排課
Ø上午盡量不要排課
Ø下午盡量不要排課
Ø禮拜一一早盡量不要排課
6.教師上課的合適時段
7.教師喜歡的上課時段
●學生
8.中午（12:
00）盡量不要排課
9.星期六儘量不要排課
10.體育課完儘量不要排課
11.共同科目同班級一起上
以遺傳演算法解決課程排課的問題
12.選修科目各班級分開選課
13.二學分課連上
14.三學分課
Ø三堂連上
Ø分成一堂、二堂上（二天）
Ø分成二堂、一堂上（二天）
8.衝堂課程學生自行選擇
參、方法介紹與模式建立
一﹑遺傳演算法的源由
遺傳演算法即是由此生物進化論之論點出發，以電腦模擬自然界的演化方式，對既定問題求最佳解。
而這個觀念最早是於1968年由美國芝加哥大學賀蘭（JohnHolland）教授所提出，並於1975年出版《自然與人工系統中的適應》（Adaptationinnaturalandartificialsystems）一書，建立遺傳演算法的原型，發展了遺傳演算法的理論基礎。
二、遺傳演算法的運作
為了要利用電腦模擬生物演化的機制，首先是把問題變數編碼成字元（Character），來代表生物界中的基因。
而染色體（Chromosome）是由基因所組成，其又稱之為個體（Individual），故將每個問題變數所代表的字元串聯成一條字串（String）來加以模擬，並且這一條字串即是問題的可行解之一。
族群（Population）則為物種之集合，也是不同字串之集合。
每個物種在自然界中須面對著環境中的各項挑戰與競爭，而經由「物競天則，適者生存」的理論下，淘汰不適合環境的物種，留下更適合的物種。
為了模擬生物界的適應的架構，將對問題建立一個適應函數（FitnessFunction），來評估每個字串的適應能力。
三、排課問題模式建立
其中限制函數可視為硬限制，滿足所有硬限制之解即為可行解。
●一位教師在同一時段中不能上兩門課。
●一個班級在同一時段中不能同時排兩門課。
而適應函數可視為軟限制，其彈性較大。
本研究設定之軟限制為：
●老師一天之中上課堂數。
●老師一天之中連續上課堂數。
●老師課程大部分在上午或下午。
●3學分的課分段上或一次上完。
●早上8點（第一節）是否排課。
●下午4點以後（最後一節）是否排課。
●中午12點（第五節）是否排課。
首先將課表加以編碼，並輸入符合硬限制式所需之個數，且利用電腦隨機產生初始合理解；再輸入每個問題之權重，藉由軟限制式給予每個合理解（染色體）加以評分，判斷其優劣，挑選出優與最優的兩條染色體，進行複製，然後輸入遮照數使其交配，產生四個子代，再予判斷是否進行突變；再挑出優與最優的染色體，然後做抉擇，如果滿足停止條件，則輸
出結果；如果不滿足，則回頭至交配處理，反覆執行。
四、產生初始族群
初始解必須滿足訂定的硬性限制式，而產生之方式是以亂數隨機產生。
因過程中填入課表之程序為隨機的方式，故實際產生初始族群中之各初始解差異十分顯著。
五、定義適應函數
本組把各項軟性限制式給予特別之權數，並以累加的方式，訂定適應性函數值。
染色體之適應性函數越高，表示其對應之課表越優良。
適應函數定義如下：
n
i=1
P=ΣWi×Ci……………………………公式
（1）
六、亂數產生器
本系統在運算交配、突變時皆會採取以亂數產生，因而本系統採用了統計學上的均勻分配法，以期可以得到隨機之亂數。
七、定義複製運算
本研究所採行的方式為「競爭式」，其步驟為先將世代中之染色體依適應函數值之大小排序，挑選其中最大的2條染色體，依其相同之權重複製至下一世代。
八、定義交配運算
本系統所採用的交配方法是遮罩交配。
因為我們使用的編碼方式是採用真實值編碼，比起傳統二元編碼組內變異較小，故希望能夠透過遮罩交配將基因打散，且保持原有基因的特性，讓求出的解不要落入區域最佳解。
九、定義突變運算
為了讓染色體在演化的過程中不陷入一侷限的範圍，所以需要做突變。
十、訂定停止規則
本研究所採用的停止規則為下，當其中一點滿足時，則停止演算。
●電腦的運算處理時間到達預設值。
●到達最佳解，即染色體的適應函數值到達預設之最高值。
●電腦在搜尋時間內找不到任何初始解。
以遺傳演算法解決課程排課的問題
肆、排課模式之評估與實驗比較
一、問卷
本小組這次的排課系統研究範圍是以工業管理學系為範圍。
經由與受訪者的溝通蒐集資料。
經過運算之後，算出每一限制式之權重，可編製其權重表如下
限制項目
選項
權重
總權重
1
老師一天之中希望上課幾堂課
1-2堂
7.5
77.5
3-4堂
69.79
5-6堂
0
7堂以上
0
2
一天之中對於課程連續排課的意願
連續兩堂
31.25
62.5
連續三堂
31.25
連續四堂
0
3
一天之中希望上午或下午上課
課程大部分在上午
5.25
52.5
課程大部分在下午
5.25
平均分配
42
4
若有三學分的課希望怎麼分配
3堂連續上課
58
72.5
2+1堂（分兩天上完）
14.5
無所謂
0
5
早上8點（第一堂）是否希望排課
希望
0
67.5
不希望
67.5
無所謂
0
6
下午4點（最後一堂）是否希望排課
希望
0
47.5
不希望
47.5
無所謂
0
7
中午12點（第五堂）是否希望排課
希望
0
70
不希望
70
無所謂
0
二、實驗設計
在本實驗中我們假設不考慮教室的屬性與數量。
亦就是說我們假設一個學校中有足夠的教室可供給我們排課。
在課程方面，每門課分別由同一教師來教授；在學分方面，我們假定每一學分均為一堂課。
希望能排出工管系四個年級，每個年級A、B、C三班，共12個班級的課表。
在我們考慮的因素中，我們以工管系為例，將班級定為A、B、C三個班級，教師名稱設定為目前工管系的實際情形。
三、實驗
GAModel（ＧＡ組）
在我們所撰寫的程式中對於遺傳演算法的參數做了以下這些設計。
●權數：
由表4.1之權重表說明各個條件限制式的重要性與權重。
我們將計算出來的權數置入程式中，讓電腦作為判斷我們課表好壞之依據。
●演算時間：
輸入演算之時間（本實驗為50、100、150、200、250、300、1000秒）。
●起始解個數：
輸入所希望的起始解個數（本實驗設定為50個）。
●交配率：
我們必須要確實的執行交配的動作，以觀察交配之後所得到的結果，所以在這裡我們將交配率定為50%。
●突變率：
突變的步驟用來確定最佳解是否被侷限在部分解裡面。
而我們在這裡將突變率定為10%、20%、50%、100%，也就是0.1、0.2、0.5、1。
經過以上繁雜的設定，我們才可以利用基因演算法來求解產生課表。
亂數Model（亂數組）
亂數組的程式輸入值所需變動的只有時間值，其演算的方式皆為亂數隨機排入。
●演算時間
輸入演算之時間（本實驗為50、100、150、200、250、300、1000秒）
最後我們把在各個時間點上，GA組與亂數組所得到之最佳解作一圖表（見表1）之分析，即可看出兩者最佳化之趨勢。
表1:
GA組與亂數組對應[時間-最佳解]一覽表
50秒
100秒
150秒
200秒
250秒
300秒
1000秒
亂數
82.03
83.9
88.45
90.9
91.4
93.41
97.93
遺傳
242.6
332.1
372.4
401.8
431.1
447.4
497.77
四、實驗差異檢定
為了比較在S秒時，使用GA產生的課表之平均分數是否優於亂數所產生的課表？
首先，使用亂數隨機產生NX（NX>=30）張課表，其NX張課表評分為X1、X2、X3、、、XNX，再使用GA方法隨機產生NY（NY>=30）張課表，其評分為Y1、Y2、Y3、、、YNY，且兩組資料也為兩組獨立樣本，由於母體變異數σx2與σY2無法得知，故以樣本標準差sx與sY，取代σx、σY，至於左尾檢定H0﹕μX≧μY對H1﹕μX＜μY，令z=（
—
）/√（sx2/NX┼sY2/NY），其棄卻域為z＜-zα。
並藉由EXCELE軟體執行ｚ檢定，其結果如下表（見表2）：
表2:
檢定結果
亂數
GA
平均數
97.930191
497.77449
變異數
34.89292
317.10593
觀察值個數
30
30
z
-116.72958
P（Z<=z）單尾
0
臨界值：
單尾
1.6448535
以遺傳演算法解決課程排課的問題
其中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可看出，GA組課表分數隨著時間的增加，呈現著成長的趨勢；而亂數組則呈現時而成長時而下滑的無規則隨機散佈。
圖1GA組課表分數趨勢圖圖2亂數組課表分數趨勢圖
●最佳解趨勢
從下圖3與圖4可看出，GA組因則優交配，所以一直會有更加解的出現；反觀亂數組則時常會有陷入長時間找不到更加解的窘境。
在1000秒之內，GA組之最佳解為334.8分，而亂數組則為99.2分。
圖3GA組最佳解趨勢圖圖4亂數組最佳解趨勢圖
●所得課表
我們以工二C之課表為例，從下圖5與圖6，我們可個別算出GA組與亂數組的分數。
1.連課分數=連課數×連課權數
G.A.連課分數=6×6.2=37.2
亂數連課分數=3×6.2=18.6
2.第一堂不排課分數=第一堂均不排課×不排課權數
圖5GA組[工二C]課表圖6亂數組[工二C]課表
●時間-最佳解之比較
最後我們把在各個時間點上，GA組與亂數組所得到之最佳解作一圖表（見表3）之分析，即可看出兩者最佳化之趨勢其GA組與亂數組對應之“時間-最佳解趨勢”，如圖7。
表3:
GA組與亂數組對應[時間-最佳解]一覽表
50秒
100秒
150秒
200秒
250秒
300秒
1000秒
亂數
82.03
83.9
88.45
90.9
91.4
93.41
97.93
遺傳
242.6
332.1
372.4
401.8
431.1
447.4
497.77
圖7:
GA組與亂數組對應[時間-最佳解]趨勢圖
以遺傳演算法解決課程排課的問題
伍、結論和未來展望
本章節將針對本小組所做的研究，包括研究過程、架構分析、模型設計及實驗結果等等，歸納出研究結論，並提供可以參考之建議。
讓未來有興趣繼續深入此一問題的後續者，能夠參考本研究而發展出更完善、效用更為顯著的排課系統。
雖然本研究是針對某一些特定的限制條件進行的研究，但是其建構出來的模型，在我們設定的情況下也可達到不錯的〝最合適〞目標之結果，亦能滿足授課老師對於排課上不同的喜好及意願。
本研究的特色在於將蒐集到的相關排課資料整理齊全後，藉由電腦程式語言撰寫模型。
概略的說，第一，模型雖然不是盡善盡美，但對於解決排課問題，至少還能得到一個令人可以接受的結果；第二，雖然模型排出來的不是最佳的課表，但其能輔助排課人員在遵行一定的規則下，將課表排出；第三，模型可產生許多〝最合適〞的課表，可供排課人員參考；第四，本模型能將原本排課的速度加快，使得排課人員有更多的時間找出其他的問題。
在傳統人工排課中，排課人員往往簡化起見，常常將課表就從第一班開始排起。
接著依班級順序排出，使得第一班通常擁有較好的排課內容，而最後一班只能從授課老師其餘的時間來安排課表，這為不公平之一，老師也沒有多大的選擇性。
相對於本組以遺傳演算法進行排課系統的研究，所產生出來的課表，不僅節省排課人員相當多的時間，在課表選擇性的空間相對的提高，而各班的課表同時產生，也比較公平。
未來展望
總結來說排課原本就是一個複雜又困難的工作。
既要同時滿足老師的需求又要使學生覺得滿意，幾乎是不可能的。
本系統也有許多未盡完善之處，在未來可再加以深入琢磨：
●加入教室因素
●考慮學生意願
●排入全校課表
●人性化使用介面
這些都是未來能進一步研究的方向，將來後續研究者可發揮的空間，進而達到真正自動化排課的資訊系統。
參考文獻
1.王本耀、曾國雄，”工研院育成中心新進廠商申請進駐評審模式研究”，國立交通大學科技管理研究所，碩士論文，民國92年2月1日。
2.王怡仁，”電腦撫助之排課系統”，雲林科技大學工業工程與管理技術研究所，碩士論文，民國81年
3.王進德、蕭大全，”類神經網路與模糊控制理論入門”，全華書局，民國90年
4.包冬意，”大專院校排課自動化之研究”，大業學報，第二卷，第一期，民國82年12月，第135-144頁。
5.向殿政男作/劉天祥譯，FUZZY理論入門，中國生產力出版公司，日本，民國80年
6.邱元泰，”遺傳演算在排課問題之應用”，國立中正大學數學研究所，碩士論文，民國91年７月。
7.沈正慈，”電腦排課”，元智大學電機暨資訊工程研究所，碩士論文，民國88年。
8.金國忠，”依規則為基礎的排課系統之研究”，淡江大學管理科學研究所，碩士論文，民國74年6月。
9.周鵬程，遺傳演算法原理與應用-活用Matlab，全華科技圖書股份有限公司，台灣，民國91年
10.楊振興，”大專院校排課之探討—以數學規劃為研究工具”，台灣，民國九十一年，第10-19頁
11.戴佳恩、何秋萍、陳彥偉、宋恩生，「人工智慧與類神經網路簡介」，民國89年2月建置，存取於2002年10月。
12.陳志昇，”大專院校電腦化之研究”，國立成功大學工業管理學系，碩士論文，民國73年6月。
13.駱至中、方志成，”向政治學與社會科學借法取經的新世代人工智慧（遺傳演算）”，佛光人文社會學院資訊學研究所，民國91年5月9日
14.韓復華、陳柏榮、王國琛，”應用限制規劃求解排課問題：
以交通大學全校性課程排課為例”，中華民國第六屆運輸網路研討會論文集，中華民國，民國90年11月，第33-42頁。
15.A.Hertz.Findungafeasiblecoursescheduleusingtabusearch.DiscreteAppliedMathematices,35（3）:
p255-270,1992.
16.D.deWerraRestricedcoloringmodelsfortimetabling.DiscreteMathematics,p161-170,1997.
升级会员 