【正文】 1=x=t。班級(jí)集合公式52： C={C1，C2，……Cc} c為班級(jí)總數(shù)，某班級(jí)可以表示為Cy，1=y=c。教室集合公式53： R={R1，R2，……Rr} r為教室總數(shù)，某教室可以表示為Tz，1=z=r。課程集合公式54： K={K1，K2，……Kk} k為教室總數(shù)，某教室可以表示為Kw，1=w=k。課表時(shí)間片集合公式55： P={{P11，P12，P13，P14，P15，}……{P71，P72，P73，P74，P75，} }某時(shí)間片可以表示為Pmn，m為星期幾的數(shù)學(xué)表示1=m=5，n為每天的節(jié)次數(shù)1=n=7。課表時(shí)間片可以直觀的表示為表51：時(shí)間一二三四五第一節(jié)P11P12P13P14P15第二節(jié)P21P22P23P24P25第三節(jié)P31P32P33P34P35第四節(jié)P41P42P43P44P45中午第五節(jié)P51P52P53P54P55第六節(jié)P61P62P63P64P65第七節(jié)P71P72P73P74P75表51 課表時(shí)間片在排課問題中某學(xué)院某學(xué)期課表的數(shù)據(jù)模型就是CyKwTxRzPmn的組合。在自動(dòng)排課前，需要進(jìn)行班級(jí)課程設(shè)置、班級(jí)課程任課教師設(shè)置，這些設(shè)置就是為了確定Cy、Kw、Tx三者的關(guān)系。設(shè)定好它們的就得到了要進(jìn)行排課的任務(wù)，每一個(gè)排課任務(wù)就對(duì)應(yīng)一個(gè)CyKwTx的組合。自動(dòng)排課的處理過程就是在滿足約束的條件下確定每個(gè)任務(wù)對(duì)應(yīng)的組合CyKwTx在一周內(nèi)與于剩下的兩個(gè)元素Rz和Pmn如何進(jìn)行組合。下面用數(shù)學(xué)的方法來分析排課的約束條件：硬性約束條件1（同一班級(jí)在同一時(shí)間只能安排一門課程），用數(shù)學(xué)來表示就是CyPmn的組合是唯一的，有且只能有一個(gè)。硬性約束條件2（同一教師在同一時(shí)間只能安排一門課程），用數(shù)學(xué)來表示就是TxPmn的組合是唯一的，有且只能有一個(gè)。硬性約束條件3（同一教室在同一時(shí)間只能安排一門課程），用數(shù)學(xué)來表示就是RzPmn的組合是唯一的，有且只能有一個(gè)。硬性約束條件4（教室總數(shù)要大于同一時(shí)間安排的課程總數(shù)），用數(shù)學(xué)來表示就是對(duì)于任意的Pmn時(shí)間片，教室總數(shù)r大于CyKwTxRz組合的數(shù)量。硬性約束條件5（教室容量必須大于上課學(xué)生人數(shù)），用數(shù)學(xué)來表示就是對(duì)于任意的CyKwTxRzPmn組合，教室Rz容量必須大于班級(jí)Cy的人數(shù)。硬性約束條件6（課程要安排在它需要的類型教室中），用數(shù)學(xué)來表示就是對(duì)于任意的課表組合CyKwTxRzPmn，課程Kw所要求的教室類型必須與教室Rz的類型一致。軟性約束條件1（優(yōu)先安排全校公共基礎(chǔ)課），用數(shù)學(xué)來表示就是排課任務(wù)CyKwTx具有較高的優(yōu)先級(jí)，要優(yōu)先進(jìn)行安排。軟性約束條件2（一周內(nèi)課次多于2次以上的多課時(shí)課程，在時(shí)間安排上要求盡量隔天安排），用數(shù)學(xué)來表示就是當(dāng)排課任務(wù)CyKwTx在一周內(nèi)的次數(shù)大于2時(shí)，在組合成CyKwTxRzPmn時(shí)，每次的m盡量不同。軟性約束條件3（較難課程應(yīng)安排在上午第一節(jié)或下午第一節(jié)），用數(shù)學(xué)來表示就是任意的課表組合CyKwTxRzPmn，如果課程Kw是較難的課程時(shí)，Pmn的節(jié)次n最好是1或3。軟性約束條件4（體育課后盡量避免直接排課），用數(shù)學(xué)來表示就是任意的課表組合CyKwTxRzPmn，如果課程Kw是體育課時(shí)，Pmn的節(jié)次n為q，則最好不要再出現(xiàn)n為q+1的課表組合CyKwTxRzPmn。軟性約束條件5（同一門課程盡量安排在固定的教室），用數(shù)學(xué)來表示就是當(dāng)排課任務(wù)CyKwTx在一周內(nèi)的次數(shù)大于2時(shí)，在組合成CyKwTxRzPmn時(shí)，每次的Rz盡量相同。通過以上的數(shù)學(xué)分析，我們將數(shù)據(jù)庫(kù)排課信息表CourseInfoTb的結(jié)構(gòu)定義為（代理主鍵，院系系統(tǒng)Id，學(xué)期Id，班級(jí)系統(tǒng)Id，課程系統(tǒng)Id，教師系統(tǒng)Id，教室系統(tǒng)Id，星期，節(jié)次，排課狀態(tài)）。4個(gè)數(shù)據(jù)庫(kù)字段“班級(jí)系統(tǒng)Id，課程系統(tǒng)Id，教師系統(tǒng)Id，教室系統(tǒng)Id”分別對(duì)應(yīng)Cy、Kw、Tx、Rz，“星期，節(jié)次”2個(gè)數(shù)據(jù)庫(kù)字段分別對(duì)應(yīng)Pmn中的m、n。在這種數(shù)據(jù)結(jié)構(gòu)的支持下，我們很容易將這些約束轉(zhuǎn)化為實(shí)際的函數(shù)和方法去處理。遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。系統(tǒng)進(jìn)行排課時(shí)，具體算法描述如下：1）編碼一條染色體中應(yīng)包含所有排課DNA分子，每個(gè)排課DNA分子又包含班級(jí)課程信息、老師信息、教室信息和時(shí)間信息，以及院系和學(xué)期信息。由于院系和學(xué)期在處理中是提前設(shè)定好的，在每次處理時(shí)都是一個(gè)給定的值，所以在染色體中可以不考慮他們。在前面的數(shù)學(xué)分析中我們將課表組合表示為CyKwTxRzPmn，這里將Pmn拆分為MN，則可將染色體表示為CyKwTxRzMN。Cy、Kw、Tx、Rz都用他們所對(duì)應(yīng)的字段Id的值來表示。M表示星期，N表示每天課節(jié)數(shù)。2）初始種群采用系統(tǒng)的隨機(jī)數(shù)，生成初始種群。在前面的數(shù)學(xué)分析中我們將排課任務(wù)表示為CyKwTx，在進(jìn)行排課是初始化種群中的個(gè)體就是用隨機(jī)函數(shù)生成染色體中的RzMN的組合。確定適應(yīng)度，首先對(duì)一條染色體中的每個(gè)DNA分子計(jì)算適應(yīng)度，然后計(jì)算一條染色體中所有DNA分子適應(yīng)度之和，將該值作為個(gè)體適應(yīng)度。其中最主要的有檢測(cè)班級(jí)、教師和教室三者的時(shí)間沖突，對(duì)應(yīng)硬性條件的3（同一班級(jí)在同一時(shí)間只能安排一門課程；同一教師在同一時(shí)間只能安排一門課程；同一教室在同一時(shí)間只能安排一門課程；）。所有的約束條件的滿足情況就是對(duì)應(yīng)的適應(yīng)度。而且對(duì)于硬性約束條件，系統(tǒng)要求必須滿足，這也就對(duì)應(yīng)的要求個(gè)體的適應(yīng)度必須達(dá)到硬性約束對(duì)適應(yīng)度的要求。一門課在一周內(nèi)應(yīng)分散安排，既不應(yīng)間隔時(shí)間太長(zhǎng)，也不應(yīng)間隔時(shí)間太近，這樣可以為學(xué)生提供消化學(xué)習(xí)時(shí)間。系統(tǒng)使用編號(hào)相同的兩課的時(shí)間差(如:Tl與T2的時(shí)間差是1。T1與T20的時(shí)間差是19)來描述這種離散度，根據(jù)測(cè)試給出相應(yīng)的期望值。如表42所示。兩課時(shí)間差333346 、2222922511222311111120期望值表52 課程離散度期望值檢測(cè)每一門課程的每一次上課的位置，計(jì)算出時(shí)間的差值，然后對(duì)所有時(shí)間的差值所對(duì)應(yīng)的期望值Fls(i)=(i=1，2，3，……35)求和。即定義課程的離散度期望值函數(shù)為[19]:對(duì)于特殊的課程(體育課、自習(xí)課)應(yīng)安排在適當(dāng)?shù)慕虒W(xué)時(shí)間點(diǎn)，所以我們對(duì)一天的三個(gè)時(shí)段分別給出了期望值：上午12節(jié)課的期望值為0；上午34節(jié)課的期望值為5；下午567節(jié)課的期望值為10。在這種定義下我們所涉及的35個(gè)時(shí)間片的期望值就確定下來了。檢測(cè)體育課的位置，即檢測(cè)在課程表中的教師編碼的課程特點(diǎn)代碼是否為“t”(扣除教師編碼中的教師名和課程序號(hào))，如是則讀取其時(shí)間片，從而對(duì)應(yīng)出它的期望值Fx(i)(i=1,2,3,4.....35),并對(duì)期望求和。檢測(cè)自習(xí)課的期望值，即讀取教師編碼為空的時(shí)間片，對(duì)期望求和。Fz(i)(i=1,2,3,4.....35)。對(duì)特殊課程所有的期望值求和，定義函數(shù)如下：Fts=∑(Fx(i)+Fz(i))盡量把難度大、費(fèi)思考的課程(理論課)安排在好的教學(xué)日、教學(xué)時(shí)間點(diǎn)(如上午比下午好)。對(duì)于每一個(gè)班級(jí)來說，一學(xué)期的所有課程中總有幾門課是比較難的課程，我們把難度大、費(fèi)思考的課程設(shè)法安排在較好的時(shí)間點(diǎn)。檢測(cè)每一個(gè)班的難度大、費(fèi)思考的課程(理論課)的位置，即檢測(cè)在課程表中的教師編碼的課程特點(diǎn)代碼是否為“l(fā)”(扣除教師編碼中的教師名和課程序號(hào))，如是則讀取其時(shí)間片，從而對(duì)應(yīng)出它的期望值Fnx(i)(i=1,2,3,4.....35)，然后對(duì)所有的期望值求和。即定義函數(shù)Fnx=∑Fnx(i)；基于以上排課目標(biāo)的分析，我們采用如下適應(yīng)度函數(shù)：F=K1*Fls+K2*Fts+K3*Fnx=K1*∑Fls(i)+K2*∑(Fx(i)+Fz(i))+K3*∑Fnx(i)K1,K2,K3為用于控制上述各種期望值對(duì)總期望值的影響參數(shù)。這樣，我們就有了沖突檢測(cè)、消除和適應(yīng)度函數(shù)。在進(jìn)化過程中，沖突必須完全消除；而適應(yīng)度函數(shù)越大，則課程表的安排越合理、有效。對(duì)于每一個(gè)期望值及其在總的期望值中的比例，我們都可以根據(jù)每一所學(xué)校的具體情況進(jìn)行必要的調(diào)整，以便更加實(shí)用、有效。對(duì)每一個(gè)課程表二維數(shù)組KB(35，BJS)，進(jìn)行沖突檢測(cè)，然后用自動(dòng)定位變異算子消除沖突。因?yàn)閷?duì)于同一時(shí)間，同一個(gè)班級(jí)或同一個(gè)教室同時(shí)上一門以上課程的硬沖突，在編碼的過程中己經(jīng)避免，不會(huì)發(fā)生。因此，我們只要對(duì)同一時(shí)間，同一個(gè)教師同時(shí)上一門以上課程的沖突進(jìn)行檢測(cè)和消除。消除同一時(shí)間，同一個(gè)教師同時(shí)上一門以上課程的沖突:對(duì)第一個(gè)課程表二維數(shù)組KB(35，BJS)，讀取它的第一行、第一列的教師號(hào)。與二維數(shù)組同一行、下一列的教師號(hào)比較。如相同，則隨機(jī)產(chǎn)生一個(gè)1一35之間的整數(shù)Z，判斷這一行、第Z列的基因編碼中的最后字符是否為“s”，即特定教學(xué)時(shí)間，如是則重新產(chǎn)生隨機(jī)數(shù)Z，否則將兩個(gè)數(shù)組元素的值互換。再重新比較，直到無相同元素為止。讀取該行、第二列的教師號(hào)，重復(fù)步驟。直到第一行的所有元素的教師號(hào)不相同。讀取課程表二維數(shù)組KB(35，BJS)的第二行、第一列的教師號(hào)，重復(fù)3，直到每一行的所有元素的教師號(hào)不相同，即沒有同一時(shí)間，一個(gè)教師同時(shí)上一門以上課程的沖突。其次，我們消除同一時(shí)間，一個(gè)實(shí)驗(yàn)室(計(jì)算機(jī)房、語音室等)同時(shí)有一個(gè)以上的班級(jí)上課的沖突：①對(duì)每一個(gè)二維數(shù)組，判斷它的每一行是否有多個(gè)元素的教師編碼中的最后一個(gè)字符為“j”，如有則在第二個(gè)元素所在的列隨機(jī)地找一個(gè)教師編碼中的最后一個(gè)字符不是“s”元素進(jìn)行數(shù)值互換。直到這個(gè)二維數(shù)組的所有行中最多只有一個(gè)元素的教師編碼中的最后一個(gè)字符為“j”；②對(duì)每一個(gè)二維數(shù)組，判斷它的每一行是否有多個(gè)元素的教師編碼中的最后一個(gè)字符為“y”，如有則在第二個(gè)元素所在的列隨機(jī)地找一個(gè)教師碼中的最后一個(gè)字符不是“s”元素進(jìn)行數(shù)值互換。直到這個(gè)二維數(shù)組的所有行中最多只有一個(gè)元素的教師編碼中的最后一個(gè)字符為“y”。這樣，我們便消除了所有的沖突了。這里我們使用的是自動(dòng)定位變異算法，在檢測(cè)的過程中如有沖突存在，則確定其位置，并消除這一沖突。使用這一算法可以大大提高遺傳算法的效率。系統(tǒng)中檢查硬性條件3的函數(shù)ClassThRmNoBusy負(fù)責(zé)檢測(cè)班級(jí)老師教室在給定的時(shí)間片是否沖突，其代碼如下：public boolean ClassThRmNoBusy(int xq,int jc,int rmid,int termId,int thid,int pclassid){boolean nobusy=true。String sql =select LessonOrders,Weeks,ClassId,TeacherId,ClassRoomId 。 sql +=from CourseInfoTb 。 sql += where TermId= + termId 。 sql += and Weeks= + xq 。 sql += and LessonOrders= + jc 。 sql += and (TeacherId= + thid + or ClassRoomId= + rmid + or ClassId= + pclassid + ) 。 try { ResultSet rs = (sql)。 if (rs !=nullamp。amp。()) { nobusy = false。 } } catch (SQLException e) { ()。 } return nobusy。 }選擇運(yùn)算和變異運(yùn)算是系統(tǒng)生成下一代種群的方式和方法，通過有限次的選擇運(yùn)算和變異運(yùn)算找到最優(yōu)解。系統(tǒng)中這部分的主要代碼為：private void BianYiXqJc(int pclassid,Random rd){ tryCount = tryCount + 1。 if (tryCount 100 ){ if( j 0 amp。amp。 jCount 6 ){ BianYiXq(rd)。 }else{ byXq = (5) + 1。 } if(CourseType==CType_JaoNan){ byJc=Jc15[(2)]。 }else if(CourseType==CType_TiYu){ byJc=Jc47[(2)]。 }else{ byJc = (7) + 1。 } }else{ byXq = (5) + 1。 byJc = (7) + 1。 } if(ClassList[(byJc1)*5 + byXq 1]==pclassid amp。amp。 tryCount 200){ BianYiXqJc(pclassid, rd)。 }}private void BianYiXq(Random rd){ byXq = (5) + 1。 for(int i=0。i3。i++){ if(XqOld[i]==byXq){ BianYiXq(rd)。 break。 } }}