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

mytomorrow

论文提出了一种解决大规模稀疏问题的多目标算法，大规模稀疏存在于许多领域：机器学习、数据挖掘、神经网络。
$ S. M. a" r/ o0 J, j作者主要讨论了四个具体的问题

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

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

  L8 {$ F3 X! a, b4 V具体问题

7 Q% Q2 e- `) I7 ?& V

) E8 k% U+ L5 r6 _" P
& I! n; i; X7 T0 y0 e! n! U$ Q
1 s' l  ^# I" H% i; b7 ^
算法的贡献

• ①设计了新的种群初始化策略（根据稀疏大规模特性，能够获得一个很好的前沿面）
• ②设计了新的基于pareto解集稀疏性的遗传算子
  ( \+ j7 x, J# N; s( M' a  v, G  f

+ b/ _7 f, |  e/ V) |" D1 z
/ `8 `" r5 b8 E1 V具体算法
  e' P0 K' ^  k0 T  N
算法框架
4 q% A- u" O* k1 S9 Z' N
类似于NSGA2的框架




9 L$ Z8 D. b( m4 I初始化策略
: |! X0 ]0 H3 u% ~
为了集成两种编码，需要引入两个向量，一个是决策变量向量dec （实际上是进化的解，对于01编码来说，可以全置1），另一个是掩码向量mask（实际上一个01向量，用来记录每个维度的好坏，好的置1），最终的决策变量是两者的内积。
1 a2 f  W% r7 V! r

) m- |( S' e& s" T1 _
) i! P' X) h$ o9 E+ K4 J: ~) [! C. ^经过初始化后的结果：



3 h/ |; s/ N( m' o% z# S. Z6 N5 p可以看到，通过该初始化策略，获得一个一个近似于pareto面的良好分布。
' B. t, D6 U" d
: S4 h: O6 n7 \6 v
( d; `$ v7 B( \4 K9 x: H' _, K交叉变异算子
- S2 Y+ P- P4 E/ X: Q
这个交叉变异是算法的核心，它每次在二进制向量mask中，以同样的概率每次在0元素中翻转一个元素，或者在非0元素中翻转一个元素，翻转是根据决策变量的适应度值进行的。因此，生成的子代不会有同样数量的0和1，并且可以保持子代的稀疏度。



( L( S3 b4 }1 b) f% ]采用交叉变异后的结果：

; V" I" w& _" [5 _) V
6 A+ ]7 Y% O, q5 g! ^' d
可以看到，通过此策略，提高了稀疏度，被置为1的维度越来越少。
- r0 h! s) Q% ^# v6 h+ `- I
2 Z' f- ?3 V! H- d$ f) q" q; L+ t
其他

/ {! E6 ~0 F; J; s5 |对于实验部分，作者设计了具体的测试套件，结果也非常乐观，在此不赘述。

Touuqu

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

youOK

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

xiaogegepcb

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