異步分層并行演化算法及其在模糊聚類分析中的應(yīng)用.pdf

1、演化計(jì)算是一種基于自然選擇和遺傳變異等生物進(jìn)化機(jī)制的全局性概率搜索算法，能夠在不要求函數(shù)連續(xù)、可微、單峰的情況下，找到問(wèn)題的近似全局最優(yōu)解。基于這些優(yōu)點(diǎn)，演化計(jì)算被廣泛地應(yīng)用于NP和NPC難題求解、神經(jīng)網(wǎng)絡(luò)優(yōu)化、多目標(biāo)優(yōu)化問(wèn)題求解及其它眾多領(lǐng)域。然而，隨著問(wèn)題規(guī)模和復(fù)雜程度的不斷提高，串行演化算法的搜索過(guò)程將成倍地增長(zhǎng)，由此，并行演化計(jì)算成為一個(gè)重要的研究方向。Cantú-Paz將并行演化計(jì)算劃分為四種類型，分別是主從模型、粗粒度模型、

2、細(xì)粒度模型和分層模型。這些模型通常在MPI、PVM和OpenMP等并行編程環(huán)境下實(shí)現(xiàn)。 為了避免傳統(tǒng)并行演化算法中常見(jiàn)的“征服問(wèn)題”和“無(wú)效問(wèn)題”，克服過(guò)早收斂，提高算法運(yùn)行效率，本文提出了異步分層并行演化算法(AsynchronousHierarchicalParallelEvolutionaryAlgorithm，AHPEA)。在算法中，對(duì)擴(kuò)展的模糊交叉算子進(jìn)行改進(jìn)，加入了適應(yīng)值信息，提出基于標(biāo)準(zhǔn)化適應(yīng)值的模糊交叉算子(Fu

3、zzyRecombinationOperatorBasedonStandardizedFitness,SF-FRO)，提高算法的收斂速度。并在此基礎(chǔ)上提出異構(gòu)模型，為各子種群的交叉操作應(yīng)用不同的全局/局部搜索度，指定相異的種群拓?fù)洌垣@取適當(dāng)?shù)倪x擇壓力。最后將各子種群充分連接，構(gòu)建異步遷移模型。本文提出的AHPEA算法有效地解決了“征服問(wèn)題”和“無(wú)效問(wèn)題”，避免了算法的過(guò)早收斂，提高了算法效率。 在仿真研究中，基于一組被廣泛使用

4、的測(cè)試問(wèn)題集，從交叉算子SF-FRO、異構(gòu)模型和異步遷移三個(gè)方面對(duì)AHPEA算法進(jìn)行性能測(cè)試。實(shí)驗(yàn)結(jié)果表明：(1)SF-FRO由于引入了適應(yīng)值信息，為算法指明了潛在的搜索方向及范圍，能夠有效地提高算法的收斂速度；(2)AHPEA算法在求解大型多峰值問(wèn)題時(shí)采用異構(gòu)模型比采用同構(gòu)模型具有更優(yōu)越的性能；(3)在AHPEA算法的各子種群間進(jìn)行異步遷移，無(wú)論從理論分析還是仿真研究的角度來(lái)看，都極大地提高了算法的性能。 作為AHPEA算法的