基于稀疏大规模矩阵的多目标进化算法简介

mytomorrow · 发表于 2021-7-13 10:22

EDA365欢迎您登录！

您需要登录才可以下载或查看，没有帐号？注册

x

论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
作者主要讨论了四个具体的问题

①特征选择
②模式挖掘
③关键节点检测
④神经网络训练 A, ?- p$ a i) o3 o% N

上面四个问题虽然存在于不同领域，但是它们都属于多目标问题，它们的pareto面的解集都是稀疏的。举例来说，对于大规模特征选择问题，10000维中只能选取不到100个，压缩率达到了99%，是典型的稀疏问题。

具体问题

算法的贡献

①设计了新的种群初始化策略（根据稀疏大规模特性，能够获得一个很好的前沿面）
②设计了新的基于pareto解集稀疏性的遗传算子" K* X, c; x) i: k

具体算法

算法框架

类似于NSGA2的框架

初始化策略

为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。

经过初始化后的结果：

可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。

交叉变异算子

这个交叉变异是算法的核心，它每次在二进制向量mask中，以同样的概率每次在0元素中翻转一个元素，或者在非0元素中翻转一个元素，翻转是根据决策变量的适应度值进行的。因此，生成的子代不会有同样数量的0和1，并且可以保持子代的稀疏度。