基于SOM聚类和自适应算子选择的高维多目标进化算法

钟沛龙，黎 明，何 超，陈 昊

（1.南昌航空大学信息工程学院，江西南昌 330063；2.南昌航空大学无损检测技术教育部重点实验室，江西南昌 330063；3.南京航空航天大学自动化学院，江苏南京 211106）

1 引言

在实际生活中，多目标优化问题存在于各类现实场景中，往往存在多个彼此相互冲突的目标，其中当目标个数为4 个及4 个以上时，多目标优化问题又被称为高维多目标优化问题（Many-Objective optimization Problems，MaOPs）［1］.为了有效地求解高维多目标优化问题，现有的文献采用了多种策略来增强高维多目标进化算法的性能［2～4］，例如引入新的指标策略［5～7］、构造新型支配关系［8～11］等.

现有方法主要将工作集中在如何去平衡算法的收敛性和多样性，并保持向Pareto 前沿的选择压力.如NSGA-III［12］利用分解的思想来保持种群的多样性，并且使用Pareto 支配加快种群的收敛速度；ε-MOEA［13］利用ε-支配和网格框架在环境选择准则中提出了收敛性和多样性度量来保存精英个体进入存档；KnEA［14］，RVEA［15］和MOEA/DDU［16］等也是如此.然而上述算法并没有考虑种群个体的数据结构信息及个体间的相似性.尽管部分基于种群个体数据结构信息的多目标进化算法被提出，但它们主要利用邻域关系发掘多目标优化问题的个体结构，此外仅采用此类结构信息，并不能最有效地产生优质个体，具有一定的局限性.如基于多目标优化的细胞遗传算法（Cell genetic algorithm based on Multi-Objective optimization，MOCell）［17］通过将每个个体置于一个网格结构的元胞中来构建个体之间的邻域关系，其中每个个体仅同它的邻域个体交互产生新个体，该方式对目标空间的搜索能力有限；基于规则模型的多目标分布估计算法（Regularity Model based Multi-objective Estimation of Distribution Algorithm，RMMEDA）［18］应用主成分分析方法（Principal Component Analysis method，PCA）［19］将Pareto 集划分为若干个不相交的类，在每个类中开展主成分分析并建立概率模型，并在模型中抽样产生新个体以更新种群，然而类的数目K值难以设置，不同的K值，对算法性能的表现影响较大.

现有文献显示，利用相似个体作为父代进行重组能够显著提高子代个体的质量，并提高算法的搜索效率［20，21］.另外，聚类算法是一类将未知标签的数据对象集进行分组的无监督学习方法，其分类的结果能够保证同一类的数据对象间的相似性较高，不同类的数据对象间的相似性较低［22］.并且，聚类算法仅利用数据本身的特征以及数据之间的相似性关系进行分类.因此自组织映射网络（Self-Organizing Map，SOM）模型能够通过无监督学习的方式对来自高维输入空间的训练点产生低维的表征，并保持输入数据间的近邻关系，从而实现聚类的目的.综上所述，SOM模型能够通过聚类的方式保持种群个体原有的拓扑逻辑关系，并可以自动地根据个体的相似性构建邻域结构.因此本文提出了一种基于SOM 聚类和自适应算子选择的方法（SOM Clustering and Adaptive Operator Selection，SCAOS）并将其作用于高维多目标进化算法中.与现有的基于数据结构的方法不同，SCAOS 可以更好地利用种群个体的数据结构信息及个体之间的相似性来增强高维多目标进化算法的性能.SCAOS 的主要贡献在于：（1）采用SOM 聚类算法提取数据结构信息，获得个体间相似性，将每个个体与相应的神经元相关联，相似个体分配到相邻神经元；（2）在类内利用个体支配信息进行自适应算子选择来产生优质子代引导个体重组，增强算法性能；（3）将提出的重组方法与环境选择策略相结合，增强了种群个体的多样性和收敛性.

2 相关工作

自组织映射网络模型由Kohonen［23］提出，是一种无监督学习的神经元网络模型，可以将输入的n维空间数据映射到一个较低的维度输出，并能够保持数据原有的拓扑逻辑关系.SOM 这类基于自组织映射的神经网络，已经被广泛应用于数据聚类［24］、图像分割［25］、数据可视化［26］等实际应用中.在处理多目标优化问题方面，根据SOM 的使用方式不同，基于SOM 的多目标进化算法被分为两类：第一类是直接应用SOM 模型产生新解，第二类是利用SOM引导算法的搜索.

在第一类中，Hakimi-Asiabar 等［27］使用精英个体对SOM 模型进行训练，然后将被训练后的SOM 输出层神经元的权值作为新产生的解，提高了产生优质新解的效率.Zhan 等［28］利用SOM 来学习多目标优化问题Pareto解集的流型结构，然后通过均匀随机扰动SOM的神经元权值的方式来产生新个体以提高算法在目标空间中的探索能力.在第二类中，Norouzi等［29］使用NSGA-II先进化一定代数以对目标空间进行初步勘探，然后利用SOM 将种群划分到若干个子种群中，每个子种群独立开展遗传操作并且进化若干代，有效提高了算法的搜索性能.Gu等［30］提出了一种基于SOM 的权值向量设计方法，在基于分解的MOEA 的权值向量设计中利用SOM网络来发现个体在目标空间的分布.

以上研究表明，SOM 网络模型不仅能够通过提高产生个体的质量来增强算法在处理多目标优化问题时的性能，而且还可以通过引导算法搜索使优质的个体向着Pareto前沿移动，进而提高多目标优化算法的搜索效率.此外，利用SOM 进行聚类的方式较为简单，无需设置初始类个数，对初始数据不太敏感.因此，基于SOM 的多目标进化算法能够适用于各种复杂多目标问题的处理，具有较好的应用前景.图1 所示为典型的SOM拓扑结构，输入层为n维空间，输出层为二维空间，每个神经元u上都有其对应的权值向量神经元权值的维数等于目标个体的维数.

图1 典型的SOM拓扑结构

可以通过竞争与合作的方式来对SOM 网络进行训练.

（1）竞争：输入个体X，根据个体X与神经元的欧氏距离判断获胜神经元，当欧氏距离最小时，此神经元即为获胜神经元，求解如下：

u′为当前个体Xc的获胜神经元，其中，1≤c≤N.

（2）合作：在训练过程中，除了更新获胜神经元的权值，还要更新与获胜神经元邻近神经元的权值.表达式如下：

其中，U为获胜神经元u′的邻近个体集合，σ为邻域半径，τ为当前训练的学习率，u∈U.

3 基于SOM 聚类和自适应算子选择的高维多目标进化算法

3.1 SOM聚类

本文利用SOM 网络特性来有效提取个体数据信息，获得个体间相似性，并得到相似个体的集合.算法1为SOM聚类算法的具体框架.

在算法1 中，Tmax和t分别表示最大迭代次数和当前迭代次数.SOM 聚类算法先对网络神经元的权值向量W及神经元邻域半径σ0进行初始化操作（第1 行）.然后通过阈值δ限制学习率及邻域半径的更新策略来训练权值向量，其具体步骤为：首先学习率从τ0降低到δ，邻域的大小从σ0降低到σ，持续优化权值向量，使得输出层能够表示出输入个体的分布情况；然后学习率τ0降低到δ后进一步减小，而邻域σ则保持不变，这种方式能够自动优化网络结构，可以在一定程度上保持个体分布的多样性（第5～10行）；再通过式（1）获取当前个体最接近的神经元u′，由式（2）获得邻近神经元集合U，式（3）更新邻近神经元的权值向量Wu（第11～16行）；最后将每个个体与神经元关联，相似个体将被分配到邻近神经元，得到相似个体集合Xu（第19～22行）.

3.2 自适应算子选择

在多目标优化过程中，相似个体之间重组，能够提高产生新个体的质量，增强算法的局部搜索能力［20］.本文依据此特点，设计一种自适应算子选择方式，充分利用相似个体数据信息产生高质量的子代，引导算法在目标空间中的搜索.其利用SOM网络得到的相似个体集合，建立父代交配池，根据交配池内个体支配信息选择重组算子，产生优质子代.具体步骤如算法2所示.

在算法2中，首先根据相似个体集合Xu，获得当前个体交配池MP，大小设置为S（第2 行）；然后获得当前交配池内个体支配信息（第3 行和第4 行）；最后根据个体支配信息选择算子，若个体均互不支配，从交配池内随机选择2 个作为父代个体进行重组产生子代y，否则，从相似个体集合随机选取2个不同于当前个体的个体作为父代个体进行重组产生子代y（第5～11行）.本文同时引入2种不同的重组算子，分别应用在交配池内和相似个体集合中产生子代，具体如算法3和算法4所示.

算法3为在交配池内选择父代个体进行子代生成.首先在交配池内选取2 个父代个体Xa，Xb；其次采用模拟二进制交叉算子（Simulated Binary Crossover，SBX）［31］产生子代y′；然后为了防止新产生的子代y′超出个体的边界值，对其进行修正为y″；最后通过多项式变异操作［32］产生最终的子代y.

算法4 为在相似个体集合选择父代个体进行子代生成.首先在相似个体集合中随机选择2 个不同的个体Xa，Xb和当前个体X作为父代个体；其次采用差分进化交叉算子（Differential Evolution，DE）［33］产生子代y′；然后修正y′为y″；最后由多项式变异生成子代y.

值得注意的是，相较于比较所有个体，在交配池内进行比较可以有效减少计算复杂度并提取个体之间的相互信息，更加有利于优质个体的产生.此外，为了保持最终产生的子代个体数为N，在进行SBX交叉算子操作时只产生1个子代.

3.3 MaOEA-SCAOS算法描述

MaOEA-SCAOS 如算法5 所述.首先初始化种群P、神经元权值向量W和训练集TS；其次利用SOM 聚类算法获得相似个体集合Xu；然后通过集合Xu，构建邻域交配池，通过自适应算子选择操作重组生成优质子代；最后通过环境选择策略选择个体更新种群.值得注意的是本文环境选择策略框架为NSGA-Ⅲ算法中环境选择框架.NSGA-Ⅲ［12］是最著名的进化多目标优化算法之一.它是在NSGA-Ⅱ［34］的基础上进一步提出的，该算法的基本算法框架和NSGA-Ⅱ算法相似，但是在选择算子上进行了改进，它通过提供和自适应更新一组预定义的参考点来维持种群个体间的多样性.由于文章篇幅限制，NSGA-Ⅲ的环境选择策略的详细步骤见文献［12］.另外在算法5 的第7行，TP 表示暂时保存训练好的个体，用于训练集TS的更新（第24 行），可以有效减少SOM 网络的训练时间.

4 实验仿真与分析

为了验证本文算法（MaOEA-SCAOS）的有效性，选取2 种利用个体数据信息的多目标进化算法（MOCell［17］，RM-MEDA［18］）和3 种多目标进化算法（NSGA-Ⅲ［12］，MaOEA-CSS［35］，KnEA［14］）与本文所提算法进行对比分析.所有的算法均是在多目标进化算法开源平台PlatEMO［36］上运行.

4.1 测试问题与性能指标

在实验中，采用DTLZ 测试问题集和WFG 测试问题集.DTLZ 测试问题集都有n=M+k-1 个决策变量，其中M为目标维数.根据文献［37］中的决策变量设置建议，DTLZ1 中设置k=5，DTLZ2-DTLZ6 中设置k=10，DTLZ7 中设置k=20.WFG 测试问题集中所有决策变量个数n=k+l，其中设置k=M-1，l=10.

为了验证MaOEA-SCAOS 获得的近似Pareto 前沿的收敛性和多样性，在实验研究中采用反世代距离（Inverted Generational Distance，IGD）和超体积指标（Hyper-Volume，HV）.HV 指标表示的是被种群中所有个体支配并且以参考点R为边界的区域，其表达的是非支配个体覆盖的目标空间区域大小.给定参考点R，获得的种群个体P*，那么关于参考点R的超体积定义为

其中，L为Lebesgue 测度，|S|表示种群个体P*支配R的数目，vi表示参考点与种群中第i个个体构成的超体积.从HV 定义可看出，HV 指标的值越大，算法求得的种群质量越高，算法性能优化效果越佳.

IGD 指标定义为每个参考点与其最近个体距离之和的平均值.其公式定义如下：

其中，dis(x，y)表示个体与参考点间的欧氏距离，由算法获得的种群个体记为P*，P为真实的Pareto 前沿面均匀采样得到的一组参考点，|P|为分布在真实Pareto 前沿面上种群P的规模.IGD的值越小表示所得种群个体越是靠近真实PF，个体分布越均匀.IGD 指标既可以评价收敛性，也可以评价多样性.

4.2 实验参数设置

（1）种群大小N：本文采用文献［12］中设置的方法.并且为了公平对比，其他算法的种群规模设置相同.所有算法种群大小设置如表1所示.

表1 种群大小设置

（2）终止条件：算法运行一次的终止条件是最大评价次数.最大评价次数等于种群规模乘以最大迭代次数.本文在3目标和5目标的最大迭代次数设置为500，在8目标和10目标上设置为1 000.

我国爬升模板的研发晚于国外发达国家，80年代末，爬模施工技术应用于桥梁及高层建设。至今爬模施工技术方法得到了明显的提升。在很多桥梁高层建筑施工中应用得到广泛推广。但对爬模的研发及施工工艺方面与国外发达国家相比仍存在很大差距。国内爬模设备模块化及规范化水平不高，需向国外先进的爬模工艺技术学习。

（3）统计方法：所有算法在每个测试问题上均独立运行20 次，对MaOEA-SCAOS 算法和其他对比算法获得的结果采用Wilcoxon 秩和检验方法进行比较，其中均值分析的显著性水平设置为5%.根据Wilcoxon 秩和检验方法，其中“+”表示对比算法所得结果要优于MaOEA-SCAOS，“-”表示对比算法所得结果要劣于MaOEA-SCAOS，“=”表示对比算法和MaOEA-SCAOS 获得的结果没有明显的差异.

（4）对比算法主要参数设置：对于MOCell和NSGA-Ⅲ中DE 运算符的控制参数F和CR 分别设置为0.3和0.2；在RM-MEDA 中，本地PCA 算法中的簇数K设置为5；在MaOEA-CSS 中，环境选择的阈值t大小设置为0；KnEA 的参数设置参照文献［14］；本文算法MaOEASCAOS中初始SOM 学习率τ0、交配池大小MP和学习率下降阈值δ分别设置为0.9，5和0.1.

（5）交叉和变异算子设置：在MaOEA-SCAOS 算法中SBX 分布因子η设置为20，DE控制参数F和CR分别设置为0.5和1.多项式变异的变异分布因子ξ均设置为20，变异概率ρ均为1（n代表决策变量数目）.

4.3 参数分析

以DTLZ1～DTLZ7 测试问题作为目标函数进行分析，使用不同参数的MaOEA-SCAOS 对每种测试问题运用IGD 性能指标值随性能评价次数的变化进行分析，其中详细分析了交配池大小MP和阈值δ.

4.3.1 交配池大小MP分析

为了客观评价交配池大小对算法的影响，本文选取3，5，10，15和20 五种不同大小的交配池，并设置相同的其他参数来验证交配池对算法的影响.图2 显示了MaOEA-SCAOS 在DTLZ1，DTLZ3，DTLZ6和DTLZ7测试问题上独立运行20次后的平均IGD 指标值随着评价次数的变化曲线.从图2 可以看出，不同的MP 在不同测试问题上有着不同的性能，其中较大的MP所得算法性能较低，较小的MP 所得算法性能较优，故较小的交配池适合MaOEA-SCAOS 算法.可以看出，当MP=5时，MaOEA-SCAOS 所呈现的收敛性能较好，故本文所设置交配池大小为5.

图2 不同交配池大小在DTLZ测试问题独立运行20次平均IGD指标值

4.3.2 阈值δ分析

不同阈值δ，决定了邻域的多样性分布情况，最终会影响算法的收敛性.为了获取最佳阈值参数，选取阈值大小为0.1，0.3，0.5，0.7来进行验证，其他参数设置相同.图3 显示了MaOEA-SCAOS 在DTLZ1，DTLZ3，DTLZ6和DTLZ7测试问题上独立运行20次后的平均IGD指标值随着评价次数的变化曲线.由图3可以看出，较小的阈值得到算法的收敛性较优，故本文设置阈值δ大小为0.1.

图3 不同阈值大小在DTLZ 测试问题独立运行20 次平均IGD 指标值

4.4 计算复杂度分析

本小节分析MaOEA-SCAOS 算法在一代内的最坏情况总体计算复杂度.在SOM 聚类阶段，首先训练阶段通过个体寻找最近神经元对其权值向量进行更新；其次聚类操作将每一个个体与最近神经元相匹配，将相似个体分配到邻近神经元，因此该过程的计算复杂度为O(N2)，其中N为种群个体数量.在自适应算子选择阶段，首先考虑交配选择，对于一个个体规模为N和M目标的优化问题，构建交配池大小MP 需要O(MN·MP)；其次交叉变异对父代个体的每个决策变量，产生N个后代需要O(DN)的运行时间，其中，D为决策变量的个数.在环境选择阶段，在最坏的情况下需要O(MN2)的运行时间.其他操作的复杂度较小.因此，MaOEA-SCAOS 在一代内的最坏情况总体计算复杂度为O(MN2).MaOEA-SCAOS算法在计算上非常高效.

4.5 算法在WFG问题上对比分析

表2和表3 分别给出了6 个算法在WFG1-WFG9 测试问题上进行20 次独立计算HV和IGD 指标的实验结果，其中表2 汇总了对比算法所获得HV 值的均值和标准差（括号内为标准差），表3 汇总了对比算法所获得IGD值的均值和标准差（括号内为标准差），其中用黑色粗体突出最好的结果.

表2 6种算法在WFG1～WFG9测试问题上获得的HV指标值的实验结果

表3 6种算法在WFG1～WFG9测试问题上获得的IGD指标值的实验结果

续表

续表

综合HV和IGD 指标的统计数据分析结果，对算法在WFG问题上的性能进行对比分析.WFG1具有复杂的Pareto 前沿，MaOEA-SCAOS 在3和8 目标问题上的IGD指标相较其他对比方法具有较好的竞争力.WFG2具有凸面不连续且多模态的Pareto 前沿，MaOEA-SCAOS 的HV指标值在3和5目标上获得最优性能，具有较好的鲁棒性.WFG3 具有线性退化的Pareto 前沿，MaOEASCAOS 算法的HV 指标结果在8 目标取得最优，并且在IGD指标上也具有一定优势.WFG4～WFG9在决策变量空间中的设计存在不同的困难，其中WFG4具有凹型和多模态的Pareto 前沿，WFG5加入欺骗性特征，WFG6具有不可分离且缩放的Pareto 前沿，WFG7 具有参数依赖性的可分离单峰，WFG8 在WFG7 基础上增加了不可分特性，WFG9具有以上测试问题特征，因此WFG4～WFG9测试问题在多目标进化算法极具挑战性.对于WFG4和WFG5测试问题，MaOEA-SCAOS在HV指标上均获得最优性能，这表明对于具有凹面的多目标优化问题，本文方法具有较好的可靠性.图4展示了各个算法获得的非支配解在WFG4 上3 目标实例中的分布情况，其中MaOEA-SCAOS算法获得的非支配解集较好地平衡了收敛性和多样性.对于WFG6测试问题，MaOEA-SCAOS大体上优于其他算法，仅在5 目标问题上性能略差于NSGA-Ⅲ算法，由图5可以看到，各个算法获得的非支配解在WFG6 上8 目标实例中的分布情况，可以看出MaOEA-SCAOS获得的非支配解优于其他对比算法.对于WFG7和WFG8 测试问题，MaOEA-SCAOS 在处理3，5，8和10 目标时性能表现突出，说明在WFG7和WFG8测试问题上处理不同目标数目的普适性较好.此外，在WFG9 问题的测试中，本文算法也表现出一定的竞争力.综上所述，可以看出MaOEA-SCAOS在WFG测试问题集上性能显著且在处理不同目标优化问题时普适性较高.

图4 WFG4问题3目标上获得的非支配解

图5 WFG6问题8目标上获得的非支配解

4.6 算法在DTLZ问题上对比分析

表4和表5 分别给出了6 个算法在DTLZ1～DTLZ7测试问题上进行20 次独立计算HV和IGD 指标的实验结果，其中，表4 汇总了对比算法所获得HV 值的均值和标准差（括号内为标准差），表5 汇总了对比算法所获得IGD 值的均值和标准差（括号内为标准差），其中用黑色粗体突出最好的结果.

表4 6种算法在DTLZ1～DTLZ7测试问题上获得的HV指标值的实验结果

表5 6种算法在DTLZ1～DTLZ7测试问题上获得的IGD指标值的实验结果

续表

续表

综合HV和IGD 指标的统计数据对算法在DTLZ问题上的实验结果进行分析.由表4 可以看出，在具有规则形状的Pareto 前沿的DTLZ1～DTLZ4 测试问题上，MaOEA-SCAOS在HV性能指标均获得较优的性能，这表明算法对具有规则的Pareto前沿面的优化问题具有较好的可靠性.图6 展示了各个算法获得的非支配解在DTLZ4上10目标实例中的分布情况，MaOEA-SCAOS算法的搜索能力并没有受到目标个数增加的影响，依然表现出较强的性能.值得注意的是，在具有凹且退化特征的DTLZ5和DTLZ6 上，MaOEA-SCAOS 能够获得与NSGA-Ⅲ算法相似的性能，并且其在DTLZ5 测试问题8目标和10目标上的指标优于NSGA-III.这说明MaOEASCAOS相较NSGA-III更适合处理具有退化Pareto前沿的高维问题.对于具有混合特征Pareto前沿的DTLZ7测试问题，算法MaOEA-SCAOS 较难处理的主要原因在于没有采用自适应特征点的环境选择策略.综上可以看出，MaOEA-SCAOS在DTLZ测试问题集中具有规则形状PF的目标问题上具有良好的可靠性，能够保持种群的收敛性和多样性；在不规则的PF上不同目标维数中仍然能够保持算法的鲁棒性，能够较好地处理不同形状Pareto前沿的问题.

图6 DTLZ4问题10目标上获得的非支配解

5 总结

针对在多目标优化问题中高维多目标优化算法的搜索效率及收敛效率降低，无法产生高质量的子代个体去引导种群搜索的问题，本文提出一种基于SOM 聚类和自适应算子选择的方法作用于高维多目标进化算法.该方法首先利用SOM 网络特性，训练提取种群个体结构信息，获得相似个体集合，构建邻域交配池；然后通过交配池内支配信息进行自适应算子选择，重组产生优质子代引导种群搜索；最后，引入NSGA-Ⅲ算法中环境策略，更新种群，以提高种群的多样性和收敛性.与现有的高维多目标优化算法进行实验对比，结果表明，本文所提出的个体重组方式的有效性优于同样利用个体结构信息的其他多目标优化算法.此外，与现有的其他算法相比，本文算法在所有基准测试函数中均具有较强的竞争力.