遺傳算法的研究及其在TTP問題中的應(yīng)用.pdf

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

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

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