高维多目标优化中基于稀疏特征选择的目标降维方法

doi:10.3969/j.issn.0372-2112.2015.07.008

电子学报 ›› 2015, Vol. 43 ›› Issue (7): 1300-1307.DOI: 10.3969/j.issn.0372-2112.2015.07.008

所属专题：机器学习—特征选择

高维多目标优化中基于稀疏特征选择的目标降维方法

陈小红, 李霞, 王娜

1. 深圳大学信息工程学院, 广东深圳 518060;
2. 深圳市现代通信与信息处理重点实验室, 广东深圳 518060

收稿日期:2014-04-28 修回日期:2014-09-17 出版日期:2015-07-25
- 作者简介:
- 陈小红 女,1979年生于辽宁省锦州市.现在深圳大学信息工程学院攻读博士学位.主要研究方向智能优化算法. E-mail:chenxh@vip.qq.com;李霞 女,1968年出生于四川省乐山市,毕业于香港中文大学获博士学位,深圳大学信息工程学院教授,博士生导师.主要研究方向为智能计算及应用,多目标优化. E-mail:lixia@szu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61171124); 深圳市科技计划项目 (No.JCYJ20130329110601621); 深圳市基础研究计划项目 (No.JC201105170613A)

Objective Reduction with Sparse Feature Selection for Many Objective Optimization Problem

CHEN Xiao-hong, LI Xia, WANG Na

1. College of Information Engineering, Shenzhen University, Shenzhen, Guangdong 518060, China;
2. Shenzhen Key Lab of Advanced Communications and Information Processing, Shenzhen, Guangdong 518060, China

Received:2014-04-28 Revised:2014-09-17 Online:2015-07-25 Published:2015-07-25
- Supported by:
- National Natural Science Foundation of China (No.61171124); Science and Technology Program of Shenzhen (No.JCYJ20130329110601621); Shenzhen Basic Research Program (No.JC201105170613A)

摘要/Abstract

摘要：

目标降维算法通过去除冗余的目标达到简化问题规模的目的,为求解高维多目标优化问题提供了一种新的思路和方法.近似解集的几何结构特征和Pareto占优关系从不同侧面反映了多目标优化问题的内在结构特性,而现有算法仅利用其中一种特征分析目标之间的关系,具有较大局限性.本文提出基于稀疏特征选择的目标降维方法,该方法利用近似解集的几何结构特征构建稀疏回归模型,求解高维目标空间映射为低维目标子空间的稀疏投影矩阵,依据此矩阵度量目标的重要性,并利用Pareto占优关系改变程度选择满足误差阈值的目标子集,实现目标降维.通过与其他已有目标降维算法比较,实验结果表明本文提出的降维算法具有较高的准确性,并且受近似解集质量的影响较小.

关键词: 高维多目标优化, 目标降维, 稀疏特征选择

Abstract:

Objective reduction approach is an effective means for many-objective optimization problems by eliminating redundant objectives with respect to the original objective set.The geometrical structural characteristics and Pareto-dominance relation of approximation set can represent the characteristics of the original problem in different aspects.This paper proposed a new algorithm based on sparse feature selection.It used the geometrical structural characteristics to construct a graph representing the original problem.A sparse projection matrix mapping the high dimensional data into low dimensional space was then learned by a sparse regression model,which was used to measure the importance of each objective.The change of Pareto-dominance relation induced by reduced set was also adopted to identify a minimum set with error not exceeding threshold value.By comparing with other algorithms,the experimental results show that the accuracy of the new algorithm outperforms other dimension reduction techniques,and is scarcely effected by the quality of approximation set.

Key words: many-objective optimization, objective reduction, sparse feature selection

中图分类号:

TP181

陈小红, 李霞, 王娜. 高维多目标优化中基于稀疏特征选择的目标降维方法[J]. 电子学报, 2015, 43(7): 1300-1307.

CHEN Xiao-hong, LI Xia, WANG Na . Objective Reduction with Sparse Feature Selection for Many Objective Optimization Problem[J]. Acta Electronica Sinica, 2015, 43(7): 1300-1307.

参考文献

[1] Farina M,Amato P.On the optimal solution definition for many-criteria optimization problems[A].Proceedings of Fuzzy Information Processing Society[C].IEEE,2002.233-238.
[2] 巩敦卫,季新芳,孙晓燕.基于集合的高维多目标优化问题的进化算法[J].电子学报,2014,42(1):77-83. GONG Dun-wei,JI Xin-fang,SUN Xiao-yan.Solving many-objective optimization problems using set-based evolutionary algorithms[J].Acta Electronica Sinica,2014,42(1):77-83.(in Chinese)
[3] Lopez-Jaimes A,Coello Coello C A.Including preferences into a multiobjective evolutionary algorithm to deal with many-objective engineering optimization problems[J].Information Sciences,2014,277:1-20.
[4] 孔维健,丁进良,柴天佑.高维多目标进化算法研究综述[J].控制与决策,2010,25(3):321-326. KONG Wei-jian,DING Jin-liang,CHAI Tian-you.Survey on large-dimensional multi-objective evolutionary algorithms[J].Control and Decision,2010,25(3):321-326.(in Chinese)
[5] Wagner T,Beume N,Naujoks B.Pareto-,aggregation-,and indicator-based methods in many-objective optimization[A].Evolutionary Multi-Criterion Optimization[C].EMO,Springer,2007.742-756.
[6] Ishibuchi H,Tsukamoto N,Nojima Y.Evolutionary many-objective optimization:a short review[A].IEEE World Congress on Computational Intelligence[C].IEEE,2008.2419-2426.
[7] Bringmann K,Friedrich T.Approximating the least hyper-volume contributor:NP-hard in general,but fast in practice[J].Theoretical Computer Science,2012,425:104-116.
[8] López Jaimes A,Coello Coello C A,Chakraborty D.Objective reduction using a feature selection technique[A].Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation[C].ACM,2008.673-680.
[9] Schutze O,Lara A,Coello C A C.On the influence of the number of objectives on the hardness of a multiobjective optimization problem[J].IEEE Transactions on Evolutionary Computation,2011,15(4):444-455.
[10] Sinha A,Saxena D K,Deb K,et al.Using objective reduction and interactive procedure to handle many-objective optimization problems[J].Applied Soft Computing,2013,13(1):415-427.
[11] Saxena D K,Duro J A,Tiwari A,et al.Objective reduction in many-objective optimization:linear and nonlinear algorithms[J].IEEE Transactions on Evolutionary Computation,2013,17(1):77-99.
[12] Brockhoff D,Zitzler E.Objective reduction in evolutionary multiobjective optimization:theory and applications[J].Evolutionary Computation,2009,17(2):135-166.
[13] Qian M,Zhai C.Robust unsupervised feature selection[A].Proceedings of 23rd International Joint Conference on Artificial Intelligence[C].AAAI Press,2013.1621-1627.
[14] Hou C,Nie F,Yi D,et al.Feature selection via joint embedding learning and sparse regression[A].Proceedings of 22nd International Joint Conference on Artificial Intelligence[C].AAAI Press,2011.1324-1329.
[15] 向馗,李炳南.主元分析中的稀疏性[J].电子学报,2012,40(12):2525-2532. XIANG Nan,LI Bing-nan.Sparsity in principal component analysis:a survey[J].Acta Electronica Sinica,2012,40(12):2525-2532.(in Chinese)
[16] Cai D,He X,Han J.Spectral regression for dimensionality reduction[R].Department of Computer Science Technical Report No.2856,University of Illinois at Urbana-Champaign,2007.
[17] He X,Cai D,Yan S,et al.Neighborhood preserving embedding[A].IEEE International Conference on Computer Vision[C].IEEE,2005.1208-1213.
[18] Saxena D K,Duro J A,Tiwari A,et al.Objective reduction in many-objective optimization:linear and non-linear algorithms[J].IEEE Transactions on Evolutionary Computation,2013,1(17):77-99.
[19] Zitzler E,Künzli S.Indicator-based selection in multi-objective search[A].Proceedings on Parallel Problem Solving from Nature[C].Springer,2004,3242:832-842.

高维多目标优化中基于稀疏特征选择的目标降维方法

Objective Reduction with Sparse Feature Selection for Many Objective Optimization Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

[1]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[2]	刘冰洁, 毕晓君. 一种基于角度信息的约束高维多目标进化算法[J]. 电子学报, 2021, 49(11): 2208-2216.
[3]	毕晓君, 张永建, 陈春雨. 基于模糊支配的高维多目标进化算法MFEA[J]. 电子学报, 2014, 42(8): 1653-1659.
[4]	巩敦卫, 王更星, 孙晓燕. 高维多目标优化问题融入决策者偏好的集合进化优化方法[J]. 电子学报, 2014, 42(5): 933-939.
[5]	巩敦卫, 季新芳, 孙晓燕. 基于集合的高维多目标优化问题的进化算法[J]. 电子学报, 2014, 42(1): 77-83.