第1期 孟勤超，等：基于改进SPEA2算法的给水管网多目标优化设计 ·121· 1.0 足则进行下一步，否则转至2)： 0.8 7)通过选择机制选出N个非支配解，并输出 0.6 结果。 0.4 为了验证算法的性能，将RVSPEA2算法与 0.2 SPEA2、NSGA-Ⅱ和MOEA/D进行对比，用于优化 双环管网和纽约管网，其布局图分别如图3和图4 1.0 0.2 0.8 所示，其节点水压和管段长度等详细数据参照文 040.6 0.6 0.4 081000.2 献[17]。为了比较算法所得解的多样性和收敛 性，本文采用了以下3个性能指标。 图2当=3，K=3时归一化空间中的参考向量 Fig.2 Reference vectors on the normalized objective space 蓄水池210m for a three-objective problem with K=3 2.1.3关联操作 2 生成参考向量后，将种群中每个成员都关联 2 一个参考向量。首先，计算种群成员与每一个参考向量 的垂直距离，如式(13)所示。与每个成员垂直距离最 近的参考向量将与该成员相关联，如式(14)： 4 d-(q.w)=q-wTgwl (13) r(g)=w argminerd-(q,w) (14) 5 式中：q为种群成员，w为参考向量，d(q,w)代表 6 q与w的垂直距离，代表向量的模，R为参考向 7 量集合，函数argmin可计算出当目标函数 图3双环管网 d(q,w)最小时的变量值w。 Fig.3 Two-loop network 2.1.4环境选择操作 若水池300m 经过关联操作后，一个参考向量可能会有一 个或多个种群成员与之相关联，甚至没有种群成 员与之相关联1。当外部归档集Q,<W时，通过 15 ② 统计已有成员所关联的参考向量，排除这部分参 2/ ⑤ 考向量，从剩余参考向量所关联的种群成员中选 ③ 14 择成员填满外部归档集。当外部归档集Q≥ © N时，则依然通过最小距离截断算法删除个体， ④ 13 直至IQ=V。通过参考向量选择可以保证算法初 4 期优化解的多样性，避免算法陷入局部最优：而 ⑤ 在算法后期，在保证算法收敛性的同时，通过最 12 小距离截断算法，进一步提高算法的多样性。 ⊙ 17®18 2.2算法流程及性能测试 6 11 设种群大小为N,最大进化代数为T,RVSPEA2 ⑦ 算法的具体流程如下： ① 19 1)初始化种群P。和外部归档集Q。,进化代 ⑧ /10 8 数0： 四 2)合并P,和Q,为Q#1: 9 2 /20 3)计算种群Q+1中各成员的适应度； ⑦16 回 4)通过选择机制，从Q1中选出N个成员； 图4纽约管网 5)进行锦标赛选择配对、单点交叉和均匀变 Fig.4 New York Tunnels network 异操作，得到P+1 1)IGD(inverted generational distance)s 6)计算=+1，并判断算法的终止条件，若满 IGD的定义如式(15)，其中P为一组均匀分2.1.3 关联操作 生成参考向量后，将种群中每个成员都关联 一个参考向量。首先，计算种群成员与每一个参考向量 的垂直距离，如式 (13) 所示。与每个成员垂直距离最 近的参考向量将与该成员相关联，如式 (14)： d ⊥ (q,w) = q−w T qw (13) r(q) = w : argminw∈Rd ⊥ (q,w) (14) d ⊥ (q,w) ∥·∥ d ⊥ (q,w) 式中：q 为种群成员，w 为参考向量， 代表 q 与 w 的垂直距离， 代表向量的模，R 为参考向 量集合，函 数 argmi n 可计算出当目标函数 最小时的变量值 w。 2.1.4 环境选择操作 经过关联操作后，一个参考向量可能会有一 个或多个种群成员与之相关联，甚至没有种群成 员与之相关联[16]。当外部归档集|Qt |<N 时，通过 统计已有成员所关联的参考向量，排除这部分参 考向量，从剩余参考向量所关联的种群成员中选 择成员填满外部归档集。当外部归档集|Qt |≥ N 时，则依然通过最小距离截断算法删除个体[6] ， 直至|Qt |=N。通过参考向量选择可以保证算法初 期优化解的多样性，避免算法陷入局部最优；而 在算法后期，在保证算法收敛性的同时，通过最 小距离截断算法，进一步提高算法的多样性。 2.2 算法流程及性能测试 设种群大小为 N，最大进化代数为 T，RVSPEA2 算法的具体流程如下： 1) 初始化种群 P0 和外部归档集 Q0，进化代 数 t=0； 2) 合并 Pt 和 Qt 为 Qt+1； 3) 计算种群 Qt+1 中各成员的适应度； 4) 通过选择机制，从 Qt+1 中选出 N 个成员； 5) 进行锦标赛选择配对、单点交叉和均匀变 异操作，得到 Pt+1； 6) 计算 t=t+1，并判断算法的终止条件，若满 足则进行下一步，否则转至 2)； 7) 通过选择机制选出 N 个非支配解，并输出 结果。 为了验证算法的性能，将 RVSPEA2 算法与 SPEA2、NSGA-II 和 MOEA/D 进行对比，用于优化 双环管网和纽约管网，其布局图分别如图 3 和图 4 所示，其节点水压和管段长度等详细数据参照文 献 [17]。为了比较算法所得解的多样性和收敛 性，本文采用了以下 3 个性能指标。 3 7 6 2 1 1 8 5 7 3 2 4 6 5 4 㧰Ⅰ↌ 210 m 图 3 双环管网 Fig. 3 Two-loop network 3 6 7 1 2 1 8 5 7 3 2 4 6 4 5 㧰Ⅰ↌ 300 m 8 9 10 17 11 12 13 14 15 16 20 18 19 9 10 11 12 13 14 15 16 21 19 20 17 18 图 4 纽约管网 Fig. 4 New York Tunnels network 1) IGD(inverted generational distance)[18] IGD 的定义如式 (15)，其中 P *为一组均匀分 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 f2 f1 f3 图 2 当 m=3，K=3 时归一化空间中的参考向量 Fig. 2 Reference vectors on the normalized objective space for a three-objective problem with K=3 第 1 期 孟勤超，等：基于改进 SPEA2 算法的给水管网多目标优化设计 ·121·