协同进化算法

2024-10-05

协同进化算法（精选8篇）

协同进化算法篇1

协同进化算法是基于协同进化理论出现的一类新的进化算法, 其在传统进化算法强调个体与个体之间因环境原因所产生的竞争的基础之上, 进一步考虑多个种群之间、种群与环境之间的在进化过程中的协同作用。目前通常使用的协同进化算法主要可以分为两类:以种群竞争的方式加速算法收敛和使用种群合作的方式保持种群多样性。但是这两种方式都只是强调了协同进化中的一部分, 都存在其不足。在大自然生物们个体之间的协同进化过程中, 竞争、合作这两种相互矛盾的关系往往都是同时存在的。只有强者才具优先交配的权利, 以遗传下自身的基因, 其他处于弱势的个体会团结起来与其对抗, 达到留下自身基因的目的。刘静在她的博士论文《协同进化算法及其应用研究》中基于种群竞争和合作思想构建了MOCEA (Multi-objective Coevolutionary Algorithm) , 通过竞争特性算子——吞并算子来达到使得优秀的基因得到广泛的传播和保持种群基因的多样性, 并得到很好的效果。但由于刘的思想仍然是主要依靠种群合作来达到加速收敛的目的, 其所采用的竞争特性算子——吞并算子对其算法进化并没起到决定性作用。

1 算法设计

1.1 算子设定

为实现上文所提到的目的, 首先给出以

定义2.1:

式中ci代表每个子种群的个体在全局非支配集中所占的个数, 为Pareto最优解集, k代表总的种群个数, 这样li可以称为该子种群的优势度。若存在ci=max{cm}, 则称子种群i为优势种群, 其他种群为弱势种群。

同样, 优势种群在面对可以战胜外部强敌 (即全局约束条件) 的情况下, 尽可能的保存弱势种群的存在性以满足种群的多样性。那么根据式 (2-1) 给出责任度的定义。

首先假设在当前进化过程存在某一子种群为Pt, 而Qt为该子种群在Pareto最优解集中的集。基于多目标优化理论可以知道在子种群Pt在其最优解附近或许可能存在着更优秀的解。基于此理论给出合作算子对Pareto最优解进行局部爬坡操作。

1.2 合作算子

设现有两个父代子种群

其中i=1, 2, 3, …, n通过合作算子的作用, 让两个独立在不同决策空间搜索的子种群Pa和Pb相互引进对方的优秀基因, 以扩大算法的搜索区域。

1.3 竞争——保护算子

设现存在总种群的总个体数为N, 经过第n代进化的种群中每个子种群的优势度分别为, 则其下一代每个子种群的规模大小为, 如果经过计算下一代中的某个子种群的优势度低于预设值, 则清除该子种群。若该子种群由于外部条件必须得到保护, 则根据其他子种群的责任度对该子种群给予保护。

1.4分裂算子

当某个子种群Pt={x1, x2, …, xn}中的个体数目过大时, 该子种群多数个体不易引入其他种群的优势基因, 仅依靠自身种群内部进行的独立进化, 这样种群的多样性会较快的消失, 使得算法发生早熟。设计分裂算子如下:

其中t代表该种群进化的代数, G (0, 1/t) 为满足高斯分布的随机数。

1.3.1 测试函数一

该测试函数为一带约束条件两目标函数, 其主要用于测试多目标优化算法在pareto前沿的收敛的能力。

从表3.1可以看出CCEA算法在Spreed这个指标上具有很大的优势, 从图3-1也可以看出CCEA算法比NSGAII算法在这个测试函数的计算上具有更大的优势。

1.3.2 测试函数二

该函数为带约束的两目标测试函数, 在其约束条件内含有两个可调变量a、b, 本文选取a=0.1, b=16来对CCEA算法和NSGAII算法进行测试。该函数的PFtrue曲线为三段相互之间不连续的曲线, 在对多目标优化算法测试时, 通常对中间一段进行关注, 其主要特点在于这个区段的部分点不易被搜索到, 性能较差的算法在这部分通常表现为断开。该函数因此可以检测算法在pareto前沿的搜索能力。

由表3.2可以看出CCEA算法除了在GD这个指标上占优势以外, 在其他两个指标上并不占优势, 甚至在Spreed这个指标上略有不如。但从图3-2看出来在中间一段曲线上CCEA算法搜索出来的为一条连续曲线, 而NSGAII算法在这部分是断开的, 这可证明CCEA算法对pareto前沿解的搜索性能要强于NSGAII算法。

2 结论

本文基于本文利用大自然中种群竞争和合作的特性, 基于大自然中种群首领在种群遇到外部危险时会对整个种群进行保护的特点, 引入优势度和责任度的概念。提出一种个体之间相互竞争和协助的协同进化算法CCEA来控制各子种群繁殖的数量, 在总的种群个体数量一定的前提下, 使得优势种群拥有更多的繁殖机会, 达到扩大搜索空间的目的, 并迫使弱势种群更多的引入其他种群的优秀基因, 达到增强自身优势度的目的。通过测试报表明该算法可以显著的提高其搜索性能, 对于复杂的多目标优化问题具有较大的实用价值。

摘要：本文基于大自然进化过程中种群之间、种群与环境之间的在进化过程中的协同作用, 提出一种个体之间相互竞争和协助的协同进化算法CCEA (Coexistence co-evolutionary Algorithm) 。基本思想为通过优势度和责任度概念, 来控制各子种群繁殖的数量, 在总的种群个体数量一定的前提下, 使得优势种群拥有更多的繁殖机会, 达到扩大搜索空间的目的, 并迫使弱势种群更多的引入其他种群的优秀基因, 达到增强自身优势度的目的。通过计算表明能有效的增强算法的搜索性能。

关键词：协同进化,多目标算法,多目标优化

协同进化算法篇2

二、文献选读内容分析及思考

（一）Borg算法

Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。1.创新点

1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。

2）提出了ε归档进程，能提高算法计算效率和防止早熟。3）种群大小的自适应调整。

4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。2.Borg算法原理

1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。

2）ε归档进程

如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解

1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。

图1 ε支配网格

在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。

3）重启

自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。

4）交叉算子的自适应选择

摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K种交叉算子，选择概率最开始是相等的，设n表示各类交叉算子产生的后代属于ε归档进程所得个数，个数越多，选取相应交叉算子的概率就越大，逐渐趋于选择解决未知现实问题的交叉算子。3.Borg算法总体流程

通过交叉算子的自适应选择选择一种交叉算子，假设所选交叉算子需要K个父代，1个父代在归档集中按均匀分布选择，K-1个父代从种群中按锦标赛选择（大小按上述第3步中计算），交叉产生一个后代，如果这个后代pareto支配种群中一个或多个个体，则随机的取代一个；如果被种群中的任一个体支配，则不能加入种群；如果互不支配，也是随机的取代种群中的一个。而加入归档集，是按照上述第2步实施的。如此循环一定代数之后，看达没达到第3步重启的条件，达到则重启过程开始，直至满足终止条件。4.思考

1）ε盒支配时，同一网格内的点只是比较离中心点距离最近的，这就有一个不足，最近的不一定是非支配解，离的远的点有可能还支配它，我觉得还需要比较一下哪个解优的目标维数多。

2）设计一种云交叉算子，加入到交叉算子的池子里，或是参数控制云交叉算子替换其中的能达到类似效果的几种算子，便于统一。

（二）基于模糊支配的高维多目标进化算法 1.算法简介

基于模糊支配的高维多目标进化算法[33]是对模糊支配关系的一种改进，2005年M.Farina首次提出的模糊支配，其隶属函数是一条正态分布函数，如图2所示，而此文的隶属函数是一条半正态分布函数，表达的概念更加清晰。

图2 正态隶属函数

对于最小化问题，归一化后的解A（a1,a2,...,aM），B（b1,b2,...,bM）如果目标向量的某一维上的差量（ai-bi）达到-1，则ai好于bi的程度为1，即pareto支配关系下ai支配bi；如果差量（ai-bi）是1，则pareto支配关系下bi支配ai。A模糊支配B程度为每一维差量映射下的隶属度之积，与种群中其他解进行比较，所得隶属度相加即为A解在整个中群众的性能好坏程度，相当于NSGA-II中的非支配排序，只是这里的等级程度更加细分，然后还得设置一个阈值α，即模糊支配隶属度达到多少才能是最优解，也就是NSGA-II中的非支配排序等级为1的解。设定这个值是关键，此文献也对这个值得选取进行了实验说明，针对不同的问题选取不同的值，但是还没能达到根据问题特性自适应调整。2.思考

1）既然隶属度函数不是一成不变的，想用云模型确定隶属度，借鉴张国英《高维云模型及其在多属性评价中的应用》构造一M维云模型，它的作用是输入M维差量映射为一维的模糊支配隶属度u，无需像上文中求出每一维隶属度再相乘。

2）由于阈值α不好确定，可不可以根据归档集的大小取前N个，找到使个体数量大于等于N的u值为α。

（三）基于网格支配的高维多目标进化算法

GrEA[34]也是针对ε-MOEA算法进行改进的，作者认为ε-MOEA算法中的网格划分是基于个体的，如果个体分配不均匀，也就不能得到分布性好的最优前沿，而且网格的大小也不能随着目标空间的特性而自适应调整。1.支配关系创新

grid-dominance，这种支配关系是基于空间区域划分网格，就是在当代种群中找出每一个目标函数上的最大值与最小值（下图上行），然后根据这两个值计算出这个目标函数的网格上下界值（下图下行）。人为设定每一个目标函数需划分的段数div,是一个固定的值，这样就使得收敛性与多样性的要求随着算法进程自适应调整，比如说刚开始时目标空间的个体分布比较广，就需要大的网格来选择个体，随着算法深入，个体更加集中于Pareto前沿区域，就需要小的网格区分个体，更加强调个体的多样性，因此这样动态的网格划分更能体现算法的进程。另外，ε-支配强调个体生死，只有非支配才能加入归档集；而grid dominance不同，它更强调个体的先后，非支配个体只是先于支配个体进入归档集，支配个体还是有机会加入归档集，这在一定程度上保留了边界点，而ε-MOEA算法会丢失边界点。

图3 网格分段示意图

2.适应度值指派创新

本文提出了适应度值指派的三个指标grid ranking(GR)、grid crowding distance(GCD)和grid coordinate point distance(GCPD)，GR和GCPD是收敛性评价指标，GCD是多样性评价指标，网格指标如图4所示。

GR表示个体所处网格各维目标函数坐标之和，相当于将目标向量各维相加，只不过这里是将函数值映射为所处网格坐标值之和。比如下图A点的网格坐标为（0,4），则GR=0+4=4。

GCD是网格拥挤距离，以往的网格拥挤距离都是在一个网格之内的，这样就不能反映分布性了，此处的GCD还考虑临近网格的个体，用网格坐标的差量之和评估，之和越小的GCD值就越大，多样性就越差。如下图C的邻居是B、D，F的邻居是E、G。

GCPD表示的是同一网格内与中心点的距离，这一点与ε-MOEA中相同。比较的先后准则是GR，GR相同比较GCD，GR、GCD都相同则比较GCPD。

图4 网格指标示意图

3.归档策略的改进

以往的归档策略都是基于适应度值的支配关系选择删除，这样会导致解集多样性的缺失，因为相邻的点具有相似的适应度值，会使他们同时被选择或删除，比如上图的E、F、G，这样多样性会得不到保证。本文作者对归档策略进行了改进，就是当一个个体加入归档集时，在归档集中和它相关的个体GR值会受到惩罚，相关的个体包括：1.处于同一网格坐标 2.被网格支配的 3.邻域个体，惩罚力度依次减小。

（四）基于坐标转换的高维多目标进化算法

针对原始的密度评估算子在高维多目标中会出现不能很好的兼顾收敛性与多样性，解集往往会有很好的多样性而收敛性差的缺点，论文设计了一种包含收敛性的密度评估算子shift-based density estimation(SDE)[35]。比如图5中的A点，按照基于pareto支配的多目标优化算法来看，是非支配解切多样性好于B、C、D，但很明显得看出A点收敛性不及BCD。SDE是将各维目标函数上小于A点对应维的值转化为A点那一维的函数值，如下图所示。转换之后A点的密度值较大，而BCD密度值较小，符合所考虑的情况

图5 坐标转换示意图

从图6的四图中可以看出，只有收敛性和多样性都好的个体，其SDE值小，即其值不仅体现密度信息，而且将收敛性信息也包含在内。SDE是一种通用的密度评估算子，可以将其植入NSGA-II，SPEA2和PESA-II中。

图6 拥挤密度示意图

（五）基于角点排序的高维多目标进化算法

本文是在非支配排序上的改进。在高维多目标优化问题中，随着目标维数的增加，非支配解之间的比较次数是非常大的，因此论文提出了角点支配。所谓的角点指的是在M维目标空间中只考虑其中k个目标，在本文中只考虑一个目标函数上的，因为在一个目标函数上最好的点肯定是非支配解。二维、三维角点分别如下图所示。

图7 二维、三维角点示意图

找到角点后，所有被角点支配的点就不用比较了，大大减少评价次数。而且本文还指出非支配解排序的比较次数应该是精确到每一维的目标函数的比较上，因为每两个解之间目标函数的比较次数从2到M，也就是说不同的两个解之间比较所花费的计算量是不同的，只计算一个解与其他解的比较次数是不对的。角点支配排序大致过程如图8所示。

图8 角点非支配排序

图8是2维目标函数的情况，首先得找出每一维目标函数上最好的点，如上图A中的白点，标记他们所支配的点如上图阴影区域，这些点在当前等级中就不考虑排序了，在剩下的点中再寻找两个角点，直到将所有的点都标记，如图B，B中白点表示等级1，等级2、3依次进行。

（六）NSGA-III算法系列文献 1.MO-NSGA-II 为了适合解决高维多目标问题，Kalyanmoy Deb针对NSGA-II的缺点，提出了MO-NSGA-II（many-objective NSGA-II），这是NSGA-III的雏形。MO-NSGA-II的基本框架和NSGA-II差不多，不同之处在于精英选择机制上，因为原有的选择机制对快速增加的非支配解已经没有选择压力。MO-NSGA-II是一种基于参考点的多目标算法，放置分布性好的参考点，使得到的非支配解靠近这些参考点，就能得到分布性好的最优前端。

让我们回顾一下NSGA-II，有一个大小为N的当前种群Pt，由他产生的子代种群Qt，大小也为N，然后对Pt、Qt的合集Rt进行快速非支配排序F1、F2...Fi,将这些点按等级加入下一代种群Pt+1，通过对Fl中个体计算拥挤距离按降序排列，依次加入Pt+1，直到种群大小为N。

参考点的设置就是从这里开始，取代原有的拥挤距离。均匀分布的参考点可以通过一些特定的系统产生。

1）超平面的建立。设F1、F2...Fi的合集为St，在这个集合中找到每一个目标函数值最小的点组成理想点zminminmin(z1min,z2,...,zM)，将目标函数值转化为相对的minf‘i(u)=fi(u)zi，然后种群中的点通过一个聚集函数求最小值（它是相对于在某一维坐标轴上的参考点的）把它当成这一维的端点，通过这M个端点构造超平面，根据这个超平面重新计算参考点，这个超平面在每一代中都不同，所以它是可以根据种群特性自适应调整。

2）选取低拥挤度的解。为了确定解集拥挤度，需要把所有的点投影到超平面上（如图9左图），找到与之距离最近的参考点，这样每个参考点就会有一定数量的解与之相关联（如图9右图）。选择参考点周围个体最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1。再选出个体数次最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1，直到加满Pt+1。

图9 关联操作

3）锦标赛选择。当Pt+1形成，用锦标赛方法产生后代Qt+1，具体操作是从Pt+1任意挑选两个解，比较策略是如果一个解的非支配等级小于另一个解，选择前一个解；如果同处一个非支配等级但是所属参考点的拥挤度不同，选拥挤度小的点；如果非支配等级和所属参考点的拥挤度都相同，则选ASF值小的。然后采用模拟二进制交叉算子，产生后代Qt+1，然后在合并进行第一步，依次循环。2.NSGA-III 本文作者针对上文提出的MO-NSGA-II作了适当改进，提出了NSGA-III。1）超平面的建立。与上文不同的是，本文将超平面进行了归一化处理，找到基于坐标轴上的参考点的每一维端点zmax后，还必须将组成的超平面延伸相交于fi，坐标系，截距为ai，如图10所示。

图10 端点归一化示意图

2）个体与参考点的关联操作。上文中是将个体投影到超平面上，而此文是个体与参考线方向的垂直距离（参考线方向是参考点与理想点的连线方向），如图11所示。

图11 关联操作

3）小生境保留操作。此处本文与上文有个很大不同，本文只计算排除Fi的St，的小生境数，选出围绕参考线个体为0的参考线，如果有多条则任选一条，即0，这样Fi个体就有两种情况。第一，Fi中有一到多个个体与参考点j相j关联，这样就选一个与参考点j垂直距离最短的个体加入下一代种群Pt+1，加

j1。第二，如果，Fi中没有个体与参考点j相关联，则这个参考点在当前代就不用考虑了。如果0，则从Fi中与参考点j相关联的个体集合中任选一个，jj加1。重新调整小生境数，直到加满Pt+1。3.C-NSGA-III 上文提出的NSGA-III是处理无约束的问题，本文为处理约束条件，对NSGA-III进行了改进。1）精英选择操作上的改进，用约束支配取代pareto支配，和NSGA-II为处理约束条件的约束支配原则是一样。此时的种群一般既有可行解，还有不可行解，如果可行解的个数NfN，那么还需要从具有最小约束违反度的不可行解中选取个体加满Pt+1；如果NfN，则按照无约束的NSGA-III精英选择操作进行，接着也要用Pt+1中可行解更新理想点和端点。

2）子代种群生成。锦标赛选取规则是任选两个解，如果一个可行解，一个不可行解，选可行解；如果都是不可行解，选约束违反度小的；如果都是可行解，任选一个；这样选择出一个父代，再进行一次，选出另一个父代，模拟二进制交叉，然后变异。

但是通过实验发现上述算法有个不足，由于约束条件的存在，可行区域可能只是整个区域的一小部分，然而参考点是均匀的分布在目标向量空间，导致不是每个参考方向都能与最有前沿面相交，也就是说有一部分参考点是没用的，而用到的参考点会与多个个体相关联，又不能达到好的分布性，如图12所示。

图12 参考点自适应调整

这就涉及到一个问题：如何使所有的参考点能均匀分布在可行区域上，理想的方法是能分配所有的参考点均匀地分布在最优前沿面，但是对于不同的问题最优前沿面是未知的。于是本文作者提出了自适应的NSGA-III，叫做A-NSGA-III，让它能够自适应鉴别出无用的参考点然后分配他们，希望能找到新的最优解。于是在原有的NSGA-III生成大小为N的Pt+1后，有两个新的操作1.增加新的参考点 2.消除无用的参考点。

1）增加新的参考点。由于参考点个数等于种群规模，理想情况是一个参考点一个个体，当参考点j方向的小生境数j1，则必存在参考点k方向的小生境数，k0。我们针对参考点j，在其周围增加M个参考点的单纯形（单纯形法是一类在小范围内具有更精细搜索效果的优化算法，能提高点的多样性），如下图所示三维空间中具有三个顶点的单纯形扩展。

图13单纯形扩展法

但是扩张的点有两种情况是不接受的：1.不在第一象限 2.在参考点集中已经存在

2）消除无用的参考点。扩张完后的参考点可能存在一些无用的，则消除那些j0的扩展点，而原始的参考点j0是要保留的，有可能下一代就有用了。4.A2-NSGA-III 论文针对A-NSGA-III的四点缺点进行了改进，提出了A2-NSGA-III，四点缺点如下：

1）当问题的最优前沿面很小时，A-NSGA-III扩张操作不能提供足够的参考点使种群分布均匀。

2）扩张操作不适合角点，因为以角点为中心扩张生成的点不在第一象限或出界。

3）由于扩张操作是从第一代开始，种群较分散，离最优前沿面较远，很可能没有足够的时间使种群在各个区域均匀分布而由于额外的扩张点陷入局部最优。

4）只有当所有参考点小生境数为0或1时才开始消除操作，对于高维多目标，由于种群变大，这个条件很难达到。

改进措施：选取参考点为单纯形的一个顶点，而不是中心，且边长减半，而且这样可以有三种外形，如图14所示。

图14 改进单纯形扩展法

当添加一个外形后，还有小生境数大于1的，采用另一个外形，直到所有M个外形都采用，如果还有，则单纯形的边长再取半，直到小生境数为0。在一个外形加入之前，需要进行检查：1.如果外形的点超出边界是不被接受，比如上图Q点，外形1、3是不被接受的。2.如果外形的点在参考点中存在，也是不被接受。

这样的扩张操作引入了更多的单纯形，能缓解第一个缺点；以参考点为顶点半边长的单纯形适用于定点，比如Q点，缓解了第二个缺点；只有当原始的参考点小生境数在过去的10代稳定在一个定值，则扩张的点才被接受，这样能克服第三个缺点；只要参考点总数达到原始参看点个数的10倍，消除操作就开始，这样能克服第四个缺点。

（七）MOEA/D-M2M MOEA/D-M2M是将高维多目标问题分解为多个简单的多目标优化子问题，通过协同方式解决这些子问题，每个子问题对应一个子种群，通过这种方式种群多样性得到维护。它是针对MOEA/D的存在的两个缺点进行的改进。

MOEA/D有两个缺点：

1）一个新个体不该完全根据聚合函数值取代旧个体，因为在有些情况下，这样完全取代会导致种群多样性的丢失。

2）对于不同的问题，MOEA/D总是需要设置合适的聚合方法和权重向量，而这个在解决问题之前是很困难的。

均匀生成K个单位方向向量，将目标空间划分为K个子区间，通过计算N个种群个体所在方向与K个单方方向的夹角，将n个个体划分到k个区域里。这样基于方向向量分解目标空间有两个好处：

1）每个子区域的局部最优前沿面可以组成整个最优前沿面。2）即使整个区域的最优前沿面是非线性几何形状（不规则），经过分解，各个子区域只是整个区域的一小部分，所以最优前沿面在子区域内可以很接近线性形状。而求解线性形状的最优前沿面比非线性几何形状简单得多。

（八）-DEA算法 1.算法简介

近期进化算法上有人基于NSGA3提出一种基于新型支配关系支配的高维多目标优化算法-DEA，它通过引入分解算法MOEA/D中的PBI聚合函数来提高NSGA3的收敛性。出发点是整合NSGA-III 和MOEA/D，达到优势互补。通过分析，文章作者得出：

1）NSGA-III 强调的是个体中靠近参考线的Pareto非支配解，然而目标维数增大时，会导致非支配解个数也急剧增多，基于pareto支配关系的NSGA-III 将缺乏足够的选择压力去促使种群向最优PF面进化，事实上NSGA-III 过多的侧重于多样性而导致收敛性不足。

2）MOEA/D通过基于聚合函数的选择操作能很好地逼近最优PF面，在高维情况下收敛性也很好，而多样性试图通过设置均匀分布的权重向量来维护，低维可以到达目的，但是在高维情况下就不适用了，因为在高维空间中，一个具有很好聚合函数值的解有可能离相应的权重向量很远，那么多样性就会缺失。

综上所诉，NSGA-III收敛性不足，MOEA/D多样性缺失，因此作者通过引入MOEA/D的聚合函数来提高NSGA-III的收敛性，而继承NSGA-III优良的多样性。

2.算法步骤

St1）合并父代种群Pt和子代种群Qt，组成Rt，对Rt进行非支配排序，i1Fi，其中Fi表示第i层pareto前沿，满足i1FiN,i1FiN

2）以N个权重向量为聚类中心，将St中的个体聚类到各个权重向量附近（各个权重向量附近个体数是不一样的），然后通过支配关系对每一个类内个体划分等级。这里所说的支配也就是MOEA/D中的PBI聚合函数，如图15所示。

1图15 PBI聚合函数示意图

其中，d1越小，代表x解的收敛性越好；d2越小说明越靠近权重向量，多样性越好。

综合这两者表示一个解的优劣，可以令Fj(x)dj,1(x)dj,2(x)，如果Fj(x)Fj(y)，我们就说x支配y，其中是惩罚系数，实验仿真取5（对5作解释）

说明一下，这里通过支配关系对每一个类内个体划分等级，其实每一个等级上只有一个解，因为Fj(x)是一个可以比较大小的数值。

3）以此取每一个类里的第一等级，第二等级，以此类推，直到选择最后一个等级，他加入的话大于N，不加入就少于N，然后随机的在这一等级里选取个体满足数量N。3.思考

1）对-DEA的改进，在第三步中，是随机的在最后一等级里选择，而我的想法是定向的选择类内个体数少的那一类的最后等级个体，能够进一步提高多样性。

2）NSGA-III在多样性维护阶段只是依靠d2来选择个体，会导致收敛性不足，而-DEA在考虑多样性d2的同时稍微考虑一点收敛性d1，根据这一点我对自己的多个子种群进化算法做了进一步改进，将子种群中由以前只依靠d2选择个体变为d1+5d2。

3）NSGA-III和-DEA都是先进行非支配排序后聚类，不同的是NSGA-III通过评估每一个类里的小生境数选择小生境数少的类内个体，而-DEA是通过支配循环选择每一类个体，因此我可以将我的子种群的NSGA-III模式改为-DEA模式。参考文献

[1] R.C.Purshouse, P.J.Fleming.On the Evolutionary Optimization of Many Conflicting Objectives.Evolutionary Computation, IEEE Transactions on.2007, 11(6): 770-784 [2] 孔维健, 丁进良, 柴天佑.高维多目标进化算法研究综述.控制与决策.2010(03): 321-326 [3] 巩敦卫, 季新芳, 孙晓燕.基于集合的高维多目标优化问题的进化算法.电子学报.2014(01): 77-83 [4] E.Hughes.Radar Waveform Optimisation as a Many-Objective Application Benchmark.In: Evolutionary Multi-Criterion Optimization--S.Obayashi, K.Deb, C.Poloni, T.Hiroyasu, T.Murata, eds.: Springer Berlin Heidelberg, 2007: 700-714 [5] A.Sülflow, N.Drechsler, R.Drechsler.Robust Multi-Objective Optimization in High Dimensional Spaces.In: Evolutionary multi-criterion optimization: Springer, 2007: 715-726 [6] R.Lygoe, M.Cary, P.Fleming.A Real-World Application of a Many-Objective Optimisation Complexity Reduction Process.In: Evolutionary Multi-Criterion Optimization--R.Purshouse, P.Fleming, C.Fonseca, S.Greco, J.Shaw, eds.: Springer Berlin Heidelberg, 2013: 641-655 [7] K.Deb, A.Pratap, S.Agarwal, T.Meyarivan.A Fast and Elitist Multiobjective Genetic Algorithm: Nsga-Ii.Evolutionary Computation, IEEE Transactions on.2002, 6(2): 182-197 [8] E.Zitzler, M.Laumanns, L.Thiele.Spea2: Improving the Strength Pareto Evolutionary Algorithm.TIK, Swiss Federal Institute of Technology(ETH.2001 [9] D.W.Corne, N.R.Jerram, J.D.Knowles, M.J.Oates, J.Martin.Pesa-Ii: Region-Based Selection in Evolutionary Multiobjective Optimization.In: Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’2001, 2001: 283--290 [10] 陈小红, 李霞, 王娜.高维多目标优化中基于稀疏特征选择的目标降维方法.电子学报.2015(07): 1300-1307 [11] H.Ishibuchi, N.Tsukamoto, Y.Nojima.Evolutionary Many-Objective Optimization: A Short Review.In: Evolutionary Computation, 2008.CEC 2008.(IEEE World Congress on Computational Intelligence).IEEE Congress on, 2008: 2419-2426 [12] K.Deb, M.Mohan, S.Mishra.Evaluating the ϵ-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions.Evolutionary Computation.2005, 13(4): 501-525 [13] H.Sato, H.Aguirre, K.Tanaka.Controlling Dominance Area of Solutions and Its Impact on the Performance of Moeas.In: Evolutionary Multi-Criterion Optimization--S.Obayashi, K.Deb, C.Poloni, T.Hiroyasu, T.Murata, eds.: Springer Berlin Heidelberg, 2007: 5-20 [14] Y.Shengxiang, L.Miqing, L.Xiaohui, Z.Jinhua.A Grid-Based Evolutionary Algorithm for Many-Objective Optimization.Evolutionary Computation, IEEE Transactions on.2013, 17(5): 721-736 [15] Z.He, G.G.Yen, J.Zhang.Fuzzy-Based Pareto Optimality for Many-Objective Evolutionary Algorithms.Evolutionary Computation, IEEE Transactions on.2014, 18(2): 269-285 [16] 毕晓君, 张永建, 陈春雨.基于模糊支配的高维多目标进化算法mfea.电子学报.2014(08): 1653-1659 [17] A.Jaimes, L.Quintero, C.C.Coello.Ranking Methods in Many-Objective Evolutionary Algorithms.In: Nature-Inspired Algorithms for Optimisation--R.Chiong, ed.: Springer Berlin Heidelberg, 2009: 413-434 [18] Z.Xiufen, C.Yu, L.Minzhong, K.Lishan.A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems.Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on.2008, 38(5): 1402-1412 [19] E.Carreno Jara.Multi-Objective Optimization by Using Evolutionary Algorithms: The

Src=“/Images/Tex/387.Gif”

基于并行协同演化的差分进化算法篇3

1 差分进化算法

差分进化算法是一种基于群体进化的智能优化算法,具有记忆个体最优解和群内信息共享的特点,即通过群内个体间的合作与竞争来优化问题的解[5]。

该算法首先取得一组随机初始化的种群:X0=[x $_{1}^{0}$ ,x $_{2}^{0}$ ,…,x $_{Ν Ρ}^{0}$ ],NP是种群规模,种群维数为D。经过一系列进化操作,第t代个体进化为x $_{i}^{t}$ =[x $_{i, 1}^{t}$ ,x $_{i, 2}^{t}$ ,…,x $_{i, D}^{t}$ ]。其基本思想是[6]:把父代两个不同随机个体相减得到的差分矢量加到随机选择的第三个个体上,生成一个变异个体,然后再按照一定的概率,让父代个体与变异个体进行交叉操作,生成一个新个体,然后在父代个体与这个新个体根据适应度函数值的大小进行选择操作,选择适应度更优的个体作为子代。

由于基本差分进化算法收敛速度慢、易早熟等不足,本文把并行协同进化引入差分进化算法之中来克服上述不足。

2 所提并行协同差分进化算法

2.1 基本思想

自然界各生物种之间存在着相互制约、相互促进的关系,这种关系称为协同演化[7]。它借鉴了生态学的种群协同理论,通过采用种群间的自动适应、自动调节原理来提高各自和全局的性能。针对标准差分进化算法收敛速度慢、易陷入局部最优解的问题,现提出了并行协同差分进化算法,其基本思想如下:首先使n个子群独立进化,并且记下每个子群当前搜索到的最优解flbest,通过比较当前最优解,找出全局最优解fgbest,采用优胜劣汰的策略,用fgbest代替每个子群中的最差粒子,作为指导信息来影响每个子群的进化,但又不改变每个子群的进化方向,这样就达到了两个效果:一是使局部的搜索性能大大提高;二是通过全局最优解信息的引入,避免了算法陷入早熟的现象发生,从而使算法性能得到了较大的改进。

2.2 算法流程

具体算法流程如图1所示。

该流程表明种群与种群之间在进化过程中的协调关系,不仅考虑了个体之间的竞争,还考虑了个体之间的协作,更加符合自然界进化的规律。

2.3 所采用的策略

2.3.1 变异算子设计策略

为了维护子群体的多样性和收敛性,同时有效地利用群体已搜索到的优良信息,采用一种新的变异公式如式(1)所示:

xm=x $_{l b e s t}^{t}$ +F*(x $_{g b e s t}^{t}$ -x $_{r 2}^{t}$ ) (1)

式(1)中:x $_{r 2}^{t}$ 为子群中随机选择的个体,x $_{l b e s t}^{t}$ 为该子群当前适应度函数值最好的个体;x $_{g b e s t}^{t}$ 为所有群体中适应度函数值最好的个体。

2.3.2 自适应交叉概率设计策略

在标准差分进化算法中,一般都采用固定形式的交叉概率因子,即在算法求解时,每个个体的交叉概率自始至终都采用某个固定值。在并行协同差分进化求解问题时,为了能够利用其他种群搜索到的优良信息,现提出了一种自适应调节交叉概率因子的方法,如式(2)所示,使得算法更符合问题本身的特征,提高了搜索效率。

$\begin{array}{l} C R_{i} = \\ {\begin{cases} \max [| \frac{f_{i} - f_{l b e s t}}{f_{i} - f_{g b s e t}} | ‚ | \frac{f_{i} - f_{g b e s t}}{f_{w o r s t} - f_{g b s e t}} |] ‚ f_{i} > f_{l b e s t} \\ \min [| \frac{f_{i} - f_{g b e s t}}{f_{w o r s t} - f_{g b s e t}} | ‚ | \frac{f_{l b e s t} - f_{i}}{f_{w o r s t} - f_{g b s e t}} |], f_{i} \leq f_{l b e s t} \end{cases} (2) \end{array}$

式(2)中,CRi是个体xi的交叉概率因子(i=1,2,…,NP);fi是个体xi的适应度函数值;flbset和fworst分别为当前子群中适应度最优和最劣的个体的适应度函数值;fgbest为当前所有群体中适应度最优的适应度函数值。

式(2)表明,当fi>flbest时,应该增大交叉概率,以便在新产生的个体中xi所占的分量更多;当fi≤flbest时,应该减小交叉概率,使得新产生的个体中flbest的成分较多。这种自适应交叉概率设计的方法,可根据迭代过程中个体之间的适应度函数值的关系,有效的调整新个体的组成成分,从而提高算法的搜索性能。

2.4 算法过程描述

Step1:初始化种群。差分进化算法采用实数编码方法,编码简单,这里采用文献[8]的编码方式进行编码,能够表示出所在出救点出发的车辆和车辆的行驶路径。染色体可以表示为(r1,r2,…,rn),其中基因ri对应于受灾点i,由出救点编号depot_num和车辆编号vehicle_num两部分组成。根据服务的结点数目(n),随机产生一个关于结点数目的排列作为一条染色体,重复产生多条染色体,直到达到种群规模,得到需要的初始种群。即:Chrom(i,:)=randperm(n);i=1,2,…,NP,其中n为服务的结点数目,NP为种群的初始规模。

Step2:置当前迭代次数G=1,计算初始子群每个个体的适应度函数值,找出每个子群的最优函数值,记为flbest,找出每个子群的最差函数值,记为fworst;同时比较所有子群的flbest,找出最优的函数值,记为fgbest。

Step3:对每个子群分别进行变异、交叉、选择这三种操作,并形成新种群。

Step4:G=G+1;如果G≥IterMax,则转Step5;否则转Step2。

Step5:输出群体当前最优解,算法结束。

3 仿真验证

下面的例子来验证所提算法:某地区发生自然灾害, 24个受灾点需要物资救援,受灾点位置(单位:km),需求量(单位:t)以及允许到达的时间区间(单位:min)见表1。

现有三个物资储备中心(出救点),每个物资储备中心的位置和拥有的车辆数见表2,每辆车的最大载重量为12吨,行驶速度是35 km/h,要求在规定的时间的范围内,完成合理的调配,使所有受灾点的物资需求都能得到满足,并使车辆行驶距离最短。

分别采用遗传算法(GA)、差分进化算法(DE)和本文算法(PCDE)对该算例在同一台计算机上进行计算。求得该算例的最优调度方案是三个出救点的7辆车参与调度,每辆车的行驶路线、行驶距离(单位:千米)、行驶时间(单位:分钟)如表3所示,车辆的总行驶距离Ltotal(单位:km)随迭代次数N变化的曲线如图2所示。

从该算例的计算结果不难看出,所采用的算法能够快速准确的求出多出救点应急调度问题的最优解,而且搜索到最优值的时间和效率均优于遗传算法和标准差分进化算法,这是因为采用的S个子群同时进行优化,子群通过个体替代相互传递信息,信息采取的是正反馈,有效的防止了群体的退化,提高了搜索效率。

4 结束语

针对差分进化算法的不足,引进协同进化的思想来加以解决,并设计了其中的变异算子和自适应交叉算子。算例表明,同遗传算法和差分进化算法相比,本文所采用的算法可以在很短的时间内求出多出救点应急物资调度的最优解,而且搜索到最优值的耗时较短。

摘要：针对传统差分进化算法搜索速度慢、易陷入局部最优解的缺点,引入协同演化的思想提出了一个基于并行协同演化的差分进化算法,并设计了相应的变异算子和自适应交叉算子。仿真验证结果表明:同遗传算法、标准差分进化算法相比,所提算法在搜索速度和寻优能力方面都具有一定的优势。

关键词：差分进化,协同演化,遗传算法

参考文献

[1] Novo J,Santos J,Penedo M G.Topological active models optimiza-tion with Differential Evolution.Expert Systems with Applications,2012;39(15):12165—12176

[2] Gnanambal K,Babulal C K.Maximum loadability limit of power sys-tem using hybrid differential evolution with particle swarm optimiza-tion.International Journal of Electrical Power&Energy Systems,2012;43(1):150—155

[3]吴斌,蔡红,樊树海,等.双倍体差分进化粒子群算法在VRP中的应用研究.系统工程理论与实践,2010;30(3):520—526

[4] Fabris F,Krohling R A.A co-evolutionary differential evolution algo-rithm for solving min-max optimization problems implemented on GPUusing C-CUDA.Expert Systems with Applications,2012;39(12):10324—10333

[5] Chang Chunguang,Chen Dongwen.Study on Multi-destination Emer-gency Scheduling Model Under Dynamic Continuous Consumption.Proc.of International Conference on Logistics Systems and IntelligentManagement.Harbin,China,2010:1532—1535

[6]王海伦,余世明,郑秀莲.自适应差分进化算法及其在参数估计中的应用.计算机工程,2012;38(5):202—205

[7] Lung R I,Dumitrescu D.A new collaborative evolutionary-swarm op-timization technique.Proceedings of the 2007 GECCO ConferenceCompanion on Genetic and Evolutionary computation,England:Lon-don,2007;2817—2820

协同进化算法篇4

科学研究和工程实践中往往存在着一些多目标优化问题 (Multi-objective Optimization Problem, MOP) , 早在1967年, R.S.Rosenberg就在其博士论文中提到了使用遗传算法解决单目标问题, 20世纪80年代中期David Schaffer设计了历史上第一个多目标优化算法。多目标优化算法发展至今已产生很多优秀的算法, 例如, Fonseca、Fleming和Horn等[2,3,4]人提出Multiobjective Genetic Algorithm (MOGA) 、Non-Dominated Sorting Genetic Algorithm (NSGA) 以及Niched Pareto Genetic Algorithm (NPGA) 。Zitzler与Thiele等[5,6,7]人提出Strength Pareto Evolutionary Algorithm (SPEA) 、Pareto Archived Evolution Strategy (PAES) 和Micro-Genetic Algorithm (Micro-GA) 。2003年, Wiegand和De Jong[8]对Cooperative Algorithms进行了深入分析。

协同进化最早由Ehrlich与Raven讨论植物和食植昆虫进化的相互影响而提出。Hillis[9]在1991年提出寄生的协同进化算法模型, 用于协同进化分类网络的设计。1995年, Rosin等[10]提出了竞争协同进化算法模型, 用于研究偷窃的博弈问题。

近年来, 对于基于协同进化的的多目标优化算法研究取得了大量成果, 如文献[11]是设置n个子种群分别独立的基于已有多目标优化算法问题。文献[12]是设置一个目标对应一个子种群, 根据生态种群密度竞争方程调整各子种群的规模, 用于描述多个目标之间的关系。文献[13]是依据在进化过程中获取的信息划分搜索空间, 该方法的不足之处是划分搜索空间后可能产生大量的子种群, 导致计算量过大。

与多目标优化算法相比, 协同进化多目标算法的均匀性与分布性较差。本文提出了基于聚集密度的协同进化多目标算法, 并且数值实验结果以及图示对新算法的均匀性与分布性做了测评。

1 多目标优化问题的相关概念

1.1 多目标优化问题的基本概念

多目标优化问题的基本形式为:

其中, x为决策向量, F (x) 为目标函数, gi (x) ≥0, hi (x) ≥0为约束条件。

多目标问题的最优解组成的集合叫Pareto最优解集, Pareto最优解集包含了所有的Pareto最优解, 下面给出Pareto最优解的定义。

定义1若xA、xB是两个可行解, 且:

则称xA相比xBPareto占优, 也称xA支配xB, 记为xAxB。

定义2 (Pareto最优解) 一个可行解被称为Pareto最优解, 当且仅当x*满足如下条件:

则称x*为Pareto最优解。

1.2 多目标优化问题最优解集的评价标准

多目标优化算法中最优解的确定是一个非常重要而且困难的研究课题, 对于找到的可行解集, 不仅要考虑得到该解集算法的复杂性, 而且要考虑该解集在目标空间的均匀程度和它们的收敛情况。

在最优化算法发展早期, 研究者们主要通过对解集边界的观察来评价解集的好坏, 这样得出来的结果不仅存在着很大的不确定性, 还受到主观因素的影响。

常用的量化评价指标有:

(1) 世代距离 (Generation Distance, GD)

其中, n为算法所得解集前端PFknown中向量个数, di为PFknown中每一维向量到解集前端PFtrue中最近向量的距离[10]。

GD主要反映PFknown对PFtrue的逼近程度。

(2) 错误率 (Error Ration, ER)

其中, n为PFknown中的向量个数, 且PFknown={X1, X2, …, Xn}, ei定义如下:

ER体现的是PFknow对PFtrue的覆盖程度, ER越小, 说明解集的正确性越高。

(3) 分布性 (Spaing, SP)

其中, n为算法产生解集中解的个数, di为第i个解到它的最近解距离, 表示di的平均值, SP即为di的均方差。根据方差的含义, SP反映的是解集分布的均匀情况。

2 协同进化多目标优化算法

协同进化算法考虑个体之间和个体与环境之间的关系, 种群中个体的进化受其它个体和环境的影响。协同进化算法可以在一定程度上克服早熟现象, 并且更适合复杂问题的计算。根据个体与其它个体之间交互方式的不同可将协同进化算法分为竞争型协同进化算法和合作型协同进化算法。

1997年, Potter在其博士学位论文中对合作型协同进化算法模型进行了深入研究, 针对已有算法需要人参与的缺陷, 给出了一种新型合作协同进化算法结构。

由于合作型协同进化遗传算法的进化效率较高, 并且计算的复杂性较小, 因此我们下面的讨论围绕合作型协同进化展开。合作型协同进化算法首先将优化问题决策变量分组, 然后对分组后的每个少变量决策变量分别编码, 产生初始子种群, 接着各子群独立进化。合作型协同进化算法中的各种群个体适应度是通过将其与其它各物种中随机选取的个体一起组成一个完整的解, 计算这个完整解的目标函数值来作为个体的适该个体的适应度。对某种群个体的评价是依据它与其它种群进化到当前代最优个体组合的好坏来进行, 它们组成的完整解的好坏决定着该个体的适应度。各种群在每代执行过程中通过适应度比较找出当前代最优个体, 各种群当前代最优个体的组合即为当前代的可行解, 这样代代下去搜寻最优解。

将多目标优化问题的决策变量分为几个部分, 既可以将其中几个决策变量作为一个部分, 另外几个决策变量作为另一部分, 剩下的决策变量再作为一个部分。每个部分对应一个种群, 每个种群的个体适应度是通过和其它种群的个体组成完整解再评价得到, 该个体的适应度是由其与其它种群个体组合中最优决定组合。具体步骤如下:

(1) 设置一个超级个体集合P为空集。

(2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量。

(3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度。

(4) 遗传操作。使用选择、交叉、变异算子分别对各子种群进行遗传操作。

(5) 更新超级集合P。

(6) 重复 (3) — (5) , 直到满足一定代数, 将当前最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性。

(7) 重复 (2) — (6) , 直到P中个体达到一定数目。

3 基于聚集密度的协同进化多目标优化算法

协同进化多目标算法在一定程度上克服了早熟现象, 但是解的分布性和均匀性较差, 对于如何提高协同进化多目标算法的均匀性和分布性已提出了不少方法。耿焕同、朱海峰将均衡分布性与收敛性用于该算法以改善解的分布性与收敛速度;张远淑将均匀设计用于该算法以提高解的多样性和分布性。

协同多目标优化算法分布性欠佳的主要原因在于算法在更新精英集时没有考虑粒子的多样性和分散性。考虑到聚集密度可反映群体的多样性和分散性, 本文提出在协同进化多目标优化算法中引入了聚集密度以进行精英集的更新, 其具体步骤为:

(1) 计算每个种群中各个体的聚集密度。

(2) 依据目标函数值和聚集密度值定义一个偏序集, 该集合中的元素有个体的目标函数值和聚集距离两个属性。

(3) 依据一定的比例, 依次从偏序集中选择个体, 更新P。

由此可以得到基于聚集密度的协同进化多目标优化算法, 具体如下: (1) 设置一个超级个体集合P为空集; (2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量; (3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度; (4) 遗传操作。使用选择、交叉、变异算子分别对子种群进行遗传操作; (5) 计算每个粒子的目标向量, 当迭代次数小于最大迭代次数时, 根据聚集密度方法更新P; (6) 重复 (3) — (5) , 直到满足一定代数, 将当前的最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性; (7) 重复 (2) — (6) , 直到P中个体达到一定数目。

4 数值实验与算法性能评测

下面用基于聚集密度的协同进化多目标算法对两个标准测试函数DTLZ1和Deb2进行数值计算, 并将计算结果与普通协同进化多目标算法的计算结果进行比较, 从而检验改进算法的性能。

图1—图4分别是用改进算法和常规算法求出DTLZ1和Deb2的Pareto最优边界。可以很直观地看出, 改进算法在解的分布性和均匀性方面均明显优于常规算法。

为了更进一步定量地评价改进算法的性能, 给出改进算法和常规算法的世代距离、错误率和分散性指标的对比数据。考虑到计算结果的随机性, 表中给出的是20次实验结果的平均值。

从表1和表2中可以很清楚地看出, 改进算法和常规算法的GD指标相差无几, 但改进算法的ER和SP指标与常规算法相比明显占优。

协同进化算法篇5

多重序列比对是生物信息学的重要研究内容, 它的目标是通过同时比较多个序列, 发现它们之间的相似区域和保守性位点, 进而推断未知生物分子的结构和功能, 或者重构系统发育树, 寻找物种之间的进化关系。比对过程是对生物序列进行重新排列, 使得它们之间的相似程度最高。多重序列比对是一个典型的NP难题[1], 人们通常采用一些近似算法实现多序列比对, 目前主要的多重序列比对算法有三类。

(1) 基于渐进策略的比对算法[2,3,4]

这类方法主要以动态规划算法为基础, 首先计算所有序列两两比对的得分, 然后选择得分最高的两条序列构造一致性序列, 再将它与其余序列进行比对, 并与得分最高的那条构造一致性序列, 依次进行, 直到所有序列都与前面的比对过, 就得到最终的比对结果。目前流行的多重序列比对软件CLUSTAL[2]采用的就是渐进策略, 这类算法的时间复杂度为O (N2n2) , 在序列不太长而且序列数量不多的情况下, 这种策略具有较好的效果, 但是随着序列的数量和长度的增加, 计算的复杂性显著增加, 效率明显下降。

(2) 基于概率模型的比对算法[5,6,7]

文献[6]提出了一种基于隐马尔可夫模型 (HMM) 的多重序列比对方法, 他们利用SCOP 数据库估计HMM的参数, 并将它与序列的局部结构信息结合起来, 较好地改善了比对的结果。但是这类方法通常需要估计某些概率模型, 计算的复杂性也较高, 而且比对结果对模型的依赖程度比较高。

(3) 基于启发式的比对算法[8,9]

文献[8]提出了一种两步法的多重序列比对算法, 首先在序列中找出一些保守的块, 然后以这些块为单位进行比对, 对于序列较长, 而且数量多的数据集到达较好的效果。文献[9]提出了一种复杂度O (Nlog $_{2}^{Ν}$ n2) 为的启发式比对算法。遗传算法也是一种启发式算法, 它由于能够避免算法陷入局部最优解而受到人们的重视, 在生物序列多重比对中也有一定的应用[10,11,12,13], 但是传统的遗传算法在处理收敛性和个体多样性的问题上难以取得很好的平衡, 这就限制了遗传算法在实际中有效应用。

本文在遗传算法的基础上, 提出一种用于多重生物序列比对的协同进化算法, 一方面采用等距抽样方法从父代中选择进入子代的种群, 保证个体的多样性;另一方面, 利用协同进化算子, 使得个体内部在进化过程中序列之间保守的区域和位点以较高的概率传递给子代, 而非保守区域和位点以较高的概率参与选择、交叉和变异运算。在BAliBASE3.0数据库上, 本文方法取得比ClustralX算法更高的比对得分, 另外该算法比传统的遗传算法具有更好的收敛性。

1 生物序列多重比对的数学描述

从数学的角度看, 生物序列多重比对是一个最优化问题, 假设n有条需要比对的序列S1, S2, …, Sn, 其中Sk=Sk1, Sk2, …, Skm, k=1, 2, …, n, Sij表示第i条序列中的第j个位置上出现的字符, 对核酸序列来说, Sij代表ATGC中的某个碱基出现在第i条序列中的第j个位置上, 而对蛋白质序列来说, Sij代表20种氨基酸残基中的一种出现在第i条序列中的第j个位置上, |S1|, |S2|, …, |Sn|分别表示各序列的长度。如果用∑表示Sij所属的字符集合, 那么对核酸序列, 有∑={A, T, G, C}, 对蛋白质序列, 有∑={A, R, N, D, C, Q, E, G, H, I, L, K, M, F, P, S, T, W, Y, V, B, Z, X}。多重序列比对的目的就是同时对多条序列进行重新排列使得它们之间的相似程度最高[10]。由于在进化过程中生物序列上的碱基 (或氨基酸) 可能发生替代、插入或者缺失, 即序列上某些位置的符号可能被其它符号代替, 或者在某些位置插入一些符号, 或者某些位置上的符号被删除掉, 因此在多重序列比对过程中, 需要考虑生物序列的这种进化特点。对于缺失或插入的情况, 在比对过程可以在相应的位置插入空位 (用“-”表示) , 则多重序列比对的结果可以用一个矩阵B来表示:

其中, n是序列的数量, m是比对后序列的长度, bij∈∑′ (∑′={∑, -}) , B中每行表示一条序列的比对结果, 删掉各行中的空位符号“-”, 可以得到每条序列的原始序列[矩阵中的某列表示比对结果中的一个位点。对于给定的打分矩阵, 可以计算出B中每两条序列之间的比对得分, 再将所有序列的比对得分累加起来就得到多重序列比对的总得分:

$f (B) = \sum_{i \neq j} C (b_{i}, b_{j}) i, j = 1, 2, \dots, n$ (2)

其中C (bi, bj) 表示序列bi和bj之间的比对得分, 定义如下:

$C (b_{i}, b_{j}) = \sum_{k = 1}^{m} r (b_{i k}, b_{j k})$ (3)

这里的r (bik, bjk) 是从给定打分矩阵查出的符号bik和bjk的匹配得分值。因此一个多重序列比对的任务就是构造矩阵B, 使得式 (2) 取得最大值, 可以将它形式化地表示为如下的最优化问题:

$\max_{B \subset \land} (f (B))$ (4)

其中, ∧表示序列S1, S2, …, Sn的所有可能比对结果的集合。

2 基于协同进化算法的多重序列比对

2.1 多重序列比对中的协同进化机制

协同进化 (Co-evolution) 的概念最早来自生物学研究[14], 它是指一个物种的性状作为对另一个物种的性状的反应而进化, 而后一物种的该性状又是作为对前一物种性状的反应而进化, 简单地说就是指不同物种的性状之间的进化存在相互影响关系。协同进化现象表明一个物种的某个性状与另外一个物种的相应性状的进化是同时进行的, 它们在进化过程中相互影响、相互制约、相互协作。就像生物进化过程的“物竞天择, 适者生存”机理被发展成遗传算法一样, 协同进化的思想也被用于最优化计算中, 并用到某些实际问题中[15,16]。

对于多重序列比对问题来说, 根据式 (2) 可知, 两条序列之间比对得分值C (bi, bj) 越大, 则比对的总得分f (B) 越大。为了获得满足式 (4) 的矩阵B, 需要对每条序列进行合适的排列, 以使得不同的序列在相同位置上的符号尽可能地相同, 而且希望这符号相同的区域和位置在排列过程中尽量保持不变, 而那些匹配程度低的位置很可能需要重新进行排列, 这样就能使序列之间的匹配程度随着排列的进行而逐渐提高。假如将每条序列看作生物进化中一个个体, 那么这些匹配程度高的区域和位置在进化过程保持相同的进化模式, 就是一种协同进化机制。从遗传算法的角度来看, 这些适应度高的区域和位置应该以更高的概率一起被传给子代;相反, 为了使子代的匹配程度提高, 应该对那些适应度低的区域和位置重新排列, 即在这些区域和位置上插入空位或者删除相应的符号, 通过这种方法我们就将生物学的协同进化机制引进到多重序列比对的遗传算法中。

2.2 协同进化算法的实现

2.2.1 种群的初始化和编码

在种群初始化的时候需要构造每个个体并对其进行编码, 假设需要比对的n条序列中最长序列的长度为, L=max (|Si|) , i=1, 2, …, n。参考基于动态规划算法的多重序列比对方法, 初始化时需要在序列中插入一定比例的空位, 使得序列之间有足够的空间进行重排, 本文设定序列中的空位比例为最长序列长度的20%, 由此可以构造比对结果矩阵, 其行数为n, 列数为m=1.2×L, 然后将每条序列中的字符分别存放在矩阵的各行中, 并且随机地在每行字符之间插入空位符号“-”, 这样的一个矩阵就可以编码一个个体 (即一个多重序列比对结果) 的初始状态, 如果种群的初始规模为80, 则一共需要构造80个矩阵M1, M2, …, M80。

2.2.2 适应度函数

本文使用了四种适应度指标:个体适应度、单条序列适应度、单个位点适应度和区域适应度。个体适应度值采用式 (2) 计算, 先根据式 (3) 计算个体B中每两条序列的比对得分, 然后所有的得分累加起来, 作为该个体的适应度;单条序列的适应度是指一个多重比对结果中, 一条序列与个体中其它所有序列比对结果得分的总和, 其计算公式为:

$g (b_{i}) = \sum_{i \neq j} C (b_{i}, b_{j}) i, j = 1, 2, \dots, n$ (5)

其中, C (bi, bj) 是指多重比对结果中序列bi和bj之间的比对得分;单个位点适应度的计算公式如下:

$h (b_{k}) = \sum_{i \neq j} r (b_{i k}, b_{j k})$ (6)

其中r (bik, bjk) 是根据给定的打分矩阵查出的bik和bjk的匹配得分值, i, j=1, 2, …, n, k=1, 2, …, m。区域的适应度是多个连续的位点适应度之和, 可由下式计算:

$R_{i, j} = \sum_{k = i}^{j} h (b_{k}) i, j = 1, 2, \dots, n$ (7)

2.2.3 选择算子

传统的遗传算法根据适者生存的原则产生子代个体, 父代中适应度高的个体被选择进入下一代, 交叉、变异只是对适应度低的个体操作, 在这种原则下, 进化过程中个体的多样性没有保障, 通常会导致过早收敛, 没法得到全局最优解。为了避免算法的过早收敛, 保证进化过程中个体的多样性, 本文在选择算子中引进了一种保留机制, 使得适应度高的个体也可能参与交叉和变异运算, 适应度低的个体也可能直接进入到下一代。具体方法是先将所有个体按照个体适应度从高到低排序, 然后采用等距抽样的方法, 从种群中每隔3个样本抽取一个个体作为子代的个体直接进入下一代, 其余个体经过交叉和变异运算后产生新的个体。

2.2.4 交叉算子

交叉计算是在繁殖下一代的个体过程中, 对不同个体相同位置的基因进行交换, 从而产生新的个体。在多重序列比对中, 每个个体用一个矩阵来表示, 矩阵的每行表示一条序列, 而每条序列由一些特定的区域和位点组成。交叉算子可以作用在行上, 也可以作用在列上。行方向的交叉运算包括个体水平上和序列水平上的运算, 个体水平上的交叉算子对不同矩阵中某些对应的区域进行交换;而序列水平上的交叉算子将矩阵中行上的某个区域与其它矩阵中相应的行上相应的区域进行交换, 图1显示了这两种交叉进化算子。

根据多重序列比对的协同进化机制, 匹配程度高的序列和区域应该以较高的概率进入子代, 而以较低的概率参与变异操作后进入子代;相反, 匹配程度低的序列和区域应该以较低的概率进入子代, 而以较高的概率参与变异后进入子代。在交叉计算过程中, 分别用式 (5) 和式 (6) 计算每条序列和每个位点的适应度, 并且分别对这些适应度值进行排序, 以中值为界将序列和位点分别分为高适应度和低适应度两部分, 然后选择合适的概率对这些不同的序列和区域进行交叉操作。

2.2.5 变异算子

变异操作是通过对个体中的编码序列进行一些操作, 包括对序列上的字符进行插入、删除和替换操作。删除将导致序列的有效字符长度不断变短, 比对结果的适应度也不断降低, 无法找出合适的重排结果;而插入字符可能导致序列长度不断变长, 也无法得到合理的结果。本文提出了一种空位重排算子来实现个体的变异运算, 即如果在序列的某个位置插入一个空位, 则需要删除掉序列中其它位置的空位;反之, 如果在序列的某个位置删除一个空位, 则在其它位置插入一个空位。由于生物序列多重比对的目的是找出序列中的保守区域和位点, 而协同进化机制的任务是在进化过程中将这些保守的区域和位点保留到子代中, 因此变异算子必须满足协同进化机制的要求, 即变异操作以较高的概率发生在适应度低的位置, 而以较低的概率发生在适应度较高的位置。本文对适应度高的区域和位置以较低的概率进行空位重排;对于适应度低的区域和位置, 如果它所在的序列适应度高, 则以较低的概率进行空位重排, 如果这些区域和位置所在的序列适应度低, 则以较高的概率进行空位重排。

3 实验结果与讨论

为了检验本文提出算法的有效性, 我们用多重序列比对基准数据库BAliBASE3.0 [17] Reference1中的序列簇进行测试, 测试的方法包括本文的协同进化算法、ClustralX算法和传统遗传算法。Reference1包含38个序列簇, 最大的序列簇包含14条序列, 最小的序列簇包含4条序列, 每个序列簇中序列的最大长度、最小长度和平均长度如图2所示。采用本文的协同进化算法时, 样本规模为80, 矩阵中每行空位比例是最长序列长度的20%, 按照等距抽样的方法选择1/3的个体直接进入子代, 其余个体中高适应度的序列和区域以0.3的概率参与选择和变异运算, 低适应度的序列和区域以0.7的概率参与选择和变异运算, 打分矩阵的对角线元素为1, 其余位置为0, 即比较的两个符号相同时得分1, 否则得分0, 进化次数为200。采用传统遗传算法时, 样本规模、矩阵中每行空位比例、打分矩阵和进化次数与协同进化算法一样, 个体适应度值最大的1/3样本直接进入子代, 参与选择运算的序列和区域随机选取, 概率为0.3, 参与变异运算的序列和区域也是随机选取, 概率为0.3。每个序列簇分别用协同进化算法和传统遗传算法计算20次。

图3是协同进化算法与传统遗传算法在Reference1数据集上的比对结果。它显示了这两种方法在38个序列簇上比对收敛时最佳个体的平均适应度与ClustralX方法比对结果的比较, 图中以ClustralX方法的结果为基准, 显示了协同进化算法和传统遗传算法结果与它的差异值, 总体上看, 这两种算法比ClustralX方法有更好的表现, 在38个序列簇中, 协同进化算法取得更高适应度的有30个, 传统遗传算法则有31个。就协同进化算法和传统遗传算法而言, 协同进化算法在多数情况下能够获得比传统遗传算法更高的适应度。这些表明协同进化算法比ClustralX算法和传统遗传算法都有更好的表现, 更加能够发现多重序列中的保守区域和位点。

为了比较协同进化算法和传统遗传算法的收敛性, 对每个序列簇分别用这两种算法运行20次。对某个序列簇, 记C (i) 为第i次运算过程中协同进化算法进入收敛状态所需的进化次数, G (i) 为第i次运算过程中传统遗传算法进入收敛状态所需的进化次数, 分别对向量C和G求平均, 得到两种算法在该序列簇上收敛时的平均进化次数。图4和图5是它们在Reference1数据集上的收敛情况。图4显示了两种算法收敛时的平均进化次数对比情况, 由图4可以看出, 协同进化算法在多数情况下需要较少的进化次数就进入收敛状态, 这主要是因为协同进化机制使得适应度高的序列和区域被保留进入子代, 而传统遗传算法是随机地对任何序列和区域进行遗传运算, 在进化过程中可能破坏掉个体中的一些保守区域和位点。图5是两种算法在Reference1数据集中1aab序列簇上的一次运行过程比较, 从该图可以看出, 两种算法在比对开始的时候, 适应度的差异不大, 但是由于协同进化机制的作用, 在进化计算到25次之后, 协同进化算法的适应度明显高于传统遗传算法, 而且从此之后一直领先, 到了100次的时候, 协同进化算法进入收敛状态, 而传统遗传算法需要再进化20多次才进入收敛状态。

4 结语

生物序列多重比对能够提供序列之间相似性的度量, 可以发现不同序列中存在的保守区域和位点, 通过多重比对可以推断生物序列的结构和功能, 也可以推断序列之间的进化关系。本文在传统遗传算法的基础上, 引进生物协同进化机制, 提出了一种用于多重生物序列比对的协同进化算法, 该算法模拟生物进化过程的协同进化机制, 使个体中适应度高的序列和区域以较高的概率被传到子代的个体中, 而适应度值低的序列和区域以较高的概率参与交叉和变异操作。在基准数据集上的实验结果显示, 协同进化算法比流行的比对算法ClustralX产生更高的适应度, 比传统的遗传算法具有更好的收敛性。

摘要：序列比对是生物序列分析的一项基础性工作, 多重生物序列比对可以帮助预测未知序列的结构和功能。在传统遗传算法的基础上, 提出了一种用于多重生物序列比对的协同进化算法, 通过引进协同进化机制, 使得保守区域和位点以较高的概率传给子代, 而非保守区域和位点以较低的概率传给子代。在BAliBASE3.0数据库上, 该方法获得比常用的比对算法ClustralX更高的适应度, 比传统的遗传算法具有更好的收敛性。

协同进化算法篇6

基于协同进化思想的优化算法近年来正成为国际上学者关注的一个热点[8]。借鉴自然界中不同生物种群之间相互作用、相互适应、协同进化的过程，协同进化算法把一个复杂的问题分解为若干个相对简单的子问题，分配给多个子群体分别进行进化操作，子群体之间定期进行信息交互，通过合作或竞争的关系，共同完成对优化问题的求解。对比一般的遗传算法，协同进化算法可以对控制变量进行合理的种群划分，对较大规模的系统求解具有较强的跳出局部最优点的能力。而电力系统无功优化通常采用可投切电容器组、有载调压变压器、发电机无功出力等控制手段[9]，控制变量的数目较多，非常适合采用协同进化算法进行优化求解。

本文将分层分区并采用协同进化算法用于电力系统无功优化问题，对IEEE30节点系统进行了无功优化试验。结果表明，与传统无功优化算法相比，该思想和算法能在更大范围内寻优，对无功优化问题求解效果明显。

1 电力系统无功优化模型

在满足运行条件约束下，无功优化问题的目标可以从安全性、电能质量和经济性的角度考虑。本文中控制变量取有载调压变压器的分接头变比、可投切电抗器的补偿容量以及发电机出口电压作为控制量，以全网有功网损最小为目标，可建立以下无功优化数学模型。

目标函数：

等式约束：

不等式约束：

式中：VGi为各个发电机节点的电压模值;Qbi为各个无功补偿设备节点的无功补偿容量;Ti j为各变压器的分接头变比;Si j为各线路上所传输的视在功率。

2 电力系统分层优化

随着电力系统大范围的互连，使得系统复杂性增强，同时不同电压等级电网的无功又有其自身的特点。如特高压输电线路通常采用8分裂导线，与以往高压、超高压输电线路相比，导线的等效直径增大，阻抗下降，阻抗角增大，传输功率增大，相对相以及相对地之间的分布电容增大。每100 km的1 000 kV特高压输电线路充电功率有530 Mvar左右，约为同等长度的500 kV输电线路的5倍[10]。而无功的平衡往往采用就地平衡原则，不希望过多的无功功率长距离传送。因此，将电力系统能够按照电压等级分层，不同电压等级的电网独立优化，是合理、必要的。

通过节点分裂法可以将一个大系统直接分解成2个子系统[11]。子系统是相对独立的，以边界节点的参数为协调变量，每个子系统的解只和自己的内部变量、边界变量有关，子系统之间依靠交换边界节点数据来进行协调，如图1所示。

图1中可见大电网由2个子网A,B通过一个边界节点相连。分层以后，将这个节点分别“撕裂”为2个节点，形成2个边界节点c1和c2。此互联系统被分解为子网A和子网B，把这个节点称为分裂点。每一个分裂后的边界节点都可看作虚拟的发电机节点，虚拟发电机节点弥补了因为电网分解而产生的潮流不平衡，不影响整个网络的目标函数值。令xb1和xb2分别为2个分区的边界变量，即xb1={Pb1,Qb1，θb1,Vb1}，xb2={Pb2,Qb2，θb2,Vb2}。Pbi,Qbi是边界节点的虚拟发电机注入功率，θbi,Vbi是边界节点电压的相角和模值。因分解而产生边界节点在电气上应该是等值的，即xb1=xb2=xb，这样，就得到了2个分区的无功优化模型：

目标函数：

约束条件：

式中：hi为第i个分区内的不等式约束条件，gi为第i个分区内的等式约束条件;φ(x)为边界协调方程(在实际优化过程中取φ(x)=xb1-xb2<ε，其中ε为一很小的正数)。在优化过程中，不等式约束条件和边界协调方程以罚函数的方式加入目标函数。这样就将一个大电网分成了2个子网优化，优化算法采用下文所述的协同进化算法。

运用上述电网分解的方法，可以按照电压等级的不同将电网分层，通常选择与变压器高压侧相连的节点为边界节点。每一个子网对应于一层。整个电力系统就被分成了若干个层次。这样，将电网分层后，按照电压等级由高到低的顺序逐层优化，以实现整个电网的优化。

3 基于协同进化的无功优化算法

3.1 协同进化算法的原理

由于现代电力系统结构复杂，分布范围广，线路和节点数目较多，问题的规模较大，采用一般的进化算法不但每种方案的计算时间急剧增加，而且遗传算法本身的收敛速度也会减慢，容易陷入早熟[9]。而无功的分布又有明显的区域性，一般采用就地平衡原则。因此，将同一层的电网分成若干个区域，区域间采用协同进化算法可以较好地解决这个问题。

协同进化算法在普通进化算法上引入生态系统的概念。普通遗传算法和进化算法将求解问题作为单一种群的进化，而协同进化算法将问题看作相互作用的若干种群组成的生态系统，以生态系统的整体进化来达到问题求解目的。它将复杂繁多的控制变量分成若干组，每一组对应于一个物种。这些不同的物种在遗传进化时是相互隔离的，而物种间通过合作或者竞争的方式共同进化，从而完成生态系统整体的进化。协同进化算法的关键就是如何对众多的变量进行分组。对于分区域的无功优化正好为种群分类提供了依据，即同一个区域的电网中的控制参数分为一个种群。

3.2 协同进化算法在无功优化中的应用

与普通进化算法相比，协同进化算法既具有普通进化算法的优点，又具有搜索时间短，收敛快的优点[8]。以一个简单的电力系统为例，说明协同进化算法在无功优化中的应用。假设该系统被划分为3个区域，每一个区域对应于一个种群。这些不同的种群都可以采用遗传进化算法独立的遗传进化，然后通过合作或竞争的关系来达到整个生态系统的进化。设区域1、2、3的控制变量的个数分别为n、m和p，其控制变量分别为X1、X2和X3。以种群1为例，种群1独立的进行杂交变异选择等进化计算，从而得到新的一簇个体，使得种群1的数目增大。在做适应度评价时，需要计算改种群中的每个个体对整个系统无功优化的效果，因此从种群2和种群3种各选取一个个体的代表X2,X3，与种群1中的各个个体组成整个系统的染色体X，代入系统中计算适应度，并由此来选择种群1中的个体的优劣，为遗传到下一代提供参考。事实上，种群2和种群3的代表X2,X3并不是任意选取的，而是选择在该组个体中，适应度最高的那一个。同理，在进行种群2和种群3进化的计算中，种群1的代表也是选取在种群1进化计算所得结果最好的那一个个体。这样，3个种群通过独立进化，相互合作，使得整个生态系统得到进化，即全网运行状态越来越合理，有功网损不断降低。该过程反复循环，直到满足停止条件为止。

综上所述，协同进化算法的步骤如下：

(1)载入原始数据，包括网络结构、潮流计算数据以及各种约束条件。

(2)将整个网络划分成N个区域，每个区域内的控制变量构成一个集合，设为Xi(i=1,2，…，N)。

(3)每个区域内的变量分别初始化，形成N个独立的种群，每个种群对应于该区域内的无功优化子问题。

(4)每一个种群独立的进行交叉、变异等操作，逐一生成新的个体。

(5)对各个种群中的个体逐一判断其优劣并排序，选择和遗传。在计算第i个种群中的各个个体对全网无功优化的效果时，从剩下的N-1个种群中选出每个种群中最好的那一个个体作为该种群的代表，共同构成全网的控制变量向量进行计算。

(6)判断是否所有的种群都已经进化完成，即是否完成了一次完整的协同进化过程，否则返回步骤(5)。

(7)返回步骤(4)，开始新的一次协同进化过程，直到结果达到某种条件为止。

该算法流程如图2所示。

4 算例

本文采用IEEE30节点测试系统[12]。将该系统分为2层，其中，1～7号节点分在高压层，其余节点分在低压层，其中4、6号节点为边界节点。低压层又分为2个区域，9～17号节点为区域1，其余节点分在区域2。控制变量为各发电机节点的出口电压，第10、24号节点的补偿设备补偿容量，以及4个变压器的分接头变比。同时，本文利用matlab优化工具箱，分别使用DFP,BFS以及单纯型法等经典算法以及普通遗传算法进行优化，对比结果如表1所示。其中U2、U5、U8、U11和U13为第2、5、8、11、13号节点(发电机节点)的电压模值(均为标幺值);Q10、Q24为第10、24号结点可投切电容器组的补偿容量，K为变压器分接头变比。

3种用于比较的方法中，DFP方法是由Davidon提出，经过Fleteher与Powell改进和加工形成的。这种方法是共轭方向法的一种，它能实现各次搜索方向之间的共轭特性。BFS法与DFP法共同属于共轭方向法，但是它具有较好的数值稳定性，同时受确定步长的一维搜索精度的影响较小。而单纯型搜索法的思想是对于在Rn中具有n+1个顶点的多面体，设V1,V2，...，Vn+1是该多面体的n+1个顶点的位置向量。

选定一个初始点，按照一定的规则形成初始单纯形。从这一单纯形出发，每次迭代都设法构造新的单纯形以替换原有的单纯形，使单纯形不断向目标函数的极值点靠近，直到搜寻到极值点为止。具体的步骤见参考文献[13]。

从优化结果中可以看出，分层分区的协同进化算法所得到的优化解要比BFS、DFP算法所得到的解更优，与单纯型法相当。但是由于前三种经典算法要求目标函数与变量连续可微，故无法考虑变压器变比与补偿容量的离散性，优化解在实际应用中难以取到。故综合比较，分层分区的协同进化算法的优化解仍然要优于经典算法和普通遗传算法。

5 结论

无功优化问题是一个多变量的离散非线性问题，无功的分布具有明显的区域性。本文针对大范围互联的电力系统的无功优化提出了一种分层分区优化的方法。先将电力系统按电压等级分层，按电压等级从高到低的顺序逐层优化。在每一层电网内，采用分区的协同进化算法进行优化。协同进化算法将全系统控制变量按地区分组，不同组的控制变量独立地杂交、变异。通过不同组之间的协调共同进化。

协同进化算法篇7

从20世纪80年代起, 人工神经网络 (Artificial Neural Network, ANN) 设计就一直是神经网络的一个重要研究方向。ANN的设计是件极为复杂的工作, 迄今没有系统的规则可循。ANN的设计主要包括ANN结构的确定和网络权值的选取两个方面, 其实质就是根据性能评价准则搜索结构空间中满足问题要求的最优网络结构。对某些复杂问题, 其搜索空间可能是巨大的且有许多局部最优点, 这使得基于下降策略的传统优化方法如最速下降法、牛顿法和变尺度法等在解决这类问题时极易陷入局部最优解。

遗传算法 (Genetic Algorithm, GA) 作为一种模拟生物遗传和进化过程而形成的智能优化算法, 具有很强的全局收敛性, 使得将GA和ANN相结合成为一种必然。

利用GA设计ANN的一个关键问题是如何对ANN的结构进行编码, 即网络参数编码方案的确定。ANN模型的参数主要包括:网络层数、每层神经元数、神经元的互连方式、各连接权重以及传递函数等。虽然用GA确定的参数越多, ANN设计的自动化程度越高, 但这样势必会加大GA的搜索空间, 因而确定哪些参数需要由GA进行优化是一个值得研究的问题。

从20世纪80年代末起, 许多学者利用GA进行各种ANN设计, 取得了丰硕的成果。但随着研究的深入, 用GA设计ANN的缺陷也陆续暴露出来, 如过早收敛、局部搜索能力较差和收敛速度较慢等。

为此, 一些学者将各种改进GA用于ANN设计以克服上述缺陷。罗健提出一种带有BP算子的基于GA的ANN设计方法, 改善了算法的收敛速度;李建珍提出一种基于GA的ANN学习算法, 可有效避免过早收敛现象;杨梅提出一种基于改进GA的ANN优化方法, 提高了算法的局部收敛性;胡仁平提出基于改进GA的ANN优化设计方法, 提高了全局收敛速度;Soares等则独辟蹊径地将模拟退火和GA相结合用于ANN设计。

本文提出一种利用协同进化GA设计自组织特征映射 (Self-Organizing Feature Mapping, SOFM) 神经网络的方法, 并将此算法用于矿井突水水源的判别问题, 取得了较为满意的结果。

1 SOFM神经网络

SOFM神经网络的学习算法步骤如下:

(1) 网络初始化。随机设定输入层和映射层间权值的初始值。

(2) 确定输入向量。将输入向量x= (x1, x2, …, xn) T赋以输入层。

(3) 计算映射层的权值向量和输入向量的距离。将输入向量x= (x1, x2, …, xn) T赋以输入层。

在映射层, 计算各神经元的权值向量和输入向量的欧氏距离。映射层的第j个神经元和输入向量的距离按式 (1) 计算。

其中, wij为输入层的i神经元与映射层的j神经元之间的权值。

(4) 选择与权值向量距离最小的神经元。计算并选择使输入向量和权值向量距离最小的神经元, 如dj最小, 则称其为胜出神经元, 记为j*, 并给出其邻接神经元集合。

(5) 权值的学习。胜出神经元和位于其邻接神经元的权值按式 (2) 更新。

其中,

式 (4) 中的σ2随着学习的进行而逐步减小, 即h (i, j*) 的范围在学习初期很宽, 随着学习的进行而变窄。从而, 领域函数h (i, j*) 可以起到产生有效映射的作用。

(6) 迭代结束判断。若达到要求则算法结束, 否则返回步骤 (2) , 进入下一轮学习。

2 基于遗传算法的神经网络设计

利用GA优化ANN的主要方法是同时优化ANN的结构和连接权值。这类方法需要同时对ANN的结构和连接权值进行编码, 加大了算法的复杂度, 也使得进化过程变得较为困难。黎明[8]提出了一种利用GA同时优化ANN的结构和连接权值的方法, 采用二进制和实数混合编码方法, 神经网络的结构采用二进制编码, 而连接权值采用实数编码。李智勇[9]提出了将多物种进化GA用于优化神经网络的结构和连接权值的方法, 算法对网络的拓扑结构和连接权值同时采用多维实数编码。但在进行遗传操作时, 仅进化由连接值构成的个体基因, 而不进化由神经网络结构构成的物种基因, 而仅在多个随机产生的神经网络结构中选择。因此, 此算法实质上仅仅优化了连接权值, 最后得到的神经网络结构不一定最优。

3 合作型协同进化遗传算法

协同进化概念最早由Ehrlich和Raven提出, 主要是指生物与生物、生物与环境之间在进化过程中的某种依存关系。

Hillis[10]最早将协同进化引入遗传算法。此后, 陆续出现了多种协同进化遗传算法[11]。

合作型协同进化遗传算法[11] (Cooperative Co-evolutionary Genetic Algorithm, CCGA) 是协同进化遗传算法的主流, 其算法步骤如下:

步骤1:将优化问题的决策变量分组;

步骤2:初始化所有的子种群;

步骤3:对每一个进化的子种群的个体, 选择代表个体, 并组成合作团体, 计算个体的适应度, 进行个体评价;

步骤4:每一个子种群进行选择、交叉和变异等遗传操作, 生成下一代子种群;

步骤5:判断算法是否满足终止条件, 若满足, 停止进化, 输出结果;否则, 转步骤3继续迭代。

4 基于CCGA的SOFM神经网络设计

SOFM神经网络对权值的调整缺乏全局最优性, 这将形成一些从未得到学习的“死”神经元, 直接影响了SOFM神经网络的全局最优性。“死”神经元在许多类型的神经网络中均存在, 已有学者给出了一些解决办法[12]。

考虑到CCGA不仅具有较好的全局最优性, 而且较传统GA更适宜优化复杂问题, 有学者尝试用CCGA设计ANN。Potter[13]将合作型协同进化思想用于神经网络优化, 获得了较为合理的神经网络结构;Pedrajas[14]也采用CCGA同时优化ANN的结构和权值;孙晓燕[15]等结合CCGA本身特性和神经网络的特点, 给出了种群分割、混合编码等一些优化神经网络的方法。

本文将CCGA用于SOFM神经网络的优化设计, 提出了一种基于CCGA的SOFM神经网络算法 (CCGAS) 。其基本思想是:针对SOFM网的某些神经元在竞争中永远无法获胜而产生的“死神经元”现象, 在SOFM神经网络中引入了全局搜索能力很强的CCGA, 这样既可提高SOFM神经网络的全局最优性, 尽量避免“死神经元”现象, 又可以适当降低算法的复杂度。

CCGAS的算法步骤如下:

步骤1:对SOFM神经网络进行纵向分割, 第1层到第2层部分为第1个模块, 第2层到第3层部分为第2个模块, 依次类推共分成N个模块。对每个模块采用一个子种群优化其结构和连接权值。即当t=0时, 对N个模块进行初始化生成N个子种群P1 (t) , P2 (t) , …, PN (t) 。

步骤2:对每个模块 (子种群) 进行编码, 其中结构 (节点间的连接关系) 采用二进制编码, 连接权值采用实数编码。

步骤3:对每个子种群选择代表个体组成合作团体, 经解码后得到各自的SOFM神经网络。选择时采用的适应度函数为:

其中, ypi为输入, 为输出, ε为适当小的正数。︵ypi

步骤4:经交叉和变异操作优化SOFM神经网络结构, 得到最优个体, 进化后生成新的子种群。

步骤5:若满足终止条件则停止进化, 输出最优的SOFM神经网络;否则t=t+1, 转步骤3。

5 CCGAS在矿井突水问题中的应用

5.1 问题描述

迄今, 基于GA的ANN已被用于材料、化工、生物医药、航空航天等领域[16,17,18,19]。本文将CCGAS用于矿井突水水源预测问题, 以检验CCGAS的算法性能。

现采集到某煤矿的39个水源样本, 分别来自4个主要含水层:二灰和奥陶纪含水层、八灰含水层、顶板砂岩含水层和第四系含水层。以每个水源样本中的Na+、K+、Ca2+、Mg2+、CI-、SO42-和HCO3-这7种离子的含量作为判别因素, 利用CCGAS设计的SOFM神经网络进行综合评价。

5.2 解决思路与步骤

问题解决步骤如下:

(1) 产生训练集和测试集。由于采集到的水源样本较少, 为了保证所建立的判别模型具有较好的分辨性能, 从每个含水层中各取出一个水源样本作为测试集, 剩下的35个水源样本作为训练集。

(2) 用CCGAS创建、训练SOFM神经网络。应用CCGAS算法优化得到SOFM神经网络的结构和连接权值, 并利用训练集对网络进行训练。

(3) 仿真测试。判别模型训练完成后, 将测试集中的4个样本对应的7个判别因素输入模型, 模型的输出即为各水源样本的预测类别。

5.3 结果分析与算法性能评价

为了检验新算法的性能, 本文分别用常规SOFM神经网络和CCGAS神经网络对数据进行了分类, 表1给出了两种算法的分类结果。

从表1中可以看出:

(1) 对于常规SOFM神经网络, 第II类水源的获胜神经元应为第1个神经元;第III类水源的获胜神经元应为第2个神经元;第I类和第IV类水源的获胜神经元难以确定。因此, 测试集中的37号和38号样本分类正确, 而36号和39号样本难以判断。

(2) 对于CCGAS神经网络, 第I类水源的获胜神经元编号为3、8、11、12、14;第II类水源的获胜神经元编号为14、15、16;第III类水源的获胜神经元编号为1、2、5、6;第IV类水源的获胜神经元编号为4、7、8、13。测试集中4个水源样本对应的神经元编号均在获胜神经元编号集中, 即CCGAS神经网络的判别正确率为100%。

图1和图2分别给出了SOFM和CCGAS的获胜神经元统计结果, 神经元编号方式为从左至右、从下至上, 图中的数字为该神经元的获胜次数。

从图1可以看出, 3号神经元从未赢得获胜机会, 即成为“死”神经元。若测试集中某个水源样本的获胜神经元编号为3, 则难以确定其属于哪一类水源, 即SOFM神经网络的确存在“死”神经元现象。

图2显示, 所有神经元均有获胜机会, 在SOFM神经网络中成为“死”神经元3号神经元在CCGAS神经网络中恰恰成为获胜次数最高的神经元。这表明, CCGAS神经网络可在一定程度上避免“死”神经元现象。

由于神经网络在训练过程中采取的是随机抽样法, 所以每次运行的结果不尽相同。为了科学地评价新算法的性能, 表2给出了SOFM和CCGAS在10次运行中的节点数、分类成功次数和CPU耗时的平均值。其中, SOFM的节点数是固定的。

从表2可以看出, CCGAS算法的节点数和运行时间远少于SOFM, 原因是CCGAS算法通过优化方法设计神经网络, 优化后的神经网络不含有冗余的节点, 降低了算法的复杂度。另外, CCGAS算法的分类成功率较SOFM算法有了较大幅度的提高, 表明CCGAS算法具有较好的全局收敛性。

6 结语

遗传算法和神经网络是近二、三十年发展起来的人工智能算法。单个智能算法不可避免存在某种缺陷, 将两种或多种智能算法相结合或在某智能算法中引入其它智能算法, 是解决单个智能算法缺陷的有效方法, 这种研究思路已被越来越多的学者所重视。

枣庄市循环经济与协同进化研究篇8

煤炭资源是重要的不可再生的能源资源, 煤炭资源的开发及其相关产业发展带来的聚集效应促进了地方经济的发展, 大量“缘煤而建、缘煤而兴”的城市应运而生:一方面煤炭资源的开发是煤炭城市得以产生并发展的必要条件, 另一方面煤炭资源的储量、赋存条件、品质也决定了煤炭城市主导企业的效益与生命周期。随着煤炭资源的日趋枯竭, 煤炭城市所面临的产业单一、后备资源不足、环境污染严重、从业人员转岗就业负担过重、煤矿企业与煤炭城市管理关系不顺等矛盾日益显现出来, 影响着煤炭城市的可持续发展。

1 循环经济是煤炭城市可持续发展的基础

熵是热力学中引入的表示系统无序程度的物理概念, 系统越无序, 熵就越大。煤炭城市系统的演化发展遵循着普利高津的总熵变方程[1]:ds=des+dis。des为负熵流, 主要由两部分组成:一是煤炭资源开采获得的物质流和能量流, 即des1;二是外界环境向煤炭城市系统输入的物质流、能量流和信息流, 即des2。随着煤炭开采生产的周期变化, 系统可以获得的负熵越来越少, 系统内部的熵产生dis却越来越大。如此下去, 煤炭城市最终将走向无序, 面临煤炭企业破产, 煤炭城市衰败的严重后果。煤炭城市可持续发展要求建立合理的控熵增序机制, 促进煤炭城市系统各组成要素的协同发展。而循环经济则是煤炭城市控熵增序的重要手段。

第一, 循环经济以经济效益、环境效益和社会效益三维整合为目标, 以遵循减量化 (reduce) 、再利用 (reuse) 和再循环 (recycle) (3R原则) 为原则, 分别对系统输入端、系统的过程、系统的输出端进行系统熵的控制。煤炭城市发展循环经济, 通过建立煤炭生态产业链, 把经济活动组织成“资源—产品—再生资源”的反馈式流程, 通过推广煤炭清洁生产和清洁利用, 最大限度的利用进入系统的物质和能量, 提高资源的利用率, 增加系统负熵;最大限度的减少污染物的排放, 提升经济运行质量和效益, 有效地保护生态环境, 减少系统熵产生, 实现煤炭城市生态环境和经济的协调发展。

第二, 循环经济通过提高煤炭资源利用效率、延长产业链、减少污染, 降低了煤炭企业和煤炭城市之间、人口、资源、环境、经济等子系统之间的矛盾, 各子系统的边界得到扩张, 子系统之间的相互作用加强, 增加了系统内部诸要素之间在行为、结构、范围上的协同。当煤炭城市系统在控制变量达到一定临界时, 通过正反馈的自我复制、自我放大机制形成巨涨落。系统在失去稳定时, 能通过系统内各要素的协同作用和相干效应跃迁到一个新的有序状态[1]。由原来的高熵转变到低熵, 由低级有序结构转变为更为高级的有序结构。

2 煤炭城市系统协同进化序参量

根据哈肯的激光模型[2], 分析一个简单的煤炭城市演化模型。城市规模变化率 $\dot{x}$ 由两个因素决定:一是城市规模的扩大, 二是城市的损耗。城市规模变化率与现有城市规模x成正相关。同时, 由于煤炭城市是因为煤炭资源的开采与加工利用生产而发展起来的城市, 煤炭城市对煤炭产业具有很强的依赖性, 因此城市规模变化率与煤炭资源的可开采量G成正比。

煤炭城市规模增长=KGx (1)

式中K为增益系数, 可以认为是技术因素。

在煤炭城市系统, 城市的损耗可以简单认为是由于煤炭资源开采造成的环境污染, 是由城市规模的扩大引起的, 城市每天排放污染物数量与城市规模成正比。

损耗=Nx (2)

式中N为损耗系数, 与城市环境治理有关。循环经济运行的越好, 煤炭资源利用率越高, 产生的废弃物越少, N越小。联立 (1) (2) 两式, 得如下煤炭城市演化方程:

$\dot{x} = Κ G x - Ν x (3)$

设定煤炭储量为G0, 已开采量为△G, 则关于可开采量X的等式为:

G= G0-△G (4)

而已开采量△G与现有城市规模成正比, 令α为煤炭资源开采对城市发展的贡献率, 即:

G=αx (5)

将 (4) (5) 式代入方程 (3) 即得:

$\dot{x} = (Κ G_{0} - Ν) x - Κ α x^{2} (6)$

式中Kα>0。KG0-N可以为正数, 也可以为负数, 在技术条件不变的情况下, 一方面取决于煤炭储量G0, 另一方面取决于N的大小。若煤炭城市经济运行模式是简单的“资源开采—生产—排放废物”的线性特征, 资源开采过程中的浪费和资源生产伴随的环境污染使G0变相减少, N增大, KG0-N为负数, 煤炭城市发展出现衰退。相反循环经济模式的实施, 一方面通过清洁生产做到减量化生产和废弃物再利用的途径变相的增加了资源拥有量G0, 另一方面污染物产生系数N减少, 从而KG0-N逐渐增大并大于零。

分析方程 (2-6) , 煤炭城市系统的不动点为 $x_{1} = 0, x_{2} = \frac{Κ G_{0} - Ν}{Κ α}$ 。当 $\frac{Κ G_{0} - Ν}{Κ α} ＜ 0$ 时, x1=0是稳定的, $x_{2} = \frac{Κ G_{0} - Ν}{Κ α}$ 不稳定, 即城市在衰退的过程中, 人口、企业外迁, 城市基础设施陈旧老化甚至报废, 城市规模不断减小, 最终趋于消亡;在 $\frac{Κ G_{0} - Ν}{Κ α} ＞ 0$ 时, $x_{2} = \frac{Κ G_{0} - Ν}{Κ α}$ 是稳定的, x1=0不稳定, 即城市在循环经济作用下资源、环境、人口、经济等子系统不断协同作用, 煤炭城市系统跃迁到持续稳定发展的新阶段。故 $\frac{Κ G_{0} - Ν}{Κ α} = 0$ 为分叉点, 在该分岔点, 煤炭城市系统稳定性交换, 城市发展性质发生改变。

若 $\frac{Κ G_{0} - Ν}{Κ α} = 0$ , 则推导出:

KG0-N=0 (7)

由 (7) 式可知, 煤炭城市系统发展的分岔点其实就是煤炭城市增益与损耗相持平的点, 是煤炭城市依赖煤炭资源发展的极限点。此时, 煤炭城市系统对偶然和随机出现的“涨落”会有放大作用, 可能出现巨涨落, 导致系统发生宏观的变化。如煤炭价格的小幅变动、煤炭生产安全事故、煤炭城市政策调整等一些小的偏差将会导致整个系统完全不同的发展前途。采用“资源消费一产品一废物排放”的单程型线性经济发展模式, 系统将逐渐衰退直至崩溃;采用“资源消费一产品一再生资源”闭环型循环经济发展模式, 在煤炭城市和企业内实施污染治理、废物利用、清洁生产, 使煤炭企业在节约生产成本、减少污染排放、提高物质利用效率的过程中, 形成相互促进、共同发展的生态产业链, 以良好的经济、环境和社会效应, 吸引、带动整个城市的有序发展[3]。可见, 循环经济是煤炭城市系统在涨落产生后使城市系统跃迁到更加有序和稳定发展阶段的动力, 是在煤炭城市进化过程中的一个主导参量。

3 煤炭城市系统协调度评价指标与模型

根据协同学理论, 序参量对系统演化发展的决定作用。系统演化过程中, 序参量通过对子系统的支配或役使作用, 主宰着系统整体演化的过程。循环经济是煤炭城市系统协调发展的序参量。本文以循环经济为基础, 选择煤炭城市系统序参量变量, 建立协调度评价模型。

3.1 煤炭城市系统协调度指标体系

煤炭城市系统包括人口子系统、经济子系统、资源子系统、环境子系统。各子系统在循环经济作用下协调发展的特征主要表现在资源减量化及高效利用、生态环境质量提高、经济发展、产业多元化和人口素质提高等方面。因此, 本文用工业用水重复利用率、煤炭有效利用率、万元产值能耗定义的资源系统有序度;用煤炭城市人均GDP、煤炭采选业产值占工业产值比重定义经济系统的有序度;用人口城市化率与科技活动人员比例定义人口子系统的有序度;用废气排放年平均值 (包括SO2、空气悬浮颗粒) 、废水排放达标率、固体废物利用率定义环境系统有序度 (图1) 。其中, 煤炭资源有效利用率为原煤入洗率、煤炭回采率两者的算术平均;城市化率用人口城市化来衡量, 即为城镇人口占城市总人口的百分比。

3.2 协调度评价模型导入

参考已有的协调度计算方法[4,5], 令各子系统i (i=1, 2, 3, 4) 的序参量变量指标为eik, k∈[1, n]且n≥1。若eik为效益型指标, 取值越大系统越有序;若eik为费用型指标, 则取值越小系统越有序。定义Φi1、Φi2分别为效益型指标集和费用型指标集, 则煤炭城市子系统各指标有序度为:

$u_{i} (e_{i k}) = {\begin{cases} (e_{i k} - E Ι_{i k} / (E Μ_{i k} - E Ι_{i k} k = Φ_{i 1} \\ (E Μ_{i k} - e_{i k} / (E Μ_{i k} - E Ι_{i k} k = Φ_{i 2} \end{cases} (8)$

式中EIik、EMik为煤炭城市i子系统第k个指标的下限值和上限值。下限值采用1998年的实际值, 上限值为2020年的煤炭城市规划值。

采用几何平均算法对子系统各指标有序度ui (eik) 进行综合集成, 则各子系统有序度为:

$u_{i} = (\prod_{k = 1}^{n} u_{i} (e_{i k}))^{1 / n} (9)$

由以上公式可知, 0≤ui≤1, ui (eik) 与ui越大, 子系统越有序。

设对于给定的初始时刻t0, 煤炭城市各子系统有序度为ui0, 煤炭城市系统在经历t时段的发展演变后的有序度为uit。若uit-ui0≥0在i=1, 2, 3, 4时同时成立, 系统是有序的。定义煤炭城市系统有序度模型为:

$X D (t) = θ \sqrt[4]{| \prod_{i = 1}^{4} (u_{i}^{t} - u_{i}^{0}) |} (3 - 3)$

式中 $θ = \frac{\min (u_{i}^{t} - u_{i}^{0}) \neq 0}{| \min (u_{i}^{t} - u_{i}^{0}) \neq 0 |} ‚ θ$ 是标度有正的协调度的参数, 当且仅当uit-ui0>0时, 系统才会在t0—t时段有序发展。

4 枣庄市协同发展演化

枣庄市煤炭开采始于1818年, 枣庄煤矿对枣庄市的形成与发展具有重要作用, 素有鲁南煤城之称, 是典型的煤炭资源型城市。从1960年建市到2008年, 城市发展经历了由无到有, 由盛到衰, 在衰退中求发展的演化过程。由于数据资料的限制, 本文仅计算枣庄市近十年的有序度 (见表1、表2) 。

由计算结果可以得到以下结论:

(1) 从1999年到2007年, 枣庄市资源子系统有序程度较高, 且呈逐步增加趋势。其中, 煤炭资源有效利用率对枣庄市资源子系统有序度的贡献率较大。2003年, 枣庄田陈煤矿作为全国首家薄煤层综采机组的试验开采获得成功, 达到了国际先进水平, 由该技术的支持, 在提高煤炭回采率一系列制度的配合下, 近5年来, 枣庄市煤炭企业工作面回采率平均达到96.40%, 采区回采率达到87.24%, 矿井回采率达到79.97%, 指标均超过国家规定[6]。与此同时, 资源子系统的另一指标——万元产值能耗对子系统有序度贡献率偏低。由于枣庄市属于资源型城市, 重工业比重较大, 城市发展又处于加速工业化时期, 因此能源强度较高, 虽然近几年来积极进行节能减排, 但仍不能完成山东省政府提出的年单位GDP能耗下降4.5%的目标。

(2) 枣庄市经济子系统人均GDP序参量有序度不断提高。近十年间, 枣庄市人均GDP年均增长15%, 增幅较大, 但是枣庄市经济总量偏小, 人均GDP水平仅达到全省平均水平的89.5%, 有序度不高。煤炭采选业占工业产值比重序参量对枣庄市经济子系统有序度影响较大。枣庄市经济对煤炭资源的依赖性强, 相关产业链条短、整体效益不高, 从而煤炭采选业产值占工业产值的20%左右。1998年至2007年由于煤炭价格波动, 导致煤炭采选业产值比重波动较大, 从另一方面也反应了枣庄城市经济工业产业结构单一化的特点。

(3) 枣庄市环境子系统有序度有升有降, 但总的趋势是增加的。枣庄市工业主要由煤炭、水泥、电力、炼焦、化工等高耗能、高污染企业为主, 部分煤质较差, 含硫量较大, 城市周围煤矸山长期自燃, 排放出大量的二氧化硫和尘埃, 水泥生产也造成较严重的粉尘污染。2002年, 枣庄市工业污染治理投资额大幅度增加, 从1998年截止到2007年, 年均增长20%。大量的环境投资带来了环境质量的提高, 枣庄市工业固体废物利用率达到98%, 工业废水排放达标率在90%以上, 空气SO2平均值与空气可吸入颗粒物年均值均有一定下降。

(4) 枣庄市人口子系统有序度较低。一方面, 枣庄市人口城市化率仅为32%左右。1999年到2001年, 受煤炭价格影响, 枣庄城市经济年均增长8%, 低于全省平均水平, 同时, 迁出人口数大于迁入人口数, 人口城市化率有一定的起伏。另一方面, 枣庄市科技人员比例低, 从总体上看, 经济增长主要依赖资源的高消耗、资金的高投入, 科技进步的拉动力较弱。

以各子系统有序度为中间变量, 以1999年枣庄市各子系统有序度为基准, 计算得到枣庄市系统总协调度 (见表3、图2) 。

由表3及图2可知, 1999—2007年, 枣庄市城市发展总协调度有正有负, 总协调度为负的年份较多, 反应枣庄市协同发展能力不足。总协调度为负值的主要原因有:环境质量的退化、人口城市化率偏低、产业结构单一。具体分析如下:

(1) 1999—2002年, 枣庄城市系统在这一时期为非协同发展。由于枣庄市煤炭资源长期开采, 资源开采难度不断增加, 矿井开采成本持续上升, 虽然加强了煤炭资源的利用效率, 但是煤炭价格偏低, 这导致严重依赖煤炭资源的枣庄城市经济增长缓慢, 煤炭采选业产值比重持续下降, 经济系统虽有序度增加, 但经济有序度的值非常小。同时, 作为污染大户的煤炭采选业产量的下降, 使环境污染程度降低, 环境系统有序度提高, 显然并非完全是环境治理的结果。经济的缓慢增长导致城市对人口迁入的吸引力降低, 人口迁出特别是科技人员迁出增加, 这一时期, 人口城市化率呈下降趋势, 人口系统有序度为负值。

(2) 2002—2005年, 枣庄城市各子系统协同关系呈波动状态。这一时期, 煤炭价格大幅上升, 城市经济得到恢复和发展, 但煤炭采选业产值比重也相应提高。从2002年开始, 枣庄市明确循环经济发展方向, 大力发展非煤产业, 非煤产业固定资产投资增长远远超过煤炭采选业, 但是由于固定资产投资效益的延迟特性, 经济子系统有序度并不稳定, 并波及到人口子系统有序度的变化。同时, 枣庄市环境治理效果明显, 环境系统有序度不断提高。

(3) 2005—2007年, 煤炭价格增幅趋缓, 且枣庄市非煤产业产值逐年提高, 经济子系统、人口子系统、资源子系统有序度稳步增加。这一时期, 环境子系统显然与其它子系统发展并不同步, 经济的增长、人口的增加导致排污强度的增大, 还应进一步加强环境治理的力度。

5 结论

本文所计算的1999—2007年枣庄市协调度是在确定协同序参量——循环经济序参量, 并对现有枣庄市统计资料分析的基础上得出的。从计算结果来看, 由于枣庄市循环经济发展水平较低, 出现了产业结构较单一导致的经济子系统不协同、经济子系统与人口系统的不协同、环境治理与经济发展水平的不协同。从总体上看, 枣庄市演化发展的协调度不高, 波动性较大。

对煤炭城市而言, 要可持续发展必须突破资源限制、控制环境污染、提高人口素质, 延长产业链条, 逐步实现产业转型。煤炭城市循环经济把清洁生产和废弃物的再循环利用融为一体, 形成“煤炭资源—产品—再生资源”的反馈环, 实现资源的可持续发展利用和对生态环境的保护, 并通过循环经济产业链对煤炭资源实行深加工, 实现多元化生产, 为煤炭城市的经济发展注入了新的活力。因此, 循环经济是煤炭城市协同发展的必然选择。

参考文献

[1]李士勇.非线性科学与复杂性科学[M].哈尔滨:哈尔滨工业大学出版社, 2006.

[2]赫尔曼.哈肯.协同学[M].上海:上海译文出版社, 2005.

[3]王云.基于耗散结构理论的循环工业发展研究[D].西安:西安理工大学, 2007.

[4]雷社平.区域产业用水系统的协调度分析[J].水利学报, 2004 (5) :14-19.

[5]李廉水.南京市3E系统协调度分析[J].机械制造与自动化, 2007 (1) :126-129.

【协同进化算法】推荐阅读：

进化算法10-04

微进化算法09-27

进化遗传算法论文05-20

混沌量子进化算法07-06

量子微分进化算法09-02