畢業設計學分制模式下基于遺傳算法(編輯修改稿)

　

【文章內容簡介】 的班級數及課程開設的校區等。(3) 教室因素 每個教室都有教室編號，教室代號及所屬的教學區域。每個教室都有教室類型，教室類型包括普通教室、多媒體教室、語音教室、實驗室、機房、體育館等。每個教室都有一定的容量，教室的容量必須不小于上課的人數。(4) 教師因素每個教師都有自己的編號及姓名，每個教師都隸屬于一個學院，教師可以對上課時間提出自己的特殊要求。同一時間老師只能上一個教學班的課。(5) 班級因素本文所涉及的班級均指的是教學班（選課班或行政班）。如前面的分析，教務處下達的教學任務書里規定了開設的課程名稱、班別、開設的校區等。其中課程名稱，班別，校區編號唯一決定一個選課班。每個選課班都有一個的最大選課人數的限制。(6) 校區因素每個校區都有編號和名稱。其中蛟橋園編號為“A”，麥廬園為“B”，楓林園為“C”。當老師、學生在不同校區上課時，應該留有一定的時間用于趕赴。根據江西財經大學課間時間的安排，上午兩個時間段之間留有40分鐘的時間，上午跟下午，下午跟晚上的上課時間間隔在90120分鐘之間，所以趕赴的時間本文不予考慮。 排課的約束條件排課問題中，主要任務是將班級、教師、課程安排在一周內某一不發生沖突的時間和教室，保證課表在時間的分配上符合一切共性(時間上不存在沖突)和個性(不與老師的特殊時間要求沖突)的要求，在此基礎上，使其安排在各個目標上盡量達到最優。一張可行的課表首先要滿足排課因素的約束。這里的約束條件主要是避免沖突。只有在滿足全部約束條件和避免所有沖突的基礎上，才能保證整個教學計劃合理正常進行。對教師、班級、課程、時間、教室等幾部分資源進行最優化配置，才能保證排課的順利完成以及充分發揮各個資源的優勢以達到提高管理水平和教學質量的目的。根據是否必須滿足，我們可以將約束條件分為硬約束和軟約束。硬約束是指教師、班級、教室、校區在時空概念上發生了不可能發生的事情，也就是發生了沖突。它是在排課過程中需要滿足的最基本的約束條件，是排課時必須遵循的原則，否則將會導致排課結果無意義。軟約束則是指排課過程中若滿足則更佳，不能滿足也不影響教學的開展的約束條件。它能夠使課表更加合理，更加具有人性化[16]，它影響排課結果的好壞。通常，排課方案的標準有多個，以下是按照江西財經大學的校情制定的約束條件。(1) 硬性約束條件① 同一時間同一班級只能上一門課；② 同一時間同一教室只能上一門課；③ 同一時間同一教師只能上一門課；④ 教室的容量必須不小于或等于實際上課的人數；⑤ 所分配的教室類型必須與課程所要求的教室類型一致；⑥ 課程必須安排在教學任務書所規定的校區。(2) 軟性約束條件① 每個時間段安排的課程數盡量均勻；② 一周的課表中每個上課時間都有一定的優度，盡量將課程安排在優度高的時間段；③ 一門課程的多次上課的時間盡量間隔并分布均勻；④ 教室容量適中，以充分利用教室；⑤ 兩個課時的課程盡量不要安排在下午或晚上，以免造成一個課時的浪費。4 基于遺傳算法的排課算法的描述本文前面已經對遺傳算法、排課流程、排課因素及排課的約束條件進行了分析，下面結合上述分析將遺傳算法具體應用到排課算法的設計過程中。 排課問題的目標分析根據江西財經大學的校情，本文確定了五個目標，分別為：教室利用度、節次優度、課程日組合優度、時間片利用度、課程的時段分布均勻度。下面分別介紹這五個目標[17]。(1) 教室利用度教室利用度，是衡量所開設的課次的教室利用程度的好壞標志。其計算方法如下： ()式中 ——所有課次的教室利用率的平均值 ——第i個課次的教室利用率 ——課次總數值越大，我們認為排課方案的教室利用率越高。(2) 節次優度節次優度是對某一時間片上課效果好壞的量化。我們為每一個時間片賦予不同的優度值以表示對這個時間片的偏好程度。節次優度含有一定的主觀因素，每個人對同一時間片的偏好不同，不同的季節同一個時間片的上課效果也會有差別。我們可以讓排課人員來設置每個時間片的節次優度，以體現不同人，不同學期的要求。如學年的第一個學期進入到冬季時，上午2節比4節的節次優度可能低些，因為天冷部分同學不愿早起上課。第二學期進入到夏季時，下午的時間片的節次優度要低些，因為此時上課，效果會差些。本系統采用的節次優度值如表31所示。表41 節次優度表時間片星期一星期二星期三星期四星期五上午2節上午4節下午7節晚上A節我們用全校課程的節次優度的平均值來衡量排課方案中節次安排的好壞，即對開課方案中每個課次的節次優度進行累加，再除以總的課次數。 (42)式中 ——全校課程的節次優度的平均值 ——第i個課程的第j個時間段的節次優度 ——第i個課程的時間段的個數 ——所開設的課程的總數的值越大，我們認為排課方案的節次優度越好。(3) 課程日組合優度課程的日組合優度，是衡量每周上課次數大于1的課程的多次上課的日組合優度好壞的標志。我們對所有的課程的日組合優度進行優度判定。例如：一個周學時為6的課程，每周上課3次，每次兩個課時，如果這三個時間片分別為周一的2節、周三的4節、周五的2節或者周一的4節、周三的2節、周五的4節，則我們認為該課程的日組合優度為1。如果一門周學時為4的課程，分別安排在周二的4節、周三的2節。當然，有些課程屬于例外，例如兩節理論假兩節實驗則可以間隔較短的時間；有些課程設計則需要連續進行。我們可以利用全校的所有周上課次數大于1的課程的日組合優度的平均值來衡量課程表中日組合優度的優劣。 ()式中 ——全校所有周上課次數大于1的課程的日組合優度的平均值 ——課程i的日組合優度 ——周上課次數大于1的課程總數值越大，說明課表中非2課時的課程日組合優度越大。(4) 課程時間片利用度課程的時間片利用度，是衡量該課程的每次上課對所分配的時間片的利用情況的標志。例如：一個周學時為2的課程，如果為其分配的時間片是在上午(2節或4節)，則其時間片利用度為1，如果在下午或晚上，則會造成一節課時間的浪費。 ()式中 ——所有課程的時間片利用度的平均值 ——課程i的第j個時間片的利用度 ——課程i的所分配的時間片的個數 ——所開設的課程的總數的值越大，說明課表的所有課程的時間片利用度越高。(5) 課程時間段分布均勻度課程的時間段分布均勻度的作用是使每個時間段所安排的課程的數目相對均勻，避免出現某個時間段的課程過于集中，某個時間段沒有課的現象。如果安排在每個時間段的課程的數目越均勻，同樣數目的課程對資源的需求就越少。課程的時間段分布均勻度為： 其中 ()式中 ——課程的時間段分布均勻度 ——每個時間段開設的課程的平均值 ——第d個時間段開設的課程總數我們用全校課程的時間段分布均勻程度的平均值來評價開設的課程的日分布均勻程度。的值越大，我們認為課程表中每個時間段安排的課程的數目越均勻。 排課系統中的基本算法 排課算法的面向對象的應用排課系統的實現采用C語言，利用面向對象的方法[1824]。在實現時，考慮到排課因素，約束條件的表現，定義如下的類(只給出各個類的字段的定義)：(1) 課元信息類為了記錄課程、教師、班級、開課校區、教室類型的要求、班級人數、周學時等信息，我們建立了相應的課元信息類，用來保存從數據庫讀取得每個教學任務中的上述信息，一個課元就相當于一個教學任務。在排課時，所有課元作為靜態數據，為排課算法提供相應的信息。public class CourseUnite { internal int CourseUniteNo。 //課元編號，主鍵 internal string CourseNo。 //課程編號 internal string TeacherNo。 //教師編號 internal string ClassNo。 //班級編號 internal char CampusNo。 //開課校區編號，A：蛟橋園//B：麥廬園 C：楓林園 internal sbyte RoomType。 //教室類型編號：多媒體1：機房//2：實驗室 3：語音室4：普通教室 internal int ClassCapacity 。 //班級人數編號 internal sbyte WeekTime。 //課程周學時 }(2) 基因基本信息類排課的任務就是為每個教學任務 (課元)安排一個合適時間和教室?；蛴脕碛涗浢總€課元的具體安排的信息。本文在給課元安排教室時，只考慮了同一課元被安排在一個教室的情況。 public class Genetic { internal int courseuniteno。 //課元編號 internal int roomno。 //教室編號 internal sbyte[] timeno=new sbyte[3]。 //時間片數組 }(3) 教師特殊時間要求類老師可能由于工作方面的原因，在一周內的某個時間段不能安排課程。考慮到這種情況，我們創建了教師特殊時間要求類，記錄老師不能上課的時間段。同時，為方便檢測同一老師同一時間只能上一個班課的約束，創建了一個記錄教師上課時間安排的數組。public class TeacherTime //創建教師特殊時間類 { internal int TeacherNo。 //教師編號 internal string canottime。 //教師不能上課的時間對應的字符串 //創建老師上課時間安排數組，取值為1表示該時間段已經安排//課，否則為0；若112節安排課，則arrangetime[0]=1。internal sbyte[] arrangetime=new sbyte[20]。 }假如，信息管理學院周四下午所有老師要開會，不能上課，其他時間都可以上課，則信息學院所有老師的canottime值為“O”。如果一名住在南昌市區的老教師，由于身體及上下班回家距離的限制，不能再晚上安排課，則將該老師的canottime字段設置為“DHLPT”。時間片對照表如表42所示。在排課系統初始化數據時，我們視老師不能上課的時間段為在該時間段老師已經安排了課程，這樣該時間段就不能再安排課程了。即首先根據某老師的canottime，設置arrangetime數組的值。如老教師的arrangetime數組的第1119個(編號從0開始)字段的值為1。表42 時間片對照表取值ABCDEFGHIJ時段1121341567189A2122342567289A312334取值KLMNOPQRST時段3567389A4124344567489A5125345567589A(4) 染色體適應度類為方便選擇操作中根據染色體適應度的大小對父種群進行配對操作以形成配對庫，我們建立了染色體適應度類，記錄染色體編號及其適應度值。public class FitnessValue //染色體適應度類 { internal int chromosomeno。 //記錄染色體號 internal float fitnessval。 //記錄染色體適應度 }(5) 教室基本信息類 在為課元安排教室的時候經常要查詢教室的容量、教室類型。為保存從數據庫讀取的教室的信息，我們建立了教室基本信息類。在排課時，為每個校區建立相應的教師信息表。public class ClassRoomInf//創建教室基本信息類 { internal int classroomno。 //教室編號 internal int roomcapacity。 //教室容量 internal short roomtype。 //教室類型 }