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