基于混沌遺傳算法的排課問題研究.pdf

1、為了保證教學(xué)質(zhì)量，學(xué)校需要制定一套規(guī)范的教學(xué)計劃，而課表編排是教學(xué)計劃得以順利執(zhí)行的重要一環(huán)。隨著高校學(xué)生數(shù)量猛增，數(shù)據(jù)規(guī)模增大、約束條件增多，在教學(xué)資源一定的情況下排課越來越復(fù)雜，人工排課已經(jīng)難以完成課表編排的工作要求。因此，利用計算機(jī)解決排課問題成為當(dāng)務(wù)之急。排課問題是典型的多重約束和組合優(yōu)化問題，并且早在70年代已經(jīng)被證明是一個NP完全問題。 遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的自適應(yīng)隨機(jī)搜索算法。它具有良

2、好的并行性、通用性、穩(wěn)定性，是一種非常有效的解決NP完全問題的方法。 目前，使用遺傳算法解決排課問題已經(jīng)成為眾多學(xué)者和高校的研究熱點(diǎn)。本文所做的工作就是針對單一智能算法存在的問題和不足，設(shè)計混沌遺傳算法這種混合智能算法，并利用混沌遺傳算法對高校排課問題進(jìn)行較為深入的研究。嘗試性的將混沌遺傳算法應(yīng)用到排課問題中，從而證明混沌遺傳算法在解決排課問題方面能夠取得一定的效果。 論文首先對排課問題進(jìn)行了概述，介紹國內(nèi)外對這一問題的

3、研究現(xiàn)狀和發(fā)展趨勢，從高校排課實(shí)際情況出發(fā)，提出排課問題的數(shù)學(xué)模型。然后概括說明了遺傳算法的結(jié)構(gòu)、功能、特征，并分析了混沌理論的主要特點(diǎn)及現(xiàn)狀。針對遺傳算法的不足，把混沌引入到遺傳算法中，利用混沌序列的內(nèi)在規(guī)律性，有效地引導(dǎo)交叉和變異操作；而在遺傳算法中加入混沌優(yōu)化策略后，大大地拓展了算法的搜索空間，同時避免了標(biāo)準(zhǔn)遺傳算法容易陷入局部極小的缺陷。 最后論文分別采用標(biāo)準(zhǔn)遺傳算法和混沌遺傳算法對相同條件下的排課問題進(jìn)行仿真，通過比較