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

關(guān)鍵詞：遺傳算法 中垂線算法 融合算法 雙種群 三桿桁架設(shè)計

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

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

1 遺傳算法與中垂線算法結(jié)合算法

1.1 遺傳算法

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

1.2 中垂線算法

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

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

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

算法產(chǎn)生初始個體j的第i個元素的公式為：

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

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

產(chǎn)生的新的點(diǎn)須有任意兩個維度的值需滿足以下條件

其中

算法終止條件為

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

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

1.3 中垂線遺傳算法

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

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

（7）

則改用采用MA進(jìn)行局部搜索。

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

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

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

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

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

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

2 仿真實(shí)驗(yàn)與分析

2.1 準(zhǔn)備工作

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

為驗(yàn)證新算法的性能，以MGA對8個常見的基準(zhǔn)函數(shù)進(jìn)行尋最優(yōu)值。8個基準(zhǔn)函數(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ù)），設(shè)定不同的和γ，獨(dú)立運(yùn)行30次MGA并記錄最終結(jié)果的均值（Mean），平方差（Std），結(jié)果如表3和表4所示。

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

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

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

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

2.3 MGA收斂精度分析

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

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

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

2.5 MGA收斂速度分析

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

3 三桿桁架設(shè)計問題分析

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

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

[10] 徐金梧，劉紀(jì)文.基于小生境技術(shù)的遺傳算法[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.