遺傳算法的研究及其在TTP問題中的應用.pdf

1、時間表問題TTP(TimeTableProblem)是一類特殊的資源調(diào)度問題，是一個多因素優(yōu)化決策問題，也是組合優(yōu)化中的典型問題。隨著計算機的飛躍發(fā)展以及各高校教學管理體制的完善，用計算機來輔助排課成為了各大高校急需解決的問題。本文以大連交通大學研究生學院的時間表問題--排課問題為研究對象，分析了其約束條件，建立了數(shù)學模型，提出了基于遺傳算法的改進算法，并用此算法解決排課問題。 遺傳算法GA(GeneticAlgorithm)作

2、為一門新興學科，從二十世紀八十年代開始迅速發(fā)展。它是一種用于解決優(yōu)化問題的并行尋優(yōu)算法，已被廣泛用于解決各類NP問題。 標準遺傳算法仍然存在一些缺陷，為了克服這些缺陷，本文設(shè)計了一個全新的改進遺傳算法MEGA(ModifiedandEvolvedalgorithmbasedonGeneticAlgorithm)，這一算法在進化方式上與傳統(tǒng)的改進遺傳算法明顯不同，最后用遺傳算法常用的測試函數(shù)對MEGA算法進行數(shù)學分析，證實了它相對

3、基本的遺傳算法有一定的改進。 通過設(shè)計MEGA算法的選擇、交叉、變異算子等，證明了MEGA.算法能有效地消除沖突，保證種群多樣性，防止局部早熟收斂；通過一些典型函數(shù)測試驗證了其有效性；處理排課問題時把課程分為兩類，簡化了問題的求解難度。在變異過程中引入混沌理論，在較優(yōu)個體的變異操作中引入一個混沌小擾動，并把混沌運動的遍歷范圍“放大”到優(yōu)化變量的取值范圍，通過一代代地不斷進化，收斂到一個最適合環(huán)境的個體上，求得問題的最優(yōu)解。