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

mytomorrow

; Y+ d0 T: @6 Q( c+ m6 b论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
6 }: j2 b) n) h2 M; ?作者主要讨论了四个具体的问题
( i  R. @+ V& ?. Y; L# {$ g! T/ j

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

上面四个问题虽然存在于不同领域，但是它们都属于多目标问题，它们的pareto面的解集都是稀疏的。举例来说，对于大规模特征选择问题，10000维中只能选取不到100个，压缩率达到了99%，是典型的稀疏问题。
$ L  a9 Q5 q7 W3 e* t/ {0 I
具体问题
2 R6 ]& M/ e, J" O+ `% X

1 s/ R& ~& X; A5 m" `% [. D! J

5 q9 _. w0 R0 Y
, l- `! Q( J6 G8 \/ ~& Z( [& M
算法的贡献
3 I( Q- V  p; c* i

• ①设计了新的种群初始化策略（根据稀疏大规模特性，能够获得一个很好的前沿面）
• ②设计了新的基于pareto解集稀疏性的遗传算子
  : p3 {( d8 q* B% f2 J  c9 H8 U

# E1 d: p/ }5 W* K* J) h$ _8 A; |
) x7 j9 D  Z# O3 J( m4 M' L具体算法

算法框架
$ G+ J$ L6 I) y& p1 s, @
类似于NSGA2的框架


3 N* z4 `6 O2 t3 t1 ]) H4 n

初始化策略
! J: ^  T3 \: v7 [0 {7 |1 B' w3 a
为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。



经过初始化后的结果：
( n4 ^5 R6 r+ g9 T) r1 `6 }


可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。
/ w' }# ^5 s, B# z. a( v& p3 @
" y' ]/ f+ t- s+ p6 ^' p
) S: C- \/ s& n1 A交叉变异算子

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

; }: o2 r6 z4 w, J" m" `

采用交叉变异后的结果：
* I) h6 x; A" |& K' A/ G7 Q4 L

7 Q' g3 ^, v1 s% {+ r
% e& k& `& J7 _可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。


/ }5 i# _1 k! F$ Y其他

对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。

Touuqu

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

youOK

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

xiaogegepcb

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