Mind Evolutionary Computaion

admin管理员组

文章数量:1532739

2024年1月23日发(作者：)

Construction Methods of Basal Evolutionary Operators of

Mind Evolutionary Computaion

Xiaojuan He1 , Jianchao Zeng2Department of Mathematics, Taiyuan Heavy Machinery Institute,Taiyuan 030024

(Email: hxj701104@ )

2)Division of System Simulation and Computer Application,Taiyuan Heavy Machinery Institute,Taiyuan 030024

Abstract MEC, Mind Evolutionary Computation presented in Literature[1] has much superiority for solving premature

convergence problem of genetic algorithm and no-numerical optimization .The method is a new algorithm, the mature evolutionary

operators haven’t come into being, so that the efficiency is lower. For the problem that the characteristic can been discrete, the concept

of Information Matrix is introduced, the construction methods of the generic similartaxis and dissimilation operators are given in the

paper, the coding method for this kind of problem is solved, the theory is more perfect, and the effectiveness is proven through the

computing examples.

Keywords MEC Information Matrix Evolutionary Operators

1)思维进化算法的基本进化算子的构造何小娟 曾建潮1）*1 2太原重型机械学院数学系，太原 030024

2）太原重型机械学院系统仿真与计算机应用研究所，太原 030024

摘 要 文献[1]提出的思维进化算法(MEC)，对于解决遗传算法存在的早熟及在非数值优化中应用困难等问题均显示出了明显的优越性，但由于该算法是一种新算法，目前还没有形成成熟的统一进化算子，而要针对具体问题进行构造，给求解问题造成一定的困难。本文针对特征可以离散化的一类问题，引入信息矩阵的概念，给出了一种通用的趋同算子与异化算子的构造方法，解决了算法对此类问题的编码问题，进一步完善了算法的理论。并通过计算实例说明了方法的有效性。

关键词 MEC 信息矩阵 进化算子

1.引言

文献[1]提出的思维进化算法是模拟人类思维进化过程的一种新算法，该算法借鉴了遗传算法中的“群体”与“进化”概念，引入“趋同算子”与“异化算子”，在解决遗传算法求解时存在早熟的优化问题及难解问题时，显示出了明显的优越性，并在很多领域得到发展，它除了能够解决数值优化问题、非数值优化问题，还可以进行群体行为仿真。由于思维进化算法是一种新算法，许多工作还需进一步研究探索，针对各种具体问题，目前还没有一个通用的进化算子对问题进行编码，本文在思维进化基本思想及框架的基础上，针对其特征可离散化问题的一类问题提出了一种通用的统一趋同、异化算子，并给出了具体的信息记录方法,使得思维进化算法在理论上又向前迈进了一步。

2.思维进化算法的基本结构框架

MEC算法的结构及详细介绍参阅文献[1] ，算法结构的基本框架如图1所示，下面给出MEC算法的简要介绍：

1)群体初始化。初始在解空间随机产生N个个体，并从中选择M+T个优胜者。

国家自然科学基金项目（资助号：60174002），山西省青年科学基金项目（资助号：20031031）

*

环用于子群体间境的信息交换同子群体A全局公告板时记录子群体的进化信息记录子群体的进化信息子群体通过分析子群体B子群体得局部公告板分提供环个体X1,X2,...,Xj...知识提取系统境信息并指导产生新子群体图算法结构基本框架

2）以每一个优胜者为中心，分别产生NM+T

个个体，构成M个优胜子群体,T个临时子群体。

3）趋同操作。在每一子群体内，计算每一个体的得分，得分最高者为优胜者，并把优胜者的得分记录到全局公告板和局部公告板上。其余个体以一定的方式向优胜者学习，产生新的子群体，重复上述步骤，直到子群体成熟，即新优胜者的得分的不到进一步改善。并将优胜者的得分定义为该子群体的得分。

4）异化操作。在每个子群体之间进行全局竞争，被放弃的临时子群体的个数记为Tr，被放弃的优胜子群体的个数记为Mr，在进化信息及全局公告板的指导下，在解空间中重新产生Tr+Mr个临时子群体，并在每一临时子群体内进行趋同操作。

重复上述步骤，当最优胜者的得分得不到进一步的改善时，则认为收敛。

3.趋同与异化算子的构造

一个个体的结构由能表示此结构特点的若干特征组合而成，每个特征又可由若干子特征来描述。群体中, 如果个体x满足f(x)=max{f(a1),f(a2),...,f(an)},其中，f(x)为个体得分,则称x是群体的优良个体，优良个体所包含的特征称为优良特征。我们知道，趋同与异化操作就是充分利用优良子群体的优良特征，以优良特征产生的信息来指导个体间的学习。基于上述思想，我们针对特征可以离散化表示的一类问题设计了一种通用的趋同与异化算子。

3.1编码

在一个个体中，设一个个体的结构可表示为Ai...An。Ai表示该个体所包含的第i个特征，

i=1,2,...n。并对每个特征所处的位置进行排序，让每一个特征与个体所有可能的取值相对应。我们要解决的问题就

是：一个个体的特征到底对应可能取值中的哪一个值，才能使个体得分达到最高。每一个特征对应的所有可能值可表示如下：aim，同时使其与一个概率向量相对应，Ai→pim。其中pil表示在第i个特征的位置上出现值ail的概率。则一个个体的信息可用一个信息矩阵表示如下：

⎧⎪p11p12"p1j"p1m⎫⎪p21p22"p2j"p⎪2m=⎪⎪⎨"""⎪mP⎪⎪且满足∑pij=1 （1）⎪pi1pi2"pij"p⎬

im⎪⎪j=1⎪"""⎪⎪⎩pn1pn2"pnj"p⎪nm⎪⎭i=1,2,...n,j=1,2,...m

记信息矩阵中每一列的位置为ci1,ci2,...cim，并分别代表相应取值ai1,ai2,...aim，即cij→aij。这样，针对一个问题的编码就完成了。

3.2 趋同算子

3.2.1产生新个体

在趋同过程中，希望充分利用并保留子群体中优良个体的特征，并以此特征对应的信息来指导个体之间的学习。在一个子群体内部，首先计算所有个体的得分并找到优胜者，将优胜者对应的信息矩阵记录到局部公告板上，完成信息记录后，就以当前信息矩阵为指导，采用轮盘选种法产生新一代个体。具体步骤如下：

设某一优胜者的取值为a11'a22'...amm',对应的信息矩阵为P*，依此信息矩阵为指导产生新个体的步骤如下：

①对应信息矩阵的每一行，依次累计各特征出现的概率值，得相应的累计值Si，最后一个累计值为Sm，且Sm=1

②在[0，1]区间内产生均匀分布的随机数r

③依次用Si与r相比较，第一个出现Si大于或等于r

（r≤Si）的节点被选中

④重复上述②、③ 直到产生整个子群体个体。

3.2.2产生新的信息矩阵

计算个体得分，找到新的优胜者，并针对其特征所对应的值产生新的信息矩阵。变化原则[2]为：在某一位置上，若优胜者的取值与局部公告板上信息矩阵对应位置上的值相同，则相应的概率增大，若与优胜者的不同，则概率减小，设参数λs∈（0-1）之间的调节参数，调节信息矩阵中概率值的变化程度，当样本数太大时，λs变小，使得概率变化程度加大，加快个体的收敛速度。K

为个体的最大特征数或最大可能取值个数,具体步骤如下：

在算法中对任意状态X∈E,Y∈E，其状态转移概率如下： （5）

⎧p⎪p*λsλsij×(1−a*ij=cij'ij'=⎨⎪*(1−λK)+K （2）

s*⎩pij×K)aij≠cij'且在局部公告板对应位置上，若出现某一值的次数越多，对应的概率就越大，可以证明，经过多次迭代后，仍然满足∑mpij=1。保证了算法的收敛性。重复上述步骤，直j=1到子群体成熟，即在信息矩阵中的每一行都有一个pil已经十分接近1。

3.3异化算子

在全局竞争中失去竞争能力的子群体被淘汰，在异化过程中重新产生相等数量的新子群体。异化过程类似于人类的发明创造过程，在前人知识积累的基础上，结合当前知识进行创新的过程。为此让子群体的信息结合三方面的信息产生，即按参数ωg吸收全局公告板的信息，按参数ωb吸收当前优胜子群体的信息，按参数ωr进行创新,参数满足ωg+ωb+ωr=1。具体步骤为：

p*'i=ωg⋅pi+ωb⋅pi+ωr⋅pD （3）

其中po为根据具体问题的特征选取的创新概率。然后以此信息为指导，产生新个体组成新群体，并参与全局竞争。从而完成异化过程。

4.算法收敛性分析

设离散空间的优化问题为(Q)，那么由本算法设计的趋同、异化算子的MEC算法产生的{XK:K≥0}依概率1收敛于整体最优状态。

证明：设E为解空间（为Rn中的离散点集），SE为随机映射：E×Ω→En，SE(X,p)=(Xm)表示以一个体X对应的概率p为指导，产生m个个体。趋同算子产生子群体的迭代过程是：X(k+1)=S(X(k)),由于S是随机映射且第k+1代种群的生成仅与第k代种群的优胜者有关，与具体代数k的值无关，又由于解空间为有限离散空间，因此子群体的迭代序列是一个以E为解空间的有限齐次马尔可夫链。由于初始状态是均匀选取的，故每个状态的初始概率分布为:

p0=(1,1,...,1

nnn)（4）

P{S(X,p)=Y}=⎧⎪⎪0g(Y)＜g(X)⎪⎨P{S(X,p)=X}×(1−λs)+λs(Y)≥g(X)且包含X的特征⎪⎪P{S(X,P)=X}×(1λKKgs⎪⎩−K)g(Y)≥g(X)且不包含X的特征

设离散状态空间E中的状态{Xm}按其适应度值的大小进行排序.若g(X1)>g(X2),则X1>X2，则趋同算子的一步概率转移矩阵为：

⎧p0⎪11"0⎫P⎪p21p22"0⎪⎪ij＞0（i≥j）,p11=1（6）

s=⎨⎪"""⎬且p"⎪⎪⎩pn1pn2"0⎪⎭由于概率矩阵是随机矩阵，可知其极限矩阵为：

⎧10⎪"0⎫P∞=⎪⎨p∞210"0⎪⎪ （7）

s⎪""""⎬⎪⎪⎩p∞n10"0⎪⎭则

P∞=P0P∞s=(1,0,"0)

由此证明序列

{

XK

:K

≥

0

}

依概率

1收敛于整体最优状态。

5.仿真实例

实验一：

为了验证本算法的有效性，我们作了实例仿真。设初始网络规模为一个具有 ：一个输入层、三个隐层（每个隐层最大包含5个隐节点）、一个输出层的五层网络。首先对问题进行编码，一个神经网络的隐层数及所包含的隐节点数决定着网络的性能。此网络中包含三个隐层，因此设该问题包含三个特征（隐层），每个特征对应取值为隐节点个数。选了三个逼近函数，群体规模N=40,分为四个子群体，其中，优胜子群体NS=1,临时子群体NT=3。BP算法训练权值时的训练最大次数为6000， 步长η=0.3, 误差精度ε=0.001。MEC中，两代之间的影响系数λs=0.3，∂=1,

β=1，最大进化50代。对每个目标函数作50次仿真，结果如表1。

表1：仿真结果

函数 收敛收敛收敛结构次数概率

f(x)=1sinx+x3+1

111 50 100%

f(x)=1(x3+1)+1((x+5)3+x3+1)

112 49 98%

f(x)=0.5+0.4sin2x

113 49 98%

从表中可以看出，本算法以几乎接近1的概率收敛于优化结构，我们同时还做了几个例子，结果也都比较理想,说明了算法的有效性。

实验二：

本实验选取最大隐节点数为20的一个网络结构。采用本文的方法对其进行编码。径向基函数神经网络的隐节点数及其所对应的中心参数决定着网络的映射性能。设该网络包含20个特征，每一个特征对应的所有可能取值为中心参数的取值。选取很多函数作为试验对象进行了仿真，表中列出了四个函数，函数如下：

1）f=0.01×{1[(x−0.3)2+0.01]+1[(x−0.9)2+0.04]−6}

2）f=1(x2+1)+sinx[1(x+1)+1(exp(x)+1)]

3）f=0.6+x[1((x+5)2+x2+1)+(x−2)2]

4）f=0.5[1(2x+5)+1(sinx+x3+1)+1(x2+1)]

从表中可以看出，本算法的运行结果均以较高的收敛性收敛于优化结构，在动态优化网络结构的同时，也优化了中心向量和权值，同时优化结构的隐节点数都比较小。同时还可以看出，采用两种方法训练权值时。不足之处为，当取值过多时，信息矩阵规模也随之变大，使得个体成熟的时间变长，同时使训练时间变长，影响了训练速度。

从上述实验可以看出，本文的编码方法确实可以解决一类其特征可以离散化的非数值优化问题。

表2：仿真结果

函数

函数1

函数2

函数3

函数4

MEC

LMS

6

6

18

18

90%

90%

5

6

0.0130280.023104MEC

LMS

5

5

19

18

95%

90%

7

10

0.0195480.025439MEC

LMS

6

8

19

16

95%

80%

6

8

0.0098150.014119权值训练方法

MEC

LMS

8

10

18

16

90%

80%

8

12

0.0096030.011623隐节点数

收敛收敛平均收敛代数

泛化误差参考文献

[1]

Chengyi Sun, Yan Sun and Lijun Wei, Mind-Evolution-Based

Machine Learning:Framework and the Implementation of

Optimization, IEEE Intelligent Conference on

Intelligent Engineering Systems,1998,355-359.

[2] 查凯，曾建潮，求解TSP问题的思维进化算法,《计算机工程与应用》，2002. 4. 102-104.

次数 概率

本文标签： 群体算法信息问题个体