基于空間交配遺傳算法的收斂性分析.pdf

1、遺傳算法(Genetic Algorithm,GA)是一種基于Darwin進化論和Mendel遺傳學說的優(yōu)化搜索算法。它因具有簡單、通用、魯棒性強的特點,自誕生以來，獲得了廣泛的關(guān)注和應(yīng)用，美國Michigan大學Holland教授在GA理論和方法的系統(tǒng)性研究方面作了很多開創(chuàng)性的工作,相關(guān)研究也日漸成為計算機科學、信息科學與最優(yōu)化領(lǐng)域研究的熱點。
　　遺傳算法在實際應(yīng)用方面已取得了巨大的成就,但其基礎(chǔ)理論的研究卻相對滯后，尤其是缺

2、乏廣泛而完整的遺傳算法收斂性理論。遺傳算法的收斂性是關(guān)系到算法是否有效執(zhí)行的關(guān)鍵。針對遺傳算法的早熟收斂、收斂緩慢甚至不收斂等多種不足,國內(nèi)外學者進行了大量的研究，并提出了許多的改進措施，以提高遺傳算法的收斂速度。這些改進的方法在很大程度上提高了算法性能，有力地推動了遺傳算法的發(fā)展。然而這些算法大都只是用實驗的方法進行了驗證,缺乏相應(yīng)的理論分析和證明。
　　鄭金華教授提出的基于空間交配遺傳算法(Genetic Algorithm

3、Based on Space Mating,GASM)有效克服了早熟收斂,實驗效果好，但也缺少相關(guān)理論的證明。
　　為此，該論文把基于空間交配遺傳算法作為研究對象，對其收斂性進行分析和證明，同時提出另外一種改進的遺傳算法。論文的主要研究內(nèi)容包括以下兩個方面:
　　(1)本文采用馬爾可夫鏈分析了基于空間交配遺傳算法的收斂性。證明了采用最優(yōu)個體保留機制的GASM,可以收斂到全局最優(yōu)解;同時證明了,在沒有變異算子的情況下,GASM

4、以概率1收斂到全局最優(yōu)解。通過4個測試問題(其中3個為多峰值復(fù)雜問題)的對比實驗,結(jié)果表明,GASM在求解多峰值復(fù)雜問題時,比采用最優(yōu)個體保留機制的經(jīng)典遺傳算法(Elitist Genetic Algorithm, EGA),具有更好的收斂性。同時與快速蜂群優(yōu)化算法進行了比較試驗,實驗表明,GASM在絕大部分函數(shù)中仍可體現(xiàn)出其優(yōu)越性。
　　(2)針對單個種群的遺傳算法容易陷入局部收斂而出現(xiàn)早熟的情況,本文提出了一種改進的遺傳算法—