遺傳算法在高校排課系統(tǒng)中應(yīng)用的研究.pdf

1、1963年,C.C.Gotlieb在文章《The Construction ofClass-Teacher Time-Tables》中提出了課表編排的數(shù)學(xué)模型,它標(biāo)志著課表編排課題的研究正式跨入了莊嚴(yán)的科學(xué)殿堂.1976年,S.Even在論文《On The Complexity of Timetable And Multi Commodity Flow Problems》,第一次證明了課表問題是NP完全的.在國(guó)內(nèi),清華大學(xué)于1984年在

2、《清華大學(xué)學(xué)報(bào)(自然版)》上發(fā)表了林漳希和林堯瑞在該課題上的實(shí)驗(yàn)性研究成果,接著國(guó)內(nèi)部分高等院校相繼開展了這方面的研究工作.本文主要探討課表編排問題,完成的主要工作如下:1.本文首先分析了課表問題中的各種因素,以及人工排課的模擬過程,討論了課表問題是一個(gè)具有不確定性、NP完全的組合優(yōu)化問題.2.提出了時(shí)間安排法 本論文設(shè)計(jì)的時(shí)間安排算法是基于經(jīng)典的遺傳算法.針對(duì)本課題,我們對(duì)遺傳算法做了多個(gè)方面的改進(jìn)和優(yōu)化.在初始種群的平均化、采用自適

3、應(yīng)的交叉概率和變異概率、分解種群為多個(gè)子種群等方面進(jìn)行了改進(jìn).3.設(shè)計(jì)了教室安排算法課表問題中除了遺傳算法的使用以外,針對(duì)教室的安排,我們還設(shè)計(jì)了教室安排算法,該算法依據(jù)"優(yōu)先教室集",綜合考慮資源分布優(yōu)化度等因素,為課程找到合理的教室安排.針對(duì)排課過程中出現(xiàn)的"甩課"問題(無(wú)法安排教室的課程),我們?cè)O(shè)置了3個(gè)子算法,它們有效地避免和解決這個(gè)問題.4.系統(tǒng)的實(shí)現(xiàn)針對(duì)本文所設(shè)計(jì)的模型,我們對(duì)主要算法進(jìn)行了實(shí)現(xiàn),效果良好.本文所討論的模型是