您好, 访客   登录/注册

基于分解的混合多目标进化算法在供水调度系统中的应用

来源:用户上传      作者: 赵晶晶 许峰

  摘 要:建立了供水调度模型,利用基于分解的多目标进化算法,首先将供水调度问题分解为若干单目标,然后根据分布估计的思想对各个单目标建立概率模型,通过采样产生新的个体。利用非支配排序法进行选择,得到最优解。实验表明,该算法对求解供水调度优化问题具有较好的多样性和均匀性,并且降低了算法的计算复杂度。
  关键词:供水调度问题;进化算法;分解策略;分布估计
  中图分类号:TP312 文献标识码:A 文章编号:16727800(2013)002002703
  0 引言
  供水调度问题的研究有着非常大意义,它不仅关系到居民的生活质量,而且对工业的发展也起着重要的作用,因此对供水调度系统的要求也越来越高。对供水系统而言,其主要运行成本为供水泵站的能量费用和由于频繁开关水泵而早成的水泵磨损的维护费用。另外,在满足最低的运行成本之外,还需要维持一定的压力服务水平来保证居民的正常生活与社会生产。供水泵站的优化调度是要实现能量费用和维护费用的最小化,以及水压服务水平的最大化。
  本文利用一种基于分布的分解多目标进化算法,先将供水调度问题分解为若干单目标,然后根据分布估计的思想对各个单目标建立概率模型,通过采样产生解。通过这种方法所得解不仅具有较好的多样性和均匀性,而且明显降低了计算复杂。
  1 供水调度系统问题及模型
  在供水调度问题中,在T时间内需要N个水泵。该问题是主要目标是在满足作业约束的条件下,最小化水供应的成本,即能量费用和维护费用,并要最大化水压服务水平,以保证居民的正常生活和工业的正常运行。
  根据对用水量的趋势预测,将一天的24小时化为几个调度时段,使用基于分布估计的分解多目标进化算法来求解供水调度优化问题。实践表明,使用这种方法求解供水调度问题可以在保持解的均匀性与多样性的条件下能够很好降低计算复杂度。
  1.1 制水费用和电力费用f1=∑Jj=1∑Ii=1Si,jQi,j+
  ∑Jj=1∑Ii=1C・NPk,j・QPk,j・HPk,jαk,j・SPk,j
  (1) 其中,J为供水调度期内划分的时段数,I为水源泵站数,C为换算系数,Si,j为第i泵站第j时段的单位制水费用,单位为元/m3,Qi,j为第i泵站第j时段的水流量,SPk,j为水泵k在第j时段的单位电费,NPk,j为水泵k在第j时段的开启状态,其中令开为1,关为0,HPk,j为水泵k在第j时段的出口压力,QPk,j为水泵k在第j时段的供水量,αk,j为水泵k在第j时段的计算效率,K为泵站内的水泵的总数。
  1.2 水泵的维护费用
  水泵的维护费用主要来源为水泵频繁开关而造成磨损,而这很难以量化。这里假设维护费用是随着开关次数的增加而增长,所以就用水泵的开关次数来代替水泵的维护成本。水泵的开关次数如(2)式表示:f2=∑Jj=1∑Kk=1max{0,NPk,j-NPk,(j-1)}
  (2)1.3 水压服务水平
  在供水调度系统中,供水管网各节点在满足水压最低服务水平的前提下,需要维持一定的压力服务水平。因为水压过低会影响居民的正常生活和工业的正常运行,但是如果水压过高就会造成不必要的浪费甚至会造成曝管,会很大程度上提高供水调度系统的运行费用。水压服务Φ(i,t)指标如下所示:
  Φ(i,t)=Pa(i,t)-PminPr(i,t)-Pmin1/2if Pmin≤Pa(i,t)≤Pr(i,t)
  (3)
  Φ(i,t)=0 otherwise
  (4)
  f3=∑Jt-1∑Ni=1Φ(i,t)
  (5) 其中,Pr(i,t)为第i节点在t时段的最大允许水压;Pa(i,t)为第i节点在t时段的实际水压。
  因为对供水管网而言,既要保证泵站运行费用和维护费用的最低,又要保证水压服务水平的最大化。但这两者不可能同时达到最优,供水调度优化模型就是要实现这二者的平衡。
  所以供水调度优化目标为:min(f1,f2) and maxf3
  (6)将以上问题综合为多目标优化问题:y=F(x)=(f1(x), f2(x), f3(x))
  (7) 约束条件有以下几点:
  (1)满足管网水力平衡的方程组:g(P,q,r)=0
  (8) 式中, P表示节点的压力向量,q表示节点的流量向量,r表示管段比阻。
  (2)泵站在时段内的供水能力限制:Qp,t≤Qmaxp,t
  (9) (3)压力控制点的供水压力要求:Pmin(i,t)≤Pc(i,t)≤Pmax(i,t),i=1,2,…,NN
  (10) 式中,Pmin(i,t)为最低的运行的服务水龙头,Pc(i,t)为第i压力控制节点t时刻的实际供水压力,Pmax(i,t)为允许承受的最高水压, NN为压力控制点数。
  (4)水泵的调速比范围:
  nimin≤ni≤nimax
  (11)
  2 求解供水调度问题的多目标遗传算法
  (1)染色体编码。在泵站的优化调度中,水泵的开关为离散型变量,而变速泵的转速比和调速频率是连续的变量,在这里使用二进制编码将其离散化。对于变频调速泵,将频率转化为调速比。
  (2)分解操作。计算每两个权重之间的欧几里得距离,为每个权向量选出最近的T个向量作为它的邻居,并将这T个权向量所控制的群体组成子种群。此时便将多目标问题转换为单目标问题。
  (3)建模操作。如何建立概率模型方法很重要,因为是根据模型选择适当的采样产生新的个体。所以概率模型的建立直接影响算法的效率和解的分布性与多样性。而一个号的模型应该具有容易构建,采样方便并且能够指导种群进化等特征。本文首先利用(m-1)维局部主分量分析法划分种群,使用聚类后的结果来建立PS流形结构的概率模型。   (4)采样操作。传统的多目标进化算法利用交叉变异等遗传操作产生新的种群,在本文中,利用蒙特卡罗方法,对概率模型高斯采样获得新个体。因为高斯噪声采样具有旋转不变性,平移不变性,线性不变性和尺度不变性等,在求解多目标问题上占有很大优势。
  (5)选择操作。采用NSGAⅡ的非支配排序的选择操作。这种操作是一种最优个体保留机制并且有效的保持群体的分布性和多样性的选择方式。这里需要构造偏序集和计算聚集距离。
  偏序集就是将父代种群与子带种群的集合P∪Q依据个体之间的Pareto支配关系划分为互不相交的m层Pareto前沿面F1,F2,…,Fm,并满足一下条件:①∪F∈{F1,F2,…,Fm}F=P∪Q;②i,j∈{1,2,…,m}且i≠j,Fi∪Fj=φ;③F1F2…Fm,Fk+1中的解集直接受Fk的解集支配(k=1,2,…,m-1)。
  聚集距离的大小与种群的分布性与多样性有着直接的关系,通常情况下回保留聚集密度小的个体,个体的聚集距离是通过计算与其相邻的两个个体子目标上距离差的和来求得。
  3 实现供水调度问题的多目标遗传算法过程
  算法的具体步骤如下:
  (1)产生N个初始群体P(t),初始化外部种群,设置初始值。
  (2)分解种群。计算每两个权向量之间的欧几里得距离,为每个权向量选出最接近的T个权向量。由这T个权向量控制的个体组成子群体。
  (3)建立模型。根据分解的子群体建立概率模型,并根据此概率模型得到新的样本。
  (4)将将父代种群与子带种群的集合依据个体之间的Pareto支配关系划分为互不相交的m层,并计算聚集距离。每次去除一个聚集密度高的个体,然后重新计算修剪后种群的个体的聚集距离。
  (5)满足终止准则,则停止;否则P(t)=P(t+1),返回步骤(2)。
  4 实例与分析
  采用改进的基于分布估计的多目标进化算法与水利模拟相结合,对下面的实例进行计算来验证这种方法的优化性能。
  假设某供水系统各水泵的制水费用、电力费用等参数如下表。最小水头25m,最大水头32m。日用水量预测曲线见图1。
  仿真程序用Matlab编制,种群规模为100,交叉概率为0.90,变异概率0.1。图2和图3中给出了某次的典型优化结果。
  参考文献:
  \[1\] 郑金华.多目标进化算法及其应用\[M\].北京:科学出版社,2007.
  \[2\] 吕谋,张士乔,赵洪滨.大规模供水系统直接优化调度法\[J\].水利学报,2011(1).
  \[3\] IVALERMIR B CARRIJO, LUISA FERNANDA REIS R, GODFREY A WALTERS, et al. Operational optimization of WDS based on multiobjective genetic algorithm and operational extraction rules using date mining\[C\]. World Water and Environmental Resources Congress,2004.
  \[4\] G SYSWERDA. Uniform crossover in genetic algorithms\[C\]. Proceedings of The Third International Conference on Genetic Algorithms,1989.
  \[5\] ZHANG QF, LI H. MOEAD: A multiobjective evolutionary algorithm based on decomposition. IEEE trans\[C\]. on Evolutionary Computation,2007(6).
  \[6\] ZHANG QF, ZHOU AM, JIN Y. RMMEDA: A regularity model based multiobjective estimation of distribution algorithm. IEEE trans\[C\]. Evolutionary Computation,2007(1).
  \[7\] LAUMANNS M, OCENASEK J. Bayesian optimization algorithms for multiobjective optimization\[C\]. The 7th Int’l Conf. on Parallel Problem Solving from Nature London: SpringerVerlag,2002.
  \[8\] KHAN N, GOLDBERG DE, PELIKAN M. Multiobjective bayesian optimization algorithm technical report, No. 2002009\[R\]. University of Illinois at UrbanaChampaign,2002.
  \[9\] DEB K, An efficient constraint handing method for genetic algorithms\[J\]. Compute methods Appl. Mech. Eng,2000(2).
  \[10\] ZHOU AM, ZHANG QF, JIN Y, SENDHOFF B, TSANG E. Global multiobjective optimization via estimation of distribution algorithm with biased initialization and crossover\[C\]. The Genetic and Evolutionary Computation Conf, GECCO 2007. New York: ACM Press,2007.
  \[11\] 赵晶晶,许峰.基于分布估计的分解多目标进化算法\[J\].软件导刊,2012(10).
  (责任编辑:余 晓)
转载注明来源:https://www.xzbu.com/8/view-6042720.htm