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