小生境遗传算法-micro-GA

计算机科学2007Vol 134№14

　

浮点数编码小生境遗传算法的研究3)

崔明义

(河南财经学院计算机科学系　郑州450002)

　

摘　要　小生境在增加遗传算法群体的多样性, 提高遗传算法的局部搜索能力方面具有良好的性能。迄今为止, 有关

小生境遗传算法的研究都是基于二进制编码, 缺乏以浮点数编码为研究对象的相应成果。而浮点数编码在提高遗传算法的性能和遗传算法的推广应用中, 具有其它编码所无法比拟的优势。本文以浮点数编码为研究对象, 研究小生境遗传算法的机理, 分析在遗传操作中小生境的生成、合并和分离的动态过程, 探索其方法。本文的研究和实验结果表明, 浮点数编码小生境遗传算法的性能是可靠的, 方法是可行的。关键词　小生境, 浮点数编码, 遗传算法　

R esearch on Niche G enetic Algorithm of Float Number Code

CU I Ming 2Y i

(Dept. of Computer Science , Henan University of Finance &Economics , Zhengzhou 450002)

　

Abstract 　Niche has better performance in increasing the population diversity of genetic algorithm (GA ) , in improving local researching performance of it. So far , research results of relating to niche GA are all on binary code , there are no almoston float number code. But in improving the performance of GA and extending GA ’sapplication, float number code is superior to other codes. In this paper , the mechanism of niche GA is researched by it on float number code. Dynamic process is analyzed by it on niche forming and merging and separating in inherit operation. The is explored by it. The results of its research and experiment indicated that the of niche GA of code is relia 2ble. The method is feasible. K eyw ords 　Niche ,Float number code , G enetic algorithm 　

(如专门化、共栖共

生、互惠共生、Lotka 2Voltera 震荡、长期进化稳定性、竞争和协作的嵌套等现象) 。随着群体规模和小生境重叠的变化漂移, 某些小生境会瞬间消失, 而新的小生境又同时产生。从开始没有小生境到小生境重叠的不断增加, 产生了从协作到竞争的“相转换”。这是一个小生境产生、维持和收敛的往复过程。

在遗传算法中引入小生境, 目的是为了避免群体中的最优个体取代所有竞争个体的复制, 防止“早熟”, 提高其局部搜索能力。小生境导致了搜索空间的恢复压力, 平衡了选择的收敛压力[8]。小生境遗传算法中稳定状态的群体分布体现了问题解的分布表达式。这些问题的高质量的解(而非优化解) 存在于平衡分布中。小生境遗传算法在防止“早熟”、提高局部搜索性能和维持理想模式(即积木块) 等都有明显的优势。适应度共享为显性小生境, 常用于多峰函数优化[9]。

2. 1　浮点数适应度共享

浮点数适应度共享小生境的构造是通过降低目标适应度值来实现的。具体思想是:计算参数空间中某个体i 与任意其他个体j 的欧几里得距离, 判断两个个体是否在估计小生境半径σm 确定的圆内, 求出其共享值sh (d ) , 将个体i 所有sh (d ) 之和m i =Σsh (d ) 作为小生境数。共享值sh (d ) 的计算如下:

sh (d i , j ) =

1　引言

, 在遗传算法用固定规模群体中的一些子群体, 分别承担求解问题的一些子任务。与基本遗传算法不同的是:基本遗传算法的群体只存在竞争, 而小生境遗传算法群体中既有竞争, 也有子群体间的协作。

Cavicchio [1]最早提出了基于预选择机制(Preselection ) 的小生境实现方法。1975年,De Jong [2]提出了基于排挤机制(Crowding ) 的小生境实现方法。1987年, G oldberg [3,4]提出了基于共享机制(Sharing ) 的适应度共享小生境实现方法, 并在1990年用于玻耳兹曼(Boltzmann ) 锦标赛选择。20世纪90年代, Horn [5～7]对小生境遗传算法的有限Markov 链进行了分析, 提出了基于资源共享的小生境实现方法, 并对搜索、优化和机器学习中的小生境遗传算法进行了分析研究。这些研究, 都是基于二进制编码的遗传算法实现的。而浮点数编码在提高遗传算法的性能和遗传算法的推广应用中, 具有其它编码所无法比拟的优势。但迄今为止, 对浮点数编码的小生境遗传算法研究较少, 缺乏浮点数编码遗传算法的小生境性能分析和机理的研究。本文着重分析适应度共享的浮点数小生境遗传算法机制, 研究浮点数遗传算法在优化过程中小生境的生成、合并和分离机理, 探索其在优化领域的优势, 为遗传算法的基础和应用研究拓展更为广阔的空间。

1-

αni

2　浮点数小生境遗传算法的机理

小生境是较直接协作的更高水平, 展示了许多复杂的通

σni

0,

,

d i , j

(1)

otherwise

将该共享值加到两个小生境数m i 和m j 中。个体由σni

3)

本课题受到河南省自然科学基金(0411014500) 和河南省高校杰出科研人才创新工程项目(2004KYCX014) 的资助。崔明义　教授, 博士, 研究方向为计算智能、软件和网络安全。

・225・

分成小生境内外两部分。参数σni 和σni 依据适应度景观的先验知识或特别目标确定。在缺少先验知识的情况下, αni 可设为1。这时, 出现三角共享函数。图1表示了共享函数随αni 变化的势曲线族。随着一对个体的欧几里得距离从0到σni 变化, 共享值则从1到0呈单调减少。所以, 参数σni 直接影响着递减函数的形状, 即小生境的形态。对于个体i , 小生境数m i 可按下式计算:

m i =∑sh (d i , j )

j =1N

个个体, 都将其小生境作为小生境集合的元素, 则其质心集中在该个体上。在初始代和后来的几代中, 执行以下操作:

(1) 依据下式重新计算当前小生境集中每一个小生境的质心:

C j =C j +

∑(v i -C j ) 3f i

i =1

n j

∑f i

n j

(5)

(2)

这里, N 是群体规模。个体i 的共享适应度依据下式计算:

f sh , i =

m i

(3)

适应度共享分布在多峰的区域内, 且与峰的高度成正比。这就使在参数空间的不同小生境最优值附近形成较稳定的子群体, 并由此花费时间复杂度为O (n 2) 的计算代价, 且受限于αni 。

2. 2　浮点数编码不同小生境的形成

与自然小生境类似, 参数空间的不同小生境由相应的子群体构成。每个小生境由其质心和半径所确定。小生境的质心和半径在遗传过程中不断变化。这样, 小生境内部的个体数量和个体编码也在不断变化, 同一个个体可能属于一个或同时属于多个小生境的成员。

j

假定小生境j 的质心和半径分别是C j 和αni , 在该小生境内的个体i 的表现型值为v i , 则

j j

(4) C j -αv i ≤C j +αni ≤ni

j

式(4) 说明, 在多维空间中, 若某个体在由C j 和αni 的区域内, 其相关信息, 这里, C j 是小生境j 的质心, v i 是个体i 的表现型的值, f i 是个体i 的适应度, n j 是小生境j 的个体数。每个小生境的质心都将移动到小生境内最适合生存的个体的最高密度上。如果一个小生境没有成员, 则它将从当前小生境集中除去。

(2) 重新计算小生境成员。如果一个个体不是任何小生境的成员, 将生成一个以该个体为质心的一个新小生境。

(3) 当前小生境集中的每一个小生境与集合中的每一个其它小生境进行两次比较:

①第一次, 如果一个小生境的质心在另一个小生境质心的βni 内, 则两个小生境合并。

②第二次, 如果一个小生境的质心在另一个小生境质心的βni 之外, 且两个小生境的半径有重叠, 则两个小生境分离。合并和分离一直用于遗传过程中, 直到小生境集合不再发生变化而趋于稳定。

(4

) 重新计算小生境成员, 体共享函数. 3。共享函数m ni , i 如n j , i ∈j

(6) m ni , i =

0, otherwise

这里, n j 是小生境j 的成员数。小生境j 中的每个个体的共享适应度可按下式计算:

f ni , i =

m ni , i

(7)

2. 4　小生境合并

如果一个小生境j 的质心在另一个小生境i 的βni 内, 则将两个小生境合并成一个新的小生境。即

i i

(8) C i +βC j ≥C i -βni ≥ni 新的小生境质心从两个小生境的最初质心移动到两个小

生境中每个个体的平均加权距离上。最初质心依据下式计算:

(9) C na =C j +

2

这里, C i >C j 。两个小生境的权值和新小生境质心的定义如下:

w i =∑(v a -C na ) 3f a 　Πa ∈i

a =1n j n i

图1　适应度共享函数曲线

假设βni 为小生境的内径, 用于决定两个小生境是否合

并。由于σni 和βni 均是不断变化的, 因此有可能产生非均等的超量小生境。为了限制小生境半径的无限增大或减小, 把它

σσββσ们限定在一定的范围:σmin ≤ni ≤max 和βmin ≤ni ≤max 。max σ和βmax 可以预先给定, min 和βmin 取决于σni 的初始值, 而σni 取

决于群体规模和参数空间的大小。群体规模越大, σni 的初始值越小, 生成的小生境就越多。

使用固定的小生境半径或者在具有固定表现型空间的遗传算法中使用最小小生境半径, 所产生的小生境都是有限的, 这特别适合合并小生境的情况。在第一代, 对于群体中的每

w j =∑(v a -C na ) 3f b 　Πb ∈j

a =1

C new =C na +

a =1

∑f a +∑f b

b =1

n i n j

(10)

这里, n i 和n j 分别是小生境i 和j 的成员数, f a 和f b 分别是个体a 和b 的适应度, v a 和v b 分别是个体a 和b 的表现型值。新的小生境半径可通过新小生境质心与两个原小生境i 和j 的质心比较求得。考虑3种情况:

(1) 若C n ew

・226・

是到小生境i 或j 最左边界的距离, 而βni n ew 是由β

ni 与αni n ew 和αni 的1/2运算得到。

i

αni n ew =C n ew -(C i -σni )

i

σni -σni

=β+

2i ni

1000, 经过调整参数和合并, 第二代为50个小生境。经过80

βni n ew

(11)

否则

j

αni n ew =C n ew -(C j -σni )

j

σni -σni

β(12) ni n ew =β+

2

(2) 若C n ew >C na , 即新质心距小生境j 较近。这时, σni new

是到小生境i 或j 最右边界的距离, 而βni n ew 是由βni 与σni n ew 和

j

ni

i j

σ如果C i +σni 的1/2运算得到。ni >C j +σni , 则

i

σni n ew =(C i +σni ) -C new

代遗传运算, 小生境不断合并或分离, 最后形成5个小生境。

运行结果如图2、图3所示。在图2, 显示了函数有5个近似极大值点x 3={0. 098, 0. 309, 0. 496, 0. 703, 0. 887}, 其相应的最优解为f (x 3) ={0.9970, 0. 8566, 0. 7036, 0. 4519, 0. 2305}。这个结果接近于理论值, 证明这种方法是可靠的。在图2和图3中, 分别显示了第2代和80代各50个和5个小生境的个体数及相应半径的变化曲线

, 不难看出, 小生境的成员数总是随着小生境的半径变化, 且小生境的半径越大, 其成员数也越多, 这与生物小生境的生活习性越普通、环境越宽容, 则群体个数越多的特点相吻合。这说明, 本文阐述的浮点数小生境的生成、合并和分离机理是可行的。

βni n ew

i

σni -σni

=β+

2i ni

(13)

否则

j

σni n ew =(C j +σni ) -C new

j

σni -σni

β(14) ni n ew =β+

2

(3) 新质心与最初质心相等, 即C n ew =C na 。这时, σni n ew 是

β小生境i 和j 最远边界间距的1/2。ni new 是小生境i 或j 的

j

ni

βni 最大值与σni n ew 的1/2和小生境i 或j 的σni 最大值之和。

(C right +σni ) -(C lef t -σni )

σ(15) ni n ew =

2

在上述三种情况中, 如果σ类似地, ni n ew >σmax , 则σni new =σmax 。对于βni n ew >βn ew , 则βni n ew =βmax 。

βni n ew =βni largest αni -αni (16)

2. 5　如果小生境i 和j 的半径重叠, 则应将其分离而非合并。

i j i

C i -σni

即

(17)

每个小生境的σni 值将一定程度地减少, 以避免重叠。对最大平均适应度的小生境半径以比例减少。

i j

Crossover =(C i +σni ) -(C j -σni ) f i + f j

j j

σ(18) ni =σni -Crossover 3

f i + f j

这里, f i 和 f j 分别是小生境i 和j 中所有个体的平均适应度。两个小生境的βni 值减少小生境半径变化的1/2。

i i σni -σni i i β(19) ni =βni -2i i

这里, σni old 和σni n ew 分别是小生境i 的老小生境半径和新小生境半径。如果σni

i i

σni =σni -Crossover 3

3　实例

为检验上述浮点数小生境方法的可靠性, 本文取著名的遗传算法测试函数:

max f (x ) =e -2×ln 2×((x -0. 1) /0. 8) ×sin 6(5πx ) , x ∈[0, 1]

(20)

2

结束语　迄今为止, 在小生境遗传算法的研究中, 国内外文献大都是以二进制代码的遗传算法为对象进行研究,

对浮点数小生境遗传算法的研究较少, 也缺乏相应的研究成果。而浮点数编码在提高遗传算法的性能和遗传算法的推广应用中, 具有其它编码所无法比拟的优势。因此, 开展对浮点数编码遗传算法的运行机理包括小生境的研究, 对于遗传算法理

(下转第288页) 　　　

对上述方法进行了测试验证。随机取10组, 每组规模为

100的[0, 1]的随机数。建立小生境, 第一代小生境数为

・227・

尔函数所共享, 这些共享的结点可以节省布尔函数在计算机内部的存储空间。

x 5

3　简化B DD 大小的方法—变量顺序

尽管BDD 是表示布尔函数的有效方法, 但是, 表示一个布尔函数的BDD 的结构和大小依赖于变量的顺序。例如下图给出了布尔函数f 1=(x 1∧x 4) ∨(x 2∧x 5) ∨(x 3∧x 6) 的在两种变量顺序下的BDD

。

结点。它们以SBDD 的形式存储有21个结点, 确实是比原来两个布尔函数的总共的结点数(8+16=24) 减少了。

但是, 当布尔函数f 1的变量顺序为x 1

bddnodenum (f ,order ) 为布尔函数f 在变量顺序order 下的BDD 结点总数。

算法:

使用动态变量再排序, 求布尔函数f 1, f 2分别在各自变量顺序下的最小结点数

bddnodenum (f 1,order1) bddnodenum (f 2,order2) 使用动态变量再排序, 求以SBDD 的形式存储布尔函数f 1, f 2的最小结点数

bddnodenum (SBDD ,order3) 比较布尔函数f 1, f 2所形成的SBDD 的结点数和布尔函数f 1, f 2的总结点数

(

+(f 2) ) )

, f 2以SBDD 的形式存储在一个unique —table 表中

图1　变量顺序对BDD 大小的影响

(a ) 的变量顺序为x 1

数为16, (b ) 的变量顺序为x 1

总数却为8。从此例可以发现, 布尔函数在不同的变量顺序下生成的BDD 的结构和结点数有很大的差别。可以说, 变量排序也是一种有效的减小BDD 近年来, 人们对BDD 序, , 。第三类的结果最好。这种方法只适用于变量数较少的系统。动态变量排序是指对已建好的BDD 的变量次序进行调整以减少BDD 的规模, 该方法往往能找到一个更好的变量次序。目前许多的BDD 包都应用了动态变量排序方法[1]。

else

分别存储f 1, f 2

按以上提出的算法思想, 能够有效简化BDD 的大小。

参考文献

12

韩俊刚, 杜慧敏. 数字硬件的形式化验证. 北京:北京大学出版社,

2001

Bryant R 1Graph 2based Algorit hms for Boolean Functions Manip 2ulation. IEEE Transaction on Computers , 1996, C 235(8) :677～691

Andersen H R. An Introduction to Binary Decision Diagrams. Mat suura M , Sasao T , Butler J T , Iguchi Y. Bi 2Partition of Shared Binary Decision Diagrams

4　SB DD 与变量重排序相结合

分析下面两个布尔函数:

f 1=(x 1∧x 2) ∨(x 3∧x 4) ∨(x 5∧x 6) f 2=(x 1∧x 4) ∨(x 2∧x 5) ∨(x 3∧x 6)

当这两个布尔函数的变量顺序为x 1

论的发展和推广应用都是很有意义的。本文对此进行了探索, 取得了一些经验。随着这方面研究的不断深入和拓展, 其成果必将推动遗传算法在工程和优化领域的应用, 为遗传算法理论的发展和推广奠定更坚实的基础。

34

～49

45

G oldberg D E. A note on Boltzmann tournament selection for ge 2netic algorit hms and population 2oriented simulated annealing. Complex Systems ,1990,4:445～460

Horn J. Finite Markov chain analysis of genetic algorit hms wit h niching. In :Forrest S , ed. Proceedings of t he Fift h International Conference on Genetic Algorit hms. San Mateo , CA :Morgan Kauf mann , 1993. 110～117

Horn J , G oldberg D E , Deb K. Implicit niching in a learning clas 2si —er system :nature ’sway. Evolutionary Computation , 1994,2(1) :37～66

Horn J. Genetic algorit hms (wit h niching ) in search , optimiza 2tion , and machine learning. In :Whitley L D , Vose M D , eds. Foundations of Genetic Algorit hms , 1996,4

Horn J. Finite Markov chain analysis of genetic algorit hms wit h niching. In :Forrest S , ed. Proceedings of t he Fift h International Conference on Genetic Algorit hms. San Mateo , CA :Morgan Kauf mann ,1993. 110～117

Im Chang 2Hwan , K in Hong 2Kyu ,J ung Hyun 2Kyo . A Novel Al 2gorit hm for Multimodal Function Optimization Based on Evolution Strategy. IEEE Transactions on Magnetics ,2004,40(2) :1224～1227

6

参考文献

12

Cavicchio D J. Adaptive search using simulated evolution :[Ph D t hesis ]1University of Michigan , Ann Arbor , University Micro 2films , 1970125～0199

De Jong K A. An analysis of t he behavior of a class of genetic a 2daptive systems :[Ph D t hesis ].University of Michigan , Ann Ar 2bor. Dissertation Abstract s International , 5140B. University Mi 2crofilms , 1975,36(10) :76～9381

G oldberg D E , Richardson J. Genetic algorit hms wit h sharing for multimodal function optimization. In :Grefenstette J , ed. Pro 2ceedings of t he Second International Conference on Genetic Algo 2rit hms , Hillsdale , NJ :Lawrence Erlbaum Associates , 1987. 41

78

39

・2

88・