基于遺傳算法的排課系統(tǒng)

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

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

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

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