多約束條件下的大學(xué)考試移除

多約束條件下的大學(xué)考試移除

1硬約束條件的約束大學(xué)考試時(shí)間自然響應(yīng)問題是一個(gè)多才多藝的優(yōu)化問題。以往的方法包括遺傳統(tǒng)計(jì)法和模擬退火法。這些方法通常存在兩個(gè)問題:首先求解時(shí)間表問題最優(yōu)解的時(shí)間復(fù)雜性是時(shí)間表規(guī)模的指數(shù)級(jí),優(yōu)化過程計(jì)算量很大;再者,不同學(xué)校、不同制度下對(duì)考試安排的約束要求都不一樣,不同對(duì)象對(duì)時(shí)間表優(yōu)劣評(píng)價(jià)也不同,花費(fèi)了巨大代價(jià)的全局尋優(yōu)得到的權(quán)衡解并不一定理想,僅僅靠一個(gè)把所有約束綜合起來的適應(yīng)值函數(shù)經(jīng)常不能明確反映出孰優(yōu)孰劣。甚至在尋優(yōu)操作過程中有時(shí)會(huì)破壞了硬約束條件而得到了不可行解?？荚嚂r(shí)間表的約束條件通常分為必須要滿足的硬約束條件和盡量要滿足的軟約束條件。該文中的硬約束是同一學(xué)生選讀的課程不能在同一時(shí)間考試、同一個(gè)教師任教的課程必須在同一時(shí)間考試。軟約束條件是每個(gè)學(xué)生的幾門課程的考試時(shí)間間隔大一些平均一些,利于學(xué)生復(fù)習(xí)。在此校方希望整個(gè)考試周天數(shù)盡量縮短,而學(xué)生希望考試課程時(shí)間間隔大一些,便于復(fù)習(xí)。該文從實(shí)際出發(fā),對(duì)基于圖著色模型得到的滿足硬約束并且考試周長度盡可能短的初始解,用非常適合的分組遺傳算法在不破壞硬約束條件的基礎(chǔ)上進(jìn)行優(yōu)化。在不延長考試周的基礎(chǔ)上擴(kuò)大了學(xué)生的復(fù)習(xí)時(shí)間,協(xié)調(diào)了校方和學(xué)生要求之間的矛盾關(guān)系。2考試總總控制公式(1)的數(shù)學(xué)模型中c表示整個(gè)考試安排的代價(jià),它趨向最大也就是使學(xué)生總的復(fù)習(xí)時(shí)間最大。T代表總的考試時(shí)間段,該文中一天只有一個(gè)時(shí)間段考試,那么T就代表考試周的天數(shù);M代表總的考試課程數(shù);npq表示同時(shí)參加考試p和q的學(xué)生人數(shù);dst表示時(shí)間段s和t的距離,即學(xué)生的復(fù)習(xí)時(shí)間;yps表示p考試安排到s時(shí)間段;yqt表示q考試安排到t時(shí)間段。公式(2)表示一門考試q只安排在一個(gè)時(shí)間段t:公式(3)表示安排在時(shí)間段t中的所有考試總數(shù)小于校方規(guī)定的一個(gè)固定的最大值:公式(4)中如果s=t那就代表同一學(xué)生參加考試的兩門課程安排在一個(gè)時(shí)間段,違反了硬約束條件,是不可行解,這時(shí)dst就取一個(gè)很大的負(fù)值。只有當(dāng)s≠t時(shí)才是可行解。3根據(jù)組ga的計(jì)算時(shí)間，優(yōu)化算法3.1熔噴非織造布的編碼遺傳算法常用的編碼方法有二進(jìn)制編碼和實(shí)數(shù)編碼。采用實(shí)數(shù)編碼,即將其真實(shí)值作為變量的編碼。將一個(gè)變量的編碼按一定順序連接在一起,形成個(gè)體編碼串。解碼時(shí)只需將染色體各個(gè)基因座上的基因值按序賦給相應(yīng)的變量即可。在這里每個(gè)滿足硬約束條件的初始解即為一個(gè)染色體,對(duì)于染色體的編碼有傳統(tǒng)的直接編碼和改進(jìn)分組編碼兩種方法。傳統(tǒng)的染色體直接編碼是:基因是考試課程,基因的值是時(shí)間,見表1。因?yàn)槭腔趫D著色算法得出的初始解所以以顏色代表考試時(shí)間段,該文中一天只有一場考試,考試周天數(shù)和考試時(shí)間段數(shù)是一致的。A、B等字母代表考試課程名稱。這樣的編碼方式有以下幾個(gè)缺點(diǎn):(1)染色體長度長,如果以某高校實(shí)際情況為例,大約有80多門不同課程考試,那么染色體的基因位數(shù)就是課程的門數(shù)有80多位。(2)帶來冗余。表2的染色體跟表1染色體比較雖然基因C和D(見表2中黑體所示)的位置交換了,變成另外的一條染色體,但其實(shí)和表1所示的染色體是一樣的。如果以學(xué)校實(shí)際情況為例,大約有80多門不同課程考試,安排在12天,這樣的編碼帶來的冗余將會(huì)是驚人的。(3)根據(jù)優(yōu)生的觀點(diǎn),父母親代的染色體差異大容易產(chǎn)生優(yōu)秀的后代,若用兩個(gè)實(shí)際上是冗余一致的染色體交叉很可能產(chǎn)生很差的后代。(4)變異操作容易破壞解的硬約束條件如表2所示,如果G、K兩門課是同一個(gè)任課教師,要安排在同一天考,那當(dāng)課程H和課程G變異互換時(shí)破壞了硬約束條件,使這個(gè)染色體成為一個(gè)非法染色體。因此采用的是改進(jìn)后的編碼,即分組著色編碼:分組著色問題是分組問題大家庭中一員,Falkenauer定義分組問題為將一系列實(shí)體按照硬約束條件分成互相獨(dú)立無關(guān)聯(lián)的子集組。裝箱問題、任務(wù)分配、媒體循環(huán)等都可以認(rèn)為是分組問題。圖著色問題中有邊連接的點(diǎn)分成不同組。每一組中的點(diǎn)都是無邊連接的。分組編碼有兩個(gè)優(yōu)點(diǎn):(1)組的數(shù)量少。分組編碼對(duì)應(yīng)的染色體中每個(gè)組(色)是一個(gè)基因,值是考試課程,這樣實(shí)際的編碼長度即為考試周的天數(shù),大約十幾天。染色體基因的位數(shù)就是十幾位,比傳統(tǒng)編碼少很多。(2)交叉、變易操作是不會(huì)破壞硬約束條件。3.2夯實(shí)班級(jí)考試時(shí)間的間隔不同班級(jí)的學(xué)生考試課程的門數(shù)不一樣,所以人均理論復(fù)習(xí)時(shí)間X=考試周總天數(shù)/人均考試課程。例如:某個(gè)學(xué)生正考課程是4門,考試周總天數(shù)是12天,則他每門課的理論復(fù)習(xí)時(shí)間是X=考試總天數(shù)/人均考試課程=12天/4門=3天/門。若一個(gè)學(xué)生4門考試課程分別安排在第1、3、4、6天,則實(shí)際的復(fù)習(xí)時(shí)間也就是時(shí)間間隔距離分別為:3-1=2天、4-3=1天、6-4=2天(第一門課的復(fù)習(xí)時(shí)間默認(rèn)很充足,不計(jì)算在內(nèi))。這個(gè)班級(jí)考試時(shí)間總的間隔個(gè)數(shù)為n=3。實(shí)際的復(fù)習(xí)時(shí)間與理論復(fù)習(xí)時(shí)間的標(biāo)準(zhǔn)方差為:則適配值函數(shù)f即為所有班級(jí)標(biāo)準(zhǔn)方差的平均值:公式(5)中的f趨向最小就意味著實(shí)際復(fù)習(xí)時(shí)間更接近理論復(fù)習(xí)時(shí)間;m代表班級(jí)數(shù);n代表每個(gè)班級(jí)考試時(shí)間總的間隔個(gè)數(shù);Di代表第i個(gè)間隔數(shù),即復(fù)習(xí)時(shí)間;X代表人均理論復(fù)習(xí)時(shí)間。3.3子代染色體交叉操作尋找鄰居的結(jié)論有兩種移動(dòng)“考試移動(dòng)”和“時(shí)間段移動(dòng)”對(duì)應(yīng)于傳統(tǒng)染色體編碼的考試移動(dòng)會(huì)打亂顏色的分組,破壞硬約束條件,放棄。應(yīng)于改進(jìn)后分組編碼的染色體的時(shí)間段移動(dòng)可以分以下幾種:隨機(jī)兩個(gè)時(shí)間段交換、選一個(gè)序列(例如起點(diǎn)2,長度4)移動(dòng)、選中一個(gè)序列顛倒、序列重排、循環(huán)移動(dòng)。先采用循環(huán)移動(dòng)產(chǎn)生若干種群,每個(gè)種群內(nèi)再采用隨機(jī)交換產(chǎn)生新解。以表3染色體為實(shí)例,考試安排在6天,則循環(huán)產(chǎn)生初始種群中有6個(gè)個(gè)體:以表3的實(shí)例為初始解,班級(jí)編號(hào)與考試課程對(duì)應(yīng)關(guān)系如表4所示?？荚嚾绨才?天則循環(huán)移動(dòng)產(chǎn)生包括6個(gè)個(gè)體的初始種群,個(gè)體1見表5。見表3的實(shí)例,紅色代表第1天,黃色代表第2天,綠色代表第3天,藍(lán)色代表第4天,紫色代表第5天,褐色代表第6天。理論復(fù)習(xí)時(shí)間為6天/3門=2天/門。用公式(5)計(jì)算得出適配值函數(shù)f=1.034。循環(huán)移動(dòng)得到個(gè)體2,見表6:其中黃色代表第1天,綠色代表第2天,藍(lán)色代表第3天,紫色代表第4天,褐色代表第5天,紅色代表第6天。對(duì)應(yīng)的每個(gè)班級(jí)復(fù)習(xí)時(shí)間如表7所示,用公式(5)同樣可以計(jì)算出適配值函數(shù)。以此類推得到個(gè)體3、4、5、6。復(fù)制操作該文采用的是直接計(jì)算每個(gè)染色體的適配值,按適配值大小采用末位淘汰復(fù)制,直接淘汰f最大的個(gè)體,若f相同則隨機(jī)淘汰其中之一。交叉操作該文采用的是實(shí)值重組,首先隨機(jī)選取兩個(gè)交叉點(diǎn),并把這兩個(gè)交叉點(diǎn)之間的區(qū)域定義為匹配區(qū)域,將交叉部分分別接在染色體后面,再刪除前面重復(fù)的顏色,使兩個(gè)子代染色體合法化。變異操作設(shè)計(jì)較簡單,隨機(jī)選2個(gè)基因位交換,因?yàn)椴扇》纸M編碼方案,不會(huì)產(chǎn)生非法染色體。3.4多系統(tǒng)優(yōu)化轉(zhuǎn)變步驟1基于圖著色模型得出初始可行解;步驟2循換產(chǎn)生初始種群,個(gè)體數(shù)目與考試周總天數(shù)一致(即如果考試周總天數(shù)是12天,則初始種群中有12個(gè)個(gè)體);步驟3計(jì)算每個(gè)個(gè)體的適應(yīng)度,并判斷是否符合優(yōu)化準(zhǔn)則,若符合,輸出最佳個(gè)體及其代表的最優(yōu)解,并結(jié)束計(jì)算,否則轉(zhuǎn)向步驟4;步驟4依據(jù)適配值選擇再生個(gè)體,淘汰適配值高的個(gè)體;步驟5交叉生成新的個(gè)體;步驟6變異生成新的個(gè)體;步驟7由交叉和變異產(chǎn)生新一代的種群,返回到步驟3。4夯實(shí)班級(jí)學(xué)生初始安排優(yōu)化實(shí)驗(yàn)是在vf6.0中編譯的程序,共有34個(gè)班級(jí)(人數(shù)忽略)參與實(shí)驗(yàn),每個(gè)班級(jí)最少的考2門,最多的考6門,共計(jì)115門課程,安排在12天考試。圖1和圖2中分別用黃、紅、藍(lán)等顏色表示一個(gè)班級(jí)幾門課程考試的安排時(shí)間,它們的間隔距離也就代表了學(xué)生的復(fù)習(xí)時(shí)間,圖1是初始安排的時(shí)間表,很明顯可以看出復(fù)習(xí)時(shí)間非常不平均,例如班級(jí)編號(hào)為1的班級(jí)三門課程考試時(shí)間安排分別為第2、11、12天。圖2是優(yōu)化后的時(shí)間表明顯比圖1中的初始安排平均分布,班級(jí)編號(hào)為1的班級(jí)三門課程考試時(shí)間安排分別為第3、8、11天,比初始安排明顯均勻,其他班級(jí)考試安排的點(diǎn)間隔也明顯比圖1均勻。圖3和圖4是每個(gè)班級(jí)實(shí)際平均復(fù)習(xí)時(shí)間(圖中用紅色點(diǎn)表示)與理論復(fù)習(xí)時(shí)間(圖中用藍(lán)色點(diǎn)表示)的比較,圖3初始安排中代表實(shí)際復(fù)習(xí)時(shí)間的紅點(diǎn)大都在理論復(fù)習(xí)時(shí)間藍(lán)點(diǎn)的下方,說明總的來說實(shí)際平均復(fù)習(xí)時(shí)間少于理論復(fù)習(xí)時(shí)間的居多。優(yōu)化后實(shí)際平均復(fù)習(xí)時(shí)間大于初始安排中的實(shí)際復(fù)習(xí)時(shí)間,見圖4中,實(shí)際平均復(fù)習(xí)時(shí)間比優(yōu)化前更接近理論復(fù)習(xí)時(shí)間,紅色的點(diǎn)平均分布于理論值的上下方,尤其是在考試門數(shù)大于等于4門的班級(jí)(圖4中,班級(jí)編號(hào)大于25的幾個(gè)班級(jí))與理論值基本重合。初始安排時(shí)間表中實(shí)際復(fù)習(xí)時(shí)間與理論復(fù)習(xí)時(shí)間的標(biāo)準(zhǔn)方差即目標(biāo)函數(shù)f為3.57,優(yōu)化后減小至2.43,在尋優(yōu)的過程中出現(xiàn)的最大f為3.9。5分組遺傳算法尋優(yōu)思想符合臨床應(yīng)用需求分組遺傳算法非常適合某高校考試安排的實(shí)際應(yīng)用,在不增加考試周總天數(shù)的條件下平均且擴(kuò)大了學(xué)生的復(fù)習(xí)時(shí)間