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

mytomorrow

论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
: I: G" G( v8 a( P% z作者主要讨论了四个具体的问题

• ①特征选择
• ②模式挖掘
• ③关键节点检测
• ④神经网络训练
  , k- N0 F  W& s' w

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

; {2 ~7 f$ y8 O' Q" y: Z


8 k7 M' e8 r  F2 g$ x
, i# z* `5 s  \
算法的贡献
8 A1 E( E' U; h+ G' g' x( }. h
( s& ^# ]$ A; F% E& K

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

3 k2 A6 ]) r& t2 n! E具体算法

算法框架
. \9 y, x1 U0 q
8 J3 Y+ i& w4 u1 |1 O2 u  P类似于NSGA2的框架


; d, i+ C3 ?( E# c# u' d

9 w! i2 d6 Q8 `* o0 C3 V初始化策略

! d' b; {! h& L- o1 r$ O为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。


7 ?7 [- Y, y# s0 p0 `
* }. X+ X$ J; g1 D/ w经过初始化后的结果：



( p5 R& b& E" B4 l; ~) |可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。


+ n' A  u% ^% a7 z交叉变异算子

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


7 J5 {8 i) R$ s& C
8 U8 \) E! V- h) G7 m" ]  z采用交叉变异后的结果：
, ]9 n0 g" Z$ t  T- S1 }7 L, m+ q

0 {* }' z8 d/ Y
4 [" h5 F' h& o/ }; o) P可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。
2 Q. K: e7 o+ X& z$ C$ G
1 V$ h/ d! z8 ]8 S+ F
% @# a- S+ k* D& L( I& }6 X其他
9 S4 T) P* Y& D  U$ A
对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。

Touuqu

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

youOK

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

xiaogegepcb

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