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

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

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