演化算法

演化算法（精选七篇）

演化算法 篇1

集合划分问题是组合优化领域中一个典型的NP难问题,它是指把m个正数组成的集合A划分成n个互不相交的子集A1、A2、…An,要求这些子集中的各元素之和S1、S2、…Sn中的最大者尽可能的小。由于它是许多实际问题的抽象,如存储分配问题、多处理机调度问题、财产分配问题等,因而得到了广泛的应用。目前对该问题的求解主要有粒子群优化算法[1]、蚁群算法[2]、遗传算法[3]等。本文采用差异演化算法来求解集合划分问题,并与文献[1]中求解结果进行比较。

1 集合划分问题模型

已知A的第i个元素为ai(i=1,2,…,m),若元素ai被分配到子集合j中,则令xij=1,否则。表示子集合j的元素和,表示元素ai只能分配到一个子集合中,其数学模型如下:

2 差异演化算法

差异演化算法[4](Differential Evolution,DE)是Rainer Storn和Kenneth Prince提出的一种基于群体差异的演化算法。差异演化算法具有收敛速度快、操作简单、易编程实现、极强的稳健性等优点,在首届IEEE演化计算大赛中,差异演化算法表现超群,随后在各领域得到了广泛的应用。差异演化算法的整体结构类似于遗传算法,与遗传算法的主要区别在变异操作上,差异演化算法的变异操作是基于染色体的差异向量进行的,其余操作和遗传算法类似。下面通过求解非线性函数f xΣ1,x2,…,xnΣ的最小值问题,xj满足,j=1,2,…,n,来介绍差异演化算法的操作过程:

令xi(t)是第t代的第i个染色体则xi(t)=xΣi1(t),xi2(t),…,xin(t)Σ,i=1,2,…,M;t=1,2,…,tmax。其中,n是染色体的长度,即变量的个数,M为群体规模,tmax是最大的进化代数。

(1)生成初始种群。在n维空间里随机产生满足约束条件的M个染色体,实施如下措施:xij(0)=randij(0,1)xΣUij-xLijΣ+xLij(2)

其中xUij与xLij分别是第j个变量上界和下界,randij(0,1)是[0,1]之间的随机小数。

(2)变异操作。从群体中随机选择3个染色体xp1,xp2,xp3且(i≠p1≠p2≠p3),则hij(t+1)=xp1j(t)+λxΣp2j(t)-xp3j(t)Σ(3)

xp2j(t+1)-xp3j(t+1)为差异化向量,λ为缩放因子。

(3)交叉操作。交叉操作是为了增加群体的多样性,具体操作如下:

randij(0,1)是在[0,1]之间的随机小数,pc为交叉概率,pc∈[0,1],rand(i)为在[1,n]之间的随机整数,这种交叉策略可确保xi(t+1)至少有一分量由hi(t+1)的相应分量贡献。

(4)选择操作。为了决定xi(t)是否成为下一代的成员,向量vi(t+1)和目标向量xi(t)对评价函数进行比较:xi(t+1)=

反复执行b.至d.操作,直至达到最大的进化代数tmax。

3 求解集合划分问题的差异演化算法

集合划分问题是非连续的离散优化问题,而上述的差异演化算法适用于连续优化问题。因此,针对集合划分问题的具体特点,本文设计了一种用差异演化算法来对其进行求解的思路。具体操作过程如下:选择初始种群的取值在区间叟-xmax,xmax叟,为了使差异演化算法可以求解离散优化问题,首先将区间分成n个相等子区间,当连续变量的取值属于某一区间时,表明该变量对应的元素放入相应的子集合内。例如设A={81,40,26,4,65,98,53,71,15},共9个数据,分成3个子集合,即m=9,n=3。令xmax=6,分成三个相等的区间[-6,-2),[-2,2),[2,6],当种群中第k个个体的第i个连续变量属于区间[-6,-2)时,元素ai被分配到子集合1中;第i个连续变量属于区间[-2,2)时,元素ai被分配到子集合2中;第i个连续变量属于区间[2,6]时,元素ai被分配到子集合3中。与函数优化问题不同的是,变量的上界xmax没有给出,需要自己设定,经过实验发现,求得问题解的好坏和收敛性对上下界的变化不敏感,本文中选取xmax为6。

4 结论

通过利用差异演化算法对集合划分问题进行求解,说明了差异演化算法应用于该类问题的可行性。由于差异演化算法的研究还处于初期,目前仍有许多问题需要进一步的研究,例如算法的收敛性、理论依据等。但从当前的应用效果来看,差异演化算法无疑具有十分光明的前景,进一步拓展差异演化算法新的应用领域仍是一项非常有意义的工作。

参考文献

[1]高尚,侯志远.集合划分问题的粒子群优化算法[J].江苏科技大学学报(自然科学版),2005,19(6):41-44.

[2]高尚,侯志远.集合划分问题的蚁群算法[J].航空计算技术,2006,36(2):720-722.

演化算法 篇2

图像修复是利用图像上待修复区域周围的已知信息对信息缺损区域进行信息填充的过程,其目的就是恢复有信息缺损的图像,并不被察觉出修复的痕迹。如果采用某些图像处理软件对受损图像进行修复处理,需要有经验的技术人员进行复杂的手工处理。当今,图像修复技术已成为计算机图形学和计算机视觉中的一个研究热点,旨在研究出精确、快速、简单的修复技术,能够轻松地修复图像。图像修复技术在文物保护、多余目标物体剔除、图像缩放、图像有损压缩等方面都有着重大的应用价值。

目前存在许多种图像修复技术,但从总体上主要可以分为两类:一类是基于非纹理结构的图像修复技术,它的主要思想是利用物理学中的热扩散方程将待修复区域周围的信息传播到待修复区域中。这种修复技术最早是由Bertalmio等人应用到图像处理中的[1],随后Chan等人通过建立图像的先验模型和数据模型提出了基于TV(全变分)模型的图像修复技术[2]。这类图像修复技术也可称之为基于变分偏微分方程PDE(Partial Differential Equation)的图像修复技术,主要用于修复小尺度破损的数字图像,且具有较好的修复效果,但当受损区域及其周围的纹理相当丰富时,就得不到很好的效果。

另一类是基于纹理结构的图像修复技术,主要用于填充图像中大块丢失的信息。这类技术效果较好、运用较多的就是基于样本的纹理合成技术。该种算法的主要思想是,从待修补区域的边界上选取一个像素点,以该点为中心,根据图像的纹理特征,选取大小合适的纹理块,然后在待修补区域的周围寻找与之最相近的纹理匹配块来替代该纹理块。Criminisi等人提出了一种基于样本的图像修复算法[3],它主要由优先级计算、搜索和复制3步组成。由于该算法在视觉效果和耗时上均优于其它算法,因此有大量的研究者开始研究Criminisi算法。宋秀敏等在计算优先权时增加多个已知像素的梯度信息来优化修复顺序[4]。中国科技大学的彭坤杨等通过引入可预计算的匹配项,代替复杂的平方差和SSD(Sum of Squared Differences)匹配计算,降低了算法的时间复杂度[5]。Nie等则对优先级函数提出了改进方法[6]。刘洋等则在Criminisi算法的基础上收缩原始图像并用阈值分割预选源区域,防止误匹配[7]。姚建亮等通过傅立叶变换将搜索空间约束到纹理方向的范围,有效地维持了图像的线性结构[8]。

但是,该修复算法仍然存在一些缺点。首先是优先权函数的置信度值迅速下降到零[9],使得优先权计算变得不可靠,从而使得修复的顺序变得不准确,影响到修复的质量。另外该算法采用在整个图像区域寻找最佳的匹配块,这种全局搜索方法相当耗时。而且在整个搜索过程中,模板窗口大小固定不变,无法随着图像局部特征的变化而变化,致使图像修复的效果不佳。因此,本文从纹理块优先权的计算、模板块大小的选取和最佳匹配块的搜索等方面改进Criminisi算法。

1 演化算法概述

演化算法(EA)[10]是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的演化原则。使用演化算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出。因为它的演化算法的整体搜索策略和优化计算不依赖于梯度信息,所以应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在函数优化、组合优化、人工智能、机器学习、规划策略、图像处理和模式识别等领域的应用中越来越展示出优越性。

演化算法简单,鲁棒性好,具有自组织性、自适应性、自学习性和本质并行的突出特点。和其他优化搜索算法相比,演化算法具有以下性质[11]:

(1) 演化算法不是直接作用在解空间上,而是利用解的某种编码表示。

(2) 演化算法从一个群体即多个点而不是一个点开始搜索,这是它能以较大的概率找到整体最优解的主要原因之一。

(3) 演化算法只使用解的适应性信息(即目标函数),并在增加收益和减小开销之间进行权衡,而传统搜索算法一般要使用导数等其它辅助信息。

(4) 演化算法使用随机转移规则而不是确定性的转移规则。

2 基于演化算法的纹理合成图像修复算法

2.1 优先权的计算

如图1所示,Φ是样本区域,Ω是目标区域,δΩ表示待修复目标区域的边界,p是边界上的一点,Ψp是以p点为中心的待修复块,Ψq是以q点为中心的匹配块。Criminisi算法的优先权定义为:

P(p)=C(p)D(p) (1)

其中,C(p)和D(p)分别称为置信度项和数据项,它们分别定义为:

$C(p)=\frac{{\displaystyle {\sum }_{q\in \Psi {}_p{\displaystyle \cap \Phi }}C}(q)}{\left|\Psi {}_p\right|}(2)$

$D(p)=\frac{\left|\nabla {\rm I}{}_p^{\perp }\cdot n{}_p\right|}{\alpha }(3)$

其中,$\left|\Psi {}_p\right|$为待修复块Ψp的面积,即像素点的个数;当q点在Φ里时,C(q)就等于1,否则就取0;α是一个归一化系数,取值为255;np为待修复区域边界δΩ上p点的法向量;ᐁI⊥p为点p的等照度线方向,一般像素点的梯度方向,就是其像素值在空域上变化最大的方向,其垂直方向即为等照度线方向,也就是说,等照度线方向是像素点的像素值在空域上变化最小的方向,其计算公式如下:

$\nabla {\rm I}{}_p^{\perp }=\frac{(-{\rm I}{}_y,{\rm I}{}_x)}{\sqrt{{\rm I}{}_x^2+{\rm I}{}_y^2}}(4)$

其中,Ix和Iy分别为像素点p在x方向和y方向上的偏微分。

然而,随着填充的进行,置信度值会迅速下降到零,这使得待修复块的选取不准确,导致错误的填充次序,进而影响到修复的效果。并且,该算法仅仅只沿着等照度线方向来修复图像,这对具有复杂特征的图像修复效果并不佳。因此,为了提高优先权计算的准确性,本文将优先权函数改进为:

P(p)=C(p)+3×D(p) (5)

其中,置信度项C(p)的定义与Criminisi算法的定义是相同的,数据项D(p)定义如下:

$D(p)=\frac{1}{\left|\nabla {\rm I}{}_p\right|}\left[\nabla \cdot \left(\frac{\nabla u}{\sqrt{\left|\nabla u\right|}}\right)\right](6)$

其中,ᐁIp是p点的梯度方向,$\nabla \cdot \left(\frac{\nabla u}{\sqrt{\left|\nabla u\right|}}\right)$是p等于3/2时的p-Laplace算子。该数据项使得待修复块的填充顺序将会顾及到等照度线方向ᐁI⊥p和垂直于等照度线方向ᐁIp这两个方向上的图像特征。式(5)中的3是一个权重值,因为数据项D(p)表现了图像各种复杂的结构信息,应在优先权函数中有较大的比重。这样设计的优先权函数既避免了置信度值迅速下降为零时对优先权计算带来的影响,又能够从ᐁI${}_p^{\perp }$和ᐁIp两个方向同时对修复的先后次序进行考虑,更准确地对受损图像进行修复。

2.2 模板窗口的大小

Criminisi算法利用默认大小的模板在整个图像区域进行搜索来寻找最佳匹配块,采用这种固定模板大小的方法没有考虑到待修复图像中有的区域纹理较为复杂,有的区域则较为平滑,对修复图像的速度和效果都造成了影响。因此,本文对模板的大小进行改进,并在不同的区域对模板的大小进行相应的调整。

因为图像的高频部分包含了图像丰富的结构信息和纹理信息,而低频部分则包含了图像中较为平滑的区域,所以在高频部分应选用较小的模板来获得图像的细节,而在低频部分则可以采用较大的模板,加快修复的速度。梯度在一定程度上可以反应频率的变化,因此,本文将模板窗口的大小改为如下定义:

$w(p)=\{\begin{array}{l}5\left|\nabla {\rm I}{}_p\right|\ge 0.3\\ 9\left|\nabla {\rm I}{}_p\right|<0.3\end{array}(7)$

其中,w(p)表示模板窗口的大小,$\left|\nabla {\rm I}{}_p\right|$是点p的梯度值。

2.3 最佳匹配块的搜索

在Criminisi算法中,确定了具有最大优先权的待修复块Ψp后,就全局搜索与之最近似的匹配块Ψq,并把Ψq中的数据复制到Ψp中,从而完成了一个待修复块的修复。Ψp与Ψq应满足如下关系:

Ψq=arg mind(Ψp,Ψq) (8)

式(8)表明Ψq是所有匹配块中与待修复块Ψp距离最近的一个匹配块。其中,d(Ψp,Ψq)表示两个像素块Ψp与Ψq之间的距离,即这两个像素块里面对应的已知像素点的像素值之间的差的平方和。

然而,该算法采用的全局搜索最佳匹配块的方式没有考虑到图像的局部相关性,它在整个图像区域进行搜索,非常耗时,并且大部分的时间都耗费在不相关的区域,导致了搜索效率的低下。因此,本文采取的改进方法是限定样本区域为待修复区域外40×40的区域,并且用演化算法来搜索最佳匹配块。像素点总是与其距离较近的区域相关程度较大,这样的限定就可以节省搜索时间,而提出用演化算法搜索匹配块,可以在保证修复效果的同时提高搜索效率。用演化算法搜索最佳匹配块的具体步骤如下:

(1) 编码方案

编码方案是应用演化算法时首要解决的问题,也是一个关键步骤。演化算法的编码方案对杂交算子和变异算子的影响较大,同时,对种群个体的多样性和算法的搜索能力也有一定的影响。

在本问题中,采用实数编码方式,将图像看作是二维笛卡尔坐标空间,而每一个染色体对应着图像中的像素点的坐标。该编码方案的优点是精度高,并且无需解码。

(2) 初始化种群

所谓初始化种群就是产生该问题的初始解,在这里将样本区域作为搜索空间。首先,在搜索空间的横坐标范围内随机生成一个N维行向量X=[X1,X2,…,XN],然后再在搜索空间的纵坐标范围内随机生成一个N维行向量Y=[Y1,Y2,…,YN]。(Xi,Yi)即表示第i个染色体,其中,Xi表示第i个染色体所对应的像素点的x坐标,Yi表示第i个染色体所对应的像素点的y坐标,Xi和Yi均为实数,初始种群initpop=[(X1,Y1),(X2,Y2),…,(XN,YN)]。N为染色体的个数,本文中N=20。

(3) 适应度函数

本文演化算法的目的是要找到与待修复块Ψp最近似的匹配块Ψq,所以本文将目标函数定义为:

minf f=d(Ψp,Ψq) (9)

其中,d(Ψp,Ψq)是两个像素块Ψp与Ψq之间的距离,d(Ψp,Ψq)的定义如下:

$d(\Psi {}_p,\Psi {}_q)={\displaystyle \sum _{i=1}^m(}V{}_{ip}-V{}_{iq}){}^2(10)$

其中,m表示待修复块Ψp中已知像素点的个数,Vip表示待修复块Ψp中第i个像素点的像素值,而Viq则表示匹配块Ψq中对应的第i个像素点的像素值。

适应度函数也称为评价函数,它是种群个体之间优劣性比较的基础,是算法演化过程的驱动力,也是进行自然选择的唯一依据。适应度函数通常是从目标函数转化而来,一般而言,在确定演化算法的适应度函数时,应保证适应度函数为最大化问题,即适应值越大越好。而本文的目标函数为最小化问题,并且目标函数值一定是非负的。因此,为了保证目标函数值越小时,适应值越大,本文将适应度函数定义为:

$S=\frac{1}{1+f}(11)$

(4) 选择策略

演化算法中通过选择算子来模拟自然界中适者生存、优胜劣汰的自然法则。选择又称复制,是建立在对个体的适应度进行评价的基础上的,目的是使生命力较强的个体以较大的概率保存下来,从而使种群以最快的速度收敛于全局最优。

本文在进行选择操作时,采用基于适应值比例的轮盘式选择和精英策略[12]相结合的方法。在进行选择之前,先求出种群中适应值最大的个体,即最佳个体。然后进行轮盘式选择,该选择方式可以保证适应值越大的个体被选择的概率也越大,但是由于是随机操作,适应值较大的个体未必都能被选择而保留下来。此时可以采用精英策略。在选择过后产生的新种群中,找出适应值最大的最佳个体和适应值最小的最差个体,将新产生的最佳个体与选择前的最佳个体进行比较,若新产生的最佳个体优于选择前的最佳个体,则用选择前的最佳个体替换掉新种群中的最差个体,否则就用选择前的最佳个体替换新产生的最佳个体。精英策略有提高收敛速度和提高解的精度的特点,而这种集成选择操作则利用精英策略的特点来克服轮盘式选择法容易遗漏精英个体和收敛速度慢的缺点。

(5) 杂交算子

杂交是指对父体对按某种方式相互交换其部分基因而形成两个新的个体。杂交在演化算法中起到了关键作用,是产生新个体的主要方法,它决定了演化算法的全局搜索能力。一般而言,不同的编码方式其杂交方式也不同。本文采用的是实数编码方式,对于实数编码,杂交方式主要包括部分离散杂交、整体离散杂交、部分算术杂交和整体算术杂交,本文采用的是部分离散杂交的方式。

设P1=(Xp1,Yp1)和P2=(Xp2,Yp2)是两个父解向量,部分离散杂交即是在父解向量中选择一个分量,然后交换该分量以形成后代。本文的具体实现是先随机产生一个小数,该小数必须大于0且小于1,然后与杂交概率相比较。若随机小数大于杂交概率,则不进行杂交,后代直接继承父代;否则在父解向量中随机选择一个分量,并交换两个父解向量的该分量的值,得到两个新的后代。如果随机选择的是第一个分量,则产生的两个后代为C1=(Xp2,Yp1)和C2=(Xp1,Yp2)。若随机选择的是第二个分量,形成的后代则为C1=(Xp1,Yp2)和C2=(Xp2,Yp1)。本文中的杂交概率pc=0.8。

(6) 变异算子

变异操作是指将父解向量中的某些基因座上的值用该基因座的其它等位基因来替换,从而形成一个新的个体。有效基因的缺损会导致算法早熟收敛,即如果只通过演化算法杂交算子的操作所产生后代的适应值较难达到最优,变异操作在一定程度上克服了这种情况的发生,有利于增加种群的多样性。在实数编码中,变异算子为主搜索算子,本文采用的是均匀性变异。

设P=(Xp,Yp)是父解向量,首先产生一个0～1之间的随机小数,然后与变异概率作比较。如果该随机小数大于变异概率,则不进行变异操作;否则在父解向量中随机选择一个分量,然后,在该分量定义区间中随机取一个实数代替该分量原有的值,以得到新的后代。若随机选择的是第一个分量,则用搜索空间横坐标范围[Xmin,Xmax]内的一个实数值Xk来代替Xp,得到的后代为C=(Xk,Yp)。如果选择的是第二个分量,就用搜索空间纵坐标范围[Ymin,Ymax]内的一个随机实数Yk来代替Yp,形成的后代是C=(Xp,Yk)。本文中的变异概率pm=0.1。

(7) 算法终止条件

一般当群体中最差个体与最好个体的适应值差的绝对值小于预先给定的充分小的数时,或者迭代次数达到最大限度时,算法终止。本文采用的迭代次数为200次,最后返回以最佳个体为中心的最佳匹配块。

(8) 算法流程图

算法流程框图如图2所示。

2.4 本文改进的修复算法

根据前几节的分析,给出本文所提改进的图像修复算法基本步骤:

1) 用户用特定颜色指定需要填充的目标区域Ω。

2) 提取目标区域的边缘,并按照优先权函数的定义计算每个以边缘上的点为中心点的待修复块的优先权,此时,每个块的大小是相同的。

3) 找到具有最大优先权的待修复块的中心点p∈δΩ,并根据其梯度信息决定块的大小,得到待修复块Ψp。然后用演化算法在样本区域寻找一个匹配块Ψq,使得d(Ψp,Ψq)为最小。最后,把Ψq中的信息复制到Ψp中。

4) 填充Ψp之后,更新优先权。具有最大优先权的待修复块填充好后,那些刚填充的像素点由目标区域变成了样本区域,置信度发生了改变,应及时更新。假设Ψp为刚刚填充好的修复块,则其像素点的置信度更新按式(12)进行:

C(p′)=C(p) ∀p′∈ψp∩Ω (12)

5) 置信度更新之后,将会得到一个新的填充边缘。如果这个边缘上的像素点不为零,重复步骤2)-4),直到目标区域全部填充修复完毕。

2.5 本文图象修复算法软件编程实现方法

function inpainting() //修复函数

{

origImg=原始图像;

fillImg=待修复图像;

fillColor=填充颜色;

while 有破损区域未被修复

boundary=待修复区域的边缘;

for k=boundary′

w=4;

Hk=以k为中心,窗口的大小为2*w+1的模板块;

置信度项C(k)= Hk中已知像素点的个数/Hk中像素点的总个数;

end

数据项D(boundary)=边界点的p-Laplace算子/其梯度值;

优先权=C(dR)+3*D(dR);

p=具有最大优先权的边界点;

if p点的梯度值>=0.3

w=2;

else

w=4;

end

Hp=以p为中心,窗口的大小为2*w+1的模板块;

Hq=ea(); //调用演化算法寻找最优匹配块

Hp(破损区域)=Hq中对应区域的已知信息;

待修复区域(Hp中原破损区域)=false;

C(Hp中原破损区域)=C(p);

end

输出修复好的图像;

}

function ea() //演化算法函数

{

最大迭代次数=200;

Pc=0.8;

Pm=0.1;

种群个数N=20;

X=在样本区域的横坐标范围内随机取20个整数;

Y=在样本区域的纵坐标范围内随机取20个整数;

Z=随机取20个大于0小于1的小数;

初始种群initpop=[X,Y,Z]′;

initpop的适应度值=fitness(); //调用适应度值函数

原最佳个体=max(initpop的适应度值);

k=1;

while k<=200

新种群newpop=selection(); //调用选择函数

交叉父体的序号排列order=随机产生的1到20的整数的无重复排列;

for i=1:2:19

父体1=newpop(order(i,:));

父体2=newpop(order(i+1,:));

[子代1,子代2]=crossover(); //调用交叉函数

newpop(order(i,:))=子代1;

newpop(order(i+1,:))=子代2;

end

for i=1:20

newpop(i,:)=mutation(); //调用变异函数

end

newpop的适应度值=fitness();

最佳个体=max(newpop(:,3));

initpop=newpop;

k=k+1;

end

m=最佳个体(1);

n=最佳个体(2);

mm=图像的长;

q=(n-1)*mm+m; //求得最佳匹配块中心点的位置

Hq=以q为中心,窗口的大小为2*w+1的模板块;

return Hq;

}

function fitness() //适应度值函数

{

q=(种群(2)-1)*图像的长+种群(1);

Hq=以q为中心,窗口的大小为2*w+1的模板块;

f=0;

for i=1:Hp中已知像素点的个数

f=f+( Hp中第i个像素点的值- Hq中第i个像素点的值)^2;

end

f=1/(1+f);

}

function selection() //选择函数

{

适应值比例prob=initpop(:,3)/适应度值的总和sum(initpop(:,3));

prob= 计算prob各行累加值得到的向量;

rand=按升序排列的值在0～1之间的20维列向量;

oldorder=1;neworder=1;

while neworder<=20

if (rand(neworder)<prob(oldorder))

选择该父体;

neworder=neworder+1;

else

oldorder=oldorder+1;

end

end

新最佳个体=max(newpop(:,3));

最差个体=min(newpop(:,3));

if新最佳个体>原最佳个体

原最佳个体=新最佳个体;

else

最差个体=原最佳个体;

end

}

function crossover() //交叉函数

{

if (随机产生的小数<Pc)

随机选择交叉点cpoint;

if cpoint=1

子代1=[父代2(1) 父代1(2:3)];

子代2=[父代1(1) 父代2(2:3)];

else

子代1=[父代1(1) 父代2(2:3)];

子代2=[父代2(1) 父代1(2:3)];

end

else

子代1=父代1;

子代2=父代2;

end

}

function mutation() //变异函数

{

if (随机产生的小数<Pm)

随机选择变异点mpoint;

子代=父代;

if mpoint =1

子代(mpoint)=样本区域横坐标范围内的一个随机实数;

else

子代(mpoint)=样本区域纵坐标范围内的一个随机实数;

end

else

子代=父代;

end

}

3 实验结果及分析

下面对Criminisi算法和本文所提出的基于演化算法的纹理合成图像修复技术进行仿真比较,所有的实验都在配置为Pentium E CPU 1.6GHz,RAM为1G的计算机上运行,仿真环境为Matlab 7.0。实验结果见图3-图6。

如图所示,本文的改进算法中的待修复区域用绿色填充。实验一的图片是一张网络上的砖块结构图,实验二的图片是一张风景相片。由图3和图4中可以看出,本文的改进算法的修复结果要明显优于Criminisi算法。在图3(c)的绿框中,Criminisi算法的对砖块的结构修复出现明显的错误,而本文算法的修复结果则没有类似错误出现。在图4(c)的绿框中,Criminisi算法的修复结果出现了误匹配,造成了非常明显的误差,而本文算法的修复结果从视觉上看更接近于原始图像,修复效果较好。

实验三和实验四是对图片上的物体进行移除并修复填充缺失信息。实验三的图片是一张经典的物体移除图片,实验四的图片是一张网络上的生活照。在图5(c)的绿框中,白色区域中间是断开的,并不连续,而本文算法则克服了这一缺点。通过对比图6(c)和图6(d)可以看出,本文算法的修复结果在视觉效果上要优于Criminisi算法的修复结果,并没有出现图6(c)绿框中的误匹配。表1给出了在同等条件下,Criminisi算法和本文改进的算法的运行时间。从表中可以看出,本文改进的算法比Criminisi算法收敛速度更快。

4 结 语

本文提出了一种基于演化算法的纹理合成图像修复技术,它在Criminisi算法的基础上,利用等照度线方向和梯度方向上的信息进行了图像修复算法改进,重新定义了优先权函数,并结合图像的特征,改进了模板窗口的大小,同时引入了基于演化算法的搜索方法。实验证明,该算法具有更快地收敛速度以及更好地修复效果。

参考文献

[1]Brttalmio M,Sapiro G,Caselles V,et al.Image inpainting[C]//Proceedings of the 27th Annual Conference on Computer Graphics andInteractive Techniques.New Orleans:ACM Press,2000:417-424.

[2]Chan T F,Shen Jianhong.Mathematical models for local non-textureinpainting[J].SIAM Journal on Applied Mathematics,2001,62(3):1019-1043.

[3]Criminisi A,Perez P,Toyama K A.Region filling and object removalby exemplar-based image inpainting[J].IEEE Transactions on ImageProcessing,2004,13(9):1200-1212.

[4]宋秀敏,尹立新,蒋海波.一种改进的基于样本块的目标移除方法[J].计算机应用与软件,2012,29(2):258-260.

[5]彭坤杨,董兰芳.一种基于图像平均灰度值的快速图像修复算法[J].中国图象图形学报,2010,15(1):50-55.

[6]Nie Dongdong,Ma Lizhuang,Xiao Shuangjiu.Similarity based imageinpainting method[C]//Proceedings of the 12th International Multi-media Modeling Conference.Beijing:IEEE Press,2006:344-347.

[7]刘洋,王昊京,田小建,等.采用区域分割的变尺寸样本块高效图像修复[J].光学精密工程,2010,18(12):2656-2664.

[8]姚建亮,彭宏京,花樱.一种改进的基于样例的图像修复方法[J].计算机应用与软件,2010,27(3):249-251.

[9]Cheng Wenhuang,Hsieh C W,Lin Shengkai,et al.Robust algorithmfor exemplar-based image inpainting[C]//Proceedings of the Interna-tional Conference on Computer Graphics,Imaging and Vision(CGIV2005).Beijing:IEEE Computer Society,2005:64-69.

[10]Holland J H.Adaptation in natural and artificial systems[M].Ann Ar-bor,USA:University of Michigan Press,1975.

[11]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

演化算法 篇3

常规的基于图像处理技术的人体检测方法不能克服人体形状和外貌多样的难点,以及不能解决人体的不同运动方式造成的人体变形问题,在实际应用中很少被采用。而基于学习的人体检测方法能够很好地解决上述问题,支持向量机(SVM)作为一种对于小样本数据有良好学习性能的机器学习方法,已经被用于网页识别、人脸识别、行人检测等许多方面[2]。由于行人检测可以看成是一个二分类问题[3],因此主要考虑SVM模型的分类问题。因此,本文提出一种算法对视频中移动摄像头下的行人检测问题进行了研究,在Ada Boost行人分类算法、支持向量机(SVM) 理论和多目标优化原理的基础之上,并结合三者的特点,提出了一种基于量子演化算法的行人检测优化算法。经过实例测试,上述算法与经典多目标优化算法NSGA-II的相比,改进效果明显。最后的实验说明了本章算法检测的准确性。

1 算法描述

首先,使用传统的Ada Boost算法对行人进行粗粒度的分类,然后使用支持向量机(SVM)设计精度更高的行人检测器。针对SVM的分类器参数多,关系复杂,而且无好的调节准则,本文根据核函数的构建条件,将实值量子演化算法引入到SVM参数的寻优问题中,对于分类性能采用多目标优化的方法,取得了较好的效果,同时从理论上分析了算法的复杂度。

1. 1 基于SVM的分级行人检测算法

提出的行人检测方法首先用一级行人检测器在视频图像中检测行人,得到高检出率和较高误报率的检测效果。然后用二级行人检测器去除一级行人检测器的误报结果并保持检出率基本不变。通过这种方法,可以把一级行人分类器的总检测性能适当降低,从而降低一级行人检测器的学习难度,也能重新利用前面段分类器的历史信息。

如图1 所示,一级行人检测器通过Adaboost Cascade从样本集中学习得到,二级行人检测器将一级行人检测器的段分类器作为其特征,通过SVM学习得到。

1. 2 基于SVM的行人检测

给定一个具有N段的Adaboost级联分类器,该分类器中每一段的值[4,5]表示如式(1)。

一个被检测对象在每段的值分别为F1,F2,F3,…,Fn,这些值构成了一个N维的特征矢量V =(F1,F2,F3,…,Fn) 。用这个特征矢量以及梯度直方图[5]在二级行人分类器中来表示行人。如图1 所示,本文算法用SVM训练二级行人检测器,用来检测能通过一级行人检测器的实例对象,这些对象用上面提到的特征矢量表示。

SVM在训练之前必须确定一些参数,其中最重要的就是核函数。从机器学习的角度,核函数决定分类函数集的复杂度,因此它控制SVM性能。从理论上说,核函数、映射函数以及特征空间是一一对应的,确定了核函数就隐含地改变了映射函数和特征空间。核参数的改变实际上是隐含地改变映射函数,从而改变样本数据子空间分布的复杂程度(维数)。不同的分类系统,核函数选取的好坏不仅决定着分类模型的特性,而且很大程度上影响着SVM系统的分类性能和预测(泛化) 性能。本文的算法则假定要优化查全率(recall) 和查准率( precision)两个性能,利用量子演化算法来进行核参数寻优。

1. 3 改进的量子演化算法

在算法初始过程中,量子种群中的每个量子个体中心值在决策向量允许的取值范围里随机选取。基因的宽度则设为决策向量取值范围的宽度值。假设有两个个体q1,q2的量子种群,如图2 所示,其2维决策向量取值范围都为[- 10,10],q1的基因:g11= ( - 5. 00,20),g12= ( - 5. 00,20);q2的基因g21=(-5.00,20),g22=(-5.00,20)。

由于中心值的取值可以在取值范围内,从图2可以看出基因在初始化的时候宽度覆盖范围不完全在决策变量允许的取值范围内,但算法运行的过程中会自动调整宽度来解决这个问题。一个基因平方脉冲的高度的计算如式(2)。

式(2)中,N为量子种群的个体数目。

算法采用非均匀变异[5—8]。设x = (x1,x2,…,xp,…,xn) 是一个变异前的决策向量,分量xp被选为进行变异,其取值范围为[ap,bp],变异后的决策向量为x = (x1,x2,…,x'p,…,xn),即xp变异为x'p。

式中,t为当前演化代数,rnd(2)表示随机产生整数模2 所得的结果,其中 Δ(t,y) 可表示为

式(3)中,max T为最大演化代数,为[0,1]之间的随机数,λ 是决定均匀性的一个参数,它起着调整局部搜索区域的作用,一般取2 ~ 5,本文取2。同其他变异操作相比,非均匀变异是一种自适应算子,搜索步长在不同阶段会自适应地调整[6]。非均匀变异算子如下。

其中,k为观测种群的规模,ξ 为变异概率。

2 算法流程

MORQIEA( 基于实值编码的多目标优化量子演化算法)的算法流程如下。

步骤1: t = 1 ;初始化个体数为N ,同时每个个体基因数为N的量子种群Q(t)。

步骤2:对Q(t) 的量子个体的每个基因位创建PDF和相应的CDF 。

步骤3:观测量子群体Q(t) ,通过CDF创建K实值解向量的临时群体E(t) 。

步骤4: 如果(t = 1) ,则评估E(t) ,C( t) ┐E( t) ,回到步骤7,否则继续。

步骤5:对E(t) 和C(t - 1) 进行均匀交叉操作结果存入E(t) ; 对E(t) 进行变异操作; 评估E(t) 。

步骤6:利用密度比较算子选取E(t) ∪ C(t -1) 最优k个个体保存在C( t) 中。

步骤7:从C(t) 中选取最优的N个个体,通过更新操作(包括迁移(translate) 操作和调整(resize)操作)产生Q(t + 1) 。

步骤8: t = t + 1 ;如果t > max T (最大进化代数),则终止,输出Q(t) ,否则回到步骤2。

3 实验结果

由于NSGA-II是到目前为止常用的多目标优化算法之一,为验证算法的收敛性和多样性,主要与NSGA-II进行对比。参数优化次数100 次( 最大演化代数为10)。选取ZDT[7]进行测试,由于ZDT5 是二进制编码而未采用,ZDT1、ZDT2 和ZDT3 的决策向量为30 维,ZDT4 和ZDT6 的决策向量为10维[8,9]。算法的参数设置如下:1NSGA-II算法的种群大小N为10,其余选择算子、变异算子和交叉算子参数设置与文献[10]相同;2MORQIEA参数设置:种群大小N为10,交叉概率为0. 5,采用非均匀变异,概率为1 /L(L为优化参数个数),系统参数b取2. 0;调整操作参数 δ = 0. 93。

利用MORQIEA比较基于不同核函数(混合核函数、RBF核函数和Polynomial核函数) SVM分类器的性能。参数优化100 次,每种核函数独立运行10 次。结果如图3 所示。

从图3 可以看出,经过不同的核函数设计,查全率和查准率得到了进一步的提高。说明优化核参数和核函数是提高检测性能的一个方法。同时,基于混合核函数,SVM分类器得到的参数查全率和查准率都优于或等于RBF。比较混合核函数和线性核函数,基于混合核函数SVM分类器得到了相同性能或更优性能的参数,说明利用混合核函数的分类器进一步提高了查全率和查准率。

为了更好的验证行人检测优化算法的准确性,选取了对移动背景下的一段视频进行测试,实验中,样本集采用Inria标准测试库中的样本数据,正样本2 100 个,其中1 600 个作为训练集中的正样本,另外500 个正样本构成验证集,负样本的数目共有1 218个。一级行人检测器采用算法基于矩形特征集的Ada Boost算法,二级行人检测器采用基于混合核函数的SVM[5]来训练。实验结果如图4 所示。

如上面的图4 所示,首先看看一级行人检测,也就是图4 中(a) 所示,误检率相当高。随着第二层SVM的逐级优化,误检率逐渐减少,如图4 中( b) 所示。图4(c) 中是优化SVM后的检测结果,结果显示本文算法优化效果比较好。

4 结束语

本文对于移动摄像头下的行人检测问题进行了研究,提出了一种基于量子演化算法的行人检测优化算法,根据核函数的构建条件,将实值量子演化算法引入到SVM参数的寻优问题中,对于分类性能采用多目标优化的概念,取得了较好的效果。经过实例测试,上述算法与经典多目标优化算法NSGA-II的相比,改进效果明显。最后的检测实验验证了本文提出的行人检测优化算法的准确性。

摘要：对视频中移动摄像头下的行人检测问题进行了研究,在AdaBoost行人分类算法、支持向量机(SVM)理论和多目标优化原理的基础之上,并结合三者的特点,提出了一种基于量子演化算法的行人检测优化算法。首先,使用传统的AdaBoost算法对行人进行粗粒度的分类,然后使用支持向量机(SVM)设计精度更高的行人检测器。针对SVM的分类器参数多、关系复杂,而且无好的调节准则,根据核函数的构建条件,将实值量子演化算法引入到SVM参数的寻优问题中,对于分类性能采用多目标优化的方法,取得了较好的效果;同时从理论上分析了算法的复杂度。经过实例测试,算法与经典多目标优化算法NSGA-II的相比,改进效果明显。最后的实验说明了算法检测的准确性。

关键词：视频,行人跟踪,量子演化

参考文献

[1] 范伊红,张元,黄涛.运用视频监控技术检测高速运动目标的新算法.计算机工程,2006;32(22):240—242Fan Yihong,Zhangyuan,Huang Tao.New algorithm for detection of high-speed moving objects using video monitor method.Computer Engineering,2006;32(22):240—242

[2] Weston J,Watkins C.Multi-class support vector machines.Royal Holloway,Department of Computer Science:University of London,1998

[3] Friedman J.Another approach to polychotomous classification.Department of Statistics of Stanford University.http://www-stat.stanford.edu/reports/friedman,1996

[4] 张瑾,方勇.基于分块Contourlet变换的图像独立分量分析方法.电子与信息学报,2007;29(8):1813—1816Zhang Jin,Fang Yong.An independent component analysis algorithm based on block-wise contourlet transform.Journal of Electronic and Information Technology,2007;29(8):1813—1816

[5] 汤义.智能交通系统中基于视频的行人检测与跟踪方法的研究.广州:华南理工大学,2010Tang Yi.Study on video-based detection and tracking method of pedestrian in ITS.Guangzhou:South China University of Technology,2010

[6] 田广.基于视觉的行人检测和跟踪技术的研究.上海:上海交通大学,2007Tian Guang.Study of visual based pedertrain detection and tracking algorithm.Shanghai:Shanghai Jiaotong University,2007

[7] Wolpert D H,Macready W G.No free lunch theorems for optimization.IEEE Transactions on Evolutionary Computation,1997;1(1):67 —82

[8] Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:empirical results.Evolutionary Computation Journal,2000;8(2):125—148

[9] Van Veldhuizen D A,Lamont G B.Multi-objective evolutionary algorithm research:a history and analysis.Ohio,USA:Department of Electrical and Computer Engineering,Air Force Institute of Technology,1998

[10] Zhou A,Jin Y,Zhang Q,et al.Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion.Proceedings of IEEE Congress on Evolutionary Computation.Vancouver,Canada:IEEE,2006:3234—3241

用演化算法求解高校排课的问题 篇4

近年来，由于学校扩招，学生和课程数量比以往大大增加，教室资源相对稀缺，使得高校课表的编排成了各高校教务处最棘手和最费时的工作之一，如何用计算机实现智能排课的问题越来越受关注。

2 排课问题的描述

课表的编排，简称排课，是每个学校在学期开学前都要面对的重要任务，简单地说就是给课程分配时间和教室。高校排课问题中课程安排最重要的是将时间、课程、教室的冲突减到最少，以使教学正常进行。排课过程中的约束条件可分为有效性约束和优化性约束两类。

2.1 有效性约束

有效性约束指一张可行有效的课程表上绝不可能发生的约束，主要包括：

1)一个都是或者一个班级或者一个教室在同一时间段内只能安排一门课程;

2)分配的教室可容纳人数应该大于学生数;

3)对于任一班级，某门课程一周内的授课时间数固定。

另外，由于各学校的不同情况，有可能还有以下有效性约束：

4)课程的学时在周和星期上分配有一定的规律。

5)每门课程都有自己的特定的教学资源。

6)分配的教室可容纳人数应该大于学生数。

7)某些课程可以先行手工排定时间和教室。

8)某些教师、班级、教室在某个时间可能不能利用。

2.2 优化性约束

优化性约束指排课过程为使课表更加合理、更加人性化而产生的约束，例如：

1)尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课。

2)尽可能满足个别教师的特殊上课时间要求。

3)一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化。

4)一个教师的课不能排满一整天。

5)学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。

2.3 排课问题的数学模型

排课问题实质就是经典的时间表问题(Timetabling Problem，简称TTP)，它可以一般化地描述为：设给定n个事件和m个资源，用cij表示将第i个事件分配给第j个资源的代价，所求问题为决定一个从事件到资源的最优分配，使得总的代价最小且满足k个附加条件[1]。

1975年艾温(S.Even)证明了TTP问题是NP完全的[2]，宣布了这一问题的学术地位和难度。

2.4 问题假设

因为课表问题的约束条件根据实际情况的不同而变化，因此在开始研究之前有必要进行假定，确定所研究问题的范围。

1)一周上五天课，每天5个教学单位时间，一个教学单位时间为2课时。

2)有的课程只在单周或双周上课，有的课程在单周双周都要上。

3)只考虑有效性约束，不考虑优化性约束。

2.5 常用算法

解决排课问题的主要方法有遗传算法、模拟退火法、分支限界法、贪婪算法等[3]，其中又以遗传算法最为常见。遗传算法重点在于基因的表达，因此产生了不同的若干算法[3,4,5]。

3 演化算法

演化算法与遗传算法相似，是借鉴生物界的进化规律深化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的并行性;能自适应地调整搜索方向，不需要确定的规则。因此演化算法具有良好的智能性、鲁棒性[6]，特别适合用于处理传统的搜索算法难以解决的复杂的和非线性的问题。

应用演化算法求解问题的核心技术主要体现在编码、评价、交叉、变异、选择和淘汰六方面。

3.1 编码

根据问题的描述，设立以下几个集合：

1)教师集合T={Ti|i=1,2,…,t}。

2)班级集合S={Si│i=1,2,…,s}。

3)课程集合C={Ci│i=1,2,…,c}。

4)教室集合R={Ri│i=1,2,…,r}。教室为授课的地点，一般有类型和容量两种属性。类型属性反映教室的设备状况，会限制某些课程不能在此上课;容量属性会限制某些班级不能在此上课。

5)时间集合M={Mi│i=1,2,…,m}。时间集合根据学校的作息时间不同而不同。根据假设，共有50个可供分配的时间单元，其中单周25个，双周25个。

6)课元集K={(t,s,c)│t∈T,s∈S,c∈C}。课元是一个三元数，由教师、班级和课程组成，表示“教师给班级上的某课程”。课元集是所有要安排的课程的集合。

7)资源集Z={(r,m)│r∈R,m∈M}。资源集是一个二元数，由教室和时间组成，表示“某教室在某时间可上课”。课元集是所有可安排的资源的集合。

根据以上定义，原问题可转化为求映射集F:K→Z的问题。所以，个体的编码方式可表示为向量(z1,z2,…,zN)，其中N=|K|，表示课元的数量;zi∈Z(i=1,2,…N)，表示第i个课元安排在资源zi中上课。这样，一个个体就代表了一个排课方案。找到最合理的排课方案，就转化成搜索到最优秀的个体的问题。

3.2 评价

根据约束条件和问题假设，设置问题的最高评价值为1000，评价值越高表示个体越优秀。当个体满足所有条件时，它获得最高评价值1000;如果某些约束条件不能满足，则扣除相应的评价分。

根据个体的编码方式，有效性约束的8条法则可总结为以下6条可操作的扣分法则：

1)同一教师不能在同一时间上不同课课程。

2)同一班级不能在同一时间上不同课课程。

3)同一资源不能指派多个课元。

4)每个课元由于老师有其它安排或班级有其它安排等原因不能在某些时间上课。

5)每个课元由于学生人数过多或者教室硬件设备落后等原因不能在某些教室上课。

6)某些资源已经被指定使用，不能指派任何课元。

用T(x)表示课元x的任课教师，S(x)表示课元x的受课班级，C(x)表示课元x的课程;用R(x)表示资源x所占用的教室，用M(x)表示资源x所占用的时间。为了进行惩罚，须设立限制集。根据规则要求定义3个限制集：

a)R4={(k,r)│k∈K,r∈R}，对应法则4，表示课元k不能指派到所有教室为r的资源。数据应该反映真实的需求，是作为问题数据的一部分存在的。

b)R5={(k,m)│k∈K,m∈M}，对应法则5，表示课元k不能指派到所有时间为m的资源。数据应该反映真实的需求，是作为问题数据的一部分存在的。

c)R6={(r,m)│r∈R,m∈M}，对应法则6，表示教室r在时间m不能指派任何课元。数据应该反映真实的需求，是作为问题数据的一部分存在的。

则上述六条法则的具体的实现方式可表示为：

1)(i,j),i≠j，如果T(i)=T(j)∧M(zi)=M(zj)，则扣分d1。

2)(i,j),i≠j，如果S(i)=S(j)∧M(zi)=M(zj)，则扣分d2。

3)(i,j),i≠j，如果zi=zj，则扣分d3。

4)(i),i∈K，如果(i,R(zi))∈R4，则扣分d4。

5)(i),i∈K，如果(i,M(zi))∈R5，则扣分d5。

6)(i),i∈K，如果(R(zi),M(zi))∈R6，则扣分d6。

其中d1～d6表示相应项的扣分量，用以调节各法则的权重。因为这六项法则都是有效性法则，任何有一项不满足都无法构成一张可行的排课表，因此这里设置d1=d2=d3=d4=d5=d6=1。

3.3 选择、交叉、变异和淘汰策略

选择策略是“优胜劣汰”的自然法则的体现。本算法使用轮盘法则进行选择，也就是按照评价值线性地决定被选择的概率。

交叉是演化算法中实行大范围搜索的主要手段，好的交叉算子能够快速定位到最优解的附近，或者能够均匀地遍历解空间，从而能以较高的概率搜索到最优解。因此，交叉算子的设计对算法的整体运行效率有重要的影响。

经验表示，在大部分使用演化算法求解的问题中，使用模仿染色体分裂的交叉算子是具有较高性能的，所以大部分算法都沿用了这一办法，除非简单的交换会导致个体非法，例如用演化算法求解TSP问题[7]。

本算法采用单点交叉策略。容易证明交叉后两个新的个体仍然是合法的个体。

变异的方法也很直接。随机选择一个课元i，然后将i所对应的资源zi随机变为另一资源z'i。

淘汰策略采用μ+λ策略。这种策略能进行小规模淘汰，实现快速收敛，对于规模较小的问题比较合适。

4 实验与分析

以电子科技大学中山学院计算机工程系2009年上半年实验课排课数据为例，得到实验数据，数据中|T|=27，|S|=23，|C|=32，|R|=5，|M|=50，|K|=62，|Z|=250，|R4|=200，|R5|=1478，|R6|=28。这组数据的特点是教室相对少，冲突相对多，所以人工排课的难度很大，经验表明大约一个人日才可完成。而且实验室排课是二次排课，它必须在理论课程排完之后再排，因此理论课程的课程表稍有改动实验课的课程表就必须调整，因此给排课工作带来极大的麻烦和不便。

使用演化算法，问题就变得简单多了。设置种群大小为50，μ+λ中λ值为3，运行5000代，运行结果图如图1。

图1中，横坐标表示运行代数，纵坐标表示运行至每一代时得到的最大评价值。可以看出，最大评价值呈上升趋势而且最终能够达到1000，结果可以接受。

从结果可以看到，程序大约运行至4000代就出现最优解，运行完5000代需要0.755秒钟。

即使加上前期大约一小时的数据录入工作，很明显，用演化算法排课要比人工排课效率高得多。而且，大部分的数据录入是一次性的，即使部分限制条件经常在变，但对已经录入的数据进行少量修改的工作量不大，数据修改后马上又可运行程序产生一个新的课程表。

5 结论

结果表明，用演化算法解决排课问题是可行的。它能极大提高排课的工作效率与减少人工操作的失误，因此是值得推广的。

参考文献

[1]郑月锋,黄德才,刘端阳.遗传算法在求解时问表问题中的应用研究[J].浙江工业大学学报,2006,34(2):162-165.

[2]Sohaerf A.A survey of automated timetabling[J].Artificial Intelligence Review,1999,13:87-127.

[3]廖远,黄勤,曹培霞.基于三维编码的自适应遗传算法在排课系统中的应用[J].计算机与现代化,2008,12:23-28.

[4]郭芸俊.遗传算法在高校排课问题中的应用[J].电脑开发与应用,2009,22(2):75-77.

[5]谭保华,彭伟.基于蚁群遗传算法的高校排课系统[J].计算机仿真,2008,25(12):294-297.

[6]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

[7]李悦乔,康立山,李程俊.求解TSP问题的实数编码演化算法[J].计算机工程与设计,2007,28(19):4592-4594.

[8]黄海.基于遗传算法排课系统的设计与实现[J].大众科技,2005(9):81-83.

演化算法 篇5

多翼离心风机是一种结构特殊的离心式通风机, 较一般离心风机具有压力系数高, 流量系数大, 在满足一定流量和全压要求时, 有体积小、噪声低等特点, 但是效率较低。为进一步提高多翼离心风机的效率, 许多学者[1,2,3,4]从不同角度采用不同方法对风机的优化设计做了一些工作。

叶轮是离心风机的核心部件, 对风机中能量传递起着主导作用, 因此提高叶轮的效率, 对风机整体性能提高意义重大。基于此, 本文以一种机车牵引电机的多翼式冷却风机为研究对象, 建立风机叶轮优化设计模型, 使用差分演化算法研究风机效率提升优化问题。

1 机车牵引风机优化模型

随着机车的运行速度和运载能力不断提升, 对机车各个部件的性能也提出了更高的要求。牵引风机是给提供动力来源的牵引电机进行冷却散热的重要部件, 其性能的优劣在一定程度上影响了机车的安全性和稳定性。本文以一种多翼式牵引风机为研究对象, 以效率作为优化设计的目标。

离心风机的叶轮结构中影响风机性能的参数有:叶轮的外径D2, 出口安装角β2A, 内径D1, 进口安装角β1A, 进口叶轮宽度b1, 出口叶轮宽度b2, 叶片数z。由于机车的安装空间限制, 对风机的外形尺寸有严格要求, 因此为了不改变风机的外形尺寸, 保持叶轮的内外径不变, 叶轮的宽度不变。以风机的进、出口安装角和叶片数为设计变量, 即设计变量为x= (x1, x2, x3) = (β2A, β1A, z) 。以提高风机效率为研究对象, 采用减少风机损失为方式来提高效率。流动损失是风机的主要损失, 降低流动损失可以通过调整风机叶轮的结构参数来实现, 因此将风机的流动损失作为优化目标。

风机在设计流量下工作的流动损失可分为三部分, 用公式表示为

1) 气流从轴向流动变为径向所造成的损失Δpl:

对于在叶轮进口处转弯损失, 已知风机流量Q, 在无集流器的情况下, 考虑到叶片有一定的厚度, 对于这种因通流截面积减小的程度可用阻塞系数τ来表示, 对于叶片进口阻塞系数τ1为

同理叶片出口阻塞系数τ2为

因此, 对于进风口处的气流绝对速度c1调整为

式中:ξ1为损失系数;ρ为气体密度, kg/m3;c1叶轮进风口处气流的绝对速度, m/s。

2) 叶道内的损失Δpimp

叶轮进风口气流的相对速度w1为

式中:ξimp为损失系数;w1叶轮进风口处气流的绝对速度 (m/s) 。

3) 蜗壳内的损失Δp4。

在扩压部分的入口空气的绝对速度c3可以近似等于叶轮出口速度c2:

式中:c2r可为叶轮出口的法向速度;u2为叶轮的牵连速度u2=πD2n/60;k为环流系数。

约束条件主要包括:

1) 进、出口安装角约束条件。对于多翼式离心风机叶轮的进出口安装角之间有一定的几何关系, 如图1。由β2A=180°-β2, β1A=β1, 则σ=180°- (β2+β1) 。当σ>90°时, 叶道截面入口较小, 而后逐渐增大, 又由大变小, 相应相对速度由大变小, 又由小变大, 这种速度变化容易形成分离损失。当σ≤90°时, 叶道截面变化不大, 相对速度基本保持不变, 可以减少气流分离损失。

2) 叶片数约束。多翼式风机的叶片数一般较多, 一般取值为[32, 64]。

3) 风机的压力约束。根据文献[5]中要求, 通风机在规定的流量下, 所对应的全压或静压偏差为上下10%。

2 差分演化算法

在众多启发式优化方法中, 差分进化 (Differential Evolution, DE) [6]是一种基于群体差异的启发式随机搜索算法, 该原理简单、参数少、算法鲁棒性强等特点, 被广泛用于约束优化计算、机械优化设计、函数优化设计等。差分演化算法的进化过程包括变异、交叉和选择三个操作, 假设种群规模为NP, 其中的个体为N维向量, 则第i个个体定义为:xi= (x1, i, x2, i, …, xn, i) T, i=1, 2, …, NP。

1) 变异操作。在第G代中, 目标个体为Xi, G, 经过变异操作后的个体为Vi, G。变异操作过程有多种方法, 常见的有5种变异操作[7], 因此本文选择DE/rand/1/bin变异, 该种变异主要特点是收敛速度快, 鲁棒性好。其重组公式为:Vi, G=Xri1, G+F (Xri2, G-Xri3, G) 。

2) 交叉操作。为了保持种群的多样性, 引入交叉操作, 即将目标个体和变异后的个体不同基因位的数值, 重新组合产生新的个体ui= (u1, i, u2, i, …, un, i) T, 交叉操作的具体方式为:

式中:产生一个随机数randj∈[0, 1], 比较randj与交叉因子CR或j与K的大小关系, 以判断是否用vi, j来替换xi, j, 以得到新个体ui, j, K∈[0, N-1]之间的整数。

3) 选择操作。新一代的个体产生方式为:

式中f () 为目标函数。在进化过程中如果子代个体优于父代个体, 将子代个体替换掉父代个体, 并将子代个体插入种群中参与下一代进化。

4) 算法的基本流程。

Step1:针对叶轮优化模型, 对设计变量进行编码, 本文采用实数编码。在决策空间范围内生成初始种群NP, 并设定迭代计时器generation=0。

Step2:对生成的种群进行适应度评估, 其中适应度评估函数为:

Step3:判断是否满足条件, 满足则输出结果, 否则generation=generation+1。

Step4:对个体进行进化操作, 包括差分变异操作, 交叉操作, 对新产生的子代个体使用二进制锦标赛法进行选择, 如2.2节介绍。

Step5:产生新的子代种群, 并转到Step3。

3 工程实例

以联城集团设计的一款南非机车牵引电机冷却风机为例, 该风机为多翼式离心通风机, 其中风机在流量Q=3.5 m3/s下, 需全压为4000 Pa, 气体密度为1.225 kg/m3, 转速n=1440 r/min, 叶轮外径D2=0.72 m, 叶片厚度为0.003 m, 叶轮厚度为0.175 m。进口安装角取值范围为[45°, 85°], 出口安装角取值范围为[155°, 180°]。对于叶片数, 为了简化工艺, 叶片数选取z=32~64。由于要保证风机的出口压力, 其取值范围为[3800, 4200]Pa。对于损失系数取值, 选取ξ1=0.15, ξimp=0.3, ξ4=0.3。

设计变量:X=[β2A, β1A, z]T=[x1, x2, x3]T。

目标函数:

约束条件为:155°≤x1≤180°, 45°≤x2≤90°, 32≤x3≤64, 90+x2-x1>0°, 3800≤p′≤4200。

设置算法的参数为种群大小为NP=100, 交叉概率为0.8, 惩罚因子为103, 最大进化代数为1000。表1为优化前后的风机叶轮参数及目标值。

从表1中可知优化后的风机的流动损失明显减小, 其流动损失由273.68减少至227.74, 减小了16.79%。因此, 差分演化算法优化风机叶轮参数, 能够有效降低风机的流动损失, 提高风机的工作性能。

4 结论

通过建立机车多翼式牵引风机参数优化模型, 以风机提高效率为目标, 针对叶轮结构进行参数优化设计。采用差分演化算法对风机优化问题进行求解, 结果表明优化后的叶轮参数降低了风机16.79%的流动损失, 说明该方法降低了人为因素对解决该类优化问题的影响, 且优化后的结果更科学、更符合实际情况。未来将进一步研究风机的多目标优化问题和考虑更多的风机设计因素。

参考文献

[1]张素梅, 郭培红, 温小萍, 等.多翼离心风机CFD分析及参数优化设计[J].风机技术, 2011 (4) :40-43.

[2]徐辰, 杨爱玲, 毛义军.离心风机噪声预测方法的进展与分析[J].流体机械, 2011, 39 (7) :35-40.

[3]李晓丽, 楚武利, 袁森.离心风机整机三维数值仿真方法及分析[J].计算机仿真, 2010, 27 (10) :335-338, 365.

[4]张涛, 孟宪举, 李健.离心式通风机的数值模拟[J].河北理工大学学报 (自然科学版) , 2011, 33 (1) :86-90.

[5]郭庆富, 李健伟.一般用途离心通风机技术条件[S].北京:机械工业出版社, 北京, 2006.

[6]杨启文, 蔡亮, 薛云灿.差分进化算法综述[J].模式识别与人工智能, 2008, 21 (4) :506-513.

演化算法 篇6

近年来,多目标优化问题MOP(Multi-objective Optimization Problem)求解已成为演化计算的一个重要研究方向,而演化算法(EA)是一类基于种群的搜索算法,可并行搜索多个目标,在搜索过程中可以将最优解保存到下一代,这些正是求解多目标优化问题所希望的。多目标演化算法研究的主要目标是使算法种群收敛到Pareto前沿,且具有良好的分布广度和均匀程度。NSGA[1]、NSGA-Ⅱ[2]、SPEA2[3]、PAES[4]等都是目前比较具有代表性的多目标演化算法,它们分别采用“小生境技术”、“排挤距离”、“最近邻居法”、“网格法”来维护群体多样性。受到上述研究的启发, 本文从更好地维护解的多样性出发, 给出一种基于动态拥挤距离的多目标优化演化算法,并根据个体的级数设计了一种自适应变异步长的柯西变异算子,对变异越界处理进行了改进。实验证明算法具有更好的收敛性与多样性。

1MOP中的一些基本概念

不失一般性,考虑下列n个自变量和m个目标函数的多目标函数优化问题:

Minimize y=f(x)=(f1(x1,…,xn),…,fm(x1,…,xn))

其中x=(x1,…,xn)∈X⊂Rn,y=(y1,…,ym)∈Y⊂Rm,x为决策(参数)向量,X为决策空间,y为目标向量,Y为目标空间。

定义1 优劣性

向量u=(u1,…,um)优于向量v=(v1,…,vm)(记为u≺v),当且仅当∀i∈{1,…,m},满足ui<=vi ,并且∃j∈{1,…,m}使得ui<vi。

定义2 Pareto最优解

设a∈X,X′为X的子集,若X′中不存在优于a的向量,则称a为关于子集X′的非劣解或关于子集X′的Pareto最优解,若a为关于X的非劣解,则a简称为非劣解或Pareto最优解。

定义3 Pareto前沿

对于给定的MOP f(x)和Pareto最优集(P*),Pareto前沿(Pf*)定义为:

Pf*={u=f(x)|x∈P*}

定义4 非支配集

设有解集P,P中的个体q不被任何其他个体支配,则q是P中的非支配个体;P的非支配个体构成的子集称为P的非支配集。即= {q|q∈P且不存在q`∈P使得q`≺q}。

2基于动态拥挤距离的自适应变异演化算法

2.1群体多样性保持策略

保持群体多样性在实际中有着重要意义,它能够给决策者提供更多合理的选择。另外对于目标函数数目很多的优化问题,会由于搜索空间的维数过高,使得群体个体之间很难进行优劣性比较,有时甚至会出现所有个体皆非支配解。且在优化后期,群体中各个体已经基本上逼近Pareto前沿,从而使进化选优无法正常地进行下去。如何解决这个问题呢?

解的分样性主要体现在解分布的广度和均匀程度。关键问题在于如何刻画解分布的广度和均匀程度。例如: 小生境技术、超网格、信息熵[5]、个体密度等。本文采用个体的拥挤距离来维持群体的多样性,且具有动态性。

个体的拥挤距离是针对种群中一层非支配个体而言。个体i的拥挤距离计算公式定义如下:

$d{}_i=\frac{1}{m}{\displaystyle \sum _{k=1}^m\left|f{}_k^{i+1}-f{}_k^{i-1}\right|}$

其中:m为目标的维数;fik为第i个个体在第k维目标上排序后的第k维目标值。下面以一个二维目标的情况来说明拥挤距离的计算过程。图1中的实心点表示同一非劣前沿上的个体。则个体i的拥挤距离:

$d{}_i=\frac{1}{2}[|f{}_1^{i+1}-f{}_1^{i-1}|+|f{}_2^{i+1}+f{}_2^{i-1}|]$

实际上为图中两虚线段之和的一半。通常我们认为种群中个体之间的距离越小, 分布度就越差, 那么进化算法就是要淘汰这些密集的点。显然, 拥挤距离 di 的值越小, 个体i就越落在拥挤区域, 反之个体 i 位于稀疏区域。

现在有一个问题,如果当前非支配集中个体的数目大于规定种群数,则要按拥挤距离从小到大一次性淘汰多余个体数。显然,这种策略比较粗糙。因为一次种群维护只需计算一次个体的拥挤距离,如果一次性淘汰所有拥挤距离小的个体,则会出现个体之间的个体缺失,使得解的分布性较差。再由于某些个体可能在某些维目标上的差值很大,而在另些维目标上的差值却很小,使得这些个体的拥挤距离较小;但某些个体在各维目标上的差值均相差不大,使得这些个体的拥挤距离较大,此时会误认为前面那些个体的分布性较后面这些个体要差,而事实刚好相反。

针对上述拥挤距离的不足,本文提出了一种称为动态拥挤距离的多样性保持策略。

对于第一个不足,本文采取这样的策略:在种群维护过程中,每淘汰一个个体就重新计算种群中剩余个体的拥挤距离;对于第二个不足,本文根据下式来计算个体i的动态拥挤距离:

ddi=di/log(1/si)

其中$s{}_i=\frac{1}{m}{\displaystyle \sum _{k=1}^m(}|f{}_k^{i+1}-f{}_k^{i-1}|-d{}_i){}^2$为个体i在各维目标相邻个体拥挤距离的方差,它能反映各维目标拥挤距离的差异程度,差异程度较大的个体被保留的机会就越大。

2.2多父体杂交算子[7]

从当前群体中任意选取M个个体,通过它们的非线性组合形成新个体v*:

$v{}^{*}={\displaystyle \sum _{i=1}^{{\rm M}}a}{}_{i}x{}_i$

其中${\displaystyle \sum _{i=1}^{{\rm M}}a}{}_i$满足=1 ,-0.5<=ai<=1.5。

其中,系数ai范围不设为常见的[0 ,1],是为了让杂交算子能搜索到由该M个个体所张成的子空间的外缘,即凸空间,增加算子搜索能力。

2.3变异算子的设计

在进化算法中,变异算子是一种非常重要的算子。它具有一定的局部随机搜索能力,可加强进化算法的鲁棒性、多样性。进化算法中常用的变异算子主要有:均匀变异、非均匀变异、高斯变异、柯西变异、多项式变异等。本文利用Pareto占优对个体进行排序并分级,1级代表最好,2级次之,以此类推。并根据个体的级数,设计了一种自适应变异步长的柯西变异算子。具体定义如下:

x′i=xi+C(0,σ)

其中C(0,σ)表示以0为中心,尺度参数为σ的Cauchy分布的随机数。而尺度参数为σ即变异步长,在本文中也表示个体的级数。这种变异操作,可使非支配个体采用较小的变异步长进行局部搜索;其他个体采用较大的变异步长,保证解在可行域空间中能进行全局搜索。

多目标优化算法在执行变异操作时,经常会出现越界这种情况。常规的处理方法是取端点值,研究表明使用这种越界处理方法效果比较很差。根本原因在于,多目标优化问题是一组最优解,不是单个最优解,这势必增加与之相对应的变异操作规模,越界的概率也会加大。而常规的越界处理方法会造成种群多样性的丧失。

下面提出改进的越界处理方法:

其中lk和uk分别是解向量取值范围的下限和上限,r为[0,1] 之间的随机数。

这种改进的越界处理方法,可以弥补因越界处理而造成的种群多样性的损失,因为变异后的值有50%的概率等于变异前原来的值。

2.4算法描述

本文算法的详细步骤如下:

1) 令进化代数t=1,随机产生一个规模为N的初始父代群体。

2) 从当前群体中任意选取M个个体和随机产生1个个体(可增加种群的多样性和全局搜索能力,使得解集具有良好的分布度),对这(M+1)个个体采用多父体杂交产生1个后代。

3) 从当前群体中任意选取2个个体进行变异操作,产生2个后代。

4) 对这(N+3)个个体进行非支配排序分级,对每一级别中的个体计算动态拥挤距离, 再根据群体多样性保持策略,淘汰动态拥挤距离最小的3个个体。

5) 如停机规则满足则停机,否则t=t+1,并转步骤2)。

3数值实验

3.1测试函数

多目标优化问题的测试函数的设计比单目标优化问题的设计要复杂得多。一般将测试函数设计成具有多模型、欺骗性、孤立最优点等特征的函数。

本文使用3个典型的测试函数来检验新算法的性能。

实验函数T1:

$\begin{array}{l}{\rm M}inimize{\rm T}{}_3(x)=(f{}_1(x{}_1),f{}_2(x))\\ f{}_1(x{}_1)=x{}_1\\ g(x{}_2,\cdots ,x{}_m)=1+9*{\displaystyle \sum _{i=2}^m}x{}_i/(m-1)\\ h(f{}_1‚g)=1-\sqrt{\frac{f{}_1}{g}}\\ m=10,x{}_i\in [0,1],i=1,\cdots ,m\end{array}$

这个问题的Pareto最优解集为g(x2,…,xm)=1,其均衡面为凸集。

实验函数T2 :

$\begin{array}{l}{\rm M}inimize{\rm T}{}_1(x)=(f{}_1(x),f{}_2(x))\\ f{}_1(x)=1-\exp \left(-{\displaystyle \sum _{i=1}^3\left(x{}_i-\frac{1}{\sqrt{3}}\right)}{}^2\right)\\ f{}_2(x)=1-\exp \left(-{\displaystyle \sum _{i=1}^3\left(x{}_i+\frac{1}{\sqrt{3}}\right)}{}^2\right)\\ x=(x{}_1,x{}_2,x{}_3)‚x{}_i\in [-4,4],i=1,2,3\end{array}$

函数T1的Pareto最优解集为,$\text{x}{}_1=\text{x}{}_2=\text{x}{}_3\in \left[\frac{-1}{\sqrt{3}},\frac{1}{\sqrt{3}}\right]$。

实验函数T3:

$\begin{array}{l}{\rm M}inimize{\rm T}{}_4(x)=(f{}_1(x{}_1),f{}_2(x))\\ f{}_1(x{}_1)=x{}_1\\ g(x{}_2,\cdots ,x{}_m)=1+10(n-1)+\\ {\displaystyle \sum _{i=2}^m(}x{}_i^2–10\cos (4\times pi\times x{}_i)\\ h(f{}_1‚g)=1-\sqrt{\frac{f{}_1}{g}}\\ m=10,x{}_1\in [0,1],x{}_i\in [-5,5]‚i=2,\cdots ,m\end{array}$

这个问题含有219个局部Pareto最优集,它能够测试算法处理多峰函数的能力。当g(x2,…,xm)=1时可求得全局Pareto最优阵面。当g(x2,…,xm)=1.25时可以求得局部Pareto最优阵面。

3.2实验结果及算法性能评估

评估多目标优化问题的算法性能指标主要有:最优群体的逼近性、分布均匀性、算法的时间复杂度及收敛速度等。但在实际问题中,决策者往往只对某一范围的最优解感兴趣,故本文只评价测试函数最终获得的最优解集的逼近性、均匀性及本文算法的时间复杂度,并与经典算法NSGA-Ⅱ进行比较。

3.2.1 算法的时间复杂度

设目标数为m群体规模为N,算法的时间复杂度取决于:

1) 非支配排序, ο(mN2);

2) 计算个体的拥挤距离,ο(mNlog(N));

3) 种群在杂交变异后最多有N+3个个体,将它们分别依m个目标进行排序,以计算个体的拥挤距离进行裁减操作。该步骤的时间复杂度为O(m(N+3)log(N+3))。

一般情况下取m≤N,则本文算法总的时间复杂度取上述分析结果中的最大值ο(mN2)。NSGA-Ⅱ是一种经典的快速非支配排序多目标精英遗传算法。设它们的群体规模为L,其时间复杂度为ο(mL2),令群体规模N=L,则它与这两种算法在最坏情况下具有相同的时间复杂度。

3.2.2 最优群体的逼近性与均匀性

引用文献[8]定义的GD来度量最优群体的逼近性, 文献[9]定义的SP来衡量最优解的分布均匀性。

实验在MATLAB中进行,参数种群数N=70,杂交个体数M=9,运行最大代数为3000代。将本文算法和经典的NSGA-Ⅱ算法独立运行30次,然后统计两种算法所得Pareto最优解集的均匀性(SP)与逼近性(GD)的最好、均值和方差,以此作为衡量算法性能的标准。图2至图7为从30次运行中随机选择的一次运行结果,从实验曲线可以看到本文算法求出的Pareto前沿在逼近性方面要优于NSGA-Ⅱ。表1至表3为两种算法对测试函数的SP与GD的统计结果,从表中数据可看出,在解集的逼近性和均匀性方面本文算法对3个测试函数的标准方差都明显小于经典的NSGA-Ⅱ 算法,这说明本文算法性能更稳定、更具鲁棒性。

4结语

本文从更好地维护解的多样性出发, 针对拥挤距离的不足,提出一种基于动态拥挤距离的分布性保持策略,它可避免造成某些区域个体密集,另一些区域个体稀疏的现象。在进行多父体杂交操作时,引入随机算子,增加了种群的多样性和全局搜索能力,使得解集更具良好的分布度同。再根据个体的Pareto排序级数设计了一种有效的自适应变异步长的柯西变异算子,并对变异越界处理进行了改进。最后通过实验证明本文算法具有更好的收敛性与多样性。

摘要：多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。根据个体的非支配排序级数设计了一种自适应变异步长的柯西变异算子,对变异越界处理进行了改进;并定义和使用动态拥挤距离来保持群体中个体的均匀分布。最后通过对测试函数的实验,验证了算法的可行性和有效性。

关键词：演化算法,多目标优化,自适应变异,动态拥挤距离

参考文献

[1]Srinivas N,Deb K.Multiobjective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.

[2]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Trans on Evolutionary Com-putation,2002,6(2):182-197.

[3]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pa-reto evolutionary algorithm[R].Zurich:Computer Engineering and Networks Laboratory(TIK),Swiss Federal Institute of Technology(ETH)Zurich,2001.

[4]Knowles J D,Corne D W.The pareto archived evolution strategy:A new baseline algorithm for pareto multiobjective optimization[C]//Congress on Evolutionary Computation.Piscataway:IEEE,1999:98-105.

[5]朱学军,陈彤,薛量,等.多个体参与交叉的Pareto多目标遗传算法[J].电子学报,2001,29(1):106-109.

[6]崔逊学,李淼,方廷健.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能,2001,14(3):291-296.

[7]Guo Tao,Kang Li-shan.A new Evolutionary Algorithm for Function Optimiza-tion[J].Wuhan University Journal of Natural Sciences,1999,4(4):409-414.

[8]Van Veldhuizen D A,lamont G B.Multiobjective evolution ary algo-rithm research:A history and analysis[R].Department Elec.Com-put.Eng.,Graduate School of Eng.,Air ForceInst.Technol.,Wright-Patterson AFB,OH.Technical Report TR-98-03,1998.

演化算法 篇7

并联机构与串联机构相比,具有刚度大、结构

稳定、承载能力强、精度高、运动惯性小等优点,在机器人和机床等领域有十分广阔的应用前景。在并联机构设计中,因尺寸变化引起的性能变化要比传统的串联结构大得多,并联机构的优化设计具有更重要的意义[1,2]。目前,并联机构的优化主要集中在工作空间和灵活性上,而且仅仅对某一性能进行优化设计[3]。并联机构的结构优化是比较困难的,这是因为并联机构的不同性能规范对于设计参数往往是相互矛盾的,是一个多目标优化问题;另外,快速有效地对并联机构的各种性能进行评价也是个难点。

实现对并联机构多个性能指标同时优化设计需要建立多目标优化模型。传统的求解多目标优化问题的方法,如主要目标法、权重系数法等大多是把多目标问题转化为单目标优化问题进行处理,很难甚至无法获取全部最优解。进化算法(如遗传算法、粒子群优化算法等)是基于群体优化的算法,十分适合用于多目标优化问题,被用于设计多目标优化算法已经取得了不少成果[4,5]。获取收敛性和分布性更好的解是多目标优化算法研究者孜孜不倦的追求。差异演化算法[6](differential evolution,DE)是近几年新兴的一种新的进化算法,已在各个领域得到了广泛的应用。本文在中心差异演化算法[7]的基础上提出一种多目标差异演化算法(multi-objective differential evolution,MODE)。

为了快速有效地评价并联机构的性能,使用蒙特卡洛方法对并联机构的工作空间进行定量评价,使用一阶影响系数评价机构的速度全域性能,并以工作空间和速度全域性能为目标建立多目标优化模型,最后,以3-TPT并联机器人机构的多目标优化设计为例建立多目标优化模型并使用MODE实现了模型的求解。

1 多目标差异演化算法

1.1 多目标优化的相关概念

一般地,一个含有n个决策变量、m个目标变量的多目标优化问题可表述为

其中,x为n维决策矢量,x=(x1,x2,…,xn)∈X⊂Rn,X为n维决策空间,y为m维目标矢量,y=(y1,y2,…,ym)∈Y⊂Rm,Y为m维目标空间。fk(x)(k=1,2,…,m)为m个目标函数,满足l个不等式约束和p-l个等式约束。针对多目标优化问题,给出以下几个重要的定义。

定义1 Pareto占优。假设xa、xb∈Xf是式(1)所示多目标优化问题的两个可行解,则称与xb相比,xa是Pareto占优的,当且仅当:

(1)∀c1=1,2,…,m,fc1(xa)≤fc1(xb)

(2)∃c2=1,2,…,m,fc2(xa)<fc2(xb)

记作xa≻xb,也称作xa支配xb。

定义2 Pareto最优解。一个解x*∈Xf被称为Pareto最优解(或非支配解),当且仅当满足如下条件:

┐∃x∈Xf:x≻x*

定义3 Pareto最优解集。Pareto最优解集是所有Pareto最优解的集合,定义如下:

${\rm P}{}^{*}\underset{}{\overset{\text{Δ}}{=}}\{┐\exists \mathit{x}\in X{}_f$:x≻x*}

多目标优化问题的求解目的是获得Pareto最优解,即不存在为改进某一项目标值而牺牲其他目标值的解。

1.2 多目标差异演化算法

差异演化算法是基于实数编码的进化算法,最初的群体是随机产生的,每个个体为搜索空间中的一个实向量。令xi(g)为第g代的第i个个体,则

xi(g)=(xi1(g),xi2(g),…,xin(g))

xLi j≤xi j(g)≤xUi j

i=1,2,…,N;j=1,2,…,n;g=1,2,…,Tmax

式中,xLi j、xUi j分别为个体的上下界;N为种群规模;Tmax为最大进化代数。

差异演化算法的实施措施如下:

(1)生成初始种群。在n维空间随机产生N个个体,实施措施如下:

xi j(0)=xLi j+rand(0,1)(xUi j-xLi j)

其中,xi j为个体xi的第j个决策变量;rand(0,1)是[0,1]上服从均匀分布的随机数。

(2)变异操作。变异操作是差异演化的关键步骤,从种群中随机选取3个个体(xp1、xp2、xp3),且p1≠p2≠p3≠i,定义变异操作为

hi j(g)=xp1,j+F(xp2,j-xp3,j)

式中,F为缩放因子。

(3)交叉操作。交叉操作定义为

$v{}_{ij}(g+1)=\{\begin{array}{l}h{}_{ij}(g)rand(0,1)\le {\rm P}{}_{\text{C}}\parallel j\ne rand(1,n)\\ x{}_{ij}(g)\text{其}\text{他}\end{array}$

式中,PC为交叉概率;rand(1,n)为[1,n]之间的随机整数。

(4)选择操作。由评价函数对父代个体向量vi(g+1)和子代个体向量xi(g)进行比较(假设评价函数值越小的个体越优),则

$\mathit{x}{}_i(g+1)=\{\begin{array}{l}\mathit{v}{}_i(g+1)f(\mathit{v}{}_i(g+1))＜f(\mathit{x}{}_i(g))\\ \mathit{x}{}_i(g)\text{其}\text{他}\end{array}$

反复执行(2)～(4),直到达到所要求的停止条件。

除了上述的演化模式外,Storn等[8]还提出了其他的模式,算法的通式表示为

DE/x/y/z

其中,DE表示差异演化算法;x代表被加噪声的个体向量;y代表差异向量的个数;z代表交叉模式,分为指数模式(exp:exponential)和二项式模式(bin:binomial)。

研究发现,DE/rand/1/bin模式收敛速度慢,但鲁棒性较好;DE/best/1/bin模式收敛速度快,但鲁棒性较差[8]。文献[7]提出一种新的模式:中心差异演化算法(DE/Cp/y/z),经验证是具有更好寻优性能的差异演化算法。定义第t代群体中心点:

$\mathit{C}{}_p=\frac{1}{{\rm N}}{\displaystyle \sum _{i=1}^{{\rm N}}\mathit{x}}{}_i$ (2)

群体中心点随代数的变化而变化,并参与交叉过程。

多目标优化问题与单目标优化问题有本质的区别:多目标优化问题需要寻求的不再是一个最优值,而是一组非支配解集。针对多目标优化问题,多目标差异演化算法(MODE)在中心差异演化算法的基础上作以下处理。

1.2.1 选择操作

MODE中父代与子代个体的相互关系有支配、被支配、互不支配三种,则MODE的选择操作如图1所示。

1.2.2 Pareto最优解集的构造及缩减

建立外部种群存储进化过程中产生的非支配解集,使用改进的快速排序方法构造Pareto最优解集,然后利用基于动态聚集距离的方法进行缩减。

改进的快速排序法[9]是快速排序法的改进版本,将快速排序法中的一个比较个体改为两个比较个体。第一个比较个体的含义与功能与原算法相同,第二个比较个体是每一轮比较中第一个与之互不支配或支配它但不被它支配的个体。如果在整个排序过程中并未找到第二个比较个体,算法退化为原算法;如果在排序过程中找到第二个比较个体,则这两个比较个体均参与与其他个体的比较,任何被这两个比较个体之一所支配的个体均被清除,只有同时不被这两个个体所支配的个体才能保留下来并进入下一轮比较。改进的快速排序算法比原来的算法具有更高的效率。

将外部种群大小限制在一个合理的数值M内,不仅避免随算法的进化,非支配解集无限制扩大而降低算法效率,也有助于选择出合适的最优解供使用。利用基于动态聚集距离[10]的方法对外部种群进行消减能保持外部种群的多样性和均匀性。当外部种群的数目大于M时,根据聚集距离一次清除聚集距离最小的个体,然后重新计算聚集距离,再清除一个聚集距离最小的个体,直至外部种群数量缩减到M。

1.2.3 约束条件的处理

通常,群体中第i个个体xi违反第d个约束条件的程度可表示为

式中,δ为等式约束条件的容忍度,一般取较小的正数。

则

$G(\mathit{x}{}_i)={\displaystyle \sum _{d=1}^{p}G}{}_d(\mathit{x}{}_i)$ (4)

表示个体xi违反所有约束条件的程度,也反映了个体xi在群体中的不可行性。

由于约束条件之间的特征差异,某些约束条件可能对个体的约束违反程度起着决定性的作用,此时,可通过标准化来平等地对待每个约束条件。在标准化过程中,首先找出群体中的个体违反每个约束条件的最大值G${}_d^{\max }$:

$G{}_d^{\max }=\underset{i=1,2‚\cdots ,{\rm N}}{{\displaystyle \max }}(G{}_d(\mathit{x}{}_i))1\le d\le p$

利用这些G${}_d^{\max }$可以标准化个体xi对每个约束条件的违反值,最后个体xi的标准化约束违反程度Gnor(xi)定义为该个体的每个约束违反标准值的平均值:

$G{}_{\text{n}\text{o}\text{r}}(\mathit{x}{}_i)=\frac{{\displaystyle \sum _{d=1}^p(}G{}_d(\mathit{x}{}_d)/G{}_d^{\max })}{p}$ (5)

使用随机排序法[11]对约束条件进行处理,即:采用参数Pf表示在不可行域中仅使用目标函数选择个体的概率,也就是说,当比较两个个体时,若两个个体都是可行解,则按照它们的目标函数值来选择个体,否则,参数Pf将决定是否采用目标函数或约束违反程度来选择个体。结合前文所描述MODE的个体选择操作策略,本文所使用的个体选择操作如图2所示。实验结果表明,当Pf=0.45时,随机排序法可以产生很好的优化效果。

1.2.4 MODE的实现

综上所述,MODE的实施步骤如下:

(1)初始化种群,计算每个个体的目标值,构造外部种群(对可行域的个体使用改进的快速排序法选择非支配解集并基于动态聚集距离对其消减),进化代数为0;

(2)按照中心差异演化算法进行变异、交叉操作产生子代个体;

(3)按照图2的方法进行选择操作;

(4)更新外部种群,将得到的可行域内的个体与外部种群合并,并对其按照改进的快速排序法选择非支配解集,基于动态聚集距离缩减其规模;

(5)分析进化代数是否达到所设置的最大进化代数,若是,输出外部种群.否则,进化代数加1,返回(2)继续运行。

1.3 算例分析

为了验证本文MODE算法的有效性,选择常用的多目标优化测试函数(Kur函数[9])来验证,并与常用的多目标遗传算法NSGA-Ⅱ(nondominated sorting genetic algorithm-Ⅱ)[4]和文献[5]中提出的多目标粒子群算法MOPSO(multi-objective particle swarm optimization algorithm)进行对比研究。Kur测试函数如下:

$\begin{array}{l}F{}_1(\mathit{x})={\displaystyle \sum _{k=1}^{{\rm N}-1}[}-10\exp (-0.2\sqrt{x{}_k^2+x{}_{k+1}^2})]\\ F{}_2(\mathit{x})={\displaystyle \sum _{k=1}^{{\rm N}}(}|x{}_k|{}^{0.8}+5\sin x{}_k^3)\end{array}$

式中,N=3,xk∈[-5,5]。

该函数具有离散特性,其Pareto最优前沿是由几个非连续的区域组成。三种算法设置相同的种群大小,数目为100,非支配解集最大个数为100,最大进化代数为400。MODE的缩放因子F每次在(0.1,0.9)之间随机选取,交叉概率Pc设置为[0.1,0.8]之间,并按照进化代数线性递增。MOPSO和NSGA-Ⅱ的其他参数设置按照文献[5]执行。可以直观地看出,MODE的结果具有更好的收敛性和分布性。对于其他如ZDT系列测试函数[9],MODE也表现出比MOPSO和NSGA-Ⅱ更好的收敛性和分散性。

2 3-TPT并联机器人结构优化建模

3-TPT并联机器人主要有上下三角平台和三个支链组成。上平台和下平台为相似三角形且平行配置,上平台为动平台,下平台为静平台。每个支链包括3个运动副,其中2个虎克铰分别与上下三角形平台定点相连,2个虎克铰的对应轴线平行,所以可约束动平台的转动,中间的移动副可在杆长的约束范围内做轴向伸缩运动,从而驱动上三角形平台实现三维平动。

2.1 工作空间计算

影响并联机构工作空间的因素有:(1)杆长限制;(2)运动副转角限制;(3)连杆间干涉;(4)奇异位形。为了简化问题,本文仅考虑杆长限制。利用蒙特卡洛方法求解并联机器人工作空间是基于并联机构位置的逆解。

建立图4所示坐标系,绝对坐标系OXYZ建立在固定平台上,O为△A1A2A3的外接圆圆心;X轴沿OA1方向;Z轴垂直于下平台指向动平台;Y轴由右手定则确定。动坐标系PX′Y′Z′建立在动平台上,P为△B1B2B3的外接圆圆心;X′轴沿PB1方向;Z′轴垂直于动平台向上;Y′轴由右手定则确定。令r1、r2分别为上下平台的外接圆半径。

3-TPT并联机器人机构的位置逆解方程[12]为

其中,P=(x,y,z)T为动平台位置中心向量;αe(e=1,2,3)为下平台各对应向量与X轴正向的夹角,βe为上平台各对应向量与X′轴正向的夹角,且αe=βe;le为各杆杆长。

使用蒙特卡洛方法[13,14]求解并联机构的工作空间是在一个包含并联机构工作空间的空间(采样空间)取大量的采样点,对符合约束条件的采样点赋值为1,其余点赋值为0。根据样本均值,依照概率收敛性定理,采样点的均值依概率收敛于并联机构工作空间与采样空间的比值,在某固定空间中大量的采样点的均值可以衡量并联机构工作空间的大小,值等于1的采样点数目也可以作为衡量工作空间大小的标准。

2.2 速度全域性能指标计算

以Cosselin等[15]提出的全域性能指标η作为评价机构在整个工作空间内运动性能:

$\eta =\frac{{\displaystyle {\int }_w\frac{1}{k{}_{\mathit{J}}}}\text{d}w}{{\displaystyle {\int }_w\text{d}}w}$ (7)

式中,kJ=cond(J)为一阶影响系数(或雅克比矩阵)的条件数;w为机器人机构的可达工作空间。

η值越大,机构的灵巧度和控制精度越高,性能越好。

简单的一阶影响系数可以通过对并联机构位置方程求导得出,复杂的可以使用螺旋理论推出,3-TPT并联机器人机构的雅克比矩阵逆阵为[12]

矩阵与其逆阵的条件数在数值上是相等的,在此使用雅克比矩阵逆阵和使用雅克比矩阵的结果是一样的。

式(7)是一个复杂的积分,解析法以及常规的数值方法均难以解出,本文使用蒙特卡洛方法[13]求其近似值。

2.3 优化模型的建立

3-TPT并联机器人机构的结构参数有r1、r2、αe、βe、Lmin、Lmax,其中固定参数r1=200,Lmin=300,θ1=α1=β1=0。为保证3-TPT并联机构的对称性,θh=αh=βh(h=2,3)。令γ2=θ2=α2=β2,γ3=θ3=α3=β3,则该模型有4个优化变量参数:γ2、γ3、r2和Lmax。当优化目标为工作空间V时、速度全局性能η值更大。加上约束条件得到模型:

$\begin{array}{l}\max f{}_1=V(\gamma {}_2,\gamma {}_3,r,L{}_{\max })\\ \max f{}_2=\eta (\gamma {}_2,\gamma {}_3,r,L{}_{\max })\\ \text{s}.\text{t}.\gamma {}_2+\gamma {}_3=2\text{π}\\ \gamma {}_3-\gamma {}_2\ge \frac{\text{π}}{6}\\ 230\le r{}_2\le 600\\ 450\le L{}_{\max }\le 900\\ \frac{\text{π}}{6}\le \gamma {}_2\le \frac{5}{3}\text{π}\\ \frac{\text{π}}{3}\le \gamma {}_3\le \frac{11}{6}\text{π}\end{array}$

3 优化结果及分析

蒙特卡洛方法的取样空间设置为:-1100<X<1100,-1100<Y<1100,0<Z<1100,求工作空间时取样点数目为105,以值为1的采样点数目衡量工作空间的大小。MODE的设置如下:群体规模N为80,最大进化代数Tmax为400,外部种群最大数量M为10,缩放因子F每次在(0.1,0.9)之间随机选取,交叉概率Pc在(0.1,0.9)之间按照进化代数线性递减。得到结果如图5所示。

从Pareto最优解的分布可以看出,工作空间和全局性能η是两个相互矛盾的目标,若要提高速度全局性能η,工作空间随之缩小,若扩大工作空间,速度全局性能η则随之降低。在进行优化设计中,如果单纯考虑以某一个性能为目标进行优化设计,得到的结果会使其他性能变得很差(如图5中Pareto前沿的边界点)。建立多目标优化模型,可以同时考虑对多个性能进行优化设计,使用MODE进行求解,能够获得分布良好的Pareto最优前沿供使用者选取。

4 结束语

本文基于工作空间和速度全域性能为目标建立了并联机构多目标优化模型,利用MODE对模型进行了求解。工作空间和速度全域性能的计算使用蒙特卡洛方法,MODE使用新的选择操作,利用改进的快速排序法和基于动态聚集距离构造非支配解集,并利用随机排序法处理约束问题。实验表明,该方法可以获得分布良好的Pareto前沿供使用者选取。

使用蒙特卡洛方法计算工作空间基于并联机构位置逆解模型,计算速度全域性能基于一阶影响系数,使用蒙特卡洛方法十分有利于计算机编程实现。这种并联机构结构多目标优化模型的建立方法不拘泥于3-TPT并联机器人,对其他并联机构结构多目标优化设计也有很好的借鉴意义。同时本文提出的MODE也适用于其他多目标优化模型的求解。

摘要：针对并联机构优化设计的复杂性,建立了多目标优化模型,并使用多目标差异演化算法(MODE)对模型进行了求解。在MODE中,使用改进的快速排序法构造外部种群,基于动态聚集距离对外部种群进行削减,使用随机排序法处理约束问题。以3-TPT并联机器人机构的工作空间和速度全域性能为目标建立了多目标优化模型,利用蒙特卡洛方法对两个目标进行了定量评价,并使用MODE实现了模型求解。多目标优化模型的建立对其他并联机构具有借鉴意义。实验结果也表明MODE是一种行之有效的多目标求解算法。