一種新型粒子群改進遺傳算法

劉 露，陳 贊，劉世劼，章 靜，朱雯雯

(1.上海航天控制技術研究所，上海 201109； 2.上海航天電子通訊設備研究所，上海 201109； 3.上海航天技術研究院，上海 201109)

一種新型粒子群改進遺傳算法

劉 露1，陳 贊2，劉世劼2，章 靜3，朱雯雯1

(1.上海航天控制技術研究所，上海 201109； 2.上海航天電子通訊設備研究所，上海 201109； 3.上海航天技術研究院，上海 201109)

傳統優化算法均存在各種局限，無法同時滿足性能優良算法的幾個標準：不容易陷入局部最優解、收斂速度較快、具有框架性及可結合性。在傳統粒子群與遺傳算法的基礎上，結合其他常用算法，提出一種新型混合智能優化算法——粒子群改進遺傳算法。該算法在變異環節、交叉環節、淘汰環節中引入許多其他算法的優點加以改進。最后，通過修正某控制系統的控制參數驗證了新算法相對于傳統單一優化算法的先進性。

遺傳算法；粒子群算法；模擬退火；局部最優

0 引言

借鑒于生物生態學的物種進化理論，基于種群的智能優化算法以其獨有的并行搜索優勢吸引了眾多科研工作者的研究。其概念首次提出于1966年，由Fogel等人提出了進化規劃，由Rechenberg和Schwefel提出了進化策略。在此基礎上，作為智能算法領域最經典的遺傳算法于1975年由Holland[1]提出，并于1992年由Koza通過其提出的遺傳規劃加以完善。

經過50多年的發展，一個性能良好的種群智能優化算法應該具有全局隨機搜索規律、全局優化性能、魯棒性、高搜索精度和收斂速度快等優點。

現階段比較常用的智能算法如遺傳算法、粒子群算法、蟻群算法、模擬退火算法等均存在各種局限，無法同時滿足性能優良算法的5個標準，例如遺傳算法易過早收斂、粒子群算法搜索精度不高、蟻群算法易陷入局部最優解且收斂速度慢[2]。

若將各個智能算法的優勢混合應用，可得到一個同時具有多個算法優點的新算法[3]。本文在遺傳算法的基礎上引入其他優化算法的局部環節，提出了一種新智能算法——粒子群改進遺傳算法。

1 粒子群改進遺傳算法概述

粒子群改進遺傳算法使用標準遺傳算法作為算法的主框架，在變異環節、交叉環節、淘汰環節中引入許多其他算法的優點加以改進。其添加的主要環節及效果概述為：改進基礎變異、引入強化變異、改進交配對象選擇方法、改進交叉環節、自適應調節迭代速率、改進淘汰機制、改進單一優化目標，以及陷入最優解的自我調整。

該算法綜合了近10種算法的優秀特性，主要適用于求解復雜、大型、具有很多局部最優解，對優化的精度要求較高，且優化問題對優化時間的要求并不嚴苛的優化問題。

2 算法細節設計

2.1 算法變異環節設計

算法變異環節包括粒子群移動變異和變異環梯度變異兩個順序進行的環節，其具體設計如下：

在粒子群移動變異的過程中，首先更新每個粒子群的最優性能及全部粒子群的最優性能。隨后，按標準粒子群算法更新全部個體的運動速度，并計算每個個體的速度是否滿足速度約束條件，如果超速，則將該個體的對應性能調整為超速的臨界點[4]。然后，在上一步得到粒子運動速度的基礎上，對全部個體的性能進行更新，并檢查更新后的個體性能是否滿足約束條件，若不滿足則將對應個體性能調整為約束條件的臨界點，從而完成粒子群迭代的單步操作。

在變異環節中，父本變異的步驟主要為以下幾步：

(1)在全部待優化參數組成的高維空間中隨機選擇一組向量，作為待變異環的法向方向，選擇本步迭代的迭代步長，作為待變異環的半徑，選擇待變異的父本個體作為變異環的圓心，就此組成變異環；

(2)在變異環中平均選取10個點作為子代胚胎，并求出各個胚胎的適應度指標，對全部子代胚胎連同其父本進行性能排序，選取前2名作為該父本變異后得到的子代個體；

(3)子代個體在粒子群環節的相關屬性如粒子最優性能和運行速度均與其父本相同。

2.2 算法交叉環節設計

算法的交叉環節包含選擇交配對象、生成子代胚胎及子代和引入移民個體等三個順序執行的步驟，其設計流程圖如圖1所示。

圖1 生成胚胎的算法設計流程圖

生成胚胎后對全部胚胎及其父母進行性能排序，選取前2名作為該父母的子代。交叉環節的第三步為添加移民算子。移民算子的實現比較簡單，在算法優化空間中隨機初始化Nadd數量的粒子，計算這些粒子的適應度函數，并將滿足基本約束條件的粒子加入到種群中。

2.3 算法淘汰環節設計

經過遺傳、交叉兩個大環節的演算，粒子總數量已達到該步迭代前的4～6倍，因此，需要淘汰環節保持種群數量的一致性[5]。取種群平均馬氏的一半作為種群間個體距離過近評判標準的閾值MTS，對種群中個體間距離小于閾值的個體對進行內部淘汰，即對這兩個距離過近的個體按性能指標排序，將排序末位個體淘汰。

2.4 算法的自適應性

2.4.1迭代收斂程度的量化

收斂程度的量化可分為三個部分：最優個體適應度值的進步程度Ebest、平均適應度值的進步程度Eava及個體間的集群聚集程度Ddr。各個指標的計算方法如式(1)～式(3)所示：

Ebest,i=100×

(1)

(2)

(3)

其中，Fj,i表示第i次迭代，種群第j個個體的適應度指標。系統的綜合迭代收斂程度指標Ecm寫作如式(4)所示：

Ecm=Kava×Eava+Kbest×Ebest+Kdr×Ddr

(4)

式(4)中各個指標的系數由各個指標的物理意義、量綱及權重決定。對于描述進化速度百分比Ebest和Eava的兩個指標，本文取適應度指標在50代內增加30%為判定收斂的界限，經過計算，Ebest和Eava兩個指標判定為收斂的界限為0.53%；而對于描述代內代際性能指標分布比率的指標Ddr，本文取分布比率為1作為判定收斂的界限[6]。取這三個指標的權重分別為30%、30%和40%，得到綜合迭代收斂程度的表達式如式(5)所示：

(5)

將式(5)整理，得到其標準計算公式如式(6)所示：

Ecm=0.556×Eava+0.556×Ebest+0.4×Ddr

(6)

因此，當綜合收斂指標Ecm小于1時，可判定該步迭代系統處于收斂的狀態。

2.4.2基于算法收斂程度的調整

該算法的核心在于迭代過程中根據收斂的程度動態調整迭代控制參數。當種群趨向于收斂時，需要動態調整迭代控制參數來保證算法的搜索范圍、迭代精度等。算法中可自適應修正的變量及其性質如表1所示。

表1 優化算法可修正變量一覽表

當綜合收斂指標小于1時，即將4個自適應變量向收斂趨勢方向調整，反之則向相反的方向調整，其調整幅度與綜合收斂指標的數值有關。該算法可使整體迭代過程更具有智能性。

3 控制器設計的實物驗證

本文分別用普通遺傳算法、普通粒子群算法、改進遺傳算法及粒子群改進遺傳算法4種方法解決實際工程問題，以此驗證提出的新算法相對傳統優化算法的先進性。

3.1 優化問題及優化指標

該優化問題為修正某控制系統的控制參數，以使該控制系統對階躍信號產生的輸出信號的震動及內部電機輸入信號的震動最小化。待修正的原控制系統結構圖如圖2 所示。

圖2 原控制結構結構圖

由于震蕩會導致系統運行故障，降低系統運行可靠性，因此，需要通過修改系統參數或系統結構來消除或最大程度地減弱震蕩。首先對系統的輸出震蕩程度進行數學描述，其震蕩程度Evib的評價指標的計算公式如式(7)所示：

(7)

其中，e1(t)、e2(t)分別為電機輸入信號和系統輸出信號，S1、S2分別為電機輸入信號和系統輸入信號在tn時間內的震動次數。

3.2 4種優化算法求解效果對比

調節控制系統參數使系統的震蕩程度Evib最小化，需要調節的控制參數k1～k8如圖3所示。

圖3 系統可調節參數圖

使用普通遺傳算法、粒子群改進遺傳算法、普通粒子群算法及其他文獻中的抽象粒子群遺傳算法分別對系統可調節系數進行100代優化迭代，得到經過4種算法迭代優化后的可調節參數組合，4種優化參數下系統的輸出信號和電機的輸入信號分別如圖4和圖5所示。

圖4 4種優化算法100次迭代后輸出信號圖

由圖4～圖5可以看出，4種優化算法經過100代優化迭代得到的系統輸出信號及電機輸入信號的震動均在1.3 s后達到平穩，而粒子群改進遺傳算法相較于其他3種算法其輸出信號和電機輸入信號均震動程度更小，波動更加平穩。因此，可驗證粒子群改進遺傳算法是一個優化性能更好的算法。

圖5 4種優化算法100次迭代后電機輸入信號圖

4 結論

本文在傳統粒子群與遺傳算法的基礎上，結合其他常用算法，提出一種新型智能優化算法——粒子群改進遺傳算法。該算法在變異環節、交叉環節、淘汰環節中引入許多其他算法的環節并為了性能優化結果的進一步提高而加以改進。該算法相對于普通遺傳算法或普通粒子群算法均具有很強的收斂性能和規避局部最優解的能力，而算法的時間開銷依舊在可接受范圍內。

[1] 戴朝華.搜尋者優化算法及其應用研究[D]. 成都：西南交通大學，2010.

[2] 匡芳君.智能混合優化算法及其應用研究[D]. 南京：南京理工大學，2014.

[3] 關沫, 佟彤. 多核系統的實時任務調度算法研究[J]. 微型機與應用, 2016, 35(2):17-19.

[4] AVRIEL M.Nonlinear programming:Analysis and methods[M].Mineola, NY: Dover Publishing,2003.

[5] FOGEL L J,OWENS A J,WALSH M J.Artificial inmlligence through simulated evolution[M]. New York: Jollll Wiley,1966.

[6] RECHENBERG I. Evolutions strategie-optimierung technischer systeme nach prinzipien der biologischen evolution[M]. Stuttgart: Fromman-Holzboog,1973.

A new particle swarm optimization improved genetic algorithm

Liu Lu1, Chen Zan2, Liu Shijie2, Zhang Jing3, Zhu Wenwen1

(1. Shanghai Aerospace Control Technology Institute, Shanghai 201109, China;(2. Shanghai Aerospace Electronic Technology Institute, Shanghai 201109, China;3. Shanghai Academy of Spaceflight Technology, Shanghai 201109, China)

There are several limitations in the traditional optimization algorithms, which can not satisfy the performances of excellent algorithms at the same time: it is not easy to fall into the local optimal solution, the convergence speed is faster, have a framework and compatibility. In this paper, based on the traditional particle swarm and genetic algorithm, combined with other commonly used algorithms, a new intelligent optimization algorithm is proposed which is called Particle Swarm Optimization Improved Genetic Algorithm. The algorithm introduces many advantages of other algorithms in the process of variation, intersection, elimination and improves the performance of optimization results. Finally, the application in optimizing parameters in a control system proved the advantages of the new algorithm.

genetic algorithm; particle swarm optimization algorithm; simulated annealing algorithm; local optimal

TM46; TN86

A

10.19358/j.issn.1674- 7720.2017.23.005

劉露，陳贊，劉世劼，等.一種新型粒子群改進遺傳算法[J].微型機與應用，2017,36(23)：17-20.

2017-06-06)

劉露(1991-)，女，碩士，工程師，主要研究方向：飛行控制系統仿真測試。

陳贊(1982-)，男，碩士，工程師，主要研究方向：通信系統設計。

劉世劼(1987-)，男，碩士，工程師，主要研究方向：通信系統設計。