基于遺傳算法的課表編排問題研究.pdf

1、排課任務(wù)歷來都是教務(wù)管理中非常煩瑣的一項(xiàng)工作，原因是其約束條件復(fù)雜多樣。人工排課周期長、效率低，計(jì)算機(jī)排課則搜索空間非常龐大，是NP完全類問題。遺傳算法是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。本文通過使用遺傳算法，采用了染色體編碼方式和遺傳操作對課表進(jìn)行優(yōu)化。 本文中，將課表應(yīng)滿足的約束分為“硬約束”和“軟約束”，滿足硬約束的課表才是合法

2、的課表，滿足軟約束越好的課表就越是“滿意”的課表，運(yùn)用遺傳算法可以很好地提高軟約束的滿意度。本文的運(yùn)行環(huán)境是VS.net+SQL2000，采用C＃作為Windows窗體編程語言，后臺數(shù)據(jù)庫用SQL2000。定義四元組(序號、課程編號、上課時(shí)段、教室)作為一個(gè)基因，定義包含這個(gè)四元組的一個(gè)數(shù)據(jù)表為一個(gè)染色體。通過建立教師“時(shí)段偏好表”以度量每一個(gè)教師對課表的滿意度，定義適應(yīng)度函數(shù)=滿意度+分散度，遺傳操作的流程包括選擇、變異和交叉。其中選