基于非均匀变异算子的状态空间进化算法

凌 哲，李茂军

(长沙理工大学 电气与信息工程学院，湖南 长沙 410114)

0 引 言

传统遗传算法是模拟自然界中生物进化，通过自然选择机制求解最适度值问题的一类自组织、自适应、自识别的人工智能技术，是人工智能和仿生计算技术相结合的产物，包括模拟了自然界中生物的进化过程的进化算法，模拟自然状态下某些生物群体群居行为的群体智能算法，为解决复杂程度高的多目标问题开辟了新的道路。但是传统遗传算法在实际应用中容易陷入一种早熟收敛的现象，算法控制参数比如迭代次数选择主要依靠经验。上述缺点很大程度上限制了遗传算法的实际应用，如何增加算法的收敛精度以及如何提升算法的收敛速度，是国内外学者积极探讨的问题。例如，文献[1]提出了不同于已有遗传算法的交叉和变异策略,即通过利用诱导和随机相结合的交叉和变异算子进行局部微调，使得种群的一部分个体采用诱导变异,其余个体采用随机变异;对搜索的初始时段采用随机线性组合交叉,结束时段采用部分确定性诱导交叉。文献[2]着重从交叉和变异算子的变换出发，通过增加种群的多样性和选择性，并且以提高算法全局与局部搜索能力加快收敛速度为目的，设计出了一种新的算法。文献[3]提出一种采用实数编码的基于状态空间模型的进化算法。状态空间模型的构建不仅能把种群信息以较少的信息量表述出来，而且能够清楚地表现出在迭代过程中个体的状态变化。文中算法通过构造一个状态进化转移矩阵来替代遗传算法中的交叉与变异算子功能进而产生一组新的群体，通过选种池的选择方式产生较优的群体。相较于遗传算法计算量大、易陷入早熟收敛、全局搜索能力差等缺点[4]，该算法有着计算量小、计算精确度高等优点。并可通过评估转移矩阵的范数来考察算法的全局收敛性和收敛速度[5-8]，突破了传统遗传算法的固有模式。

1 状态空间模型进化算法

1.1 算法概述

遗传算法逐渐成为寻找优化方式的路径，通过交叉、选择、变异三个算子来筛选出最优值。文中基于离散系统的状态空间模型，引入遗传算法的理念，构建基于状态空间模型的方程[9-11]，即

X'(k+1)=GX(k)

(1)

在该算法中，X(k)表示进化算法中的群体，X(k)为第k代群体，含有N个分量，每个分量均代表了1个个体，每个个体中包括了M个变量(个体是通过实数编码的方式产生的)。实际上，状态向量X(k)表示为一个N×M矩阵，矩阵的每一行可视为一个个体，每一个元素表示为变量的实数值。通过基于进化算法中的进化方式来构建状态转移矩阵，在此是通过运用遗传算法中的算子来构建状态转移矩阵G。先是通过随机产生的方式得到初始群体X(0)，在左乘矩阵G得到群体X'(1)，以此类推可到一系列的X'(1)，X'(2)，…。再让群体X'(k+1)和X(k)同时进入选种池内，选种池是按照物竞天择、适者生存的思想构建的，通过计算两个群体中2N个个体的适应度函数值，并选择其中较大的N个个体组成新的X(k+1)群体，然后置为式1中的X(k)，如此循环，直到满足最后的终止条件。通常建立为如图1所示的有选择性的闭环模式。

图1 基于状态空间进化算法的有选择闭环模型

1.2 状态转移矩阵的构造

状态方程G的构造是影响状态空间算法收敛速度和收敛性的决定因素，也是评价算法好坏的标准。状态转移矩阵G的构造可以拟用仿生算法中群体进化的基本方法进行，例如可以模仿遗传算法的遗传算子来构造状态转移矩阵，也可以采用其他算法或者数学方法[12-14]。对基于传统的遗传算法中的遗传算子构建状态转移矩阵做详细阐述。选择、变异、交叉是遗传算法中的基本操作，由于已经有了适应度评判函数，所以只需要在状态空间转移方程下体现交叉和变异的特点。对于实数编码下的情况，交叉操作一般选取个体间的算术均匀交叉方式，其状态空间转移矩阵方程为：

(2)

其中，0

父代种群经过左乘形如G1的状态转移矩阵后，便实现了遗传算法中个体的交叉操作。从中可得子代群体的1号个体是由父代群体中的1号个体和n号个体交叉产生，由此可推断出只要交叉参数不同，其产生的子代也将有所不同[15-17]。但是这里完全没有实现遗传算法中变异算子的功能，种群的多样性得不到较好的维持，算法容易出现早期收敛的现象。

为了实现种群的多样性，引入变异操作，将上述矩阵进行变换，如下所示：

(3)

其中，β=0.028+0.01rand()(经由实验确认)，rand()为在[0,1]符合均匀分布的随机数，父代群体左乘以形如G2的状态转移矩阵后，交叉和变异的遗传算子得以实现[18-19]。

2 基于改进的非均匀变异的状态转移矩阵

2.1 矩阵的设计

上述的状态空间转移矩阵的构造仅仅是基于两个个体间的交叉和单个个体多点变异的状态转移矩阵，并且种群的一号个体不能经过交叉产生，不能体现自然选择的特点。

本文以2007-2016年沪深两市全部A股上市公司为研究样本。样本公司的财务数据均来自CSMAR数据库。

为此将进行如下改进。

(4)

文中在此基础上改进之前的变异算子，使得种群尽可能地搜索到含有优良基因型的个体，同时为了避免陷入局部搜索的情况，由一个变异点变成三个点，最大程度上能够达到全局最优解。由于在选种池的操作中，选取2N个体里适度值大的N个个体并按适度值从高到低排列组成新的X(k+1)种群，这样下一代排列靠前的个体往往是最优个体。

(5)

其中，0

对照上述公式，εi的设置如下：

(6)

采用非均匀变异操作后，在原有最优个体附近区域进行微小搜索，能够精准快速到达全局最优解，并根据优胜劣汰的自然选择法则，以一定概率并入了算术交叉算子，使得适应度高的优秀个体能够以较大概率参与到下一次的迭代过程中。这样情况下的子代对父代的延伸程度越高，种群多样性也越高。

2.2 约束处理

在算法的迭代过程中，随着算法的搜索区域不断增大，可能导致子代的个体元素不在可行域的范围之内，故对其约束如下：

(7)

(8)

其中，[Umin,Umax]为变量的取值范围；ξ表示寻值的精度限定；<>表示向下取整。

3 仿真实验

实验的仿真平台为MATLAB 2013a。实验使用了2个经典函数进行测试，如下所示：

(1)Camel函数。

(9)

(0.089 8,-0.712 6)为最小值点，最小值为-1.031 628。

(2)Rastrigrin函数。

(10)

有多个极小值点，但只有一个全局最小值0，在(0,0)处。

在本次测试中，设定算法参数中的种群规模大小100，迭代的次数为60，每个测试函数运行50次。为了对比结果，实验采用两种算法进行比较，分别为一般状态转移矩阵下的状态空间进化算法(evolutionary algorithm based on state-space model，SEA)和基于改进的非均匀变异转移矩阵的状态空间进化算法(state-space evolutionary algorithm based on non-uniform mutation，NUMSEA)。对以上两个测试函数分别从平均最优解、平均收敛代数、标准差(平均最优解与全局最优解之差)等方面进行比较。

结果如表1所示。

表1 测试结果

图2和图3分别显示了运用文中算法(NUMSEA)对求解上述函数优化问题时所得的最优解对应的适应度函数值随迭代次数变化的曲线。

图2 求解f1优化问题时适应度函数值变化曲线

实验结果表明，NUMSEA算法在2个函数的优化中明显优于之前所述的SEA算法，算法的收敛速度相对较快，且最优值更为接近理论值，并且能在短时间内精确定位，充分体现了其高效性。通过50次的测试可以看出，在平稳性方面较之前的算法有较大的提升，计算量上有一定程度的缩减，如果能适当调整其控制参数，或将具有更好的全局搜索能力。

4 结束语

为了精准地从大数据环境下样本化、随机化的数据中提取有效信息，设计了一种具备伸缩性与并行处理功能的算法。针对一般转移矩阵下状态空间进化算法的不足，提出了一种基于非均匀变异的状态空间进化算法。通过引入改进的非均匀变异算子实现种群多样化，在一定程度上提高了算法的收敛速度与收敛精度。经过对2个多峰值的经典函数的优化实验，证明了该算法的可行性与稳定性，表现出了比较突出的寻优性能，缩减了处理数据的时间。虽然仿真实验结果令人满意，但是仿真环境是设为一个理想的条件下，并且实验的次数是有限的。因此，进一步构造更为良好的状态转移矩阵，以及验证算法的全局收敛性和空间遍历性，仍需要进行不断研究。