基于病毒進(jìn)化遺傳算法排課系統(tǒng)的研究與實(shí)現(xiàn).pdf

1、1976年S.Even和Cooper證明了排課問題是一個NP完全問題，不存在精確求解排課問題的多項式時間算法，需借助智能算法尋找其較合理和滿意的近似最優(yōu)解。遺傳算法通過模擬自然界生物遺傳中的“優(yōu)勝劣汰、適者生存”原則，避免陷入局部最優(yōu)解，從而實(shí)現(xiàn)對最優(yōu)解或次優(yōu)解的快速搜索，被廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化等領(lǐng)域，是當(dāng)今影響深遠(yuǎn)的進(jìn)化計算方法之一，但其存在著局部早熟收斂和進(jìn)化后期搜索速度下降等問題。
　　病毒進(jìn)化遺傳算法通過引入病毒種

2、群的感染、復(fù)制和刪減操作在實(shí)現(xiàn)了種群的生物多樣性的同時，又保持了遺傳算法原有的同代間基因信息傳遞，有效的實(shí)現(xiàn)了上下代種群之間的縱向遺傳信息傳遞和同代種群的橫向進(jìn)化信息傳遞，獲得了較為滿意的算法收斂性能，有效的克服了傳統(tǒng)遺傳算法固有早熟和收斂性能不佳的缺點(diǎn)。本文借鑒病毒進(jìn)化遺傳算法的思想對排課問題進(jìn)行了研究與應(yīng)用，其主要工作如下:
　　1.系統(tǒng)研究了排課問題，并根據(jù)課題的實(shí)際需要，分析了排課問題的基本要素、各類軟、硬約束條件和求解目

3、標(biāo)，建立了排課系統(tǒng)的數(shù)學(xué)優(yōu)化模型。
　　2.在總結(jié)了遺傳算法在排課問題中的應(yīng)用研究后，針對排課問題本身的特點(diǎn)，提出一個適宜解決該問題的改進(jìn)病毒進(jìn)化遺傳算法(ImprovedVirusEvolutionaryGeneticAlgorithm，IVEGA)，其主要改進(jìn)在于:(1)改進(jìn)傳統(tǒng)病毒種群的隨機(jī)生成方式，有效的利用了排課歷史數(shù)據(jù)和約束條件，加快了病毒種群的收斂。(2)針對排課問題設(shè)計了一種有效的基因編碼方式，使得原有算法更有針對