多项目群

多项目群（共10篇）

多项目群 篇1

摘要：对于工程问题来说, 工期、成本和质量三个目标是项目规划者需要考虑的具体目标, 这三个目标之间相互影响和制约, 一般算法难以求得三个目标同时最优的解。针对这种情况, 该文采用了多目标粒子群算法来求解工程项目工期-成本-质量多目标问题, 通过粒子群算法的最优解跟踪来求得问题的多目标非支配解集, 通过仿真算法表明, 该算法具有良好的搜索特性, 能够得到问题的多目标支配解集。

关键词：粒子群,算法,工程项目,多目标,优化算法

现代工程实践和科学研究中遇到的很多问题都是多目标优化问题, 多个目标之间通过决策变量项目制约, 对于单个目标的优化问题的唯一最优来说, 多目标问题的解并不是唯一的, 而是存在一个最优解结合, 在该集合内的每一个解都称为多目标非支配解。对于工程项目来说, 工期、成本和质量是工程项目的“三大目标”, 也是决定项目成功与否的关键因素, 对于任何一个项目, 即需要在约定时间内完成, 也需要控制项目成本, 同时还必须确保项目质量符合需求。但是工期、成本和质量这三个目标存在相互制约的关系, 一般来说, 工期和成本成正比, 工期和质量成反比, 成本和质量成反比。。因此, 需要采用多目标算法来求解工期、成本和质量三个目标优化问题, 并且从得到的解集中根据需求挑选出最优解作为该项目的最优规划目标解。

1 多目标粒子群算法

1.1 多目标算法

多目标优化算法可以描述为:一个由满足一定约束条件的决策变量组成的向量, 使得一个由多个目标函数组成的向量函数最优化。目标函数组成了性能标准的数学描述, 而性能标准之间通常是互相冲突的。优化意味着要找到一个使得所有目标函数值都可接受的解。

多目标优化问题中的最优概念最先由Francis Ysidro Edgeworth提出, 后来Vilfredo Pareto给出了系统的定义, 通常称为Pareto最优[1,2]。

不失一般性, 在一个有k个目标函数最大化的问题中, 称决策向量x*∈F是Pareto最优的, 当不存在另外一个决策向量x∈F同时满足式1。

同样地, 在最大化问题中称决策向量x优于y, 或者支配y, 需要满足式2。

1.2 多目标粒子群算法

结合粒子群算法搜索思想和多目标算法原理设计多目标粒子群算法, 由于相对于单目标粒子群算法中的个体历史最优和群体历史最优的唯一性, 多目标算法中个体历史最优和群体历史最优均是一个非支配解集, 因此在多目标算法的设计中需要解决从非支配解集中挑选出最优跟踪个体的问题。该文采用了文件记录的方法来记录在算法搜索的过程中找到的所有的非支配解, 并且采用一定的方法来选择个体跟踪的优秀目标。

由于多目标粒子群算法在搜索的过程中同时记录个体全局最优解, 个体最优解和局部最优解, 因此需要三个记录文件来记录。但是由于三个记录文件中的非支配解存在相互交叉支配的现象, 并且为了算法简洁高效, 该文采用一个档案文件同时记录全局最优解, 个体最优解和局部最优解, 档案文件在算法搜索的过程中, 只要发现新得到的搜索解存在支配管理, 就把该解放入记录文件中, 同时根据支配关系, 密度关系等调整记录文件中的最优解。

在记录文件记录所有最优解的基础上, 通过非支配解排序的方法来解决这个每次迭代搜索的时候, 粒子跟随的最优个体问题, 具体思路就是首先评估排序所有的非支配解, 然后从排序好的解集中根据排序的序号, 以选择概率的方法选择排序靠前的非支配解作为个体跟踪对象, 非支配解排序的序号越靠前, 其被选中的概率越大。

2 工程项目多目标建模

2.1 工程项目分解

本文在求解的时候首先采用网络计划技术把整个项目进行工序分解, 并且得到工序流程图, 流程图中的每个工序节点都有多种不同的施工方案, 每个施工方法都对应不同的施工费用、工期和质量。因此项目建设规划便存在多种工期、成本和质量的组合方案, 工程项目网络计划图如图1所示[3]。

其中, Mij表示第i道工序的第j种执行模式, Cij、Tij、Qij为该执行模式需要的执行成本、执行工期以及工序质量。

2.2 模型建立

在多目标模型建立的环节, 首先分别建立工期目标模型、成本目标模型和质量目标模型, 然后把三个模型进行组合, 得到了工程项目工期、成本和质量多目标优化模型[4]。

项目工期模型如式 (3) 所示。

其中, L表示路径集合, Li表示具体的路径, xim为0或者1, 代表是否执行了活动i的第m道执行模式, 其中1表示执行, 0表示没有执行。tim表示执行了活动i的的第m道执行模式所获得的所需工时。

项目成本模型如式 (4) 所示。

其中, xim为0或者1, 代表是否执行了活动i的第m道执行模式。uim, k表示在执行活动i第m道执行模式时, 所耗费的第k项资源的单位费用, rmi, k表示在执行活动耗费的第k项资源的量。idcim, k表示执行活动耗费的第k项间接资源费用。

质量目标模型如式 (5) 所示。

其中, qim表示在子工序i的在第m道执行模式中对应的质量值, 分母表示把所有子工序对应的指标质量值均设为10时的项目总质量值。

因此, 总体的多目标模型如式 (6) 所示。

3 仿真实验

采用工程项目多目标粒子群算法仿真实际工程道路项目, 该道路工程为典型的土方施工项目, 根据项目施工规划要求以及施工地的地质特点, 整个项目可以细化为包括施工准备、路基土方、软土处理、防护工程等在内的15项具体活动, 该连接线工程的网络计划图如图2所示。

采用多目标粒子群算法优化项目工序模式选择, 因为项目工序模式为整数, 所以采用对种群进行离散化, 即每一次迭代得到新的种群后, 都采用四舍五入的方法把新的种群离散化。因为一共有14道施工工序, 所以粒子维数为14, 从而每一个粒子都代表一个施工方案, 其他的参数为种群个数为100, 算法迭代次数为20。算法得到的多目标非支配解如图3所示。

从图3可以看出, 该文提出的多目标粒子群算法搜索性能较高, 算法在运行的时候能够找到较多的非支配解集, 对于每个非支配解集中的解来说, 都代表其中的一个施工方案。

4 小结

针对工程项目建设规划问题中工期-成本-质量三个目标相互制约, 一般算法难以得到三个目标的最优解的问题, 该文采用多目标粒子群算法进行求解, 在建立寻优问题的基础上, 采用粒子群算法搜索多目标问题的非支配解集, 仿真实验表明多目标粒子群算法能够得到工期-成本-质量多目标优化问题的解集, 从而为工程项目规划提供了一个新的参考方法。

参考文献

[1]郑向伟, 刘弘.多目标进化算法研究进展[J].计算机科学, 2007, 34 (7) :187-192.

[2]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006:6-12.

[3]曹吉鸣, 徐伟.网络计划技术与施工组织设计[M].上海:同济大学出版社, 2000 (6) .

[4]周艳.工程项目工期成本质量综合优化研究[D].西南交通大学, 2008:1-25.

多项目群 篇2

基于二元语义多属性群决策的投影法

针对解决具有语言评价信息的多属性群决策问题,提出了一种基于二元语义信息处理的群决策方法.该方法采用近年来最新发展的二元语义概念对语言评价信息进行处理和运算,并依据传统投影分析方法的基本思想,通过计算备选方案对正理想方案和负理想方案的.投影值,进而计算备选方案对正理想方案相对贴近度,最终确定最优方案.该方法具有对语言信息处理较为精确的特点,避免了以往采用的语言信息处理方法所带来的信息扭曲和损失.最后给出了实例分析.结果表明方法简单,有效和易于计算.

作 者：作者单位：刊 名：运筹与管理 ISTIC PKU英文刊名：OPERATIONS RESEARCH AND MANAGEMENT SCIENCE年，卷(期)：18(5)分类号：C934关键词：群决策 语言评价信息 二元语义 投影法 group decision making linguistic assessment information two-tuple project method

多项目群 篇3

摘要：蚁群优化算法作为单目标优化问题，由于只有一个目标函数，通常会将解限制到特定的范围内。当优化的目标不恰当时，算法可能失效，比如分辨率限制问题。我们将多目标优化的思想与传统的用于社区检测的蚁群优化算法相结合，增加了目标函数个数，即增加了解的评价指标数目。该算法引入多目标策略，提出多目标ACO算法，该算法在一次运行过程中会产生一组Pareto最优解。并在三个真实世界网络证明该算法的有效性和准确性。

关键词：复杂网络；社区检测；蚁群优化算法；多目标优化

中图分类号：TP18文献标识码：A

1引言

1991年意大利学者Dorigo M等人首次提出了蚁群优化算法[1，2]引起了学者的广泛关注与研究。蚁群算法是一种基于种群的启发式仿生进化系统，该算法采用了正反馈分布式并行计算机制，易于与其它方法相结合并且具有较强的鲁棒性。

本文介绍了一种基于蚁群优化的多目标社区检测方法，将蚁群优化算法与多目标策略[3]相结合，是一种优化模块度的社区检测方法。对于多目标优化问题，通常无法得到最优解，若同时考虑多个目标函数则算法将会得到一组优于其它解的最优解集。该集合叫做帕雷托（Pareto）解集或者非支配解集。

2基于蚁群优化的多目标社区检测

蚁群优化算法（ACO），是一种基于蚂蚁觅食行为的启发式方法，用来解决困难的组合优化问题，并且已经成功的应用到了各种棘手的问题，像二次分配问题（QAP），车辆路径问题（VRP）等。在1996年，Gambardella等人提出了一种修正的蚁群优化算法——蚁群系统（Ant System，AS），已经成功地应用在旅行商问题上。在这之后，科学家们也发明了一些改进的算法，比如精英蚁群系统（Elitist Ant System，EAS），最大最小蚁群系统（MaxMin Ant System，MMAS）以及排序蚁群系统（RankBased Ant System，ASrank）。

运用蚁群优化来做社区检测，首先需要指出如何表达一个解，其次就是如何构建一个解，然后就是信息素的初始化以及更新。下面我们将详细描述该算法。

2.1编码方式

社区就是复杂网络的子图，因而检测社区结构就等价于找出能揭示网络最好分割的一组子图。因此，社区检测问题的解可以明确地表示为：一个n个元素的向量表示图，其连通分量相当于社区。向量的元素和索引对应于图G=（V，A）中的节点。例如，向量中第i个元素等于j，即节点Vi和Vj之间有边相连，也就是说这两个节点在同一个连通分量里面，即处于同一个社区。

该编码框架的优点有很多，最重要的是不需要预先知道复杂网络的社区划分数目。解码的过程需要找出所有的连通分量。所有属于同一个连通分量的节点被划分到一个社区，解码过程是有必要的且可以通过广度优先搜索（breadthfirst search，BFS）或者深度优先搜索（depthfirst search，DFS）在线性时间内完成。解码完成后，会得到一个表示每个节点归属的向量。这种基于基因近邻的编码框架已经应用到了多目标聚类领域。该框架在社区检测的应用中有几个主要的优点，最重要的是，不需要预先知道社区的真实划分数目K，因为在解码过程中能够自动地得到K的取值。

3.1真实世界网络

本节将MOACO算法应用在三个真实世界网络上，分别是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上复杂网络是社会网络分析领域中的经典数据集，将这些数据在并与没有加入多目标策略的ACO算法以及GA、GAloacal算法进行了对比。由表2可以看出，三十次独立运行后，在Zacharys Karate Club网络中，ACO和MOACO的平均模块度值均不如GA和GA-local算法的结果好，而MOACO和ACO的平均模块度相差不大；在Dolphin social network网络中，本文提出的MOACO算法的平均NMI值明显好于其它算法。在Dolphin social network网络中，MOACO算法的模块度Q平均值与ACO算法的结果相差不大，而NMI的平均值要好于ACO算法。

为了验证蚁群规模和迭代次数对算法的影响，以Zacharys Karate Club网络为例进行参数分析，参数α、β、T、ρ、ε的值不变化，算法独立运行三十次求平均模块度值Q和平均NMI值，讨论蚁群规模N对算法结果的影响。

由表3可以看出，随着蚁群规模的增加，平均模块度值呈增长趋势，在蚁群规模为80时，达到了最大值。而由于蚁群优化算法中蚂蚁个体选择路径是随机的，因而平均NMI值没有呈现一定的规律，而当蚁群规模为40时，平均NMI值取得最大值。

表4表示参数α、β、N、ρ、ε保持不变，讨论迭代次数T对算法结果的影响，算法独立运行三十次的算法结果如表4所示。

由表4可知，迭代次数对算法的平均模块度值影响不大，而当迭代次数为150次的时候，平均NMI值取得了最大值。

图2表示调节参数过程中，算法取得的最优结果，即每一次运行的模块度值和NMI值，data1表示平均模块度值，data2表示平均NMI值。最优参数为：迭代次数150次，种群规模40。可以看出模块度值非常稳定。

3.2计算机仿真网络

本节使用经典的GN benchmark复杂网络来检测算法的可行性和有效性。GN基准网络是由Newman等提出。对于该基准网络，每个图包含了128个节点，分为4个由32个节点构成的社区。每个节点平均有Zin条边与同社区内节点连接，Zout条边与社区外节点连接。其中Zin+Zout = 16，作为每个节点的期望的度。随着Zout的增大，所产生的随机网络给社区检测算法带来了更大的挑战。特别是当Zout大于8时，意味着每个节点在社区内的边都要小于社区外的边，这时网络的社区结构就会非常模糊。当Zout≤ 8时，节点外度所占的比例小于内度所占的比例，因此算法应该能检测出网络中存在的社区结构，当Zout = 0时，表明节点的外度为0，此时节点仅与自身社区内的节点相连接，社区结构非常明显。分别对Zout从0到2进行了测试，对每种类型的网络产生一个复杂网络，使用NMI来衡量算法检测的结果和真实网络划分之间的相似性。对于每个网络，计算三十次独立运行的平均值。

由表5可以看出，当GN网络的外度为0时，该算法可以准确地检测出网络划分情况；当GN网络的外度为1和2的时候，该算法得到的结果也还都是有效的。

但是，在蚁群优化方法中，其算法复杂度比较高，所需要的搜索时间很长，而且容易出现所有的蚂蚁所对应的解完全相同这种“停滞现象”。导致了当复杂网络的社区数目较大时，算法不能产生有效解。另外，该算法对计算机生成的仿真网络不能得到有效的结果，这是我们进一步研究的内容。

4小结

基于传统的蚁群优化算法（ACO）算法的缺陷，提出了一种用于复杂网络社区检测的多目标蚁群优化算法MOACO，该算法将继续沿用传统的基于模块度优化的策略，加入了多目标的思想，每次迭代过程中，根据两个目标函数的不同折中，最终得到Pareto解集，选取每一代中优先级最高的那一组解。在三个真实世界网络和GN网络中的外度较小的网络上证明了算法的有效性，并将提出算法与ACO算法进行了比较，NMI平均值要优于ACO算法，模块度Q的平均值与ACO算法相当。缺点是不能处理社区划分类别多的复杂网络，对于结构模糊的GN网络，算法的效果不明显。

参考文献

[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.

[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.

[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.

[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.

多项目群 篇4

关键词：项目调度,资源受限,多模式,蚁群系统算法

0 引 言

资源约束项目调度问题RCPSP(Resource-Constrained Project Scheduling Problem)一般以找出工期最短(或耗费最小)的调度方案为优化目标,项目由一系列相互关联的活动组成,调度决策需要同时满足项目活动之间的时序约束和资源约束,以使管理目标最优[1]。多模式资源约束项目调度问题MRCPSP(Multi-mode Resource Constrained Project Scheduling Problem)是传统RCPSP的扩展,其考虑项目中每个活动都有多种可供选择的执行模式,每种执行模式对应一定的工期和资源需求,在调度时能够动态地选择活动执行模式及其属性。相对于单模式调度问题[2],MRCPSP在资源约束条件下,不仅要选择项目中各活动的执行模式,还要确定活动的开工期,是一类带有复杂非线性特征NP-难问题,精确类算法很难求解。随着智能算法的不断发展,其在项目管理领域的应用也越来越多。针对该问题,文献[3]提出基于二维编码方式的混合遗传算法对MRCPSP问题进行求解;文献[4]采用差分演化算法求解MRCPSP,取得了不错的效果;文献[5]运用改进蚁群算法求解MRCPSP,采用规则池管理和使用大量优先级规则,提升了算法的通用性和性能。

蚁群优化算法是文献[6]于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种新型的基于种群的启发式仿生进化算法,具有全局搜索、快速收敛等特点。由于它特有的构建性策略,特别适合于项目调度问题的求解。文献[7]已经验证,蚁群优化算法是求解传统以最短工期为目标的RCPSP的性能最优的算法之一。本文提出一种性能最优的蚁群优化算法之一的蚁群系统(Ant Colony System,ACS)算法[8]来实现MRCPSP的优化,采用基于活动执行模式的一维实数编码方案,把活动网络图转换为构建图,蚂蚁在构建图上在资源约束和时序约束下按一定规则游走来确定调度生成方案,定义新的信息素表示和启发式,得出一种用于优化MRCPSP的蚁群系统算法,最后用实验结果验证算法的正确性与有效性。

1 问题描述及模型

MRCPSP是研究在工程项目活动网络图的基础上,满足资源和活动时序等约束来安排各活动的执行模式和开始时间,以使项目工期最短的调度方法,其实质是寻求各个活动执行模式和开工时间的最佳组合。本文采用AOA(activity-on-arrow)有向活动网络图表示整个项目活动,如图1所示。其中结点代表事件,箭线代表活动,方向代表时序约束。

基于AOA图建立MRCPSP模型时作如下假设:

(1) 每种活动均有多种执行模式可供选择,每种执行模式对应不同的工期和资源需求。

(2) 每个活动只能选择其中一种执行模式执行,而且一旦执行就不能被中断和更改执行模式直至完成;

(3) 活动具有时序约束和资源约束;

(4) 资源均为可更新资源,每个活动所需资源量均小于资源的最大供应量;

(5) 对事件和活动进行编号时,确保事件按时序约束非严格递增,即事件j的所有紧前事件编号必须小于j,后继事件编号必须大于j;

(6) 为方便描述问题引入虚事件0和N+1(只有一种执行模式,不占用资源且执行时间为0),代表整个项目的开始和结束。Fm+1为结束事件(N+1)对应的唯一活动(M+1)的最早开始时间,即项目总工期。

设项目包含N个事件M个活动,从事件i到事件j的一项活动记为(i,j),r${}_{ijv}^k$为活动(i,j)用模式k执行时单位工期所需资源v的数量,d${}_{ij}^k$为工期。所有活动共享V种可更新资源,其中第v种资源的供应量为Rv。P(j)为事件j的紧前事件集合,S(j)为事件j的后继事件集合。优化目标是在满足资源约束和时序约束前提下,通过确定合理的活动执行顺序、相应的执行模式以及活动的开始时间,使项目的工期最短。其数学模型为:

minf(x)=Fm+1 (1)

s.t.${\displaystyle \sum _{(i,j)\in SA{}_t}{\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}r}}{}_{ijv}^{k}X{}_{ij}^k\le R{}_v(v=1,2,\cdots ,V$;t=1,2,…,TN) (2)

${\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}X}{}_{ij}^k=1((i,j)\in A)$ (3)

${\displaystyle \sum _{\begin{array}{l}t=E{\rm T}{}_{ij}\\ i\in {\rm P}(j)\end{array}}^{L{\rm T}{}_{ij}}t}Y{}_{ijv}^t\le {\displaystyle \sum _{\begin{array}{l}t=E{\rm T}{}_{jl}\\ l\in S(j)\end{array}}^{L{\rm T}{}_{jl}}(}tY{}_{jl}^t-{\displaystyle \sum _{k=1}^{{\rm K}{}_{jl}}d}{}_{jl}^{k}X{}_{jl}^k)(j=1,2,\cdots ,{\rm N})$ (4)

${\displaystyle \sum _{t=E{\rm T}{}_{ij}}^{L{\rm T}{}_{ij}}Y}{}_{ij}^t=1$ (5)

式(1)表示最小化项目工期;式(2)表示资源约束,SAt表示在时期t时正在进行的活动集合;式(3)表示活动仅能用一种模式执行(X${}_{ij}^k$=1时,活动以模式k执行,否则为0);式(4)表示时序约束,表达的是任意事件j的前趋活动(i,j)必须在事件j的后继活动(j,l)开始之前完成;式(5)定义了活动的时间窗约束,即活动(i,j)必须在其时间窗[ETij,LTij]内完成(如果活动(i,j)在时间窗[ETij,LTij]中的一个时点t上被完成,则Y${}_{ij}^t$=1,否则为0)。

2 求解MRCPSP模型的蚁群算法设计

在MRCPSP模型中使用蚁群系统算法,需要把问题表示的AOA网络图转换为蚂蚁路径构建图,得出问题的解的构建方法,并重新定义信息素和启发式信息的表示。

2.1 构建图

对所有活动(i,j)∈A的所有执行模式进行编号并将其变成构建图的结点,如图2所示。

假设图1中每个活动均有两种执行模式,即通常模式(N)和通过增加资源缩短工期的压缩模式(C)。则活动1的两种执行模式分别对应结点m1和m2,活动2的两种执行模式分别对应m3 和m4,活动3的两种执行模式分别对应m5 和m6,活动4的两种执行模式分别对应m7 和m8 ,m0和m9分别对应项目的开始和结束。通过编号得到构建图的结点集MODE={m1,m2,…,m|MODE|}。其中|MODE|是所有真实模式的总数目,mode0和mode|MODE|+1是哑模式,分表代表项目的开始和结束。

MODE中模式在两个方向上完全连接的有向边为信息素和启发式信息的载体,在边(mi, mj)上的信息素含量记为τij,在此边上的启发式信息记为ηij。

2.2 解的构建

蚂蚁从初始模式m0出发,寻找一条遍历所有活动一次且仅一次,最终到达结束模式m|MODE|+1的合法路径。

(1) 蚂蚁把开始模式m0添加到解序列中,初始化当前时间,并把所有初始事件的直接后继活动所有模式添加到候选集中。

(2) 蚂蚁根据信息素和启发式信息,从候选集中选出下一个可行模式添加到解序列中,根据当前时间、满足时序约束时间以及满足资源约束时间确定此模式的最快可开始时间(取三者最大值),将其设置为该模式实际执行时间。同时将当前时间设置为该模式的最快可开始时间,以保证模式序列开始执行时间的非严格递增性。

(3) 蚂蚁更新当前所占用的资源集合并更新候选集:

① 判断所选择的模式Si所属活动,把所有同属于该活动的模式从候选集中删除。

② 如果Si所在活动属于事件j的紧前活动,并且执行Si后所有事件j的直接紧前活动都已经被选择执行,那么事件j被激活,其直接后继活动的所有模式都被加入到候选集中;转(2)直到候选集为空。

2.3 算法流程

(1) 初始化

将蚁群置于开始模式m0处并初始化信息素。由于MRCPSP问题的优化目标是工期,项目总工期的长短是衡量一个项目调度方案质量优劣的标准。本文以项目总工期作为信息素的表达对象,信息素按式(6)进行初始化,其中,T0为由初始调度得到的项目总工期。

$\tau {}_{ij}=\tau {}_0=\frac{1}{{\rm T}{}_0}$ (6)

(2) 生成调度

蚂蚁在构建图的每次迭代过程中,各蚂蚁在各结点间信息素的引导下,按照一定的转移规则选择可行的活动模式并记下该模式所在的结点,同时将其放入模式列表中,直至生成一个时序可行的活动模式列表S=(S0,S1,…,SM+1),其中,S0= m0,SM+1= m|MODE|+1,即项目的开始和结束;对于l=1,2,…, M,Sl对应于按时间序列第l项发生的一种执行模式。每一种活动只对应于S中的一种模式,且必须满足AOA网络给定的时序约束。通过串行进度生成机制对所得模式列表进行解码,从而得到问题的一个解,即一种可行调度方案,最后根据得到项目工期评价各调度方案的优劣。

其中,某只蚂蚁当前位于模式mi时,选择下一可行的活动模式Sk时按转移规则式(7)和式(8)进行:

$S{}_k=\{\begin{array}{l}\text{a}\text{r}\text{g}\text{m}\text{a}\text{x}{}_{m{}_j\in \text{候}\text{选}\text{集}}\{[\tau {}_{ij}]\cdot [(\eta {}_{ij}){}^{\beta }]\}\text{如}\text{果}q\le q{}_0\\ \text{轮}\text{盘}\text{赌}\text{选}\text{择}\text{否}\text{则}\end{array}(7)$

${\rm P}(m{}_j)=\{\begin{array}{l}\frac{\tau {}_{ij}\cdot (\eta {}_{ij}){}^{\beta }}{{\displaystyle \sum _{m{}_l\in \text{候}\text{选}\text{集}}\tau }{}_{il}\cdot (\eta {}_{il}){}^{\beta }}\text{如}\text{果}m{}_j\in \text{候}\text{选}\text{集}\\ 0\text{否}\text{则}\end{array}(8)$

算法生成一个随机数q∈[0,1]并与参数q0相比较,如果q≤q0则选择函数直接返回候选集中具有最大信息素与启发式信息的β次幂的乘积值的模式mj,否则执行轮盘赌选择,如式(7)所示。也就是说,选中候选集中某种模式的概率与该模式的信息素与启发式信息的β次幂的乘积的值的大小成正比,如式(8)所示。其中,ηij为用于评价蚂蚁从Si向Sj移动的路径启发信息,β是一个表示启发式信息权重的参数。本文通过最大资源需求量优先启发式规则来确定ηij,若mj的资源总需求量为${\displaystyle \sum _{m{}_j\in \text{候}\text{选}\text{集}}r}{}_{m{}_{j}v}$,则t时刻蚂蚁在结点Si处的启发信息如式(9)所示,这样能够使最多资源需求的候选模式被更多的蚂蚁选择。

$\eta {}_{ij}(t)=\frac{{\displaystyle \sum _{m{}_j\in \text{候}\text{选}\text{信}}r}{}_{m{}_{j}v}}{{\displaystyle \sum _{v=1}^{V}R}{}_v}$ (9)

(3) 信息素更新

在所有蚂蚁完成一次循环后,对信息素进行更新。本文ACS采用两种信息素更新方式:在局部信息素更新中,每当蚂蚁从模式mi移动到mj,信息素更新规则将被立刻调用,如式(10)所示:

τij←(1-ρ)·τij+ρ·τ0 (10)

其中,ρ∈[0,1]是一个参数。由于τ0是信息素的初始值,相对较小。对于信息素含量高,经常被蚂蚁使用的边来说,局部信息素更新的作用在于减少该边上的信息素,使后来的蚂蚁能够尝试选择更多不同的边,从而增加了算法的搜索多样性。

全局信息素更新规则仅在每次迭代完成之后才执行。当所有蚂蚁都构建出它们的解并计算出其项目工期之后,全局信息素更新规则将对算法执行以来所发现的最优解S′上的所有边释放较大量的信息素,如式(11)所示:

τij←(1-α)·τij+α·T(S′) (11)

其中,mi和mj是在解S′模式序列上的两个相邻模式。全局信息素更新增大了蚂蚁对最优解上的模式的选择偏向性,从而使算法向最优解收敛。

3 实例验证与分析

本文采用一个包含10事件14活动的项目实例来验证ACS算法在解决该类问题上的可行性和有效性,项目活动网络图如图3所示。该项目需要三种可更新资源R1、R2 和R3,单位工期限量分别为8、16和20,除虚事件对应活动外,项目中每个活动均有两种可执行模式:通常模式(N)和通过增加资源缩短工期的压缩模式(C),不同执行模式下各活动的工期(T)及所需资源如表1所示。

利用本文提出的ACS算法对上述模型进行求解,算法参数设置:蚂蚁数目m=10,启发式信息权重 β=1,式(7)中的q0=0.5,局部信息素更新参数ρ=0.1,以及全局信息素更新参数α=0.1,算法迭代次数为30。运行结果为:项目最短工期31天,平均工期为32天,最佳调度方案如表2所示。

(1) 由表2可知:ACS算法能有效求解多模式资源约束调度问题,对项目各活动的执行模式和开工日期做出合理调度,以使整个项目工期最短。

(2) 运用遗传算法求解该实例,运行30次,其平均工期为34天,说明了ACS算法在求解MRCPSP问题上的高效性。

(3) 将ACS与简单遗传算法(GA)两种方法应用于一个包含20个事件、36个活动的项目上测试,两种方法均运行100次,结果如表3所示。说明对于较大规模的算例,ACS同样表现了良好的全局收敛性能。

4 结 语

本文把ACS算法应用到MRCPSP的求解中,详细分析了问题的模型,给出算法的设计思想、详细方法,通过实验用ACS算法对MRCPSP问题进行解答,数值实验结果证明了算法的正确性和有效性。特别是本文提出的算法无需结合其他优化技术,简洁高效,其基于活动执行模式的一维实数编码方案,相对于其它文献[2,3,4,5]的二维编码,更为简单实用,有利于蚁群算法在项目管理领域的进一步推广和应用。

参考文献

[1]Valls V,Ballestin F,Quintanilla S.Justification and RCPSP:A tech-nique that pays[J].European Journal of Operational Research,2005,165(2):375-386.

[2]陈旺,李波,史彦军,等.求解RCPSP问题的带分布估计的差异演化算法[J].计算机工程与应用,2011,47(4):1-4.

[3]王为新,李原,张开富.基于遗传算法的多模式资源受限项目调度问题研究[J].计算机应用研究,2007(1):70-74.

[4]Damak N,Jarboui B,Siarry P,et al.Differential evolution for solving multi-mode resource-constrained project scheduling problems[J].Computers&Operations Research,2009,36(9):2653-2659.

[5]彭武良.一种求解多模式资源受限项目调度问题的蚁群算法[J].信息系统学报,2009,3(1):1-10.

[6]Colomi A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European conference on Artificial Lift.France:Elsevier,1991:134-142.

[7]Merkle D,Middendorf D,Schmeck H.Ant colony optimization for re-source-constrained project scheduling[J].IEEE Transactions on Evo-lutionary Computation,2002,6(4):333-346.

多项目群 篇5

【关键词】机电专业群；交叉课程；前导课程；项目比较教学

【分类号】G712.4

目前，全国各高职院校注重课程改革，提倡项目载体、项目驱动教学，课程改革取得了一定成就。但是，存在一个共性的问题，就是专业群中同类课程的教学项目在设计选取上没有考虑专业人才培养规格的差别以及专业前导课程差异，所设计的教学项目基本一致。比如，机电专业群的电气自动化专业、机电一体化专业、应用电子专业都要学习单片机应用技术这门课程，可是三个专业在具体教学实施时，采取的教学载体基本是电子专业教学时采用的教学项目，结果导致机电一体化专业、电气自动化专业学生不了解该门课程的目的，更不明白和本专业职业能力有何关联。

一、机电专业群单片机应用技术课程教学项目改革的必要性

现代机电一体化产品或电气自动化控制系统都包含控制部分，控制器主要采用PLC或单片机。要求从业人员对产品或系统的控制装置拥有一定的装调、维护和技术改造能力.目前高职各类专业的单片机课程教学大都在理实一体化教室进行，并采用基于工作过程的行动导向教学，譬如项目引领、任务驱动、范例教学等[1]。

二、机电专业群单片机课程项目改造---以机电一体化专业为例

下面以机电专业群交叉课程---单片机应用技术为例，介绍交叉课程的项目改造方法。结合学院机电类专业精细化人才培养方案[4][5]，对项目教学内容进行改革，将项目载体由电子产品改为机电产品。具体做法就是将前导课程“机床电器控制”、“PLC应用技术”中的成熟项目改造成“单片机应用技术”课程项目。

“机床电器控制”与“PLC应用技术”是机电专业的两门专业核心课程，有比较完善的三相交流电机控制实训装置，教学设施齐全，教学设计完整且项目具有可操作性。学生通过项目学习与实训装置的训练，能够制作继电器控制电路板，组装PLC控制硬件系统。面对一个不太复杂的机电控制任务，基本上能够绘制出顺序功能图，并用梯形图程序来实现。因此学生对电机的继电器控制、PLC控制具备了较好的基础，在此基础之上，将前导课程中的成熟项目改造成单片机课程项目是可行的、必要的。我们设计并实施的项目如图1所示。

改造后的单片机教学项目，与前导课程项目比较起来，控制任务没有变。硬件方面，主电路没有变，只是控制电路有所改变，采用的控制器由PLC改成单片机，外围接口电路随之改变[6][7]。软件方面，PLC编程相对来说比较简单易学，从PLC编程过渡到单片机编程，具有循序渐进、一脉相承的特点，通过强化训练，学生能较好地完成知识与能力的迁移、内化，从而提高模块化、结构化程序设计能力。在项目教学过程的每个环节都引入比较教学法[8]──将该项目的每个模块或任务都与前导课程的对应项目进行比较。

三、专业群交叉课程教学项目改革措施

专业群交叉课程的教学项目设计需要考虑各专业人才培养规格的共性及差异，搭建一个“共性+特性”的课程教学资源平台，以实现课程教学与各专业类别人才培养目标的无缝链接，切实提高人才培养的质量。具体措施如下：

1.专业群交叉课程内容整合和划分，搭建“共性+特性”的教学平台[9]。

经过对我校机电专业群的人才培养方案、就业岗位群和典型工作任务、课程大纲的分析，发现这些专业对控制装置的安装、调试及维修能力培养要求上具有共性。但由于各专业岗位群职业技能目标的不同，也需要学生掌握自身专业相关的技能。

2.“项目比较”的创新教学模式。

根据相应的专业前导课程，结合“共性+特性”的教学内容设计，各专业教师在进行课程教学时，要充分结合学生已掌握的前导知识，进行“项目比较”教学。通过类比、对比实现异中求同、同中求异，从而加深学生的印象，同时把握知识要点。

参考文献

[1]张晓峰.工作过程导向的高职《单片机技术》课程改革与实践[J].职教论坛，2012.5：43-45；

[2]教育部职业教育与成人教育司.高等职业学校专业教学标准（试行）---电子信息大类[M].北京：中央广播电视大学出版社，2012；

[3]教育部职业教育与成人教育司.高等职业学校专业教学标准（试行）---制造大类[M].北京：中央广播电视大学出版社，2012；

多梯级泵站群调度自动化系统设计 篇6

关键词：泵站群,调度,自动化,模型

1工程概况

甘肃省景泰川电力提灌工程 (简称景电工程) 是高扬程多梯级大流量的电力提灌工程, 地处腾格里沙漠南缘。灌区横跨甘、蒙两省区, 白银、武威、内蒙古阿拉善盟三市 (盟) , 景泰、古浪、民勤、左旗四县 (旗) 。工程分期建设。

一期工程:1969年10月开工建设。设计流量10.6 m3/s, 加大流量12 m3/s, 年提水量1.48亿m3。设计灌溉面积2.028万hm2。

二期工程:1984年10月开工建设。设计流量18 m3/s, 加大流量21 m3/s, 年提水量2.66亿m3。设计灌溉面积3.47万hm2。

景电二期延伸向民勤调水工程:是一项利用景电二期工程的灌溉间隙和空闲容量向民勤调水工程。工程设计流量6 m3/s, 年设计调水量6100万m3。恢复灌溉面积1.013万hm2。

1996年, 在景电二期工程总干13级泵站建设了计算机监控系统, 2002年在景电一期工程10级泵站建设了泵站计算机监控系统。

2景电多梯级泵站群的运行调度

景电多梯级泵站群的运行为统一调度。调度上位计算机实时监测各泵站实时信息;调度人员通过上位计算机完成对水泵开/停远程控制操作和调节水位;事故/故障情况下, 制定并下达事故处理方式;通过闸门自动化控制系统, 监测各分水口实时流量, 定期电话询问并记录其他分水口的流量信息。

2.1景电多梯级泵站群的特点

梯级泵站多。景电一期工程11级泵站提水, 景电二期工程19级泵站提水。

总扬程高。景电一期工程总扬程472 m, 景电二期工程总扬程713 m。

流量大。景电一期工程设计流量10.56 m3/s, 加大流量12.00 m3/s;景电二期工程设计流量18.00 m3/s, 加大流量21.00 m3/s。

装机容量大。景电一期工程总装机容量6.7万kW, 景电二期工程总装机容量19.27万kW。

机组台数多。景电一期工程装机103台, 景电二期工程装机204台。

水泵流量不可调节。景电工程目前采用的水泵为固定流量的离心水泵。

泵站地处偏僻分散。泵站位于偏僻地区, 分散布局在113.24 km的渠线上。

工程渠线长, 建筑物多。景电一期工程总干及干渠总长73.44 km, 有各类建筑物141座;景电二期灌区总干渠及干渠总长113.24 km, 各类建筑物375座。

总干及干渠各种分水口多。共有流量从0.05～6.00 m3/s不等的干、支、独斗及其他分水口共计170多个。

工程运行监测点多, 信息实时性要求高。随着景电工程信息化建设的不断完善与发展, 对工程运行中计算机远程实时监测的点越来越多, 监测信息的实时性逐步增强。

对机电设备和水工建筑物完好率要求严格。泵站计算机监控系统要求机电设备的完好率高, 动作可靠。

泵站群运行调度复杂。在运行调度中, 要对各泵站水泵、各泵站区间流量分配、泵站群前池水位平衡调节、泵站群机电设备安全运行、渠道及其建筑物安全运行等一系列业务综合调度。

2.2多梯级泵站群运行调度自动化系统模型的建立

多梯级泵站群运行调度自动化内容包括:基本参数、经验数据、泵站运行方案生成及优化、泵站群自动运行、泵站前池水位调节、事故/故障处理等模块。

(1) 模块功能。

基本参数模块:存储基本的技术参。经验数据模块:存储调度经验数据和对基本参数的修改值。方案生成及优化模块:根据输入的参数, 生产各泵站运行方式, 并进行优化和存储方案。自动运行模块:自动下达控制命令。泵站前池水位调节模块:自动调节泵站前池水位。事故处理模块:根据事故发生的类型, 自动编制并自动执行最合理运行方案。

(2) 任务分布。

上位计算机:承担基本数据库的录入, 运行方案生成及优化, 控制命令下达, 泵站前池水位调节, 事故/故障处理等任务, 监视泵站运行信息。中心服务器:存储基本数据库、泵站各种运行信息、基本参数、经验数据、运行方案、各种流量及水位对应的库容量。下位计算机:执行上位计算机的指令, 采集与上报泵站各种相关信息, 事故状态的及时动作与上报 (如图1所示) 。

①基本参数库。

供电系统:电压、电流允许变化范围;保护系统信息;各种刀闸、开关的正常位置等基本数据。电动机:编号, 铭牌数据;断路器位置状态;远程/就地操作切换开关位置等基本数据。水泵:编号;铭牌数据;进、出水阀状态;轴承允许的最高温度等基本数据;泵站区间渠道:泵站区间渠道长度;渠道比降;渠道横断面形状、技术参数等基本数据。泵站前池:最低、最高控制水位;前池进水方式等基本数据。流量控制:水源泵站加大流量;各泵站区间的最大分水流量等基本数据。

②经验数据库。

电动机允许启动时间间隔;各水泵实际流量与名牌流量的差值;水泵、阀门、电机检修记录;泵站前池水位变幅等经验数据。

③条件判断。

水泵在开机前、运行中、停机后, 只要监测到目前状态满足基本数据库所有监测的开关量、数据量的要求, 视为正常。

④泵站运行方案生成及优化。

上位计算机以灌区需要的总流量为目标, 对水源泵站所有正常水泵, 按水泵铭牌流量和经验数据进行组合, 在各种组合中选取铭牌流量之和与目标最接近, 泵站装置效率最高的一组, 存储在服务器中。水源泵站下游各级泵站运行方案的生成, 以相邻上游泵站目标流量与该区间计划分配流量、损失流量的差为目标流量, 上位计算机对该泵站水泵进行组合, 选择最优的一组存入如服务。

2.3多梯级泵站群自动运行

(1) 多梯级泵站群开机。

泵站群首次开机, 对水源泵站, 上位计算机根据服务器存储的运行方案, 以经验数据库规定的时间间隔, 下达控制命令。

上位计算机监测水源泵站下游逐级泵站前池水位变化, 当水位达到最低设定值, 根据服务器存储的该泵站运行方案, 开启第一台水泵。以水位变幅达到经验数据库设定值, 且满足电动机启动允许时间间隔, 逐台启动水泵。

(2) 泵站前池水位调节。

水位调节是对泵站群水位的系统调节。引起泵站前池水位变化的因素是相邻泵站的提水流量差, 泵站前池水位调节是流量的调节。

①流量差的计算。

中心服务器机定时存储各泵站前池水位, 在当期流量下, 按照明渠非恒定非均匀流原理, 以泵站区间渠道特性为基础, 计算并存储当前水位对应的泵站区间的库容量, 与前一时刻库容比较, 库容差值与时刻间隔之比得到流量偏差。

②泵站前池水位调节方式及时刻。

泵站前池水位调节方式有区间分流调节, 改变原有更换同型号水泵调节, 操作调节水泵调节, 操作主水泵调节等多种方式。根据泵站群各泵站区间水位变化趋势, 综合判断, 选择需要调节的泵站, 以流量偏差的大小确定调节方式。当调节或被调节泵站前池水位达到设定上限或下限使, 上位计算机自动开始水位调节操作, 当达到设定下限或上限时, 上位计算机发令终止调节。

(3) 事故/故障处理。

事故/故障, 仅指泵站计算机监控系统能够检测到的电气设备事故/故障。

当出现事故/故障时, 根据事故类型、发生事故的范围, 上位计算机重新制定并下达新的运行方案。事故恢复后, 执行事故前的运行方案。

3结语

多梯级泵站运行调度水平, 直接关系到工程安全、高效节能运行。影响多梯级泵站运行调度的因素众多, 仅靠人力完成多梯级泵站的运行调度, 因为考虑、分析问题的不全面, 往往出现泵站溢流损失水量, 造成提水耗电量的增加, 事故处理不及时导致引发事故的发生。研究探讨多梯级泵站群调度自动化系统, 实现泵站各水泵最高效优化组合运行, 提高泵站装置效率, 避免因溢流造成水量损失, 提高干渠利用率, 减少能源消耗;及时准确的事故处理, 预防事故扩大, 造成经济损失, 保证工程安全, 在多梯级泵站群计算机监控的基础上, 进一步提升自动化、现代化水平。尤其是对安装了变速水泵的泵站群, 更容易实现调度自动化。

多目标优化的生长竞争蚁群算法 篇7

多目标优化问题的目标往往是互相冲突的, 能满足所有约束条件且使所有目标函数都能达到全局最优的解往往不存在, 而只是存在一组Pareto最优解或非劣解。近年来, 智能优化方法在解决多目标优化问题已取得一些成果。很多学者使用遗传算法[1,2,3]、 粒子群算法[4]、 蚁群算法[5,6]等对求解多目标问题的Pareto最优解进行了有益的探讨。

蚁群算法是一种源于大自然生物世界的仿生类算法[7]。蚁群算法已在一系列困难的组合优化问题求解中已取得了成效。基于植物生长向光性和竞争性机理, 本文提出了一种求解多目标连续系统优化问题的生长竞争蚁群算法及其数学描述, 并对部分典型多目标连续函数优化问题进行了测试和验证。

2 多目标优化的生长竞争蚁群算法

2.1 多目标优化

在实际应用领域中, 存在大量的多目标优化问题。如何在多个目标中寻找折中最优解是一个比较复杂的问题。多目标优化的数学描述如下:

$\begin{array}{l}\min F(x)=(f{}_1(x),f{}_2(x),\cdots ,f{}_k(x))\\ x=\{x{}_1,\cdots ,x{}_n|x{}_i\in [a,b]\}\\ \text{s}.\text{t}.g(x)\le 0\end{array}$

其中, F (x) 为多目标优化问题的目标函数, 其分量fi (x) , i=1, 2, …, k均越小越优, 对x*∈X, 若在X中不存在x使fi (x) ≤fi (x*) , i=1, 2, …, k, 且至少对一个i严格不等式成立, 则称x*为多目标优化问题的Pareto最优解或非劣解。

常用的优化技术本身并不能直接处理多目标优化问题, 往往将其转化为比较容易处理的单目标问题, 典型的方法有:主要目标法、线性加权法、平均和加权法、理想点法、乘除法和几何平均法等[8]。这些优化技术一般每次都只得到Pareto解集中的一个, 或是相对于Pareto最优解的一个折中解。

2.2 生长竞争机制

自然界中的竞争是在一定竞争规则下, 在竞争者的实力、竞争者和环境间的关系、竞争者之间的实力的差距等多种因素的作用下, 经过多次竞争, 使不同的竞争者分别占有一定的资源而达到一种新的竞争状态, 只要新的竞争状态优于旧竞争状态, 就会达到优化的目的。

生物学实验已经证明, 植物生长过程中, 当植物有1个以上的节时, 具体哪个节能生长出新枝取决于其形态素浓度, 形态素浓度大的节获得长出新枝的机会比浓度小的节大[9]。而形态素的浓度取决于对光资源的获取。在此我们引入如下的定义:

植物的n个节点为n个竞争者集合, m个可能长出新枝的机会构成m个资源集合, 第i个节点的状态s (i) , 即该生长点的生长素浓度。

n个节点的竞争力函数pk (i) 定义为:

$pk(i)=\{\begin{array}{cc}0,& s{}^{new}(i)<s(i)\\ \frac{s{}^{new}(i)-s(i)}{{\displaystyle \sum _{j\in v}s}{}^{new}(j)-s(j)},& v=\{j|s{}^{new}(j)>s(j)\}\end{array}$

其中, snew (i) 为第i个节点长出新枝后的生长素浓度。pk (i) 的含义是在当前状态下, 第i个竞争者占用资源后, 获得生长素的能力, 若pk (i) <rank (1) , 则该节点退化, 无竞争能力, 将不可能长出新枝。

2.3 多目标生长竞争蚁群算法的描述

一个孤立的蚂蚁随机移动时, 能检测到其它同伴所释放的信息素, 并沿着该路线移动, 同时又释放自身的信息素, 从而增强了该路线上的信息素数量。蚁群个体之间就是通过这种信息的交流达到搜索食物的目的。

一个典型的带约束函数优化问题可以使用常规的罚函数法将所有约束方程转入目标函数中。这样, 在算法的具体搜索过程中就不必考虑约束是否满足的问题, 而直接考虑目标函数优化。

对于连续函数fi (x1, x2, …, xn) , i=1, 2, …, k, 其定义域集合为n维欧氏空间, 可将其的定义区域等分作为搜索区域, 蚂蚁在搜索区域内按基于生长竞争机制进行局部优化, 并按不同情况释放不同的信息素, 而这些信息素可以被整个定义域空间中其它蚂蚁所感知。

定义1 多目标优化生长竞争机制

(1) 破土而出的茎杆有n个节点可能长出m个新枝;

(2) 每个生长点的生长素浓度s (i) = (f1 (x (i) ) , f2 (x (i) ) , …, fk (x (i) ) ) ;snew (i) = (fnew1 (x (i) ) , fnew2 (x (i) ) , …, fnewk (x (i) ) ) 为第i个节点长出新枝后的生长素浓度;

(3) 对于多目标问题, 为了保持pk (i) 大于等于零, 要求每个目标项的差值大于零。为此对竞争力函数pk (i) 作适当修改, 具体如下:

$pk(i)=\frac{\sqrt{\frac{1}{k}{\displaystyle \sum _{j=1}^k[}f{}_j^{new}(x(i))-f{}_j(x(i))]{}^2}}{{\displaystyle \sum _{i=1}^n\sqrt{\frac{1}{k}{\displaystyle \sum _{j=1}^k[}f{}_j^{new}(x(i))-f{}_j(x(i))]{}^2}}}$

(4) 若pk (i) >rank (1) , 共有k个。 若k>m, 按pk (i) 从大到小取前m个节点长出新枝。 若k<m, 取k个节点长出新枝;

(5) 若k=0或新枝越出规定的范围, 生长结束。

定义2 信息素释放规则

(1) 初试化区域初试最佳值Ziopt和全局初试最佳值Zopt

(2) 选取区域Ni按生长竞争机制获得最好解Zi,

①若Zi≥Ziopt, 不释放信息素;

②若Zi<Ziopt, 替换区域的最佳值;

若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2;

③若Zi与Ziopt无法比较

若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi 与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2。

蚂蚁的寻优方向与空间中其他区域的信息素浓度以及它们之间的目标函数的平均差异程度有关。

定义3 蚂蚁的邻域的转移概率定义为

${\rm P}{}_{ij}=\frac{[\tau {}_j]{}^{\alpha }[\eta {}_{ij}]{}^{\beta }}{{\displaystyle \sum _k[}\tau {}_k]{}^{\alpha }[\eta {}_{ik}]{}^{\beta }}$

其中, τj为区域j的信息素强度, ηij为为目标函数平均差异程度, 即为:

$\eta {}_{ij}=\sqrt{\frac{1}{k}{\displaystyle \sum _{t=1}^k[}f{}_t(c{}_i)-f{}_t(c{}_j)]{}^2}$

α为邻域吸引强度的相对重要性 (α≥0) ;β为目标函数平均差异的相对重要性 (β≥0) 。

定义4 信息素强度更新方程为:

$\tau {}_j^{new}=\rho \tau {}_j^{old}+{\displaystyle \sum _k\Delta }\tau {}_j^k$

这里, Δτkj的值为第k个蚂蚁在区域Nj每迭代一次所释放的信息素, ρ体现强度的持久性。

算法主要流程:

随着蚂蚁在区域内的信息素的释放, 依据蚂蚁的转移概率, 蚂蚁将集中于非劣解较多的区域, 获取更多的非劣解;同时蚂蚁在不同的区域内搜索, 使得所得的解有一定的分布度。

由算法实现的描述可知, 生长竞争机制区域搜索的时间和空间复杂度和新枝的长度及新枝中节点数有关, 实际计算过程中新枝的长度一般取区域半径的1/100～1/10, 而对应新枝中节点数为10～100。搜索过程超出区域, 则停止。因此, 整个算法的时间和空间复杂度主要和区域划分数、区域中的蚂蚁个数及非劣解的数量有关。假设区域的数量为k, 区域中的蚂蚁也为k, 非劣解的数量为s, nc为运算迭代次数, 则算法整个过程的时间复杂度为O (nck2s) , 空间复杂度为O (ks) 。应用上, 这个复杂度是可接受的。

3 实例验证

为了验证方法的有效性, 本文采用了如表1所示的3组测试函数[1,5]来测试算法的性能。在每个测试实例中, 以图形化的方式给出了此方法生成的Pareto前沿, 并对解的分布性能及散布范围[10]进行比较。

定义5 间距评估

$S=\sqrt{\frac{1}{n-1}{\displaystyle \sum _{t=1}^n(}\overline{d}-d{}_i){}^2}$

其中:

$\begin{array}{l}d{}_i=\underset{j}{{\displaystyle \min }}(|f{}_1^i(x)-f{}_1^j(x)|+|f{}_2^i(x)-f{}_2^j(x)|),\\ i,j=1,2,\cdots ,n\\ \overline{d}=\frac{1}{n}{\displaystyle \sum _{i=1}^{n}d}{}_i\end{array}$

n为算法获得的Pareto前沿上向量的个数, 当所获得的解越接近均匀散布时, 间距S的值越小。

定义6 最大散布范围评估

$D=\sqrt{(\underset{i=1}{\overset{n}{{\displaystyle \max }}}f{}_1^i-\underset{i=1}{\overset{n}{{\displaystyle \min }}}f{}_1^i){}^2+(\underset{i=1}{\overset{n}{{\displaystyle \max }}}f{}_2^i-\underset{i=1}{\overset{n}{{\displaystyle \min }}}f{}_2^i){}^2}$

其定义了两个极值解的距离, 其值越大, 表明算法的解散布范围越广。

算法用MATLAB编程实现并进行了计算测试。测试中所用的参数为α=β=1, ρ=0. 7, Q=1。区域分割数为10, 则每个实例为100个区域。生长竞争机制中n=10, m=1。

表2给出第1组测试函数迭代200次后的求得的间距, 所有解绘制的Pareto曲线如图2;表3给出文献[1]和文献[6]中算法的间距。两者比较本文算法好于其它算法。

表4给出编号2测试函数迭代10次后的求解结果, 图3给出第5次所得的Pareto曲线图;表5给出文献[5]、文献[6]的结果。两者比较本文算法其结果优于文献[5]、文献[6]的结果, 很好地逼近了Pareto前沿。

表6给出编号3测试函数迭代100次后的求解结果, 第2次求得的解绘制的Pareto曲线如图4; 表7给出文献[5]、文献[6]的结果。本文算法其结果优于文献[5]、文献[6]的结果。

4 结束语

本文基于生长竞争机制, 提出了用于求解多目标优化的生长竞争蚁群算法。通过将生长竞争与信息素释放相结合, 引导蚂蚁的行走方向。通过算例求解与测试, 效果良好, 可以很好地逼近Pareto前沿, 同时有一定的散布广度。算法的收敛性的理论分析是今后研究的重点。

摘要：提出一种求解多目标优化的生长竞争蚁群算法。该方法将生长竞争规则引入蚁群算法, 给出了在连续空间多目标函数优化的算法描述, 定义了生长竞争规则及蚁群邻域的转移概率, 并提出了实现算法的具体步骤。算法在MATLAB环境下, 对一些典型的测试函数进行了求解和验证, 实验结果表明该方法具有向真实的Pareto前沿逼近的效果, 是一种求解多目标优化的有效方法。

关键词：蚁群算法,生长竞争,多目标优化

参考文献

[1]Coello C A, et al.Multiobjective optimization usinga micro-genetic algorithm[C]//Proceedings of theGenetic and Evolutionary Computation Conference (GECCO2001) .San Francisco:Morgan KaufmannPublishers, 2001:274~282.

[2]Mu S J, et al.An efficient evolutionary multi-objective optimization algorithm[C]//Proceedingsof the IEEE Congress on EvolutionaryComputation (CEC2003) .Canberra:IEEE Press, 2003:914~920.

[3]王跃宣等.处理带约束的多目标优化进化算法[J].清华大学学报 (自然科学版) , 2005, 45 (1) :103~106.

[4]张利彪等.求解多目标优化问题的一种多子群体进化算法[J].控制与决策, 2007, 22 (11) :1313~1316, 1320.

[5]张勇德, 黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策, 2005, 20 (2) :170~173.

[6]朱刚, 马良.多目标函数优化的生长竞争蚁群算法[J].控制与决策, 2007, 22 (11) :1317~1320.

[7]Colorni A, Dorigo M, Maniezzo V.Distributedoptimization by ant colonies[C]//Proc.of the FirstEuropean Conf.on Artificial Life.Paris:ElsevierPublishing, 1991:134~142.

[8]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社, 2005:440~447.

[9]李彤等.求解整数规划的一种仿生类全局优化算法[J].系统工程理论与实践, 2005, 25 (1) :76~85.

多项目群 篇8

多传感器影像融合是指将不同传感器接收到的影像信息经过融合,提取各自的有用信息,最后综合成同一图像以供观察或进一步处理。从信息论的角度讲,融合后的图像将比组成它的各个子图像具有更优越的性能,综合整体信息大于各部分信息之和,也就是说,融合的结果应该比任何一个输入信息源包含更多的有用信息。多聚焦图像是指成像条件相同,而镜头聚焦目标不同的多个图像。当光学传感器(如数码相机)对某一场景进行成像时,由于场景中不同目标与传感器的距离不同甚至有很大差异,无法同时聚焦到这些目标使其清晰,常常分别聚焦到各个目标多次拍摄而得到多幅对这些目标分别聚焦的图像,聚焦点的不同导致各幅图像中清晰区域和模糊区域也各不相同,通过融合选取各图像中的所有清晰区域,可得到一幅景物均被“聚焦”的图像,便于人眼的观察或计算机的后续处理。

在众多的融合方法中,经典的有基于色彩空间变换的方法,如IHS变换、Lab变换、YUV变换[1]等;基于统计的方法,如主成份分析,Brovey变换[2]等;以及基于多尺度分析融合的方法,如金字塔分解和小波变换[3]等。这些方法在某些程度上都能获得一幅景物都清晰的图像,但它们都是独立工作,各自的优点不易综合;它们的融合规则也不易根据后续图像处理的需要而进行自适应调整,从而获取更加合适的图像。为了解决这两个问题,我们提出基于粒子群优化算法的多聚焦图像融合方法,首先利用离散小波变换和梯度金字塔方法融合获得的图像作为初始粒子,然后根据后续图像处理的需要来构造目标函数,再利用粒子群优化算法来优化目标从而获取合适的图像。

1 多尺度分析融合

小波变换用于图像融合有很多优点,图像经小波分解后,不同分辨率上的细节信息互不相关,这样可以将不同频率范围内的信号分别组合,产生多种不同特征的融合图像,而且图像在不同分辨率水平上的能量和噪声不会互相干扰,融合图像的块状伪影也容易消除[4,5]。在本文的实验中,将两幅图像进行基于DBSS(2,2)的离散小波变换,得到各自的低频部分和不同尺度下的高频细节部分,对于低频部分用加权平均的算子进行处理,对于高频部分采用取大算子进行处理。

梯度金字塔方法是对源图像进行多次滤波从而形成一个塔式结构,在塔的每一层都用一种算法对这一层的数据进行融合,从而得到一个合成的塔式结构。然后对合成的塔式结构进行重构,最后得到合成的图像,合成图像包含了原图像的所有重要信息[6]。

2 粒子群算法原理

粒子群算法(Particle Swarm Optimization,PSO)是一种全局优化进化算法,该算法源于对鸟类捕食行为的模拟,是一种非常有效而被广泛应用的迭代优化算法。与遗传算法相比,PSO的优势在于简单、容易实现,没有许多参数需要调整,特有的记忆功能使其可以动态跟踪当前的搜索情况调整搜索策略,适宜于对多目标进行优化[7]。

粒子群优化算法可描述为:假设在一个n维的目标搜索空间中(n为图像的像素的个数)有m个粒子(每个粒子代表一幅图像)组成种群Z={Z1,Z2,…,Zm},每个粒子所处的位置Zi相当于图像的灰度值,位置的变化对应于灰度值的变化。粒子通过不断调整自己的位置Zi来搜索新解。每个粒子都能记住自己搜索到的最好解,记为pid,以及整个粒子群经历过的最好的位置,即目前搜索到的最优解,记做pgd。每个粒子还有一个速度,记做Vi={vi1,vi2,…,vin},当局部最优解和全局最优解都找到后,每个粒子根据式(1)更新自己的速度,根据式(2)调整自己的位置。

式中:vid(t+)1表示第i个粒子在t+1次迭代中第d个像素上的速度,w为惯性权重,c1和c2是加速常数,rand()为0～1之间的随机数。

3 图像融合

3.1 融合算法

分别进行1、2、3、4层小波分解对原始图像进行融合得到的4幅图像与3、4、5、6层梯度金字塔融合方法产生的4幅图像作为初始图像,根据后续处理要求来构造由多个图像评价指标的加权和组成的目标函数,利用粒子群算法来优化目标函数来获取最终的融合图像。粒子群算法流程见图1。算法步骤如下:

1)粒子束初始化:分别利用DBSS(2,2)的离散小波变换和梯度金字塔变换的方法对源图像进行融合,所得到的每幅图像用一个向量表示并作为一个粒子,两种方法所得到的图像集作为粒子群算法的初始粒子种群;

2)目标函数构造:根据图像的后续处理的需要,选取合适的图像评价指标(组合)作为粒子群优化算法的目标函数,我们给每组图像分别选择平均梯度、熵、标准方差、空间频率作为目标函数;

3)每个粒子的初始速度设为0向量,计算每个种子的适应度函数值;

4)根据式(1)和(2)更新每个粒子的速度和位置,式(1)和(2)中的w、c1和c2选取与一般文献采用的值不一样,这里都选为0.5;

5)计算每个粒子的适应度值,即对于每个粒子计算它的目标函数值;

6)对于每个粒子,比较它的适应度值和它经历过的最好位置的适应度值pid,如果更好就更新pid;

7)对于每个粒子,比较它的适应度值和群体经历过的最好位置的适应度值pgd,如果更好就更新pgd;

8)判断终止条件,若在获得某个全局最优粒子后,连续5次迭代中最优粒子都没有改进或迭代次数达到30次,就结束迭代输出结果影像,否则转步骤4)继续迭代。

3.2 算法复杂度分析

假设每幅图像有n个像素,如把加、减、乘、除、赋值都看成一个单位运算,则本文算法的优化部分算法的时间复杂度为:每个粒子需要6n个运算来更新速度,n个运算来更新状态,即更新速度和状态的时间复杂度为O(7n);计算目标函数值(标准方差、平均梯度、熵、和空间频率)所需要的运算次数小于10n,因此总时间复杂度最多为O(17g⋅t⋅n)。其中,g表示粒子种群中粒子的个数,t为算法迭代最多的次数,本文中分别为8和30,即本文优化部分的时间复杂度最多为O(4 080n);而传统的小波包的复杂度O(nlog2n),典型的非下采样Contourlet一次变换复杂度为O(1 536n)。

空间复杂度:设存储每幅多光谱图像(n个像素)需要一个单位的空间,本文方法的模型算子和观测算子共产生8幅图像,即有8个初始粒子;在优化过程中,每个粒子需要保存一个自己搜索到的最好解和一个速度,即每个粒子共需要3个单位的空间;加上一个保存全局最优解的空间,由些可知本文共需要31个单位空间,即空间复杂度为常数31。

从上述的分析可知,本文方法的时空复杂不高,分别为线性和常数,正常情况下可以得到满足。

4 融合试验与结果分析

为了验证本文方法的性能,我们选择了两种类型的多聚焦图像进行融合实验,第一组是中间模糊四周清晰的图像与四周模糊中间清晰的图像,图像大小为256×256,如图2所示;第二组是左聚焦图像与右聚焦图像,图像大小为512×512,如图3所示。并与DBSS(2,2)的小波变换和梯度金字塔方法进行了对比。

表1为lady图像融合结果见。表2为Pepsi图像融合结果。

(a)中间模糊四周清晰的图像;(b)四周模糊中间清晰的图像;(c)DBSS(2,2)的小波3层变换融合的图像;(d)梯度金字塔3层融合的图像;(e)平均梯度作为目标函数融合;(f)熵作为目标函数融合;(g)标准方差作为目标函数融合;(h)空间频率作为目标函数融合

(a)Image with around focus;(b)Image with central focus;(c)3-level DBSS(2,2)fused image;(d)3-level gradient pyramid fused image;

(a)左聚焦图像;(b)右聚焦图像;(c)DBSS(2,2)的小波3层变换融合的图像;(d)梯度金字塔3层融合的图像;(e)平均梯度作为目标函数融合;(f)熵作为目标函数融合;(g)标准方差作为目标函数融合;(h)空间频率作为目标函数融合

(a)Image with left focus;(b)Image with right focus;(c)3-level DBSS(2,2)fused image;(d)3-level gradient pyramid fused image;

4.1 实验平台

实验的软硬件环境是:计算机为Intel(R)Core(TM)2 Duo CPU 2.50 GHz,内存为3 G,操作系统为Windows XP,实验平台为Matlab 7.0。

算法仿真伪代码如下:

如果我们用(迭代代数,适应度值)的形式来表示中间结果,在第一组试验中,以标准方差为目标函数时,各次迭代中最优粒子的适应度值如下:(0,59.9340)、(1,60.3672)、(2,60.7301)、(3,61.2110)、(4,61.4612)、(5,61.841 5)、(6,62.191 6)、(7,62.441 7)、(8,62.690 7)、(9,62.943 9)、(10,63.157 6)、(11,63.284 2)、(12,63.365 5)、(13,63.388 0)、(14,63.388 0)、(16,63.388 0)、(17,63.388 0)、(18,63.388 0)。其收敛过程如图4所示。

从图4可看出,用小波变换和金字塔变换融合方法所得的图像集作为初始粒子种群,粒子群优化算法刚开始迭代时,目标函数值上升较快,随着迭代代数的增加,上升速度开始下降,大概经过15次迭代后目标函数值就不再上升了。其它实验的情况与此类似,在此就不赘述了。

4.2 结果分析

本文从目视效果和图像的定量分析两方面来评价融合图像的质量。从目视效果上看,DBSS(2,2)小波变换方法和本文方法都获得了全景清晰的图像,但本文方法得到的图像相比DBSS(2,2)小波变换方法的结果,细节更突出,纹理更清晰,更有效地消除了图像模糊。图像的定量分析主要是从数理统计的角度算出图像的统计指标,常用的评价指标有:标准方差、平均梯度、熵、空间频率、相关系数、均方交叉熵等来评价融合的质量。其中标准方差是图像灰度值相对于均值的分散度的测定,值越大则图像的灰度范围越趋于分散,图像的反差大,分辨率越高。平均梯度能够反映出图像中微小细节反差和纹理特征,一般说来,该值越大,图像就越显得清晰。熵反映了信息量,一般熵值越大,图像所含的信息越丰富。空间频率反映了图像的空间清晰度。相关系数反映两幅影像光谱特征的相似程度。均方根交叉熵表示源图像与融合图像间的综合差异,均方根交叉熵越小,表示融合图像与源图像差异越小,融合效果也越好[8,9]。

从表1和表2中可以看出,当分别以平均梯度、熵、标准方差、空间频率为目标函数时,所得到的对应图像的平均梯度、熵、标准方差都较离散小波变换和梯度金字塔方法的对应值有一定程度的提高。这表明本文的方法可根据后续处理要求由图像各个属性指标值的依赖程度确定各个属性指标的权重值,从而获取合适的图像。从两个表中也可看出,通过本文方法所获取到的图像的平均梯度、熵、标准方差、空间频率的值普遍比DBSS(2,2)小波变换和梯度金字塔方法的对应值高,这表明本文方法可以有效地综合两个不同融合方法及各分解层数的优点。两组实验中,在反映互信息的相关系数指标上,本文方法不如小波变换和金字塔变换融合方法,这表明本文的优化算法部分在优化的过程中,对中间结果进行了一定的改变,即在一个中间结果图像中加入了其它的中间结果图像的信息。本文方法的均方根交叉熵都比DBSS(2,2)小波变换的大,比梯度金字塔方法的小,这在某种程度上表明本文方法在处理过程中没有引入虚假信息。

结束语

本文方法可根据图像各个属性指标对图像后续处理的影响程度,确定各个属性指标的权重值,构造由图像的多个评价指标加权和作为同化的目标函数。本文用四个极端例子即平均梯度、熵、标准方差和空间频率为目标函数,验证了该方法可以根据后续处理的要求对融合规则进行自适应地调整,能够有效地综合不同融合传统方法的优点。作为初始粒子的影像,除了离散小波分解、梯度金字塔外,还可使用主成分变换融合、高通滤波融合等其他融合方法得到的影像。在实际应用中,一般要综合考虑多个属性对图像后续处理的协同影响,以设置合适的目标函数。

参考文献

[1]SHI Hai-liang,FANG Min.Multi-focus Color Image Fusion Based on SWT and HIS[C]//Fourth International Conference on Fuzzy Systems and Knowledge Discovery,Haikou,Hainan,China,Aug24-27,2007,2:461-465.

[2]林卉,景海涛,张连蓬.a'Trous小波变换与PCA变换相结合的遥感影像融合分析[J].地球信息科学,2008,10(2):269-272.LIN Hui,JING Hai-tao,ZHANG Lian-peng.Remote Sensing Images Fusion Based on a'Trous Wavelet and PCA Transformation[J].Geo-Information Science,2008,10(2):269-272.

[3]王仲妮,余先川,张立保.一种基于整数小波变换的遥感影像融合算法[J].光电子-激光,2008,19(11):1542-1545.WANG Zhong-ni,YU Xian-chuan,ZHANG Li-bao.A remote sensing image fusion algorithm based on integer wavelet transform[J].Journal of Optoelectronics-Laser,2008,19(11):1542-1545.

[4]SUN Wei,WANG Ke.A Multi-Focus Image Fusion Algorithm with DT-CWT[C]//International Conference on Computational Intelligence and Security,Harbin,China,Dec16-19,2007:147-151.

[5]TANG Lei,ZHAO Zong-gui.The Wavelet-based Contourlet Transform for Image Fusion[C]//International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,Qingdao,China,July30-Aug1,2007,2:59-64.

[6]Petrovic V S,Xydeas C S.Gradient-based multiresolution image fusion[J].IEEE Transactions on Image Processing(S1057-7149),2004,13(2):228-237.

[7]del Valle Y,Venayagamoorthy G K,Mohagheghi S,et al.Particle Swarm Optimization:Basic Concepts,Variants and Applications in Power Systems[J].IEEE Transactions on Evolutionary Computation(S1089-778X),2008,12(2):171-195.

[8]狄红卫,刘显峰.基于结构相似度的图像融合质量评价[J].光子学报,2006,35(5):766-771.DI Hong-wei,LIU Xian-feng.Image Fusion Quality Assessment Based on Structural Similarity[J].Acta Photonica Sinica,2006,35(5):766-771.

多项目群 篇9

我国能源供应日益紧张,能源短缺将成为经济社会发展的制约瓶颈。经济负荷分配问题(Economic Load Dispatch,ELD)长期以来受到电力系统工程技术人员和研究者的重视,是电力系统分析领域中的重要研究课题。此外,发电过程中产生的很多污染物也逐渐引起人们的关注。因此在满足机组约束条件下,综合考虑燃煤成本和污染物排放量,采用多目标优化方法对机组负荷分配问题进行优化具有重要意义。

粒子群优化算法(PSO)是由Kennedy和Eberhart提出的一种优化算法[1],由于其易实现,在许多优化问题上得到了成功应用[2],并且很多情况下要比GA更有效。目前已有一些学者提出了基于PSO的多目标优化算法,其中Coello Coello等于2004年提出的MOPSO具有里程碑的意义[3];Liang等提出了全面学习粒子群算法(CLPSO)[4],该算法利用所有粒子的历史最好信息来更新粒子的速度;Liu等提出了一种模糊多目标粒子群算法(FMOPSO)[5],该算法引入了同步粒子局部搜索(SPLS)和模糊全局最好位置f-gbest;Agrawal等提出了一种交互粒子群算法(IPSO)[6],该算法结合了Pareto支配和交互决策行为。

在综合考虑燃煤成本和污染物排放量的情况下,很多学者提出了多种解决方案,如人工神经网络法[7]、免疫遗传算法[8]、人工免疫混沌优化方法[9]、伪并行NSGA-Ⅱ方法[10]等,此外另有针对区域电网节能发电调度模式的研究[11]。

本研究在节能减排背景下,综合考虑最小化机组煤耗量和污染物排放量,提出多目标节能减排负荷调度模型,改进基于Pareto最优概念的多目标粒子群算法,并对该模型进行求解。笔者按照本研究提出的方法对算例进行仿真实验,获得了分布良好的Pareto最优解,并有效降低了系统煤耗和污染物排放量。

1 多目标节能减排负荷调度模型

1.1 目标函数

本研究采用的节能减排发电调度模型是在满足系统运行约束和机组运行约束的条件下,以系统燃煤成本和污染物排放量最小为目标。

(1)最小燃料成本(或煤耗)。

燃煤成本是电厂生产最重要的经济指标,可以用机组有功出力的二阶多项式表示:

式中:Pi—第i台发电机组的有功功率;Ng—系统内发电机总数;ai,bi,ci—第i台机组的煤耗特性系数。

(2)最小污染物排放量。

火电机组在运行过程中会产生各种有害气体,主要为SO2和NOx氮氧化合物。SO2和NOx排放目标可用如下二次多项式表示(单位为kg/h):

式中:αis,βsi,γis和αi N,βi N,γi N—第i台机组的SO2和NOx的排放特性系数。

两个目标函数的量纲不同,宜采用标准化处理。由于本研究采用的多目标粒子群算法不需将多目标问题单目标化处理,同时由于引入半可行域概念从而避免了采用惩罚因子处理约束条件,只需要对相拥有同量纲的目标函数进行比较,故目标函数量纲不同不影响算法结果。

1.2 约束条件

(1)系统负荷平衡约束:

式中:PD—系统负荷需求;PL—系统的总网损,一般利用B系数法求取[12];P—Ng维发电机有功功率列矢量;B—Ng×Ng维对称方阵;B0—Ng维列矢量;B00—常数。

公式(5)给出了网损与B系数及各发电机有功功率的关系。

(2)机组出力约束:

式中:Pi,min、Pi,max—第i台机组的出力上、下限。

2 多目标粒子群算法及其改进

2.1 多目标优化问题

多目标优化问题的数学模型描述如下:

式中:x—决策向量,x=(x1,x2,…,xn)∈D;F—目标函数向量,F=(f1,f2,…,fr);gj(x)和hk(x)—约束条件;D—决策空间。

解x0、x1∈D,当且仅当:

称x0支配x1,记为xo>x1;设x*当且仅当不存在x∈D使得x>x*成立,则x*是Pareto最优解;所有Pareto最优解构成最优解集;所有Pareto最优解对应的目标函数值所形成的区域称为Pareto最优前端。

2.2 标准粒子群算法

标准PSO中,粒子在搜索空间的速度和位置根据如下公式确定:

式中:w—惯性权重;r1,r2—加速常数;rand()—[0,1]区间内产生的随机数;Pt,Gt—t时刻粒子自身最好位置pbest和全局最好位置gbest;xt,vt—时刻t的位置与速度。

PSO算法简单,容易实现,但使用PSO算法处理优化问题容易陷入局部最优,且由于多目标优化问题的特殊性,PSO算法还不能直接应用于多目标优化问题,需要对其进行改进。

2.3 改进多目标粒子群算法

2.3.1 约束条件处理

目前,使用最广泛的约束条件处理方法是惩罚函数法,该方法需要以大量的实验为基础来获得适当的惩罚系数,效率低下。本研究引入半可行域概念,避免了惩罚因子复杂的选取过程,通过设计PSO选择算子,并结合竞争选择对约束条件进行处理。

(1)竞争选择[13]:

(1)任何可行解都优于不可行解;

(2)两个可行解,目标函数值较好的为优;

(3)两个不可行解,违反约束程度小者为优。

(2)半可行域[14]:

大部分约束优化问题的解是在可行域边界附近取得,半可行域的引入就是对约束条件的放宽,这样可以更好地利用可行域边界附近的不可行解的有用信息。

(1)针对多目标优化问题,本研究对搜索空间的任一点X和可行域D之间的距离定义为:

式中:p,q—等式约束和不等式约束条件个数,m=p+q为全部约束条件个数;Gj(X)—违反第j个约束条件程度。

公式(15)表示了搜索空间中一点X违反第j个等式约束时Gj(X)等于gj(X),否则为0;公式(16)表示X违反第j个不等式约束时Gj(X)为hj(X)。显然d(X,D)描述了给定搜索空间中一点X和可行域D之间的关系:

(2)对于给定的正数ε∈R+,存在0

(3)半可行解优于不可行解,但劣于可行解。

(4)在半可行域内的个体可由多目标函数决定的Pareto支配来判定其优劣。

(3)选择算子[15]。

选择算子主要有两个作用:(1)形成半可行域,保证全局极值g Best一定在半可行域或可行域中,从而保证正确的进化方向;(2)当群体中的有利个体(可行解和半可行解)达到一定比例时,选择算子将逐渐减小半可行域宽度。选择算子的作用如图1所示,随着有利个体的不断增加,在已放宽的约束条件下,算法必将向此时的约束最优点(A1点)收敛,此时半可行域的宽度将减小,之后算法又将向另一点收敛(A2点),如此循环直至半可行域宽度为零,所有个体全部进入可行域,收敛于约束最优解B点。具体方法如下:

群体规模N,有利个体比例阈值R,初始化ε=0。

(1)计算有利个体的比例rate;

(2)如果rate>R并且ε=0,结束;

(3)如果rate>R并且ε>0,则ε=ε-σ,转(1);

(4)如果rate

一般来说σ的选取应该比ε小几个数量级。

2.3.2 非劣解集的构造

非劣解集用来保存每次迭代产生的新种群中的非支配解,外部精英集的更新将在非劣解集的基础上进行。本研究采用庄家法构造非劣解集,每一轮在群体中任选一个个体出任庄家,由庄家依次与群体中其他个体进行比较,将庄家所支配的个体淘汰出局;若庄家不被任何其他个体所支配,则庄家即为非支配个体,否则庄家也被淘汰出局。按照这种方法进行下一轮比较,直至群体为空。

2.3.3 精英归档技术

本研究采用精英归档技术,保存迭代过程中搜索到的非支配解。归档技术主要体现在两方面:(1)构建外部精英集,用来保存粒子群历史最优非支配解,并作为每个粒子全局极值的候选集合,通过自适应网格法进行维护,外部集保留的最终解集就是算法求解的结果;(2)构建粒子个体外部非支配解集,用来保存个体的历史最优非支配解,并作为每个粒子个体极值的候选集合。实践证明,归档机制能够大幅度提高算法的收敛速度和解的质量。

2.3.4 采用自适应网格法维护外部精英集

为了让外部集对种群起到很好的引导作用,以及获得分布均匀的Pareto前端,本研究采用自适应网格法对外部精英集进行维护。自适应网格法首先将整个目标空间分成若干个超立方体,网格的划分数和外部精英集大小为确定常数,网格的大小在搜索过程中根据当前代的个体分布情况自动调整。每个外部精英集中的粒子都对应一个超立方体,定义每个超立方体中的粒子数为该超立方体的密度值;当外部精英集满溢时,本研究随机选取密度最大的超立方体中的一个粒子抛弃,以实现对外部精英集的维护和更新。本研究对新产生的个体x分情况进行处理,注意不要抛弃在某个目标上取最小的个体(称为极点),这样有利于使进化群体具有更好的分布性。新非支配解在外部集边界外时的外部集更新方式如图2所示。具体方法如下:

(1)若个体x被外部集支配,则个体x不进入外部集;

(2)若个体x支配外部集中的某些粒子,则将个体x加入外部集,并去掉外部集中的被支配粒子;

(3)若个体x与外部集无关,且外部集不满,则将个体x加入外部集;若外部集满溢:(1)个体x在边界外或者个体x在边界内且不在密度最大区域,则将个体x加入外部集,并随机选择密度最大区域中的一个粒子抛弃;(2)个体x在边界内且在密度最大区域,则外部集保持不变。

2.3.5 个体极值和全局极值的选取

(1)个体极值pbest的选取。本研究引入半可行域的概念和个体外部非支配集后,对每个粒子i基于下述规则来选取pbest:当粒子i和其上一代pbest均为非可行解时,比较二者与可行域D之间的距离d(X,D)(定义见半可行域),d小者为pbest;当两者分别在可行域和半可行域,或者分别在半可行域和非可行域时,选取前者为pbest;当两者同为可行解或半可行解时,以支配关系来选取pbest;而当两者同为可行解或半可行解且是非支配关系时,把两个个体均存入个体外部非支配集,计算个体外部非支配集中非支配个体的权重系数Fi,对应权系数最小的个体被选作pbest。权重系数计算公式如下:

式中:fj(Xi)—个体外部非支配解集中个体Xi第j个目标函数值,Np—个体外部非支配解集中非支配解的数目,r—问题目标个数。

(2)全局极值gbest的选取。gbest的选取直接影响算法的收敛速度和解集的分布性,本研究采取轮盘赌法和高斯变异的方法对gbest进行选取。对外部精英集中的每个粒子i按照轮盘赌法选取一个超立方体(见自适应网格法),然后随机选取超立方体中的一个粒子,如果该候选粒子支配粒子i的上一代gbest,则将该候选粒子设为粒子i的新gbest。在迭代过程中,每个粒子所获得的gbest均不相同,这意味着粒子将沿不同的方向飞行,对提高算法的探索能力有利。

当算法运行到一定阶段后,作为gbest的粒子已在非劣最优面上,此时将很难找到支配gbest的粒子,gbest不再发生变化,最终导致算法停止搜索最优面上的其他解而影响解集的分布性。本研究采用实时变异来解决这个问题。当目前群体中的gbest位置连续无变化或变化非常小时,保留gbest位置并对gbest实行高斯变异,用变异后代代替gbest。对粒子i的gbesti=(gi1,gi2,…,gin)进行高斯变异,定义如下:

式中:N(0,1)—服从均值为0、均方差为1的高斯分布。

3 多目标最优负荷分配

3.1 粒子群矩阵表示方法

本研究构造粒子群矩阵P,维数为Num P×D,其中Num P为粒子群中的粒子个数,D为目标维数,具体形式如下:

式中:fij—第i个粒子的第j个目标函数值。

3.2 约束条件处理

对于问题的不等式约束,本研究引入半可行域的概念进行处理;对于等式约束,则先考虑前n-1台机组出力,然后以等式约束确定第n台机组出力,故该问题等式约束可严格满足。

3.3 最优折中解的确定

在得到Pareto解后,为从中选择一个满意解作为最后结果,本研究采取模糊逻辑来选出最优折中解。定义模糊隶属度函数[16]如下:

式中:fi—第i个子目标适应度值;fi,max,fi,min—适应度函数的上限和下限。对Pareto解集中每个解求其标准化满意度值,标准化满意度值最大的解即为最优折中解。标准化满意度值定义如下:

式中:uk—每个解的标准化满意度值,Nobj—目标个数,M—Pareto解集中个体的数目。

3.4 算法基本流程

算法基本流程如下:

(1)初始化粒子群P,对每个粒子确定其初始位置和零初始速度;

(2)计算粒子群P中每个粒子的目标向量;

(3)初始化pbest和gbest为本身初始位置;

(4)更新粒子速度和位置;

(5)利用选择算子,获得足够多的有利个体;

(6)利用庄家法构造非劣解集;

(7)更新外部精英集:利用自适应网格法将非劣解集放入外部集;

(8)更新pbest和gbest:按照pbest和gbest的选取规则更新pbest和gbest;

(9)返回步骤(4),直至满足终止条件。

4 算例分析

根据目前的模型及算法,本研究以文献[12]中的某厂六机组系统为算例,在负荷分别为500 MW和700 MW的情况下,计算求解各机组出力并进行综合分析。机组燃煤成本系数、NOx排放系数以及网损系数详见文献[17],系统负荷为PD=500 MW(/700 MW),种群规模为100,外部精英集规模为200,个体非支配解集规模为50,自适应网格划分数为16,w=0.5,r1=r2=2.0,有利个体比例阈值R=0.1,半可行域初始宽度ε=10,步长σ=0.001,最大迭代次数为300,仿真实验的终止条件为达到最大迭代次数。

算例计算过程表示,在迭代至10次以上时,粒子群中的大部分粒子将收敛至可行域,这部分粒子用来作为进入外部精英集的备选粒子;另有部分粒子位于不可行域并徘徊于可行域边缘,该部分粒子将继续引导粒子群探索最优解。

负荷为500 MW和700 MW时,采用本研究使用的改进多目标粒子群算法得到的Pareto前沿的分布情况如图3、图4所示。由该Pareto前沿可见,本研究采用的改进多目标粒子群算法通过使用自适应网格法维护外部精英级获得了分布均匀的Pareto最优解。此外图中显示的燃煤成本和NOx排放量的关系说明了二者之间的矛盾性,无论是降低燃煤成本还是降低NOx排放量都将已牺牲另一个节能减排指标为代价,而一般情况下使各目标同时最优是不可能的。本研究分别给出了燃煤成本最优、NOx排放量最优以及折中解3种结果,决策者可根据实际情况从中选取适当的最优解使用:当以燃煤成本为主要目标时,选择最优成本解;当以污染物排放量为主要目标时,选择最优NOx排放量解;若希望从整体角度进行节能减排优化,可选择折中解。

排放目标函数的收敛情况如图5所示,从图5中可以看出,在迭代45次后排放目标函数收敛(燃煤成本函数收敛情况类似),获得了较好的目标函数值。

在负荷为500 MW和700 MW时,笔者采用MAMOEA、NSGA-Ⅱ和本研究算法所求得的不同结果如表1、表2所示。由得到的不同负荷情况下的Pareto前沿及不同算法的求解结果可见:(1)无论是最优燃煤成本还是最优NOx排放量均获得了更低的最优值,扩大了值域范围,说明本研究采用的改进多目标粒子群算法利用精英归档技术以及基于半可行域的个体极值和全局极值选取方法得到了具有更好多样性的Pareto最优解;(2)由表1和表2可见,相比较MAMOEA和NS-GA-Ⅱ所得到的结果,本研究算法得到的最优燃煤成本、最优NOx排放量和500 MW负荷下的最优折中解均优于前二者,甚至在最优燃煤成本的结果中,同时获得了更低的NOx排放量,最优NOx排放结果也有类似情况,总体来说获得了更低的煤耗成本和污染物排放效果。假定全年每台机组平均运行320天,以负荷500 MW为例,则本研究方法与其他两种方法相比,一年最高可节省70多万元的燃煤成本,污染物排放量最高可减少4.5 t,充分说明了本研究算法的优越性。

5 结束语

本研究提出了多目标负荷调度的数学模型,并用改进的多目标粒子群算法加以求解。利用该算法可以得到具有良好多样性和分布性的Pareto最优解,并为决策者提供了具有不同侧重目标的最优解,有效地降低了系统煤耗和污染物排放量,分析结果验证了该方法的有效性和可行性。

摘要：在节能减排背景下,综合考虑最小化机组煤耗量和污染物排放量,提出了求解多目标节能减排负荷调度的模型及改进多目标粒子群算法。该改进算法引入半可行域的概念处理约束条件,避免了惩罚因子复杂的选取过程;采用精英归档技术构建了外部精英集和个体非支配解集,提高了算法的收敛速度和解的质量;采用了自适应网格法维护外部精英集,获得了分布均匀的Pareto前沿;并提出了基于半可行域概念的个体极值和全局极值选取规则。利用该方法对某电厂6台机组系统进行了节能减排最优负荷调度,获得了分布良好的Pareto最优解,有效降低了系统煤耗和污染物排放量,分析结果验证了该方法的有效性和可行性。

多项目群 篇10

蚁群算法(ant colony optimization,ACO)是20世纪90年代由意大利学者Dorigo等[1]受自然界中真实蚁群行为的启发首先提出的一种模拟进化算法。算法主要由策略选择、信息素更新和局部搜索算法组成。蚁群算法目前已被扩展应用到许多问题领域中,但国内外文献中比较多地集中在纯组合优化如旅行商问题(TSP)、调度问题(JSP)、车辆路径问题(VRP)等,或者连续优化问题如连续函数优化等,对蚁群算法在生产批量决策等这一类混合规划问题中的应用研究比较少。

在工业生产中,对于多时间段的生产批量优化问题一类混合规划问题,一方面需要对批量与库存等连续变量进行决策,另一方面需要对生产与不生产的0-1整数规划问题进行决策。单级多时段多资源约束的生产批量问题(capacitated lot sizing problem,CLSP)是生产批量问题中比较常见的问题,同时也是实现制造资源计划(MRPⅡ)的关键问题,它是在多资源的约束下,为了消除资源冲突,对产品、时间、数量这三维变量同时进行调整,使得在整个计划范围内生产费用、调整费用和库存保管费用的总和最小[2]。Florian等[3]证明了单个产品的单资源约束的生产批量计划问题属于NP-hard问题。目前该类问题的精确解求解算法只能求解小规模问题,而专用的启发式算法只能求解特定的生产批量计划问题。近年来出现了一些启发式和元启发式算法,如模拟退火算法[4,5](simulated annealing)、遗传算法[6,7](genetic algorithm)、粒子群算法[8,9](particle swarm algorithm)、元算法[10](memetic algorithm)等,为解决更大规模的此类问题提供了新的途径。

目前,国内外学者对用蚁群算法解决生产批量问题的研究很少,只有极少数学者进行了一些尝试,如Pitakaso等[11]使用蚁群算法和改进的Wagner-Whitin算法来求解无能力约束的两层批量生产问题,其中使用蚁群算法来得到批量生产次序,再利用改进的Wagner-Whitin算法来得到具体生产数量;Almeder[12]使用蚁群算法和LP/MIP求解器(如CPLEX)相结合的方法来求解有能力约束的两层批量生产问题,其中使用蚁群算法来得到批量生产次序,再根据生产次序利用LP/MIP求解器来得到具体的生产数量。马艳等[13]研究了含再制造的批量问题,并用蚁群算法进行求解。与国内外学者提出的算法不同的是,本文提出了用于求解多资源约束生产批量计划问题的新颖蚁群算法,该算法的新颖之处在于:首先使用惩罚因子的方法对多资源约束条件进行处理,然后根据文献[14,15]得到的关于单级多资源多时段约束生产批量问题的一些性质,把连续与整数混合规划生产批量问题转换为求解0-1整数生产矩阵的问题。本文算法也相应地把蚁群算法中的每只蚂蚁的寻优空间设置为0或1,最后为了提高寻优率,对得到的0-1整数生产矩阵进行变异操作并进行局部搜索。将本文算法的结果与其他算法的结果以及优化软件Lingo得到的结果进行了比较分析。

1 单级多时段多资源约束的生产批量计划模型

单级多时段资源约束的生产批量计划问题可以描述为:给定不同时间段的不同产品的需求,在有限资源约束下,寻找最佳的不同时间段的生产批量,以满足需求。根据此问题的特点,可作如下假设:①每个产品的提前期为1;②不允许缺货;③不允许加班。则此问题的数学模型如下[14]:

$\min ({\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{t=1}^{{\rm T}}(}}p{}_{it}x{}_{it}+s{}_{it}y{}_{it}+h{}_{it}{\rm I}{}_{it}))$ (1)

s.t. Ii,t-1+xi t=Ii t+di t (2)

i=1,2,…,N;t=1,2,…,T

${\displaystyle \sum _{i=1}^{{\rm N}}(}a{}_{ij}y{}_{it}+b{}_{ij}x{}_{it})\le C{}_{jt}$ (3)

j=1,2,…,R,t=1,2,…,T

xi t≤Myi ti=1,2,…,N;t=1,2,…,T (4)

yi t∈{0,1} i=1,2,…,N;t=1,2,…,T (5)

xi t≥0,Ii t≥0 i=1,2,…,N;t=1,2,…,T (6)

Ii0=Ii t=0 i=1,2,…,N (7)

$y{}_{it}=\{\begin{array}{l}1\text{产}\text{品}i\text{在}\text{时}\text{间}t\text{有}\text{生}\text{产}\text{任}\text{务}\\ 0\text{其}\text{他}\end{array}$

式中,N为生产产品的总数;T为计划期的长度;R为可用资源数;M为足够大的数;pi t、si t、hi t分别为产品i在时间t的单位生产成本、单位调整成本、单位库存成本;di t为产品i在时间t的需求量;ai j为产品i对第j种资源的准备工时系数;bi j为产品i对第j种资源的加工工时系数;Cj t为资源j在时间t的可用工时;xi t为产品i在时间t的生产量,为决策变量;Ii t为产品i在时间t的库存量,为决策变量;yi t为决策变量。

目标函数式(1)使整个计划期内产品总的调整费用、库存费用和生产费用之和最小;式(2)表示满足需求的物流平衡方程;式(3)表示资源能力的限制;式(4)表示只有当生产数量大于0时才能发生调整费用和准备工时;式(5)表示yi t是0或1的调整变量;式(6)表示每个生产周期的生产数量为非负且不允许缺货;式(7)表示初始和结束周期库存为0。

2 求解单级多时段多资源约束的生产批量计划的改进蚁群算法

蚁群算法的构造主要包括初始解设定、转移概率计算、适应值计算、信息素更新。具体的构造过程如下。

2.1模型解的性质与解的构造

约束生产批量问题是一个混合整数规划问题,其中包括连续变量xi t和Ii t,还存在0-1整数变量yi t,因此明确变量之间的关系对问题的求解会有很大帮助。

对于多资源多时段约束生产批量问题,通过下面定理可知,一旦给定变量yi t,就能唯一地确定xi t和Ii t。

定理1[14,15] 对于单级多资源多时段约束生产批量问题,如果yi t给定(i∈[1,N],t∈[1,T]),则此问题的最优解xi t和Ii t可由yi t唯一确定,即

$x{}_{it}=\{\begin{array}{l}0y{}_{it}=0\\ {\displaystyle \sum _{j=t}^{t{}_1}d}{}_{ij}y{}_{it}=1,t{}_1=\underset{p=t+1,\cdots ,{\rm T}}{{\displaystyle \min }}\{p|y{}_{ip}=1\}\end{array}(8)$

Ii t=Ii,t-1+xi t-di t (9)

因此,对于单级多资源多时段约束生产批量问题的蚁群算法,采取如下策略对该问题进行求解:①每只蚂蚁根据转移概率确定某产品i在t时间段是否安排生产任务来确定变量yi t;②根据定理1,由yi t通过式(8)和式(9)来确定xi t和Ii t的值。

2.2信息素和启发信息设定

由于变量yi t是一个二值变量,信息素和启发信息是影响yi t选1还是选0的因素,因此信息素和启发信息都分为两种情况。

(1)信息素的设置。令Vk(1)(l)为第l次迭代第k只蚂蚁对应的执行生产任务的信息素矩阵,Vk(0)(l)表示第l次迭代第k只蚂蚁对应的不安排生产任务的信息素矩阵,则有如下关系:

Vk(1)(l)=[τk(1)i t(l)]N×T

Vk(0)(l)=[τk(0)i t(l)]N×T

其中,τk(1)i t(l)为第l次迭代第k只蚂蚁所对应的产品i在t时间段进行生产的信息素,τk(0)i t(l)为第l次迭代第k只蚂蚁所对应的产品i在t时间段不安排生产的信息素。这里,设置迭代开始的时候,信息素τk(1)i t(l)和τk(0)i t(l)为随机产生的介于0.01～1间的值,可根据下式生成:

τk(1)i t(l)=τmin+R(0,1)τmax (10)

其中,τmin=0.01,τmax=1,R(0,1)为介于0～1间的随机数。τk(0)i t(l)可同理生成。

(2)启发信息的设置。启发信息与迭代次数和蚂蚁无关,只与初始的数据有关,因此不因迭代和蚂蚁而变化。显然,如果产品的调整费用系数越大,生产费用系数越高,则其可见性也应该越小,因此我们将有生产任务的启发信息矩阵设置为H(1)=[η(1)i t]N×T,其中

η(1)i t=c0/(s′i t+p′i t) (11)

式中,η(1)i t为产品i在t时间段进行生产的启发信息;s′i t为产品调整费用系数si t的归一化值;p′i t为产品生产费用系数pi t的归一化值;c0为给定的权重系数。

令η(0)i t为产品i在t时间段不安排生产任务的启发信息,显然有η(0)i t=1-η(1)i t。

2.3转移概率的设定

令yki t(l)为第l次迭代第k只蚂蚁对应产品i在t时间段是否安排生产的调整变量,对应的调整变量矩阵为Yki t(l)=[yki t(l)]N×T,设置转移概率为[12]

$p{}_{it}^k(l)=\frac{(\tau {}_{it}^{k(1)}(l)){}^{\alpha }(\eta {}_{it}^{(1)}){}^{\beta }}{(\tau {}_{it}^{k(1)}(l)){}^{\alpha }(\eta {}_{it}^{(1)}){}^{\beta }+(\tau {}_{it}^{k(0)}(l)){}^{\alpha }(\eta {}_{it}^{(0)}){}^{\beta }}$ (12)

式中,pki t(l)为第l次迭代第k只蚂蚁对应产品i在t时间段进行生产的概率;α为信息素的重要性;β为启发信息的重要性。

本文考虑如下转移规则:

如果第l次迭代第k只蚂蚁对应产品i在t时间段有生产任务的概率比没有生产任务的概率要大,则将yki t(l)置为1,即第l次迭代第k只蚂蚁对应产品i在t时间段进行生产。

2.4适应值的计算

一旦确定了调整变量矩阵Yk(l),就可根据定理1来确定所有其他决策变量(生产批量矩阵Xk(l)=[xki t(l)]N×T和库存量矩阵Ik(l)=[Iki t(l)]N×T),因此适应值是矩阵Yk(l)的函数[8]:

$\begin{array}{l}f{}_k^l[\mathit{Y}{}^k(l)]=({\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{t=1}^{{\rm T}}(}}p{}_{it}x{}_{it}+s{}_{it}y{}_{it}^k(l)+h{}_{it}{\rm I}{}_{it}))+\\ G{\displaystyle \sum _{t=1}^{{\rm T}}{\displaystyle \sum _{j=1}^R\max }}(0,{\displaystyle \sum _{i=1}^{{\rm N}}(}a{}_{ij}y{}_{it}^k(l)+b{}_{ij}x{}_{it})-C{}_{jt})(14)\end{array}$

其中,G为一个足够大的数。令Fk(l)为第l次迭代第k只蚂蚁的适应值,其相应的调整矩阵为Yk(l)。Fiter(l)为第l次迭代找到的最优适应值,其相应的调整矩阵为Yiter(l);Fopt为最终找到的全局最优适应值,其相应的调整矩阵为Yopt。每次迭代后,根据如下公式进行更新:

式中,K为算法中蚂蚁的数量;L为总迭代的次数。

2.5局部搜索

由大量的关于元启发算法的文献可知,将局部搜索算法和生成初始解的机制相结合是获得高质量解的有效途径[1]。为了加快蚂蚁搜索的收敛,本文在上面得到了每一次迭代的所有蚂蚁的适应值Fiter(l)及相应的调整矩阵Yiter(l),由于调整矩阵Yiter(l)是0-1矩阵,所以我们可以通过每次改变调整矩阵中的一个值yi t(如0→1或1→0)得到新值y′i t来进行局部搜索,并根据改变后得到的调整矩阵Y′iter(l)的适应值来更新调整矩阵,以此作为下一次迭代蚂蚁的寻优方向,使得蚂蚁的寻优更准确、更迅速。具体方法如下:

Yiter(l)=[yi t]N×T,WTHX]Y′iter(l)=[y′i t]N×T

由此得到的调整矩阵就是蚂蚁进行信息素更新的方向。

2.6信息素的更新

根据上文得到的适应值和局部搜索得到的调整矩阵进行蚂蚁的信息素更新。为了防止因信息素过量累积导致蚂蚁寻优过早地收敛到局部最优解,本文采用按概率进行信息素更新的思想生成下一次迭代的信息素,即如果某次迭代中生成的随机数大于设定的概率δ,则只让信息素进行蒸发而不考虑信息素增量,否则在信息素蒸发的同时考虑信息素增量。具体实现如下。

首先令Δτ(1)i t为产品i在t时间段进行生产的信息素增量,Δτ(0)i t为产品i在t时间段不安排生产的信息素增量,c1、c2为学习因子,则信息素增量由下式计算[12]:

下一次迭代的信息素值为

其中,R(0,1)是0～1间的随机数;ρ为信息素的蒸发系数。

2.7算法流程

求解单级多资源多时段约束生产批量问题的改进蚁群算法的流程如下:

(1)确定参数。确定总迭代次数L,蚂蚁数量K,参数c0,学习因子c1、c2,信息素的重要性α,启发信息的重要性β,概率δ,信息素蒸发系数ρ。

(2)初始化。根据式(10)生成信息素矩阵的初始值,根据式(11)生成启发信息矩阵的初始值。

(3)主循环如下:

For l=1:L

For k=1:K

For i=1:N

For t=1:T

根据式(12)计算转移概率,并根据式(13)确定调整变量矩阵Yk(l)=[yki t(l)]N×T

End f or

End f or

For i=1:N

For t=1:T

根据前面确定的Yk(l)和式(8)可以得到生产批量xki t(l)

由式(9)可进一步确定Iki t(l)

End f or

End f or

由前面确定的Yk(l),Xk(l)=[xki t(l)]N×T和Ik(l)=[Iki t(l)]N×T,代入式(14)得到适应值flk

根据式(15)、式(16)更新此次迭代每只蚂蚁的最优适应值和此次迭代最优适应值

End f or

根据式(17)得到当前的全局最优适应值

For i=1:N

For t=1:T

根据式(18)进行局部搜索,得到相应的适应值,根据式(19)对调整矩阵进行更新

End f or

End f or

根据式(20)～式(23)对信息素进行更新

End f or

3 仿真实验

本文采用文献[4]和文献[7]中的单级多资源多时段约束生产批量问题的例子,使用MATLAB7.0为上文提出的算法编写程序。该例子考虑的是5个周期(T1、T2、T3、T4、T5)、5个产品以及2个资源的批量计划问题,原始数据见表1和表2。本文的改进蚁群算法的参数如下:c1=c2=180,蚂蚁的规模为K=30,最大进化代数为20。程序在运行环境为Windows Vista操作系统、CPU主频为2GHz的笔记本电脑上独立运行50次,其中运行1次的结果及其目标函数收敛曲线如图1所示,平均耗时不到1s。运行50次的结果及收敛曲线如图2所示,50次的运行结果都达到了本文的最优值,平均进化代数大约为7。

为了说明算法的有效性,本文将改进蚁群算法的计算结果与文献[4]和文献[7]中的结果进行对比,见表3。从表3可以看出,一方面本文算法能在较小的迭代次数下寻得最优解,而文献[4]和文献[7]只能寻得近优解;另一方面,本文算法的平均最优解也较文献[4,7]的平均最优解要好。为了进一步验证本文算法的有效性,本文将改进蚁群算法的计算结果与LINGO程序的求解结果进行了对比,见表4,可以看出,本文的算法和LINGO程序求解的结果一样,说明本文的改进蚁群算法求得的是最优解。因为本文的改进蚁群算法每次运行时,最大进化次数为20,平均进化7代达到最优解,所以本文的改进蚁群算法平均是140次迭代,比LINGO程序所需要的219次迭代要小,而运行时间上本文的改进蚁群算法运行50次的平均求解时间也比LINGO程序的运行时间要短。因此可以认为本文的改进蚁群算法在求解单级多时段多资源约束的生产批量问题上是可行和有效的。

4 结束语

蚁群算法作为一种模拟蚂蚁寻觅食物的仿生优化技术,已经得到了很好的应用。本文设计了一个用于求解具有多时段连续与整数混合规划问题的算法结构,并以单级多时段多资源约束的生产批量问题的模型为背景进行了应用研究,根据此类问题的特点设计了新颖的蚁群算法。该算法首先使用惩罚因子的方法对多资源约束条件进行处理,再根据文献[14,15]得到的关于单级多资源多时段约束生产批量问题的一些性质,把连续与整数混合规划生产批量问题转换为求解0-1整数生产矩阵的问题,文中算法也相应地把蚁群算法中的每只蚂蚁的寻优空间设置为0或1,最后为了提高寻优率,对得到的0-1整数生产矩阵进行变异操作进行局部搜索。通过对其他文献中的例子进行了计算并进行结果比较,结果表明,本文设计的蚁群算法在寻优方面要比退火惩罚混合遗传算法和传统的遗传算法要好,验证了所提算法的可行性和适用性。

摘要：设计了一个用于求解具有多时段连续与整数混合规划问题的算法结构,并以单级多时段多资源约束的生产批量问题(CLSP)的模型为背景进行了应用研究,根据此类问题的特点设计了新颖的蚁群算法,阐明了算法的具体实现过程。通过对其他文献中的例子进行计算和结果比较,表明提出的改进蚁群算法在寻优方面比退火惩罚混合遗传算法和传统的遗传算法要好,验证了所提算法对解决此类问题的可行性和适用性。