利用子群体迁徙的思维进化算法设计❋

王 芳,刘 军,谢克明

(1.太原理工大学信息工程学院,山西太原 030024;2.山西省质量技术监督局,山西太原 030002)

思维进化算法(Mind Evolutionary Algorithm,MEA)[1]是模拟人类思维进化过程的一种进化算法,它是根据对遗传算法(Genetic Algorithm,GA)存在问题的思考以及对人类思维进步的分析,将群体划分为若干子群体,提出了“趋同”和“异化”算子.进化操作“趋同”起开采的作用,“异化”起勘探的作用,这两个操作都隐含有选择操作.二者的作用并非对立,而是协调工作的,大大提高了搜索效率,并已取得了许多成功应用[2-4].改进趋同和异化操作对整个算法性能的改善都有贡献.群体智能(SwarmIntelligence,SI)是近年来发展迅速的人工智能学科.通过研究分散、自组织的动物群体和人类社会的智能行为,学者们提出了许多迥异于传统思路的智能算法,很好地解决了不少原来非常棘手的复杂工程问题[5-6].

本文将群体智能引入 MEA中,充分利用生物群体中信息交互、相互协作的思想以加快收敛速度,同时采取信息浓度更新规则限制过度学习来保证种群的多样性,使算法能够有效地进行全局搜索.

1 基本思维进化算法

众所周知,自然界中的生物通过遗传和自然选择,进化了上亿年,生物的这个进化过程非常缓慢.相比之下,人类思维的进步速度却远高于生物的进化,有两个原因很重要,即向前人和优胜者学习以及不断地探索与创新.思维进化算法受此启发提出了“趋同(Similartaxis)”和“异化(Dissimilation)”操作,它继承了进化计算的“群体”和“进化”的精髓,仍然属于进化计算的一部分.

MEA把每一代中所有个体(潜在解)的集合称为一个群体.在“学习”初期,个体在解空间中随机散布,计算每个个体的得分.一些得分高的个体成为胜者,以它们为种子,形成若干个子群体并分为两类,即优胜子群体和临时子群体.在子群体范围内,个体为成为胜者而竞争的过程叫做趋同.一个子群体在趋同过程中,若不再产生新的胜者,则称该子群体已经成熟.当子群体成熟时,该子群体的趋同过程结束.趋同类似人类不断地向周围的成功者学习,有效地利用成功者积累的经验、知识来提高自己的过程.在整个解空间内,各子群体为成为胜者而竞争,并按得分高低优胜劣汰,不断地探测解空间中新的点,这个过程叫做异化.它类似人类在向他人学习的同时不断改变自己的思维方式,探索新的领域.MEA利用趋同与异化算子分别实现局部的开采与全局的探测功能.趋同算子使得各子群体朝着各自的局部最优的方向进化,而异化使优胜子群体朝全局最优的方向进化;由于算法中引入了局部公告板与全局公告板分别来记录两种操作中的有效信息并对其加以引导,使得 M EA中开采与探测两种作用能够协调工作.

2 群体智能理论

群体智能[7-8]的研究起源于对社会性动物群体行为的模拟.群体智能中的群体(swarm)指的是“一组相互之间可以进行直接通信或者间接通信的主体,这组主体能够合作进行分布问题求解”.群集智能指“无智能的主体通过合作表现出智能行为的特性”.群集智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础.

群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息,具有不同于传统优化算法的特点[9]：①群体中相互合作的个体是分布式的,不存在中心控制,具有较强的鲁棒性,即不会由于某一个或某几个个体出现故障而影响群体对整个问题的求解.②每个个体只能感知局部信息,不能直接拥有全局信息,并且群体中每个个体的能力或遵循的行为规则非常简单,因而群体智能的实现比较简单、方便.③个体之间通过非直接通信的方式进行信息的传输与合作,因而随着个体数目的增加,通信开销的增幅较小,也就是说,它具有较好的可扩充性.④自组织性.即群体表现出来的复杂行为是通过简单个体的交互突现出复杂的行为.

3 子群体迁徙及算法设计

3.1 带子群体迁徙的算法概述

本文受群体智能算法的启发而改进思维进化算法,算法中每个个体的大小和功能要根据所求解的问题而定,包括 3个重要的基本操作,即趋同、异化和子群体迁徙,它们遵循 Reynolds[9]所提出的动物(即个体)以群落形式生存觅食时遵循的 3个规则,即分隔规则、对准规则、内聚规则.先给出一些定义.

定义 1 子群体行为.设在 D维解空间中,有 S个子群体,子群体的行为就是子群体中的优胜者,即子群体种子,在解空间中的坐标.其中第i个子群体在解空间中的行为是 Hi=(hi1,hi2,…,hiD)(i=1,2,… ,S;j=1,2,… ,D).hij表示子群体 i在 j维上的行为.

定义 2 子群体动量.设在 D维解空间中,有 S个子群体,子群体的迁徙动量就是子群体中的优胜者,即子群体种子,在解空间中的迁徙动量.其中第i个子群体具有迁徙动量 Mi=(mi1,mi2,…,miD)(i=1,2,… ,S;j=1,2,… ,D).mij表示子群体 i在 j维上的迁徙动量.

定义 3 信息浓度.设解空间有 S个子群体,第i个子群体的信息浓度fi是历史最优子群体所发布的信息对其影响程度.它反映了整个群体的社会局势.

本文所设计的算法强调已有知识的共享和利用,增强各子群体之间的协同.所有子群体都可以获得社会局势信息,子群体的行为根据社会局势和子群体自身的行为及动量信息更新,而子群体中的个体则是根据子群体行为信息生成的.也就是说,每个子群体利用自己的知识和历史最优信息改善自己的行为,并共享和更改全局公告板信息,而子群体中的个体以其种子为中心按某种概率随机散布,根据较优秀的个体信息快速进化.同时,为了避免陷入局部最优解,防止算法早熟,在信息共享的条件下,旧的信息会随时间而渐渐淡化、挥发.这样,既实现了各子群体间的信息共享,避免各子群体进行封闭竞争,又有利于加快各子群体的收敛速度,减短子群体的生命期,相互促进更快找到全局最优.

MEA算法的异化操作对应分隔规则,体现个体信息的利用.趋同操作、子群体迁徙策略对应对准规则和内聚规则,体现了社会局势信息的利用.算法寻优进程中每个个体的动态不能保证在每个时刻都具有最佳的寻优收敛特征,算法寻优方式的实现是通过整个群体的总体优化特征来体现的,寻优过程是随机的、并行的、分布式的,这是群体智能的体现.综合看来,改进思维进化算法的精髓是找到一种合理的机制,使得在利用较好的解和搜索新的解两方面达到最佳平衡,在搜索速度和收敛性两方面达到最佳平衡.

3.2 子群体迁徙策略

趋同操作过程中各个子群体内的胜者,称为子群体的种子,也就是下一步操作的基础.异化操作通过公告板信息选出优胜子群体、临时子群体,并用新子群体代替临时子群体.但原有的 MEA没有充分利用公告板的全局信息,本文设计各个子群体,可以通过公告板获知其它子群体的信息,并按一定规则学习它们,以此来更正自己的行为.这种信息可以视为“社会局势信息”.在人类发展过程中,知识和信息为人类所共享,相互学习、交流促进了人类思维整体的进步.本文算法利用社会局势信息和自身的知识进行子群体迁徙,正符合了人类思维发展过程的特点.

定义 4 信息浓度更新规则.信息浓度发生变化的规则是,如果群体中最优个体的行为随着时间推移更新,则信息浓度参数重置,否则按线性衰减.也就是,第i个子群体信息浓度fi从 t时刻到 t+1时刻更新规则为：若最优个体在 t+1时刻发生行为更新,则fi重新置 1,否则fi线性规律减小,即

式中：di为第i个子群体信息挥发速度,且 0＜di＜1.

根据以上定义,本文在原有基本趋同操作以后,充分利用公告板中公布的社会局势信息,更新各子群体的行为,修整子群体优胜者的行为,即子群体的中心进行迁徙,设计的迁徙策略为

式中：Hi(t)是 t时刻子群体 i在解空间的行为;Mi(t)是其相应的迁徙动量;fi(t)是 t时刻子群体 i的信息浓度;pb(t)是 t时刻整个群体所找到的历史最优行为;gbi(t)是子群体 i寻优过程中 t时刻的历史最优行为,需要强调的是,gbi(t)不是子群体中某一单个个体的历史最优,而是子群体的;w为惯性权重且 w≥0;c1和 c2是学习因子且 c1≥0,c2≥0;r1和 r2是 [0,1]之间的随机数;S为 MEA中子群体的数目.

式(2)由三部分信息组成：① wMi(t)是子群体先前动量的影响分量,说明了子群体目前的状态,体现了子群体运动的惯性作用,使其具有扩展搜索空间的趋势,有助于新区域的搜索,有助于平衡全局和局部搜索.② c1r1(gbi(t)-Hi(t))是子群体信息,即局部知识的影响分量,表示子群体本身的认知、思考,使子群体有足够强的全局搜索能力,避免局部极值.③ c2r2fi(t)(pb(t)-Hi(t))为社会局势信息的影响分量,体现了子群体间的信息共享.信息浓度fi(t)反映了历史最优行为对其它子群体的影响程度,并随着时间推移而挥发,有助于避免过度学习,防止陷入局部极值.这 3个部分共同决定了子群体的空间搜索能力,体现了信息的共享.

通过“社会局势信息”、“子群体信息”的利用,有助于增强各子群体之间的协同,既实现了各子群体间的信息共享,避免各子群体进行封闭竞争,又有利于加快各子群体的收敛速度,减短子群体的生命期,相互促进更快找到全局最优.这样不仅保证了算法寻优过程可以在搜索空间中较大范围进行,又加快了算法的搜索速度,保证快速收敛性.同时,由于信息浓度的引入,有助于防止陷入局部最优.

3.3 带子群体迁徙的算法步骤

带子群体迁徙的 MEA算法具体步骤为：①设置进化参数,如群体规模,子群体规模,循环结束条件.②在整个解空间范围内按某种概率随机散布产生若干个个体.根据事先定义的适应度函数评价个体,并从中选出 S个最好的个体,分别作为 M个优胜子群体和 N个临时子群体的种子.其中 S=M+N.③每个子群体随机产生迁徙动量.④趋同操作.分别以已选出的 S个种子为中心,在每个种子周围按某种概率分布分别随机产生 G个个体组成 S个子群体,并进行内部竞争到子群体成熟,各子群体只有一个胜者被保留,代表该子群体进入下一步操作.⑤子群体迁徙操作.计算子群体迁徙动量和行为.根据适应度函数评价子群体,分为 M个优胜子群体和 N个临时子群体.⑥异化操作.释放 N个临时子群体及其迁徙动量,在整个解空间重新散布 N个个体,以它们为中心按某种概率分布分别随机产生 G个个体来组成 N个子群体并随机产生相应的动量.临时子群体进行内部竞争到子群体成熟.如果临时子群体在竞争中优于优胜子群体,则该临时子群体取而代之,而该优胜子群体则被降为临时子群体.竞争结束,所有的临时子群体被淘汰,并在整个解空间内重新产生 N个个体及动量.⑦判断进化结束条件.如果进化结果满足结束条件则转第8步,否则跳转到第4步.⑧结束迭代过程.输出进化结果.

4 实例仿真与分析

本文采用典型测试函数问题的优化来说明基于群体智能的思维进化算法的有效性.仿真实验所用的非线性测试函数有：① De Jong′s函数Booth函数 F2=(x1+ 2x2-7)2+(2x1+ x2-5)2,xi∈ [- 10,10].③ Schwefel函数,xi∈ [- 500,500].④ Powell函数 F4=(x1+ 10x2)2+ 5(x3-x4)2+(x2- 2x3)4+ 10(x1- x4)4,xi∈ [- 4,5].

粒子群算法(PSO)[10]是公认的群体智能算法中的一种,因其算法简单易实现,已有广泛应用[11].实验中将本文算法和基本 MEA、基本粒子群算法(PSO)在相同控制参数下进行了比较,其中最大进化代数均为 500,F1,F2和 F4的目标误差为 10-6,F3的目标误差为 0.1.表 1给出了实验结果,其中算法IM EA表示本文算法.图 1～图 4为函数 F1～F4寻优过程中最佳函数值进化曲线图.其中,实线表示本文算法进化过程曲线,点划线和虚线分别为基本 M EA和 PSO的进化过程曲线.结果显示,本文算法都获得了最优解,PSO和 MEA均出现了未能找到全局最优的情况(函数 F3和 F4).可以看出,带子群体迁徙的 MEA算法明显改善了基本思维进化算法,能有效地找到最优点,进化速度快、精度高,均未出现陷入局部极值点的现象.

表13种算法对测试函数的计算结果Tab.1 Calculating results of test function with three algorithm

5 本文算法自适应在线整定 PID控制

迭代次数实验采用带子群体迁徙的 MEA算法在线整定 PID控制参数,即针对每个采样时间实现PID参数的优化.仿真在 MAT LAB7.0平台上进行,算法参数为：群体规模为 6,优胜子群体和临时带子群体迁徙的 MEA算法子群体数目均为 3,并且子群体规模为 10,最大进化代数为 10.在每个采样时间,选取足够多的个体(PID控制参数),通过本文算法的优化,选择适应度最优的个体所对应的 PID参数作为该采样时间下的控制参数.设被控对象为二阶传递函数采样时间为 1 ms,输入指令为单位阶跃信号.本文算法优化过程中确定参数 Kp的取值范围为 [71,73],参数 Kd的取值范围为[2.3,2.4],参数 Ki=0.为了获取满意的过渡过程动态特性,并防止产生超调,设计算法适应度函数为

当误差较小时,以误差为主要调节目标;当产生超调时,增加惩罚功能,将超调量作为一项增加到适应度函数中.图 5为系统闭环控制单位阶跃响应曲线图,其中实线表示利用本文算法在线整定 PID控制效果,虚线为 PD控制效果(Kp=71,Kd=2.3).图 6和图 7分别为参数Kp,Kd在控制过程中变化曲线图,图 8为控制量的变化曲线图.由仿真结果可见,本文算法能有效地在线优化 PID控制参数,上升时间短,超调量小,获得良好的控制效果.

6 结束语

本文将群体智能的理论引入思维进化算法,分析改进 MEA的机制及实现技术,根据算法的机制设计了利用信息共享的子群体迁徙策略和信息浓度更新规则,有助于增强各子群体之间的协同,既实现了各子群体间的信息共享,避免各子群体进行封闭竞争,又有利于加快各子群体的收敛速度,减短子群体的生命期,相互促进更快找到全局最优.算法尽可能地在利用较好的解和搜索新的解并使两方面达到最佳平衡,同时在搜索速度和收敛性两方面达到最佳平衡.实验中进行了 4个测试函数的寻优,均能在短时间内搜索到高精度的全局最优解,均未出现陷入局部极值点的现象,说明了算法稳定性好,搜索时间短,优化精度高.本文将改进的 M EA应用于在线整定 PID控制参数,获得了良好的控制效果.

[1]谢克明,邱玉霞.基于数列模型的思维进化算法收敛性分析[J].系统工程与电子技术,2007,29(2)：308-311.Xie Keming,Qiu Yuxia.Convergence analysis of mind evolutionary algorithm based on sequence mode[J].Systems Engineering and Electronics,2007,29(2)：308-311.(in Chinese)

[2]Liu J X,Wang F,Xie K M.Application of improved mind evolutionary algorithm in wideband impendence transformer design[C].Proceeding of the 4th International Conference on Natural Computation(ICNC’08),Jinan,China,2008：428-432.

[3]刘建霞,王芳,谢克明.基于改进的思维进化算法的宽带阻抗变换器设计[J].中北大学学报(自然科学版),2008,29(5)：435-438.Liu Jianxia,WangFang,Xie Keming.Design of broadband impedance transformer based on improved mind evolutionary algorithm[J].Journal of North University of China,2008,29(5)：435-438.(in Chinese)

[4]刘建霞,王芳,谢克明.基于混沌搜索的思维进化算法 [J].计算机工程与应用,2008,44(30)：37-39.Liu Jianxia,Wang Fang,Xie Keming. Mind evaluation algorithm based on chaos searching[J].Computer Engineering and Applications,2008,44(30)：37-39.(in Chinese)

[5]Liu H B,Ajith A,Maurice C.Chaotic dynamic characteristics in swarm intelligence[J].Applied Soft Computing,2007,7(3)：1019-1026.

[6]Robert B.Swarm intelligence and robotics[J].Industrial Robot,2008,35(6)：488-495.

[7]Kennedy J,Eberhart R C,Shi Y.Swarm Intelligence[M].San Francisco,USA：Morgan Kaufmann Publishers,2001.

[8]Millonas M M.Swarms,phase transitions,and collective intelligence[C].C.G.Langton Artificial Life III.Santa Fe Institute Studies in the Sciences of Complexity,1994：417-445.

[9]Reynolds C W.Flocks,herds and schools：a distributed behavioral model[C].SIGGRAPH’87：Proceedings of the 14th annual conference on computer graphics and interactive techniques,New York,NY,USA,ACM Press,1987：25-34.

[10]Eberhart,Shi Y H.Particle swarm optimization：developments,applications and resources[C].Proceedings of the 2001Congress on Evolutionary Computation,South Korea,2001：81-86.

[11]张起贵.基于粒计算的清浊音分段算法[J].中北大学学报(自然科学版),2009,30(2)：184-188.Zhang Qigui.The unvoiced/voiced segment method based on granular computing[J].Journal of North University of China(Natural Science Edition),2009,30(2)：184-188.(in Chinese)