用遺傳算法求解課程表問題.pdf

1、實現(xiàn)計算機(jī)自動排課，是學(xué)校教學(xué)管理工作邁入科學(xué)化、規(guī)范化和現(xiàn)代化管理的關(guān)鍵步驟，其意義十分重大。然而，排課問題己被證明為NP完全的組合優(yōu)化問題，至今在多項式時間內(nèi)沒有完善、成熟的解決方案。遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、自適應(yīng)的隨機(jī)搜索算法，是一種非常有效的解決NP完全組合問題的方法。本文在詳細(xì)分析遺傳算法的應(yīng)用特點和關(guān)鍵要素的基礎(chǔ)上，結(jié)合課程表問題的求解難點和目標(biāo)，綜合考慮排課問題涉及到的各種因素和約束條

2、件，確定了求解排課問題方案的總體思路，設(shè)計了遺傳算法的具體實現(xiàn)方案，以濟(jì)寧市實驗中學(xué)2008-2009學(xué)年度第一學(xué)期課程表為實例，使用C＃和.net作為開發(fā)工具設(shè)計完成了計算機(jī)自動排課系統(tǒng)。本文的主要的研究內(nèi)容有：
　　1.系統(tǒng)完整地討論了排課問題中的影響因素、主要約束條件、求解目標(biāo)和難點，用數(shù)學(xué)模型完整地描述了排課問題，并提出了使用遺傳算法求解課程表問題的方法和優(yōu)勢。
　　2.針對排課問題研究了染色體編碼方式以及遺傳操作算

3、子的設(shè)計，提出了一種針對課程表問題解的特點的染色體混合矩陣二進(jìn)制編碼，并引入多目標(biāo)決策協(xié)調(diào)模型優(yōu)化課程表問題，并改進(jìn)了遺傳算法一般結(jié)構(gòu)，形成了一套多目標(biāo)協(xié)同優(yōu)化的排課算法。
　　3.以C#和．net為基本開發(fā)工具，MS SQL SERVER2000為后臺數(shù)據(jù)庫，設(shè)計和實現(xiàn)了基于GA算法的B/S和C/S混合架構(gòu)的自動排課系統(tǒng)。我們通過對濟(jì)寧市實驗中學(xué)的共306個教師和90個班級的1230個開課計劃的實例，在由時間片優(yōu)先度、班級日分布