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

mytomorrow

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

• ①特征选择
• ②模式挖掘
• ③关键节点检测
• ④神经网络训练
  

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

& y: s0 @* j8 D) ]具体问题
+ y# ]3 }- p- V' X& |/ v

; [( x$ s, s  R6 r. ]& H6 l* d: A

, I, Z* l1 y4 ^% \! _  y3 G; o
6 H& w; w2 n8 B4 j1 _
( E4 y  l# W5 x算法的贡献

• ①设计了新的种群初始化策略（根据稀疏大规模特性，能够获得一个很好的前沿面）
• ②设计了新的基于pareto解集稀疏性的遗传算子
  

具体算法

: s% [; g+ J7 o. Z; u- ]" b: M算法框架

类似于NSGA2的框架

7 w7 X& D: P: s8 d
7 S, a5 u. e/ C+ q
- E* J# \! W6 ^
  J7 n4 Q+ n  h5 j& Z初始化策略
- X9 z4 u$ u' f0 t0 X. ~# E
( Y7 m+ G! }$ V- n为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。
: i  ?6 b2 b0 I$ n! g


经过初始化后的结果：
3 ^5 V/ y( b: x

: z' x, z" N" a# R" f! z
可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。


1 p2 ~& @8 y9 P+ f+ H- W4 r8 s3 G9 B0 E0 c交叉变异算子

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



7 W( H! M/ v7 ]) ?! ]  V" q* F采用交叉变异后的结果：
& \- J% q3 h4 j6 @  w- W


可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。


其他
# U/ A: N3 `/ |9 @$ P
9 N" f0 k) R- g, J对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。

Touuqu

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

youOK

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

xiaogegepcb

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