【正文】 重組基因(crossover/rebination)遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。教學(xué)任務(wù)書中要明確所要開設(shè)的課程、應(yīng)開設(shè)班級(jí)數(shù)目(班別)、課程開設(shè)的校區(qū)等信息。課程表包括全?？傉n程表、學(xué)生課程表、教師課程表和教室課程表。教學(xué)任務(wù)書下達(dá)到各學(xué)院后，學(xué)院根據(jù)自身教師情況，修改某些課程的班級(jí)數(shù)目及相應(yīng)的班級(jí)容量，之后為教學(xué)任務(wù)書添加老師，并提出課程對(duì)教室的要求，及學(xué)院老師對(duì)上課時(shí)間的要求(如某個(gè)時(shí)間段不能安排課程)，這樣就形成了課元信息。每天上午分兩個(gè)時(shí)間段(片)，每個(gè)時(shí)間段兩節(jié)課，下午和晚上各一個(gè)時(shí)間段，每個(gè)時(shí)間段三節(jié)課。(4) 教師因素每個(gè)教師都有自己的編號(hào)及姓名，每個(gè)教師都隸屬于一個(gè)學(xué)院，教師可以對(duì)上課時(shí)間提出自己的特殊要求。當(dāng)老師、學(xué)生在不同校區(qū)上課時(shí)，應(yīng)該留有一定的時(shí)間用于趕赴。硬約束是指教師、班級(jí)、教室、校區(qū)在時(shí)空概念上發(fā)生了不可能發(fā)生的事情，也就是發(fā)生了沖突。 排課問題的目標(biāo)分析根據(jù)江西財(cái)經(jīng)大學(xué)的校情，本文確定了五個(gè)目標(biāo)，分別為：教室利用度、節(jié)次優(yōu)度、課程日組合優(yōu)度、時(shí)間片利用度、課程的時(shí)段分布均勻度。如學(xué)年的第一個(gè)學(xué)期進(jìn)入到冬季時(shí)，上午2節(jié)比4節(jié)的節(jié)次優(yōu)度可能低些，因?yàn)樘炖洳糠滞瑢W(xué)不愿早起上課。如果一門周學(xué)時(shí)為4的課程，分別安排在周二的4節(jié)、周三的2節(jié)。如果安排在每個(gè)時(shí)間段的課程的數(shù)目越均勻，同樣數(shù)目的課程對(duì)資源的需求就越少。 //課程編號(hào) internal string TeacherNo。本文在給課元安排教室時(shí)，只考慮了同一課元被安排在一個(gè)教室的情況。 //教師編號(hào) internal string canottime。如老教師的arrangetime數(shù)組的第1119個(gè)(編號(hào)從0開始)字段的值為1。 //教室編號(hào) internal int roomcapacity。教室調(diào)度算法具體描述如下：(1) 初始化i=0，countfalse=0(記錄失敗次數(shù))；(2) 判斷i是否小于該校區(qū)教室的總數(shù)，若不小于則結(jié)束，沒有找到要求的教室，提示錯(cuò)誤；(3) 判斷第i個(gè)教室的教室類型、容量是否符合要求，若不符合，轉(zhuǎn)(6)；(4) 判斷countfalse是否小于50，若小于，判斷當(dāng)前時(shí)間下，該教室是否可用；若可用，轉(zhuǎn)(5)；否則重新產(chǎn)生一個(gè)可用的時(shí)間(該時(shí)間老師沒有安排課程)，countfalse=countfalse+1，轉(zhuǎn)(4)；(5) 判斷教室已占用的時(shí)間段數(shù)目是否小于15，若小于，則教室i在該時(shí)間段被分配且重置countfalse=0；否則轉(zhuǎn)(6)；(6) i=i+1，轉(zhuǎn)(2)。同時(shí)，對(duì)于周學(xué)時(shí)為3的課程(包括周學(xué)時(shí)位5的課程，為其安排的一個(gè)時(shí)間段)，必需保證安排在下午或晚上，如果在上午，則重新安排，轉(zhuǎn)(1)。所以這里的沖突檢測(cè)函數(shù)只要檢測(cè)同一時(shí)間同一教師是否只上一門課。本文根據(jù)排課問題實(shí)際，設(shè)計(jì)了有利于交叉操作，適合于排課問題的編碼方法。 初始種群的產(chǎn)生種群的大小是由用戶決定的。輪盤被劃分為不同比例的區(qū)域，這里的比例是根據(jù)個(gè)體適應(yīng)度的大小分配的。這樣采用優(yōu)秀個(gè)體和重新生成的新個(gè)體來替換存在沖突的被淘汰的個(gè)體，既可以提高種群的平均適應(yīng)度，又給種群帶來了新鮮個(gè)體，增加了種群的多樣性。第一步，對(duì)新一代種群中的染色體隨機(jī)兩兩配對(duì)(選擇操作中直接插入的5條除外)；第二步是隨機(jī)產(chǎn)生一個(gè)01之間的隨機(jī)數(shù)，并與事先確定的交叉概率進(jìn)行比較，以決定是否進(jìn)行交叉。將選中的時(shí)間片隨機(jī)變?yōu)橐粋€(gè)老師可用的時(shí)間片。C既保持了C/C++中熟悉的語法，還包含了大量的高效代碼和面向?qū)ο筇匦?。本文取蛟橋園、麥廬園、楓林園各1114個(gè)待排教學(xué)任務(wù)，共涉及18門課程、23名教師，共有51個(gè)課元信息，每個(gè)基因有3個(gè)字段，因此一條染色體共153個(gè)字段。5教師利用度權(quán)值6節(jié)次優(yōu)度權(quán)值7課程時(shí)間段分布均勻度權(quán)值8時(shí)間片利用度權(quán)值9課程日組合優(yōu)度權(quán)值 (1) 種群規(guī)模對(duì)排課效率的影響本文分三次實(shí)驗(yàn)，分別測(cè)試了種群規(guī)模為100、150、200時(shí)，遺傳效率的大小。交叉概率越大，則頻率越高。 (3) 變異概率對(duì)排課效率的影響在自然界中，生物產(chǎn)生變異(基因突變)的概率是很小的，正是因?yàn)槿绱?，種群在世代相傳。當(dāng)遺傳代數(shù)過高時(shí)，種群可能會(huì)出現(xiàn)大量同一個(gè)體，種群幾乎停止進(jìn)化，甚至可能出現(xiàn)退化。無沖突性是一個(gè)課程表必須滿足的首要條件。③ 人性化根據(jù)老師的具體要求對(duì)課表進(jìn)行編排，體現(xiàn)排課過程中人性化的考慮。自動(dòng)排課系統(tǒng)會(huì)盡量朝對(duì)稱方面優(yōu)化，但是結(jié)果往往會(huì)是周一的2節(jié)、周三4節(jié)、周五4節(jié)。主要成果有以下幾點(diǎn)：① 系統(tǒng)完整的分析了排課流程，排課問題涉及的因素，排課的約束條件及優(yōu)化目標(biāo)。② 在排課時(shí)，如何保證每個(gè)學(xué)生每個(gè)學(xué)期的必修課在時(shí)間安排上一定不沖突，以保證學(xué)生都能按照教學(xué)計(jì)劃的要求選到必修課也是進(jìn)一步研究的一個(gè)重點(diǎn)。不奮斗就是每天都很容易，可一年一年越來越難。⑤ 進(jìn)一步改進(jìn)和完善系統(tǒng)設(shè)計(jì)的各個(gè)方面，包括界面設(shè)計(jì)、數(shù)據(jù)交換等，力爭(zhēng)使系統(tǒng)達(dá)到實(shí)際應(yīng)用的目標(biāo)。在教室利用度、節(jié)次優(yōu)度、課程時(shí)間段分布均勻度、時(shí)間片利用度、課程日組合優(yōu)度五個(gè)因素組成的目標(biāo)空間上進(jìn)行求解，結(jié)果比較理想。6 總結(jié)與展望(1) 對(duì)本文工作的總結(jié)排課問題的實(shí)質(zhì)是為教師，學(xué)生的教學(xué)活動(dòng)合理的安排時(shí)間和教室，以保證教學(xué)計(jì)劃的順利進(jìn)行。而利用計(jì)算機(jī)系統(tǒng)排課，在設(shè)置好相應(yīng)參數(shù)后，只需要幾分鐘最多幾小時(shí)就可以排出可行的優(yōu)化的課表。同樣，對(duì)于學(xué)生來說，每次教學(xué)內(nèi)容學(xué)習(xí)完畢后，學(xué)生需要時(shí)間來消化學(xué)習(xí)內(nèi)容，進(jìn)一步理解和鞏固所學(xué)知識(shí)。 結(jié)果分析根據(jù)表51的參數(shù)的設(shè)置，本文進(jìn)行了5次測(cè)試，結(jié)果如表56所示。、遺傳效率的大小。、遺傳效率的大小。表52 種群規(guī)模對(duì)排課效率的影響(單位：秒)編號(hào)實(shí)驗(yàn)一(100)實(shí)驗(yàn)二(150)實(shí)驗(yàn)三(200)12345平均值由上表可以看出，當(dāng)種群規(guī)模增大時(shí)，最優(yōu)個(gè)體達(dá)到一定的適應(yīng)度所需的時(shí)間越短，遺傳算法的效率越高。表51 實(shí)驗(yàn)參數(shù)設(shè)置序號(hào)參數(shù)名稱取值及對(duì)目標(biāo)收斂的影響1種群規(guī)模取值較小時(shí)，目標(biāo)值波動(dòng)大，不穩(wěn)定，不能反映優(yōu)化各個(gè)目標(biāo)。SQL Server2000是新一代的大型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，作為微軟公司的產(chǎn)品可以和操作系統(tǒng)實(shí)現(xiàn)無縫集成，能對(duì)數(shù)據(jù)庫中的數(shù)據(jù)提供有效的管理，并采用有效的措施實(shí)現(xiàn)數(shù)據(jù)的完整性和數(shù)據(jù)的安全性。基于前面的排課目標(biāo)的分析，我們采用如下適應(yīng)度函數(shù) ()其中，、是由排課人員決定的，分別代表教室利用度、節(jié)次優(yōu)度、課程時(shí)間段分布均勻度、時(shí)間片利用度、課程日組合優(yōu)度的權(quán)值。在遺傳算法中，變異操作用于保證種群多樣性，防止搜索到的解陷入局部次優(yōu)解，并作為一種擾動(dòng)操作，有效抑制遺傳算法早熟。(2) 交叉操作的設(shè)計(jì)交叉，是遺傳算法中最主要的一種操作。在選擇操作中，創(chuàng)建類型為FitnessValue()的一維數(shù)組fitnessvalue，用來記錄染色體編號(hào)及其適應(yīng)度值。填充染色體的函數(shù)的具體實(shí)現(xiàn)如下：(1) 首先建立蛟橋園、麥廬園、楓林園三個(gè)校區(qū)的教室時(shí)間表，并初始化為0，表示沒有相應(yīng)的教室—時(shí)間對(duì)被占用；(2) 初始化每個(gè)教師的arrangetime數(shù)組各元素值為0，然后根據(jù)老師不能上課的字符串canottime將相應(yīng)arrangetime數(shù)組中相應(yīng)的時(shí)間段的值置為1。圖41 染色體編碼示意圖…………如圖41所示，代表第i個(gè)課元信息的課元編號(hào)，代表第i個(gè)課元分配的教師的編號(hào)，是為第i個(gè)課元分配的時(shí)間片。編碼方法確定后，遺傳算法通過對(duì)染色體編碼的操作，不斷搜索出適應(yīng)度高的個(gè)體，并在種群中逐漸增加其數(shù)量，最終尋找出問題的最優(yōu)解或近似最優(yōu)解。這樣填充的課表滿足所有的硬性約束，是一個(gè)可行的課表。 基因初始化算法基因是染色體的基本組成單位，在排課問題中，染色體相當(dāng)于一個(gè)課表，基因相當(dāng)于課表中的一個(gè)課元。建立了三個(gè)教室時(shí)間表，行為教室，列為時(shí)間段，用來記錄某個(gè)時(shí)間段某教室的占用情況。 //記錄染色體適應(yīng)度 }(5) 教室基本信息類 在為課元安排教室的時(shí)候經(jīng)常要查詢教室的容量、教室類型。如果一名住在南昌市區(qū)的老教師，由于身體及上下班回家距離的限制，不能再晚上安排課，則將該老師的canottime字段設(shè)置為“DHLPT”。 //時(shí)間片數(shù)組 }(3) 教師特殊時(shí)間要求類老師可能由于工作方面的原因，在一周內(nèi)的某個(gè)時(shí)間段不能安排課程。 //教室類型編號(hào)：多媒體1：機(jī)房//2：實(shí)驗(yàn)室 3：語音室4：普通教室 internal int ClassCapacity 。在實(shí)現(xiàn)時(shí)，考慮到排課因素，約束條件的表現(xiàn)，定義如下的類(只給出各個(gè)類的字段的定義)：(1) 課元信息類為了記錄課程、教師、班級(jí)、開課校區(qū)、教室類型的要求、班級(jí)人數(shù)、周學(xué)時(shí)等信息，我們建立了相應(yīng)的課元信息類，用來保存從數(shù)據(jù)庫讀取得每個(gè)教學(xué)任務(wù)中的上述信息，一個(gè)課元就相當(dāng)于一個(gè)教學(xué)任務(wù)。(4) 課程時(shí)間片利用度課程的時(shí)間片利用度，是衡量該課程的每次上課對(duì)所分配的時(shí)間片的利用情況的標(biāo)志。 (42)式中 ——全校課程的節(jié)次優(yōu)度的平均值 ——第i個(gè)課程的第j個(gè)時(shí)間段的節(jié)次優(yōu)度 ——第i個(gè)課程的時(shí)間段的個(gè)數(shù) ——所開設(shè)的課程的總數(shù)的值越大，我們認(rèn)為排課方案的節(jié)次優(yōu)度越好。(2) 節(jié)次優(yōu)度節(jié)次優(yōu)度是對(duì)某一時(shí)間片上課效果好壞的量化。通常，排課方案的標(biāo)準(zhǔn)有多個(gè)，以下是按照江西財(cái)經(jīng)大學(xué)的校情制定的約束條件。這里的約束條件主要是避免沖突。其中課程名稱，班別，校區(qū)編號(hào)唯一決定一個(gè)選課班。課程因素還包括開設(shè)的班級(jí)數(shù)及課程開設(shè)的校區(qū)等。安排教師課元信息表各年級(jí)、各專業(yè)培養(yǎng)方案各年級(jí)、各專業(yè)學(xué)生人數(shù)課程性質(zhì)教師信息學(xué)院安排、調(diào)整課表教務(wù)處時(shí)間要求培養(yǎng)方案教室資源信息制定教學(xué)任務(wù)書教學(xué)任務(wù)書提出特殊要求教務(wù)處課程表圖 35 排課總流程時(shí)間要求 排課因素分析排課工作是教學(xué)工作順利進(jìn)行的基礎(chǔ)工作，排課問題涉及到的因素也幾乎是全校性的。安排、調(diào)整課表課程表課元信息表時(shí)間要求培養(yǎng)方案教室資源信息教務(wù)處圖34 排課流程(5) 江西財(cái)經(jīng)大學(xué)排課總流程江西財(cái)經(jīng)大學(xué)每屆新生入學(xué)前，各學(xué)院各專業(yè)已經(jīng)為新生制定了在校四年的培養(yǎng)方案，作為在校期間學(xué)生選課的依據(jù)。然后，在教學(xué)任務(wù)書中為每門課程的每個(gè)班添加老師，以及該課程對(duì)教室的要求，這樣形成的信息稱之為課元信息。交叉之后子代經(jīng)歷的變異，實(shí)際上是子代基因按小概率擾動(dòng)產(chǎn)生的變化。這些基本操作又有許多不同的方法。遺傳算法采納了自然進(jìn)化模型，如選擇、交叉、變異、遷移、局域與臨域等。(11) 解碼(decodi ng)編碼的逆過程，即從遺傳子型到表現(xiàn)型的映射。一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程。(3) 種群(population)染色體帶有特征的個(gè)體的集合稱為種群。由于參數(shù)選擇關(guān)系到算法的精度、可靠性和計(jì)算時(shí)間等諸因素，并影響到結(jié)果的質(zhì)量和系統(tǒng)性能，因此參數(shù)選擇的研究受到重視。后來為解決模式里有太大的變動(dòng)或遺傳算法欺騙問題，有人提出了具有破壞性選擇的遺傳算法。變異能恢復(fù)個(gè)體失去的或未開發(fā)的遺傳物質(zhì)，以防止個(gè)體在形成最優(yōu)解過程中過早收斂。根據(jù)Holland教授提出的編碼應(yīng)該有利于交叉變異操作的編碼原則[4]，本文設(shè)計(jì)了適用于排課問題的編碼模型。本文在將遺傳算法應(yīng)用到排課問題中時(shí)，對(duì)遺傳算法的編碼、適應(yīng)函數(shù)的設(shè)計(jì)、遺傳算子、遺傳算法參數(shù)的選擇等進(jìn)行了分析[11]。經(jīng)過20余年的發(fā)展，計(jì)算機(jī)智能已經(jīng)成為人工智能研究的一個(gè)重要方向，以及后來人工生命研究的興起，使遺傳算法受到廣泛關(guān)注。文獻(xiàn)[9]中提出了結(jié)合網(wǎng)絡(luò)流算法與禁忌搜索算法的優(yōu)勢(shì)，求解排課問題的方案，雖然得出了可行解，但結(jié)果不夠理想，很多優(yōu)化因素沒有考慮。模擬退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人們從自然界固體退火過程中得到啟發(fā)并從中抽象出來的一種隨機(jī)優(yōu)化算法。但由于在實(shí)踐中遇到的困難，人們對(duì)排課問題的解是否存在產(chǎn)生了疑問。 Multiobjective Optimization目 錄1 引言 12 遺傳算法 2 遺傳算法研究的內(nèi)容 3 遺傳算法的基本術(shù)語 4 遺傳算法的基本思想 5 遺傳算法的基本操作 63 排課系統(tǒng)的需求分析 8 排課系統(tǒng)的業(yè)務(wù)流程分析 8 排課因素分析 10 排課的約束條件 114 基于遺傳算法的排課算法的描述 12 排課問題的目標(biāo)分