中垂線遺傳融合算法研究

摘 要：為改善遺傳算法的局部尋優(yōu)性能和收斂速度，提出了一種將遺傳算法和中垂線相算法結合的融合算法——中垂線遺傳算法。中垂線遺傳算法以遺傳算法進行全局搜索，再以中垂線算法進行局部搜索。并將中垂線算法中的單一種群分化為雙種群，將雙種群中的優(yōu)秀個體進行耦合交叉和變異，提升改進算法的全局搜索能力和跳出局部最優(yōu)的能力。仿真實驗討論了算法轉換系數(shù)的變化對改進算法性能的影響。通過與6個算法的對比實驗，證明改進的中垂線遺傳算法解決了傳統(tǒng)遺傳算法收斂速度慢和局部尋優(yōu)能力弱的問題。并且與主流優(yōu)化算法和其他遺傳融合算法相比，改進的算法性能更加優(yōu)越。最后，利用改進算法處理了三桿桁架的設計問題，結果表明了中垂線遺傳算法在處理實際問題時具有可行性。

關鍵詞：遺傳算法 中垂線算法 融合算法 雙種群 三桿桁架設計

中圖分類號：TP3-05

Research on the Genetic Midperpendicular Fusion Algorithm

CHEN Wei HE Yujie WU Dafei

Yunnan Land and Resources Vocational College， Kunming， Yunnan Province， 652501 China

Abstract： In order to improve the local optimizaton performance and convergence speed of the genetic algorithm， this paper proposes a fusion algorithm that combines the genetic algorithm and the midperpendicular algorithm： the genetic midperpendicular algorithm. The genetic midperpendicular algorithm performs global search with the genetic algorithm and then local search with the midperpendicular algorithm， and it differentiates a single population in the midperpendicular algorithm into a double population， and cross-couples and mutates the excellent individuals in the double population， so as to improve the global search ability and the ability to jump out of the local optimum of the improved algorithm. Simulation experiments discuss the effect of the variation of the conversion coefficients of the algorithm on the performance of the improved algorithm. Through comparison experiments with six algorithms， it is proved that the improved genetic midperpendicular algorithm solves the problems of the slow convergence speed and weak local optimization ability of the traditional genetic algorithm. Compared with the mainstream optimization algorithm and other genetic fusion algorithms， the performance of the improved algorithm is more superior. Finally， the improved algorithm is used to deal with the design problem of the three-rod truss， and results show that the genetic midperpendicular algorithm is feasible in dealing with practical problems.

Key Words： Genetic algorithm; Midperpendicular algorithm; Fusion algorithm; Double population; Three-rod truss design

遺傳算法（Genetic Algorithm ， GA）通過模擬自然界的基因變化和自然選擇過程進行工作 [1，2]。雖然遺傳算法具有良好的全局搜索能力，但局部搜索能力較差，且迭代速度較慢，因此對于遺傳算法的改進一直是研究的熱點。改進遺傳算法的方式眾多，如改進編碼方式[3]、優(yōu)化種群規(guī)模[4]、優(yōu)化遺傳操作[5]等，以其他算法與遺傳算法相結合的方式效果顯著[6]。因此，許多學者已對混合遺傳算法進行了深入研究。如吳永忠等人[7]以自適應模擬退火遺傳算法解決傳統(tǒng)遺傳算法局部搜索精度不高的問題，該方法雖提升了遺傳算法的局部搜索性能，但改進算法收斂速度較慢且局部搜索性能仍較低。武曉金等人[8]將免疫算法與遺傳算法結合起來，構建了免疫遺傳算法，擴大了遺傳算法的應用范圍。徐雨等人[9]成功將免疫遺傳算法應用于車間調度的求解，但該方法沒有提升算法的局部搜索性能，對收斂速度的改善不大。徐金梧等人[10]提出運用小生境技術解決傳統(tǒng)遺傳算法的多種不足。

上述融合算法雖改善了遺傳算法的一定性能，但改進算法的收斂速度和局部尋優(yōu)性能乃至于實用性還有進一步改善的空間。中垂線算法（Midperpendicular Algorithm，MA）依托于中垂線上的任意一點到被垂直平分的線段端點的距離相等這一性質進行工作。MA局部搜索能力較強，迭代速度快，但全局搜索能力較弱。本文提出將GA與MA進行融合，以GA進行全局搜索，以MA進行局部搜索；同時將MA的種群分化為雙種群，在每次迭代結束后，將雙種群優(yōu)秀個體進行耦合交叉和變異操作，籍此解決MA和GA存在的一些問題。

1 遺傳算法與中垂線算法結合算法

1.1 遺傳算法

GA通過模擬生物進化中的基因選擇和自然選擇過程進行尋優(yōu)操作，具體尋優(yōu)過程為將問題抽象為染色體，其中一個染色體對應一個問題的解，利用適應度評價染色體后，適應度好的個體有更高的概率被保留，保留的染色體再進行交叉、選擇、變異等方式產生下一代染色體，直至找到最優(yōu)點。算法的基本步驟為：（1）初始化算法參數(shù)，生成初始群體；（2）計算初始群體中每個個體的適應度；（3）判斷終止條件，若滿足終止條件則進行解碼操作后結束算法；（4）利用選擇、交叉、變異產生新群體。

1.2 中垂線算法

中垂線算法的核心原理是以線段的中垂線上的任意一點到該線段的兩個端點之間的距離相等的性質不斷縮小尋優(yōu)區(qū)間，直至尋到最優(yōu)點。算法通過選取當前最優(yōu)的兩個點A和點B作為線段的端點，作出該線段的中垂線后，中垂線可將固定的取值區(qū)域分割為兩部分，一部分為A點所在區(qū)域，另外一部分為B點所在區(qū)域，若最優(yōu)點P居于A點所在區(qū)域，則必存在以下條件，

即P點到A點的距離小于P點到B點的距離。依照以上規(guī)律，在算法中，MA通過計算點A和點B的適應度，即可確定最優(yōu)值所在區(qū)域。之后在該區(qū)域內隨機取點，重復上述操作即可找到最優(yōu)值。

假定粒子，并定義每次迭代選取的兩個最優(yōu)粒子A和B為

算法產生初始個體j的第i個元素的公式為：

其中為的最小值，為的最大值，表示0-1的隨機數(shù)。算法開始迭代后，產生新個體j的第i個元素的公式為：

式（3）中：為當前迭代次數(shù)；為最大迭代次數(shù)；為范圍因子。

產生的新的點須有任意兩個維度的值需滿足以下條件

其中

算法終止條件為

式（6）中：為當前最優(yōu)粒子的適應度；為設定的精度因子。

算法的步驟為：（1）初始化參數(shù)：包括最大迭代次數(shù)，范圍因子，精度因子，個體取值范圍和；（2）根據(jù)公式2產生初始粒子，并評價粒子的適應度；（3）選擇適應度最佳的粒子作為粒子A和B；（4）根據(jù)式（3）產生新粒子，并判定新粒子是否符合公式4的條件，若不滿足，則重新產生新粒子。直至生成的粒子達到種群數(shù)。（5）判斷是否滿足公式6的算法終止條件，若滿足，則終止算法，否則跳轉至（3）。

1.3 中垂線遺傳算法

1.3.1 中垂線遺傳算法的搜索策略

GA的全局搜索能力良好，但算法收斂速度慢，局部搜索能力較差；MA的全局搜索能力偏弱，但算法收斂速度極快，且有較好的局部搜索能力。將GA與MA結合，組成一種組合算法—遺傳中垂線算法（Genetic Midperpendicular Algorithm，GMA）。GMA前期利用GA進行全局搜索，若GA搜索到的最佳粒子的適應度滿足人工設定參數(shù)或設定GA的迭代次數(shù)k達到人工設定參數(shù)γ，即

（7）

則改用采用MA進行局部搜索。

1.3.2 中垂線遺傳算法的雙種群耦合交叉變異策略

交替算法進行搜索的策略雖使得GMA具備GA的全局搜索性能和MA的局部搜索性能，但無法提升GMA跳出局部最優(yōu)的能力，為此，引入一種雙種群耦合交叉變異的策略，進一步提升算法的全局尋優(yōu)能力和跳出局部最優(yōu)的能力。

當MGA交替到MA進行局部搜索后，該策略將種群分化為種群1和種群2。設定GA和MA交替時，種群1的最佳兩個體分別為A和B，種群2的兩個最佳兩個體分別為C和D。且有，。兩個種群按照MA的搜索策略搜索最優(yōu)值，搜索過程中兩種群完全獨立。

為減少MGA的時間復雜度，采用實數(shù)編碼方式進行交叉和變異操作。當每次迭代結束后，兩種群的兩個最佳個體隨機進行交叉，當任意個體進行交叉操作時，其余三個體被選為交叉對象的概率相同，交叉概率Pc控制兩個體的交叉概率。當交叉結束后，每個個體會進行變異操作，變異概率Pm控制個體基因的變異概率，當?shù)趉次迭代時個體的第j個變量需進行變異時，按MA的收斂策略完成變異，即

可得到交叉變異后的個體、、和，將初始最優(yōu)個體A、B、C和D與變異后的個體進行比較，若交叉變異后的個體適應度更優(yōu)，則代替初始最優(yōu)點。

MGA算法流程圖如圖1所示。

2 仿真實驗與分析

2.1 準備工作

實驗的6個對照算法：遺傳算法、中垂線算法、粒子群優(yōu)化算法（Particle Swarm Optimization， PSO）、多肉植物算法[11]（Succulent Plant Algorithm， SPA），模擬退火遺傳算法（Simulated Annealing Genetic Algorithm， SAGA），遺傳粒子群算法（Genetic Particle Swarm Optimization Algorithm， GPSOA），算法初始參數(shù)設定如表1所示（其中所有遺傳融合算法遺傳算法部分參數(shù)設置同遺傳算法，融合粒子群算法參數(shù)同粒子群優(yōu)化算法），本節(jié)所有實驗的算法種群個數(shù)均為50，最大迭代次數(shù)為500次。

為驗證新算法的性能，以MGA對8個常見的基準函數(shù)進行尋最優(yōu)值。8個基準函數(shù)見表2。包括兩個單模態(tài)函數(shù)（F1，F(xiàn)2），4個多模態(tài)函數(shù)（F2-F6），2個固定維度函數(shù)（F7，F(xiàn)8）[10-13]。

2.2 MGA參數(shù)分析

在MGA中，參數(shù)或γ的選取會直接影響算法的性能，為確定和γ對算法的影響，選取了三個函數(shù)F1（單模態(tài)函數(shù)）、F6（多模態(tài)函數(shù)）、F7（固定維度函數(shù)），設定不同的和γ，獨立運行30次MGA并記錄最終結果的均值（Mean），平方差（Std），結果如表3和表4所示。

由表3可看出，隨著的變化，MGA的收斂精度和穩(wěn)定性呈現(xiàn)不規(guī)則變化，F(xiàn)1和F7的數(shù)據(jù)均表明，選擇合適的可提升MGA的穩(wěn)定性和收斂精度。從3個目標函數(shù)的結果來看，的值不應過大。

從表4中可以看出，隨著γ的變化，MGA的收斂性和穩(wěn)定性呈現(xiàn)無規(guī)則變化。處理不同函數(shù)，MGA的最佳γ均不同，且最佳γ的取值需根據(jù)實際函數(shù)確定。

不同λ參數(shù)下，MGA收斂情況如圖2所示。由圖可看出，參數(shù)設定得越大，則MGA的收斂速度越快。由以上分析可得，選取λ時，首先應確保λ大于GA尋找到的最優(yōu)值；若想提升MGA的全局搜索能力，λ不應設置過大；若想提升MGA的收斂速度，應設定相對較大的λ。

不同γ參數(shù)下，MGA收斂情況如圖3所示。MGA的收斂速度隨著γ的增加不斷減慢。結合表4數(shù)據(jù)，當MGA采用γ為交換算法的條件，若想提升算法的收斂速度應選擇較小的 γ。

2.3 MGA收斂精度分析

為確定MGA的收斂精度，以MGA對表1所示目標函數(shù)進行30次獨立尋優(yōu)。選用迭代次數(shù)進行遺傳中垂線算法的轉換且設γ=25。為突出MGA算法的優(yōu)越性，選取6個其他算法進行相同操作，結果如表5所示。由表5可得，在F5、F6和F8的目標函數(shù)尋優(yōu)中，GMA在7種算法中收斂精度的表現(xiàn)最好；當目標函數(shù)為其他函數(shù)時，MGA的表現(xiàn)一般。GMA在所有目標函數(shù)的測試中的收斂精度表現(xiàn)均優(yōu)于GA和MA，并且同其他兩種主流遺傳融合算法相比，收斂精度表現(xiàn)最佳。

2.4 MGA穩(wěn)定性分析

由表5可看出，當目標函數(shù)為F5，F(xiàn)6時，MGA穩(wěn)定性在7種算法中表現(xiàn)最佳，當目標函數(shù)為其他函數(shù)時MGA的穩(wěn)定性均位于中游水平。且相較于GA和MA，除目標函數(shù)為F4和F8時，MGA的穩(wěn)定性均優(yōu)于二者。同其他主流算法和遺傳融合算法相比，同樣具有極強的競爭力。

2.5 MGA收斂速度分析

7種算法在不同的目標函數(shù)中的收斂情況如圖4所示，從圖中可看出，在各算法處理眾多函數(shù)的收斂過程中，雖MGA的收斂速度慢于MA ，但相比于GA，MGA的收斂速度大幅增加，緩解了GA收斂速度慢的問題；同其他流行的主流算法相比，MGA的收斂速度更加優(yōu)越；與兩種遺傳融合算法相比，MGA的收斂速度同樣更快。

3 三桿桁架設計問題分析

三桿桁架設計是一個工程問題，設計的目標是在考慮到應力約束和體積的情況下，評估最佳橫截面積。圖5顯示了三桿桁架的結構。問題的數(shù)學描述如下：

由MGA獨立處理該問題30次，MGA利用迭代次數(shù)轉換算法，且γ=25，種群數(shù)為50，最大迭代次數(shù)為500次，結果如表6所示。從表中可以看出MGA的尋優(yōu)結果均為在時取值158.58。說明MGA在處理真實工程問題具有可行性。圖6為MGA處理三桿桁架算法收斂曲線。

4 結語

本文將GA與MA算法進行融合，首先以GA進行全局搜索，達到算法轉換條件后，再以 MA進行局部搜索的策略融合兩種算法，再以MA雙種群耦合交叉變異策略增強了算法跳出局部最優(yōu)的能力和算法的穩(wěn)定性。仿真實驗表明MGA改善了MA局部搜索能力不足，GA收斂速度慢、局部搜索能力弱的問題。同主流算法相比，MGA無論是穩(wěn)定性、收斂精度和收斂速度均具備極強的競爭力。同其他兩種遺傳融合算法相比，MGA更加優(yōu)越。最后，成功將MGA應用于三桿桁架的設計問題中，證明了MGA應用于實際問題的可行性。

參考文獻

[1] 鄭立平，郝忠孝.遺傳算法理論綜述[J].計算機工程與應用，2003（21）：50-53，96.

[2] 馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，29（4）：1201-1206，1210.

[3] 李韙韜，王惠南，錢志余.遺傳算法的一種新穎編碼研究[J].信息與控制，2006（5）：624-628，633.

[4] 史明霞.多種群協(xié)同演化遺傳算法[J].商丘師范學院學報，2006（2）：72-74.

[5] 潘家文，錢謙，伏云發(fā)等.模糊自適應并行遺傳算法在函數(shù)優(yōu)化中的應用[J].小型微型計算機系統(tǒng)，2021，42（11）：2313-2322.

[6] 吳玫，陸金桂.遺傳算法的研究進展綜述[J].機床與液壓，2008（3）：176-179，172.

[7] 吳永忠，劉華威，侯詩文等.模擬退火遺傳算法在風力提水機翼型優(yōu)化設計中的研究[J].太陽能學報，2021，42（6）：385-390.

[8] 武曉今，韓生廉.免疫-遺傳系統(tǒng)的構造及在函數(shù)尋優(yōu)中應用[J].遼寧工程技術大學學報（自然科學版），2001（5）：669-672.

[9] 徐雨，黃海松，胡淶.一種求解車間調度的混合免疫遺傳算法[J].機械設計與制造，2020（9）：287-291.

[10] 徐金梧，劉紀文.基于小生境技術的遺傳算法[J].模式識別與人工智能，1999，12（1）：104-108.

[11] ONG K，ONG P，SIA C K. A carnivorous plant algorithm for solving global optimization problems[J].Applied Soft Computing，2021，98：106833.