模擬植物生長算法及其改進研究

吳俊秋，何 迪

（1.上海交通大學 電信學院，上海 200240；2.上海海鷹機械廠，上海 200436）

模擬植物生長算法及其改進研究

吳俊秋1,2，何 迪1

（1.上海交通大學 電信學院，上海 200240；2.上海海鷹機械廠，上海 200436）

模擬植物生長算法（Plant Growth Simulation Algorithm，PGSA）是針對整數規劃問題提出的一種仿生類隨機優化算法。通過分別對重新初始化、搜索步長，算法終止判據等方面進行研究與改進，以達到縮短算法運行時間、提高最優解精度的效果。使用電子干擾資源分配模型對改進后的PGSA進行仿真研究，并與基本PGSA比較。仿真結果表明本文提出的三種改進方法能明顯地提升算法的穩定性、改善算法終止判據的自適應能力、提高算法全局收斂性，具有很好的理論意義與實用價值。

模擬植物生長算法；初始化；可變搜索步長；算法終止判據；電子干擾資源分配模型

0 引 言

隨著科學技術的發展，傳統的一些求解模型已無法滿足求解需要。在這種情況下，研究一種新的求解方法或對原模型進行改進，十分必要。PGSA是根據Aristid Lindenmayer等人在1968年提出的一個計算機模擬植物生長系統（L-systems）演化而來的。該算法是遵循大自然中植物或者樹木的一定生長規律，繼而被提出的一種智能優化搜素算法。目前，國內外對于模擬植物生長的研究還處在起步階段，且國外主要針對模擬植物生長的過程進行研究。國內最早對于該算法的研究，是由天津大學的李彤、王春峰等人于2005年提出[1]，并將該算法運用于求解整數規劃問題，取得了較為滿意的效果。至此，基本PGSA產生，并被廣大學者所熟知。隨后，在基于靜力平衡的索力識別問題[2]、消除冗余讀卡問題[3]、射頻識別網絡優化問題[4]以及在配電網絡重構等問題中[5]進行應用。

1 基本模擬植物生長算法

PGSA是通過模仿大自然中植物對周圍環境的自我適應性，在植物的生長環境（整數搜索空間）內建立隨機且向光源（全局最優解）的生長動力模型。PGSA的生長模式可以歸納如下：由一個種子（即初始點）向著2n（n為變量維數）個方向生長成一個主干，再根據主干上每個生長點的向光性不同分配形態素濃度（形態素濃度較大的生長點，生長幾率較高），在主干上生長出新莖；隨后，根據現在生長后的所有不同生長點的向光性重新分配，新莖變為樹桿，生長新枝；如此反復進行，直到沒有新的生長點出現。莖和枝干上生長點形態素濃度值的計算公式如下。

設樹干M和樹枝m上分別有k個和l個生長點(SM1,SM2,…,SMk)和(Sm1,Sm2,…,Sml)，則樹干及樹枝上各生長點形態素濃度分別為：

式中，X0為初始種子值，f(*)為生長點的背光函數。受光越小，f(*)的函數值越大，且該函數值隨著生長點受光照的增大而減小[6]。由上式不難證明，因而其形態素濃度狀態空間構成如圖1所示。

圖1 形態素濃度狀態空間

在該區間[0,1]內共樹莖和樹枝m+l個生長點，同時可根據式（1）和式（2）求出對應的形態素濃度。隨后，在該閉區間內隨機生成一個數η，將該隨機數所對應的形態素濃度值的點作為下次的生長點進行生長，并將該點移出生長點集。新樹枝生長完成后，所對應的k與l值及其中這些生長點所對應的形態素濃度均會改變。如此反復，直到滿足終止條件為止。

2 模擬植物生長算法的改進

2.1 算法初始點的優化改進——重新初始化

為了避免可能陷入局部最優解的情況，提高算法搜索全局最優解的穩定性，本文將對PGSA進行重新初始化（即重新初始化PGSA），即算法在迭代過程從重復出現幾次相同的最優解時重新初始化，以尋找全局最優解，并與當前搜索到的全局最優解進行比較。如果能搜索到新的最優解，則原解為局部最優；如果之后的幾次迭代不變，則認為搜索出全局最優解。

2.2 搜索步長的改進

為了提升算法運算效率且保證適應大部分模型，可以根據解的規模選取適當的步長進行變化（即變步長PGSA）。本文對步長進行改進，初始值選取一個比可行域小幾個數量級的數進行搜索。如果在搜索最優解的過程中，產生不屬于之前生長點形成的生長空間內的點，則步長將會減小1，直至減為1為止；反之，則步長按之前進行計算，隨后再次進行搜索。

2.3 算法終止判據的改進

本文將終止判據中每次迭代出現的最優點適應值出現的重復次數作如下定義：設變量e為一個隨著迭代次數而減小的線性值（3～5之間）；k為一個初始值為比可行域小幾個數量級的數，該數是不斷減小變化的值，可以為線性，也可以與變步長改進中的步長值相同，最后直到該數減小到1，重復次數設定為k/e。如果達到，則視為該值已經為全局最優解；反之，則繼續迭代直至結束。

3 改進的模擬植物生長算法在電子干擾中的應用

電子干擾是以破壞敵方各種電子設備的正常工作，導致敵方指揮系統和武器系統失靈而喪失戰斗力所釋放電波擾亂的一種措施。它使敵方的通信中斷、雷達迷盲，從而提高載機在作戰中的生存能力。

在空中，一架作戰飛機可能會同時遭到敵方的空中機載雷達、末制導雷達、近炸引信、地面搜索指揮雷達、地空導彈系統、炮瞄雷達、海面艦載雷達等有源干擾以及敵方飛機發射的紅外彈、箔條彈等無源干擾的威脅。不同的干擾方式對不同目標的干擾能力與效果存在差異，為了保證自己的生存，需要能有效地對抗敵方諸多的威脅雷達和武器系統。

本文針對協同干擾資源分配，以獲得最優干擾效果為目標，建立電子干擾資源分配模型。針對傳統植物生長算法收斂速度慢的不足，設計并采用改進的植物生長算法進行干擾資源分配，最后進行仿真驗證和對比實驗。

3.1 電子干擾資源分配模型

3.1.1 威脅目標、干擾效果及干擾貢獻評估

假設作戰系統由敵機和地面指揮臺構成，干擾資源可分為機載干擾機和地面干擾機兩種。機載干擾機分散于多個地理位置不同的基地，且根據干擾種類不同。設定Ri為地面干擾機，R={Ri|i∈[1,NR]}為地面干擾機資源集合，資源總數|R|=NR。設定表示部署在基地性能為d的機載干擾機為機載干擾資源集合，資源數目|vad|=Nad，其中基地集合A={Ai|i∈[1,NA]}，飛機性能集合D={Di|i∈[1,ND]}。Vad=?表示基地a沒有裝備性能d的無人機。設定WI為威脅目標，W={Wi|i∈[1,NW]}為干擾目標集合，目標數目|T|=NT。設定Pi為某受保護目標，P={Pi|i∈[1,NP]}為保護目標集合，目標數目|P|=NP。將機載干擾資源和地面干擾資源的并集稱為干擾資源集合Rsum，則總的干擾資源數目：

便于建模，對集合R、W、P中每個元素采用下標進行編號，如集合R={Ri|i∈[1,NR]}可表示為R={1,2,…,NR}。集合V中元素按照a,d,i順序排序，可得將V與編號集合num={NR+1,NR+2,…，Nsum}中的元素按其所在位置進行逐個映射，且其映射方式采用f(numi)=Vi。因此，集合干擾源可轉換為Rsum={1,2,…,NR,NR+1,…,Nsum}。

目標威脅評估是指在協同作戰體系中如數據鏈等利用前方雷達或自身偵查手段，將偵查到的敵方目標雷達參數如載波頻率、到達時間、脈沖寬度、脈沖重復頻率和幅度等信息進行結合，以判斷來襲目標的威脅大小。本文將定義目標威脅評估表達式為：

式中：ti表示第m個威脅目標的威脅程度，Fm-function表示目標m的使用系數，Pj-imp表示j被敵方威脅的程度（注意：），Dmj表示目標m對j的威脅距離程度，可表示為：

式中：dmp表示來襲目標m距被保護目標j的距離，dmax=max{dim|i∈W,m∈P}。

干擾機在進行干擾工作時，主要使干擾信號對準敵方雷達頻率和在極化上對準敵目標，同時需使用大功率的干擾源，且干擾源的樣式要與敵干擾方式相匹配，以此來提高干擾效果。考慮到以上的種種因素，定義如下矩陣來評價干擾效果。

3.1.2 電子干擾資源分配模型的目標函數設計

根據分析，定義來襲目標的干擾貢獻函數為：

將干擾代價作用最小化是另一個電子干擾資源分配的目標。在分配干擾資源時，優先選擇距離目標最近地面的基地內的無人干擾機，可用下式表達：

式中：DISim表示無人干擾機i與來襲目標m之間的距離，其最大值DISmax=max{DISim|i∈(Rsum-R),m∈W}，表示被分配的無人干擾機總數，1/(N·DISmax)是歸一化因子。

干擾過程中，每個來襲目標都需要一個分配資源與之對應，且保障一部干擾機對應一個目標雷達，即：

另外，考慮到每個基地每種類型的無人干擾機數目是有限的，即：

同樣，被分配的干擾資源數量也不能超過基地部署的資源總數：

3.1.3 電子干擾資源分配模型

最后，建立電子干擾資源分配的數學模型為：

約束條件如式（13）、式（14）和式（15）所示，即同時滿足：

3.2 基點、變量的處理

本文將模型利用式（12）、式（13）、式（14）和式（15）作為目標函數及約束條 件。利用一 組整數數組X表示生長過程中的基點及各生長點。將電子干擾資源分配的模型采用兩者同時對干擾源協同作用的工作模式，假設Nsum≥2NW，每個元素可代表干擾資源號，其內容代表對威脅源起作用的編號，即X[i]=m表示干擾資源i對威脅源m起作用。為了方便編程，將X剩余部分（Nsum-2NW）的空余位置用0替代。當X[i]=m時，干擾貢獻PROim=0。

3.3 改進的PGSA的電子干擾資源分配

改進的PGSA的電子干擾資源分配流程圖如圖2所示。其中，對基本模擬植物生長算法在初始化的優化改進——重新初始化、對搜索步長選取的改進以及對算法終止判據的改進，具體方法論述分別見前文。

圖2 改進PGSA的電子干擾資源分配流程

本文采用文獻[7]中部分仿真條件測試系統數據，以測試所采用的基本模擬植物生長算法（基本PGSA）與改進模擬植物生長算法（改進的PGSA）的電子干擾資源分配，以驗證其性能。

假設該系統具有5部地面干擾雷達，其分布在2個基地周圍。某時發現6個不同的威脅源，此時需要將部署在2個基地的共8架飛機調配協同作戰完成任務，從而使干擾資源使用最優，確保基地安全。采用威脅源信息、基地坐標干擾源等信息，如表1所示。

表1 威脅源信息、基地坐標、干擾源等信息

本文的測試在CPU型號Intel core i3、主頻2.27 GHz、內存容量2 G的Matlab 7.10.0平臺上進行，使用基本PGSA以及綜合改進PGSA分別對其進行電子干擾資源分配。這兩種方法的維數都是13，迭代次數均為60次。詳細參數設置如表2所示。

表2 基本PGSA與改進的PGSA的典型參數

算法測試都獨立運行50次，分別將兩種方法求得的系統最優電子干擾資源分配值f，比較如表3所示。基本PGSA與改進的PGSA的電子干擾資源分配值f獨立運行50次的平均值隨迭代次數的變化曲線如圖3所示。從圖3中可以看出，本章所采用的方法可以使系統更快取得最優電子干擾資源分配值，具有更好的全局尋優能力。

表3 基本PGSA與改進的PGSA運行結果

圖3 算法適應值變化趨勢

4 結 語

本文在基本模擬植物生長算法的基礎上，改進與修改一部分參數設置，系統分析改進對算法收斂精度、收斂速度的影響。本文使用電子干擾資源分配問題對改進后的PGSA進行仿真研究，并與基本PGSA進行比較。仿真結果表明，本文提出的改進方法能明顯提升算法的穩定性，改善算法終止判據的自適應能力，提高算法全局收斂性，具有很好的理論意義與實用價值。

[1] 李彤,王春峰,王文波等.求解整數規劃的一種仿生類全局優化算法——模擬植物生長算法[J].系統工程理論與實踐,2005,1(01):76-85. LI Tong,WANG Chun-feng,WANG Wen-bo,et al.A Global Optimization Bionics Algorithm for Solving Integer Programming-Plant Growth Simulation Algorithm[J].Systems Engineering-Theory & Practice,2005,1(01):76-85.

[2] 阮智健.基于改進PGSA的預應力鋼結構優化設計及其拉索索力識別方法研究[D].廣州:華南理工大學,2015. RUAN Zhi-jian.Research on Optimization Design of Prestressed Steel Structure based on Improved PGSA and Cable Force Identification Method[D].Guangzhou:South China University of Technology,2015.

[3] Shilei Lu,Shunzheng Yu.A Middleware-Based Model for Redundant Reader Elimination Using Plant Growth Simulation Algorithm[C].Computational Intelligence and Security(CIS),2013:36-40.

[4] HUANG Yi-hua,LV Shi-lei.RFID Network Planning based on k-Coverage Using Plant Growth Simulation Algorithm[C].Computing Technology and Information Management(ICCM),2012:196-201.

[5] Muthu Kumar R,Thanushkodi K.Network Reconfiguration and Restoration in Distribution Systems through Oppostion based Differential Evolution Algorithm and PGSA[C].Current Trends in Engineering and Technology (ICCTET),2013:284-290.

[6] 劉學.農村集中供水管理模式與運營問題研究[D].無錫:江南大學,2012. LIU Xue.The Research on Rural Centralized Water Supply Management Model and Operational Issues[D]. Wuxi:Jiangnan University,2012.

[7] 瞿曉峰.資源調度機制的研究及其在電子對抗中的應用[D].南京:南京航空航天大學,2010. QV Xiao-feng.Research on Mechanisms of Resource Allocation and its Application in Electronic Warfare[D]. Nanjing:Nanjing University of Aeronautics and Astronautics The Graduate School,2010.

吳俊秋（1990—），男，在職碩士，助理工程師，主要研究方向為無線電、雷達、電子對抗系統維護、測試與研究；

何 迪（1975—），男，博士，副教授，主要研究方向為無線通信、通信信號處理等。

Plant-Growth Simulation Algorithm and Its Improved Algorithm

WU Jun-qiu1,2, HE Di1
(1.School of Electronic Information and Electronical Engineering, Shanghai Jiaotong University, Shanghai 200240, China; 2. Shanghai Haiying Machinery Factory, Shanghai 200436, China)

PGSA (Plant-growth simulation algorithm) is a kind of bionics random optimization algorithm aiming at integer programming problem. Based on the research of reinitialization, changeable search stepsize， termination criterion, a modified PGSA is proposed and simulated, which could reduce algorithm runtime and promote the precision of optimal solution. The modified PGSA is applied to resource allocation model of cooperative jamming in electronic warfare, and then its simulation results are compared with those of the basic PGSA. Simulation results indicate that the three improvements could significantly promote stability and adaptability of the termination criterion and raise global convergence of the algorithm. This is of great theoretical and practical value.

PGSA(Plant Growth Simulation Algorithm); reinitialization; changeable search step-size; termination criterion; resource allocation model of cooperative jamming in electronic warfare

TP183；TN974

A

1002-0802(2016)-12-1629-06

10.3969/j.issn.1002-0802.2016.12.011

2016-08-10

2016-11-06 Received date:2016-08-10;Revised date:2016-11-06