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

mytomorrow

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

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

上面四个问题虽然存在于不同领域，但是它们都属于多目标问题，它们的pareto面的解集都是稀疏的。举例来说，对于大规模特征选择问题，10000维中只能选取不到100个，压缩率达到了99%，是典型的稀疏问题。
# r1 @8 ]; ^! [& ~0 F+ R, E
9 B  ^8 l' m8 j$ S具体问题
* m( D( u- I& g9 V8 r  Z
+ S  Q" O0 d  C4 B. e# q" `
3 i4 |4 k7 Y2 }% |  L



算法的贡献
# A; G( a" H; z7 ?

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

具体算法
9 c$ J, O1 e2 _1 E1 d- @( T
' u& T: Q+ [0 h! p% p  Z* \算法框架
) D; H3 F) e; M# `; p0 f
类似于NSGA2的框架
, h' j! V/ p- c& T  U$ E; l  m0 V5 T


9 k. M! {/ a9 u9 l' i8 p* M
初始化策略
& J5 l7 s+ o, t
为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。
6 r4 W! ~- q# U& x6 {% @8 r
2 i- T" ]( |  o) @0 M. W6 F
9 w; x3 [6 J2 C& p
0 ]" k) @7 |& r/ H经过初始化后的结果：
) a. K% t' J3 j, O
8 L8 U% G: K, ~9 u' [
" F/ j: g+ c/ ~/ o2 V5 J' M
% `( U  Z  H! T" F6 c7 ], f可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。
! n5 ]6 c# I% P: f4 R

. V0 M3 ]0 s2 L' ]2 K0 x) L& @8 g9 ]交叉变异算子

' Z* U4 J" g( {# g- D4 S, t( B这个交叉变异是算法的核心，它每次在二进制向量mask中，以同样的概率每次在0元素中翻转一个元素，或者在非0元素中翻转一个元素，翻转是根据决策变量的适应度值进行的。因此，生成的子代不会有同样数量的0和1，并且可以保持子代的稀疏度。
, T; _5 m) f+ Z
5 T: J7 |+ ~0 L

采用交叉变异后的结果：
3 J2 F" I2 B" K8 ^# r
4 }8 t1 r$ }4 y1 b
- x2 h4 X  m# f. i3 `
可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。
- l9 Q, u, y  a  d0 g+ n0 }' a

1 a8 Q  g. U8 P$ M  |其他
7 e( a( T# c; B0 a# P; S
$ U: Q% [. p/ V, L对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。

Touuqu

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

youOK

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

xiaogegepcb

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