第5章生物群落演化模式与优化算法
引言

本章对自然界生物群落中具有不同种群关系(包括竞争、捕食、互利、共存和寄生关系)的生物群落演化模式进行建模与仿真研究，并在此基础上设计了新型的基于多群体协同进化的生物启发计算算法，分别是基于共栖关系的多群体协同粒子群优化MSPSOC、基于寄生关系的多群体协同粒子群优化MSPSOP、基于寄生关系的多群体协同粒子群优化MOPSOM和多种群多目标人工蜂群算法。本章对这些算法的性能进行了实验比较，并将其应用于实际工程应用中的RFID网络优化问题和多目标问题。
5.1生物群落进化中的种群演化模式

生态系统是指生物群落与其无机环境之间由于不断进行物质循环和能量交换而形成的统一整体［1］。而其中生活在一定空间内相互有直接或间接关系的有关种群的总体称为生物群落，即在自然界的生物群落系统中，由于同种生物个体之间(部分之间)的相互作用关系会形成种群； 各个种群由于其中的个体(部分)之间的相互作用会表现出一定的整体属性，即群属性。各个群以其属性为基础，相互之间的作用又构成了群落。例如，在一座山或一片森林里全体生物的总体构成了群落； 若仅考虑其中的两种或几种生物，如狼和野兔的捕食关系，这两种生物也可以看作是一个群落。
5.1.1生物群落的层次性信息网络拓扑结构
生物群落拓扑结构是一个多层结构。在每个种群内，由个体间的交流拓扑构成了群体的拓扑结构； 而在群落层面，种群之间的交流方式又构成了更高一层的拓扑网络。如图51所示，不同种群通过相互之间的竞争合作关系构成了群落的层次拓扑结构。

种群间的拓扑结构并不影响种群内部的拓扑结构，即种群内和种群间的拓扑构型可以各不相同。图52为一个种群之间为松散的环形链接，内部为紧密的晶体链接的层次异构结构。而在图53中，种群内部分别为环形、晶体、轮形和星形结构，种群间为全链接结构。


图51群落拓扑结构




图52内部为晶格连接外部为松散链接的2层拓扑结构




图53种群内部和种群间均为不同拓扑结构






5.1.2生物群落内种群共生模式的多型性

在生物群体的交互关系中，有一种方式很引人注意，即不同物种之间的共生行为。共生一词在英文或是希腊文
中，字面含义就是“共同”和“生活”，在生物学中指的是两种生物彼此互利地生存在一起、缺此失彼都不能生存的一类种间关系，是生物之间相互关系的高度发展。共生是生物在生理上相互分工，互换生命活动的产物，在组织上形成了新的结构［3］。术语“宿主”通常被用来指共生关系中较大的成员，较小者称为“共生体”。共生依照位置可以分为外共生、内共生。就外共生而言，共生体生活在宿主的表面，包括消化道的内表面或是外分泌腺体的导管； 而在内共生机制下，共生体生活在宿主的细胞内或是个体身体内部(在细胞外)都有可能。20世纪末的生物学研究推测，细胞内的叶绿体和线粒体也可能是内共生的形式之一。地衣是众所周知的共生实例，它是藻类和菌类的共生体。除地衣以外，在生物界的很多门类
都可以举出许多共生的例子。昆虫纲等翅目的昆虫及其肠道中的鞭毛虫之间的关系就是共生关系。等翅目昆虫的肠道是鞭毛虫或细菌的栖身之所，它们帮助等翅目昆虫消化纤维素，而等翅目昆虫不仅为它们提供藏身之所，还给它们提供养料。若互相分离，两者都不能生存。

根据共生对共生关系的生物体利弊关系而言，种群的共生模式又可以分为互利共生、偏利共生和寄生。
1. 互利共生［1］(++)

互利共生指的是共生的生物体成员彼此受益。例如，小丑鱼居住在海葵的触手之间，这些鱼可以使海葵免于被其他鱼类食用，而海葵有刺细胞的触手，可使小丑鱼免于被掠食； 而小丑鱼本身则会分泌一种黏液在身体表面，保护自己不被海葵伤害。一些寄居蟹会将海葵背于壳上。一些虾虎鱼种类，可和枪虾类形成共生。枪虾会在沙中挖掘洞穴并且清理它，这两种生物就居住在这个洞穴里面，枪虾几乎是全盲的，因此若在地面(水中的地面)有天敌的状况下会变得非常脆弱，在危急的情况下虾虎鱼用尾巴碰触虾，以警告它们身处危险之中，随后两种生物都会迅速退回洞穴中保护自己。在陆地环境，有一种鸟以擅长捕食鳄鱼身上的寄生虫而出名，而鳄鱼也欢迎鸟类在身上寻找寄生虫和清理食物残渣，甚至张大口颚以利鸟儿安全地至口中觅食。对鸟来说，这不仅是现成的食物来源，也是一个很安全的环境，因为许多掠食者不敢在鳄鱼身边攻击这些鸟类。
2. 偏利共生(+0)

偏利共生是指其中一方生物体受益，却对另一方无害。例如，印首鱼会利用头部的吸盘状构造，吸附在其他鱼类的表面，但是不造成伤害，借着被附着的个体的活动而行于水中。一些植物或是蕨类，例如鸟巢蕨(又称做山苏花)会附生在其他的植物上，特别是大树上较为平坦的一小块区域都是它们选择附生的所在。
3. 寄生(+-)
寄生是指一种生物寄附于另一种生物身体内部或表面，利用被寄附生物的养分生存，寄生对一方有利而对另一方有害。主要的寄生物有细菌、病毒、真菌和原生动物。在动物中，寄生蠕虫特别常见，而昆虫是植物的主要寄生物。根据寄生程度的不同又可分为专性寄生和兼性寄生，其中前者必须以宿主为营养来源，后者也能自由活动。较为极端的是： 一类寄生生物在完成一定的发育后，会将宿主食尽，对这种类型的寄生物特称为捕食性寄生物(Parasitoid)或者拟寄生物，以与一般的寄生物相区别。拟寄生物
包含一大类昆虫寄生物，它们在昆虫宿主身上或体内产卵，通常会导致宿主死亡。
5.1.3生物群落内种群的增长、迁徙和消亡模式

生物群落是不断运动的。我们知道，大自然中生物群落的动态变化受环境条件(特别是气候)周期性变化的制约，并与生物种的生活周期关联。群落的变化动态是群落本身内部的变化，是随着群落内各个物种种群的变化而变化的。组成一个群落的物种在其内部以及物种之间都存在特定的相互关系。这种关系随着外部环境条件和群落内环境的改变而不断进行调整。比如当一个种群密度增加时，种群内部的关系会紧张化，竞争能力强的种群将得以充分发展，而竞争能力弱的种群则不断缩小自己的地域，甚至被排挤到其群落之外。所以群落变化的实质是群落内种群的变化［4］。要想掌握群落的动态，必须熟悉一个种群的变化模式。下面对种群的变化模式进行介绍。
1. 种群的增长
种群中个体的数量经常在变化，也就是说，种群大小经常发生变化，这种变化是生态学工作者最感兴趣的问题。生态学工作者利用数学模型来模拟种群规模的变化。其中，以指数级增长是一种常见的方式。
在无限环境中，因种群不受任何限制因子的约束，种群的潜在增长能力得到了最大限度的发挥，种群数量呈现指数式增长格局，种群的这种增长规律称为种群的指数增长规律。常用指数模型进行描述，模型的假设： 

(1) 种群增长是无界的，即种群在无限的环境中生长，不受食物、空间等条件的限制； 
(2) 世代不相重叠(即寿命仅一年)，增长是不连续的(即一年只有一个繁殖季节)或称为离散的； 
(3) 种群无迁出和迁入(生境是彼此隔离的)； 
(4) 种群无年龄结构。

数学模型： 世代不相重叠种群的离散增长模型，通常是把世代t+1的种群Nt+1与世代t的种群Nt联系起来的差分方程
式： 


Nt+1=lNt或Nt=N0lt


式中，N为种群大小； t为时间； l是种群的周期增长率。
2. 种群的迁徙

某些无脊椎动物，如东亚飞蝗、蝴蝶等； 爬行类，如海龟等； 哺乳类，如蝙蝠、鲸、海豹、鹿类等； 还有某些鱼类都有季节性的长距离更换住处的行为，这种行为称为迁徙。动物的迁徙都是定期的、定向的，而且多是集成为大群地进行。

鸟类的迁徙每年在繁殖区和越冬区之间周期性地发生，大多发生在南、北半球之间，少数在东、西方向。人们按鸟类迁徙活动的有无把鸟类分为候鸟和留鸟。留鸟终年留居在出生地，不发生迁徙，如麻雀、喜鹊等。候鸟中夏季飞来繁殖、冬季南去的鸟类被称为夏候鸟，如家燕、杜鹃等； 冬季飞来越冬、春季北去繁殖的鸟类称为冬候鸟，如某些野鸭、大雁等。鱼类的迁徙活动有一个专有名称叫“洄游”。大多数的鱼类可以说都是洄游鱼类，只有少数鱼类不表现出规律性的洄游。鱼类洄游按目的分为3种： 生殖洄游、索饵洄游和越冬洄游。青鱼、草鱼、鲢鱼、鳙鱼、大黄鱼、小黄鱼、大马哈鱼都进行生殖洄游。哺乳动物的迁徙规模浩大，例如驯鹿的千里踏雪大迁徙。每年入冬，成千上万头的驯鹿汇集成巨大的鹿群，从北向南，朝森林冻土带的边缘地带转移。次年春天，它们再向北方的北冰洋沿岸进发。四五月份，鹿群到达它们熟知的冻土带僻静处，在此养育儿女。昆虫的迁徙有时能创造奇迹，最著名的是产于美洲的彩蝶王，它们春天从中美洲飞到加拿大，秋天又飞回中美洲，行程4500km，历时几个月，真是令人惊叹不已。

动物的迁徙行为是一种适应现象，凭借这种活动，可以满足它们在特定的生活时期所需要的环境条件，使个体的生存和种族的繁荣得到可靠的保证。与此同时，这些动物所处区域的生态系统也会随着迁徙行为的进行发生周期性的变化。
3. 种群的消亡

种群是在一定环境下由个体组成的。个体除了具有生物学特征外，还具有出生、生长、衰弱、死亡等状态。随之带来的是种群的增长，强大、衰落与消亡。当环境发生剧烈变化时，可能会造成整个种群出生率急剧下降或死亡率急剧上升。个体大规模死亡，甚至整个种群消亡。例如，白垩纪时期所发生的恐龙灭绝就是在极端环境造成的整个物种消亡。
5.2基于生物群落演化的计算模式设计
5.2.1基于生物群落演化的统一优化框架

基于生物群落的优化框架是在生物群体行为优化框架的基础上加上群体之间协作与竞争等交互组成的。在群体层面上，一个群体表现出了分工、协作和通信交流等智能行为。在群落层面上，种群之间存在信息交流与种间协同进化等现象。同时每个种群还独自表现出了增长、壮大、衰老和消亡等现象。

第4章中已经建立了基于生物群体行为的优化框架。本章在此基础上建立了以种群为基础的生物群落统一优化框架，如图54所示。


图54基于生物群体行为的优化层次框架



本章基于生物群落的统一优化框架模型可以形式化表示如下： 


BCM=(Individual,Population,Colony,Environment,Topology,Coevolution) 


(1) Individual： 群落中的个体。



Individual={Individual1,Individual2,…,Individuali,…,IndividualINUM}

Individuali=<IID,INOBJ,STATUS,BHV,MESS,ACT,TANS>


（2） Population： 群落中的种群。



Population={Population1,Population2,…,Populationi,…,PopulationPNUM}


其中，每个种群都有微观特性和宏观特性。
 种群微观特性表示如下： 



Population1={Individual1,Individual2,…,IndividualINUM}

=IID1INOBJ1STATUS1BHV1MESS1ACT1TANS1

IID2INOBJ2STATUS2BHV2MESS2ACT2TANS2

︙︙︙︙︙︙︙

IIDINUMINOBJINUMSTATUSINUMBHVINUMMESSINUMACTINUMTANSINUM


 种群宏观特性表示如下。 



Population=<PID,POBJ,OPT,PBHV,DRE,SPA,

N(t),DEN,STR,INPUT,OUTPUT,TRAN>



(3) Col： 模型中的群落。



Col={Col1i{Col2j{Col3k{…{ColNumx}}}}}

ColNumx=<CID,CN(t),CDRE,CSPA,CSTR,

CDEN,CBHV,INPUT,OUTPUT,TRAN>


具体含义详见5.3.1节。
（4） Environment： 环境，即优化的目标函数。
其中，Environment={Range,Food}，具体含义详见2.2节。
(5) Topology： 群落拓扑结构。
其中，Topologyk=(tk,Tk,TS,TD,{Aik,Pnjk})，具体含义详见5.3.2节。
（6） Coevolution： 不同个体、群体和层次之间的协同进化规则。
其中，Coevolution={Rul,Sym}，Rul具体表示方法详见5.3.3节，Sym具体
表示方法详见5.3.3节。
5.2.2基于生物群落演化的基本操作

由于生物群落是以多个生物种群为基础，因此基于生物群落的协同进化的本质是种群与种群之间的相互作用、相互交流。其主要体现在以下几个方面。
1. 种群间个体交流
(1) 种群之间的个体交换。用一个群体中的部分个体代替另一个群体中的部分个体。以加快整个群落的演化速度。
(2) 种群的合并、融合。两个或多个种群合并为一个种群。
2. 种群之间的个体信息共享与传递
在共生关系中，重要的一点就是资源的互相给予和利用。豆科植物和根瘤菌在整个共生阶段，根瘤菌被包围在宿主质膜所形成的侵入线中，在宿主内合成固氮酶。豆血红蛋白则系共生作用产物。具体来讲，植物产生球蛋白，而血红素则由细菌合成。豆血红蛋白存在于植物细胞的液泡中，对氧具有很强的亲和力，因此对创造固氮作用所必需的厌氧条件是有利的。就这样细菌开始固氮。在植物体内细菌有赖于植物提供能量，而类菌体只能固氮而不能利用所固定的氮。所以豆科植物供给根瘤菌碳水化合物，根瘤菌供给植物氮素养料。这种养分的互相供给在生物启发算法中可以表现为不同种群间的信息共享。
不同种群之间信息共享方式有多种。对偏利共生型群落结构，可能共享优秀个体信息，其他种群个体可以向这些优秀个体学习。对竞争性群落结构，被捕食种群个体可能根据捕食种群个体的位置、距离发生逃避行为。
3. 种群消亡与再生［1］

种群消亡与再生的思想主要来源于生物界的物种灭绝，本意是泛指植物或动物的种类不可再生性地消失或破坏，在地球的生命演化中扮演着重要的角色。据统计，全世界每天有75个物种灭绝，每小时有3个物种灭绝。在生物群落演化的计算模式中，种群消亡与再生是对种群的一个重要操作，每个种群都有自己的生命周期，当一个生命周期结束时，种群中属性不好的部分个体就要消亡，而另一些新的个体诞生，补充进来，保持种群的规模。

(1) 消亡规则。对长期不能适应环境的个体(具体表现为适应度或累积适应度差)，将其从种群中剔除。
(2) 再生规则。为保持个体的平衡和算法的稳定性，根据变量范围随机生成与消亡等量的个体，与初始化规则相同。
5.3生物群落建模与仿真分析
5.3.1生物系统群落的形式化定义

群落由多个种群组成，种群间的行为及关系构成了群落微观状态。但组织格局进入到群落水平时，生物个体和群体已成为较大和较复杂生物体系中的一部分，此时，作为整体的群落出现了许多不为种群所拥有的独有的新特征，如群落密度、群落等级等，即群落宏观信息集合。群落具有一定的自然属性，这种自然属性由底层所有个体和各层次种群的自然属性和社会属性共同出现形成。




ColNumx=<CID,CN(t),CDRE,CSPA,CSTR,CDEN,CBHV,INPUT,OUTPUT,TRAN>


(1) CID： 群落标识符，表示该群落在生态系统中的身份。


CID={CI,((1,i),(2,j)，…，(Num-2,l），(Num-1,u)，v)}


其中，CI表示当前种群的绝对身份，即代表整个系统中的标识。

((1,i),(2,j),…,(Num-2,l),(Num-1,u),v)
描述的是当前种群在群落中的相对身份，即第1层的第i个子种群落，第2层的第j个子种群落，以此类推，第Num-1层的第u个子种群落，第Num层的第v个子种群落。
(2) CN(t)： 此群落中种群个数，其值可以为常量，也可以为变量。

(3) CDRE： 此群落内种群等级。
(4) CSPA： 此群落空间分布范围。
(5) CSTR： 此群落空间格局。组成群落的种群在其空间中的位置或布局，随机分布、均匀分布或集群分布。
(6) CDEN： 此群落种群密度。
(7) CBHV： 此群落种群间个体交流方式。
(8) INPUT： 此群落接收的外界信息集合，如子种群落消亡信息、迁移信息等。这类信息是对此群落的宏观调控，并可对此群落内所有单元产生其相应作用。
(9) OUTPUT： 此群落进化过程中的输出信息集合，包括涌现的知识、求解问题的阶段性成果等。
(10) TRAN： 此群落群体状态的转换函数，也可称为刺激反应规则。TRAN: INPUT×STATUSi→STATUSi+1，表示此群落在接收到某些宏观调控信息后状态的转换。

5.3.2群落拓扑结构的形式化定义
群落拓扑结构形式化描述如下： 


Topologyk=(tk,Tk,TS,TD,{Aik,Pnjk})




（1） tk： 0≤tk≤tend，表示当前时间。如果拓扑结构为静态，则tk为任一常数。
（2） Tk： 第k个时间点整个群落所有层次所有进化单元的拓扑关系集合。


{Tk}=Tk

Tk1,1Tk1,2…Tk1,C1

Tk2,1Tk2,2……Tk2,C2

︙︙︙︙︙︙

TkNum,1TkNum,2…………TkNum,CNum



其中，{Tk}中的元素均可为静态拓扑关系或动态拓扑关系，Tki,j=(TSm)OR(TDm)。
（3） TS： 整个群落所有静态拓扑关系集合。



TS=TS1

TS2

︙

TSTSnum=
sname1deg1cc1apl1adeg1…

sname2deg2cc2apl2adeg2…

︙︙︙︙︙︙

snameTSnum
degTSnum
ccTSnum
aplTSnumadegTSnum…




其中，TSnum表示觅食时间内静态拓扑关系的个数； sname表示静态拓扑关系名称； deg表示拓扑关系直径；  cc表示聚类系数； apl表示平均路径长度； adeg表示平均度。另外，也可以根据此描述方法增加拓扑关系所需的参数。
（4） TD： 整个群落所有动态拓扑关系集合。



TD=TD1

TD2

︙

TDTDnum=
dname1function1Iupdate1…

dname2function2Iupdate2…

︙︙︙︙

dnameTDnumfunctionTDnum
IupdateTDnum…



其中，TDnum表示觅食时间内动态拓扑关系的个数； dname表示动态拓扑关系名称； function表示邻域函数； Iupdate表示个体状态更新方式。动态拓扑关系有时很难用邻域函数表示，此时，也可以根据此描述方法增加特殊拓扑关系所需的参数。目前研究较多的静态拓扑关系有全互连结构、环形结构、冯·诺依曼结构、随机结构及小世界网络等。

（5） Aik： 表示第k个时间点个体i的邻域关系。


Aik=(Xki,Ψkp)，Ψkp={Ψk1,a,Ψk2,b,…,Ψkp,…}



其中，Xki表示第k个时间点个体i的属性； Ψkp是与个体Aik存在协作关系的其他个体集合； p是此集合中个数总数目； a,b,…表示每个个体在整个个体集合中的序号，1≤a,b,…≤I。

（6） Pnjk表示第k个时间点第n层第j个群体的邻域关系： 


Pnjk=(Pn,kj,SkQ)， SkQ={Sk1,a,Sk2,b,…,SkQ,…}


其中，Pn,kj表示第k个时间点第n层j个群体的属性； SkQ表示是与群体Pnjk存在协作关系的其他群体集合； Q是此集合中群体总数目。
5.3.3基于不同种群关系生物群落演化建模与仿真
1. 种群共生关系


生物种群生活在一定空间里相互会有着直接或间接的共生进化关系。在自然生态系统中，共生进化现象非常普通。物种在生存区域内，通常存在多个群体，每个群体都自己的个体类型。不仅群体中的个体可以相互交流，而且不同类型的群体之间也可以共生进化，从而实现这片生存区域内所有个体的共生。
(1) 互利共生(mutualism)。
互利共生是指两种生物生活在一起，彼此有利，两者分开以后都不能独立生活。图55很好地描述了两个物种随着进化的进行而展现出的两者之间的关系。可以看到，两个种群都能够迅速地收敛于最优点，并且收敛速度几乎同步。这说明它们之间相互合作共享了最优值的信息。


图55互利共生的两物种之间进化关系图



(2) 共栖(commensalism)。
共栖是指两种生物生活在一起，对一方有利，对另一方也无害，或者对双方都有利，两者分开以后都能够独立生活。例如，有些附生植物附着在大树上，借以得到充足的光照，但是并不吸收大树体内的营养。海葵常常固着在寄居蟹的外壳上，海葵靠刺细胞防御敌害，能对寄居蟹间接地起到保护作用而寄居蟹到处爬动，可以使海葵得到更多的食物，但是它们分开以后仍能独立生活。由图56可以看出，Host种群独自进行优化，而Commensal种群借鉴了Host种群的信息使其迅速收敛，该图很好地反映了这种共栖状态下两种生物的进化关系。


图56共栖的两物种之间进化关系图


(3) 寄生(parasitism)。
寄生是指两种生物在一起生活，一方受益，另一方受害，后者给前者提供营养物质和居住场所，这种生物的关系称为寄生。图57描绘了具有寄生的两物种之间的关系。当Host种群通过逃离Parasite种群时，其种群能够壮大生长。而当Parasite种群追踪到Host种群后利用了Host发现的最优区域，因此在迭代后期收敛效果较好。


图57竞争的两物种之间进化关系图


(4) 捕食者猎物(predatorprey)。
捕食者与猎物之间的竞争与寄生类似，也是一方受益而另一方受害。捕食者与被捕食者通过这种进攻与防御的竞争，互相不断进化。这是典型的一种协同进化。在此不多做介绍。

基于生物群落的优化思想主要来源于以上介绍的协同进化概念，应用到实际优化中，可理解为更广义的概念。不仅是不同物种的个体生活在一起，形成相互都受益的关系，而且也可以有相同物种的不同种群中的个体互相合作的关系。同样，上面中提到的例如互利共生的概念也使用较广义的术语定义，所以此术语也可指相互离开也可正常生存的生物组合中物种间的关系。
2. 共生进化模型

生物在长期进化过程中的共生关系多种多样，依照对共生关系的生物体利弊关系而言，共分为4类： 无关共生、合作共生、寄生共生和竞争共生，如表51和图58所示。


表51共生单元间的共生类型



类型单元A单元B特征

无关共生关系［图58(a)］00双方都无益无损

合作


互利共生［图58(b)］++共生双方都得到好处
偏利共生［图58(c)］+0对一方有利，对另一方没有影响

寄生关系(捕食关系)［图58(d)］+-对其中一方有利，对另一方有害

竞争

竞争共生［图58(e)］--共生双方都受损
偏害共生［图58(f)］-0对一方有害，对另一方没有影响

“+”表示有利，“-”表示有害，0表示既无利也无害。



图58共生关系分类



整个群落内的种群和子种群落的共生关系都可按上述关系进行划分，因此，统一框架模型中的共生关系可按如下形式来描述： 



Sym={unitAi}=({signa},{a},{unitB},{signb},{b})

=

signa1a1unitB1signb1b1

signa2a2unitB2signb1b2

︙︙︙︙︙

signaunumaunumunitBunumsignb1bunum

i


其中{unitB}表示与unitA有共生关系的单元集合，unitA和{unitB}中的元素可为种群，也可为子种群落。
{signa}和{signb}中的元素表示它们之间的共生关系。如{signa}=+，{signb}=+，则表示它们之间为
互利共生。
如{signa}=-，{signb}=0，则表示它们之间为偏害共生。
{a}和{b}
中的数值分别表示他们之间的共生程度。如
{signa}
=+，{signb}
=-，aj=5，bj=4，则表示
unitA
和unitBj
之间为寄生关系(捕食关系)，unitA
受益程度为5，unitBj
受害程度为4。如果省略这两个数值，则表示它们为完全共生。
3. 举例： 子种群协作群搜索算法
基于群搜索算法，考虑到约束优化问题的特点，利用偏利共生型协同进化思想，设计了子种群协作群搜索算法。算法中包括共同生活在某个区域内且位置相邻的两个群体，满足约束条件的个体组成可行子种群(feasible subswarm)； 反之，不满足约束条件的个体组成了不可行子种群(infeasible subswarm)； 这两个子种群按照偏利共生型协同进化方式共生。可行子种群为主群，不可行子种群为从群。首先，每个群的成员都能按照群的特有生存方式生活，互不干扰。其次，主群能从从群获得利益并使主群内的成员更好
地进化，但这种利益关系对于从群成员无关紧要。

在可行子种群和不可行子种群之间存在着一个约束边界。在偏利共生型协同进化方式中它起到了“单向围墙”作用，如图59所示。可行子种群内的个体可在可行域内自由搜索，一旦当个体通过搜索移动到了不可行域，这个围墙会阻止个体的这次行为，让它回到原来的可行域内的另一个位置。不可行子种群内的个体既可以继续在不可行域内搜索，也可以通过搜索进入可行域，从而成为可行子种群成员。


图59个体行为规则



可行子种群的搜索策略与标准群搜索算法类似，群内成员同样被分为3类： 发现者、加入者和游荡者。在每轮迭代中，当前位置最佳的个体为此轮的发现者，其他个体随机地被选择为加入者或游荡者。发现者和加入者的搜索策略与标准群搜索算法中的相同，唯一不同的是游荡者搜索策略。在可行子种群内，每个个体都会保存它整个搜索过程中的历史最优位置信息。当个体的角色为游荡者时，个体会基于它的历史最优位置进行随机步长的独立搜索，如式(51)所示。


Xk+1i=Xkp+
liDki(φk+1i)
(51)


在不可行子种群内，不存在全局最优个体，因此只有搜索者和游荡者两类成员。每个个体都可以在这两种角色中切换。这两种角色的个体的搜索策略与标准群搜索算法相同，此处不再赘述。
本书将子种群协作搜索算法应用于1个优化函数和3个机械优化设计问题。
1) Himmelblaus函数
Himmelblaus函数是非线性优化问题，包括5个设计变量和6个非线性约束条件。

目标函数：  f(X)=5.2578547x23+0.835689x1x5+37.293239x1-40.792141
约束条件：  g1(X)=85.334407+0.0056858x2x5+0.0006262x1x4-

0.0022053x3x5≤92

g2(X)=80.51249+0.0071317x2x5+0.0029955x1x2+

0.0021813x23≤110

g3(X)=9.300961+0.0047026x3x5+0.0012547x1x3+

0.0019085x3x4≤25

其中，78≤X1≤102，33≤X2≤45，27≤X3≤45，27≤X4≤45及27≤X5≤45。

2) 压力容器
工程上常见的半球形封头压力容器设计简单，如图510所示，广泛应用于石油及化学等工业领域。在力求满足强度等要求的前提下，以压力容器重量为目标函数。此问题共4个约束条件和4个优化变量。

目标函数： f(X)=0.6224X1X3X4+1.7781X2X23+3.1661X21X4+19.84X21X3
约束条件：   g1(X)=0.0193X3-X1≤0 
g2(X)=0.00954X3-X2≤0
g3(X)=1296000-πX23X4-43πX33≤0
g4(X)=X4-240≤0


其中，X1和X2分别为封头(Th)和筒体壁厚(Ts)，0.0625≤X1，X2≤6.1875； X3为筒体及封头底面半径(R)； X4为筒体长度(L)，10≤X3，X4≤200。在4个变量中，X1和X2是间隔为0.0625的均匀离散变量，X3和X4是连续变量。
3) 压缩弹簧
压缩弹簧广泛使用在一些机械中，如内燃机和压缩机等，如图511所示，因而弹簧性能的好坏直接影响到机器的工作性态。压缩弹簧通常以质量最小作为最优化设计目标。此问题共4个约束条件和3个优化变量。
目标函数： f(X)=(X3+2)X2X21
约束条件：   g1(X)=1-X32X371785X41≤0
g2(X)=4X22-X1X212566(X2X31-X41)+15108X21-1≤0
g3(X)=1-140.45X1X22X3≤0； g4(X)=X2+X11.5-1≤0

其中，X1为弹簧线径(d)，0.05≤X1≤2； X2为弹簧圈均径(D)，0.25≤X2≤1.3； X3为弹簧线圈数目，2≤X3≤15。这3个变量均为连续变量。


图510压力容器




图511压缩弹簧


4) 焊接悬臂梁
焊接梁优化设计问题以最小化焊接梁的总费用为优化目标，如图512所示。此问题共7个约束条件和4个优化变量。


图512焊接悬臂梁结构示意图


目标函数：  f(X)=1.10471x21x2+0.04811x3x4(14.0+x2)
约束条件：  g1(X)=τ(X)-13000≤0； g2(X)=σ(X)-30000≤0
g3(X)=x1-x4≤0
g4(X)=0.10471x21+0.04811x3x4(14.0+x2)-5≤0
g5(X)=0.125-x1≤0； g6(X)=δ(X)-0.25≤0
g7(X)=6000-Pc(X)≤0



τ(X)=(τ′)2+2τ′τ″x22R+(τ″)2，τ′=60002x1x2，τ″=MRJ，M=6000L+x22，

R=x224+x1+x322，δ(X)=504000x33x4，J=2x1x22x2212+x1+x322

σ(X)=2.1952/x4x23，Pc(X)=64746.022(1-0.0282346x3)x3x34


其中，优化目标为最小化焊接梁的总费用。焊接厚度h=X1，焊接接头长度l=X2，梁的宽度t=X3和梁的厚度b=X4。0.1≤X1≤2.0，0.1≤X2≤10，0.1≤X3≤10，0.1≤X4≤2.0。变量X1和X2是间隔为0.0065的均匀离散变量，X3和X4是连续变量。 

表52列出了iGSO算法基于上述问题分别执行30次获得的最优值、平均最优值、最差值和标准差。可以看出，iGSO算法能够获得较优秀的解。除此之外，表53显示出iGSO最终求得的机械变量设计方案没有违反任何约束条件。因此iGSO算法不仅对约束优化测试函数有效，而且可以用于实际的工程应用。


表52函数测试结果



结果Himmelblaus压力容器压缩弹簧焊接梁

最优值-30665.36476059.7140 0.01271.7217
平均值-30665.36006238.80100.01271.7380
最差值-30370.55226820.41000.01301.9174
标准差72.2230194.32005.1×10-50.0345


表53测试实例最优设计方案



问题结果

Himmelblaus function


优化方案(78,33,29.9959,44.9987,36.7746)
约束值(92,98.8409,20)


Pressure Vessel

优化方案(0.8125,0.437500,42.0984,176.6366)
约束值(0,-0.0359,0,-63.3634)


Spring

优化方案(0.0517,0.3568,11.2862)
约束值(0,0,-4.0539,-0.7277)


Welded Beam

优化方案(0.205709,3.4484,9.0366,0.2057)
约束值(-0.0009,-0.0007,-3.9601,-3.4350,-0.0807,

-0.2355,-0.0003)



为验证iGSO优化算法的收敛速度，本书将iGSO同iPSO和iGA这两个算法进行了对比。iPSO和iGA分别是指将iGSO的约束处理方法附加在标准的PSO和GA上。对于压缩弹簧测试实例，iGA、iPSO和iGSO 3个算法优化的结果分别是0.015892、0.013442及0.012664； 对于压力容器测试实例，iGA、iPSO和iGSO 3个算法优化的结果分别是6924.1653、6311.9632及6059.7143。从实验数据可以看出，iGSO的优化性能优于另外两个算法的优化结果。图513给出了3个算法优化这两个实例的迭代进化曲线。同iPSO和



图513两个机械设计实例的收敛曲线比较图


iGA相比，iGSO的最优解值优化性能并不突出，但iGSO具有较高收敛速度，即可以以最快的速度找到最优解，在时间特性上有了比较好的改善。
5.4基于生物群落演化的优化模型与算法实例设计
5.4.1协同进化算法的发展现状

近几十年随着群落生态学的发展以及对多种群协同进化理论的深入研究，许多以协同进化为基础的进化算法相继被提出并得到了很好的优化效果。协同进化算法在进化算法的基础上，考虑了种群与环境之间、种群与种群之间在进化过程中的协调。虽然协同进化算法起步较晚，但由于其算法的优越性，目前已成为当前进化计算、群体智能领域的一个研究热点［7］。

根据生态学上物种间的捕食者与猎物(predatorprey)、寄生物与宿主(hostparasite)、相互竞争(competition)、互利共生(mutualism) 4种关系，可以将协同关系划分为两类，即竞争关系和合作关系。因此协同进化算法同样也分为体现竞争关系的竞争型协同进化算法(Competitive CoEvolutionary Algorithm)和体现合作关系的合作型协同进化算法(Cooperative CoEvolutionary Algorithm)［811］。

在合作型协同进化算法方面，Potter和De Jong是合作型协同进化算法的先驱，提出了用于函数优化问题的协同进化遗传算法(Cooperative Coevolutionary Genetic Algorithm，CGGA)［12，13］。考虑一个具有N个变量的待优化函数，CCGA对每个变量维持一个种群，并用传统遗传算法对每个种群进行优化。由于各个种群的单个个体只是部分解，个体适应度的计算需要从各个种群选出个体构成问题的一个完整解来赋值。郑浩然等提出了多模式共生进化算法
(MultiPattern Symbiotic Evolutionary Algorithm，MSEA)［16］，与CCGA算法不同之处在于： 其一，MSEA将优化函数变量分成几组，称为模式，各个模式采用不同的进化方式； 其二，个体适应度的计算方法不同，对于某个种群内的个体a，MSEA首先从各个种群随机选取n个个体与a组成完整解，然后计算这个n个完整解的适应度，把这些解的适应度的平均值作为个体a的适应度。除此之外，刘静等对协同进化计算模型进行了分析，并提出了一种组织协同进化算法用于海量数据分类问题［14］。Seredynski针对N人博弈问题提出了协同进化多智能体系统模型。GarciaPedrajas等将合作型协同进化算法用于神经网络集成的设计，并通过一组真实的分类问题测试了其有效性［15］。

在竞争型协同进化算法方面，曹先彬、郑浩然等人［1719］提出了基于生态竞争模型的协同进化算法。该算法把种群分成若干子种群，算法在每次迭代中都依次进行进化和协同过程，其中进化过程采用遗传算法的操作方法，协同过程通过种群竞争方程计算种群密度，并根据计算出的种群密度调整各个子种群的规模，从而实现根据适应度的情况动态地调整各个模式在种群中的比例的目的。随着协同进化理论在进化计算方面的应用越发成熟，本书在下面给出了基于自然界多群体群落共生协同进化的思想，集成了3种共生模式设计出的一种新型多群体协同统一优化模型，从而指导新型的多群体智能算法设计。
5.4.2多群体协同进化统一模型

本节根据前面提到的互利共生、共栖、寄生3种种群之间的关系，设计了一个新型多群体协同统一优化模型。在该优化模型中，基于主(Master)从(Slave)式的结构来表示多群体群落，并基于有向加权图来定义群体之间的共生关系。整个群落被分为
N个子种群，由Nm个主群(Master species)和Ns个从群(Slave species)组成，Nm+Ns=N。这里规定： 

(1) 从群之间在进化时没有信息交流。
(2) 主群之间或主群与从群之间可以进行信息交流。
(3) 每个种群均包含相同的个体数，基于不同共生模式的种群间信息交流模式由集合I={Mutualism，Commensalism，Parasitism}定义，其中3种共生关系Mutualism，Commensalism，Parasitism分别由Master A+Master B，Slave A+Master B，Slave A+-Master B定义。
(4) 每个种群均可以应用不同的进化计算或群体智能优化算法作为进化规则。

由此建立的多种群共生协同进化优化模型如图514所示，图中箭头表示在不同共生关系下种群间的信息的传递。根据不同的主、从群数以及信息交流模式设置，该多种群共生协同进化统一模型可以表示不同的共生模式。


图514多种群共生进化模型



(1) Nm=0,Ns=N,I∈： 各种群独立进化，种群之间没有信息交流，即基于基本进化计算或群体智能算法的并行优化算法模型。
（2） Nm=1,Ns=N-1，I={Commensalism}： 主群接收多个从群传递的信息从而受益，从群之间无信息交流，即基于共栖模式的多种群协同进化。
（3） Nm=1,Ns=N-1，I={Parasitism}： 主群与从群直接具有信息交互，主群受益而从群受害，从群之间无信息交流，即基于寄生模式的多种群协同进化。
（4） Nm=N,Ns=0，I={Mutualism}： 所有的种群共享信息而互相受益，即基于互利共生模式的多种群协同进化。

5.4.3多种群共生协同进化粒子群优化算法
根据5.4.2节提出的多群体协同进化统一模型，本节提出了多种群共生模式的协同进化粒子群优化算法(Multispecies Symbiotic Particle Swarm Optimizer，MSPSO)。首先对3种模式下的MSPSO给出了一个统一的形式化描述。紧接着基于该形式化描述详细描述了3种多种群协同进化粒子群优化算法。3种算法分别是基于共栖关系的粒子群优化算法MSPSOC、基于寄生关系的粒子群优化算法MSPSOP和基于寄生关系的粒子群优化算法MOPSOM。最后对3种算法的性能进行了实验比较。
1. 多群体共生协同进化粒子群算法的形式化描述
MSPSO算法的进化模型是由个体层、群体层和群落层构成。定义如下： 


MSPSO=(Individual,Population,Colony,Environment,Topology,Coevolution)


1) 个体层


Individual={Individual1,Individual2,…,Individuali,…,IndividualINUM}


第i个个体表示为Individuali=<IIDi,POSIi,FITNESSi,BHVi>，它们分别表示个体i的序号、位置、适应度和行为集合。
2) 群体层


P={P1,P2,…,PM}


其中，群体层的任一个种群可表示为Population=<OPT,PBHV,N>其中，OPT为群内最优个体； PBHV表示群内个体间行为，PBHV={CA}； N为种群大小。
3) 群落层


Col={Col1i{Col2j{Col3k{…{ColNuml}}}}}



4) 环境
Environment由优化函数定义。
5) 拓扑结构


Topology=(TS,{Aik,Pnjk})



其中，TS表示此算法静态拓扑结构； Aik： 表示第k个时间点个体i的邻域关系； Pnjk表示第k个时间点第n层第j个群体的邻域关系。

6) 协同进化



Coevolution={Sym}，Sym={unitAi}=({signa},{unitB},{signb})i



对于算法的每一次迭代t，个体的进化规则CA表示如下： 



αt+1ik=c1r1(pbesttik-Xtik)+c2r2(sbesttk-Xtik)+Bβt+1k(52)

βt+1k=c3r3(cbesttp-Xtk)
(53)



式(52)中αt+1ik表示个体层Xtik在下一时刻(t+1)的加速度； pbesttik表示个体在解空间中的最优历史位置； sbesttik表示个体层群体k中和个体Xtik有协作关系的个体在解空间中的当前最优位置； r1和r2为均匀分布在［0,1］区间的随机数； c1和c2为学习因子； Bβt+1k表示个体Xtik从其他种群中所获得的最优位置信息。其中B为控制变量，B={-1,0,1}。当B=-1时，表示个体Xtik所处种群与其他种群是受害关系，受到其他种群伤害。当B=0时，表示个体Xtik所处种群与其他种群是互不影响的关系。当B=1时，表示个体Xtik所处种群从其他种群获利。

其中式（53）中cbesttp表示群体层中和Xtk所在种群有协作关系的其他种群最优位置信息； r3为均匀分布在［0,1］区间的随机数； c3为学习因子。则整个系统的进化可以表示为： 



Vt+1ik=χ(Vtik+αt+1ik+Bβt+1ik)
(54)

if(k∈e)Xt+1ik=r×(ub-lb)+ub(55)

elseXt+1ik=Xtik+Vt+1ik(56)



式（55）表示所有物种(群体层的个体)承受同样的外部环境压力，当压力超过某一阈值时，一些物种将消失以缓解环境压力，新的物种将同时产生以增加系统的生物多样性。其中e表示将要灭绝的物种集合。基于上述形式化描述，下面给出了多种群共生协同进化粒子群优化算法的一个流程框架，如图515所示。



图515多群体共生协同粒子群优化算法框架


2. 多种群共栖粒子群算法MSPSOC

根据统一模型，此时Nm=1,Ns=N-1，I={Commensalism}。在每次迭代过程中，每一个从群执行标准的PSO算法进行种群内个体速度与位置更新，更新方程式如下： 


vSjid=wvSjid+c1r1pSjid-xSjid+c2r2pSjg-xSjid(57)

xSjid=xSjid+vSjid(58)


在所有的从群在进行下一步状态更新之前，把到目前为止发现的最好位置信息发送给主群，然后主群根据自身位置信息和其他从群中最好位置信息进行状态的更新，更新方程式如下： 



vMid=wvMid+c1r1pMid-xMid+c2r2pMg-xMid+c3r3(pQg-xMid)(59)

xMid=xMid+vMid(510)


式中各变量的含义如下： 
M： 主群； 
S： 从群集合； 
j： 从群集合中的种群编号，j=1，2，…，N-1； 
Q： 从群最好位置信息集合； 
c3： 共生学习因子，通常取2.0； 
r3： (0,1)之间的随机数； 
pQg： Q中的最优位置信息。


其余变量的含义见基本PSO算法介绍。

可见，在多种群共栖粒子群算法的更新机制中，主群中每个粒子根据自己本身的最优历史经验、其隶属种群的当前最优经验以及所有从群的当前最优经验进行状态更新。
3. 多种群寄生粒子群算法MSPSOP

此时Nm=1,Ns=N-1，I={Parasitism}，主群与从群分别模拟寄生物与宿主。在每次迭代过程中，每一个从群因与发生信息交互而受害，其表现形式为远离主群当前最优位置所在的区域，更新方程
式如下： 


vSjid=wvSjid+c1r1pSjid-xSjid+c2r2pSjg-xSjid-c3r3pMg-xSjid(511)

xSjid=xSjid+vSjid(512)



在所有的从群进行下一步状态更新之前，把到目前为止发现的最好位置信息发送给主群，然后作为寄生物的主群根据自身位置信息和其他从群中最好位置信息进行状态的更新，更新方程式如下： 


vMid=wvMid+c1r1pMid-xMid+c2r2pMg-xMid+c3r3(pQg-xMid)(513)

xMid=xMid+vMid(514)


可见，在多种群寄生粒子群算法的更新机制中，主群粒子追踪从群粒子加速了向全局最优解靠近，从群粒子受主群粒子排斥跳出局部最优点，逃离到新的搜索区域。这样的寄生进化模式能够有效保持种群多样性，克服了基本粒子群算法“趋同性”早熟收敛问题。


表54MSPSO算法伪代码




Algorithm MSPSO

Begin

Initialize the population //主群和从群

Evaluate the fitness value of each particle in each swarm

Repeat

Do in parallel //从群进化

Swarm i,1≤i≤Ns 

End Do in parallel

Barrier synchronization//等待所有进程完成

Select the fittest global individual pSg from all the slave swarms

Do in parallel//主群进化

Swarm j,1≤j≤Nm

End Do in parallel

Barrier synchronization

Evolve the slave and master swarm

Evaluate the fitness value of each particle in each swarm

Until a terminatecondition is met

End


4. 多种群互利粒子群算法MSPSOM

此时Nm=N,Ns=0，I={Mutualism}，所有种群共享各自发现的最优位置信息而互相受益。在每次迭代过程中，每个种群更新方程式如下： 



vMjid=wvMjid+c1r1pMjid-xMjid+c2r2pMjg-xMjid+c3r3(pLg-xMjid)(515)

xMjid=xMjid+vMjid(516)


公式中各变量的含义如下： 
 M——主群集合； 
 j——主群集合中的种群编号，j=1，2，…，N； 
 L——主群最好位置信息集合； 
 pLg——L中的最优位置信息。
可见，多种群互利协同进化过程不仅加快了算法的收敛速度，而且有效地保持了整个系统的多样性，在克服“趋同性”早熟收敛问题的同时，显著提高了算法的收敛精度与收敛速度。

上述3种版本多群体共生粒子群优化算法可统一由表54的MSOPSO算法伪代码表述。
5.4.4算法性能分析
1. 实验设置

为测试3个版本MSPSO算法的性能，选择了常用的一组标准测试函数，即
Sphere()、Rosenbrock()、Ackley()、Rastrigrin()、Griewank()函数。其中，Sphere()、Rosenbrock()、Ackley()为单峰函数，Rastrigrin()、Griewank()为多峰函数。

为了检验MSPSO模型的性能，本节设计了两个实验，分别为算法优化性能实验和多种群协同进化动态特性实验。第1个实验用于检验3个版本MSPSO算法的综合优化(全局、局部搜索能力)性能，并与基本粒子群算法PSO进行比较分析； 第2个实验用于深入分析MSPSO模型中不同共生关系的种群进化动态特性。第1个实验选用了上述5个测试函数，第2个实验选用了单峰函数Rosenbrock()和多峰函数Rastrigrin()、Griewank()。

PSO参数设置为Vmax、Vmin为自变量边界范围的一半，c1和c2设为2.0，
惯性权重设置为随着迭代次数的增加从0.9线性减小到0.4。对于3个版本的MSPSO算法，3个学习因子均取值为1.494，惯性权重设为0.729。在所有的试验仿真中算法的群体规模设置为80，MSPSO分为2个子种群，每个子种群的群体数都为40。算法终止的条件为满足最大迭代次数1000。每个算法独立运行30次。
2. 实验1： 函数优化
5种算法对所有30维测试函数的运行30次的平均值见表55，所有算法针对每个函数的优化过程收敛曲线比较见图516。

对于较为简单只有一个全局最优解的单峰函数，收敛速度是考查优化算法性能的重要指标。从图516(b)可以观察到，所有的算法都能迅速收敛到Sphere（）函数的全局最优解。但是，3种协同进化算法比基本PSO算法具有更快的收敛速度，这体现了
共生协同进化模型中不同种群之间的信息交流显著提高了算法的收敛速度。Rosenbrock（）函数被称为“香蕉问题”，其全局最优解隐藏在了一条狭长扁平的通道中。发现通道并不是很难，难的是发现通道中的最优点。对于Rosenbrock（）函数，协同进化算法仍然要由于PSO算法。其中，MSPSOC以最快的收敛速度达到了该函数的次优解。说明MSPSOC模型中主群通过从群的全局最优信息，增强了整个群体的寻优能力。

函数Ackley（）是一个相对简单的多峰函数，从优化结果可以看出，所有算法都收敛到了全局最优解，但是协同进化算法仍然表现出了突出的收敛速度，这从另一个方面体现了协同进化算法的鲁棒性。
函数Rastrigrin（）是复杂的多模态函数。协同进化算法与PSO算法的最终收敛结果基本趋同，但协同进化算法的收敛速度仍然是优于PSO算法的。 
对于最后一个复杂多峰函数Griewank（），MSPSOP体现出了优异的性能。从图515可以看到，PSO算法在500代后趋于停滞，陷入局部最优，其收敛曲线表现为一条直线。而MSPSOP以非常快的速度向优优解收敛，并在750代附近定位到函数的全局最优。

通过对表55及图516的研究，可以得出本章提出的多群体共生协同进化方法是一类性能优越的优化算法，与经典PSO算法相比，它在收敛速度、求解精度与稳定性等方面都有很大程度的提高。因此，有理由相信MSPSO的突出优化能力来源于在进化过程中多群体间的共生机制对算法多样性保持起到了很大作用。


表55所有算法的测试结果




函数


算法MSPSOCMSPSOPMSPSOMPSO

Sphere()1.8453e-0442.1518e-0365.9234e-0312.2973e-012
Rosenbrock()13.349113.94190.197524.4461
Ackley()9.2371e-0156.9870e-0157.3423e-0152.3529e-005
Rastrigrin()44.706832.502036.217228.4593
Griewank()0.008402.4653e-0040.0183

3. 实验2： 协同进化仿真
为了进一步分析MSPSO模型中多群体进化的动态特性，图517~图519给出了基于3种共生机制的算法在测试函数定义的环境中的协同进化过程。可以看到，3种算法都有效地模拟了自然界中的共生模式。
对于模拟共栖模式的MSPSOC模型，Host种群从多数图中可以观察到从群在迭代初期迅速收敛，在迭代后期一般会产生早熟收敛停滞不前； 而Commensal种群通过接收Host种群的最优解信息，在迭代初期迅速收敛到最优解区域，进而在迭代后期定位全局最优解。

对于模拟寄生模式的MSPSOP模型，由于竞争关系，在迭代初期收敛缓慢，这是因为Host种群通过逃离Parasite种群所在的区域，从而能够进行大范围最优值探索； 而Parasite种群一方面对自己种群发现的最优解区域进行开发，另一方面又可以追踪Host种群发现的最优解区域，从而能够在迭代后期定位更为优秀的最优值。
对于模拟互利共生模式的MSPSOM模型，两个种群共享各自发现的最优解信息，因此两个种群均能够以最快的收敛速度发现全局最优或次优解。

综上，通过对自然界共生现象的模拟，本章提出的多群体协同进化优化算法能够有效保持整个群体的多样性，在一定程度上平衡了算法的探索能力和开发能力，使其优化性能得到提高。



图516测试函数的收敛曲线比较图





图516(续)





图516(续)




图517Rosenbrock的协同进化过程




图518Rastrigrin的协同进化过程



5.4.5基于MSPSO的RFID网络读写器调度
1. RFID网络读写器调度问题背景

在大规模RFID应用中，在工作区域内部署多个RFID读写器，构成密集读写器网络，其拓扑结构通常如图520所示［5］。网络中每个RFID读写器分别对其识读区域内的电子标签进行读写，并将采集到的标签数据发送到中央控制系统进行处理。由于密集读写器网络要对物理环境中海量标签进行全方位覆盖(防止漏读)，某些读写器不可避免地会发生识读区域的相互重叠情况。为了便于说明，图520给出了密集读写器网络环境下的读写器冲突情况。即图520中给出了基于损耗模型的读写器电磁波分贝值，每个黑色圆周代表一个读写器的识读区域，白色圆周代表读写器发生频率干扰的区域，圆点代表相应的读写器。如果两个读写器的识读区域或者频率干扰区域发生相互重叠，就会产生读写器冲突，甚至使整个RFID系统无法正常工作。
2. RFID网络读写器调度模型

RFID网络的读写器冲突可以用图论方法描述。对于有n个读写器的RFID网络，由干扰图
G=(V,E)表示其读写器冲突。V(g)={v1,v2,…，vn}代表网络中读写器集合称作顶



图519Griewank的协同进化过程




图520RFID读写器冲突


点集合， E(g)={e1,e2,…,en}代表所有读写器之间的冲突关系称作边集。对于如图521(a)所示的RFID网络，其对应的干扰图G如图521(b)所示。为此，RFID网络的读写器冲突问题可以简化为在图G上求解图分割问题。



图521RFID读写器网络



下面面向大规模RFID网络环境下的读写器调度问题，综合考虑读写器频率冲突和网络总处理时间等要素，定义调度规则： 

(1) 在每个时隙中，始终最大化RFID读写器网络子图的读写器数量，从而尽量减少整个调度过程中的时隙总数。
(2) 尽量最小化每个时隙中RFID读写器网络子图的读写器处理时间方差，从而减少整个网络的总处理时间。
(3) 在每个时隙中尽量选择冲突关系最多的读写器，从而降低下一时隙调度的复杂性。

基于上述规则建立RFID网络读写器调度的数学优化模型如下： 



Max  f(st)=w1fα(st)+w2fβ(st)+w3fγ(st)+w4fλ(st)-ηfp(st)(517)



模型中符号含义如下： 
st——在时隙t中能够共同工作的RFID读写器网络子图，即可行解； 
fα——RFID读写器网络子图st中读写器的最大处理时间； 
fβ——RFID读写器网络子图st中的读写器数量； 
fγ——RFID读写器网络子图st中的读写器与其他读写器冲突数量和； 
fλ——RFID读写器网络子图st读写器的平均处理时间； 
fp——惩罚函数； 
w1,w2,w3,w4,η——不同子目标的权重。

3. RFID网络读写器调度模型的MSPSO算法求解

对于RFID网络优化问题，一般难以采用传统最优化方法来进行精确求解
。下面应用MSPSO优化算法来求解上面提出的RFID网络读写器调度模型。
Step1： 编码

选择区间{0,1}上的二进制编码，RFID网络读写器调度模型的编码表示为
st=(st1,st2,…,stn(t))，这里n(t)表示时隙t的RFID网络调度子图中的读写器数量。例如，可行解［0 1 0 0 1 0］，第1位值为零，表示读写器1在当前时隙t为休眠状态； 第2位值为1，表示读写器2在当前时隙为工作状态。由于不同的时隙会分配不同数量的读写器，因此在整个调度过程中，可行解的维度是动态变化的，如图522所示。



图522RFID网络读写器调度的二进制编码及其动态变化


Step2： 初始化
初始化RFID读写器网络，具体包括读写器的读写距离以及干扰范围、处理时间、网络中读写器数量。基于上述生成RFID读写器网络干扰图如图523所示。


图52330读写器的RFID读写器网络



初始化MSPSO算法种群，确定种群规模、共生进化模式、迭代次数、收敛精度、惯性权重、最小速度、最大速度和学习因子等参数。其中，粒子的维度由当前RFID网络工作读写器的数量确定。
Step3： 粒子的更新
由下式检测每个粒子适应度值大小： 


f(sti)=w1maxP(sti)+w2∑n(t)j=1stij+w3∑n(t)j=1C(stij=1)+w4∑P(sti)∑n(t)j=1stij-η∑n(t)j=1stij(518)



这里数组P(·)代表可行解中在时隙t的读写器工作数量； C(·)代表每个读写器与网络中其他读写器的冲突数量和，这里要求w1w2w3w4； η取值为1000×n(t)。

更新共生种群的速度，选择个体极值、种群极值和全局极值。这里由于RFID网络调度问题是离散问题，根据下式对粒子位置进行离散操作： 



if(rand()<S(vid))那么xid=1;而且xid=0(519)

S(vid)=11+exp(-vid)(520)



Step4： 终止准则
本书将最大迭代次数设定为终止准则。如果本次迭代后仍有读写器未完成操作，则在RFID干扰图中删除本时隙中工作的读写器子图，转到Step3； 否则，输出RFID网络读写器调度结果，包括RFID网络总处理时间、调度时隙以及每个时隙中的RFID网络子图等。

基于MSPSO其求解程序流程如图524所示。


图524基于MSPSO的RFID读写器网络调度求解流程


4. 实例研究

本节将应用MSPSO算法求解4个不同规模的RFID网络。4个RFID网络的读写器数量分别为30、60、120和200。每个读写器的处理时间随机生成并限制在［0，20］区间内，4个RFID网络的处理时间列表见表56~表59。图525给出了30个读写器网络和60个读写器网络的干扰图，受绘图软件条件限制，这里未给出其他网络的干扰图。

在应用MSPSO时，选用优化性能比较全面的互利共生算法模型。整个种群规模设置为120，即两个互助种群的大小都等于60，学习因子c1、c2和c3均取值为2.0。为了保证比较的MSPSO算法求解RFID网络读写器调度问题的性能，本节选用二进制PSO算法和GA算法进行比较分析。
表510给出了3种算法在30次试验中在满足读写器间干扰约束条件下的调度结果。图526给出了3种算法的收敛曲线。从调度结果可以看出，MSPSO算法在4个RFID读写器网络调度实例中都取得了理想的效果。与其他两种算法相比，MSPSO算法具有更快的收敛速度、更精确的调度结果和更好的鲁棒性等性能。另一方面，随着RFID网络规模的




表56读写器处理时间(30个读写器)



13.5254817.193684.6248775.6162171.2209058.0424593.6408046.41628110.840128.071299
8.8983024.0165618.9020589.3689797.28872516.8197613.9283212.779215.2992411.819877
15.4980910.311671.0817134.6268789.9424614.7393717.9277519.4495411.0481710.30737


表57读写器处理时间(60个读写器)



5.5436113.29920310.418025.1423415.46443218.0145411.8149717.9080114.1667616.72932
12.3101518.491249.6338786.32043213.945365.1405276.0974335.4995389.46038218.85579
15.5455414.4521916.0964719.013065.86472518.696192.4996714.3647715.5662418.67656
3.7778756.33470816.131141.77785714.358884.2370072.1063257.151492.48295219.24336
11.992568.97222410.204721.84897415.7828811.716239.19511815.789275.53562914.14483
7.23299619.8793118.454995.36025714.9111219.967427.5558919.2289219.0177715.84604


表58读写器处理时间(120个读写器)



13.982574.44845.9742977.93593713.6014312.9005313.6019314.7553817.592819.7617
13.93214.08622812.848482.5156565.4824415.30887110.3219215.870393.28629817.23889
5.37241717.5182113.9236315.0824213.751917.3537410.314185.7545586.14771511.66981
12.0189215.555643.164292.1588477.3881287.2124945.16059113.207799.9898314.53907
1.22609615.7694111.600813.0378415.251445.1023059.96445915.759024.03951316.17976
17.778419.2543514.8381216.4744117.299812.43907313.8669711.2412113.757599.012546
7.54501510.2654113.185831.49917815.217039.71729813.7397213.6434619.1836219.26257
17.830737.7483619.32525218.821836.13858219.599914.569074.87107219.242481.148687
17.201792.7801214.8509488.22720619.009214.350272.6758438.5392510.955311.916034
17.0136415.8477612.0934912.4028219.0176510.624428.5204992.8573669.75060819.17048
11.8973517.2826916.7492717.529214.4524819.1302310.4175518.037768.5085943.383246
2.7951329.9830642.19869611.5146711.2441217.4540115.4715417.975641.83563811.08876






表59读写器处理时间(200个读写器)



1.518843.7834189.1667116.1503215.420929.69518117.895966.62743519.5444819.41964
14.0451612.483987.27635318.3381117.150276.25650811.446416.713119.1101210.35465
10.6757215.1985819.0449115.8321318.215513.819675.2507672.9923659.5821965.045153
3.39021915.639224.13756214.1858214.786622.16009117.0331117.684814.141977.375756
14.824296.5854054.97812712.480343.85094914.207212.07014615.3208119.6465215.13217
15.1126312.145894.9968548.81810917.262914.4044968.03446719.2714817.147367.361117
6.58182810.420162.47044113.6417119.543847.2922334.69213612.644396.92722311.28651
5.54893810.558248.03974419.3277412.740119.77225616.74616.2747742.44846211.96855
8.17851211.99266.488779.2157116.4484213.158821.76764815.6686318.0309514.07118
8.6976713.941346.1366211.3878317.5491310.0815218.484718.73782.18786910.86169
12.217618.0504311.0864619.0998310.7639419.632977.2521814.6108217.3540114.44436
15.556925.4513748.89169916.850572.4854264.88924718.185037.56041811.8323815.24188
4.7016464.764264.4824322.95998915.994572.80507713.111086.02197813.2838418.4006
19.2390113.872654.68052313.320252.2461565.58643710.6937211.7854413.94368.712922
3.70008814.6995619.423343.8585917.2904617.6385916.26315.59186616.0815816.55967
1.98554712.5573615.084712.3068713.160418.4294511.638553.7941118.5071810.46088
2.95295517.2877219.1424913.5017612.719837.86555219.6908711.3302919.9530716.57186
9.57209613.677811.1862710.326918.491910.68712.49071.73917518.254818.
458165
3.4562934.7644162.80868814.110065.73613119.877467.70699715.7026915.587515.33049
12.7114618.341363.40674410.2406318.1375919.805222.44803116.402223.14801916.57516




图525RFID网络干扰图




表510RFID网络调度结果



MSPSOPSOGA

读写器数量最优值平均值标准差最优值平均值标准差最优值平均值标准差

3097.4430.800178.6330.614989.1000.7589
601213.2221.33011314.3670.80871415.2670.6397
1202120.1781.18912223.9000.95952324.8331.0199
2003836.9901.00563941.2331.35663536.8331.2888




图526算法收敛曲线


提升，PSO和GA算法的求解性能逐渐下降，而MSPSO算法性能却逐渐提高。可见这里提出的方法更具有求解大规模RFID网络调度问题的潜力。

为了更清晰地表现出RFID网络调度方法的求解过程，图527中的时间片1~12(Time Step 1~Time Step 12)给出了MSPSO算法对30个读写器RFID网络进行调度时的网络干扰图变化过程。





图527网络调度过程






图527（续）




图527（续）

5.5多种群多目标人工蜂群算法
5.5.1算法基本思想与流程

多种群多目标人工蜂群算法(MSMOABC)采用了多个蜂群来协同进化，每个蜂群内部采用原始的蜜蜂邻域搜索策略，向其随机邻居的某一维度学习。群体之间的交流是通过优秀个体替换实现的。每经过若干次迭代(由参数Tex控制)，会进行一次替换交流。对每个种群，选出一部分优秀个体和较差个体分别进入发送列表和被替换列表。对各个种群以环形的方式进行替换，用发送列表中优秀个体替换下一种群的被替换列表中的个体，以达到整体进化的目的。整个群落的拓扑结构如图528所示，每个种群将自己的优良信息传递给下一个种群，相当于一种偏利共生型合作关系。


图528MSMOABC群体拓扑结构


为用于求解多目标问题，非支配快速排序和基于拥挤距离的选择机制也加入到了算法中。对每个种群中的个体，计算其非支配等级和拥挤距离。在对个体的优劣程度进行排序时，首先按照非支配等级进行排序，等级值越低表明个体越优秀。对相同等级的个体，再按拥挤距离排序，拥挤距离大的个体优于距离较小的个体。

算法的流程如下： 




MSMOABC算法流程

(1) 初始化各个种群，T=0

(2) While终止条件不满足

(3) For each种群

根据ABC算法规则产生新的跟随蜂； 

采用非支配快速排序求取非支配解； 

计算拥挤距离； 

根据拥挤距离选择个体。

(4) End for

(5) IF Mod(T,Tex)=0

准备发送列表和被替换列表； 

将发送列表中优秀个体替代下一种群的被替换列表。

(6) End if





5.5.2算法的形式化描述

MSMOABC算法的进化模型由个体层、群体层和群落层构成。定义如下： 


MSMOABC=(Individual,Population,Colony,
Environment,Topology,Coevolution)


1. 个体层


Individual={Individual1,Individual2,…,Individuali,…,IndividualINUM}，


第i个个体表示为Individuali=<IIDi,POSIi,FITNESSi,BHVi>，它们分别表示个体i的序号、位置、适应度和行为集合。
2. 群体层


P={P1,P2,…,PM}


群体层的任一个种群可表示为Population=<OPT,PBHV,N>其中，OPT为群内最优个体； PBHV表示群内个体间行为，PBHV={CA}； N为种群大小。
3. 群落层



Col={Col1i{Col2j{Col3k{…{ColNuml}}}}}


4. 环境
Environment由优化函数定义。
5. 拓扑结构


Topology=(TS,{Aik,Pnjk})



其中，TS表示此算法静态拓扑结构； Aik表示第k个时间点个体i的邻域关系； Pnjk表示第k个时间点第n层第j个群体的邻域关系。
6. 协同进化


Coevolution={Sym}，
Sym={unitAi}=
({signa},{unitB},{signb})i


5.5.3算法性能分析
1. 测试函数


算法在ZDT1、ZDT2、ZDT3、ZDT6、DTLZ2和DTLZ6共6个基准函数上进行了测试。
1) ZDT1
ZDT1是一个有30个变量的优化问题，具有凸形帕累托前端。函数描述如表达式(521)所示。



ZDT1: 
Minimizef1(x)=x1

Minimizef2(x)=g(x)［1-x1/g(x)］

g(x)=1+9∑ni=2xi(n-1)(521)




其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0(i=2,3,…,30)。
2) ZDT2
ZDT2是一个有30个变量的优化问题。函数描述如表达式(522)所示。



ZDT2: 
Minimizef1(x)=x1

Minimizef2(x)=g(x)［1-(x1/g(x))2］

g(x)=1+9∑ni=2xi(n-1)(522)


其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0
(i=2,3,…,30)。
3) ZDT3
ZDT3是一个有30个变量的优化问题，但其帕累托前端是由一组不连续的曲线构成。函数描述如表达式(523)所示。



ZDT3: 
Minimizef1(x)=x1

Minimizef2(x)=g(x)［1-x1/g(x)-x1g(x)sin(10πx1)］

g(x)=1+9∑ni=2xi(n-1)(523)



其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0
(i=2,3,…,30)，但并非所有满足0≤x*1≤1，x*i=0的点都在帕累托前端上。
4) ZDT6
ZDT6是一个具有10个变量的多目标优化问题。然而该问题的帕累托最优前端的密度并非均匀分布。函数描述如表达式(524)所示。



ZDT6: 
Minimizef1(x)=1-exp(-4x1)sin6(6πx1)

Minimizef2(x)=g(x)［1-(f1(x)/g(x))2］

g(x)=1+9∑ni=2xi(n-1)
0.25(524)




其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0(i=2,3,…,10)。
5) DTLZ2
当取M=3时，DTLZ2测试问题的帕累托最优边界是第一象限内的单位球面，其描述如表达式(525)所示。


DTLZ2: 
Minimizef1(x)=(1+g(xM))cos(x1π/2)…cos(xM-1π/2)

Minimizef2(x)=(1+g(xM))cos(x1π/2)…sin(xM-1π/2)

︙︙

MinimizefM(x)=(1+g(xM))sin(x1π/2)

Subject to0≤xi≤1,i=1,2,…,n

Whereg(xM)=∑xi∈xM(xi-0.5)2(525)


该问的帕累托最优解为x*i=0.5 (x*i∈xM)并且所有目标函数值必须满足
∑Mm=1(f*m)2=1。和DTLZ1一样，这里取k=|xM|=10。总的决策变量n=M+k-1。
6) DTLZ6
DTLZ6测试问题具有2M-1个不连续的帕累托最优边界，其描述如式(526)所示。



DTLZ6: 

Minimizef1(x)=x1

Minimizef2(x)=x2

︙︙

MinimizefM-1(x)=xM-1

MinimizefM(x)=(1+g(xM))h(f1,f2,…,fM-1,g)

Subject to0≤xi≤1,i=1,2，…,n

Whereg(xM)=1+gxM
∑xi∈xMxi

h=M-∑M-1i=1fi1+g(1+sin(3πfi))(526)


该问题能够检测一个MOEA使最优个体在不同帕累托最优边界保持较好的分布的能力。这里函数g取k=|xM|，总决策变量数量为n=M+k-1。建议取k=20。
2. 评价指标
为了便于定量评估多目标优化算法的性能，这里给出了两种性能量度： 
(1) 解集的收敛性量度Υ。该量度测量的是MOEA算法所求出的最优解集向真实帕累托前端逼近的程度，计算式如下： 


Υ=∑Ni=1diN(527)



其中，N是一个MOEA算法获得的非支配解的数量； di是每个非支配解到真实帕累托前端的欧氏距离。为了计算该量度，设置H=10000个帕累托最优解，使这些解的目标函数值均匀分布在真实帕累托前端上。对于每个算法获得的每个解，计算该解到H的最近距离。每个算法所有解求得的平均距离被记作收敛性量度Υ。图529显示了该量度的计算过程。
(2) 解集的多样性分布量度Δ。该量度测量的是MOEA算法所求出的最优解集的分布程度，即所获得的最优解覆盖真实帕累托前端的程度。计算式如下： 


Δ=df+dl+∑N-1i=1|di-
d-|df+dl+(N-1)d-(528)



其中，di是所获得的非支配解集中连续两个解之间的欧氏距离； N是一个MOEA算法所获得的非支配解集中解的个数； d-是所有di的平均值； df和dl是理论上的极限解与所获得的解集中的边界解之间的距离，描述如图530所示。


图529收敛量度Υ




图530多样性量度Δ


3. 测试结果
多目标优化结果如表511所示。


表511多目标优化结果



测 试 函 数标准MSMOABCNSGA2（pop=100）

ZDT1

D=30

理论帕累托前端是当g=1时，
参数： 

收敛性

越小越好


平均值8.5264e-0042.2278e-001
中值8.3455e-0041.4410e-001
最优值7.5656e-0047.2072e-002
最差值1.0510e-0038.7348e-001
标准差8.0445e-0052.3806e-001


多样性

越小越好


平均值6.1502e-0015.9362e-001
中值6.0783e-0015.2694e-001
最优值5.3456e-0014.5810e-001
最差值6.7678e-0019.1451e-001
标准差4.4416e-0021.5649e-001


续表



测 试 函 数标准MSMOABCNSGA2（pop=100）

ZDT2

D=30

理论帕累托前端是当g=1时，
参数： 
NSGA5容易收敛于一点

收敛性

越小越好


平均值8.2512e-0022.9476e-001
中值8.3727e-0041.8105e-001
最优值6.2466e-0041.0668e-001
最差值4.7223e-0019.8218e-001
标准差1.4789e-0012.6288e-001


多样性

越小越好


平均值6.7809e-0017.6302e-001
中值6.7379e-0017.2999e-001
最优值6.1118e-0014.6617e-001
最差值7.5581e-0011.0542e+000
标准差4.4541e-0022.3567e-001


ZDT3

D=30

理论帕累托前端是当g=1时，
参数： 

收敛性

越小越好


平均值4.0779e-0032.1662e-001
中值4.0750e-0031.5563e-001
最优值3.5541e-0037.9710e-002
最差值4.7440e-0036.3936e-001
标准差3.2377e-0041.7221e-001


多样性

越小越好


平均值6.3788e-0017.0351e-001
中值6.4409e-0016.9255e-001
最优值5.5876e-0016.5156e-001
最差值6.7171e-0018.1501e-001
标准差3.3904e-0024.6110e-002


ZDT6

D=10

理论帕累托前端是当g=1时，
参数： 

收敛性

越小越好


平均值5.0334e-0013.3642e+000
中值1.0989e-0023.9688e+000
最优值9.6425e-0046.9186e-001
最差值1.7650e+0004.7179e+000
标准差7.4049e-0011.4822e+000


多样性

越小越好


平均值7.9631e-0011.1219e+000
中值7.6843e-0011.1187e+000
最优值6.0809e-0011.0231e+000
最差值1.1885e+0001.2849e+000
标准差1.9418e-0018.8914e-002


DTLZ2

收敛性

越小越好


平均值2.8571e-0038.7363e-002
中值2.8582e-0038.9419e-002
最优值2.5627e-0036.0319e-002
最差值3.1086e-0031.1310e-001
标准差1.5407e-0041.6418e-002


多样性

越小越好


平均值4.3011e-0014.0903e-001
中值4.2726e-0014.0881e-001
最优值3.9502e-0013.7879e-001
最差值4.6634e-0014.3358e-001
标准差2.2715e-0021.8498e-002

续表



测 试 函 数标准MSMOABCNSGA2（pop=100）

DTLZ6

收敛性

越小越好


平均值1.5498e-0026.6160e-001
中值1.5033e-0022.8640e-001
最优值1.2131e-0021.6724e-001
最差值2.0374e-0023.1497e+000
标准差2.6337e-0039.2366e-001


多样性

越小越好


平均值5.2003e-0015.7305e-001
中值5.1893e-0015.5839e-001
最优值4.6557e-0014.5813e-001
最差值5.9150e-0017.0776e-001
标准差3.7954e-0027.2624e-002


由表511和图531~图533可以看出，在收敛性指标上，MSMOABC在6个测试函数上均要优于NSGA2算法； 在分布性指标上，除在ZDT1和DTLZ2上略差于NSGA2外，其他均比NSGA2好。



图531优化结果








图531(续)





图532DTLZ2真实帕累托前端





图533DTLZ6真实帕累托前端


5.6基于p最优性准则的多种群多目标优化算法
5.6.1算法基本思想与流程

基于p最优性准则的多种群多目标优化算法(pMSMOEA)是一类应用p最优性准则和多种群策略的多目标进化算法的总称，包括基于p最优性准则的多种群非支配排序基因算法Ⅱ(pMSNSGAⅡ)、基于p最优性准则的多种群多目标差分进化算法(pMSMODE)和基于p最优性准则的多种群多目标分解算法(pMSMOEA/D)，以下说明以pMSNSGAⅡ算法为例。p最优性标准用于进化过程中的选择算子，通过一个最优函数pfunction来确定位于相同非支配等级的解决方案中最可行的解决方案。


pfunction(a)=∑ki=11-Pi(a)p1p



其中，Pi(a)是个体a在第i个目标函数上优于其他个体的概率。

同时，在多群策略中设计了子种群间的竞争与合作机制，采用了多个子种群来协同进化，每个子种群内部采用相应的原始多目标进化算法搜索策略。种群之间的交流是通过优秀个体替换实现的。每经过若干次迭代(由一参数SMCN控制)，会进行一次替换交流。对每个子种群，选出一部分优秀个体和较差个体分别进入发送列表和被替换列表。对各个子种群以环形的方式进行替换，用发送列表中优秀个体替换下一子种群的被替换列表中的个体，以达到整体进化的目的。整个群落的拓扑结构如图534所示，每个子种群将自己的优良信息传递给下一个子种群，相当于一种偏利共生型合作关系。最后，经过SMCN×EN次迭代，所有子种群融合为一个种群。


图534pMSMOEA群体拓扑结构


算法流程图如下： 




pMSNSGAⅡ算法流程


1: 设置子种群个数(m)，每个子种群大小(N)，p值上下界(plb,pub)，最大迭代次数(MCN)，子种群交换迭代数(SMCN)，种群间交换次数(EN)

2:循环

3: 初始化子种群S1,S2,…,Sm,为每个子种群分配p1,p2,…,pm

4: 循环

5: 初始化的个体按照非支配方法排序

6: 对于每个子种群Stj

应用基于p最优性准则的选择算子来选择优良个体

应用交叉和变异算子

生成后代子种群St'j 

对Stj和St'j应用非支配排序和拥挤距离生成下一父代子种群St+1j

如果mod(I,SMCN)=0

m个子种群进行种群交换

结束条件

7:结束循环

8:迭代次数为 SMCN*EN 结束循环

9:子种群融合为一个种群并且应用非支配排序

10: 迭代次数为MCN结束循环




5.6.2算法的形式化描述
pMSNSGAⅡ算法的进化模型由个体层、群体层和群落层构成。定义如下： 





pMSNSGAII=(Individual,Population,Colony,Environment,Topology,Coevolution)




1. 个体层


Individual={Individual1,Individual2,…,Individuali,…,IndividualINUM}



第i个个体表示为Individuali=<IIDi,POSIi,FITNESSi，BHVi>，它们分别表示个体i的序号、位置、适应度和行为集合。
2. 群体层


P={P1,P2,…,PM}



群体层的任一个种群可表示为Population=<OPT,PBHV,N>其中，OPT为群内最优个体； PBHV表示群内个体间行为，PBHV={CA}； N为种群大小。
3. 群落层


Col={Col1i{Col2j{Col3k{…{ColNuml}}}}}


4. 环境
Environment由优化函数定义。
5. 拓扑结构


Topology=(TS,{Aik,Pnjk})



其中，TS表示此算法静态拓扑结构； Aik： 表示第k个时间点个体i的邻域关系； Pnjk表示第k个时间点第n层第j个群体的邻域关系。

6. 协同进化


Coevolution={Sym}，
Sym={unitAi}=({signa},{unitB},{signb})i


5.6.3算法性能分析
1. 测试函数


算法在SCH2、ZDT3、ZDT4、ZDT6、DTLZ2和DTLZ3共6个基准函数上进行了测试。
1) SCH2
SCH2是一个有1个变量的优化问题。函数描述如表达式(529)所示。


SCH2： 
Minimize f1(x)=-x,x≤1

x-2,1<x≤3

4-x,3<x≤4

x-4,x>4

Minimize f2(x)=(x-5)2
(529)


其中所有变量都在［-5,10］区间内。

2) ZDT3
ZDT3是一个有30个变量的优化问题，但其帕累托前端是由一组不连续的曲线构成的。函数描述如表达式(530)所示。


ZDT3: 
Minimizef1(x)=x1

Minimizef2(x)=g(x)1-x1/g(x)-x1g(x)sin(10πx1)


g(x)=1+9∑ni=2xi(n-1)(530)



其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0（i=2,3,…,30），但并非所有满足0≤x*1≤1，x*i=0的点都在帕累托前端上。
3) ZDT4
ZDT4是一个有10个变量的优化问题。函数描述如表达式(531)所示。


ZDT4： 
Minimizef1(x)=x1

Minimizef2(x)=g(x)1-f1(x)g(x)

g(x)=91+∑10i=2(x2i-10cos(4πxi))
(531)


其中第一个变量在［0,1］区间内，剩余变量在［-5，5］区间内。

4) ZDT6
ZDT6是一个具有10个变量的多目标优化问题。然而该问题的帕累托最优前端的密度并非均匀分布。函数描述如表达式(532)所示。


ZDT6：  
Minimizef1(x)=1-exp(-4x1)sin6(6πx1)

Minimizef2(x)=g(x)［1-(f1(x)/g(x))2］

g(x)=1+9∑ni=2xi(n-1)0.25(532)



其中所有变量都在［0,1］区间内。帕累托最优解为： 0≤x*1≤1并且x*i=0（i=2,3,…,10）。
5) DTLZ2
当取M=3时，DTLZ2测试问题的帕累托最优边界是第一象限内的单位球面，其描述如表达式(533)所示。



DTLZ2: 

Minimizef1(x)=(1+g(xM))cos(x1π/2)…cos(xM-1π/2)

Minimizef2(x)=(1+g(xM))cos(x1π/2)…sin(xM-1π/2)

︙︙

MinimizefM(x)=(1+g(xM))sin(x1π/2)

Subject to0≤xi≤1,i=1,2，…,n

Whereg(xM)=∑xi∈xM(xi-0.5)2(533)


该问题的帕累托最优解为x*i=0.5 (x*i∈xM)并且所有目标函数值必须满足
∑Mm=1(f*m)2=1。和DTLZ1一样，这里取k=|xM|=10。总的决策变量n=M+k-1。
6) DTLZ3
DTLZ3测试问题具有球形的帕累托最优边界，其描述如表达式(534)所示。



DTLZ3:

Minimizef1(x)=(1+g(xM))cos(x1π/2)…cos(xM-1π/2)

Minimizef2(x)=(1+g(xM))cos(x1π/2)…sin(xM-1π/2)

︙︙

MinimizefM(x)=(1+g(xM))sin(x1π/2)

Subject to0≤xi≤1,i=1,2,…,n

whereg(xM)=100|xM|+∑
xi∈xM(xi-0.5)2-cos(20π(xi-0.5))(534)



其中k=|xM|，总决策变量数量为n=M+k-1。建议取k=10。

2. 评价指标

为了便于定量评估多目标优化算法的性能，这里给出了两种性能量度： 
(1) 解集的收敛性量度Υj。该量度测量的是MOEA算法所求出的最优解集向真实帕累托前端逼近的程度，计算式如式(535)所示： 


Υ=∑Ni=1diN
(535)



其中，N是一个MOEA算法获得的非支配解的数量； di
是每个非支配解到真实帕累托前端的欧式距离。为了计算该量度，设置H=10000个帕累托最优解，使这些解的目标函数值均匀分布在真实帕累托前端上。对于每个算法获得的每个解，计算该解到H的最近距离。每个算法所有解求得的平均距离被记作收敛性量度Υ。图535所示显示了该量度的计算过程。
(2) 解集的多样性分布量度Δ。该量度测量的是MOEA算法所求出的最优解集的分布程度，即所获得的最优解覆盖真实帕累托前端的程度。计算式如下： 


Δ=df+dl+∑
N-1i=1|di-|

df+dl+(N-1)
(534)


其中，di
是所获得的非支配解集中连续两个解之间的欧氏距离； N是一个MOEA算法所获得的非支配解集中解的个数。
是所有di
的平均值。df
和dl
是理论上的极限解与所获得的解集中的边界解之间的距离，描述如图536所示。


图535收敛量度Υ




图536多样性量度Δ



3. 测试结果
多目标测试结果如表512所示。


表512多目标优化结果



测试

函数标准p
MSNSGAⅡp
MSMODEp
MSMOEA/DNSGAⅡMODEMOEA/D

SCH2

D=1


收敛性

越小越好


平均值5.01e-068.73e-057.59e-044.01e-043.54e-038.19e-03
最优值3.93e-061.20e-067.05e-043.78e-043.35e-037.29e-03
最差值2.04e-051.72e-048.03e-047.80e-043.83e-039.96e-03
标准差2.10e-061.61e-053.99e-051.10e-051.98e-045.29e-04


多样性

越小越好


平均值6.81e-025.19e-027.73e-026.48e-027.21e-028.59e-02
最优值3.06e-024.93e-027.01e-024.09e-026.62e-027.25e-02
最差值8.62e-026.48e-021.13e-011.16e-011.19e-011.31e-01
标准差5.59e-034.95e-032.57e-031.27e-035.50e-037.60e-03


ZDT3

D=30


收敛性

越小越好


平均值8.59e-052.51e-054.15e-042.03e-021.76e-028.62e-03
最优值5.37e-052.04e-053.96e-041.09e-025.51e-037.40e-03
最差值1.28e-042.86e-044.34e-042.26e-022.05e-023.05e-02
标准差3.00e-054.92e-041.59e-055.71e-027.85e-036.30e-02


多样性

越小越好


平均值4.62e-026.24e-027.69e-025.21e-027.73e-028.45e-02
最优值3.79e-025.65e-025.65e-024.63e-025.85e-026.55e-02
最差值6.40e-026.52e-021.28e-016.59e-029.82e-021.32e-01
标准差2.49e-032.31e-031.42e-023.85e-037.42e-031.80e-02

续表



测试

函数标准p
MSNSGAⅡp
MSMODEp
MSMOEA/DNSGAⅡMODEMOEA/D

ZDT4

D=30


收敛性

越小越好


平均值1.04e-022.61e-034.77e-033.69e-021.64e-024.78e-02
最优值1.01e-021.12e-031.62e-032.40e-021.97e-033.01e-02
最差值1.14e-027.51e-039.41e-031.21e-017.68e-029.93e-02
标准差5.78e-041.14e-021.56e-021.44e-022.05e-022.41e-02


多样性

越小越好


平均值6.63e-027.02e-029.81e-028.93e-029.08e-021.00e-01
最优值6.13e-024.90e-027.05e-026.32e-029.05e-028.24e-02
最差值7.91e-029.87e-021.19e-011.09e-011.68e-011.18e-01
标准差7.36e-038.87e-036.78e-031.12e-021.64e-016.89e-03


ZDT6

D=10


收敛性

越小越好


平均值2.95e-052.89e-044.30e-046.98e-023.71e-025.48e-02
最优值2.39e-052.71e-053.21e-045.31e-022.72e-035.09e-02
最差值3.87e-056.45e-046.74e-047.72e-027.37e-027.01e-02
标准差6.08e-061.10e-057.63e-056.52e-032.17e-026.45e-03


多样性

越小越好


平均值6.37e-025.68e-028.14e-028.35e-019.99e-018.96e-01
最优值5.87e-024.08e-026.76e-026.12e-019.31e-016.19e-01
最差值7.51e-027.32e-021.01e-011.12e+001.24e+001.16e+00
标准差1.26e-034.03e-032.06e-031.08e-011.91e-021.87e-01


DTLZ2


收敛性

越小越好


平均值2.96e-031.96e-044.06e-044.15e-021.79e-035.51e-03
最优值2.88e-032.30e-056.80e-053.05e-027.50e-041.58e-03
最差值3.02e-037.13e-045.67e-036.51e-027.97e-026.27e-02
标准差6.30e-048.48e-055.87e-048.10e-032.11e-021.01e-02


多样性

越小越好


平均值4.46e-024.21e-024.76e-025.07e-014.77e-015.39e-01
最优值3.37e-023.75e-022.16e-023.85e-014.23e-012.88e-01
最差值4.60e-024.64e-027.61e-026.73e-014.92e-019.98e-01
标准差1.97e-031.88e-037.12e-035.32e-027.81e-021.29e-01



DTLZ3


收敛性

越小越好


平均值3.92e-024.70e-021.84e-011.21e-013.72e-013.60e-01
最优值3.48e-021.86e-036.73e-025.08e-021.53e-011.78e-01
最差值4.10e-021.05e-018.26e-016.56e-011.08e+001.02e+00
标准差2.55e-011.23e-011.24+008.65e-012.38e+002.6+00


多样性

越小越好


平均值5.87e-023.75e-028.00e-029.42e-024.16e-028.02e-02
最优值4.21e-023.49e-022.70e-024.54e-023.61e-023.45e-02
最差值6.97e-024.67e-021.21e-011.24e-014.81e-021.27e-01
标准差7.35e-032.62e-031.52e-022.07e-022.81e-032.06e-02


可以看出，在收敛性和分布性指标上，pMSNSGAⅡ、pMSMODE和pMSMOEA/D在6个测试函数上均分别优于NSGAⅡ、MODE和MOEA/D算法，如图537~图543所示。





图537SCH2优化结果







图538ZDT3优化结果







图539ZDT4优化结果







图540ZDT6优化结果







图541DTLZ2优化结果







图542DTLZ3优化结果




图543DTLZ2、DTLZ3真实帕累托前端

参 考 文 献


［1］李振基.生态学［M］.北京： 科学出版社，2000.

［2］Janzen D H.When is it coevolution?［J］.Evolution，1980，34： 611612.

［3］尚玉昌.行为生态学［M］.北京： 北京大学出版社，1998.

［4］Douglas A E.Symbiotic Interactions［M］.Oxford：  Oxford University Press，1994.

［5］陈瀚宁.RFID系统优化模型与智能算法研究［D］.沈阳：  中国科学院沈阳自动化研究所，2009.

［6］牛奔.基于生物行为的群体智能优化方法研究［D］.沈阳：  中国科学院沈阳自动化研究所，2008.

［7］Hillis W D.Coevolving parasites improve simulated evolution as an optimization procedure［J］.Physica D，1990，42(13)： 228234.

［8］Angeline P J，Pollack J B.Competitive Environments Evolve Better Solutions for Complex Tasks［C］//Proceedings of the 5th International Conference on Genetic Algorithms.Illinois：  Springer，1993.

［9］Paredis J.Coevolutionary computation［J］.Artificial life，1995，2(4)：  355375.


［10］Paredis J.Coevolutionary lifetime learning［C］//International Conference on Parallel Problem Solving from Nature.Berlin：  Springer，1996：  7280.

［11］Rosin C D，Belew R K.New methods for competitive coevolution［J］.Evolutionary computation，1997，5(1)：  129.

［12］Potter M A，De Jong K A.A cooperative coevolutionary approach to function optimization［C］//International Conference on Parallel Problem Solving from Nature.Berlin：  Springer，1994：  249257.

［13］Potter M A，Jong K A D.Cooperative coevolution：  An architecture for evolving coadapted subcomponents［J］.Evolutionary computation，2000，8(1)：  129.

［14］刘静.协同进化算法及其应用研究［D］.西安：  西安电子科技大学，2004.

［15］郭圆平.动态种群规模的协同进化算法模型，理论与应用［D］.合肥：  中国科学技术大学，2008.

［16］郑浩然，基于生态特征的进化与协同研究［D］.合肥：  中国科学技术大学，2000．

［17］Cao X B，Li J L，Wang X F.Research on coevolutionary optimization based on ecological cooperation［J］.Journal of software.200l，12(4)，521528.

［18］曹先彬，高隽，王煦法.基于生态竞争模型的遗传强化学习［J］.软件学报，1999(06)： 99103.

［19］曹先彬，罗文坚，王煦法.基于生态种群竞争模型的协同进化［J］.软件学报，2001(04)： 8490.

［20］Chen H，Zhu Y，Hu K，et al.Dynamic RFID network optimization using a selfadaptive bacterial foraging algorithm［J］.International Journal of Artificial Intelligence，2011，7(11)：  219231.

［21］Chen H，Zhu Y，Hu K，et al.RFID network planning using a multiswarm optimizer［J］.Journal of Network and Computer Applications，2011，34(3)：  888901.

［22］Chen H，Zhu Y，Hu K.Discrete and continuous optimization based on multiswarm coevolution［J］.Natural Computing，2010，9(3)：  659682.

［23］金莉，朱云龙，申海.三级物流网络选址路径问题建模与求解算法研究［J］.控制与决策，2010 (8)：  11951200.

［24］常春光，朱云龙，胡琨元，等.基于人工免疫算法的精铜板带加工配料优化［J］.控制与决策，2010 (7)：  10931097.

［25］Shen H，Jin L，Zhu Y，et al.Hybridization of particle swarm optimization with the KMeans algorithm for clustering analysis［C］//2010 IEEE Fifth International Conference on BioInspired Computing：  Theories and Applications.IEEE，2010：  531535.

［26］Shen H，Zhu Y，Jin L，et al.Twophase heuristic for capacitated vehicle routing problem［C］//2010 Second World Congress on Nature and Biologically Inspired Computing.IEEE，2010：  534539.

［27］Ma J，Zhu Y，Shi G.Immune genetic algorithm for flexible jobshop scheduling problem［C］//2010 IEEE International Conference on Automation and Logistics.IEEE，2010：  486489.

［28］Chunguang C，Yunlong Z，Kunyuan H，et al.Selective Purchasing Optimization of Raw Materials for Refined Copper Strip by BFO Algorithm［C］//2010 International Conference on Digital Manufacturing & Automation.IEEE，2010，2：  337340.

［29］Chunguang C，Yunlong Z，Kunyuan H，et al.Research on smelting ingredient diluting for refined copper strip by bacteria foraging optimization algorithm［C］//2010 International Conference on Digital Manufacturing & Automation.IEEE，2010，2：  275278.

［30］Chang C，Zhu Y，Hu K，et al.Optimization of grouping batch and sorting order for smelting charges in refined copper strip producing by AIA［C］//2010 IEEE International Conference on Progress in Informatics and Computing.IEEE，2010，1：  4043.

［31］Yan X，Zhu Y，Sui X，et al.Research of manufacturing enterprise information system integration based on extended ESB［C］//International Conference on Applied Informatics and Communication.Springer，Berlin，Heidelberg，2011：  4148.

［32］Zou W，Zhu Y，Chen H，et al.Artificial bee colony algorithm based on von neumann topology structure［C］//The Third International Conference on Computer and Electrical Engineering.2012，53.

［33］Zou W，Zhu Y，Chen H，et al.Cooperative approaches to artificial bee colony algorithm［C］//2010 International Conference on Computer Application and System Modeling (ICCASM 2010).IEEE，2010，9：  944948.

［34］Ma J，Zhu Y L Shi G，et al.An Adaptive Immune Genetic Algorithm and Its Application for FJSP［C］//Proceedings of the 4th International Conference on Intelligent Information Technology Application.

［35］Ma J，Zhu Y，Shi G.Immune genetic algorithm for flexible jobshop scheduling problem［C］//International Technology & Innovation Conference.IEEE，2010.

［36］Ma J，Zhu Y，Shi G.Solving the flexible jobshop scheduling problem by immune genetic algorithm［C］//2010 3rd International Conference on Advanced Computer Theory and Engineering.IEEE，2010，4：  42154218.

［37］Kunyun Hu，Yunlong Zhu，Compound Particle Optimization Using Speciation for Multimodal Function Optimization，2009 Fifth International Conference on Natural Computation，Tianjin，China，pp.182186.

［38］Chen H N，Zhu Y L，Hu K Y.Compound Particle Optimization Using Speciation for Multimodal Function Optimization［C］//2009 Fifth International Conference on Natural Computation.Tianjin，182186.

［39］Xu J W，Jiang B，Zhu Y L，et al.Operation Model for a Class of Manufacturing/Remanufacturing System with Uncertain Demands［C］//Proceedings of International Conference of management engineering and information technology.2009：  490494.

［40］Shen H，Zhu Y，Liu T，et al.Particle swarm optimization in solving vehicle routing problem［C］//2009 Second International Conference on Intelligent Computation Technology and Automation.IEEE，2009，1：  287291.

［41］Zhou X，Zhu Y，Guo H.Research on retailerdriven revenuesharing contracts model under manufacturers competition［C］//2008 International Seminar on Business and Information Management.IEEE，2008，2：  7983.

［42］Niu B，Zhu Y，He X，et al.A multiswarm optimizer based fuzzy modeling approach for dynamic systems processing［J］.Neurocomputing，2008，71(79)：  14361448.

［43］Chen H，Zhu Y.Optimization based on symbiotic multispecies coevolution［J］.Applied Mathematics and Computation，2008，205(1)：  4760.

［44］Chen H N，Zhu Y L，Hu K Y，et al.Global optimization based on hierarchical coevolution model［C］//2008 IEEE Congress on Evolutionary Computation.Hongkong：  IEEE，2008：  14971504.

［45］Jin P，Zhu Y.Mining customer change model based on swarm intelligence［C］//International Conference on Intelligent Computing.Springer，Berlin，Heidelberg，2007：  456464.

［46］Chen H N，Zhu Y L，Hu K Y，et al.Global optimization based on hierarchical coevolution model［C］//2008 IEEE Congress on Evolutionary Computation.Hongkong：  IEEE，2008：  14971504.

［47］Hu Y，Chen H，He M，et al.MultiSwarm MultiObjective Optimizer Based onOptimality Criteria for MultiObjective Portfolio Management［J］.Mathematical Problems in Engineering，2019.