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

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

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

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