模擬植物生長(zhǎng)算法及其改進(jìn)研究

吳俊秋，何 迪

（1.上海交通大學(xué) 電信學(xué)院，上海 200240；2.上海海鷹機(jī)械廠，上海 200436）

模擬植物生長(zhǎng)算法及其改進(jìn)研究

吳俊秋1,2，何 迪1

（1.上海交通大學(xué) 電信學(xué)院，上海 200240；2.上海海鷹機(jī)械廠，上海 200436）

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

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

0 引 言

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

1 基本模擬植物生長(zhǎng)算法

PGSA是通過(guò)模仿大自然中植物對(duì)周圍環(huán)境的自我適應(yīng)性，在植物的生長(zhǎng)環(huán)境（整數(shù)搜索空間）內(nèi)建立隨機(jī)且向光源（全局最優(yōu)解）的生長(zhǎng)動(dòng)力模型。PGSA的生長(zhǎng)模式可以歸納如下：由一個(gè)種子（即初始點(diǎn)）向著2n（n為變量維數(shù)）個(gè)方向生長(zhǎng)成一個(gè)主干，再根據(jù)主干上每個(gè)生長(zhǎng)點(diǎn)的向光性不同分配形態(tài)素濃度（形態(tài)素濃度較大的生長(zhǎng)點(diǎn)，生長(zhǎng)幾率較高），在主干上生長(zhǎng)出新莖；隨后，根據(jù)現(xiàn)在生長(zhǎng)后的所有不同生長(zhǎng)點(diǎn)的向光性重新分配，新莖變?yōu)闃錀U，生長(zhǎng)新枝；如此反復(fù)進(jìn)行，直到?jīng)]有新的生長(zhǎng)點(diǎn)出現(xiàn)。莖和枝干上生長(zhǎng)點(diǎn)形態(tài)素濃度值的計(jì)算公式如下。

設(shè)樹干M和樹枝m上分別有k個(gè)和l個(gè)生長(zhǎng)點(diǎn)(SM1,SM2,…,SMk)和(Sm1,Sm2,…,Sml)，則樹干及樹枝上各生長(zhǎng)點(diǎn)形態(tài)素濃度分別為：

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

圖1 形態(tài)素濃度狀態(tài)空間

在該區(qū)間[0,1]內(nèi)共樹莖和樹枝m+l個(gè)生長(zhǎng)點(diǎn)，同時(shí)可根據(jù)式（1）和式（2）求出對(duì)應(yīng)的形態(tài)素濃度。隨后，在該閉區(qū)間內(nèi)隨機(jī)生成一個(gè)數(shù)η，將該隨機(jī)數(shù)所對(duì)應(yīng)的形態(tài)素濃度值的點(diǎn)作為下次的生長(zhǎng)點(diǎn)進(jìn)行生長(zhǎng)，并將該點(diǎn)移出生長(zhǎng)點(diǎn)集。新樹枝生長(zhǎng)完成后，所對(duì)應(yīng)的k與l值及其中這些生長(zhǎng)點(diǎn)所對(duì)應(yīng)的形態(tài)素濃度均會(huì)改變。如此反復(fù)，直到滿足終止條件為止。

2 模擬植物生長(zhǎng)算法的改進(jìn)

2.1 算法初始點(diǎn)的優(yōu)化改進(jìn)——重新初始化

為了避免可能陷入局部最優(yōu)解的情況，提高算法搜索全局最優(yōu)解的穩(wěn)定性，本文將對(duì)PGSA進(jìn)行重新初始化（即重新初始化PGSA），即算法在迭代過(guò)程從重復(fù)出現(xiàn)幾次相同的最優(yōu)解時(shí)重新初始化，以尋找全局最優(yōu)解，并與當(dāng)前搜索到的全局最優(yōu)解進(jìn)行比較。如果能搜索到新的最優(yōu)解，則原解為局部最優(yōu)；如果之后的幾次迭代不變，則認(rèn)為搜索出全局最優(yōu)解。

2.2 搜索步長(zhǎng)的改進(jìn)

為了提升算法運(yùn)算效率且保證適應(yīng)大部分模型，可以根據(jù)解的規(guī)模選取適當(dāng)?shù)牟介L(zhǎng)進(jìn)行變化（即變步長(zhǎng)PGSA）。本文對(duì)步長(zhǎng)進(jìn)行改進(jìn)，初始值選取一個(gè)比可行域小幾個(gè)數(shù)量級(jí)的數(shù)進(jìn)行搜索。如果在搜索最優(yōu)解的過(guò)程中，產(chǎn)生不屬于之前生長(zhǎng)點(diǎn)形成的生長(zhǎng)空間內(nèi)的點(diǎn)，則步長(zhǎng)將會(huì)減小1，直至減為1為止；反之，則步長(zhǎng)按之前進(jìn)行計(jì)算，隨后再次進(jìn)行搜索。

2.3 算法終止判據(jù)的改進(jìn)

本文將終止判據(jù)中每次迭代出現(xiàn)的最優(yōu)點(diǎn)適應(yīng)值出現(xiàn)的重復(fù)次數(shù)作如下定義：設(shè)變量e為一個(gè)隨著迭代次數(shù)而減小的線性值（3～5之間）；k為一個(gè)初始值為比可行域小幾個(gè)數(shù)量級(jí)的數(shù)，該數(shù)是不斷減小變化的值，可以為線性，也可以與變步長(zhǎng)改進(jìn)中的步長(zhǎng)值相同，最后直到該數(shù)減小到1，重復(fù)次數(shù)設(shè)定為k/e。如果達(dá)到，則視為該值已經(jīng)為全局最優(yōu)解；反之，則繼續(xù)迭代直至結(jié)束。

3 改進(jìn)的模擬植物生長(zhǎng)算法在電子干擾中的應(yīng)用

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

在空中，一架作戰(zhàn)飛機(jī)可能會(huì)同時(shí)遭到敵方的空中機(jī)載雷達(dá)、末制導(dǎo)雷達(dá)、近炸引信、地面搜索指揮雷達(dá)、地空導(dǎo)彈系統(tǒng)、炮瞄雷達(dá)、海面艦載雷達(dá)等有源干擾以及敵方飛機(jī)發(fā)射的紅外彈、箔條彈等無(wú)源干擾的威脅。不同的干擾方式對(duì)不同目標(biāo)的干擾能力與效果存在差異，為了保證自己的生存，需要能有效地對(duì)抗敵方諸多的威脅雷達(dá)和武器系統(tǒng)。

本文針對(duì)協(xié)同干擾資源分配，以獲得最優(yōu)干擾效果為目標(biāo)，建立電子干擾資源分配模型。針對(duì)傳統(tǒng)植物生長(zhǎng)算法收斂速度慢的不足，設(shè)計(jì)并采用改進(jìn)的植物生長(zhǎng)算法進(jìn)行干擾資源分配，最后進(jìn)行仿真驗(yàn)證和對(duì)比實(shí)驗(yàn)。

3.1 電子干擾資源分配模型

3.1.1 威脅目標(biāo)、干擾效果及干擾貢獻(xiàn)評(píng)估

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

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

目標(biāo)威脅評(píng)估是指在協(xié)同作戰(zhàn)體系中如數(shù)據(jù)鏈等利用前方雷達(dá)或自身偵查手段，將偵查到的敵方目標(biāo)雷達(dá)參數(shù)如載波頻率、到達(dá)時(shí)間、脈沖寬度、脈沖重復(fù)頻率和幅度等信息進(jìn)行結(jié)合，以判斷來(lái)襲目標(biāo)的威脅大小。本文將定義目標(biāo)威脅評(píng)估表達(dá)式為：

式中：ti表示第m個(gè)威脅目標(biāo)的威脅程度，F(xiàn)m-function表示目標(biāo)m的使用系數(shù)，Pj-imp表示j被敵方威脅的程度（注意：），Dmj表示目標(biāo)m對(duì)j的威脅距離程度，可表示為：

式中：dmp表示來(lái)襲目標(biāo)m距被保護(hù)目標(biāo)j的距離，dmax=max{dim|i∈W,m∈P}。

干擾機(jī)在進(jìn)行干擾工作時(shí)，主要使干擾信號(hào)對(duì)準(zhǔn)敵方雷達(dá)頻率和在極化上對(duì)準(zhǔn)敵目標(biāo)，同時(shí)需使用大功率的干擾源，且干擾源的樣式要與敵干擾方式相匹配，以此來(lái)提高干擾效果?？紤]到以上的種種因素，定義如下矩陣來(lái)評(píng)價(jià)干擾效果。

3.1.2 電子干擾資源分配模型的目標(biāo)函數(shù)設(shè)計(jì)

根據(jù)分析，定義來(lái)襲目標(biāo)的干擾貢獻(xiàn)函數(shù)為：

將干擾代價(jià)作用最小化是另一個(gè)電子干擾資源分配的目標(biāo)。在分配干擾資源時(shí)，優(yōu)先選擇距離目標(biāo)最近地面的基地內(nèi)的無(wú)人干擾機(jī)，可用下式表達(dá)：

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

干擾過(guò)程中，每個(gè)來(lái)襲目標(biāo)都需要一個(gè)分配資源與之對(duì)應(yīng)，且保障一部干擾機(jī)對(duì)應(yīng)一個(gè)目標(biāo)雷達(dá)，即：

另外，考慮到每個(gè)基地每種類型的無(wú)人干擾機(jī)數(shù)目是有限的，即：

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

3.1.3 電子干擾資源分配模型

最后，建立電子干擾資源分配的數(shù)學(xué)模型為：

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

3.2 基點(diǎn)、變量的處理

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

3.3 改進(jìn)的PGSA的電子干擾資源分配

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

圖2 改進(jìn)PGSA的電子干擾資源分配流程

本文采用文獻(xiàn)[7]中部分仿真條件測(cè)試系統(tǒng)數(shù)據(jù)，以測(cè)試所采用的基本模擬植物生長(zhǎng)算法（基本PGSA）與改進(jìn)模擬植物生長(zhǎng)算法（改進(jìn)的PGSA）的電子干擾資源分配，以驗(yàn)證其性能。

假設(shè)該系統(tǒng)具有5部地面干擾雷達(dá)，其分布在2個(gè)基地周圍。某時(shí)發(fā)現(xiàn)6個(gè)不同的威脅源，此時(shí)需要將部署在2個(gè)基地的共8架飛機(jī)調(diào)配協(xié)同作戰(zhàn)完成任務(wù)，從而使干擾資源使用最優(yōu)，確保基地安全。采用威脅源信息、基地坐標(biāo)干擾源等信息，如表1所示。

表1 威脅源信息、基地坐標(biāo)、干擾源等信息

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

表2 基本PGSA與改進(jìn)的PGSA的典型參數(shù)

算法測(cè)試都獨(dú)立運(yùn)行50次，分別將兩種方法求得的系統(tǒng)最優(yōu)電子干擾資源分配值f，比較如表3所示?；綪GSA與改進(jìn)的PGSA的電子干擾資源分配值f獨(dú)立運(yùn)行50次的平均值隨迭代次數(shù)的變化曲線如圖3所示。從圖3中可以看出，本章所采用的方法可以使系統(tǒng)更快取得最優(yōu)電子干擾資源分配值，具有更好的全局尋優(yōu)能力。

表3 基本PGSA與改進(jìn)的PGSA運(yùn)行結(jié)果

圖3 算法適應(yīng)值變化趨勢(shì)

4 結(jié) 語(yǔ)

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

[1] 李彤,王春峰,王文波等.求解整數(shù)規(guī)劃的一種仿生類全局優(yōu)化算法——模擬植物生長(zhǎng)算法[J].系統(tǒng)工程理論與實(shí)踐,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] 阮智健.基于改進(jìn)PGSA的預(yù)應(yīng)力鋼結(jié)構(gòu)優(yōu)化設(shè)計(jì)及其拉索索力識(shí)別方法研究[D].廣州:華南理工大學(xué),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] 劉學(xué).農(nóng)村集中供水管理模式與運(yùn)營(yíng)問(wèn)題研究[D].無(wú)錫:江南大學(xué),2012. LIU Xue.The Research on Rural Centralized Water Supply Management Model and Operational Issues[D]. Wuxi:Jiangnan University,2012.

[7] 瞿曉峰.資源調(diào)度機(jī)制的研究及其在電子對(duì)抗中的應(yīng)用[D].南京:南京航空航天大學(xué),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—），男，在職碩士，助理工程師，主要研究方向?yàn)闊o(wú)線電、雷達(dá)、電子對(duì)抗系統(tǒng)維護(hù)、測(cè)試與研究；

何 迪（1975—），男，博士，副教授，主要研究方向?yàn)闊o(wú)線通信、通信信號(hào)處理等。

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