﻿ 基于改进SPEA2算法的给水管网多目标优化设计
«上一篇
 文章快速检索 高级检索

 智能系统学报  2018, Vol. 13 Issue (1): 118-124  DOI: 10.11992/tis.201701012 0

### 引用本文

MENG Qinchao, YANG Cuili, QIAO Junfei. Multi-objective optimization design of water distribution systems based on improved SPEA2 algorithm[J]. CAAI Transactions on Intelligent Systems, 2018, 13(1), 118-124. DOI: 10.11992/tis.201701012.

### 文章历史

1. 北京工业大学 信息学部，北京 100124;
2. 北京工业大学 计算智能与智能系统北京市重点实验室，北京 100124

Multi-objective optimization design of water distribution systems based on improved SPEA2 algorithm
MENG Qinchao1,2, YANG Cuili1,2, QIAO Junfei1,2
1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China;
2. Beijing Key Laboratory of Computational Intelligence and Intelligence System, Beijing University of Technology, Beijing 100124, China
Abstract: To solve the multi-objective optimization problem in water distribution system design, we consider three objective functions-the cost of the pipe network and the sum and variance of the node surplus head. Then, we optimize the water distribution system in terms of economy and reliability. To obtain well-diversified and well-convergent solutions, we combine the concepts of domination and decomposition and introduce reference vectors into the Strength Pareto Evolutionary Algorithm 2 (SPEA2). The diversity and convergence of the algorithm are increased by the use of the domination strength-based solutions selection method. We use the proposed algorithm to optimize the two-loop network and the New York Tunnels network, and the simulation results demonstrate its effectiveness in realizing the multi-objective optimization of water distribution systems design. Finally, we apply the algorithm to actual pipe network construction.
Key words: water distribution system    multi-objective optimization    strength Pareto evolutionary algorithm 2    reference vectors    economy    reliability    two-loop network    New York tunnels network

1 给水管网优化模型描述

1.1 目标函数

 $Z = \sum\limits_{j = 1}^P {{C_j}\left( {{D_j}} \right){L_j}} ,j = 1,2, \cdots \! ,P$ (1)

 ${I_{si}} = {H_i} - {H_{\min }},i = 1,2, \cdots \! ,I$ (2)

 ${I_s} = \sum\limits_{i = 1}^I {\left( {{H_i} - {H_{\min }} } \right)}$ (3)

 $\overline {{I_s}} = \frac{{{I_{s1}} + {I_{s2}} + \cdots + {I_{sI}}}}{I}$ (4)

 $S = \sum\limits_{i = 1}^I {{{\left( {{I_{si}} - \overline {{I_s}} } \right)}^2}} ,i = 1,2, \cdots \! ,I$ (5)

 $\left\{ \begin{array}{l}\min Z = \sum\limits_{j = 1}^P {{C_j}\left( {{D_j}} \right){L_j}} ,j = 1,2, \cdots \! ,P\\\min Is = \sum\limits_{i = 1}^I {\left( {{H_i} - {H_{\min }}} \right),i = 1,2, \cdots \! ,I} \\\min S = \sum\limits_{i = 1}^I {{{\left( {{I_{si}} - \overline {{I_s}} } \right)}^2}} ,i = 1,2, \cdots \! ,I\end{array} \right.$ (6)

1.2 约束条件

1) 节点流量连续性约束

 ${\mathit{\boldsymbol{Ag}}} + G = 0$ (7)

2) 能量平衡约束

 $\sum\limits_{k \in {\rm{Loop }}l} {\Delta {H_k} = 0} , \; \forall l \in L$ (8)

3) 节点流量连续性约束

 ${H_{\min }} \leqslant {H_i} \leqslant {H_{\max }}$ (9)

4) 能量平衡约束

 ${D_j} \in \left\{ {{D_1},{D_2}, \cdots \! ,{D_m}} \right\}$ (10)

2 基于参考向量的强度帕累托进化算法RVSPEA2

2.1 基于参考向量的选择机制

2.1.1 自适应目标归一化

 ${f'_{i,j}}({\mathit{\boldsymbol{x}}}) = \frac{{{f_{i,j}}({\mathit{\boldsymbol{x}}}) - f_{i,j}^{\min }}}{{f_{i,j}^{\max } - f_{i,j}^{\min }}}$ (11)

2.1.2 参考向量的生成

 $K = \left\lfloor {\sqrt[m]{N} + 0.5} \right\rfloor$ (12)

2.1.3 关联操作

 ${d^ \bot }({\mathit{\boldsymbol{q}}},{\mathit{\boldsymbol{w}}}) = \left\| {{\mathit{\boldsymbol{q}}} - {{\mathit{\boldsymbol{w}}}^{\rm{T}}}{\mathit{\boldsymbol{qw}}}} \right\|$ (13)
 $r({\mathit{\boldsymbol{q}}}) = {\mathit{\boldsymbol{w}}}:{\rm{argmi}}{{\rm{n}}_{{\mathit{\boldsymbol{w}}} \in {R}}}{d^ \bot }({\mathit{\boldsymbol{q}}},{\mathit{\boldsymbol{w}}})$ (14)
 Download: 图 1 当m=3，K=3时归一化空间中的27个参考点 Fig. 1 Twenty-seven reference points on the normalized objective space for a three-objective problem with K=3
 Download: 图 2 当m=3，K=3时归一化空间中的参考向量 Fig. 2 Reference vectors on the normalized objective space for a three-objective problem with K=3

2.1.4 环境选择操作

2.2 算法流程及性能测试

1) 初始化种群P0和外部归档集Q0，进化代数t=0；

2) 合并PtQtQt+1

3) 计算种群Qt+1中各成员的适应度；

4) 通过选择机制，从Qt+1中选出N个成员；

5) 进行锦标赛选择配对、单点交叉和均匀变异操作，得到Pt+1

6) 计算t=t+1，并判断算法的终止条件，若满足则进行下一步，否则转至2)；

7) 通过选择机制选出N个非支配解，并输出结果。

1) IGD(inverted generational distance)[18]

IGD的定义如式(15)，其中P*为一组均匀分布在Pareto前沿上的解，P为算法所求得的非支配解，d(x, P)代表解xP中解的最小欧式距离。如果P*中解的数量足够多，IGD在一定程度上能同时反映解的多样性和收敛性。IGD的值越小，算法所得解的多样性和收敛性越好。

 ${\rm{IGD}}({P^ * },P) = \frac{{\sum\limits_{x \in {P^ * }} {d(x,P)} }}{{\left| {{P^ * }} \right|}}$ (15)

2) GD(generational distance)[19]

GD的定义如式(16)所示，其用于计算非支配解与Pareto前沿之间的距离。GD的值越小，算法所得解的收敛性越好。

 ${\rm{GD}}(P,{P^ * }) = \frac{{\sqrt {\sum\limits_{x \in P} {d{{(x,{P^ * })}^2}} } }}{{\left| P \right|}}$ (16)

3) SP(spacing)[20]

SP用于计算非支配解中相邻解之间距离的方差，其公式如式(17)：

 ${\rm{SP}} = \sqrt {\frac{1}{{n - 1}}\sum\limits_{i = 1}^n {{{\left( {\bar d - {d_i}} \right)}^2}} }$ (17)
 ${d_i} = \min \left( {\sum\limits_{k = 1}^m {\left| {f_k^i\left( x \right) - f_k^j\left( x \right)} \right|} } \right),\;{\rm{ }}i,j = 1,2, \cdots \! ,n$ (18)

3 工程实例