ｈ　ｔｅａｍ　ｓｙｓｔｅｍａｔｉｃａｌｌｙ　ｄｅｓｃｒｉｂｅ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｓ　ｆｒｏｍ　ｔｗｏ　ａｓｐｅｃｔｓ：ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔｔｉｎｇ　ｍｅｔｈｏｄｓ　ａｎｄ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ．Ｉｎ　ｔｈｅ　ｓｅｔｔｉｎｇ　ｏｆ　ｐｒｅｆｅｒｅｎｃｅｓ，ｗｅ　ｓｕｍｍａｒｉｚｅ　ｔｈｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｉｎｃｏｒｐｏｒａｔｉｎｇｐｒｅｆｅｒｅｎｃｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｒｏｍ　ｔｈｅ　ｆｏｕｒ　ａｓｐｅｃｔｓ：ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎｓｈｉｐ，ａｎｇｌｅ　ｒｅｌａｔｉｏｎｓｈｉｐ，ｗｅｉｇｈｔｖｅｃｔｏｒ　ａｎｄ　ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔ．Ｆｉｒｓｔｌｙ，ｗｅ　ｓｕｍｍａｒｉｚｅ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎｓｈｉｐ．Ｔｈｅ　ｃｏｒｅ　ｉｄｅａ　ｂｅｈｉｎｄ　ｉｔ　ｉｓ　ｔｏ　ｍｏｄｉｆｙ　ｔｈｅ　Ｐａｒｅｔｏｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎｓｈｉｐ，ｅｎｈａｎｃｅ　ｔｈｅ　ｓｅｌｅｃｔｉｏｎ　ｐｒｅｓｓｕｒｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｇｕｉｄｅ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓｔｏ　ｑｕｉｃｋｌｙ　ｃｏｎｖｅｒｇｅ　ｔｏ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｒｅｇｉｏｎ．Ｓｅｃｏｎｄｌｙ，ｗｅ　ｓｕｍｍａｒｉｚｅ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃ－ｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ａｎｇｌｅ　ｒｅｌａｔｉｏｎｓｈｉｐ．Ｔｈｅ　ｃｏｒｅ　ｉｄｅａ　ｉｓ　ｔｏ　ｕｓｅ　ｔｈｅ　ａｎｇｌｅｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｓｏｌｕｔｉｏｎｓ　ｔｏ　ｇｕｉｄｅ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ，ｗｈｉｌｅ　ｕｓｉｎｇ　ｔｈｅ　ａｎｇｌｅｔｏ　ｃｏｎｔｒｏｌ　ｔｈｅ　ｒａｎｇｅ　ｏｆ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｒｅｇｉｏｎ　ｔｏ　ｏｂｔａｉｎ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｓｏｌｕｔｉｏｎｓ．Ｔｈｉｒｄｌｙ，ｗｅ　ｓｕｍ－ｍａｒｉｚｅ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｗｅｉｇｈｔ　ｖｅｃｔｏｒ．Ｔｈｅ　ｃｏｒｅｉｄｅａ　ｉｓ　ｔｏ　ｔｒａｎｓｆｏｒｍ　ｔｈｅ　ｄｅｃｉｓｉｏｎ－ｍａｋｅｒ’ｓ　ｐｒｅｆｅｒｅｎｃｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｎｔｏ　ａ　ｓｅｔ　ｏｆ　ｗｅｉｇｈｔ　ｖｅｃｔｏｒｓｃａｒｒｙｉｎｇ　ｐｒｅｆｅｒｅｎｃｅ　ｉｎｆｏｒｍａｔｉｏｎ，ａｎｄ　ｔｈｅｎ　ｄｅｃｏｍｐｏｓｅ　ｔｈｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｉｎｔｏ　ｓｅｖｅｒａｌ　ｓｉｎｇｌｅ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｓｕｂ－ｐｒｏｂｌｅｍｓ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｗｅｉｇｈｔ　ｖｅｃｔｏｒｓ．Ｗｅ　ｌａｓｔｌｙｉｎｔｒｏｄｕｃｅ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔｓ．Ｔｈｅｃｏｒｅ　ｉｄｅａ　ｉｓ　ｃｏｅｖｏｌｖｉｎｇ　ａ　ｓｅｔ　ｏｆ　ｒａｎｄｏｍｌｙ　ｇｅｎｅｒａｔｅｄ　ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔｓ　ｔｏｇｅｔｈｅｒ　ｗｉｔｈ　ｐｏｐｕｌａｔｉｏｎ．Ｔｈｅｎ，ｉｎ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｅｒｆｏｒｍａｎｃｅ，ｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｐｒｅｆｅｒｅｎｃｅ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅｓｅｌｅｃｔｅｄ　ｆｒｏｍ　ｅａｃｈ　ｏｆ　ｔｈｅ　ｆｏｕｒ　ｍｅｔｈｏｄｓ　ｔｏ　ｐｅｒｆｏｒｍ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔｓ．Ｉｎ　ａｄｄｉｔｉｏｎ，ｉｎ　ｏｒｄｅｒｔｏ　ｖｅｒｉｆｙ　ｔｈｅ　ｒｏｂｕｓｔｎｅｓｓ　ｏｆ　ｔｈｅ　ｅｉｇｈｔ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｄｉｆｆｅｒｅｎｔ　ｐｒｅｆｅｒｅｎｃｅ　ｒｅｇｉｏｎｓ．Ｏｕｒ　ｒｅｓｅａｒｃｈ　ｔｅａｍｓｅｌｅｃｔ　ｔｗｏ　ｄｉｆｆｅｒｅｎｔ　ｒｅｆｅｒｅｎｃｅ　ｐｏｉｎｔｓ　ｉｎ　ｔｈｅ　ｆｅａｓｉｂｌｅ　ｒｅｇｉｏｎ　ａｎｄ　ｔｈｅ　ｉｎｆｅａｓｉｂｌｅ　ｒｅｇｉｏｎ　ｆｏｒ　ｅｘｐｅｒｉｍｅｎｔａｌｃｏｍｐａｒｉｓｏｎ．Ｎｅｘｔ，ｗｅ　ｃａｒｒｙ　ｏｕｔ　ａ　ｓｙｓｔｅｍａｔｉｃ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｅｉｇｈｔ　ａｌｇｏｒｉｔｈｍｓ　ｆｒｏｍ　ｔｈｒｅｅａｓｐｅｃｔｓ：ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｓｔｒａｔｅｇｙ，ｔｈｅ　ｏｖｅｒａｌｌ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ｓｅｔ，ａｓ　ｗｅｌｌ　ａｓ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ａｎａｌｙｚｅｄ　ｔｈｅｉｒ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ　ｉｎｄｅｐｔｈ．Ｆｉｎａｌｌｙ，ｏｕｒ　ｒｅｓｅａｒｃｈ　ｔｅａｍ　ｅｎｄ　ｕｐ　ｗｉｔｈ　ｄｉｓｃｕｓｓｉｎｇ　ｓｏｍｅ　ｐｏｔｅｎｔｉａｌ　ｔｒｅｎｄｓ　ｉｎ　ｐｒｅｆｅｒｅｎｃｅ－ｂａｓｅｄ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ’ｆｕｔｕｒｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｆｒｏｍ　ｔｈｅ　ｓｉｘ　ａｓｐｅｃｔｓ：ｐｒｅｆｅｒｅｎｃｅｉｎｆｏｒｍａｔｉｏｎ　ｃｏｎｖｅｒｓｉｏｎ， ｐｒｅｆｅｒｅｎｃｅ　ｌｅａｒｎｉｎｇ，ｉｍｐｌｉｃｉｔ　ｐｒｅｆｅｒｅｎｃｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ， ｐｅｒｆｏｒｍａｎｃｅｉｎｄｉｃａｔｏｒｓ　ｏｆ　ｐｒｅｆｅｒｅｎｃｅ　ａｌｇｏｒｉｔｈｍｓ，ｖｉｓｕａｌｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ　ａｎｄ　ｐｒａｃｔｉｃａｌ　ａｐｐｌｉｃａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ　 ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔｔｉｎｇ；ｄｏｍｉｎａｎｃｅ　ｒｅｌａｔｉｏｎｓｈｉｐ；ａｎｇｌｅｒｅｌａｔｉｏｎｓｈｉｐ；ｗｅｉｇｈｔ　ｖｅｃｔｏｒ；ｐｒｅｆｅｒｅｎｃｅ　ｓｅｔ１　引　言在科学研究和实际应用中通常存在多个目标同时 优 化 的 问 题，这 些 问 题 称 为 多 目 标 优 化 问 题ＭＯＰｓ（Ｍｕｌｔｉ－Ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍｓ）．ＭＯＰｓ的最优解并不是单个的最优解，而是一组由Ｐａｒｅｔｏ最 优 解 组成的最 优 解 集合［１］．现 阶 段 求 解ＭＯＰｓ的主要方法是多目标进化算法（Ｍｕｌｔｉ－ＯｂｊｅｃｔｉｖｅＥｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍｓ，ＭＯＥＡｓ）．根据进化机制的不同，又可以将 ＭＯＥＡｓ分为以下三类：（１）基于支配关系的 ＭＯＥＡｓ，其基本思想是利用基于 Ｐａｒｅｔｏ的适应度分配策略，从当前种群中找出所有非支配个体．Ｄｅｂ等人［２］提出的 ＮＳＧＡ－ＩＩ（Ｎｏｎ－ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ－ＩＩ）、Ｚｉｔｚｌｅｒ等人［３］提出的 ＳＰＥＡ２（Ｓｔｒｅｎｇｔｈ　Ｐａｒｅｔｏ　ＥｖｏｌｕｔｉｏｎａｒｙＡｌｇｏｒｉｔｈｍ　２）和 Ｃｏｒｎｅ 等 人［４］提 出 的 ＰＥＳＡ－ＩＩ（Ｐａｒｅｔｏ　Ｅｎｖｅｌｏｐ－ｂａｓｅｄ　Ｓｅｌｅｃｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ－ＩＩ）是该类算法的三种典型代表．然而传统 Ｐａｒｅｔｏ支配关系随目标维度的增加而迅速恶化，通过修改 Ｐａｒｅｔｏ支配关系能有效增强对个体的选择压力．Ｌａｕｍａｎｎｓ等人［５］提出的ε－支配通过修正因子ε来修改 Ｐａｒｅｔｏ支配关系；Ｐｉｅｒｒｏ等人［６］提出用优先排序方法取代了传统的非 支 配 排 序 方 法；Ｗａｎｇ 等 人［７］和 Ｈｅ等２１０９ 计　　算　　机　　学　　报 ２０１９年支配关系设计新的排序策略；Ｙａｎｇ等 人［９］提 出 基 于 网 格 的 进 化 算 法 （Ｇｒｉｄ－ｂａｓｅｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ，ＧｒＥＡ），通 过 调 整网格大小来 选 择 优 先 级 较 高 的 非 支 配 解；Ａｎｔｏｎｉｏ等人［１０］通过交替使用收益函数和ε－支配方法来提高算法性能；Ｌｉ等人［１１］提 出基 于 偏 移 的 密 度 估 计策略，对算法中的多样性维持机制进行改进，使基于Ｐａｒｅｔｏ支配的算法更适用于求解 ＭＯＰｓ；Ｃｈｅｎｇ等人［１２］通 过 引 入 ＤＤ（Ｄｉｒｅｃｔｉｏｎａｌ　Ｄｉｖｅｒｓｉｔｙ）和 ＦＣ（Ｆａｖｏｒａｂｌｅ　Ｃｏｎｖｅｒｇｅｎｃｅ）指标来衡量算法的收敛性和多样性，在交叉变异阶段，将ＦＣ指标与 Ｐａｒｅｔｏ支配方法相结合以提高算法的收敛性，在选择阶段，提出一种多样性维持策略以平衡算法的多样性和收敛性．最近，学者们提出在支配关系的基础上引入偏好信息以提高算法的选择压力，如 Ｗａｎｇ等人［１３］提出的基于目标向量偏好集协同进化算法（Ｐｒｅｆｅｒｅｎｃｅ－Ｉｎｓｐｉｒｅｄ　Ｃｏ－ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　Ｕｓｉｎｇ　Ａｄａｐ－ｔｉｖｅｌｙ　Ｇｅｎｅｒａｔｅｄ　Ｇｏａｌ　Ｖｅｃｔｏｒｓ，ＰＩＣＥＡ－ｇ）和 Ｚｈａｎｇ等人［１４］提出的基于 Ｋｎｅｅ点驱动的进化算法（ＫｎｅｅＰｏｉｎｔ　Ｄｒｉｖｅｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ，ＫｎＥＡ）等．（２）基于指标的 ＭＯＥＡｓ，其基本思想是使用性能评价 指 标 来 引 导 搜 索 过 程 和 对 解 的 选 择 过 程．ＩＢＥＡ（Ｉｎｄｉｃａｔｏｒ－Ｂａｓｅｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ）［１５］、ＨｙｐＥ（Ｈｙｐｅｒｖｏｌｕｍｅ　Ｂａｓｅｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ）［１６］和 ＳＭＳ－ＥＭＯＡ（Ｓ－Ｍｅｔｒｉｃ　Ｓｅｌｅｃｔｉｏｎ　Ｂａｓｅｄ　Ｅｖｏｌｕ－ｔｉｏｎａｒｙ　Ｍｕｌｔｉ－Ｏｂｊｅｃｔｉｖｅ　Ａｌｇｏｒｉｔｈｍ）［１７］是三种 广 泛使用的该类算法．ＩＢＥＡ 是一种基于评价指标的算法框架，可 以 与 任 意 指 标 相 结 合，而 ＳＭＳ－ＥＭＯＡ和 ＨｙｐＥ 则 是 利 用 超 体 积 值 对 个 体 进 行 选 择．Ｇｅｒｓｔｌ等人［１８］提 出 一 种 基 于 Δｐ 指 标 的 算 法 （Δｐｉｎｄｉｃａｔｏｒ－ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ，Δｐ－ＥＭＯＡ），其 中 Δｐ为近似解集与真实 Ｐａｒｅｔｏ前沿间的 Ｈａｕｓｄｏｒｆｆ距离；Ｖｉｌｌａｌｏｂｏｓ和 Ｃｏｅｌｌｏ［１９］将 Δｐ 指标与差 分 进 化相结合，以解决１０维的 ＭＯＰｓ；Ｌｏｐｅｚ等人［２０］提出ＩＧＤ＋－ＥＭＯＡ（Ｉｎｖｅｒｓｅ　Ｇｅｎｅｒａｔｉｏｎａｌ　Ｄｉｓｔａｎｃｅ　ＰｌｕｓＥｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ）算法，通过建立参考集以评估搜索过程中得到的解的质量．（３）基于分解的 ＭＯＥＡｓ，其基本思想是将复杂的 ＭＯＰ 分 解 为 单 目 标 子 问 题 （Ｓｉｎｇｌｅ－ＯｂｊｅｃｔｉｖｅＰｒｏｂｌｅｍｓ，ＳＯＰｓ）或多个简单的 ＭＯＰｓ进行求解．Ｚｈａｎｇ等人［２１］将传统的数学规划方法与进化算法相结合提出基于分解的 ＭＯＥＡ／Ｄ（Ｍｕｌｔｉ－ＯｂｊｅｃｔｉｖｅＥｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）算法；在此 基 础 上，众 多 学 者 对 ＭＯＥＡ／Ｄ 进 行 改进，提 出 许 多 ＭＯＥＡ／Ｄ 的 改 进 算 法［２２－２５］；此 外，Ｃｈｅｎｇ等 人［２６］提 出 的 ＲＶＥＡ （Ｒｅｆｅｒｅｎｃｅ　Ｖｅｃｔｏｒｇｕｉｄｅｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ）算 法 也 是 通 过 将ＭＯＰ分解为多个ＳＯＰｓ进行求解．Ｌｉｕ等人［２７］提出的 ＭＯＥＡ／Ｄ－Ｍ２Ｍ （Ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｏｆ　ａ　Ｍｕｌｔｉｏｂ－ｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍ　ｉｎｔｏ　ａ　Ｎｕｍｂｅｒ　ｏｆＳｉｍｐｌｅ　Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　Ｓｕｂｐｒｏｂｌｅｍｓ）算 法 将 整 个目标空间划分为若干子区域从而进行求解；Ｄｅｂ等人［２８］提 出 的 ＮＳＧＡ－ＩＩＩ（Ａｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｍａｎｙ－Ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｕｓｉｎｇ　Ｒｅｆｅｒｅｎｃｅ－ｐｏｉｎｔ　Ｂａｓｅｄ　Ｎｏｎ－ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ａｐｐｒｏａｃｈ）算法，将 ＮＳＧＡ－ＩＩ中的非支配分层机制和 ＭＯＥＡ／Ｄ中的分解机制相结合，避免了 Ｐａｒｅｔｏ支配带来的退化问题，同时保证种群的多样性．随着目标维度的增加，传统 ＭＯＥＡｓ的搜索机制迅速陷入瓶颈，算法性能急剧下降，使其面临极大的挑战［２９］：（１）逼近整个 Ｐａｒｅｔｏ前沿所需解的数量呈指数级增长，使 得算法的 计 算复杂度 明 显增大；（２）种群中非支配解的比例急剧增长，严重削弱了传统 Ｐａｒｅｔｏ支配关系对种群的选择压力，导致算法的收敛性能严重恶化；（３）增加了解集可视化的难度，使得决策者（Ｄｅｃｉｓｉｏｎ　Ｍａｋｅｒ，ＤＭ）难以从大量的非支配解中选择其满意的最优解．针对传统 ＭＯＥＡｓ求解高维目标问题面临的诸多困难，学者们提出了许多改进方法：（１）降低目标维度．Ｚｈｏｕ等人［３０］和 Ｚｉｔｚｌｅｒ等人［３１］都通过删除冗余目标的方法以达到目标降维的目的．Ｍｕｒａｔａ等人［３２］运用目 标 函数加权 法对冗余目标进行加权，可 有效防 止 重要信息 的 丢失．然而，目标降维的前提是优化问题中必须存在多个冗余目标．但在实际优化问题中往往不存在多个冗余目标且冗余目标的确定需要花费巨大的计算资源．（２）使用指标函数．在 ＭＯＥＡｓ中，需要运用评价指标对算法的性能进行评价，因此可以直接利用性能评价指标指导算法的搜索方向．其中，超体积指标（ＨｙｐｅｒＶｏｌｕｍｅ，ＨＶ）［３３］是最常用的指标函数．然而在高维目标空间中，ＨＶ 指标的计算复杂度很大，这也限制了该方法的广泛应用．（３）修改 Ｐａｒｅｔｏ支配关系．目前已提出众多新的支配关系，如ε－支配关系［５］、排序支配关系［６］、模糊支配关系［７－８］等．虽然新的支配关系能增强种群在进化过程中的选择压力，但其重复利用目标函数的信息使得算法的计算复杂度明显增大．（４）结合 ＤＭ 偏好．Ｆｌｅｍｉｎｇ等人［３４］运用偏好６期 王丽萍等：偏好多目标进化算法研究综述２１１９］，通过逐渐缩小搜索区域来获得偏好解．Ｄｅｂ等人［３６］将参考点的偏好信息纳入到 ＮＳＧＡ－ＩＩ算 法 中 以 获 得 非 支 配 解 集．Ｍｏｌｉｎａ等人［３７］提出给定参考点的ｇ－占优方法（ＲｅｆｅｒｅｎｃｅＰｏｉｎｔ　Ｂａｓｅｄ　Ｄｏｍｉｎａｎｃｅ　ｆｏｒ　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　Ｍｅｔａ－ｈｅｕｒｉｓｔｉｃｓ，ｇ－ｄｏｍｉｎａｃｅ），将参考点作为偏好信息引导种群的搜索趋势和前沿的逼近方向．其中，参考点是目标空间中由 ＤＭ 定义的点，用于表示 ＤＭ 对每个目标不同的期望程度．由于该类方法只需要搜索ＤＭ 感兴趣的区域，不仅提高 ＭＯＥＡｓ的求解效率，还能帮助 ＤＭ 选择其偏好解，因而受到研究者们的广泛关注．本文第１节引言部分简要介绍 ＭＯＥＡｓ主流研究者和研究团队的工作概况；第２节偏好多目标进化算法，着重介绍了偏好 ＭＯＰｓ的相关概念，从占优关系、角度关系、权重向量和偏好集四个方面对偏好的设置方法进行详细分析；第３节偏好多目标进化算法性能对比分析，从四类偏好设置方法中各选取两种代表性的偏好算法进行仿真实验，从偏好策略的有效性、解集的整体性以及算法的复杂度三个方面进行实验对比并深入分析其优缺点，并给出了专门用于评价偏好 ＭＯＥＡｓ性能的指标；第４节结语，提出了偏好 ＭＯＥＡｓ有待进一步研究的若干方向．２　偏好多目标进化算法在现实问题中，ＤＭ 通常只对 ＭＯＰｓ的 Ｐａｒｅｔｏ前沿部分区域感兴趣．而随目标维度的增加，种群中非支配解的比例急剧增长，这将导致算法的性能衰减严重［３８］．若能结合 ＤＭ 的偏好信息，将算法的搜索集中在 Ｐａｒｅｔｏ前沿的特定区域，便能降低算法的计算复杂度，提高收敛性能．因此如何结合 ＤＭ 的偏好信息以及如何利用偏好信息引导种群的搜索成为当前的研究热点．２．１　偏好多目标优化问题相关概念多目标优化是指同时优化多个目标使其达到最优，然而各个目标间往往是相互冲突的，因此 ＭＯＰｓ的解是一 组 折 中 的 最 优 解 集 合．本 文 以 最 小 化 问题为例，对于一个具有 ｍ 个目标，ｎ 维 决策变 量 的ＭＯＰｓ，其数学模型描述如下：　Ｍｉｎ　ｙ＝Ｆ（ｘ）＝（ｆ１（ｘ），ｆ２（ｘ），…，ｆｍ（ｘ））Ｔｇｉ（ｘ）０，ｉ＝１，２，…，ｐｈｊ（ｘ）０，ｊ＝１，２，…，烅烄烆 ｑ（１）其中，ｘ＝（ｘ１，ｘ２，…，ｘｎ）∈Ｘ，ｘ 为决策变量，ｙ＝（ｙ１，ｙ２，…，ｙｍ）∈Ｙ，ｙ 为优化目标，Ｘ 为ｎ 个决策变量构成的决策空间，Ｙ 为ｍ 个优化目标构成的目标空间，Ｆ（ｘ）为目标向量，ｇｉ（ｘ）和ｈｊ（ｘ）分别为问题的约束条件．定义１（Ｐａｒｅｔｏ支配）．　设ｘ 和ｙ 是种群中任意两个个体，需满足如下约束条件，则称ｘ 支配ｙ，记作ｘｙ．ｆｉ（ｘ）ｆｉ（ｙ）， ｉ＝１，２，…，ｍｆｊ（ｘ）＜ｆｊ（ｙ），ｊ＝１，２，…，烅烄烆ｍ（２）定义２（非支配解）．　设ｘ 是集合Ｑ 中的任意解，需满足式（３），则称ｘ 为集合Ｑ 中的非支配解．／ｙ∈Ｑ：ｙｘ （３）定义３（Ｐａｒｅｔｏ最优解）．　设可行域Ｒ 中任意两个个体ｘ与ｙ，需满足式（４），则称个体ｘ为Ｐａｒｅｔｏ最优解．／ｙ∈Ｒ：ｙｘ （４）定义４（Ｐａｒｅｔｏ最优解集）．　可行域 Ｒ 中所有的 Ｐａｒｅｔｏ 最 优 解 组 成 Ｐａｒｅｔｏ 最 优 解 集 （ＰａｒｅｔｏＳｅｔ，ＰＳ）．Ｓ＝｛ｘ｜ｘ∈Ｒ 且ｘ 是Ｐａｒｅｔｏ最优解｝ （５）定义５（Ｐａｒｅｔｏ前沿）．　Ｐａｒｅｔｏ最优解集中所有Ｐａｒｅｔｏ最优解在目标空间上的映射，称为：Ｐａｒｅｔｏ前沿（Ｐａｒｅｔｏ　Ｆｒｏｎｔ，ＰＦ）．ＰＦ＝｛ｆ（ｘ）∈Ｒ｜ｘ∈ＰＳ｝ （６）定义６（决策偏好）．　在多准则决策（ＭｕｌｔｉｐｌｅＣｒｉｔｅｒｉａ　Ｄｅｃｉｓｉｏｎ　Ｍａｋｉｎｇ，ＭＣＤＭ）领域，决策偏好是指决策者在面对几个选项或备择方案时选择其中某一选项或备择方案的倾向［３９］．定义７（偏好表示）．　ＤＭ 通常将参考 点的位置信息作为偏好信息的载体，不同参考点的位置信息代表 ＤＭ 不同的偏好要求［４０］．此外，由参考点确定的参考方向、光束搜索等方法也用来表示 ＤＭ 的偏好信息［４１］．定义８（偏好支配）．　设种群中任意两个个体ｘ与ｙ，若个体ｘ偏好支配ｙ，当且仅当满足如下２个条件之一，记作ｘｒｙ，ｒ为 ＤＭ 偏好．（１）ｘ支配ｙ；（２）ｘ与ｙ 互不支配，ｘ在偏好意义上占优ｙ．定义９（偏好最优解）．　设可行域 Ｒ 中的个体ｘ，若不存在任意个体ｙ，使得ｙｒｘ，则称个体ｘ为偏好最优解．由偏好最优解组成的最优解集合为偏好最优解集．２．２　偏好的理论研究多准则决策（ＭＣＤＭ）主要解决具有多个相互冲２１２９ 计　　算　　机　　学　　报 ２０１９年出 版 日 期：２０１９－０１－０６．本 课 题 得 到 国 家 自 然 科 学 基 金 项 目 （６１４７２３６６，６１３７９０７７）、浙 江 省 自 然 科 学 基 金（ＬＹ１７Ｆ０２００２２）、浙江省重点研发计划项目（２０１８Ｃ０１０８０）资助．王丽萍（通信作者），博士，教授，中国计算机学会（ＣＣＦ）会员，主要研究方向为计算智能、决策优化．Ｅ－ｍａｉｌ：ｗｌｐ＠ｚｊｕｔ．ｅｄｕ．ｃｎ．丰美玲，硕士研究生，主要研究方向为计算智能、决策优化．邱启仓，硕士，主要研究方向为智能控制．章鸣雷，硕士，主要研究方向为计算智能．邱飞岳（通信作者），博士，教授，主要研究方向为智能控制、深度学习．Ｅ－ｍａｉｌ：ｑｆｙ＠ｚｊｕｔ．ｅｄｕ．ｃｎ．偏好多目标进化算法研究综述王丽萍１），２）　丰美玲２）　邱启仓３）　章鸣雷２）　邱飞岳４）１）（浙江工业大学计算机科学与技术学院　杭州　３１００２３）２）（浙江工业大学信息智能与决策优化研究所　杭州　３１００２３）３）（之江实验室　杭州　３１１１００）４）（浙江工业大学　杭州　３１００２３）摘　要　多目标优化需要同时优化若干相互冲突的目标，其目的是获得均匀分布于整个 Ｐａｒｅｔｏ前沿上的最优解集．然而在实际多目标优化问题中，决策者通常只对目标空间中部分区域内的 Ｐａｒｅｔｏ最优解感兴趣，因此将决策者的偏好信息与多目标优化方法相结合成为进化计算领域的研究热点．偏好多目标进化算法通过引入决策者的偏好信息，将算法的搜索集中在决策者感兴趣的偏好区域，有效利用算法的计算资源，提高算法的求解效率，降低计算复杂度，同时有利于决策者高效地做出最终决策．本文从偏好的设置方法和算法性能两个角度介绍偏好多目标进化算法．在偏好的设置上，从占优关系、角度关系、权重向量和偏好集四个方面综述融入偏好信息的多目标进化算法；在算法性能上，从上述四类偏好的设置方法中各选取两种偏好算法进行仿真实验，从偏好策略的有效性、解集的整体性以及算法的复杂度三个方面进行实验对比并深入分析其优缺点．最后，总结了偏好多目标进化算法的未来发展趋势．关键词　多目标优化；偏好设置；占优关系；角度关系；权重向量；偏好集中图法分类号 ＴＰ３９１　　　ＤＯＩ号 １０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．０１２８９Ｓｕｒｖｅｙ　ｏｎ　Ｐｒｅｆｅｒｅｎｃｅ－Ｂａｓｅｄ　Ｍｕｌｔｉ－Ｏｂｊｅｃｔｉｖｅ　Ｅｖｏｌｕｔｉｏｎａｒｙ　ＡｌｇｏｒｉｔｈｍｓＷＡＮＧ　Ｌｉ－Ｐｉｎｇ１），２）　ＦＥＮＧ　Ｍｅｉ－Ｌｉｎｇ２）　ＱＩＵ　Ｑｉ－Ｃａｎｇ３）　ＺＨＡＮＧ　Ｍｉｎｇ－Ｌｅｉ　２）　ＱＩＵ　Ｆｅｉ－Ｙｕｅ４）１）（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　３１００２３）２）（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　ａｎｄ　Ｄｅｃｉｓｉｏｎ　Ｏｐｔｉｍｉｚａｔｉｏｎ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　３１００２３）３）（Ｚｈｅｊｉａｎｇ　Ｌａｂ，Ｈａｎｇｚｈｏｕ　３１１１００）４）（Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　３１００２３）Ａｂｓｔｒａｃｔ　 Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｎｅｅｄｓ　ｔｏ　ｏｐｔｉｍｉｚｅ　ｓｅｖｅｒａｌ　ｃｏｎｆｌｉｃｔｉｎｇ　ｏｂｊｅｃｔｉｖｅ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｔｈｅ　ａｉｍ　ｏｆ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｔｏ　ｏｂｔａｉｎ　ｔｈｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｓｅｔｓ　ｗｈｉｃｈ　ｕｎｉｆｏｒｍｌｙｄｉｓｔｒｉｂｕｔｅｄ　ｏｎ　ｔｈｅ　ｗｈｏｌｅ　Ｐａｒｅｔｏ　ｆｒｏｎｔ．Ｈｏｗｅｖｅｒ，ｄｅｃｉｓｉｏｎ　ｍａｋｅｒｓ　ｕｓｕａｌｌｙ　ａｒｅ　ｏｎｌｙ　ｉｎｔｅｒｅｓｔｅｄ　ｉｎｔｈｅ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎｓ　ｉｎ　ｓｏｍｅ　ｒｅｇｉｏｎｓ　ｏｆ　ｔｈｅ　ｏｂｊｅｃｔｉｖｅ　ｓｐａｃｅ　ｉｎ　ｐｒａｃｔｉｃａｌ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ．Ｔｈｅｒｅｆｏｒｅ，ｃｏｍｂｉｎｉｎｇ　ｄｅｃｉｓｉｏｎ　ｍａｋｅｒ’ｓ　ｐｒｅｆｅｒｅｎｃｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｗｉｔｈｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｉｓ　ｇｒａｄｕａｌｌｙ　ｂｅｃｏｍｉｎｇ　ａ　ｈｏｔ　ｓｕｒｖｅｙ　ｔｏｐｉｃ　ｉｎ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｆｉｅｌｄｏｆ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｃｏｍｐｕｔｉｎｇ．Ｃｏｍｂｉｎｉｎｇ　ｔｈｅ　ｄｅｃｉｓｉｏｎ　ｍａｋｅｒ’ｓ　ｐｒｅｆｅｒｅｎｃｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｗｉｔｈ　ｔｈｅｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ　ｓｅａｒｃｈ　ｐｒｏｃｅｓｓ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　ｃａｎ　ｂｅ　ｃｏｎｃｅｎｔｒａｔｅｄｉｎ　ｔｈｅ　ｐｒｅｆｅｒｅｎｃｅ　ｒｅｇｉｏｎ．Ｔｈｉｓ　ｃａｎ　ｎｏｔ　ｏｎｌｙ　ｕｓｅ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｒｅｓｏｕｒｃｅｓ　ｅｆｆｅｃｔｉｖｅｌｙ　ａｎｄｉｍｐｒｏｖｅ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ，ｂｕｔ　ａｌｓｏ　ｃａｎ　ｒｅｄｕｃｅｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｈｅｌｐ　ｄｅｃｉｓｉｏｎ　ｍａｋｅｒｓ　ｍａｋｅ　ｔｈｅ　ｆｉｎａｌ　ｄｅｃｉｓｉｏｎ　ｅｆｆｉｃｉｅｎｔｌｙ．Ｉｎ　ｔｈｉｓ］．ＭＣＤＭ 包括适用于解决有限 离 散 问 题 的 多 属 性 决 策 （Ｍｕｌｔｉｐｌｅ　ＡｔｔｒｉｂｕｔｅＤｅｃｉｓｉｏｎ　Ｍａｋｉｎｇ，ＭＡＤＭ）和 适 用 于 连 续 问 题 的多目标决策 （Ｍｕｌｔｉｐｌｅ　Ｏｂｊｅｃｔｉｖｅ　Ｄｅｃｉｓｉｏｎ　Ｍａｋｉｎｇ，ＭＯＤＭ）．目前已有许多求解 ＭＣＤＭ 问题的方法，如理想点法、主成分分析法、加权平方和法等，这些方法 大 多 需 要 给 出 各 指 标 的 权 重，即 ＤＭ 的 偏好［４３］．权重是各个准则相对于总准则作用的量化，能反映每个准则的相对重要性．在 ＭＣＤＭ 领域中，偏好 的表示方法主要有以下三种：序数法、不确定法和基数法［４４］．序数法主要用于处理序数关系值类的偏好信息，即 ＤＭ 给出对多个方案的排序信息．不确定法一般用于决策过程中存在不确定因素时的偏好信息表示．基数法是指能够明确度量 ＤＭ 偏好、决策规则以及效用函数时的决策信息表示方法．根据以上三种表示方法，决策偏好的表示形式一般有序关系值、效用值、互反偏好关系、模糊偏好关系等［４５］．Ｓｉｎｄｈｙａ等人［４６］将 ＭＣＤＭ 与 ＭＯＥＡ 相 结 合的 方 法 归 纳 为 两 类：ＭＯＥＡｓ 融 入 到 ＭＣＤＭ 和ＭＣＤＭ 融入到 ＭＯＥＡｓ．ＭＯＥＡ 融入到 ＭＣＤＭ 是指应 用 ＭＯＥＡｓ 求 解 ＭＣＤＭ 方 法 中 的 ＳＯＰｓ，ＭＯＥＡｓ可以帮助 ＭＣＤＭ 解决数学规划（Ｍａｔｈｅ－ｍａｔｉｃａｌ　Ｐｒｏｇｒａｍｍｉｎｇ，ＭＰ）方法难以处理的难题．ＭＣＤＭ 融入到 ＭＯＥＡｓ是指将 ＤＭ 的偏好信息以先验或交互的方式结合到 ＭＯＥＡｓ中，将算法的搜索集中在偏好区域，可以有效利用算法资源，同时降低计算复杂度，提高算法的求解效率［４７］．２．３　偏好的设置方法通过将 ＤＭ 的 偏 好 信 息 融 入 到 ＭＯＥＡｓ框 架中，可以将算法的搜索集中在 Ｐａｒｅｔｏ前沿的期望区域．基于以上思想，学者们提出了许多偏好的设置方法，有效地将 ＤＭ 的偏好信息融入到 ＭＯＥＡｓ框架中．本文根据偏好的设置方 法从占优关系、角 度 关系、权重向量以及偏好集这四个角度，综述融入偏好的 ＭＯＥＡｓ．２．３．１　占优关系除偏好信息外，偏好设置方法的不同也在很大程度上影响算法的性能．根据 ＤＭ 给定的参考点，通过修改 Ｐａｒｅｔｏ占优关系，在一定程度上增强解之间的选择压力，引导算法快速向 ＤＭ 的偏好区域搜索．同时，基于占优关系的设置方法实现简单，能容易地融入到其他的 ＭＯＥＡｓ中．Ｍｏｌｉｎａ等人［３７］提出了一种基于 ＤＭ 给定参考点的ｇ－占优方法．该方法根据参考点划分搜索空间，定义了搜索的优先区域，通过修改 Ｐａｒｅｔｏ占优关系，使算法的搜索区域集中在该参考点附近．定义Ｆｌａｇｇ（ｘ）如下：Ｆｌａｇｇ（ｘ）＝１， ｇｉｘｉ，ｉ＝１，２，…，ｍ１， ｇｉｘｉ，ｉ＝１，２，…，ｍ０，烅烄烆其他（７）其中，ｇ为 ＤＭ 给定的参考点，ｘ 是目标空间中的任意一点．从以上定义可得，参考点 ｇ 将目标空间划分为Ｆｌａｇ＝０和 Ｆｌａｇ＝１两部分，如图１所示［３７］．利用式（７）可以定义如下支配关系．图 １　ｇ－占优［３７］定义１０（ｇ－占优）．　可行域中任意２个个体ｘ和ｙ要满足ｘ　ｇ －占优ｙ 当且仅当满足如下２个条件之一：（１）Ｆｌａｇｇ（ｘ）＞Ｆｌａｇｇ（ｙ）；（２）Ｆｌａｇｇ（ｘ）＝Ｆｌａｇｇ（ｙ）且有ｘＰａｒｅｔｏ支配ｙ．ｇ－占优机制能容易地将 ＤＭ 的偏好信息融入到 ＭＯＥＡｓ中，且在２、３维优化问题上种群能较好地收敛到偏好区域．但该算法存在两个明显的不足：（１）参考点严格控制了优先区域，种群容易丢失多样性，使得算法在局部最优较多的问题上收敛性差；（２）参考点位置对算法的影响很大，当参考点设置在距离 Ｐａｒｅｔｏ前沿附近时，算法性能表现得十分不稳定，甚至导致算法不收敛．为解决ｇ－占优机制在高维 ＭＯＰｓ上不收敛和对参考点 位 置 敏 感 等 问 题，Ｓａｉｄ 等 人［４８］提 出 了 一种ｒ－占 优 （Ｒｅｆｅｒｅｎｃｅ　Ｓｏｌｕｔｉｏｎ　Ｂａｓｅｄ　Ｄｏｍｉｎａｎｃｅ，ｒ－ｄｏｍｉｎａｎｃｅ）方法，该方法通过在 Ｐａｒｅｔｏ非支配解集上建立严格的偏序集，引导算法朝偏好区域进行搜索．与ｇ－占优相比，ｒ－占优受偏好点位置的影响较小，但ｒ－占优只能保证弱 Ｐａｒｅｔｏ支配的最优性，特别是在不连续 Ｐａｒｅｔｏ前沿的问题中会产生大量的弱 Ｐａｒｅｔｏ最优解，即所得解集中存在大量的非支配解，这将严重影响算法的收敛性能．定义１１（ｒ－占优）．　可行域中任意２个个体ｘ６期 王丽萍等：偏好多目标进化算法研究综述２１３９且仅当满足如下２个条件之一：（１）ｘＰａｒｅｔｏ支配ｙ；（２）ｘ与ｙ是Ｐａｒｅｔｏ互不支配的，且Ｄ（ｘ，ｙ，ｇ）＜－δ，δ∈［０，１］．其中，Ｄ（ｘ，ｙ，ｇ）＝Ｄｉｓｔ（ｘ，ｇ）－Ｄｉｓｔ（ｙ，ｇ）Ｄｉｓｔｍａｘ－Ｄｉｓｔｍｉｎ，Ｄｉｓｔｍａｘ＝Ｍａｘｚ∈ＰＤｉｓｔ（ｚ，ｇ），Ｄｉｓｔｍｉｎ＝Ｍｉｎｚ∈ＰＤｉｓｔ（ｚ，ｇ），Ｄｉｓｔ（ｘ，ｇ）＝∑ｍｉ＝１ｗｉｆｉ（ｘ）－ｆｉ（ｇ）ｆｍａｘｉ－ｆｍｉｎ（ ）ｉ槡２（８）ｗｉ∈［０，１］，∑ｍｉ＝１ｗｉ＝１，ｇ为参考点，δ∈［０，１］为控制偏好区域大小的参数．邱飞岳等人［４１］同时考虑 ＤＭ 的正、负偏好信息，提出了双极偏好占优机制，并将其融入到 ＮＳＧＡ－ＩＩ中，形成２ｐ－ＮＳＧＡ－ＩＩ算法．该算法在非支配解间建立更为严 格 的 占 优 关 系，能 有 效 解 决 在 高 维 目 标空间中因非支配解的比例急剧增长导致算法性能衰减严重的问题．首先定义正、负参考点 Ｐ＋和 Ｐ－，在种群Ｐｏｐ中其他任意个体ｉ到正、负参考点的距离分别为ｄ＋ｉ和ｄ－ｉ，如图２所示［４１］．为了综合考虑个体ｉ到正参考点的贴近度和到负参考点的远离度定义如下贴近度计算公式：Ｃｉ＝ｄ－ｉｄ＋ｉ＋ｄ－ｉ（９）图 ２　双极偏好占优［４１］定义１２（双极占优）．　在种群 Ｐｏｐ中任意两个个体ｘ，ｙ∈Ｐｏｐ，ＤＭ 给定正负参考点Ｐ＋、Ｐ－，定义ｘ双极占优ｙ，当且仅当满足如下３个条件之一（其中Ｆｌａｇ 计算方法同ｇ－占优）：（１）Ｆｌａｇ＋ｐ（ｘ）＞Ｆｌａｇ－ｐ（ｙ）；（２）Ｆｌａｇ＋ｐ（ｘ）＝Ｆｌａｇ－ｐ（ｙ）且ｘＰａｒｅｔｏ支配ｙ；（３）当（１）和（２）都不成立，Ｃｘ＞Ｃｙ．２ｐ－ＮＳＧＡ－ＩＩ算法提高对种群的选择压力，引导种群快速向靠近正参考点同时远离负参考点的偏好区域收敛．但该算法只考虑了正、负偏好点间的相对距离，算法的求解效果并不理想，且在不同的测试函数上算法的表现差异较大，算法的鲁棒性较差．当ＤＭ 设置的正参考点远离 Ｐａｒｅｔｏ前沿，负偏好点靠近 Ｐａｒｅｔｏ前沿时，该算法容易陷入局部最优而丢失部分偏好最优解．Ｊａｉｍｅｓ等人［４９］定义新的偏好占优关系，该偏好占优关系将整个目标空间划分为两个子空间，其中一个子空间的个体使用强化的 Ｐａｒｅｔｏ支配关系进行比较，另 一 个 子 空 间 的 个 体 使 用 收 益 标 量 函 数（Ａｃｈｉｅｖｅｍｅｎｔ　Ｓｃａｌａｒｉｚｉｎｇ　Ｆｕｎｃｔｉｏｎ，ＡＳＦ）进 行 比较，如图３（ａ）所示［４９］．通过设定参考点，利用新的偏好关系 引 导 种 群 向 偏 好 区 域 进 化，如 图 ３（ｂ）所示［４９］，定义解ｚ１占优解ｚ２．随后，将新的偏好占优关系以交互的方式嵌入到优化过程中，在每个交互点处向 ＤＭ 提供当前的近似 Ｐａｒｅｔｏ解，以便 ＤＭ 指导后续搜索的进行．该偏好占优关系其优点在于，不仅可以根据 ＤＭ 的需求直观的设置参数，与 ＤＭ 进行实时交互，而 且在高 维 上也能获 得 较 优 的 解．ＡＳＦ函数定义如下：Ｍｉｎ　Ｓｇ（ｆ（ｘ））＝ ｍａｘｉ＝１，２，…，ｍ｛ｗｉ（ｆｉ（ｘ）－ｇｉ）｝＋λ∑ｐｉ＝１（ｆｉ（ｘ）－ｇｉ） （１０）其中，λ＞０ 是一个很小的增量系数，ｉ代表第ｉ 个目标，ｗｉ为第ｉ个目标上的权重即重要程度，ｇｉ为参考点第ｉ维的值．图 ３　定义新的偏好占优关系［４９］２．３．２　角度关系基于占优关系的偏好设置方法虽实现简单，但其不能灵活控制偏好区域的范围，且在高维目标优化问题上表现较差．而通过角度引入 ＤＭ 的偏好信息，根据参考点和角度值确定偏好区域，利用个体间的角度关系引导算法的进化，增强算法的选择压力，同时利用角度控制偏好区域的范围，最终获得 ＤＭ的偏好解．Ｚｈｅｎｇ等人［５０］提出一种基于个体间角度关 系２１４９ 计　　算　　机　　学　　报 ２０１９年　Ｄｏｍｉｎａｔｅｄ　ＮＳＧＡ－ＩＩ）算法．该算法通过重新定义个体间支配关系和聚集距离，优先保留距离偏好点近的个体，引导种群朝偏好区域进行搜索．偏好点仅用于搜索种群中离其最近的点，以最近点为基点使用角度控制偏好区域，因此算法的性能不会受偏好点位置的影响．如图４（ａ）所示［５０］，ＤＭ 首先设置一个偏好点ｐ，然后求得种群中距离偏好的最近点 Ｎ，其中α 为 ＤＭ 指定的角度范围，θ是 ＤＭ 定义的角度下界用于避免个体过度集中．对于种群中的其他个体，采用离偏好最近点 Ｎ最近的个体优先保留策略．其中，利用角度信息引入ＤＭ 偏好的相关定义如下．图 ４　角度偏好关系［５０－５１］定义１３（个体间角度）．　种群中任意两个个体ｘ与ｙ 间的角度：Ａｎｇｌｅ（ｘ，ｙ）＝Ｆ（ｘ）ｃｏｓＦ（ｘ）·Ｆ（ｙ）Ｆ（ｘ）× Ｆ（ｙ（ ））（１１）Ｆ（ｘ）＝（（ｘ１－ｐｉ）／（ｆｍａｘ１－ｆｍｉｎ１），…，（ｘｍ－ｐｍ）／（ｆｍａｘｍ－ｆｍｉｎｍ）），Ｆ（ｙ）＝（（ｙ１－ｐｉ）／（ｆｍａｘ１－ｆｍｉｎ１），…，（ｙｍ－ｐｍ）／（ｆｍａｘｍ－ｆｍｉｎｍ）） （１２）定义１４（偏好角度支配）．　设种群中任意两个个体ｘ 与ｙ，若个体ｘ 偏好角度支配ｙ 当且仅当满足如下２个条件之一：（１）ｘＰａｒｅｔｏ支配ｙ；（２）ｘ 与ｙ 是Ｐａｒｅｔｏ互不支配的，且Ａｎｇｌｅ（ｙ，Ｎ）－Ａｎｇｌｅ（ｘ，Ｎ）α，其中，Ｎ 为距离偏好最近的点，α为 ＤＭ 指定的角度范围．定义１５（偏好聚集距离）．　 非支配排序后，对处于同一层级的个体，优先选择距离偏好点近的个体进入下一代．重新定义个体间的聚集距离如下，其中，Ｂ 是一个很大的正数．　Ｃｒｏｗｄ（ｘ）＝　Ｂ－Ａｎｇｌｅ（ｘ，ｐ），ｉｆ　Ｍｉｎ（Ａｎｇｌｅ（ｘ，ｙ））＞θＭｉｎ（Ａｎｇｌｅ（ｘ，ｙ｛））（１３）ＡＰ－ε－ＭＯＥＡ（ＡＰ－ε－ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍ）［５１］算法通过参考点及角度值来引入 ＤＭ的偏好信息．首先将目标空间划分为偏好区域和非偏好区域两部分，使算法在 ＤＭ 的偏好区域进行搜索，有效提高算法搜索效率；随后利用 ＤＭ 定义的角度值控制偏好区域的大小，如图４（ｂ）所示［５１］．进而，在 Ｐａｒｅｔｏ最优解中利用 ＡＰ－ε 支配策略建立更为严格的偏序关系，从而区分非支配解中的偏好解和非偏好解．该支配策略可以通过角度值有效控制偏好解集的分布范围，并且支持多偏好区域的搜索，同时算法能以较快的速度收敛到 Ｐａｒｅｔｏ前沿且搜索到 ＤＭ 感兴趣的偏好解．定义１６（ε支配策略）．　设种群中任意两个个体ｘ 与ｙ，若个体ｘ 和ｙ 满足如下公式，则称ｘε 支配ｙ，记作ｘεｙ．Ｂｉ（ｘ）Ｂｉ（ｙ）， ｉ＝１，２，…，ｍＢｊ（ｘ）＜Ｂｊ（ｙ），ｊ＝１，２，…，烅烄烆ｍ（１４）其中，向量Ｂ（ｘ）表示个体ｘ 在目标空间中的格子位置，定义为Ｂｉ（ｘ）＝［（ｆｉ（ｘ）－ｆｍｉｎｉ）／εｉ］ （１５）ｆｍｉｎｉ为第ｉ个目标的最小值，εｉ为第ｉ 个目标的偏差强度值．定义１７（ＡＰ－ε 支配策略）．　 可行域中任意 ２个个体ｘ 和ｙ 要满足ｘ　ＡＰ－ε 支配ｙ 当且仅当满足如下２个条件之一：（１）个体 ｘ 和ｙ 同属于偏好区域或非偏好区域，且ｘε 支配ｙ；（２）个体ｘ属于偏好区域，ｙ属于非偏好区域．ＡＤＡ （Ａｄａｐｔｉｖｅ　ａｎｇｌｅ　ｂａｓｅｄ　ｐｒｕｎｉｎｇ　Ａｌｇｏ－ｒｉｔｈｍ）［５２］是一种自适应角度修剪算法，该算法根据ＤＭ 提供的角度信息修剪 Ｐａｒｅｔｏ最优解．ＡＤＡ 算法首先根据 ＭＯＥＡ 获得 Ｐａｒｅｔｏ最优解，然后根据ＤＭ 提供的最大角度阈值，运用自适应角度修剪机制对上一阶段所得到的 Ｐａｒｅｔｏ最优解进行修剪．自适应修剪机制通过计算每个目标上每对解之间的角度且与最大角度阈值相比较来确定占优关系，然后使用拥挤距离策略维持解集的多样性．其基本原理是通过扩大每个目标上每对解间的角度，增强解之间的选择压力，以消除那些仅在某些目标上占优但在其他目标上显著更差的解．如图５（ａ）所示［５２］，根据传统 Ｐａｒｅｔｏ支配关系，Ａ、Ｂ 两点互不支配．然而在图５（ｂ）中［５２］，根据自适应角度修剪机制对 Ａ、Ｂ 两点分别进行角度扩展，Ａ、Ｂ 两点两侧扩展的角度为α 和β，经角度扩展后，Ａ 点明显支配Ｂ 点，其中δ为最大角度阈值，α、β分６期 王丽萍等：偏好多目标进化算法研究综述２１５９角度修剪算法［５２］别为修剪的角度值．通过对 Ａ、Ｂ 两点进行角度扩展，重新定义了两点间的支配关系，增强了对优秀解集的选择压力，引导解集朝 Ｐａｒｅｔｏ前沿上的偏好区域收敛．随后，Ｓｕｄｅｎｇ等人［５３］对 ＡＤＡ 算法进行改进，提出了基于特定角度偏差参数的修剪算法 （Ａｎｇｌｅｂａｓｅｄ　ｗｉｔｈ　Ｓｐｅｃｉｆｉｃ　ｂｉａｓ　ｐａｒａｍｅｔｅｒ　ｐｒｕｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ，ＡＳＡ）．该算法首先使用反正切函数计算每对解间的角度，然后引入偏差强度参数计算角度阈值，从而在偏好区域内确定偏好解，其中可以根据偏好信息在不同的目标上对偏差强度参数进行适当的调整．将基于特定角度偏差参数的修 剪机制应用于获得Ｐａｒｅｔｏ最优解阶段，可以帮助 ＤＭ 获得鲁棒性更强的 Ｐａｒｅｔｏ最优偏好解．ｉ－ＡＳＡ－ＮＳＧＡ－ＩＩ（Ｉｎｔｅｒａｃｔｉｖｅ　Ｐｒｅｆｅｒｅｎｃｅ－ｂａｓｅｄＭｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ）［５４］是一种基于 ＤＭ 偏好信息的交互式算法．该算法首先根据参考点及扩展角度确定 ＤＭ 的偏好区域，然后应用 偏 好 信 息 扩 展 角 度 的 支 配 策 略 来 替 换 原始 ＮＳＧＡ－ＩＩ中的拥 挤 距 离 策 略．在 种 群 进 化 过 程中，多次与 ＤＭ 进行交互，使用 ＡＳＡ 算法对得到的解集进 行 修 剪，直 到 最 终 获 得 ＤＭ 满 意 的 偏 好 最优解．图 ６　ｉ－ＡＳＡ－ＮＳＧＡ－ＩＩ算法模型［５４］ｉ－ＡＳＡ－ＮＳＧＡ－ＩＩ算法的模型如图６所示［５４］，由ｉ－ＡＳＡ－ＮＳＧＡ－ＩＩ算法产生初始的近似解集呈现给ＤＭ，ＤＭ 根据初始解集以及其偏好要求通过给定参考点的形式确定偏好区域，随后算法将划定的偏好区域呈现给 ＤＭ，若偏好区域满足 ＤＭ 的要求，则通过 ＡＳＡ 角度修剪机制对偏好区域内的解集进行修剪，将修剪后的偏好解集再次呈现给 ＤＭ，直到最终满足 ＤＭ 的要求．２．３．３　权重向量参考向量和权重向量在聚合功能上相似，但因其物理意义不同，在搜索过程中对算法有不同的影响．通常，参考向量表示解向量的方向，权重向量表示不同目标的重要性；参考向量在目标空间中，权重向量在权重空间中．参考点是以结构化方式预先定义或由 ＤＭ 定义的点［３８］．参考向量和参考点都能表示目标的期望或重要性，且参考点、参考向量与权重向量之间可以相互转换［３９］．如 ＲＶＥＡ［２６］中的参考向量和 ＮＳＧＡ－ＩＩＩ［２８］中的参考点都是由均匀分布的权重向量转换而来．Ｍｏｈａｍｍａｄｉ等人［５５］提出的 Ｒ－ＭＥＡＤ（ＲｅｆｅｒｅｎｃｅＰｏｉｎｔ　Ｂａｓｅｄ　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＴｈｒｏｕｇｈＤｅｃｏｍｐｏｓｉｔｉｏｎ）算法通过引入分解机制，将参考点的位置信息和 ＤＭ 的偏好信息转化为一组携带偏好信息的权重向量，随后这组权重向量将 ＭＯＰｓ分解为若干个单目标优化子问题进行求解．该算法通过计算每个个体与每个参考点的距离，将距离参考点最近的个体所对应的权重向量作为初始权重，在初始权重向量附近重新生成一组新的权重向量，动态调整权重向量使其逐渐靠近 ＤＭ 的偏好区域．由于 Ｒ－ＭＥＡＤ 从 ＭＯＥＡ／Ｄ 中继承了 单格子点设计方 法 进 行 初 始 化 权 重，使 得 种 群 的 大 小 受到目标 维 度 的 约 束．Ｍｏｈａｍｍａｄｉ等 人［５６］提 出 了Ｒ－ＭＥＡＤ２以解决 Ｒ－ＭＥＡＤ 在权重初始化时存在的问题．Ｒ－ＭＥＡＤ２采用均匀随机数生成方法产生权重向量 代替 Ｒ－ＭＥＡＤ 中的单 格子点 设 计 方 法，并且在权重生成的过程中不断重构调整权重向量，这不仅消除了目标维度对种群大小的约束，而且能够在高维目标空间中产生均匀分布的权重向量．图７［５６］所示为算法在进化过程中权重向量的重构示意图．图７［５６］左侧的黑色方块表示在第ｔ次迭代前的解，灰色方块表示经过算法迭代后的解，箭头表示由权重向量和每个解所决定的更新方向，ｒ 为ＤＭ 设定的偏好区域．其中，与参考点最接近的解所对应的权重向量被视为最优权重 Ｗｂ．一旦确定最优权重，则使用均匀随机数生成法生成一组新的围绕最优权重的权重向量，如图７［５６］中心处的方框所示，权２１６９ 计　　算　　机　　学　　报 ２０１９年重Ｗｂ生成．随后，将这些权重分配回上次迭代中所获得的解．最后，使用新生成的权重进行算法优化．如图７［５６］右侧所示，由五角星标记的新解在参考点的方向上逐渐收敛于偏好区域．图 ７　权重向量重构［５６］Ｌｉ等人［５７］在 ＭＯＥＡ／Ｄ－ＳＴＭ（Ｓｔａｂｌｅ　Ｍａｔｃｈｉｎｇ－Ｂａｓｅｄ　Ｓｅｌｅｃｔｉｏｎ　ｉｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　ＭｕｌｔｉｏｂｊｅｃｔｉｖｅＯｐｔｉｍｉｚａｔｉｏｎ）算法的基础上，提出了应用权重向量引入 ＤＭ 偏好信息的ｒ－ＭＯＥＡ／Ｄ－ＳＴＭ 算法．该算法首先根据 ＤＭ 提供的参考点，使用单格子点设计方法生成大量的权重向量，然后选择距离参考点最近的若干权重向量作为 ＤＭ 的偏好区域．Ｚｈｅｎｇ等人［５８］提出一种基于权重迭代的 偏 好多目标分解算法 ＭＯＥＡ／Ｄ－ＰＲＥ（Ｐｒｅｆｅｒｅｎｃｅ－ｂａｓｅｄＡｎｄ　Ｄｅｃｏｍｐｏｓｉｔｉｏｎ－ｂａｓｅｄ　ＭＯＥＡ），该算法首先利用权重迭代方法产生一组均匀分布的权重向量，随后利用该权重向量对偏好区域进行映射，消除参考点位置对算 法 性 能 的 影 响，如 图 ８ 所 示［５８］．ＭＯＥＡ／Ｄ－ＰＲＥ算法还提出了一种新型的偏好区域模型，该模型可以根据 ＤＭ 的偏好信息动态调整偏好区域的大小．此外，在高维问题上，ＭＯＥＡ／Ｄ－ＰＲＥ 算法也具有优越的性能．图 ８　ＭＯＥＡ／Ｄ－ＰＲＥ算法［５８］Ｈｕ等人［５９］提 出 的 基 于 权 重 向 量 选 择 机 制 的Ｐ－ＮＳＧＡ－ＩＩ（Ａ　Ｐｒｅｆｅｒｅｎｃｅｂａｓｅｄ　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅＥｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　ｕｓｉｎｇ　Ｐｒｅｆｅｒｅｎｃｅ　ＳｅｌｅｃｔｉｏｎＲａｄｉｕｓ）算法，有效缓解了基于 Ｐａｒｅｔｏ占优关系的偏好算法随目标维度增加算法整体性能急剧下降的问题．该选择机制分为两部分，首先根据权重向量及偏好半径构建偏好区域，将整个目标空间划分为偏好区域和非偏好区域两部分；其次通过 Ｐａｒｅｔｏ支配关系在偏好区域中选择最优解，若所获得偏好解的数量未达到 ＤＭ 的要求，则依次在非偏好区域内选择与参考向量距离最小的解直到满足 ＤＭ 的要求，如图９（ａ）所示［５９］．Ｚｈａｎｇ等人［６０］提出一种基于权重向量的偏 好ＭＯＥＡ，该算法首先将均匀分布的权重向量映射到偏好点附近，随后根据映射后的权重向量搜索偏好点附近的 Ｐａｒｅｔｏ最优解．然而，映射后的权重向量并不能 搜 索 到 偏 好 点 附 近 的 Ｐａｒｅｔｏ 最 优 解．文中证明了解的搜索方向不是映射后权重向量 ｗ′ｉ＝（ｗ′ｉ１，…，ｗ′ｉｍ）的 方 向，而 是 沿 着λｉ＝ （１／ｗ′ｉ１，…，１／ｗ′ｉｍ）方向进行搜索．为能有效搜索到偏好点附近的 Ｐａｒｅｔｏ最优解，需要将映射到偏好点附近的权重向量ｗ′ｉ＝（ｗ′ｉ１，…，ｗ′ｉｍ）修改为λｉ＝（λｉ１，…，λｉｍ），其中λ′ｉ＝１／ｗ′ｉ，λｉ＝λ′ｉ／∑ｍｉ＝１λ′ｉ，如图９（ｂ）所示［６０］是由权重向量ｗ 的方向搜索到的偏好解．图 ９　权重向量调整［５９－６０］ＲＶＥＡ（Ａ　Ｒｅｆｅｒｅｎｃｅ　Ｖｅｃｔｏｒ　Ｇｕｉｄｅｄ　ＥｖｏｌｕｔｉｏｎａｒｙＡｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｍａｎｙ－Ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ）［２６］是一种由参考向量引导的偏好 ＭＯＥＡ．该算法产生若干个均匀分布的权重向量，将目标空间划分为与权重向量数量相等的若干个子空间，通过精英选择策略和角度惩罚距 离 ＡＰＤ（Ａｎｇｌｅ－Ｐｅｎａｌｉｚｅｄ　Ｄｉｓｔａｎｃｅ）机制在各个子空间中进行搜索，使得子种群中的最优解能够快速向 Ｐａｒｅｔｏ前沿收敛．同时结合基于偏好的参考向量生成方法，根据 ＤＭ 的要求确定中心参考向量ｖｃ和偏好半径ｒ，通过式（１６）的变换生成若干子空间中的参考向量．ｖ′ｉ＝ｒ·ｖｉ＋（１－ｒ）·ｖｃｒ·ｖｉ＋（１－ｒ）·ｖｃ（１６）其中，ｖｃ是单位向量，半径ｒ∈（０，１），ｖｉ是均匀分布的参考向量，ｖ′ｉ是由ｖｉ转化得到的子空间中的参考向量，ＤＭ 的偏好区域由ｖｃ和ｒ 确定．通过参考向量６期 王丽萍等：偏好多目标进化算法研究综述２１７９