1、基于遺傳算法的排課系統(tǒng)設(shè)計陳常濤一、 數(shù)據(jù)庫設(shè)計 概述排課問題是一個多因素的組合優(yōu)化問題，屬于NP完全類問題。傳統(tǒng)的方法難以得到高質(zhì)量的課表，而采用遺傳算法能更有效地得到更優(yōu)化的課表。 需求分析排課問題有是關(guān)于教師，班級，時間，教室以及課程的多因素優(yōu)化決策問題。所以本系統(tǒng)要求實現(xiàn)以下功能1 在得出的課表中教師不能再同一個時間片段同時上兩門或兩門以上課程。2 在得出的課表中一個班級在同一個時間片段內(nèi)不能同時上兩門或兩門以上課程。3 由于教室容量有限，所以在同一個時間片段內(nèi)在該教室上課的班級的人數(shù)之和不能大于教室的容量。4 在同一個教室上的課必須是同一門課，并且是同一個老師教的。5 所有的課程按照

2、上學(xué)期某各個學(xué)院的開課計劃來安排 概念結(jié)構(gòu)設(shè)計1 根據(jù)以上所述現(xiàn)劃分出實體以及實體的屬性如下l 教師實體教師有其姓名，教師編號，并且一個教師可以教授多門課程和多個班級。所以教師實體的屬性如下屬性一：教師姓名屬性二：教師編號屬性三：教師所教授的班級編號屬性四：教師所授的課程編號l 班級實體一個班級有其所屬的年紀以及班級號，也有其班級編號，當然還有班級人數(shù)這個重要的屬性，所以班級實體的屬性如下屬性一：班級所屬年級以及班級號屬性二：班級編號屬性三：班級人數(shù)l 教室實體屬性一：教室編號屬性二：教室容量l 課程實體屬性一：課程編號屬性二：課程名l 開課計劃實體屬性一：班級屬性二：課程屬性三：該課程每周需

3、要開設(shè)的節(jié)次 邏輯結(jié)構(gòu)設(shè)計實體對應(yīng)以下關(guān)系模式l 教師(教師編號，教師姓名，教師所教授的班級編號，教師所授的課程編號)l 班級（班級號，班級編號，班級人數(shù)）l 教室（教室編號，教室容量）l 課程（課程編號，課程名）l 開課計劃（班級編號，課程編號，開設(shè)節(jié)次） 物理結(jié)構(gòu)設(shè)計實體間參照關(guān)系如下教師實體的教師所授的班級編號和課程編號分別參照班級實體的班級編號和課程實體的課程編號開課計劃的班級編號和課程編號分別參照班級實體的班級編號和課程實體的課程編號二、 算法設(shè)計 染色體的編碼基因編碼為：教師編號+課程編號+教室編號并且為了更好地拆分和組合基因，現(xiàn)規(guī)定教師編號為四位，課程編號為四位，教室編號為四位基

4、因所代表的意思是某一時間片段的課程安排，而染色體所代表的是所有班級在一周內(nèi)的20個時間片段的課程安排所以染色體為n個班和20個時間點所組成的二維維數(shù)組染色體結(jié)構(gòu)如下： T1 T2 T19 T20班級一基因基因基因基因基因班級二基因基因基因基因基因基因基因基因基因基因班級n-1基因基因基因基因基因班級n基因基因基因基因基因 群體的初始化對于每一個班級，按照開課計劃實體和教師實體里以及教室實體的數(shù)據(jù)組合成一個基因隨機填入不同的時間片段內(nèi)。 適應(yīng)度函數(shù)1 沖突問題對于二維數(shù)組的每一列，如果遇到教師編號相同則課程編號必須相同，否則用某一方法消除。對于二維數(shù)組的每一列，如遇到教室編號相同則課程編號也必須相同，并且教師編號也必須相同，且各個班級的人數(shù)之和不能超過教室容量。否則用某一方