基于云理论的进化计算模型

论文标题：基于云模型的进化算法 论文作者：

张光卫: 何锐: 刘禹

北京航空航天大学计算机学院，北京，100083 北京航空航天大学计算机学院，北京，100083 北京航空航天大学计算机学院，北京，100083 中国电子工程系统研究所，北京，100040 中国电子工程系统研究所，北京，100040

李德毅: 陈桂生

中文摘要：

基于云模型在非规范知识的定性、定量表示,及其相互转换过程中的优良特征,结合进化计算的基本思想,提出一种基于云模型的进化算法.该算法利用云模型对物种的遗传变异进化统一建模，能够自适应控制遗传变异的程度和搜索空间的范围,从而可以快速收敛到最优解.较好地避免了传统遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.仿真结果表明该算法具有精度高、收敛速度快等优点.云模型和进化计算思想的有效结合一方面拓宽了云模型的应用领域,也为进化计算的研究进行了新的探索和尝试.

关键字：

云模型; 进化计算, 数值优化, 遗传算法, 数值优化, 人工智能

- 1 -

基于云模型的进化算法*

张光卫,何锐,刘禹,李德毅,陈桂生

( 1北京航空航天大学计算机学院 北京100083 2 中国电子工程系统研究所 北京 100840）

1

1

1

2

2

摘 要：

基于云模型在非规范知识的定性、定量表示,及其相互转换过程中的优良特征,结合进化计算的基本思想,提出一种基于云模型的进化算法.该算法利用云模型对物种的遗传变异进化统一建模，能够自适应控制遗传变异的程度和搜索空间的范围,从而可以快速收敛到最优解.较好地避免了传统遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.仿真结果表明该算法具有精度高、收敛速度快等优点.云模型和进化计算思想的有效结合一方面拓宽了云模型的应用领域,也为进化计算的研究进行了新的探索和尝试. 关键词：云模型;进化计算;遗传算法;数值优化,人工智能

引言

遗传算法(GA)[1~6]是智能计算的重要分支.问题解按照一定编码方案被表示成遗传空间的串结构个体,用适应度函数进行评价以选择出优秀个体,通过交换和变异操作产生新一代更适应环境的种群.系统初始化为一组随机解,经过逐代演化,收敛到一个最适应环境的串上,求得问题的最优解.

[7～10]

云模型是李德毅院士提出的一种定性知识描述和定性概念与其定量数值表示之间的不确定性转换模型,已经在智能控制、模糊评测等多个领域得到应用.正态云模型是最重要的一种云模型,由于其具有良好的数学性

[8]

质,可以表示自然科学、社会科学中大量的不确定现象.

云模型在知识表达时具有不确定中带有确定性、稳定之中又有变化的特点,体现了自然界物种进化的基本原理.对于云模型 C(Ex,En,He),Ex可以代表父代个体遗传的优良特征,是子代对父代的继承, En和He可以表示继承过程的不确定性和模糊性,表现了物种进化过程中的变异特征. 用正向云算子可以完成概念空间到数值空间的转换,在三个参数的控制下产生子代种群,完成遗传操作.一方面这种转换是确定的和精确的,因为数值空间的每一个云滴都是定性概念的一次量化实现,都在一定程度上是该定性概念的代表;另一方面,这种转换又是随机的和模糊的,每一次变换得到不同的云滴集合,而且同一定性概念可用云滴集合中的任何一个代表,不同的云滴代表该概念的确定程度不同.

基于云模型的优良特性,结合进化计算的基本原理本文提出一种基于云模型的进化算法,该算法不但比传统遗传算法精度高,而且能够很好地避免遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.

本文组织如下:首先对云模型进行简单介绍;然后重点给出了CBEA的思想和详细算法流程;仿真实验部分对本文提出的算法进行测试和对比分析;最后总结全文并给出下一步的研究方向.

1云模型简介

定义1.1云和云滴 设U是一个用数值表示的定量论域,C是U上的定性概念,若定量值x?U是定性概念C

x??(x),则x在论的一次随机实现,x对C的确定度?(x)?[0,1]是有稳定倾向的随机数:?:U?[0,1] ?x?U[7]

域U上的分布称为云(Cloud),记为云C(X).每一个x称为一个云滴. 如果概念对应的论域是n维空间,那么可以拓广至n维云. 云模型所表达概念的整体特性可以用云的数字特征来反映,云用期望Ex（Expected value）,熵En(Entropy),超熵He(Hyper entropy)这3个数字特征来整体表征一个概念,多维云模型的整体特征可由多组数字特征表示.期望Ex是云滴在论域空间分布的期望,是最能够代表定性概念的点,或者说是这个概念量化的最典型样本;熵En代表定性概念的可度量粒度, 熵越大通常概念越宏观,也是定性概念不确定性的度量,由概念的随机性和模糊性共同决定.一方面En是定性概念随机性的度量,反映了能够代表这个定性概念的云滴的离散程度;另一方面又是定 *

国家自然科学基金(60496323，60375016)，现代设计大型应用软件的共性基础973计划(2004CB719401)

作者简介:张光卫(1970-),男,山东济南人,博士生，研究方向为人工智能,电话:13601166529,E-mail:ezhang@263.net;李德毅(1944－),男,江苏泰县人,博士生导师,中国工程院院士,主要研究领域为人工智能,指挥自动化.

- 1 -

性概念亦此亦彼性的度量,反映了在论域空间可被概念接受的云滴的取值范围;超熵He(Hyper entropy)是熵的不确定性度量,即熵的熵,由熵的随机性和模糊性共同决定.用三个数字特征表示的定性概念的整体特征记做C(Ex,En,He).

定义1.2 一维正态云算子ArForward(C(Ex,En,He))是一个把定性概念的整体特征变换为定量表示的映射?:C??,满足以下条件:

(1)??{ti|Norm(En,He)的一次实现 i=1..N}

(2)X?{xi|xi为Norm(Ex,ti)的一次实现ti??,i=1..N}

22(3)?={(xi,yi)|xi?X,ti??,yi=e-(xi-Ex)/(2ti)}

其中Norm(?,?)为期望为?方差为?的正态随机变量,N为云滴的个数

利用正态云算子,就可以把定性概念C(Ex,En,He)变换为数值表示的云滴集合,实现了概念空间到数值空间的转换. 一维正态云算子可以拓广至n维正态云算子.

2 基于云模型的进化算法(CBEA)

通过正向云算子根据三个数字特征产生云滴的过程能够刻画遗传和变异的思想,以一维正态云模型C(0, En,He)为例,它表达的概念为“坐标轴原点附近”,以不同的熵和超熵可以把这个定性概念转化为定量表示,如图分别做出通过正向云算子得到的500个云滴的图形.图形上的每个云滴可以理解为以0（期望）为种子个体,以不同的熵和超熵得到的后代个体,云滴形成的每个云相当于一个种群,可以看到四个种群的在覆盖范围和离散程度的明显差异,即熵越大个体的覆盖范围越大,超熵越大种群中的个体越离散.

C(0, 0.5, 0.1)10.80.60.40.20-210.80.60.40.20-2-1012-10C(0, 0.5, 0.2)10.80.60.40.20-4-20241210.80.60.40.20-4-20C(0, 1, 0.2)24C(0, 1, 0.1)

图1 用云表达概念“坐标轴原点附近”

可见期望体现了遗传的稳定性,熵体现了变异的范围,可以表示搜索的广度,超熵体现了进化的稳定程度,可以表示求精的粒度.根据人类搜索的经验,“当前优秀个体周围往往存在更加优秀的个体”,制定下面的搜索过程：首先,求出优秀个体,对一个进化代所有的个体（云滴）根据被优化的函数进行适应度计算 (fitness value),根据适应度选择得到前m个最适应的优秀个体,称为优秀个体向量；其次,以优秀个体为母体繁殖下一代个体,即分别以m个个体为种子产生一定数量的云滴作为下一代个体,给定规则使得越优秀的种子产生的下一代个体数量越多,这样得到新一代的个体中存在更加优秀的个体的可能性较大,反复叠代便可逐步寻优；另外,根据历史进化代的情况可以对下一个进化代熵和超熵的值进行自适应控制（放大或缩小）,以控制搜索的范围和求精的粒度,这个控制过程一方面要防止算法陷入局部最优和早熟收敛,另一方面还要满足在可能存在最优解的范围内迅速求精,当然这两个方面是矛盾的,需要制定合适的控制策略.

在这个过程中,遗传和变异是统一在一起的,都融合在新个体的产生过程中,因为由正向云算子产生的子代个体（云滴）都会聚集在母体（云期望）周围,充分体现了“龙生龙,凤生凤”的遗传特征,同时这也是一个充满不确定性的过程,是随机的和模糊的,每一次变换得到不同的云滴集合,体现了“一母生九子九子各不同”的变异

- 2 -

特征.当算法在若干进化代都不能产生新的优于历史个体的最优个体时,就要考虑突变操作,生物学认突变是能够影响生物遗传性状的变异,但它并不经常发生,本算法中最深度的突变操作是系统重新进行初始化.

以此上面的思想为基础本文提出一种新颖的演化算法-CBEA（Cloud Based Eevolutionary Algorithm）.类似大多数演化计算技术遵循的过程,CBEA的计算过程为：

1.系统初始化为一组随机解,即随机初始化群落中个体的值.

2.计算所有个体的适应度,并选择出适应度最好的前m个最优秀个体,形成优秀个体向量. 3.前m个个体分别繁殖一个种群.

4.如果达到演化代数则算法停止,最优秀的个体即为最优解,否则转步骤2.

[13,14]

CBEA与粒子群算法(Particle Swarm Optimization,PSO)和遗传算法有很多共同之处,都是基于叠代的优化过程,都随机初始化种群,而且都使用适应值来评价系统,进而根据适应值来进行一定的随机搜索,它们都不能保证一定能找到最优解.

CBEA与遗传算法的不同之处在于,虽然也是通过叠代搜寻最优值,但没有遗传算法的二进制编码工作,也没有相应的交叉(crossover)、变异(mutation)等操作,而是通过正向云算子完成新一代种群的产生,通过熵、超熵控制产生子代种群的位置、范围（搜索的范围）以及子代种群集聚程度（求精的粒度）,算法的实现也较遗传算法简单.

CBEA和PSO都采用实数编码,都没有相应的交叉、变异操作,PSO根据粒子的速度来决定搜索,粒子们追随当前的最优粒子在当前解空间中搜索,而CBEA在各个进化代是个体不断产生和被淘汰的过程,既体现了进化论的思想,也体现了人类搜索的特点.

假设参加叠代寻优的个体总数为n,称为一个群落C,群落中的个体被分成m个种群,m也称为群落的丰富度.群落和种群的关系为C??Pi,其中Pi 表示第i个种群,各个种群包括的个体的数目可以不同,个体被编码为一个k

i?1k元组,xij表示第i个种群的第j个个体的第k个分量,由于个体能且只能属于一个种群,所以n=j1+j2+…+jm ,种群是

m个体的集合,表示为：

12k12k12kP1 ? { (x11,x11,...,x11) ,(x12,x12,...,x12) ,...,(x1j1,x1j1,...,x1j1) }

P2 ? { (x121,x221,...,xk21) ,(x122,x222,...,xk22) ,...,(x12j2,x22j2,...,xk2j2) }

…

Pm ? { (x1m1,x2m1,...,xkm1) ,(x1m2,x2m2,...,xkm2) ,...,(x1mjm,x2mjm,...,xkmjm) }

按照群落中种群的规模对种群的地位进行划分,分为建群种、优势种和劣势种,其中优势种是拥有较多个体的种群,建群种为优势种中的最优者.一个群落中建群种只有一个,是群落中的最具代表性的种群,优势种和劣势种则可以有多个,其中劣势种规模最小但个数最多.根据当前最优个体周围存在更加最优个体的概率较大的原则,越优秀的个体将产生更多的子代个体.在每一个进化代,挑选适应度最好的前m个最优个体,m为群落中种群的个数,淘汰群落中所有其余个体,以m个最优个体为母体产生m个种群,构成新一代群落,最优秀的个体产生建群种,依此类推使得越优秀的个体产生的种群规模越大.

比如假设群落C的个体总数n=1000,种群数m=10, 种群大小依次为[300,200,150,50,50,50,50,50,50,50],在每个进化代的优秀个体向量大小为10,算法在每一个进化代根据个体的适应度挑选出10个优秀个体,下一代的种群由这10个优秀个体产生,其中最优秀的个体将作为母体产生建群种,其它次优秀的个体将依次产生优势种和劣势种群,则种群结构与优秀个体的关系如图2所示.

基于云模型的进化算法不像遗传算法那样注重父代与子代的遗传细节(通过基因表达遗传操作)上的联系,而是通过云模型把进化和遗传作为一种定性知识进行描述,进而通过不确定的定性定量转换,把定性知识转化成

- 3 -

图2 种群结构与优秀个体的关系

若干定量实现(子代个体).在每一个进化代,一方面通过对子代个体的适应性评估得到优秀个体,另一方面根据历史进化情况确定下一步进化的范围,从而形成新的知识,为下一步进化做好了准备.为了便于表述算法思想首先定义以下基本概念.

定义2.1 进化模型(Evolving Pattern) EP(Ex,En,He)是用云模型表达的进化模型.其中Ex称为种子个体,表达祖先遗传的优良特性； En称为进化熵,代表变异的大概范围； He称为进化超熵表示进化的稳定性,He越大则不确定性越强.进化模型包括一维模型和多维模型,多维模型用EP(Ex1,En1,He1,…, Exn,Enn,Hen)表示,其中维数n为大于等于1的整数.给定父代个体(Ex)作为母体, 指定熵和超熵(En,He),利用正向云算子便可以产生任意数量的云滴,所有云滴均是该母体的后代个体,形成一个种群,因而进化模型可以看成是种群的产生模型. 定义 2.2 进化 (Evolvement) 是指以父代种群中适应度较好的优秀个体为母体,按照进化模型产生新种群的操作.进化操作包含有一定的变异成分,因为个体即继承了母体的优良特征,又与母体有一定程度的不同,由于这种变异为稳中求变,故称为进化式变异.进化式变异的变化程度主要受进化模型的参数En控制, 其变化程度可能较小(En较小时),也可能较大(En较大时).

定义 2.3 突变（Mutation）是指进化过程中全部或部分抛弃父代种群的优秀个体,并按照一定策略生成新的个体作为母体产生新种群的操作.经过突变产生的群落相对与父代群落差异较大.

定义 2.4 进化代(Evolving Generation)进化过程中新群落的一次产生称为一个进化代.

定义 2.5 适应度(Fitness) 群落中各个个体对环境的适应程度,是衡量个体优劣的程度,根据适应度的大小,决定某个个体是被保留还是被淘汰.适应度通常是费用、盈利、方差等目标的表达式, 适应度函数的构造可以参考遗传算法中适应度评估函数的构造方法.

定义2.6 精英个体(Elite Individual)指进化过程中得到的适应能力最强的个体,分为当代精英和跨代精英,当代精英指一个进化代的所有个体中适应性最强的个体,跨代精英指多个进化代中适应性最强的个体,进化过程(算法)的最终结果即为所有进化代中的最优跨代精英个体.出现跨代精英的进化代称为非平凡进化代,没有出现跨代精英的进化代称为平凡进化代,两个跨代精英个体之间相隔的进化代数称为连续平凡代数,是连续没有出现跨代精英个体的进化代数.连续出现跨代精英的进化代数称为连续非平凡代数.

连续平凡代数和连续非平凡代数是进化过程中进行自适应调节的重要数据.较大的连续平凡代数说明目前搜索的邻域中难以发现更加优秀的个体,那么此时算法可以自适应地采取突变操作.连续非平凡代的出现则表明当前进化代是有效的,算法可以自适应地控制进化过程中的变异程度（求精操作）.

定义2.7 进化策略(Evolving Strategy)指进化过程中进化操作的控制策略,亦即通过调整进化模型的参数En和He来优化子代种群产生的策略.通过制定进化策略可以解决两方面问题:(1) 局部求精,当出现了跨代精英个体时,算法可能找到了新的极值邻域,或更加逼近了老的极值邻域,此时需要求精操作,方法是降低进化范围(减小En)和增加稳定性(减小He),从而加大搜索的精度和稳定度以达到快速局部求精的目的,比如可以简单地把En和He减小为原来的1/K,其中K为大于1的实数,称为进化系数.（2）局部求变(进化式变异),当若干进化代没

- 4 -

有发现新的跨代精英,即连续平凡代数达到一定的阈值?local时,算法可能陷入了一个局部最优邻域,此时需要跳出这个小局部,并在该局部附近尝试寻找新的局部最优.方法是提高En和He, 比如简单地提高为原来的L倍,L称为进化式变异系数,L?K,可取L??K?.当函数的局部最优值非常邻近时,进化式变异可以在众多邻近局部

??最优值中寻找全局最优.

定义2.8 变异策略(Mutation Strategy)指进化过程中对突变操作的控制策略,是算法摆脱局部的保证.当经过若干代进化没有得到适应性更加优异的个体,而且进化式变异没有效果时,算法有可能陷入局部, 需要进行一次突变操作.进行局部求变和突变的连续平凡代数阈值之间的关系为?global??local.突变方法有两种,一种是取历史跨代精英个体的平均值,另一种是取历史当代精英个体的平均值,熵可取为相应历史精英个体的方差.

在CBEA中进化和变异是统一的,进化式变异是进化和变异融合,可以用来进行局部求精或跳出小局部,而突变则用来在全局范围内寻找新的极值搜索区域.算法可以判断出当前的进化状况,进而可以自适应地进行调整.

相比传统遗传算法,当种群中多数个体的适应值相差不大时交叉操作就显得无能为力, 此时算法容易陷入局部解而不能通过交换解决,突然变异能够使之摆脱局部收敛而跃出局部解,但后期的变异可能破坏已产生的对形成最优解有建设性作用的模块.CBEA可以有效避免遗传算法的这个缺点, 因为进化式变异和突变均利用了历史搜索结果.进化算法的详细结构如图3所示.

图3进化算法结构图

3仿真实验及分析

为了验证算法的有效性,我们选用如下经典非约束类测试函数进行对比实验. f1?0.5?22sin2x1?x2?0.5222[1?0.001(x1?x2)],?100?xi?100,i?{1,2}, 即Schaffer函数,其在(0,0)处取得全局最小值0.

- 5 -

?214?222f2??4?2.1x1?x1?x1?x1x2?(?4?4x2)x2,?3?x1?3,?2?x2?2,也称Six-Hump Camel Back函数,有两个全局最

3??小值-1.03162845348988.

f3?{?icos[(i?1)x1?i]}?{?icos[(i?1)x2?i]},?10?xj?10,j?{1,2},也称Shubert 函数,有18个全局最小值

i?1i?155-186.7309088310239.

f4??cos(x1)cos(x2).exp(?(x1??)2?(x2??)2),?100?xi?100,x?{1,2},也称Eazom函数,在(x1,x2)?(?,?)时取得全

局最小值-1.

f5??i?1xi2,?100?xi?100,i?1,2,...,n,n?10,即Sphere函数, 在(0,0,...,0)处取得全局最小值0.

f6?20?e?20e?115nn?i?1xi2n?e?1n?n?1cos(2?xi)n,?32.768?xi?32.768,i?1,2,...,n,n?10,即Ackley函数, 在(0,0,...,0)处有全

局最小值0. f7?xin1n2即Griewank函数,在(0,0,...,0)处有全局最小值x?cos()?1,?600?xi?600,i?1,2,...,n,n?10，??ii?14000i?1in0.

f8?10n??[xi2?10cos(2?xi)],?5.12?xi?5.12,i?1,2,...,n,n?10,即Rastrigin函数, 在(0,0,...,0)处有全局最小值0.

i?1实验1 CBEA算法搜索过程和执行效率分析

以函数f1为例,实验的初始值设置：群落规模500,群落丰富度10,群落中种群的规模为[150,100,75,25 ,25, 25, 25,25 25,25],适应度函数取为目标函数fitness= f1,进化代数20,阈值?local?2,?global?10 ,进化系数K=10, 进化

式变异系数L??K?,进化模式初始取值为: EP(Ex1,En1,He1,Ex2,En2,He2) =(40, 100, 0.01, 20,100, 0.01)

??以一次随机运行为例分析结果的收敛情况,最优点 f1(8.814651527942963e-005, 1.489411529440795e-004)=

2.998322828906552e-008,分别做出x1,x2和函数值的收敛曲线,横坐标为代数,纵坐标为函数值或x1,x2的值,如图4所示.分析如下:(1)算法共运行20代,在第15代找到了全局最优点.(2)算法在第1,2,3,11进化代4次寻找到新的变化较大的局部极值点邻域,经过求精后迅速从第1,2个逃出,在第3个局部极值点邻域连续求精8个进化代,其中找到5个跨代精英.由于阈值?local?2,所以当算法在连续两代没有发现跨代精英的时候,就要进行变异, 第11代进行变异,并立即找到了新的跨代精英,表明了算法具有良好的变异特性,使得算法能快速跳出局部极值邻域并进入新的求精阶段.(3)第18,19,20代为连续变异,没有找到跨代精英,算法结束. (4)观察连续非平凡代数,大量实验表明连续非平凡代数一般不超过5,表明算法有很好的局部求精能力.

以上分析表明算法不但能够快速定位全局极值点所在邻域,而且具有高效的局部求精能力,能够较好地避免遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.

- 6 -

精英个体函数值收敛曲线0.060.040.020100-1050-502468101214跨代精英个体当代精英个体变异个体161820精英个体x1分量收敛曲线02468101214161820精英个体x2分量收敛曲线02468101214161820

图4 进化过程中各项指标的收敛曲线

为了更好地了解算法的执行情况,下面对x1和x2的搜索空间的演变进行分析.x1的变化情况如图5所示,图中给出了第1,3,5,14进化代x1的搜索空间,算法在第3代,建群种已经接近了最优解邻域,第5代的时候群落中除了有两个种群外其余的种群都回归到最优解附近,数据表明在第5进化代x1已经很逼近最优值了.

x1搜索空间 第1代100806040200-20-40-60-80-100050100150200250300350400450500543210-1-2-3-4-5050100150200250300350400450500x1搜索空间 第3代

x1搜索空间 第5代0.250.20.150.10.020.0500-0.05-0.1-0.15-0.020.08x1搜索空间 第14代0.060.04-0.04050100150200250300350400450500-0.06050100150200250300350400450500

图5 x1的搜索空间变化情况

x2的搜索空间的变化情况如图6所示,图中给出了第1,6,12,15进化代x2的搜索空间,直到第6代时x2仍局限在局部最优邻域-3.14附近,在第11代出现变异,第12代的时候其建群种开始接近了最优解邻域,基本确定了下一步演化的方向,第15代时群落中所有10个种群都回归到最优解附近,正是在15代算法取得了最优解(见图4).

- 7 -

x2搜索空间 第1代10080-3.066040200-20-40-60-3.16-80-100050100150200250300350400450500-3.18050100150-3.12-3.08-3.04x2搜索空间 第6代-3.1-3.14200250300350400450500

x2搜索空间 第12代20.06x2搜索空间 第15代

1.50.0410.020.500-0.02-0.5-0.04-1-0.06-1.5050100150200250300350400450500-0.08050100150200250300350400450500

图6 x2的搜索空间变化情况

为了考查CBEA的执行时间和计算精度, 针对函数f1, 算法根据不同的总代数各运行100次, 由于运算结果呈非对称偏态分布,不适合用平均值作为测度,因而做出每次运行结果的频度统计如表1所示. 算法的配置为群落大小为500, ?local?2,?global?10,K=10, L??K?.CBEA的执行时间受运行的总代数,适应度函数的复杂度以

??及群落大小的影响,对于函数f1每次运行的平均时间如表所示.实验机器为赛扬笔记本1.5G主频,512M内存,仿真软

件为Matlab7.1.

表1 结果频度统计表

运行 次数 运行代数 (代/次) 0 (精确解) 100 100 100 100 100 30 50 80 100 150 40 95 95 97 99 [1e-17, 1e-13] 45 2 3 3 1 运行结果频度统计(次) [1e-12, 1e-10] 7 2 2 0 0 [1e-09, 1e-06] 5 1 0 0 0 [1e-05, 1e-04] 0 0 0 0 0 1e-03 (失败) 3 0 0 0 0 0.02266 0.04125 0.06297 0.07781 0.11562 平均时间 (秒/次) 在上面的初始配置下,对于函数f1当运行总代数大于50时,成功率基本达到100%,且平均精度优于10-10数量级.当运行总代数大于50时,算法得到精确解的比率大于90%.如果提高群落的大小,那么能够进一步提高成功率.当算法运行的总代数小于100时算法能够在0.1秒内完成寻优,算法的执行效率还是相当高的. 实验2 CBEA收敛性实验

为了说明CBEA的收敛性,利用所选取的所有测试函数对算法的演化情况进行了跟踪并绘制各自的演化曲线. CBEA对每个函数都计算50次,每次演化100代;各个函数的演化曲线在某一代的值是50次实验中算法演化到该代时所有搜索到的最优解的平均值. 实验中,CBEA的群落大小均取1000,群落丰富度10,群落中种群的规模为

- 8 -

[300,200,150,50,50,50,50,50,50,50].

算法对所有函数演化曲线如图7所示(由于各个搜索范围和精确解位置不尽不同,故未将所有收敛曲线画在同一坐标系中).

图7. CBEA计算函数f1~f8的收敛曲线

由图7可知,无论测试函数是2维还是10维,CBEA都能够很快的收敛到最优解的水平,除了f3之外,其他函数都能够在前10代逼近最优解,而f3也能够在25代左右逼近其最优解.事实上,实验数据表明所有函数都能够在30代左右到达或非常接近最优解.不过由于显示粒度的原因不能在图中完全表现出来. 实验3 全局搜索能力对比分析

为了说明CBEA的全局搜索能力,分别与遗传算法和PSO算法进行了比较。前者是基于函数f1~f4，后者是基于f5~f8.

遗传算法方面，选取了传统GA[1]( 采用浮点编码、非一致变异算子和算术交叉算子)和直接用局部快速微调遗传算法(FLAGA)[12]和CBEA进行比较。CBEA的参数设置同实验2.实验结果的对比情况如表2所示,其中GA与FLAGA的数据来自文献[12].

表2 与遗传算法比较

函数 GA T GA 平均值 GA 成功 次数 F1 F2 300 300 0. 0819251 999945 -1.03 131 046 699 639 50 200 -1.03 162 845 348 226 50 100 -1.03 162 845 348 986 50 15 300 7.396492233593399e-6 FLAGA T FLAGA 平均值 FLAGA 成功 次数 50 100 2.220446049250313e-18 CBEA T CBEA 平均值 CBEA 成功 次数 50 - 9 -

F3 F4 200 300 -186.366 281 815 724 -0.60 547 253 510 119 48 34 300 300 -186.7 309 088 006 962 -0.99 999 999 999 999 50 50 100 100 -186.7 309 088 310 227 -1.0 50 50 从表2可以看出, CBEA在所有测试函数中都表现得更好.它用比其他算法更少的进化代数取得了更好好的函数平均值,并且50次的成功次数（即全部成功）也说明算法具有良好的稳定性. 此外,实验中CBEA的达到精确解的比例相当高,由于篇幅限制没有列出解的频度统计表.

PSO算法方面,选取了经典的PSO算法[15]和J.J.Liang等新近提出的PSO改进算法CLPSO[16]作为比较对

象.CBEA的参数设置同实验2.为了便于比较,使用了与文献[16]相同的统计参数,PSO和CLPSO的数据也来自文献[16].实验结果对比如表3所示.

表3 与PSO算法比较

函数 平均值 F5 F6 F7 F8 7.96e-51 1.58e-14 9.69e-02 5.82e+00 PSO 标准方差 3.56e-50 1.6e-14 5.01e-02 2.96e+00 平均值 5.15e-29 4.32e-14 4.56e-03 0 CLPSO 标准方差 2.16e-28 2.55e-14 4.81e-03 0 平均值 0 0 0 0 CBEA 标准方差 0 0 0 0 由表3可知,对函数f5~f8,CBEA在准确性和稳定性都具有较为显著的优势.事实上对于这四个测试函数, CBEA每次都能够找到精确最优解,因此其平均解即为精确最优解且所有解的标准方差为0;而PSO对这些函数都不能找到最优解,CLPSO也仅在测试函数f8上具有相同的精确性和稳定性. 4 结论与展望

基于云模型在定性概念与其定量数值表示之间转换过程中的优良特性,结合进化计算的基本思想,本文提出一种基于云模型的进化算法(CBEA).该算法能够自适应控制遗传、变异的程度和搜索空间的范围,从而可以快速使算法收敛到最优,较好地避免了遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.

CBEA不像遗传算法那样注重父代与子代的遗传细节(通过基因表达遗传操作)上的联系,而是通过云模型把进化和遗传作为一种定性知识进行描述,进而通过不确定的定性定量转换,把定性知识转化成若干定量实现(子代个体).在每一个进化代,通过对个体的适应性评估得到优秀个体,作为下一代进化母体.

云模型和进化计算思想的成功结合拓宽了云模型的应用领域,也为进化计算的研究进行了新的探索和尝试. 本文的研究工作仅是这一交叉研究领域的开始,如何拓宽算法在优化问题中的应用范围和对算法迭代过程的理论分析均是有意义的下一步研究方向.

参考文献：

[1]王正志, 薄涛. 进化计算. 长沙:国防科技大学出版社,2000.

Wang Zhengzhi, Bo Tao. Evolutionary computing. Changsha Changshao: National Univeristy of Defence Technology Press,2000. [2] Holland , J H. Adoption in natural and artificial system. Ann Arbor : The University of Michigan Press ,1975. [3] Goldberg , D. E. Genetic algorithm in search, optimization and machine learning. MA: Addison Wesley, 1985. [4] Davis, L. Handbook of genetic algorithms. New York: Van Nostrand Reinhold, 1991

[5] Heirkotter, J and Beasley, D. The hitch-hiker's guide to evolutionary computation. FAQ in Comp Ai Genetic, 1995 [6] Schwelfel, H.P. Numerical optimization of computer models. Chichester: Wiley, 1981.

[7] 李德毅, 杜鹢. 不确定性人工智能. 北京: 国防工业出版社, 2005.

Li Deyi, Du Yi. Artificial intelligence with uncertainty. Beijing: National Defense Industry Press, 2005.

[8] 李德毅, 刘常昱. 论正态云模型的普适性.中国工程科学, 2004, 6(8):28-33

Li Deyi, Liu Changyu. Study on the universality of the normal cloud model. Engineer and Science of China, 2004, 6(8): 28-33

- 10 -

[9] 李德毅, 刘常昱, 杜鹢, 韩旭. 不确定性人工智能.软件学报, 2004, 15(9): 1583-592

Li Deyi, Liu Changyu, Du Yi, Han Xu. Artificial intelligence with uncertainty. Journal of Software, , 2004, 15(9): 1583-592 [10] 李德毅. 知识表示中的不确定性. 中国工程科学, 2000, 2(10) : 73-79.

Li Deyi. Uncertainty in Knowledge Representation. Engineer and Science of China, 2000, 2(108): 73-79 [12] 刘习春,喻寿益. 局部快速微调遗传算法. 计算机学报, 2006, 29(1): 100-105

Liu Xichun, Yu Shouyi. A Genetic Algorithm with Fast Local Adjustment. Chinese Journal of Computers, 2006, 29(1): 100-105 Science1 Piscataway , Nagoya, Japan,1995. New Jersey: IEEE service center, 1995:39-43

[14] Kennedy, J. and Eberhart , R. Particle swarm optimization The IEEE International Conference on Neural Networks , Perth ,

Australia , 1995. New Jersey: IEEE service center, 1995: 1942-1948

[15] Shi Y. and Eberhart R.C. A modified particle swarm optimizer. The IEEE International Conference on Evolutionary Computation. New

Jersey: IEEE Press, 1998: 69-73

[16] Liang J.J.and Qin A.K. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE

Transaction on Evolutionary Computing, 2006, 10( 3): 281-295

[13] Eberhart, R. and Kennedy, J. A new optimizer using particle swarm theory. The 6th Int'l Symposium on Micro Machine and Human

- 11 -

An Evolutionary Algorithm Based On Cloud Model

Guangwei Zhang1,Rui He1, Yu Liu1, Deyi Li2, Guisheng Chen2

(1. School of Computer Science and Engineering, Beihang University, Beijing 100083, China 2. China Electronic System Engineering Company, Beijing 100840, China)

Abstract:

Based on the outstanding characteristics of the cloud model on the process of transforming a qualitative concept to a set of quantitative numerical values, and integrating with the basic principle of evolutionary computation, we propose a novel rapid evolutionary algorithm, namely Cloud Model Based Evolutionary Algorithm or CBEA for short. With the cloud model, inheritance and mutation of species can be modeled naturally and uniformly, which make it easy and nature to control the scale of mutation and inheritance, and the scope of searching space. This enables CBEA to be able to find accurate numerical solutions within a short time. Numerical optimization experiments are carried out to verify the algorithm. With some of the typical test functions, the performance of CBEA is studies and also be compared with other algorithms. The results prove the high quality of the algorithm on precision, stability and convergence rate. In addition, the successful integrating of the cloud model and evolution principle expands the research fields of Cloud Theory and also indicates a new way for the research of evolutionary computation.

Key words: Cloud Model; Evolutionary Computation, Genetic Algorithm; Numerical Optimization, Artificial

Intelligence

研究背景:

在自然选择和生物进化理论基础上发展起来的进化计算,在全局最优化问题的研究中显示了强有力的优势,以其鲁棒性、可并行处理性及高效率得到广泛的应用.但传统的进化算法存在易陷入局部最优解和选择压力过大造成的早熟收敛等问题.

李德毅院士提出的云模型,在表达知识时,具有不确定中带有确定性、稳定之中又有变化的特点,体现了自然界物种进化的基本原理.

本文结合进化计算的基本思想和云模型,利用在云模型定性概念与其定量数值表示之间转换过程中的优良特征,提出一种进化算法,该算法能够自适应控制遗传、变异的程度和搜索空间的范围,从而可以快速收敛到最优解.较好地避免了传统遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题.尤其是算法具有很好的求精能力和执行效率.

- 12 -

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