基于动态小生境集的多种群协同进化模型

臧文科;杨杰;韩秀萍

【摘 要】将常规进化计算应用到建筑设计中,直接进化操作得到的优化方案的成功率并不高,而且进化速度缓慢.基于此,提出一种基于动态小生境集的多种群协同进化模型,融合动态小生境共享和协同进化计算的优点实现创新概念设计,从而具有良好的适应性和稳定性.应用表明,该模型能提高设计作品的创新水平,激发设计人员的创作灵感.

【期刊名称】《计算机工程》 【年(卷),期】2010(036)018 【总页数】3页(P226-228)

【关键词】动态小生境集;协同进化;创新设计 【作 者】臧文科;杨杰;韩秀萍

【作者单位】山东师范大学数学科学学院,济南,250014;山东师范大学数学科学学院,济南,250014;山东师范大学数学科学学院,济南,250014 【正文语种】中 文 【中图分类】TP301 1 概述

在标准遗传算法中，遗传操作完全是随机的，虽然这种随机形式在寻优的初级阶段保持了解的多样性，但在进化后期，大量个体集中于某一极值点上，它们的后代造

成了近亲繁殖。在用遗传算法解决多峰函数的优化计算时，经常是只能找到个别最优解，甚至往往得到的是局部最优解。笔者希望优化算法能够找出全部最优解，引进小生境概念有利于实现这样的目的。

本文提出了一种基于动态小生境集的多种群协同进化设计模型，描述了这个多种群进化模型，并在创新概念设计中进行成功的应用。 2 小生境

遗传算法在解决多峰函数的优化问题中有着很大的优越性，因此在建筑、工程领域中得到了广泛的应用。但是，在很多情况下，除了最优解，也期望得到其他的优化解。这样在约束条件发生变化等许多情况下，这些解可以作为很好的选择。另外，最优解如果在实现上非常复杂或者难以实现的时候，其他的非最优但是低价的优化解就成为很有吸引力的选择。

小生境技术就是每一代个体划分成若干类，每个类中选择出若干适应度较大的个体作为一个类的优秀个体代表组成一个种群，再在种群中以及不同种群间通过杂交、变异，产生新一代个体群，同时采用预选择机制或排挤机制或分享机制完成选择操作。小生境遗传算法(Niched Genetic Algorithms,NGA)可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题[1]。

3 基于动态小生境集的协同进化模型

协同进化是近年来针对遗传算法的不足而兴起的一个研究热点，意指多个种群通过适应度的关联同时进化，最早由Ehrlich和Raven提出。这一概念在理论进化中非常重要，它被广泛定义为一种适应度基于种群密度、种群自身及相互作用种群的遗传成分的进化，特别适合于进化复杂系统的动态描述。与协同进化相比，遗传算法作为目前常用的一种优化技术，只是采用基于个体自身适应度的进化模式，而没有考虑其进化的环境和个体之间的复杂联系对个体进化的影响。正因为如此，它在

应用中表现出了易出现未成熟收敛，并且收敛的速度较慢等缺陷。现有的改进方法虽然很多，但如果仍然只是通过个体适应度来控制个体的进化，则难以获得满意效果。

本文提出的协同进化模型融合了动态小生境集共享和协同进化计算的长处。进化过程中形成的峰值就是小生境，动态利用这个峰值来分类所有个体，或者属于动态小生境，或者属于非峰值类。在动态小生境集共享模式下，小生境里单个个体的共享适应度值就是被动态小生境种群大小分割的原始适应度值。个体属于非峰值类，它的小生境数可以通过标准的小生境数来计算。实验效果已经表明，动态小生境集共享比标准共享技术更有效。

动态小生境集进化模型的动态性体现在下面几个方面：

(1)种群被动态地分成几个子种群。这一动态过程由小生境核心集推动，小生境核心本身就是动态的。在实现时，按照建筑功能的创新设计分成4个种群：底部进化群体，顶部进化群体，中心轴线进化群体和楼体轮廓线进化群体。

(2)小生境的动态性由小生境的核心部分决定，小生境的核心部分包含了问题的最佳解决方案。

(3)小生境核心部分是动态的。它依赖于所有子种群的进化过程，也决定了小生境和种群进化趋势，反之亦然。

协同进化模型能够自动定位小生境。一般来说优化解并不会平均分布，因此动态模型通过消除那些没有优化解的区域能够极大地缩减计算时间。通过这项技术，能以相对小的计算复杂性找到所有可能优化解。

子种群间有2种类型的通信：通过小生境核心集的共享通信和直接数据共享。本文只需应用第1种通信。但是，在其他问题下，直接数据共享会更有效。能共享参数例如小生境半径信息、权值，这些信息在其他小生境已被证实是非常有效的，这可以加速整个子种群的进化过程。

动态小生境集协同进化模型结构如图1所示。 图1 基于动态小生境集的多种群协同进化模型 4 模型在建筑创新设计中的应用

创新设计技术研究是近几年先进制造与自动化技术领域的一大热点问题。实现创新的关键阶段是设计早期的概念设计过程。关于创新设计、概念设计技术的研究还处于初级阶段。本文在研究进化计算的基础上，将基于动态小生境集的协同进化模型应用到建筑设计过程中的概念设计和创新思维上，取得了良好的效果[2]。为了将协同进化模型应用于自生长的楼体设计，需要构造基因型的种群，使用改进的动态小生境集模型。假设目标函数有一些可估量的峰值，所有的峰值彼此都有一个最小距离。现在详细描述这个模型。

动态小生境集模型的关键问题在于确定形成小生境的峰值，把所有个体分类成小生境。现在定义个体的适应值。假设P是含有个体ξi的种群，i是个体索引。种群被分成多个小生境，j是小生境索引。假设 nj是小生境 j的种群大小，f(ξi ) 是最初适应度。假设 ξi,ξj是 2个个体，这 2个个体的染色体编码分别是 ξi (t0,t1,… ,t n )及 ξj (s0,s1,… ,sm)。不失一般性，设n＞m，对 ξi,ξj 编码重新修正，设Si=0(m +1 ≤i≤ n)，定义它们之间的距离为染色体编码的欧氏距离：

定义个体xi的小生境共享面积为：

其中，σ0是小生境半径，函数sha(t)在[0,1]范围内是严格递减的：

φ(t)在[0,1]范围内是严格递增的。例如，能选择：

现在定义：

然后定义i的动态适应值：

这是一个变化的适应度值。如果一个个体跟存在的最佳个体相似，那么它的适应度值就要减少。否则，保持不变。在这种方式下，能通过动态小生境集技术定位所有可能的最佳个体。这一过程是动态的，因为小生境在协同进化过程中也是动态的。 为了用小生境信息来进化种群，把种群分为几个子种群。所有子种群独立进化，进化过程中暂不允许子种群间的个体交换。无论何时当子种群中发现成功优化的解时，将该解放到小生境核心，然后初始化各子种群，重新开始进化过程。如果一个个体处于小生境核心解的半径a内，按照式(6)重新计算它的适应度，继续这个过程，直到发现新的优化解并加入到小生境核心，否则满足预定义的终止条件为止[3]。 用Ω表示小生境核心。为了获得不同的解，要求小生境尽可能得小。因此，定义σ0为小生境半径的最小值。这样对于某一解ς来说，利用下式计算动态小生境半径：

通过这一动态小生境技术，在一个小生境里仅能找到一个解，这能保证不会在极端狭小的范围里寻找最优解。最小化小生境半径大小能通过σ0进行预设；但是它强烈依赖于问题的编码规模。另一方面，如果预先定义了小生境半径距离，那么所有的大小定义就会被实际的解分布所影响。 5 遗传操作

系统对每个子群体采用标准遗传算法SGA的算法流程，针对实数编码的特点，选择算术交叉和随机变异的方式进行遗传操作。协同进化算法的主旨是多个种群同时进化，并且当所有种群都收敛到最优目标时整个算法停止。下面介绍本文提出的遗传算子。

5.1 交叉算子

由于模型基因型具有不同的长度，采用多点交叉算法，设有2个不同个体,ξ1,ξ2，染色体如下：

设K ＜min{}，选择交叉点，这样2个个体的染色体被分成K+1段。交叉子个体由2个父个体交换相应的基因段生成。为了保持正确的染色体信息，只将相应的偶数段基因采用算术交叉操作，如图2所示。 图2 四点交叉算子

设2个父个体ξ1,ξ2某一偶数段基因位，交叉之后基因位变为 5.2 变异算子

系统采用的是标准变异算子。为保持种群多样性，同时不至于使种群大小增加太快，在进化过程中每隔一定代数，随机生成一些新个体添加到种群中。这些新个体将参加到下一代遗传操作[4]。 5.3 选择算子

系统采用线性排序选择策略。设某一时间种群按照适应度大小排序如下：

令 η+∈ (1,2]是最大期望概率，则选择概率为：

同时采用排挤机制的选择策略，保留精英个体，这样在进化过程中始终保持已有的最优个体，使得算法最终收敛。基本思想源于在自然界中，当某一种群中的个体大量繁殖生存时，为争夺有限的生存资源，群体中个体之间的竞争压力必然加剧，因此，个体的寿命和出生率也会降低。基于这种机制，使用“排挤算子”，即新生成的子代将替代或排挤相似的旧父代个体。该方法可有效提高群体的多样性。使用排挤算子CF(一般取 CF=2或 3 )做试验，CF规定了候选解被后代取代的个体数目。

个体之间的相似性可用个体编码串之间的海明距离来度量。排挤方法可描述如下：(1)设定参数CF；(2)从群体中随机挑选CF个个体组成个体集(新的个体不包括在内)；(3)从该个体集中淘汰一个个体，该个体与新个体的海明距离最短。 个体i的适应度采用变化值：

其中，fi代表个体i的适应度； Nj代表个体j所属的类j的个体总数。这样在一个小生境中的每个个体的共享函数都等于该小生境的个体总数，因此，在未调整之前适应度大的个体调整之后适应度仍然高于其他的个体。对于那些不属于任何小生境的个体，适应度调整为。择偶限制也非常容易实现，就是允许同一个小生境中的个体可以交叉，同时精英保留策略扩展为保留每个小生境的最优个体[5]。 5.4 进化结果

模型基于ACIS和VC++进行了实现。在设计过程中，根据建筑功能，基于动态小生境集将种群动态地划分成4个子群体。图3和图4是其中的底部子群体和顶部子群体的初始模型。通过子群体内部动态小生境集间的交叉变异和不同子群间小生境的遗传操作，保持了解的多样性，使得最终建筑获得很好的创新性。进化后的建筑效果如图5所示。 图3 底部模型 图4 顶部模型

图5 进化后的建筑效果实例(顶部挖空) 6 结束语

本文从进化计算出发，提出了基于动态小生境集的多种群协同进化创新概念设计模型，并进行了实现。试验和用户数据显示了这个模型的适应性和稳定性。而且，这种协同进化技术在概念形体设计过程中有着潜在的广阔的应用领域。多种群协同进化虽然是创新概念设计的有效手段，但目前关于多种群协同进化算法仍然存在理论

体系不够完善、实现方法不太成熟等问题。本文的多种群协同进化模型没有考虑到多工作站情况，下一步考虑将多种群协同进化拓展到多台工作站，实现分布式并行进化。 参考文献

[1] 刘希玉, 王文平, 刘 弘, 等.动态小生境微粒群优化技术在概念设计中的应用[J].计算机科学, 2006, 33(10): 163-169.

[2] 陈云峰, 段成华.自适应小生境遗传算法在系统级综合中的应用[J].计算机工程, 2008, 34(8): 221-223.

[3] 肖宏峰, 谭冠政.基于单纯形的小生境混合遗传算法[J].小型微型计算机系统, 2008, 29(9): 1719-1725.

[4] 席红雷, 行小帅, 张清泉.基于梯度优化的自适应小生境遗传算法[J].计算机工程, 2008, 34(11): 186-188.

[5] 林毅申, 彭 宏, 韦 佳.小生境基因表达式编程在函数发现的研究[J].小型微型计算机系统, 2008, 29(11): 2111-2114.