两阶段遗传算法（精选7篇）
两阶段遗传算法 篇1
0 引言
动态因果模型[1 - 4]DCM是通过不同的成像技术推断在神经元水平下脑活动的通用框架, 是一种进行功能整合的有效方法。在过去的几年中, DCM作为一种估计有效连接[5]的方法应用到功能磁共振成像数据的处理上, 在影像学中获得了很快的普及[6]。传统的DCM建模基于先验指导, 然而最优的DCM模型很可能存在于先验指导之外的模型空间中。
1975 年Holland教授首次提出了遗传算法[7]的思想, 并吸引了大批的研究者。遗传算法提供了一种求解复杂系统优化问题的通用框架, 它不依赖于问题的具体领域, 对问题求解的范围有很强的适应性[8]。遗传算法的主要应用领域包括函数优化、组合优化、生产调度、自动控制、机器人学、图像处理、人工生命、机器学习、数据挖掘等[8]。启动遗传算法的要素包括问题的解决方案集合 ( 种群) 以及适应性函数。适应性函数用来评估解决方案的优异程度, 然后通过选择方法决定个体是被丢弃或者遗传给下一代, 通过交叉和变异用来产生新个体: 变异是对群体中的个体串的某些基因座上的基因值作变动, 交叉是把两个父代个体的部分结构加以替换重组而生成新个体的操作。
近年来M. Pyka[9]等人首次将遗传算法应用于DCM寻优问题, 把整个DCM空间作为解空间, 摒弃了先验模型的指导, 并验证了该方法在DCM模型搜索中是适用的。M. Pyka的遗传算法设计没有局限于局部最优, 但是较大的变异幅度导致该算法在后期搜索聚集到全局最优[10]后, 对全局最优空间的搜索并不高效。本文针对该缺陷提出了两阶段遗传算法来进行DCM优化求解。
1 基础理论
1. 1 DCM简介
DCM是一种基于非线性神经系统的模型。DCM采用双线性微分方程组来近似描述, 利用贝叶斯模型估计[11]来估计模型各生理参数。
在DCM中假设激活区的数量为N, 这N个激活区神经元活动随时间的变化率可以描述为一个多变量的微分方程, 如下:
式中t为时间变量, 单位为s; zt为状态变量; m为刺激输入的数量, ut为刺激输入的时间函数。因变量dzt/ dt与zt和ut的乘积呈线性关系, 所以上式所描述的是一个双线性模型。表达式中A、Bj和C为常数矩阵, 它们分别为内连接矩阵、双线性连接矩阵和驱动输入矩阵。其中矩阵A表示各激活区的内在连接, 即没有刺激输入的情况下各激活区间的有效连接。矩阵Bj表示第j个刺激输入对激活区之间的有效连接的作用。矩阵C表示刺激输入对激活区的作用。
本文将遗传算法应用到动态因果模型的模型寻优中, 将动态因果模型中的内连接、驱动输入、双线性连接的连接矩阵作为遗传信息并编码转化为遗传因子, 并用软件SPM8 中自带的贝叶斯模型选择作为筛选功能。
1. 2 贝叶斯模型选择原理
贝叶斯模型选择是针对模型决策统计的一个基本方法。其原理为在给定的样本和相关参数下, 求得后验概率最大的模型。假设给定的样本为D, 则模型M的先验概率与似然函数的乘积是与模型M的后验概率成比例的。假设模型先验分布为P ( M) , 则贝叶斯模型选择等同于下面的优化问题:
其中P ( M) 可以根据专家的知识和样本的信息来适当选取。当先验信息不存在的情况下, 可以采用贝叶斯假设将P ( M) 看作均匀分布。这时贝叶斯模型选择进一步简化为下面的优化问题:
2 经典遗传算法优化求解DCM
遗传算法DCM求解步骤包括:
( 1) 随机产生初始个体: 随机产生连接矩阵A、B和C, 并将A、B和C连接矩阵信息编码为二进制染色体;
( 2) 产生4 个个体启动循环: 用改变 ( 1) 产生染色体的八个随机的二进制位来产生其他3 个不同的个体。将4 个个体作为启动遗传算法启动基因, 循环标志初始化: i = 1, 开始循环;
( 3) 产生种群: 由4 个个体交叉和突变来产生其他16 个个体, 这20 个个体组成一个种群。具体步骤为: 从4 个个体中随机选取两个, 并随机产生这两个个体染色体的交叉点, 在该交叉点处将这两个个体的染色体进行置换。对新生成的个体以0. 5 的概率[9]来选择是否发生突变 ( 改变染色体中随机选择的n位, 其中n为2 到8 之间的一个随机整数) 。由于矩阵B是刺激作用于内连接的连接矩阵, 即矩阵B的配置依据于矩阵A, 所以我们根据矩阵A中的内连接去掉矩阵B中的无效刺激, 此外, 还要检查生成的个体是否与本代或者其他代重复, 如果重复那么放弃该个体, 并用上面算法重新生成个体。按以上方法执行16 次, 产生的16 个新个体与4 个父代个体组成一个种群;
( 4) 择优: 将20 个个体中的信息转化为DCM。用SPM8 软件对DCM进行模型估计, 然后用贝叶斯模型选择将这20 个DCM按优异程度进行排序。i = i + 1, 当i < 50 时, 选择排名前四位的4 个个体, 继续执行步骤 ( 3) , 否则执行步骤 ( 5) ;
( 5) 找出排名最高的个体, 终止程序。
经典遗传算法为了避免寻优限于局部最优, 所以设置的变异幅度比较大, 这样可能造成遗传算法聚集到全局最优后, 搜索效率不高。所以本文提出两阶段遗传算法进行DCM优化求解。
3 设计两阶段遗传算法优化求解DCM
两阶段遗传算法DCM优化求解将优化过程分为前、后两个阶段。前阶段为经典遗传算法DCM寻优阶段, 该阶段使用的是经典遗传算法, 根据以往实验的经验设置最大进化代数为30, 使遗传算法聚集到全局最优。后阶段为自适应遗传算法DCM寻优阶段, 该阶段采用自适应遗传算法, 设置最大进化代数为20。
自适应遗传算法是将经典遗传算法步骤 ( 3) 中的遗传概率和变异幅度分别与本次迭代中的模型的负自由能和模型编码后的海明距离相联系, 负自由能是指SPM贝叶斯模型选择软件针对模型进行拉普拉斯逼近求解的过程中所给出的判别模型相对优异程度的依据, 而贝叶斯模型选择是指利用贝叶斯理论在给定的数据样本和相关参数信息的条件下, 寻求具有最大后验概率的模型, 海明距离是指两个二进制向量之间的不同位的个数。其具体做法如下:
( 1) 选择用于交叉的两个个体的做法为: 四个个体中优异程度排序为x、y的两个个体以Pxy的概率被选中, Pxy的计算公式为:
式中, Mk表示把遗传算法上一代运行产生的20 个个体按优异程度进行排序后, 第k个个体染色体对应的DCM模型, F ( Mk) 为模型Mk的负自由能。
( 2) 排序为x、y的个体交叉产生的新个体以0. 5 的概率进行变异。变异的具体做法为: 首先等概率随机生成一个1 到H之间的正整数N, 然后在新生成个体的染色体中随机选择N个二进制位进行变异, 其中H的计算方法如下:
式中Ham ( x, y) 表示个体x、y的染色体之间的海明距离。式 ( 1) 表明让优秀的个体组合以高概率参与变异; 式 ( 2) 表明变异幅度会随着结果的收敛而逐渐变小, 这样有利于在最大可能的模型空间发挥出更高效率的搜索。
4 实验结果及分析
4. 1 实验数据
本实验采用互联网上提供的一组真实数据集[12] ( http: / /www. fil. ion. ucl. ac. uk / spm / data / attention / , 由Büchel and Friston提供) 作为实验数据, 这组数据来自于研究心理、注意对视觉通路影响的试验。该实验由Photic、Motion和Attention三个刺激输入构成, 这三个输入分别代表所有不同性质的光点、运动光点、加入注意成分的运动光点。实验提取了四个激活区, 分别为: 初级视皮层 ( V1) 、视觉运动区 ( V5) 、额下回 ( IFG) 与上顶叶皮层 ( SPC) 。
这组数据建立的DCM模型包含4 个激活区和3 个外部刺激。内连接矩阵A由16 ( 4 × 4) 个二进制位组成, 其中矩阵A的主对角线上的元素代表自我抑制连接是默认存在的, 则在这16位中不确定的二进制位为12 位, 因此矩阵A转码为染色体的有效位为12 个。双线性连接矩阵B的配置受内连接矩阵A的影响, 所以矩阵B转码染色体中的有效位数和矩阵A的配置有关。而刺激输入矩阵C是一个4 × 3 的矩阵, 矩阵C转码为染色体的有效位为12 个。
4. 2 实验分析
1) 实验方法
本文从下面几个方面来比较经典遗传算法DCM寻优与两阶段遗传算法DCM寻优的优劣:
( 1) 比较两种算法得到的全局最优解及其求解稳定性。
( 2) 比较每次两种算法平均所能找到优于Friston等人提出的经典DCM的模型数量, 并用SPM贝叶斯模型选择来对比两种算法找到的最优模型。
为了从上面两个方面进行算法对比, 本文将实验数据分别按照方案 ( 1) 、方案 ( 2) 进行处理。
方案 ( 1) 首先将实验数据用经典遗传算法寻优迭代30次, 然后将结果作为启动个体分别输入经典遗传算法与自适应遗传算法, 两种遗传算法各进行20 次迭代。
方案 ( 2) 将实验数据分别用经典遗传算法与两阶段遗传算法各运行10 次每轮都循环迭代50 代, 每轮两种算法都以同一个随机生成的DCM模型来启动。
2) 两阶段遗传算法和经典遗传算法计算比较
(1) 优化过程对比
对方案 ( 1) 处理的数据进行分析显示: 当算法收敛到全局最优后, 两阶段遗传算法 ( 改进遗传算法) 相对于经典遗传算法在寻优过程中具有明显的优势。两种算法的寻优过程对比情况如图1 所示。图1 中横坐标表示迭代次数, 纵坐标为本次迭代寻找到的最优模型与迭代30 次寻找到的最优模型的负自由能差值 ( 相对优异程度) 。
从图1 中可以看出: 当算法收敛的情况下, 两阶段遗传算法比经典遗传算法具有更高效的寻优能力, 而且改进遗传算法的寻优曲线爬升比较稳定, 然而经典遗传算法的寻优过程稳健性比较差, 这表明经典遗传算法全局搜索效率的不足。两阶段遗传算法比经典遗传算法最终找到的最优模型更优秀。
( 2) 优化结果对比
对方案 ( 2) 处理的数据进行分析, 经典遗传算法平均每轮运行找到43 个优于Friston等人提出的经典DCM的模型, 而两阶段遗传算法平均每轮运行找到72 个, 平均比普通遗传算法多找到67% 。
用SPM软件对两阶段遗传算法和经典遗传算法找到的最优DCM模型进行贝叶斯模型选择, 结果如图2 所示。
图2 中横坐标是20 个DCM, 其中模型1—10 为两阶段遗传算法寻找到的最优模型, 模型11—20 为经典遗传算法找到的最优模型, 纵坐标为模型被选为优秀模型的概率。从图中可以看出, 成对贝叶斯模型选择显示超过85% 的概率会选择两阶段遗传算法的结果。并且在贝叶斯模型选择中可以明显看出两阶段遗传算法找到的模型比经典遗传算法找到的模型更具有优异性。
进一步地将两阶段遗传算法找到10 个最优模型中性能最好的模型记作模型A, 将经典遗传算法找到10 个最优模型中性能最好的模型记作模型B, 对模型A和模型B分别建立模式图, 如图3 和图4 所示。
由图3 和图4 的对比可以看出, 经典遗传算法和两阶段遗传算法找到的最优DCM模型具有高度一致性, 这验证了M.Pyka[9]的遗传算法进行DCM寻优找到的最优DCM具有高层次一致性的结论。模型A与模型B都认为激活区V1 到V5、V5 到PFC、PFC到IFG和PFC到V5 存在正向连接。并且都一致认为刺激输入attention对激活区IFG与V5 有激励作用; 刺激输入motion对激活区V1 有激励作用, 且增强了激活区IFG到V1 和PFC到IFG的连接作用, 同时抑制了激活区V1 到V5 的连接作用; 刺激输入photic对激活区V1 有激励作用, 对激活区V5 有抑制作用, 且增强了激活区IFG到V1 的连接作用。模型A与模型B差别在于是否存在激活区V5 到激活区V1 的连接, 这个差别表现在在染色体上只有一个海明距离。经典遗传算法变异幅度较大, 很难从模型B搜寻到模型A。两阶段遗传算法在后期模型搜寻中随着寻优的收敛而减小变异幅度, 所以从模型B到模型A的搜寻比较容易。
对模型A和模型B进行贝叶斯模型选择得出模型A比模型B更具有优异性, 这也验证了两阶段遗传算法找到的最优模型在性能上优于经典遗传算法。
5 结语
本文提出了两阶段遗传算法, 该算法分为经典遗传算法和自适应遗传算法两个阶段: 前阶段采用变异幅度较大的经典算法进行全局搜索, 快速聚集到全局最优空间; 后阶段采用自适应遗传算法, 弥补了经典遗传算法搜索后期搜索效率不高的缺点。本文采用真实的数据论证了两阶段遗传算法相对于经典遗传算法在寻优过程中更稳定高效, 寻优的结果更具有优异性。无论是经典遗传算法还是两阶段遗传算法都寻找到了很多优于Friston等人提出的经典DCM的模型, 由此看来遗传算法在DCM寻优的应用上有很大的前景。
摘要：动态因果模型是分析脑区间有效连接最有效果的方法。针对经典遗传算法在搜索最优动态因果模型DCM (Dynamic Causal Models) 的后期, 变异幅度过大这一缺陷进行改进, 提出两阶段遗传算法。利用网上的真实数据集实验表明, 相对于经典遗传算法, 两阶段遗传算法计算结果更优越。
关键词：动态因果模型 (DCM) ,经典遗传算法,两阶段遗传算法
参考文献
[1]Friston K J, Harrison L, Penny W.Dynamic causal modeling[J].NeuroImage, 2003, 19 (4) :1273-1302.
[2]Marreiros A C, Kiebel S J, Friston K J.Dynamic causal modelling for fMRI:A two-state model[J].NeuroImage, 2008, 39:269-278.
[3]Stephan K E, Kasper L, Harrison L M, et al.Nonlinear dynamic causal models for fMRI[J].NeuroImage, 2008, 42:649-662.
[4]贾传海, 张志强, 卢光明.动态因果模型的基本原理及其在脑功能磁共振成像中的应用[J].中国医学影像技术, 2009, 25 (1) :149-152.
[5]高晴, 陈华富.基于动态因果模型的运动执行和运动想象脑网络研究[J].电子科技大学学报, 2010, 39 (3) :475-460.
[6]Büchel C, Friston KJ.Modulation of connectivity in visual pathways by attention:cortical interactions evaluated with structural equation modelling and fMRI[J].Cereb Cortex, 1997, 7 (8) :768-78.
[7]丁建立, 陈增强, 袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展, 2003, 40 (9) :1351-1356.
[8]向佐勇, 刘正才.基于完全自适应策略的遗传算法[J].中南林业科技大学学报, 2007, 27 (5) :136-139.
[9]Pyka M, Heider D, Hauke S, et al.Jansen.Dynamic causal modeling with genetic algorithms[J].Journal of Neuroscience Methods, 2011, 194:402-406.
[10]刘坤.遗传算法自适应模糊神经网络控制[J].计算机仿真, 2005, 22 (9) :136-139.
[11]张艳, 陈春晓, 卢光明, 等.基于DCM的减法运算脑功能效应连通性方法研究[J].生物医学工程学杂志, 2009, 22 (5) :931-935, 940.
[12]Data Sets from Büchel and Friston@The Wellcome Department of Cognitive Neurology, 12 Queen Square, London WC1N 3BG, United Kingdom[EB/OL].http://www.fil.ion.ucl.ac.uk/spm/data/attention/.
两阶段遗传算法 篇2
遗传算法作为一种有效的全局搜索方法, 由于它具有鲁棒性、自适应和学习性、不需要其他辅助知识等特点, 也为多目标指派问题的求解提供了有效的途径[5,6,7]。
本文讨论一类两个目标的多任务指派问题的求解方法。首先给出该问题的数学模型;然后通过合理的编码策略和相关参数设计, 使用遗传算法求解该类问题;最后通过对算例的运算结果说明该算法的有效性。
一、两目标多任务指派问题及优化模型
某工厂的一条生产线上共有m个地方发生故障, 而且必须所有故障都排除后, 生产线才能恢复正常工作。现在该工厂安排个维修工人对这n (n<m) 个故障进行维修。
已知每个故障只需要一个工人维修, 为第i个工人维修第j个故障所需要的时间, 为第i个工人维修第j个故障, 工厂向该工人支付的基本维修费用。
并且工厂对维修工人支付的维修费用采取基本维修费用基础上的浮动计费制。即:当某一个工人维修第一个故障时, 工厂只支付基本维修费用, 从第二个故障开始, 每个故障的维修费用按照比例p依次上浮, 作为额外工作的费用。并且每位工人维修的故障数没有限制。
工厂希望能够合理地安排维修任务, 使得在尽早恢复生产线正常工作的前提下, 所支付的修理费用尽可能少。
首先, 我们建立该两目标多任务指派问题的优化模型。
因此可以建立以目标f1 (x) 最小化和目标f2 (x) 最小化为目标, 满足每个故障都有唯一工人在唯一次序下维修的条件的多目标0-1整数优化模型如下:
为了适合于二进制编码的遗传算法, 我们利用惩罚函数法[9]对模型 (1) 进行改进。
令
因此, 当惩罚因子M充分大时, 模型 (1) 就转换为如下无约束多目标优化问题:
二、遗传算法设计
首先给出遗传算法中的相关参数设计。
1. 编码设计:
模型 (2) 中共有nm2个0-1整数决策变量, 所以选择二进制编码较为适合。模型 (2) 的一个可行决策变量对应一个长度为nm 2的染色体。
2. 初始群体的选取和种群规模:
一般采用随机产生初始群体。而且初始种群规模的选择通常与染色体的个数有关[10]。规模越小, 获得最优解得遗传次数就越多;规模越大, 每一次的计算时间就会增加。
3. 适应度函数:
选取向量函数作为算法中的适应度函数。其中对任意两个变量x1和x2, 向量函数Fit (x) 的大小关系定义如下:
4. 选择算子:
采用最佳个体保存法与联赛选择法相结合的方法。其中, 最佳个体保存法是指将种群中适应度值最高的个体不进行配对交换, 而直接复制到下一代中。联赛选择法是指从群体中按照一定的数目随机选择个体, 把其中适应度值高的个体保存到下一代。
5. 交叉算子:
采用多点交换的交叉算子。交叉概率为r。
6. 变异算子:
采用单点变异, 即对挑选出的一个染色体根据长度nm2, 随机产生一个变异位置, 即[1, nm2-1]上的一个整数, 然后把原有的数字进行0-1变异。变异概率为q。
7. 迭代终止准则:
选择两个标准共同作为停止准则, 即最多迭代T代或者连续Q次最优解没有改变, 就停止。
下面给出算法的具体步骤:
step1首先将问题的搜索空间中每个可能的点表示为确定长度为n m 2的二进制串, 即染色体;确定群体规模N, 适应度函数Fit, 交叉率r和变异率q;
step2在定义域内随机选择N个染色体组成初始群体G (l) , 并令l=0;
step3计算G (l) 中每个染色体的适应值Fit;
step4令l=l+1, 从G (l-1) 中利用选择算子得到G (l) ;
step5 G (l) 中每个染色体按概率r参加交叉;
step6每个基因以概率q参与变异运算;
step7若满足预先设定的终止标准, 则停止, 否则转step3。
三、算例
下面给出一个具体的维修工人排除故障问题的算例, 来说明上述遗传算法的有效性。
某工厂的一个生产线上共有6个地方发生故障, 而且必须所有故障都排除后, 生产线才能恢复工作。现安排5个维修工人进行维修, 已知工人维修故障所需时间矩阵[tij]和基本维修费用矩阵[wij]的数据如下
且维修费用按照比例为=0.1。
遗传算法的相关参数为N=20, r=0.2, m=0.05, T=1000, Q=10。利用前面设计的遗传算法, 进行15次运算得到结果如表1。
由以上算例的计算结果可知, 利用遗传算法求解这种多层目标多任务指派问题是有效的。
进一步要考虑的是, 随着实际情况的不断发展变化, 会有许多更复杂形式的指派问题产生, 这就需要进一步研究多种优化算法的使用, 以获得满意的效果。
参考文献
[1]宋业新, 陈绵云, 张曙红.基于模糊指派的多目标多工程选址决策[J].系统工程理论与实践.2002, 22 (1) :108-111.
[2]甘勤涛, 阳平华, 耿立杰, 刘振国.模糊层次分析法在多目标运输指派问题中的应用[J].科学技术与工程.2006, 6 (5) :604-606.
[3]黄德才.求广义指派问题最优解的有效算法[J].控制与决策.1999, 14 (3) :272-275.
[4]周晶, 何建敏, 盛昭瀚.一类新型的指派问题的多目标模型[J].系统工程学报.1999, (2) :118-122.
[5]Rendens Flasse S P.Hybrid methods using genetic algorithms for global optimization[J].IEEE Transactionson Systems Man and Cybernetics (Part B) , 1996, 26 (2) :243-258
[6]陶世群, 蒲保兴.基于遗传算法的多级目标非平衡指派问题求解[J].系统工程理论与实践.2004, 24 (8) :80-85.
[7]Hajri-Gabouj Sonia.A fuzzy genetic multiobjective optimization algorithm for a multilevel generalized assignment problem[J].IEEE Transactions on Systems, Man and Cybernetics (Part C) , 2003, 33 (2) :214-224.
[8]Candler W, Norton R.Multilevel programming[R].World Bank Development Research Center, Washington D.C., 1977.
[9]王凌.智能优化算法及其应用[M].北京:清华大学出版社, Springer出版社.2001.
两阶段遗传算法 篇3
交货期对于模具制造业来说是至关重要的,它是模具企业在竞争中生存的重要条件。在尽可能满足交货期的前提下,合理安排生产,尽量避免资源浪费,实现生产准时化、均衡化,这是优秀企业追求的目标。
在模具制造过程中,电火花加工(EDM)是一个重要的生产环节,其过程如下:首先在CNC工序生产电极,然后用完成CNC的电极在对应的内模上进行电火花加工(一个内模对应多个电极)。电极在内模上进行电火花加工的过程是一个串行加工过程,即一次只能用一个电极在内模上进行加工。在最后一个电极加工完成后,内模的EDM工序才算完成。由于同时进入CNC、EDM单元加工的电极数目众多,资源有限,所以,制定一个合理的电极CNC和EDM加工顺序计划,使之既能保证内模按时完成,又能实现电极生产均衡化,是非常有意义的。
上述加工过程可以看作是一个由CNC和EDM两道工序构成,且后工序带成组特征的柔性流水车间(FF2)作业排序过程。柔性流水车间排序是并行机排序与流水车间排序的推广,它的特征是在某些加工工序上存在着并行机,因而它又具有并行多机调度问题的特征,其求解比一般的Flow Shop调度问题更为困难。1973年,Salvador[1]首次提出了FFS环境下的生产调度问题,在随后的30多年里,学者们对于该类问题进行了深入研究,其中Wittrock在文献[2]、[3]分别用周期调度和非周期调度启发式算法来解决FFS排序问题,Brah和Hunscke在文献[4]、[5]利用分枝定界法解决小规模的FFS问题。文献[6]对一个阶段有并行机,另一个阶段是单机的特殊Flowshop作了研究,给出了近似解算法。文献[7]对两个阶段,其中一个阶段有并行机,另一个阶段是单机的特殊情况作了研究,给出了近似解算法。可以看到,以往所讨论问题的目标多数是最小化最大完工时间。而对调度的另两个重要指标交货期和准时化指标的研究却很少;另外,对于柔性Flow Shop的带成组特征的调度问题研究也很少,Rasaratnam Logendran在文献[8]讨论了柔性Flow Shop的成组调度问题,通过试验设计比较分析了三种启发式算法(LN2PT2S、LN2PT2M、PT2LN2S)的性能,目标函数是最小化总的完工时间和;文献[9]通过建立提前/拖期惩罚费用最小的数学模型,利用启发式算法得到一个使提前拖期总成本为零的调度方案;文献[10]运用遗传算法对车间调度问题进行了优化,给出了自适应的遗传算子,进行了遗传算法参数设置,使得遗传操作大大简化,达到有效调度的作用。
本文对具有CNC和EDM两道工序,且后道工序带有成组特征水车间工作调度问题进行了一般描述,并以最小化停机待料时间、工件无效等待时间及模具拖期时间的总惩罚费用为目标建立了该问题的数学模型,然后利用遗传算法求满意解,并应用实例验证该算法的有效性。
2 问题描述
具有两道工序的柔性流水车间(FF2)调度问题的基本思想是:有n个工件,每个工件需要进行2个不相同阶段的加工,其中至少有一个阶段存在并行机。所有工件的阶段加工次序相同。每个工件在每个阶段中只能在一台机床上加工,每台机床每次只能加工一个工件。
本文所研究的问题在上述一般FF2模型的基础上,考虑了后道工序存在模具约束的调度模型,即电极在后道工序(EDM工序)的加工是受到EDM工序上加工的内模约束的,带有成组加工的特点。
为了进一步使问题具体化,根据模具加工的实际情况,本文提出以下假设:
(1)模具及其对应的工件的数量已知且确定;
(2)每套模具的最早开工时间、最迟完工时间已知且确定;
(3)每个工件在每个阶段必须并且只能在一台机床加工;
(4)工件在同个机床阶段中的并行机上的加工时间相同;
(5)允许工件在工序之间等待,两道工序之间具有无限的缓存能力;
(6)每一台设备同时只能加工或使用一个工件;
(7)工件一旦在设备上开始加工,不允许中途停下来,或插入其它的工件;
(8)在后道工序中,通常是用多个工件来加工一套模具,工件加工模具是一个串行加工过程,即一个工件一次只能加工一套模具。
文中涉及到的变量定义如下。
mj为第j道工序阶段内的机床总数,j=邀l,2妖;Mkj为第j道工序阶段内的第k个机台,k=邀l,2,…,m妖;nkj为安排在第j道工序内第k个机台上加工的工件数,k=邀l,2,…,m妖;n为待加工的工件总数,第i(1≤i≤N)套模具对应的工件数为ni,其中n1+n2+…+nN=n;[i,x]为在第i套模具上加工的第x个工件;p[t,x]j为工件[i,x]在第j道工序的加工时间;r[i,x]j为工件[i,x]最迟到达第j道工序的时间;t[t,x]j为工件[i,x]在第j道工序的开始加工时间;c[i,x]j为工件[i,x]在第j道工序的完成加工时间;tESi为第i套模具的最早开工期;tLFi为第i套模具的最迟完工期;Ti为模具i对应的最后一个加工工件ni的拖期时间,Ti=max(0,c[i,ni]2-tLFi);pjky和cjky分别为第j道工序内机台k中第y项加工任务的加工时间和完工时间;S为一个调度方案;f(S)为调度S的目标函数值。
本文的研究目的是将所有工件分配到各机台上加工,并且决定其加工次序,使得在模具既满足交货期要求,同时也满足准时化生产的要求。为此,本文定义三类造成增加模具制造成本的时间及其对应的单位惩罚成本系数:
(1)第i组工件后道工序停机待料的时间对应的单位惩罚费用系数为αi,其中Δt[i,x]h为第i组工件第x个工件导致的停机待料时间;
(2)第i组工件后道工序无效等待时间其对应的单位惩罚费用系数为βi,其中Δt[i,x]w为第i组工件第x个工件产生的无效等待时间;
(3)第i套模具的拖期时间Ti(即该组工件后道工序最后一个加工工件[i,ni]的拖期时间),Ti=max(0,c[i,ni]2-tLFi)其对应的单位惩罚费用系数为γi。
这样就初步得出本文的优化目标函数:
其中:
上述的表达式中:式(1)表示问题的目标函数;式(2)表示单位惩罚系数均为大于0的常数(3)表示每套模具的第1个工件在EDM工序内的开始时间不能早于模具的最早开工时间;式(4)表示每个工件在每个工序阶段必须被加工1次;式(5)表示任意一个工件必须在某一工序阶段中的某一机台上加工;式(6)表示同一个工件必须在前一道工序阶段加工完成后才能在下一道工序阶段上加工;式(7)表示同一台机床只有在加工完一个工件之后才可以加工另外一个工件;式(8)表示每个工序阶段中所有机床上加工的工件数目之和为总的工件数;式(9)表示每个工件只有在到达第1道工序后才可以被安排加工。
为使目标函数更加具体化,对目标函数中的Δt[i,x]h,Δt[i,x]w,c[i,ni]2作进一步推导如下。
(1)首先排程之前(t=0,CNC加工之前)给各工件集的工件加以编号,如第i组里的各工件记为Ji,1,Ji,2,…,Ji,ni为工件的初始记号。
(2)设S为任意一个调度方案,各组工件按S方案在第1道工序的各台机床里排序加工,记工件组J1k1,J1k2,…,J1knkj为第1道工序第k台机床上各工件加工序列,p1k1,p1k2,…,p1knkj为其对应的加工时间,c1k1,c1k2,…,c1knkj为完工时间,则有
(3)在S方案下,对第一道工序各机床排序的所有工件按其对应的模具i(i=1,2,…,N)的重新分组,然后对各组工件根据c1ky作不减排列,并加以编号,记为J[i,1]2,J[i,2]2,…,J[i,ni]2,此次序即为第二道工序的第i组工件的加工次序(第二道工序加工顺序遵循工件先到先加工原则),记下此组工件对应的前道工序的完工时间并标记为c[i,1]1,c[i,2]1,…,c[i,ni]1,设p[i,1]2,p[i,2]2,…,p[i,ni]2和c[i,1]2,c[i,2]2,…,c[i,ni]2为此组工件第二道工序对应的加工时间和完工时间。
(4)当c[i,x]1-c[i,x-1]2>0时,后道工序加工的工件J[i,x]2会导致一个EDM机床缺料等待时间量Δt[i,x]h,如图1所示。
则工件组i产生的总的停机待料等待时间量为:
(5)当c[i,x]1-c[i,x-1]2<0时候,J[i,x]2会产生一个工件无效等待时间量Δt[i,x]w,如图1所示。
则工件组i产生的总的工件无效等待时间量为:
(6)C[i,ni]2为第二道工序第i组最后一个加工工件J[i,ni]的完工时间,则有:
3 带成组特征的FF2问题求解遗传算法
遗传算法自从1975年由Holland提出至今已被广泛的应用到组合优化、机床学习、模式识别以及人工神经元网络等方面,它是一种高度并行、随机和自适应优化算法,它将问题的求解表示成“染色体”的适者生存过程,通过种群的一代又一代的进化,淘汰劣质解,最终收敛到最适应环境的个体,从而得到问题的最优解或满意解。本文运用遗传算法对上文提出的数学模型进行求解,过程如下。
3.1 编码设计
根据问题的特征,提出以下染色体编码方法。染色体根据第一道工序机床数目分为k个子段,每个子段上的基因排列代表某台机床上工件排列,不同的机床上的工件排列用标记符“0”隔开。基因aij包括两部分,集合(1,2,…,N)中的一个整数和(0,1)中的随机小数,整数部分代表该工件所对应的模具号,小数部分代表该工件在该组中的初始记号。
例如有2套模具,第一套模具有5个工件第二套模具有4个工件,第一道工件共有3台机床,分别为M11、M21、M31,则染色体[2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4],表示代表的工件在第一道工序各机床的加工顺序如下:
3.2 适度函数设计
根据上文给出的数学模型,可以得到染色体的适应值F(S)=σ·e-εf(S),其中f(S)为目标函数,σ、ε为大于零的常数,为计算方便本文这两个值始终取1。
3.3 种群初始化
本文采用完全随机方法产生初始种群中的所有个体。由于编码非常简单,因此,产生初始种群的算法也容易实现。
3.4 复制操作
复制过程的目的是为了从当前的群体中选出优良的个体,使它们有机会作为父代将其优良的个体信息传递给下一代。在第M代第j个体的选取概率计算公式为:
通过以上式子采用赌轮方式来决定每个个体的复制份数,把复制后的个体送到配对库,以备配对繁殖。
3.5 交叉操作
遗传算法的交叉操作就是模仿自然生态系统的双亲繁殖的机理而获得新个体的主要方法,它通过一定的交叉概率,将两个亲代个体的部分基因进行交换,产生新的基因组合而得到新的个体,这个新个体从两个亲代个体中获得遗传信息,有机会产生比亲代更优秀的个体。本文染色体交叉具体过程如下:
(1)从一个父代染色体中找到字符“0”所在的位置,建立一个空白后代染色体,并将父代染色体中的字符“0”复制到后代染色体相应的位置;
(2)从该父代染色体中随机取出一个子段,并将其填入所建后代染色体中的相应位置;
(3)在另一个父代染色体中,将与步骤2中取出的子段中相同的基因标记为“-1”;
(4)将第二代父代中不为“0”和“-1”的基因通过从左到右扫描,依次填入后代染色体中的空余位置。
假设有2个父代P1和P2,选择P1和P2的最右边的子段扩展成后代C1和C2,交叉运算的执行过程如下所示:
父代P1:2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4;
父代P2:2.3,1.4,2.4,0,2.2,1.5,2.1,0,1.3,1.2,1.1。
中间执行过程如下:
父代P1':2.1,-1,-1,0,-1,1.5,2.3,0,1.4,2.2,2.4;
父代P2':2.3,-1,-1,0,-1,1.5,2.1,0,1.3,1.2,1.1;
结果如下:
3.5 变异操作
利用遗传算法的编码特点,本文以随机方式选取两个位置,然后互换基因位置(SWAP)。随机交换的基因可以是工件号和工件号,也可以是工件号和“0”的不同组合,所以导致了4个基本类型的变异:
(1)如果两个基因都是工件,可能出现两种情况。一种情况是两个工件在同一台机床上加工,这时实质是改变工件的加工顺序,如下所示:
变异前:2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4;
变异后:2.1,1.1,1.3,0,1.2,1.5,2.3,0,1.4,2.2,2.4。
(2)另一种情况是两个工件在不同的机床上加工。这时变异改变染色体的工件顺序和工件对机床的分配,如下所示:
变异前:2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4;
变异后:2.1,1.3,1.4,0,1.2,1.5,2.3,0,1.1,2.2,2.4。
(3)如果两个基因都是“0”,则把原有机床上的加工任务按照原来的加工顺序对调,如下所示:
变异前:2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4;
变异后:1.2,1.5,2.3,0,2.1,1.3,1.1,0,1.4,2.2,2.4。
(4)如果一个基因是“0”,另一个基因是工件,变异同时改变染色体的工件顺序和工件对机床的分配,如下所示:
变异前:2.1,1.3,1.1,0,1.2,1.5,2.3,0,1.4,2.2,2.4;
变异后:2.1,1.3,1.1,0,1.2,1.5,2.3,1.4,0,2.2,2.4。
3.7 停止准则
算法停止准则一般以预先设定的最大繁殖代数Gmax作为停止准则。本文在数值仿真中也采用了这个准则。
4 应用实例
为验证本遗传算法的有效性,本文结合车间的具体加工数据设定了如下实例。
前道工序(CNC)有3台机床,后道工序(EDM)有4台机床,现有4套内模(I1,I2,I3,I4)上的电极需要加工,各套内模及对应电极的相关数据见表1~3。设各内模对应的所有电极原料在当前排程时刻(t=0)均已经准备就绪。
在上述给定条件下,应用本文的遗传算法求解,设置运行环境为种群4个,交叉率为0.5,变异率为0.03,遗传代数为12。
通过仿真,发现最好的染色体出现在第7代~11代,均为:
该方案下,总的EDM停机待料时间为13小时,其中1号和4号EDM机床停机待料时间较多,分别为4小时和5小时;工件总的无效等待时间为12小时,其中1号EDM机床工件无效等待时间为10小时;编号为1的模具产生4小时的拖期量,其余几套模具均没有拖期情况发生。
结果证明,运用本文设计的遗传算法确能有效地求解后阶段带成组特征的两阶段流水车间准时生产调度问题,并能应用到实际生产排程系统中。
5 结束语
后工序带成组特征的两阶段柔性Flow Shop作业调度问题是模具电极CNC和EDM工序加工过程的主要特点,它也普遍存在于各类制造业企业中。本文针对此类生产过程建立数学模型,并利用遗传算法求解,对于该数学模型提出针对性的编码设计方法和遗传操作方法,最后利用一个比较小规模的实际例子证明该算法的有效性。
摘要：模具电极在CNC和EDM工序加工的调度是一个两阶段且后阶段带成组特征的柔性Flow Shop问题,目标是既要尽可能满足交货期,又要实现模具的准时生产。为此,首先建立问题的数学模型,然后用遗传算法求解,并应用实例验证该算法的有效性。
关键词：模具成组,准时生产,柔性流水加工,成组调度,遗传算法
参考文献
[1]Salvador M S.A Solution of a special class of flow shop scheduling problems[A].Proceeding of the Symposium on the Theory of Scheduling and Its Applications[C],Berlin:Springer Verlag,1973:83-91.
[2]Wittrock R J.Scheduling Algorithms for Flexible Flow Line[J].IBM Journal of Research and Development,1985,29(4):401-412.
[3]Wittrock R J.An Adaptable Scheduling Algorithm for Flexible Flow Lines[J].Opers Res,1988,33(4):445-453.
[4]Brah S A,Hunsucker J L.Optimal Scheduling in a Flow Shop with Multiple Processors[A].Paper Presented at the TIMS/ORSA Joint Nation Meeting in New Orleans[C],Louisiana,1987(5):4-6.
[5]Brah S A,Hunsucker J L.Branch and Bound Algorithm for a Flow Shop with Multiple Processors[J].Eur J Opl Res,1991,51(1):88-99.
[6]Gupta J N D.Two2stage Hybrid Flowshop Scheduling Prob-lem[J].J Opl Res Soc,1988,39(4):359-364.
[7]Tsubone H.A Production Scheduling System for a Hybrid Flow Shop-a Case Study[J].OMEGA,Int J of Mgmt Sci,1993,21(2):205-214.
[8]Rasaratnam Logendran,Sara Carson,Erik Hanson.Group-scheduling in flexible flow shops[J].Int J Production E-co2nomics,2005,95(3):143-45.
[9]王莉,王梦光.基于遗传算法的多机多阶段的Flow Shop问题[J].信息与控制,1997,26(4):56-60.
两阶段遗传算法 篇4
分类(又称有监督学习)[1]是在给定一组带标签的训练样本集合(通常以固定长度的特征向量表示)的情况下通过学习获得一个分类模型,并以此模型来预测未知样本的类标签。
1999年Dong等人提出了一种被称作显露模式[2](Emerging Patterns,EPs)的新的知识模式,并受到了数据挖掘界的广泛重视[3,4]。基于EPs的分类算法通过聚合多个EP的分类能力来分类,综合考虑了不同数据集在多组属性上的差异,能够弥补传统分类方法(如决策树方法)只考虑一组属性而形成的缺陷,取得了很好的分类结果。
但对大型数据库,特别是高维数据来说,EPs的数量巨大(可达109),导致在构造分类器时算法有很高的时间和空间复杂度,并且挖掘到的EPs中存在有大量的冗余。2000年Fan和Ramamohanarao提出了eEPs(Essential Emerging Patterns,基本显露模式)的概念,有效地解决了一般形式的EPs在分类时的冗余问题,同时又不会丢失太多对分类有用的信息。
在解决数据挖掘领域中的分类问题时,传统的分类算法多数采用顺序覆盖技术来训练分类规则,这种方法有着自身无法很好解决的问题,即反例碎片问题(problem of splintered false positive)和有错误倾向的小覆盖问题(error-prone small disjunction)[5],在稀有类分类中这种问题更加突出。2000年Ramesh Agarwal和Mahesh V.Joshi提出的基于规则的两阶段方法很好地解决了上述问题,在稀有类分类和图像分类[6]中取得了良好效果。
结合两阶段思想和eEPs在分类方面的优势,提出了一种改进的分类算法EPTPC(the essential Emerging Patterns based Two-Phase Classification)。该算法使用两个阶段挖掘eEP并用于分类,分类时考虑第二阶段对第一阶段的修正作用,特别是优化了评分策略和两个阶段的权重设置。实验结果表明,EPTPC在UCI机器学习库中的11个数据集上可以取得与常见经典优秀分类算法可比的整体分类效果,并在部分数据集上优于其他算法。
文章下面首先讨论相关领域的工作;然后给出EPTPC算法详细描述;最后给出实验结果并与其他相关分类方法进行比较。
2 相关概念描述
2.1 eEP及相关定义
假定项x是属性名和属性值的对偶,若干个不同的项组成的集合被称为项集,它是数据库元组的子集,记为X。给定一个项集X1,和元组T包含的项的集合X2,如果∀x∈X1满足x∈X2,就可以说项集X1覆盖元组T,也可以说元组T包含项集X1。
定义1.支持度(support),给定数据集D和项集X,假设被X覆盖的元组的集合为D′,则称X在D中的支持度为suppD(X)=|D′|/|D|,记为,其中|D′|和|D|分别指数据集D′和D中的元组个数。
定义2.增长率(growth rate),给定项集X,数据集D1和D2,X在D1和D2中的支持度分别记为suppD1(X)和suppD2(X),则X从D2到D1的增长率记为growth-rateD2→D1(X),如下定义:
undefined
定义3.显露模式(Emerging Patterns, EPs)[7],按照定义2,如果growth-rateD2→D1(X)不小于给定的增长率阈值ρ,就可以称X为从D2到D1的ρ—EP,简称为数据集D1的EP。D1称为EP的宿数据集,而D2称为EP的对立数据集。
定义4.基本显露模式(essential Emerging Patterns,eEPs)[8],如果一个项集X满足下面的三个条件:
1)是满足一定增长率阈值的EP;
2)在类C中满足一定的支持度阈值;
3)其任何真子集都不满足上面两个条件;则称X为eEP,即基本的EP。
2.2 两阶段方法简介
两阶段思想也称为PN规则(PN-Rule),是在试图解决传统的基于顺序覆盖的策略在稀有类分类中产生的问题时提出的。因为它既发现能够预测目标类存在的规则(P规则),又发现能够预测非目标类不存在的规则(N规则)。与其它现有的方法一样,该方法的第一个阶段(P阶段)没有严格的准确度限制,如果准确度和支持度产生矛盾,放宽准确度限制优先考虑支持度高的规则。在第二个阶段(N阶段),训练数据集从所有P规则所覆盖的实例集开始,学习规则以去除尽可能多的反例。
研究结果表明[5],两阶段方法能够解决绝大多数顺序覆盖技术所不能很好解决的小覆盖问题和反例碎片问题,并且能够在两个阶段中分别获得高覆盖和高精确度。
3 EPTPC算法描述
3.1 基本思想
本算法基于两阶段思想和分类模式eEPs来构造分类器。在两个阶段中,首先把挖掘到的eEPs按{增长率,支持度}降序排列,优先考虑增长率和支持度都比较高的eEPs,并且当eEPs的增长率不能满足要求时,放宽对其增长率的要求,而按支持度大小来选择。其次,以eEPs的增长率作为单个eEP分类能力的评分标准,即在分类未知实例时,它包含的某个类的eEPs的平均增长率越高,它属于那个类的可能性就越大。最后,在用N阶段eEPs来修正P阶段的判断结果时,加上了一个修正强度因子,以便更合理地发挥N阶段的辅助作用。
3.2 基本概念
定义5. 给定类C和一个eEP e,如果e是C的一个eEP,就称e跟C是关联的(relative)。而二者的关联度(relativity)是e的增长率的一个衡量尺度,记作Rel(e,C),简记为Rel(e),定义如下:
undefined
定义6. 给定实例s和类C,在第一阶段挖掘得到的C的eEPs(即C的P-eEPs)对s归属于C的支持程度,称为s对C的趋向度(tendency),记作TenC(s),简记为Ten(s),定义如下:
undefined
其中PE(s)表示s覆盖的与C关联的eEPs的集合
定义7. 给定实例s和目标类C,非目标类C′在第二阶段挖掘得到的C′的eEPs(即C的N-eEPs)对s不归属于C的支持程度,称为s对C的背离度(deviation),记作DevC(s),简记为Dev(s),定义如下:
undefined
其中NE(s)表示s覆盖的与C′关联的eEPs的集合
定义8. 给定类C,第一阶段中C的P-eEPs覆盖的训练实例个数与第一阶段中的训练实例总数的比值,被称为修正强度因子(strength factor),记作SF(C)。
定义9. 给定未知实例s,它属于类C的可能性被称为s对C的隶属度(belongingness),记作BelC(s),简记为Bel(s),定义如下:
Bel(s)=Tec(s)-Dev(s)*SF(C) (4)
3.3 eEP的挖掘
基于边界的算法[7]能够有效地表示和挖掘所有的EPs,但是缺点是:
(1)需要大量的边界来表示所有的EP;
(2)边界表示法中并不包含EP的支持度和增长率,需要在后续处理中提取,对于稠密数据集或大数据集来说,这个过程非常耗时。
本算法采用的挖掘eEP的方法不使用边界表示法,其思想借鉴了FP-growth[8],但在构造和遍历树方面都不完全与FP-growth相同,甚至优于FP-growth。通过引入后缀子树(用几个很小的数组表示),使算法在挖掘模式时并不生成条件子树,克服了FP-growth在挖掘模式时需要递归地生成大量的条件子树的缺点,从而大大提高了模式挖掘的时空效率。
3.4 EPTPC算法综合描述
EPTPC算法描述如下:
4 实验及结果分析
算法采用10-折交叉验证的性能评估方法,在UCI机器学习库的11个数据集上进行测试,并与一些经典分类算法(Naundefinedve Byaes(NB),CBA,C5.0,CMAR以及两个基于EP的分类算法CAEP[2]和BCEP[8])的分类结果进行比较(见表1)。
从表1看出,在11个数据集上,EPTPC都比基于EP的经典分类算法CAEP要强一些,特别是在Vechile和Lymph两个数据集上;与BCEP相比,分类准确率也不相上下。整体来看,EPTPC在Austrilian,Cleve,Heart,Vechile上优于其他算法,在Mushroom数据集上也基本上接近100%,在其他的数据集上EPTPC的分类准确率也与最好结果接近。
5 总结
在对两阶段分类思想和基于EP的分类算法作了深入研究的基础上,提出了一种新的分类算法,与传统的分类方法不同的是,不仅采用两阶段思想构建分类算法框架,更加注重在稠密数据库和高维数据库中的模式灾难问题,采用eEP作为分类模式。采用10折交叉验证方法训练分类器,最大程度地减少了分类误差。EPTPC在11个UCI机器学习数据集上取得了与其他优秀算法相媲美的分类效果。
参考文献
[1]JIAWEI HAN,MICHELINE KAMBER.范明,孟小峰等译.数据挖掘:概念与技术(第2版)[M].北京:机械工业出版社,2007.
[2]GUOZHU DONG,XIUZHEN ZHANG,LIM-SOON WONG,JINYAN LI.CAEP:Classifica-tion by Aggregating Emerging Patterns[J].Dis-covery Science 1999:30-42.
[3]GUOZHU DONG,JINYAN LI.Emerging Pat-tern Based Classification[M].//Encyclopediaof Database Systems,Edited by LING LIU andTAMER M.OZSU.2009.
[4]GUOZHU DONG,JINYAN LI.Applications ofEmerging Patterns for Microarray Gene Expres-sion Data Analysis[M].//Encyclopedia of Da-tabase Systems,Edited by LING LIU and TAM-ER M.OZSU.2009.
[5]RAMESH AGARWAL,MAHESH V.JOSHI.IBM Research Report.PNrule:A new Frame-work for Learning Classifier Models in Data Min-ing(A Case-Study in Network Intrusion De-tection)[C].In Proceedings of First SIAMConference on Data Mining,Chicago,April2001.Expanded version available as IBM Re-search Division Report,RC 21719,April 2000.
[6]CHUAN-YU CHANG,RU-HAO JIANHUNG-JEN WANG.Two-phase Fuzzy-ART with Independent Component Analysis forSemantic Image Classification[J],2009.
[7]GUOZHU DONG,JINYAN LI.Efficient Miningof Emerging Patterns:Discovering Trends andDifferences[J].KDD 1999:43-52.
两阶段遗传算法 篇5
在分布式网络环境中,保证QoS约束的服务组合优化问题是NP难题,需要有效的解决方法,当前多采用启发式优化算法,如人工神经网络算法,蚁群算法,遗传算法等。现有启发式优化算法解决这类服务组合优化问题有快速收敛,全局优化的优点,同时也存在非常鲜明的缺点。如蚁群算法,算法初期缺乏对搜索空间的知识,信息素积累的过程比较漫长,求解速度较慢。遗传算法存在早熟现象的问题,对新的空间的搜索能力有限,容易收敛到局部最优解。
赵义武等提出了一种实现遗传算法和蚁群算法融合的策略[4],遗传算法在搜索初期向最优解收敛较快,在一个时间点之后收敛速度明显降低,而蚁群算法在搜索初期由于信息素匮乏,搜索速度比较慢,当信息素有一定程度的堆积之后,向最优解收敛的速度迅速增加。因此,本文的解决方案是设计一种轻量级、协同计算的启发式算法,结合遗传算法和蚁群算法的优点,降低算法时间复杂度,加快收敛速度。
1 总体描述
现阶段,对于具有复杂业务逻辑的Web服务组合问题没有系统的解决方法,多采用启发式算法寻优以解决这类问题,期望得到Pareto最优解。启发式算法具有高效的优化性能和准确的信息决策能力,对问题信息依赖低等优势。
本文中的工作都是基于下面的2个假设展开的。
1)业务流程中的每个任务都对应一组同质Web服务可用。
2)这些同质Web服务拥有不同的QoS约束参数值。
保证QoS约束的服务组合问题转化为业务流程中的每个任务选择一个实体Web服务,从而使得整个聚合服务的聚合QoS参数值相对于已知的全局约束是安全的。
1.1 系统参数和记号
本文使用的系统参数和符号如表1所示,表中的一些概念已经被广泛支持和认可[1],将在上下文中直接使用。
表1系统参数和符号表(参见下页)
1.2 系统模型
如图1所示为系统的多阶段图,任务集合[t1,t2,…,tn]组成一条业务流程,业务流程定义了任务的执行顺序和工作效果。业务工作流程映射为聚合Web服务路径,每个任务从其对应的候选服务集合中选择某一个实体Web服务,如果所有任务在一定的外部条件下按照指定的顺序都执行完成,则业务流程结束。图中每个节点代表一个实体Web服务,每条边连接两个相互邻接的节点,边上的权重表示这两个节点之间的QoS参数向量,本文中假设任意两个邻接任务对应的候选服务集合中的实体服务都是网络可达的。
一个Web服务组合序列包含n个任务,如果有1≤a≤b≤n,则任务ta在任务tb执行之前执行。Ca为对应于任务ta的、提供相同功能的、不同的候选Web服务集合。引入一个二元值xij,当Ci中的Web服务CSij在整个执行计划中被执行,则xij=1,否则xij=0。必须保证为了完成每个任务有且只有一个Web服务被选中,。
1.3 两阶段启发式算法概览
本文设计的启发式算法是一个两阶段算法,采用遗传算法和蚁群算法结合的方案,首先利用遗传算法对待求解问题解空间的快速学习的特点,设计遗传算子和制定算法敏感参数,控制算法的收敛速度,得到待求解问题的一组可行解,并将其转化为蚁群系统的初始信息素分布;然后利用蚁群系统的分布式计算、自组织和正反馈等系统学特性优化服务组合问题,期望获得一组全局最优解。这两个算法实现优势互补,两阶段启发式服务组合算法如图2所示。
2 两阶段启发式算法
2.1 QoS模型
在保证QoS约束的Web服务组合中,QoS参数是评估和匹配Web服务的主要依据。QoS属性按照生长增益的不同,可以分为正向QoS属性和负向QoS属性两类。正向QoS属性是指一类属性对评估服务的质量是正有益的,如可扩展性和声誉等。负向QoS属性是指一类属性对评估服务的质量是负有益的,如响应时间、开销等。本节介绍QoS参数的预处理方法,主要考虑到2点原因:首先,不同类型的QoS参数对应全局约束目标函数的形式存在差异,具有不同的聚合公式,不便于统一计算和评估;其次,多种QoS属性所评估的领域不同,所以每种QoS属性可能会映射到不同的值域,甚至可能会在不同的数量级。如果直接使用这些QoS属性计算的话会影响后文中服务选择方法的公平性和有效性。根据上面的分析,为了保证QoS属性聚合模型的兼容性和服务选择算法的有效性,下文提出了QoS参数的预处理方法,实现不同QoS参数的统一标准化。
对于数值数量级存在差异的不同的QoS参数,首先将其值域缩放到[0,1]范围内,然后映射到统一的值域[C1,C2]范围中,其中C1,C2为非负实数,并且满足C2>C1≥0。由于所有的QoS参数都转化为线性加和型的负向Qo S模型,下面设计其函数形式:
2.2 遗传算法阶段
2.2.1 染色体编码
结合服务组合问题的特点,采用一维整数编码方式[2]。本文假设每个业务流程的执行路径都用相同的固定长度n,则每个染色体由一个定长一维整型数组表示,数组的长度表示业务流程的执行路径包含的任务数。数组中的每个元素代表一个基因,染色体中的基因顺序和业务流程执行路径中涉及的任务的执行顺序相同。一维数组中的每个元素的数值对应实体Web服务所在Web服务候选集合的当前位置。如图3所示,对于染色体X,位串向量为X=(x1,x2,…,xn),其中基因x1指向候选服务集合C1中的实体Web服务cs12,使用整数编码方式,则x1=2,同理,x2=4,xn=k,X=(2,4,…,k),有1≤k≤ln。
2.2.2 初始化种群
种群初始化是遗传算法中非常重要的一部分,初始化种群的组成直接影响到算法收敛速度,所以第一代种群要尽量体现搜索解空间的随机性和遍历性。本文采用随机化方法产生一组满足全局约束条件的执行计划,然后编码成染色体位串向量Xi=(xi1,xi2,…,xin),i=1,2,…,N的形式,组成初始化种群S,其中N为初始种群的规模,存在N=|S|。C表示候选服务集合的集合,C中的元素Ci为候选服务集合,有Ci∈C,i=1,2,…,n。种群初始化算法如图4所示。
图4种群初始化算法(参见右栏)
2.2.3 适应度函数
本文中初始种群规模设计不会很大,为了避免早熟现象,拟采用保证种群的多样性的方法。基于Shannon的信息熵理论为个体差异性评估提供支持[5],下面介绍个体Xi的适应度函数Fit(Xi)的计算方法。适应度值算法如图5所示。
适应度值算法首先计算种群S中所有染色体间的相似度,对于种群S中的个体Xi的适应度函数为Fit(Xi),种群S中个体Xi和个体Xj的相似度Aij通过P的信息熵的倒数计算,其中P为个体Xi和个体Xj中基因重叠的概率,比如,定长染色体的长度为n,个体Xi和个体Xj中重叠的基因个数为l,则P=l/n。求取个体Xi的适应度函数值FXi,当前代t有FXi=Fit(Xi),最后将种群所有染色体的适应度值按从大到小排序。从整个计算过程,我们利用适应度值反映染色体的多样性和QoS约束参数的优化策略。适应度计算方法中使用信息熵,提高了计算的灵敏度,其中ε是一个小于1的正实数。fi,i=1,2,…,N为个体Xi的影响因子xi,j=1,2,…,n为Xi位串向量的第j维数值。fi的计算形式如下:
2.2.4 遗传算子
选择:采用基本的适应度值比例方法进行选择操作。适应度值比例选择操作通过个体适应度值和当前代种群中所有个体的适应度值加和的值的比值计算选择概率。个体Xi选择概率定义为:
交叉:本文采用单点交叉方式,交叉概率采用自适应的调整规则,试图使适应度值大的优良个体保留下来,并且加速适应度值小的个体的进化速度,我们将使用刘健提出的自适应交叉概率表示方法[6],Pc的自适应交叉概率为:
其中,Fitmax表示种群个体的最大适应度值,Fitavg表示种群个体的平均适应度值,Fit(Xi)表示适应度较小的个体Xi的适应度值,P*c表示调整后的交叉概率。
变异:本文具体的思路是,从交配池中随机选择染色体,随机选择染色体位串上的一个等位基因按照变异概率进行替换,即对于某个实体Web服务,从同质候选Web服务集合中随机选择一个不同的实体Web服务的位置来替换当前服务的位置表示的基因。变异概率的选取也与交叉概率同样的方法,采用自适应调整规则来进行变异操作,Pm的自适应交叉概率为:
其中,P*m表示自适应调整后的变异概率。在算法后期,种群中的个体的差异性变小,大多数个体的适应度值趋近于平均值时,调整后的变异概率将会变大,加速产生新的个体,保证了种群的多样性,避免出现早熟现象。
2.3 蚁群算法阶段
给定系统的多阶段图,如图1所示,Web服务组合问题可以被描述为从每个候选服务集合中选择候选服务,从而得到具有全局最优评估计算值的聚合服务。换句话说,我们也可以通过将系统的多阶段图转化为蚁群系统来处理动态Web服务选择问题,蚁群系统通过人工蚂蚁对问题解空间的逐步学习,实现信息素的不断堆积,尽量逼近甚至获取全局最优解。图中每个节点都有到邻接候选服务集合中所有节点的有向边,人工蚂蚁从当前节点出发可以转移到可行邻域中任何一个节点。每个人工蚂蚁根据状态转移概率从业务流程中的下一个任务对应的候选服务集合中选择Web服务。从实体服务csi1j1指向实体服务csi2j2的有向边上的数值表示信息素的值,用τi1j1,i2j2表示,直观地,这个值反映了从当前实体服务csi1j1转移到后继实体服务csi2j2的期望[3],Web服务组合优化算法是一个改进的蚁群算法,如图6所示。
算法初始时刻,按照遗传算法阶段获得的一组可行解设计初始信息素分布。Sw表示人工蚂蚁w的记忆状态,有0≤|Sw|≤n。Ps(csi2j2)表示人工蚂蚁w由当前实体服务csi1j1出发选择后继实体服务csi2j2的状态转移概率。τbest存储当前算法执行时刻所有信息素路径的最优值,对应地,τbest对应的执行计划即当前算法执行时刻的最优解。
上述算法中的状态转移概率和信息素更新规则参照作者2011年提出的一种改进的ACO算法[4]。本文的算法通过优化信息素路径来得到一组Pareto最优服务组合路径。
3 实验分析
3.1 实验参数
本文提出的算法是一个两阶段算法,下面分别介绍两个阶段关键参数的设置。
基于遗传算法的信息素初始分布算法的主要参数有种群规模N,交叉概率P*c,变异概率P*m,其中P*c和P*m表示自适应调整后概率,调整方法参照2.2.4节。种群规模N=40;为了方便计算,候选服务集合的集合C中的元素候选服务集合Ci的规模都相同,其中li=5,i=1,2,…,n;染色体为定长的一维数组,其中染色体Xi的长度n=4。
基于改进的蚁群算法的服务组合优化算法,通过改变信息启发式因子a,期望启发因子和信息素挥发系数这三个参数来影响人工蚂蚁的行为,我们通过降低a和的数值来降低信息素对人工蚂蚁运动的影响,其中a=1,=0.02,通过增加的值来增加人工蚂蚁的探索能力,其中β=5。
3.2 实验结果与分析
3.2.1 遗传算法阶段
业务流程包含4个抽象服务,假设每个抽象服务候选集合有相同的规模,分别拥有5个实体Web服务。本文考虑2个QoS参数,包括开销和响应时间,定义全局QoS约束向量为:R=(400,90)。首先进行QoS参数的预处理。候选服务集合中实体服务QoS参数列表如表2所示,其中开销的单位是人民币元,响应时间的单位是ms,由于开销和响应时间都属于线性加和型的负向QoS模型,需要映射到相同的值域范围。根据式(1)预处理操作后的实体服务QoS参数列表如表3所示,设置实数C1=0,C2=100,则统一值域为[0,100]。
根据遗传算法阶段计算得到一组可行解,包括(cs14,cs22,cs32,cs43)和(cs11,cs22,cs32,cs43),如表4所示,表中同时列出了QoS聚合成本。我们根据这组可行解设置蚁群系统的初始信息素分布。所有节点的信息素初始值设置为1.00,两个可行解重合部分包括实体服务cs22,cs32和cs43,表明这些节点的基因更优,这些服务节点的信息素值要设置略高一些,设置为1.20,cs11为较优解的起点,设置cs11所在的服务节点信息素值为1.15,设置次优解起始服务cs14所在的服务节点信息素值为1.10。通过计算得到信息素初始分布如图7所示。
3.2.2 蚁群算法阶段
根据基于改进的蚁群算法的服务组合优化算法得到了一个较优解,如表5所示,可行解为(cs12,cs22,cs32,cs44)。根据QoS聚合成本的比较,可行解(cs12,cs22,cs32,cs44)是保证QoS约束的服务组合问题的Pareto最优解。
实验部分通过制定算法的两个阶段的关键参数控制算法的灵敏度和准确度,对算法的两个阶段分别设计实验。首先进行QoS参数的预处理操作,所有QoS参数转化成统一的线性加和型的负向QoS模型,具有统一的值域。然后使用改进的遗传算法为后面的蚁群系统提供信息化的初始分布,避免人工蚂蚁的随机搜索,加快收敛速度。最后通过改进的蚁群算法获得更好的、满足全局QoS约束的解。通过对结果进行分析,算法的第二个阶段可以得到待求解问题的可行解,这验证了优化算法的可行性。我们可以看到实验结果的可行解是Pareto最优的,这验证了优化算法的有效性。
4 结语
本文建立了一种有效的QoS模型,实现服务组合优化问题的多目标优化,使算法自然收敛,避免了传统的对QoS参数的加权归一化操作带来的人为因素的依赖。并且提出一种保证QoS约束的服务组合的启发式优化算法,利用启发式算法的随机性,全局搜索和快速收敛的特点,利用两个阶段性的处理,融合遗传算法和蚁群算法的优点,具有良好的优化效果。最后通过仿真实验验证了算法的可行性和有效性。
摘要：保证QoS约束的Web服务组合优化问题是一个多目标多选择的问题,是NP难的,很多工作都是关于如何设计一种有效的优化算法展开的。本文提出了一种两阶段的启发式算法,利用遗传算法和蚁群算法相互融合的策略,实现这两个算法的优势互补,通过优化多个目标函数,获得一组满足约束条件的Pareto最优解。仿真实验说明的算法的可行性和有效性。
关键词：Web服务,QoS,服务组合,启发式算法,遗传算法,蚁群算法
参考文献
[1]Yu T,ZhangY,Kwei J.Efficient algorithms for Webservices selection with end-to-end QoS constraints[J].ACM Transactions on the Web,2007,1(1):1-26.
[2]Canfora G,Penta M D,Esposito R,et al.An approachfor QoS-aware service composition based on GeneticAlgorithms[C]//Genetic and EvolutionaryComputation Conference,2005:1069-1075.
[3]Zhang W,Chang Carl K.,Feng T,et al.QoS-baseddynamic Web service composition with ant colonyptimization[C]//IEEE 34th Annual ComputerSoftware and Applications Conference,2010:493-502.
[4]Zhao S S,Wang L,Ma L,et al.An improved antcolony optimization algorithm for QoS-awaredynamic Web service composition[J].AmericanJournal of Engineering and Technology Research,2011,11(9):1632-1637.
[5]赵义武,牛庆银,王宪成.遗传算法与蚁群算法的融合研究[J].科学技术与工程,2010,10(6):4017-4020.
[6]刘书雷,刘云翔,张凡,等.一种服务聚合中QoS全局最优服务动态选择算法[J].软件学报,2007,18(3):646-656.
两阶段遗传算法 篇6
根据不同的分析主体和目的, 有多种财务分析方法可供采用, 例如从内容的综合程度上, 有杜邦分析方法、沃尔分析方法等。但是杜邦分析的缺陷是能够参与分析的指标较少, 损失较多, 综合性分析不够;沃尔分析的不足是不能进行企业之间财务状况的横向、综合比较。本文从投资者投资决策的角度, 提出基于两阶段聚类算法的上市公司综合财务分析方法。
一、二阶段聚类算法
聚类分析是研究事物分类的基本方法, 它从事物数量上的特征对事物进行分类。其优点是使用简便, 分类效果好。聚类分析的算法很多, 主要有二阶段聚类、中心聚类、层次聚类等。其中二阶段聚类的优点是其算法适合任何尺度的变量。该算法主要分为以下两个步骤:
第一, 确定聚类数。具体有有两种方法:一是根据数据特点, 按照一定的信息准则 (BIC或AIC) 进行迭代运算, 自动聚类 (BIC或AIC数值最小时对应的分类数最优) , 但需要指定最大分类数。二是研究者自己根据需要和经验指定所想要的分类数。
第二, 进行聚类结果描述。描述范围包括每一聚类的平均值、标准差等统计特征、参与聚类的变量对聚类结果的贡献程度、聚类变量数字特征的置信区间等。
二、实例分析
本文对张瑞龙 (2008) 在进行类似研究中提出的汽车配件板块7家上市公司2005年财务数据进行分析, 分别为:沪东重机、航天晨光、长春一东、耀玻璃、ST方向、轮胎橡胶、航天科技。同时选择流动比率、股东权益比、存货周转率、应收账款周转率、资产净利率、净资产收益率、净利率增长率等7个财务变量指标进行研究。
根据人们对于不同事物在相同属性差别的分辨判断能力和习惯, 一般采用3标度、5标度、9标度法进行度量。由于本文讨论的公司数量只有7个, 因此采用3标度法进行分类, 即将选取的7家公司计划分为3类。各变量指标距离间的度量采用欧氏距离进行度量, 利用SPSS3.0软件进行分析。表2是3类公司中每类包含的公司数量。可以看出, 分为第一类的公司数量最多, 占公司总数的42.9%。
各财务指标对于公司分类的影响程度是不一样的, 可以用统计学方法中的检验进行表示, 图1是第1类公司的财务指标对分类结果的影响程度。可以看出, 上市公司财务指标中净资产收益率对分类结果的影响在置信水平为95%的检验中是显著的, 其余财务指标在统计学意义上没有显著影响。第6个指标净资产收益率平均值95%的置信区间如图2所示。
通过对选取的汽车配件板块7家上市公司2005年的财务指标采用二阶段聚类算法进行分析, 发现在7家公司分为3类的情况下, 选用的7个财务指标中, 第6个指标净资产收益率对分类结果的影响是显著的, 其余财务指标在统计学意义上没有显著影响, 该结论可以为投资者提供决策帮助和参考。
参考文献
[1]马建锋:《企业财务分析方法评价》, 《焦作工学院学报 (社会科学) 》2003年第4期。
[2]李华金:《试论我国上市公司的财务分析方法》, 《甘肃农业》2004年第9期。
[3]宇传华:《SPSS与统计分析》, 电子工业出版社2007年版。
两阶段遗传算法 篇7
随着我国经济的高速发展和电力系统的不断扩大, 人们对供电的安全性、可靠性等方面的要求也日益增长, 势必需要大量的输变电工程投入到电网建设中。为应对建设需求, 每年都会有大量的输变电工程上报。在这些工程中, 一部分是电网建设需要的, 但另有一部分也是没有必要的, 或者上报的方案不是最优的, 需要被替换成更好的实施方案。如何在大量的工程中选择需要的并且以一种最好的方案进行实施, 对于电网建设决策者而言至关重要。
输变电工程立项决策模型的基本任务是根据对电网的全面评价, 确定上报申请的待选项目是否有必要立项。如果确定立项, 则合理地决策用哪一种方案进行针对性地改造和建设, 从而使规划方案能满足电网安全可靠运行的要求, 适应电力发展的需求, 同时使能源资源得到合理的优化配置。
输变电工程立项决策问题是一个非线性、多阶段、多目标的复杂优化问题。它有3个方面的关键技术难点:需要一套科学、客观、合理以及全面的评价指标体系去建立该数学模型;输变电工程立项决策模型往往建立成一个多目标优化模型, 需要寻找一种高效的多目标优化算法进行求解;在利用多目标优化算法求得Pareto最优解后, 应用一种有效的综合评价方法比选备选决策也是一个重要的环节。
对于在输变电工程立项决策问题中的难点, 目前大部分文献集中在对于可选的电网规划方案, 用一些评价指标对各个方案进行评价后得到一个最终方案[1,2,3], 但采用多指标全方位地对电网进行综合评价并将其转化为多目标优化模型的文献并不多见。
对于多目标优化问题, 多目标遗传算法[4,5]最先被提出, 且很多学者专家对其进行了大量的改进[6,7]。鉴于粒子群优化算法参数简单, 并且无需复杂调整的特点, 在多目标遗传算法的基础上, 文献[8]首先提出了多目标粒子群优化 (MOPSO) 算法。为了更好地保持多样性, 文献[9]提出了基于小生境的多目标粒子群优化算法, 文献[10]提出了基于自适应划分的多目标粒子群优化算法, 进一步优化了多目标粒子群优化算法。但输变电工程立项决策问题指标众多, 普通的多目标优化算法很难求解这样一个高维的问题。
在评价方法方面, 已有文献提出了利用多目标模糊评价方法[1]、基于区间层次分析法[2]、基于熵权灰色法[3]和独立信息数据波动赋权 (DIDF) 法[11]等优度评价法, 对电网规划方案进行评价。但这些文献在指标选取上没有一个统一的标准, 而且其中有些指标意义不大或者在实际电网中难以获得原始数据。
因此, 本文基于一个较为完整的输变电工程立项决策方案评价指标体系, 包括电网的安全性、经济性、环境友好性、适应性和协调性5个方面, 形成一个输变电工程立项决策的多目标优化问题, 并针对部分指标需要优先满足的要求, 提出自动寻优的两阶段双层粒子群优化算法, 有效地求解各个方案的评价指标, 形成Pareto最优解, 最后用综合评价方法进行比选决策, 选取最优方案。
1 输变电工程立项决策数学模型
多目标优化问题的数学模型一般可以表示为式 (1) 的形式。
其中, n为决策变量的个数;m为目标变量个数;n维的决策变量x= (x1, x2, …, xn) , m维的目标函数矢量y= (y1, y2, …, ym) ;hi (x) 为等式约束;gj (x) 为不等式约束。
定义1:假设多目标优化问题的2个解向量U、V∈RD, 若满足
则称U相比V是Pareto占优, 也称U支配V。
定义2:假设x*∈RD, 当且仅当RD中不存在支配x*的x时, 则称x*为多目标优化问题的Pareto最优解。
本文将输变电工程立项决策问题构建成一个两阶段多目标的数学优化模型, 2个阶段分别为立项阶段和决策阶段。
在立项阶段, 决策者主要考虑目前该部分电网是否存在某个缺陷, 比如供电能力不足、容载比过低或存在安全隐患等。根据现有电网的输变电工程立项评价指标体系 (见图1) , 判断是否需要立项。若满足安全性I类指标要求, 则不需要立项;反之, 则需要立项。因此, 立项阶段主要考虑安全性I类指标, 包含容载比、主变及线路的最大负载率等。
在决策阶段, 对于系统某个缺陷, 存在很多实施方案, 同时上报的方案并不一定是最好的, 所以决策者需要在众多方案中选取一种最优的方案, 或者通过一定的方法去寻找出一种最优的方案。另一方面, 既然是因为安全性缺陷而立项, 那么所选的方案必须以满足安全性Ⅰ类指标为前提, 继而再去寻找安全性Ⅱ类、经济性[12,13]、环境友好性、协调性[14]、适应性[14]等其他指标的最优性。因此, 决策阶段综合考虑安全性Ⅰ类、安全性Ⅱ类、经济性、环境友好性、适应性和协调性6个大类指标, 构建一个较为完整的输变电工程方案决策评价指标体系, 如图2所示。
2 双层多目标粒子群优化算法
2.1 标准粒子群优化算法
标准粒子群优化算法用一群粒子表示优化问题的潜在解。在m维的搜索空间中, 粒子i在t时刻的位置为xi (t) , 速度为vi (t) , 该粒子的历史最好位置记为Pbesti, 而全部粒子经历过的最好位置记为Gbest。粒子群优化算法中粒子通过不断更新自身的位置和速度向最优解飞行, 第i个粒子的速度和位置更新公式为:
其中, r1、r2为均匀分布在[0, 1]区间的随机数;c1、c2为群体认知系数, 一般c1=c2=2;惯性权重ω=0.9-0.5i/Titer+1, Titer为迭代的总次数。
2.2 自动寻优的双层多目标粒子群优化算法
输变电工程立项决策模型包含非常多的目标函数, 并且体现安全性Ⅰ类指标的目标函数需要满足一定的安全限定, 同时又要尽可能被优化。由于安全性I类指标众多, 如果用罚函数处理这些指标并加入到约束中, 会导致搜索方向混乱, 优化时很难找到Pareto最优解。因此, 本文提出用双层多目标粒子群优化算法来求解这样的问题, 即在目标函数中, 有部分目标函数需要优先被满足。
本文用安全性Ⅰ类的多个指标构成下层的多目标优化模型, 将安全性Ⅱ类、经济性、环境友好性、适应性和协调性作为目标函数, 构成上层的多目标优化模型, 从而形成一个双层多目标优化模型。其中下层模型为必要条件, 上层模型则在下层模型的基础上进行优化。
2.2.1 自动寻优编码
在使用粒子群优化算法时, 首先要根据数学模型的特点编制相应的解编码, 使解从空间上映射到需要的数学表达方式, 合理的编码方式有利于提高算法的整体效率。
对于输变电工程立项决策方案自动寻优算法而言, 其解编码需要体现其具体的方案。对网架拓扑而言, 节点集合和线路集合会发生变化。对于自动寻优机制, 需要先输入可选的节点信息和线路信息, 这些信息都可以用一个整数值表示, 即对于可选的信息是选还是不选, 如果选的话是选几个。
a.可选的节点信息。因为对于一个具体的项目, 若要新建或者扩建变电站, 其容量等信息都是已知的, 只要决策是新建还是扩建。所以编码的第一位按0、1、2编码, 其中0为不建, 1为新建, 2为扩建, 分别对应相应的可选节点信息。
b.可选的线路信息。在可选的线路中, 一般考虑每个通道最多建4回线, 所以编码为0、1、2、3、4, 其中0表示不建, 1、2、3、4即为该通道新建的回路数, 如果需要建更多回路数, 可以根据具体情况设定相应的限值。编码的位数由可选的线路通道数决定。
假设某个项目有5个可选线路通道, 并且需要新建或者扩建1个变电站, 则其粒子的维数为6。如图3所示, 粒子的第1位表示新建变电站, 第2—6位表示相应的线路通道新建线路的回数。
2.2.2 上下层协调策略
上下层协调策略如图4所示, 本文在上下层协调策略中设置了安全方案集和不安全方案集, 先在下层多目标模型中计算安全性I类指标, 若不满足指标要求则将方案提交至不安全方案集, 并留下记录;反之则将方案提交至安全方案集, 并通过综合评价方法计算其安全裕度, 将具体方案和对应的安全裕度提交至上层多目标模型;然后进行上层多目标模型的优化, 即安全性Ⅱ类、经济性、适应性、环境友好性和协调性等其他特性指标的优化, 进一步求解Pareto最优解。
同时, 在粒子更新过程中, 将更新后的粒子与不安全方案集中的粒子以及安全方案集中的粒子进行比较:
a.若新粒子在不安全方案集中, 则粒子选择再次更新, 直至不在不安全方案集中;
b.若新粒子在安全方案集中, 则保留在上层多目标模型中, 等待下一次的迭代更新;
c.若新粒子既不在不安全方案集中, 也不在安全方案集中, 则将其移到下层多目标模型中, 继续校验其安全性Ⅰ类指标以及相应的安全裕度。
3 立项决策两阶段算法流程
基于输变电工程立项决策模型和双层多目标粒子群优化算法, 形成一个两阶段双层多目标粒子群优化算法。整体上分为立项和决策2个阶段, 在决策阶段又分为上下2层。在形成Pareto最优解后, 通过综合评价方法对各个方案进行评价确定最优方案。
3.1 综合评价方法
本文的综合评价方法由组合赋权法[15]先进行赋权, 再由灰色关联分析法[3]确定各个方案与理想方案的关联度, 决策者根据关联度的大小判断方案的优劣。其中组合赋权法将主观和客观赋权法结合起来, 既符合实际问题需要, 又能兼顾数据客观波动的影响, 其结构如图5所示。本文采用基于矩估计理论的组合赋权法。
3.2 算法步骤
利用两阶段双层多目标粒子群优化算法求解输变电立项决策模型的计算步骤如下。
阶段一:立项阶段。读入原始数据, 包括电力系统数据和算法初始参数;对整个系统进行潮流计算, 判断是否满足安全性I类指标要求, 若满足则无需立项;反之则进入决策阶段。
阶段二:决策阶段。
步骤1:读入方案初始数据, 进入上层多目标模型;设置迭代种群规模, 迭代次数t=0, 在控制变量变化范围内, 随机初始化粒子群 (初始种群规模大于迭代规模) , 每个粒子的个体极值和全局极值均为初始位置, 同时设置精英集为空。
步骤2:根据每个粒子对应的方案, 对整个系统进行潮流计算, 计算安全性I类指标对应的各个目标的适应值;将所求各个方案的安全性I类指标与安全极限进行比较, 将满足安全性I类指标要求的方案放入安全方案集, 不满足要求的方案则放入不安全方案集。
步骤3:用综合评价方法评价安全方案的安全裕度, 在初次迭代时, 以安全裕度的高低选取迭代种群规模数量的安全方案, 提交到上层多目标模型;在后续迭代中, 若更新粒子均满足要求, 则直接提交至上层多目标模型;若更新粒子不满足要求, 则不进行更新。
步骤4:进入上层多目标模型, 对下层多目标模型优化提交的安全方案, 计算出电网系统的安全性Ⅱ类、经济性、环境友好性、适应性和协调性等这些目标函数值。
步骤5:判断是否满足结束准则。达到最大允许迭代次数或最优解对应的目标函数值在给定的迭代步数内改变量小于给定值时, 停止优化并输出结果, 形成Pareto最优解, 转至步骤9;否则迭代次数t=t+1, 进入步骤6。
步骤6:根据Pareto支配概念, 比较各个粒子之间的优劣, 构造粒子群的非支配解集;通过比较非支配解集和精英集中解的Pareto支配关系, 更新精英集;若精英集数量还未达到上限, 则跳至步骤7, 反之则根据网格策略对精英集进行缩减。
步骤7:更新粒子的个体极值和全局极值, 全局极值采用随机从精英集中选择1个极值的策略, 然后按式 (3) 更新粒子的速度, 按式 (4) 更新粒子的位置, 构造新粒子。
其中, sigmoid函数;rand () 为随机函数。
步骤8:判断新粒子是否在安全方案集中, 若在则保留在上层多目标模型中, 转到步骤7, 等待下一次的更新;反之再判断新粒子是否在不安全方案集中, 若在则转到步骤7再次更新粒子的速度和位置;若新粒子既不在安全方案集中, 也不在不安全方案集中, 则转到步骤2, 进入下层多目标模型, 校验新粒子的安全性I类指标。
步骤9:根据自动寻优的双层多目标粒子群优化算法得到的Pareto最优解, 确定评价等级的范围, 根据3.1节建立优化模型, 将各种赋权法确定的指标权重进行优化组合求取最终的组合权重向量, 利用灰色关联分析法结合由矩估计得到的综合权重形成最终的评价结果。
4 算例分析
4.1 算例介绍
以某供区电网为例进行仿真计算, 验证本文算法的有效性。该原系统包含20个节点、3台发电机, 其拓扑结构见图6。图中, 节点A—F为500 kV电压等级的节点, 节点1—15为220 kV电压等级的节点, 方形节点为变压器节点。该供区原先有一个500 kV变电站 (节点A) 、3台1000 MV·A的主变。目前有一个项目上报, 需要对其进行立项决策。该项目考虑选择扩建节点A的变电站 (附带在节点B新建220 kV开关站, 且附带新建节点B至节点4—8的220 kV线路) 或者在节点B新建变电站, 两者新增变电容量均为2000 MV·A, 其余可选新建线路信息见表1。
4.2 立项决策过程
4.2.1 立项阶段
目前该供区需500 kV变电站网供负荷约为2 400 MW, 根据电力规划导则, 500 kV变电站容载比需在1.5~1.9之间, 经计算该供区500 kV变电站容载比为1.25, 不满足安全性I类的指标, 需要立项。为了提高供电可靠性, 必须提高变电容量。
4.2.2 决策阶段
本文以第1次迭代来说明本文算法的流程。首先根据自动寻优粒子编码方法, 随机选取表2所示的初始粒子方案 (新建/扩建一列中, 数字1表示新建, 数字2表示扩建, 后同) 。然后进入下层多目标模型, 经过潮流计算, 判断各个方案的安全性, 得方案4、5不满足安全性I类指标, 将其放入不安全方案集;方案1、2、3、6 (安全裕度分别为0.680、0.705、0.784、0.839) 满足安全性I类指标, 将其放入安全方案集。用综合评价方法对安全方案集中的方案进行比选, 并选出安全裕度较高的4个粒子方案 (迭代种群规模为4) , 提交至上层多目标模型。
在上层多目标模型中, 通过对粒子方案的安全性Ⅱ类、经济性、环境友好性、适应性和协调性计算比较后, 将方案1、2、3、6均放入精英集, 并根据粒子更新公式对各个粒子进行位置和速度的更新, 得到新粒子方案见表3。新粒子方案既没有在安全方案集中, 也没有在不安全方案集中, 需要到下层多目标模型中再校验安全性。
注:上标 (1) 表示迭代次数1。
在下层多目标模型中, 新粒子方案均满足安全性I类指标, 将其加入到安全方案集, 并提交至上层多目标模型。通过对粒子方案的安全性Ⅱ类、经济性、环境友好性、适应性和协调性指标进行计算比较后, 将方案1 (1) 、2 (1) 、3 (1) 、6 (1) 均放入精英集。此时精英集中包括方案1、2、3、6和更新的方案1 (1) 、2 (1) 、3 (1) 、6 (1) , 数量超过其规模上限 (4个) , 进行缩减, 得到表4。
按上述的过程不断迭代, 不断更新粒子方案, 直到得到最优解, 然后通过综合评价方法得到方案的最终评价结果见表5。
由表5可知, 方案3的灰色关联度最高, 为最优方案。从评价结果看在节点B处新建变电站的方案更优, 且安全裕度也更高。
注:上标 (1) 表示迭代次数1。
注:上标 (f) 表示精英集中的最终方案。
5 结论
针对输变电工程立项决策问题, 本文以安全性I类指标为前提, 安全性Ⅱ类、经济性、环境友好性、适应性和协调性指标为进一步优化目标, 建立了一个较为完整的输变电工程立项决策方案评价体系的高维多目标优化问题。为了能更有效地求解该问题, 提出自动寻优的两阶段双层多目标粒子群优化算法, 能在保证安全性的情况下, 有效地求解各个方案的评价指标, 并用综合评价方法进行比选决策, 选取最优方案。实际算例的应用结果表明该方法能有效地求解输变电工程立项决策问题。
摘要：建立输变电工程两阶段多目标决策评价模型, 该模型包括立项和决策2个阶段, 以及电网的安全性、经济性、环境友好性、适应性和协调性5个指标;提出双层多目标粒子群优化算法, 求解模型的Pareto最优解, 最后用综合评价方法选出最优实施方案。算例分析结果验证所提模型的正确性和有效性。