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

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

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

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

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