【正文】 如表 414所示 表 414 專業(yè)必修課的期望值 Table 414 fitness of Professional pulsory course 時間片 11 21 1 17 、 22 1 18 、 23 1 124 1 25 期望值 10 8 4 2 0 如表 415 所示 表 415 公共課和選修課的期望值 Table 415 fitness of proficient and selective course 時間片 1 1 2 1 1 24 1 17 、 22 1 18 、 23 1 25 期望值 2 8 10 0 如表 416 所 示 表 416 體育課的期望值 Table 416 fitness of sports course 25 時間片 1 1 2 1 2 2 25 1 122 118 119 期望值 0 4 8 10 如表 417 所示 表 417 實驗課和語音課的期望值 Table 415 fitness of experiment and Speech course 時間片 1 12 2 225 1 122 1 18 119 120 期望值 0 4 6 10 8 前面四種期望值的計算方式是遍歷一個個體，檢查它的課程性質(zhì)，判斷它是哪種類型的課程，當(dāng)為 10000000 時表示專必課，算出它的適應(yīng)度值加在 F1 中，為 11000000 和 11100000時表示專選課和公共課，算出它的適應(yīng)度值加在 F2中，為 11110000 和 11111000、 11111110時表示上機實驗課和專業(yè)實驗課、語音課，算出它的適應(yīng)度值加在 F3中，為 11111100 時表示體育課算出它的適 應(yīng)度值加在 F4 中。以老師為對象，首先檢測老師所上的課是否有重復(fù)的情況。如此循環(huán) bjs 次，產(chǎn)生了與班級數(shù)目對等的染色體數(shù)目。 20 為了解決“特定資源”沖突問題，可在 教師編碼中加上 2B 表示該教師所教授的課程的性質(zhì)。消除冗余數(shù)據(jù)雖然能提高空間的利用率，但同時也會提高檢索的代價，因此，這三方面必須權(quán)衡，選擇一個折中方案。 表 22 約束表 Table 22 constraint table 基本硬約束 B1 同一時間，同一班級不能上兩門不同的課程 B2 同一時間，同一個教師不能上兩門不同的課程 B3 同一個時間，同一個教室不能上兩門不同的課程 硬約束 H1 課程的學(xué)時 在每周要均勻化 H2 滿足每門課的特定教學(xué)資源 H3 教室足夠大，能夠容納學(xué)生 H4 某些課程要 特定 安排 ，如 某些教師的課程要固定 H5 教師學(xué)生上課不能用于在路途 上的奔波 H6 體育課盡量安排在下午 軟約束 S1 課程的分布要做到離散化 S2 一周有些時段處于最佳利于學(xué)習(xí)時間 S3 盡量不讓老師連著上課 S4 班級相鄰上課地點盡量近些 9 模型 問題陳述 設(shè)課程集合： L={l1， l2， ..... lA}；班級集合： C = {c1， c2， .......， cB}；教室集合： R = {r1， r2， .....， rQ}；教師集合： S={s1， s2， ......， sK}；時間集合：T={t1， t2， ......tD}[2]、 [4]。 另一個功能，學(xué)院在這塊可以查詢本學(xué)院的課表，還有學(xué)院內(nèi)班級的課表。每門課程都有指定的教室類型。開始算法設(shè)計的基礎(chǔ) 是 對這些數(shù)據(jù)之間的問題的透徹分析和適當(dāng)?shù)奶幚怼? 本文根據(jù)高校開課的具體情況，采用優(yōu)化的編碼方案，滿足排課過程中的一些硬性和軟性約束因素，利用遺傳算法對課表進行了優(yōu)化，從而得到了最終的無沖突、更人性的排課方案。本文將遺傳算法應(yīng)用于排課問題的求解中 ,采用基于輪盤賭算法的選擇操作方法和優(yōu)化的個體適應(yīng)度計算方法，滿足了排課過程中多部分軟硬約束條件，實現(xiàn)了各種類型課程的排課。將遺傳算法應(yīng)用于排課問題中，首先，初始化課表種群，其次，檢測初試種群中的沖突，然后，對種群做選擇，雜交，突變操作，一直迭代到具體指定的代數(shù)，最后就會得到較優(yōu)解。 (4)把上一步排出的結(jié)果 與 位置表結(jié)合，就完成了課表的安排 ，中間整個過程都要解決沖突問題。我們在此系統(tǒng)的排課都是按 一個大節(jié) 開設(shè)的，符合按 25 個時間片劃分的設(shè)計，但確有少量的課程的周學(xué)時數(shù)為單數(shù)，如“ 3 學(xué)時”或“ 5 學(xué)時”， 在此 仍按“ 4 學(xué)時”或“ 6 學(xué)時”進行編排，雖然這會浪費一小節(jié)課程 。 根據(jù)業(yè)務(wù)分析和數(shù)據(jù)分析，可得出排課系統(tǒng)主要完成以下幾個功能 : 院管理模塊 這一模塊首先是每個學(xué)院從教學(xué)計劃中安排自己學(xué)院的開課任務(wù)書，具體就是對本學(xué)院課程和教師的安排。其中基本硬約束是指教師、學(xué)生和教室在時空概念上發(fā)生了不可能發(fā)生的事情， 既是時間，空間 ，人之間的矛盾， 它是排課過程中最基本的約束條件，也是眾多排課模型中都 要 涉及的約束條件 ； 硬約束是 根據(jù) 學(xué)校的實際情況，排課時必須遵循的原則，否則將會導(dǎo)致排課結(jié)果無意義 ， 8 所以要因地制宜； 軟約束是指排課過程中滿足更佳但不滿足又無妨的約束條件， 這些條件的目的就是使課表更加人性化，每個排課都是要突出解決軟約束這個問題的，違背這些約束就與實際情況相悖 。對于排課問題要進行的分析主要有 :教學(xué)計劃、各學(xué)院教學(xué)任務(wù)、教室基礎(chǔ)數(shù)據(jù)、時 間模式、開課任務(wù)、及各種課表等數(shù)據(jù)。這也反應(yīng)了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。首先把固定教學(xué)時間的教師編碼填入該行中，然后使用隨機函數(shù)產(chǎn)生一個 1— 25的數(shù)，將該班的其它教師編碼填入其中。//后 25 位來標(biāo)識教師一周上課情況， 1為有課， 0 為無課 //前 7位來表示教師的每周課的總節(jié)數(shù) unsigned char TagForRepeat[4]。適應(yīng)度值實際上反映了排課人員對課表理想化編排的一種期望。 本文選用隨機單點交叉模式，如下圖示。 (3)雜交率 Pz 將被選個體進行兩兩配對，若配對中的父本個體的適應(yīng)度值不相等，則進行雜交，雜交后的子代與父本進行適應(yīng)度值的比較，選擇適應(yīng) 度值較大的二個個體進化到下一代中。個體數(shù)較多的種群中最有個體要比個體數(shù)較少的具有更高適應(yīng)度值，實驗結(jié)果令人滿意，證明了利用新的二進制編碼和教室填充方法是可以的。 不積跬步何以至千里，本設(shè)計能夠順利的完成，也歸功于 四年來 各位任課老師的認(rèn)真負(fù)責(zé)，使我能夠很好的掌握和運用專業(yè)知識，并在設(shè)計中得以體現(xiàn)。注意一點，每列都是用所有的教室去填充，而不是上次填充剩下的。對于每一類期望值及其在總的期望 值中的比例，都可以根據(jù)每一所學(xué)校的具體情況進行必要的調(diào)整，使排課系統(tǒng)更加實用、有效。找到這些為 1 位的對應(yīng)的班級的課的教師，將這些教師的 TEACHER_INFOR::HavingClass與第有重復(fù)課的教師的 TagForRepeat的后 25位相比較，比較 TagForRepeat 為 1 的位，前者是否 為 1，任意一位為 1則重復(fù)第六步的內(nèi)容，直到都不為 1為止，則這樣的教師為滿足條件的交換教師。因為對于同一時間，一個班級同時上一門以上課程的沖突，在編碼的過程中己經(jīng)避免，不會發(fā)生 。功能室 (實驗室機房、語音室等 )已經(jīng)在編碼時分配好，而理論課的那些，要等到后面再去分配。 (4)迭代第四步，直到進化停止，就是 generation=終止代數(shù) N。 圖 33 排課系統(tǒng)數(shù)據(jù)流圖第 3層 Chart 33 the third layer of timetabling system data flow chart 正如數(shù)據(jù)流圖的第二層所示，數(shù)據(jù)分流后，在此模塊，學(xué)院會根據(jù)自己學(xué)院的特殊情況 11 完成學(xué)院的開課任務(wù)書，所謂開課任務(wù)書，既 是課程、班級和老師的組合，還沒有結(jié)合時間和地點此二維因素，僅僅表達(dá)此班上哪位老師講授的哪門課程的問題。 此圖描述了功能模塊圖，如圖 22 示： 7 圖 22 功能模塊圖 Chart 22 the function model chart 排課是將教師與學(xué)生在時間和空間上根據(jù)不同的約束條件進行排列組合， 在此同時也要安 排課程， 以使教學(xué)正常進行。 (5)“特殊課”問題：像體育課，要跟硬件設(shè)施有關(guān)，故要妥善處理。 (5)晚上 9, 10 節(jié)課 7:309:10。 分析一般高校的排課流程，其過程將如下， 下面將排課整個流程作個介紹 : (1)各學(xué)院從教學(xué)計劃中導(dǎo)入開課任務(wù)書，讓各學(xué)院安排好教師及教師的各種相關(guān)要求，比如班級、教室類型、時間類型等。 Classroom Arrangement。 Timetabling。要想編排好學(xué)校的課程表，需要綜合考慮學(xué)校的教師、教室、學(xué)生、班級、時間等多方面因素，反復(fù)調(diào)整，避免沖突 。 (4)下午 7, 8 節(jié)課 4:205:50。 (4)“固定課”問題 :有的教師因為某些原因需要安排特定的教學(xué)時一段，如 教室受到其他課程的影響，或者 某學(xué)院部門領(lǐng)導(dǎo)，因工作性質(zhì)關(guān)系，須指定安排上課時間為“星期五的第 6節(jié)”，這樣的要求在編排課程表時必須滿足，即“ 固定 時段”問題。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當(dāng)然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。 圖 32 排課系統(tǒng)數(shù)據(jù)流 第 2 層 Chart 32 the second layer of timetabling system data flow chart 根據(jù)登錄者不同的身份，進入不同的功能模塊，分別進行不同的操作，學(xué)院身份進入圖33的學(xué)院管理模塊，落實學(xué)院開課任務(wù)書，教務(wù)處身份進入圖 15的校管理模塊，匯聚校開課任務(wù)書，并且進行排課。 (3)遺傳操作 :包括選擇 算子 、交叉 算子 和變異 算子，產(chǎn)生子代，逐漸優(yōu)化。在大多數(shù)，每周上 6學(xué)時的課程不會太多，大多數(shù)時 4 學(xué)時和 2 學(xué)時； 通過以上把課程與教師等同的處理后，原課表的五要素 (班級、教室、課程、時間、教師 )轉(zhuǎn)化為四要素 (班級、課程、時間）和班級。 關(guān)聯(lián)容器的使用方法如圖 47 所 示： 22 圖 47 容器結(jié)構(gòu)圖 Chart 47 vessel structure chart 完成種群初始化后，個體的數(shù)據(jù)結(jié)構(gòu)如下圖示： 圖 48 個體結(jié)構(gòu)圖 Chart 48 individual structure chart 沖突檢測及排除 對每一個課程表二維數(shù)組 kcb (25,bjs)進行沖突檢測，然后用自動定位變異算子消除沖突。 (6)取其中任意的重復(fù)課數(shù)且為 1的位。而適應(yīng)度函數(shù)值越大，則課程表的安排越合理、有效。 (2)選擇率 為使優(yōu)勢個體的特性得以保留， 應(yīng)確保適應(yīng)度值高的優(yōu)良個體被選入下一代，故構(gòu)造如 29 下選擇率及選擇數(shù)計算公式： 期望的選擇率： Pselect=Fit(i)/FitSum 其中 Fit (i)為某個個體適應(yīng)度值， FitSum 為種群的適應(yīng)度值總和， i=1, 2, 然后處理班級 +教師 +課程 +時間片記錄，先讀取第一列，依次判斷每行是哪種課程屬性，還有就是判斷就看它是哪個班級，用指定的教學(xué)樓里的教室去填充它（當(dāng)然得根據(jù)教師和班 30 級的情況，例如人數(shù)問題），如果不是，就檢查下一行，直到處理完這列； 對上面的處理迭代執(zhí)行，直到 25個時間片都處理完。 這將是我大學(xué)四年里一段十分美好的回憶。 39 在本文中，遺傳算法被充分應(yīng)用在排課中，對使用遺傳算法研究及實現(xiàn)排課系統(tǒng)的編碼模式進行了深入地討論，以對課表進行最大優(yōu)化為目標(biāo)，對傳統(tǒng)編碼模式進行了修正和改進。本文將用此策略進行雜交遺傳，這樣可以保證將好的個體保留到下一代。隨機選擇一個數(shù)， 滿足條件就交換此點的染色體。因此，如何把這些“期望 ”轉(zhuǎn)化為具體的“值”，是使排課系統(tǒng)得以智能化的關(guān)鍵所在。//后 25 位作為掩碼來表示有重復(fù)課的時間 //片，前 7 位用來標(biāo)識重復(fù)課的總節(jié)數(shù) }TEACHER_INFOR。如產(chǎn)生的隨機數(shù)對應(yīng)的時間片中己有數(shù)據(jù)，則重新產(chǎn)生，直到將所有教師編碼無重復(fù)地填入該行中。 我們給了 15bit去表示教師 ， 15bit能表示 215個數(shù)，足矣滿足任何一所高校的教師編號，所以，在數(shù)據(jù)庫里，教師表里教師編號的數(shù)據(jù)項要為短整型。 這些關(guān)系用 ER 圖表示如圖 41， 42， 43: 圖 41 院管理 ER圖 Chart 41 the ER chart of college management 13 圖 42 校管理 ER圖 Chart 42 the ER chart of school manageme