一种双种群进化规划算法

大家好好利用

第!"卷!第#期!$$%年#月

计!!算!!机!!学!!报

&’()*+*,-./)01-2&-34.5*/+

6789!")79#

3:$$%;!

一种双种群进化规划算法

王向军!向!东!蒋!涛!林春生!龚沈光!方!兴

>%

>%

!%

!%

!%

>%&海军工程大学电气与信息工程学院

!%&海军工程大学兵器工程系<%&海军驻

<%

%<$$<<!武汉!L

%<$$<<!武汉!L

%?$"所军事代表室!武汉!L<$$?$

摘!要!在分析了导致进化规划算法早熟原因的基础上#提出了一种新的双群进化规划算法9在该算法中#进化在通过使用不同的变异策略#实现种群在解空间具有尽可能分散的探索能力的同时在两个不同的子群间并行进行#

局部具有尽可能细致的搜索能力9通过子群重组实现子群间的信息交换9对该算法性能进行的理论分析以及基于典型算例的数字仿真均证明该算法具有更好的性能9关键词!双群"进化规划"探索"搜索中图法分类号54>M

!"#$%&’(!)*#+$#&+.(#/0**#*044(/,-1233

>>!!

N0)OPA:E=,FE(0)OR7E,(0)O5:7()&SFE=+SGE!P!1QQ!Q

!<

O-)O+SGE=OF:E0)OPAEQ!2Q

>%&

%%%%

%%

%!"##$$"#$()*+(,#,-./-"*0,)+"-’-+-$$*+-1,2,#3-+2$*4+)-+-$$*+-678,-!L<$$<<%&’&%%#5"&’%%#

!%&

%9$,*)0$-)"$,"-*-+-$$*+-1,2,#3-+2$*4+)-+-$$*+-678,-!L<$$<<:&6:5’%%#5"&’%%#

<%&

%1,2,#;$*$4$-),)+2$,)1"<?$";$4$,*(8/-4)+)7)$#678,-!L<$$?$:

!56.*07.TG@:UFTGK7EHGTGEKGAJUSGV:U:8JS7TUK7@AEVUT:WAUA7E:8GH78FUA7E:TT7T:@=!4QQ7;IQ

#@AEX:JGW7EUSG:E:8JAJ7VTG@:UFTGK7EHGTGEKG7VUT:WAUA7E:8GH78FUA7E:TT7T:@@AE:Q9;IQ;IQQE7HG8XA=T7FH78FUA7E:TT7T:@@AEX*4%:87TAUS@AJIT77JGW9(EUSAJ:87TAUS@#GH7=QIQQI*;4QQ&

#8FUA7E7VUB7JFY=T7FJAJI:T:88G8IGTV7T@GWBAUSWAVVGTGEU@FU:UA7EJUT:UGAGJ:EWUSGEUSGQIQT7F:EGC87TGUSGJ78FUA7EJ:KGJG:T:UG8EWJG:TKSUSG87K:8:TUAEWGU:A8:88U7GUSGT9(E=QIKIII;:IQ

=V7T@:UA7EAJGCKS:EGWBSGEJFYT7FJ:TGTG7T:EAZGW94GTV7T@:EKG7VUSAJ:87TAUS@AJ:E:=QQIQQ8ZGWAEUSG7T9+A@F8:UA7EJY:JGW7EYGEKS@:T[JK7EVAT@US:UX*4:87TAUS@AJYGUUGTUS:EK8:J=;;Q

JAK:8GH78FUA7E:TT7T:@@AE87TAUS@AEUSG:JGKUJ7VQ87Y:87UA@AZ:UA7E#K7EHGTGEKG;IQQ:QIIQJGGW:EWUSGT7YFJUEGJJ9I

""8%9#*:6A=T7FGH78FUA7E:TT7T:@@AEGC87TGJG:TKS!YQI";IQQI1

解决实值连续函数全局优化$神经网络结构优化$模

;!引!言

进化计算借鉴生物界自然选择法则$遗传机制#利用选择$交叉$变异等操作模拟生物进化的过程以

>"<(

式识别与系统辨识等问题’进化规划&9*H78F=

#是进化计算中的代表算UA7E:TT7T:@@AE*4%;4QQ法之一#但大量的研究证明#由于过度选择$变异操作破坏有效模式$参数选取不当等原因#该算法存在

收稿日期!修改稿收到日期!王向军#男#博士#讲师#研究方向为进化计算$神经网络$电磁场理论9!$$<=>>=>!"!$$%=$!=!<9>"?<年生#!B向!东#*=@:A8CEFGA9JAE:9K7@9!HDI

万方数据

大家好好利用

M<%

计!!算!!机!!学!!报!$$%年

L"%"一些亟待克服的缺点!#$%进化容易出现过早收>?&M"

算法的性能!文献!提出了一种基于19?"\H;概

敛&从而陷入局部极值点&即早熟现象’$进化后!%期&个体之间的竞争趋缓导致算法后期的搜索效率降低’$%对初始参数敏感9本文针对传统进化规划算<法的弱点&提出了一种双群进化规划算法$XA=T7FQI&&种群按一定规*H78FUA7E:TT7T:@@AEX*4%;4QQ则划分为两个子群&其中一个子群使用振荡的高斯变异算子&以实现该子群中的个体能够尽可能分散地到达解空间的各个位置$即探索%&另一个以保证此子群中子群使用递减的高斯变异算子&

率分布的进化规划算法1在该算法中使用1*4&\H;变异代替变异&其核心思想是使用具有更大方差的变异算子来促使种群更快地收敛到函数的最优但使用大方差的变异算子将使种群逼近最优解9

解的速度变慢&精度降低9文献!提出了一种并M"行进化算法$&4:T:88G8*H78FUA7E:TT7T:@@AE;4QQ&在该算法中&多个种群同时使用高斯变异算4*4%子和柯西变异算子&其核心思想是同时利用高斯变异算子良好的局部搜索能力和柯西变异算子良的个体在每一个局部能够找到尽可能好的解$即

搜索%#9

两个子群间的信息通过种群的个体重组进行交换&这样就保证了整个种群既具有大范围的搜索能力&也具有局部寻优能力9理论分析以及对典型的进化算法算例的计算机仿真证明&此种算法具有良好的性能9

!-2算法

在传统*4算法中&参与进化的只有一个种群&因此在这个唯一的种群中的个体只能遵循唯一的规律进行进化$相同的高斯变异算子标准差!$%9较大的高斯变异算子可以保证种群具有较好的探索能力&

即能够以比较大的概率到达解空间的各个地方&种群$或者种群中的部分个体%能够以比较大的概率落在全局最优解所在的邻域&在每一个局部极值都具有很好的局部逃逸能力9但此种探索$局部逃逸%能力的取得是以降低解的精度为代价的&种群总是在全局最优解的附近跳转&无法使用足够小的变异来以足够高的精度逼近最优解9较小的高斯变异算子能够保证种群在局部具有良好的搜索能力&即能够以高的精度找到种群所在局部的极值&但小的变异算子不能$

或者需要很多的进化次数才能%产生足够大的变异从而使种群从这个局部进化到具有更大极值$或者全局最优解%的局部&从而早熟收敛9由于我们无法预知函数各个局部极值$包括全局最优解%的位置&也无法预知局部极值间的距离以及离全局最优解最近的局部极值与全局最优解间的距离&因此无法选取合适的!&使其既能大到足够使个体产生大的变异从局部极值点逃逸&又能小到使个体产生小的变异&在全局最优解附近以高的精度逼近最优解9

近年来万方数据&一些学者提出了很多方法来改善*4

好的全局探索能力&

以期既能快速收敛到最优解附近&又能有比较好的逼近精度9但是同一个体使用两种变异方式&导致算法的计算复杂度增加&算法的收敛速度受到影响&同时该算法对初始参数敏感9

=!双群进化规划算法流程

为了平衡算法的探索和搜索能力&使种群既能够从局部极值的邻域跳转到全局最优解的邻域&又能够在全局最优解的邻域内以高的精度进行搜索&本文提出一种双群进化规划算法9它是将种群按照一定规则划分为两个子群>+和>1<>1子群使用了较大的振荡的高斯变异算子!1&因而该子群具有良好的全局探索能力&在局部极值点的邻域内能够良好地逃逸<>+子群使用了递减的高斯变异算子!+&小的变异算子确保子群能够以很高的精度找到子群所在的局部的极值<该方法就好像有粗(细两个镜头的显微镜&

粗镜头用来在大范围内寻找感兴趣的目标&而细镜头则用来对找到的目标仔细观察&因此&称>1为粗调子群&>+为细调子群&!1为粗调算子&!+为细调算子<通过种群的重组可实现子群间的信息交流<算法流程如下#

><参数初始化<设置种群个体数目1$1取为偶数%&随机竞争个体数目?&最大进化代数@@:C&选取高斯变异算子标准差!$

&设置种群进化代数AB$&设置进化终止条件’!<

种群初始化<在问题的可行解空间中随机产生1个个体作为初始种群>$$%’

<<终止进化判断<满足&停止进化&输出计算结果’否则&转步L’

#

在本文中&严格区分探索$GC87TG%和搜索$的涵义&称之为探索JG:T&K而在种群S%种群到达此前未曾到达过的位置I

所9在位置的附近进行局部寻优&称之为搜索9

<

大家好好利用

#期

王向军等$一种双种群进化规划算法

M<?

随机选取1!其它个体组成种L<!个个体组成子群>+"群>1#

变异产生后代<子群>+中的个体按照如下方式进行#<变异$

%A&

+

如下方法进行处理$

如果则如果则

%&%&"C1DBC1HI1I+I+EI"%&%&"&C1DB!HC1IF%1I+I+EI%&%&"C1DBC1,I1I+I+EI#%&%&"&C1DB!,C1IF%1I+I+EI

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%A&

%&%%&?%&M%&"

C

%A&

+

%&+DBC

!%A&

+

%A&+%&+E"%A&

+%&>%&!

式中"$""为一服从1%!

%A&

&分布的高斯白噪声"

%GCFA&!!I+B$#

后产生的后代群体称为>D+<

式中"’为解空间在第I维的取值约束条,HI"I(

%A&

重复使用式%&&"直到C1%&件">"-(<%"D$$%I$’I+

式中"其选取与预期的求解精度有关<>+经变异#为一常数"

’,H<"(

子群>1中的个体按照如下方式进行变异$

C%A&%+DBC%A&%A1&1%+&E"&

1

%<&式中""%A&

为一服从1%$"!%A&11

&

分布的高斯白噪声"!%A&

1BG%J

AE$

@%@:C

F:TKJAE%>]G&&E>&

L&GB

L

%#

&式中"H为常数"代表种群在解空间中进行大范围搜索的次数"6为解空间在各个维的宽度<>1变异后产生的后代群体称为>D1<

子群高斯变异算子标准差随进化代数演变过程如图>"图!所示<

%<重组<>+">D+">1">D1组成临时种群>E

"

计算>E中1个个体的适应度函数"

使用随机?竞争法则"选取排在前的个体组成新的种群>%AE>&

#

?<ABAE>"

转步<

<图>!!%A&

+

随进化演变过程图!!!%A&

1

随进化演变过程

在使用X*4对函数进行优化时需注意两个

问题$

%>

&如果函数为多维"对于每一维的高斯变异算子应独立#

%!&算法使用很大的高斯变异算子!1

"因此变异后的子代可能超万方数据出问题的可行解空间"本文使用

II!数值仿真

为了比较X*4算法的性能"

我们用此算法与*4’?(算法)4*4算法’M(

同时进行函数优化以考察

算法的性能<在本文算法中参数选取如下$#B$^$>"B>$$<在函数优化过程中"各算法均有1BL$"B!#"@@:CB

#$$$<测试函数的表达式)函数维数以及函数的定义域分别如表>所示"

各函数的进化计算过程如图<%:&"%

V&所示<其中"横坐标表示进化代数"纵坐标表示函数值%也是进化过程中进化算法所使用的适应度函数&<

表;!测试函数

函数

维数1定义域

1

&>B%C+

!<$

%F>$$">$$

&1+B>1

+

&!

!B%%%C

I&<$%F>$$">$$

&1+B>IB>

1

&<BF+JAE

!$%$"#$$

&1+%C

B>1

&LB%*

C+!

F>$K7J%!$C+&E>$+!$

%F#^>!"#^>!

&1+B>

&#BF!$GCI*F$^

F!$%>1

F<!"<!

&1GCI

1K

7J%!$C+

!

&+B>

+E!$_GCI%>&&%B

LC!

>F!^>CL

>E<%

>

EC>C!F!%F#"#

&1LC!!ELCL!

从图<可以看出"在对函数进行优化的时候"

*4算法相对于其它两种改进的进化算法不仅具有更快的收敛速度"而且具有更高的收敛精度9X*4算法的良好性能特别表现在对高维函数的优化上"而且不仅是高维单峰函数%如图<%:&和%Y&所示&"也表现在对高维多峰函数的优化上%如图<%K&"%G&所示&<而对于低维函数"三种算法的优化性能基本相同%如图<%V&所示&<

>1H?!1X

大家好好利用

M<M

计!!算!!机!!学!!报!$$%年

图<!不同函数的进化过程

全局最优解所在的邻域!但是这些个体的变异强度

?!理论分析

在进化规划算法中!如果算法未能以指定精度搜索到全局最优解通常称之为不收敛!但经过分析发现!这种不收敛包含两种情况"

#$由于算法使用了不合适的变异算子标准差>#通常是过小$!导致种群陷入了局部极值不能脱离!因此求解精度不能满足需要!对于这种情况的不收敛在本文中定义为第一类不收敛!也就是平时所说的的早熟收敛%

#$由于算法使用了不合适的变异算子标准差!

万方数据#通常是过大$!种群中的某些个体虽然已经到达了

是如此地大!以至于个体与全局最优解间的距离始终不能足够地小!因此求解精度不能满足需要!对于这种情况的不收敛在本文中定义为第二类不收敛9

设待优化的一维函数如图L所示!假设某一时刻种群中的所有个体到达了函数的某个局部极值点但是还没有任何个体进入区域&!CCC#的附近!>!!’

假设算法的参数!$^>!1BL$!CC>!C$B#F!B!F

那么在传统的进化规划算法中!种群中在C$^#!>B

的概CCC#附近的个体经过一次变异进入区域&>!!’

率为

!F!!

J>’L$(GCCB<^>‘>$IF(!W>^#!$^>F

#$>$

(

>F

#$

大家好好利用

#期

王向军等’一种双种群进化规划算法

M<"

!

J!BGCC’$^<LIF!W$^$$$>!$^$$$>F

$%><

(

$

$%

图L!待优化函数的区域划分

也就是大约平均需要<‘>$

!>

代的进化!才有一个个体从局部极值进入区域"C>!C!#!而这个进化代数对于工程应用来讲实在是太长了!这也是理论上证明了能够全局收敛的*4算法之所以还会陷入局部极值的原因<在此时!种群陷入早熟收敛<

设种群中的某个个体经过有限次的进化后进入区域$C?!C!%!并位于C?附近!此时收敛精度对应的区域为"C%!C?#!而且有!$B$^>!C?FC%B$^$$$>!那么在传统的进化规划算法中个体经过一次变异进入收敛精度对应的区域"C%!C?#

的概率为J!B(

$

F

$^$$$>GCI$F!

!$^>!%

WC’L‘>$FL$>>%因此大约需要平均!#$$次进化才能有获得一个满

足精度要求的个体!这也就是较大的变异算子能够在设定的进化代数内搜索到全局最优解的邻域!但是在设定的进化代数内无法满足精度要求的原因<在此时!种群陷入了第二类不收敛<

假设某一时刻种群中的所有个体到达了函数的局部极值点C#的附近!

在X*4算法中!子群>1的高斯变异算子标准差!以@@:C1

H

为周期做振荡!只要H的取值比较合适!总可以在某个进化代数的时候!1落在">!>^##区间<假设此时!1B>^!!那么子群>1中的以个个体经过一次变异进入区域"C>!C!#的概率为

J>B(

F

>F

>^#GCI$F!&!

>^!!%

WC’$^$"?!$>!%对于一个包含!$个个体的子群而言!

经过一次变异平均就有大约两个个体进入区域"C>!C!#

<设子群>>中的某个个体经过有限次的进化后进入区域$C?!C!%!并位于C?附近<子群>+使用指数递减的高斯变异算子标准差!+!只要选取合适的值!

总可以使!+’$^$$$>!那么个体经过一次变异进入区域万方数据"C%!C?#

的概率为因此大约需要<次进化个体就能进入收敛精度对应的区域"C%!C?#

<正是由于X*4算法同时使用不同大小的变异算子标准差!从而保证种群中的个体既能对变量空间进行分散的探索!又能够对探索到的局部进行充

分的搜索9

!结!论

针对进化规划算法容易早熟收敛的弱点!从平衡进化规划算法的探索能力和搜索能力出发!本文提出了一种双群进化规划$X*4%算法9将种群的进化划分为两个并行的子群同时进行!一个子群使用振荡的高斯变异算子对解空间进行大范围地粗略地反复探索!另一个子群使用递减的高斯变异算子!对粗略寻找到的目标进行仔细地搜索9通过种群的重组实现子群间的信息交流与融合9通过典型算例!测试了X*4算法与一些改进的*4算法的性能!数值仿真结果证明!X*4算法具有更好的性能!而且这种良好的性能特别体现在高维函数的优化中9

参

考文献

a:7P9!1AFa990EGBGH78FUA7E:T;J;JUG@V7TGH78HAEQ:TUAVA=KA:8EGFT:8EGUB7T[J9(***5T:EJ:KUA7EJ7E)GFT:8)GUB7T[J!>""?!M$<%’%"L"?><

+GY:8W0969!+KS8GEZAQ,993AEA@:CWGJAQ

E7VEGFT:8EGUK7E=UT788GTJV7TSAQS8;FEKGTU:AEI8:EUJ9(***5T:EJ:KUA7EJ7E)GF=T:8)GUB7T[J!>""L!#$>%’?<"M!X7TES78WU+9!OT:FEWGEZR99OGEGT:8:J;@@GUTAKEGFT:8EGU=B7T[J:EWJUTFKUFTGWGJAQEY;QGEGUAK:8Q7TAUS@J9(***5T:EJ=:KUA7EJ7E)GFT:8)GUB7T[J!>""!!#$#%’<!?"<<L27QG8R9X990II8;AEQGH78FUA7E:T;IT7QT:@@AEQU7JG8GKUGWUT:HG8AEQJ:8GJ@:EIT7Y8G@9&;YGTEGUAKJ:EW+;JUG@!>""<!!L$>%’!?"<%a:7P9!1AFa9!1AEO99*H78FUA7E:T;IT7QT:@@AEQ@:WGV:J=UGT9(***5T:EJ:KUA7EJ7E*H78FUA7E:T;&7@IFU:UA7E!>"""!<$!%’M!">$!

+7EQ0A=OF7!1F,A=/GE90T:E[AEQY:JGW:W:IUAHGGH78FUA7E:T;

7IGT:U7TQGEGUAK:8Q7TAUS@905&0*8GKUT7EAK:+AEAK:!>"""!8!?$>%’M#"MM$AE&SAEGJG

%$宋爱国!陆佶人9一种基于排序操作的进化算子自适应遗传算法9电子学报!>"""!!?$>%’M#"MM%1GG&9!a:7P99*H78FUA7E:T;IT7QT:@@AEQFJAEQ@

FU:UA7EJ@>

!<

L

#

%?

#

大家好好利用

ML$

计!!算!!机!!学!!报!$$%年

Y:JGW7E1\HT7Y:YA8AUAJUTAYFUA7E9(***5T:EJ:KUA7EJ7E;I;W"#$!$$L!M>>"><*H78FUA7E:T7@FU:UA7E!;&IM

!a57EKSA@+9:7P994:T:88G8GH78FUA7E:TT7T:@@AE9(E$Q;IQQ

4T7KGGWAEVUSG!$$L(***(EUGTE:UA7E:8&7EVGTGEKG7E*H78F=Q7!$$#!>$><%!"><%

?UA7E:T7@FU:UA7E!;&I

A!")B(0/3CD+/!Y7TEAE>"?<!4S9R9!8GKUFTGT9’AJTGJG:TKSAEUGTGJUJAEK8FWGGH78FUA7E:T;K7@IFU:UA7E!EGFT:8EGUB7T[:EWG8GKUT7@:QEGUAKUSG7T;

907E3

*#+/:5SAJ:TUAK8GAJ7EGI:TU7VB:TJSAIT:WA7E7AJGK8:JJAVAK:=A7EIT7DGKUA7E9)GFT:8EGUB7T[AJBAWG8;FJGWAEJSAIE7AJGGK7QEAUA7E!YFUAUAJWAVVAKF8UU7WGJAQEGVVGKUAHGEGFT:8EGU=7T[!USGEBGUT;U7WGJAQEEGFT:8EGUB7T[FJAEQGH78FUA7E=T;:8Q7TAUS@94TG@:UFTGJ7@GUA@GJS:IIGEGWAEGH78HAEQ!BGK:EE7UQGU:SAQ

SIGTV7T@:EKGEGFT:8EGUB7T[K8:JJAVAGT9万方数据

5SGXA=QT7FIGH78FUA7E:T;IT7QT:@@AEQAJIT7I7JGWU7:H7AWUSGITG@:UFTG9.JAEQXA=QT7FIGH78FUA7E:T;IT7QT:@@AEQU7WGJAQEUSGEGFT:8EGUB7T[!BGQGUSAQSGTTGK7QEAUA7ET:UG:EWUA@G7VGH78FUA7EIT7KGJJAJJS7TUGTUS:EFJAEQ7USGTGH78F=UA7E:T;:8Q

7TAUS@J9’UTB:

本文来源：https://www.bwwdw.com/article/rufm.html