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

mytomorrow

论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
. M4 j3 I6 h% B2 l# q8 `作者主要讨论了四个具体的问题
9 d( G( @- X% Q3 b" p6 S4 f$ X1 v

• ①特征选择
• ②模式挖掘
• ③关键节点检测
• ④神经网络训练
  6 m; S! j; x1 i; u

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

具体问题
! N& W9 m9 q$ Q' k7 x' B

  S. f: _. F" f& N+ M. ?1 R
9 m1 ]! g' o0 d


2 y. c7 P7 ^& a算法的贡献

, K+ C2 n- ^. Y/ G* a

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

$ O3 o& K2 k+ [; w具体算法

% S) e* V2 a2 }" G9 q算法框架
) `/ a: K2 n, }5 m% J& Q2 ^
类似于NSGA2的框架
3 R$ ~/ O$ c, E5 P- {* [( ?2 |

2 `8 N) x9 L  |0 y6 X' v

# A7 f8 W4 `! |8 a3 k初始化策略

, W) V+ F8 Z5 Z- I/ a$ z$ r* \' K# r为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。
! X7 F$ I! l, d4 ^( L6 |
' ]: C& F4 T# R
7 H7 o4 M8 A+ ?8 B+ n- m- j
经过初始化后的结果：

" j4 E6 u! |3 E  h( Q/ z  P

- @$ k3 x8 t! X# E- E7 J可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。
8 z, x9 P# G9 P: K$ g) C+ ~
) D8 n, \3 T8 o  Y; i3 F
交叉变异算子
; p* s) c/ e. ^8 s& e
这个交叉变异是算法的核心，它每次在二进制向量mask中，以同样的概率每次在0元素中翻转一个元素，或者在非0元素中翻转一个元素，翻转是根据决策变量的适应度值进行的。因此，生成的子代不会有同样数量的0和1，并且可以保持子代的稀疏度。



" T- Q3 m+ ?9 L, Y0 K7 F# _采用交叉变异后的结果：
& G3 A% f8 `- h( p: Z

% {; o) G; n& K) ^3 p$ N
5 T) [; F4 ~4 A( c可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。
! f$ J1 j! }3 S

) R+ n* `) @% I5 i5 Z5 C% j7 I6 }其他
! X8 d7 }; P3 {
% R# i: V9 G) I( ?# e* v对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。
  ~+ r) _7 {9 r; M& C0 P

Touuqu

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

youOK

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

xiaogegepcb

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