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

mytomorrow

论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
1 C/ L, H+ H% ]" M2 e( E9 c2 O" T- J作者主要讨论了四个具体的问题

• ①特征选择
• ②模式挖掘
• ③关键节点检测
• ④神经网络训练
  & y$ J  O& r! x% [# U4 B+ i

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

具体问题
8 O* h' e/ M: F3 k7 T3 l* n





9 c3 u2 R. q+ y$ Q算法的贡献

, ^" u) b; z& `' A

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

1 q; M% x( E5 [% g9 J; t, o
9 m9 y; r. l# c具体算法

算法框架

类似于NSGA2的框架
% i, h$ L. h7 P5 M2 [) Q' M6 g. b

. ?2 o. `7 R* |( o" T, `' `& P" y
3 v8 h8 F! F6 d9 U1 y) {% \# S8 ~) |
% j5 v( p3 o! C; k/ C# V% E1 S初始化策略
- `. ]! x6 }! }7 L( Y7 W7 X- R
4 z+ s. z: A8 X' H! _9 D2 n为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。


. P, V1 M5 U$ x  P9 n& u4 H# _9 G1 V
经过初始化后的结果：

' m" s& L$ j" [

& \. `$ p& @8 x5 [( |可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。

& c" M. i0 w1 i: V
. s2 Y$ `7 F) t* c5 b+ b, ]" A交叉变异算子
6 ^2 H7 H( k$ K
: p* T+ A2 Y( A7 n$ A$ _! R这个交叉变异是算法的核心，它每次在二进制向量mask中，以同样的概率每次在0元素中翻转一个元素，或者在非0元素中翻转一个元素，翻转是根据决策变量的适应度值进行的。因此，生成的子代不会有同样数量的0和1，并且可以保持子代的稀疏度。
) \' @* J/ U5 u" _

9 G" n+ x: n3 O" M
采用交叉变异后的结果：
3 R9 {0 g" g; i9 j7 Z2 H0 \1 C5 y
. g' o# j5 {5 A
, X! f2 `( s( |' F: q( o0 T, X
) A4 |. D- f  C; |可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。

) J. M0 u$ ~  E) `
其他

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

Touuqu

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

youOK

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

xiaogegepcb

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