協(xié)同進化數(shù)值優(yōu)化算法及其應(yīng)用研究.pdf

1、協(xié)同進化是自然界的一種普遍現(xiàn)象。當(dāng)兩個或更多個種群之間的進化相互影響時，就出現(xiàn)了協(xié)同進化，它通常被用來解釋種群間的相互適應(yīng)現(xiàn)象。生物學(xué)研究表明協(xié)同進化對于生物進化是有益的。協(xié)同進化算法是將協(xié)同進化機制引入傳統(tǒng)進化算法而產(chǎn)生的一類進化算法的衍生算法。近年來，使用協(xié)同進化算法求解優(yōu)化問題已成為進化計算研究領(lǐng)域的一個重要方向。本文主要進行協(xié)同進化算法的研究，包括建立協(xié)同進化模型、設(shè)計協(xié)同進化算法和進行協(xié)同進化算法的應(yīng)用研究。本文在歸納總結(jié)現(xiàn)有

2、協(xié)同進化算法的基礎(chǔ)上將協(xié)同進化算法進行分類，并對各類協(xié)同進化算法的研究進展進行了綜述。之后，本文針對包括無約束優(yōu)化、約束優(yōu)化以及多目標(biāo)優(yōu)化在內(nèi)的數(shù)值優(yōu)化問題提出了新的協(xié)同進化模型以及若干新的算法和策略，并將這些新算法應(yīng)用于通信信號的檢測問題和以衛(wèi)星模塊布局設(shè)計為背景的帶平衡約束的圓形布局問題。本文的主要工作可概括如下：
　　 (1)借鑒協(xié)同進化和精英策略的思想，提出了解決高維無約束數(shù)值優(yōu)化問題的M-精英協(xié)同進化模型和M-精英協(xié)同

3、進化算法(M-Elite Coevolutionary Algorithm，MECA)。MECA算法認為適應(yīng)度較高的個體群(稱為精英種群)，在整個種群進化中起著主導(dǎo)作用。算法將整個種群劃分為由M個精英組成的精英種群和由其余個體組成的普通種群這樣兩個子種群，依次以M個精英為核心(稱為核心精英)來選擇成員以組建M個團隊。若選中的團隊成員是其他精英，則該成員與核心精英利用所定義的協(xié)作操作來交換信息；若團隊成員選自普通種群，則由核心精英對其進行

4、引導(dǎo)操作。其中，協(xié)作操作和引導(dǎo)操作由若干不同類型的交叉或變異算子的組合所定義。理論分析證明，算法以概率1收斂于全局最優(yōu)解。對15個標(biāo)準(zhǔn)測試函數(shù)的測試結(jié)果顯示，該算法對其中幾乎所有測試函數(shù)都能夠找到最優(yōu)解或好的次優(yōu)解。與兩種經(jīng)典的傳統(tǒng)進化算法以及三種其他協(xié)同進化算法相比，在適應(yīng)度函數(shù)評價次數(shù)相同時，該算法所求解的精度更高。同時，該算法的尋優(yōu)時間較短，甚至略短于同等設(shè)置下的標(biāo)準(zhǔn)遺傳算法。此外，對參數(shù)的實驗分析結(jié)果顯示，該算法對參數(shù)不敏感，易

5、于使用。
　　 (2)改進M-精英協(xié)同進化算法并將其擴展應(yīng)用于約束優(yōu)化問題。以M-精英協(xié)同進化模型為基礎(chǔ)，引入正交交叉算子，并使用靜態(tài)罰函數(shù)法處理約束，研究了M-精英協(xié)同進化算法在約束優(yōu)化問題中的應(yīng)用。利用13個約束優(yōu)化測試函數(shù)對算法進行了測試，仿真實驗和參數(shù)分析結(jié)果表明該算法尋優(yōu)精度高，尋優(yōu)時間少，算法穩(wěn)定，其性能優(yōu)于一些經(jīng)典的約束優(yōu)化進化算法，也優(yōu)于所對比的協(xié)同進化算法，能夠有效解決復(fù)雜的約束優(yōu)化問題。
　　 (3)

6、在M-精英協(xié)同進化的框架下引入非支配近鄰選擇機制，提出了非支配近鄰協(xié)同進化多目標(biāo)優(yōu)化算法(Nondominated Neighbor Coevolutionary Algorithm，NNCA)。將非支配種群根據(jù)擁擠距離的大小分為精英種群和普通種群，其中精英種群由nE個具有較大擁擠距離值的非支配個體組成。其所處區(qū)域個體分布越稀疏的精英個體，越有機會選擇更多成員來組建團隊，從而實現(xiàn)對其所在區(qū)域的更加充分的搜索。為避免當(dāng)非支配個體過少時算法

7、陷入因非支配近鄰選擇機制引起的“搜索停滯”狀態(tài)，NNCA采用精英規(guī)模保障機制，即當(dāng)精英種群實際規(guī)模達不到nE時，從由被支配個體構(gòu)成的備選種群中隨機選擇若干個備選個體遷移至精英種群中，使精英種群規(guī)模達到nE，從而避免算法在當(dāng)前非支配個體過少時僅圍繞有限的幾個非支配個體進行搜索以至陷入“搜索停滯”狀態(tài)。協(xié)同進化機制、非支配近鄰選擇機制和強調(diào)精英種群作用的思想相結(jié)合，使得算法具有較好的搜索能力和較強的收斂性。關(guān)于13個多目標(biāo)優(yōu)化測試問題的實驗

8、分析結(jié)果表明，與NSGA-Ⅱ、SPEA2以及NNIA等優(yōu)秀多目標(biāo)優(yōu)化進化算法相比，NNCA得到的Pareto最優(yōu)解在逼近性和寬廣性方面具有比較明顯的優(yōu)勢，而均勻性也僅次于SPEA2，優(yōu)于NSGA-Ⅱ和NNIA。
　　 (4)為解決垂直分層空時系統(tǒng)中的最大似然(Maximum-Likelihood，ML)檢測算法復(fù)雜度過高的問題，并針對通信系統(tǒng)對實時性要求較高的特點，設(shè)計了一種復(fù)雜度較低且性能優(yōu)良的算法，即M-精英進化算法(M-e

9、lite EvolutionaryAlgorithm，MEA)，并將其應(yīng)用于垂直分層空時系統(tǒng)的信號檢測，來逼近ML檢測算法的性能。通過一個經(jīng)典背包問題的仿真驗證了MEA求解組合優(yōu)化問題的有效性，實際的通信系統(tǒng)仿真表明基于MEA的檢測算法的性能優(yōu)于一些經(jīng)典的檢測算法，也優(yōu)于基于標(biāo)準(zhǔn)遺傳算法及克隆選擇算法的檢測算法，能夠較好地逼近ML檢測算法的性能。
　　 (5)將M-精英協(xié)同進化算法擴展應(yīng)用于求解帶平衡約束的圓形Packing問題

10、，該問題以衛(wèi)星模塊布局設(shè)計為背景，屬于NP難問題。通過使用靜態(tài)罰函數(shù)方法將約束Packing問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。首先利用Welded BeamDesign、Spring Design、Speed Reducer Design和Three-Bar Truss Design這4個工程設(shè)計優(yōu)化問題驗證了MECA解決實際工程問題的能力，之后對3個帶平衡約束的圓形Packing問題的典型算例進行了測試，結(jié)果顯示M-精英協(xié)同進化算法以較