用遺傳算法求解課程表問(wèn)題.pdf

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

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

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