Natural Computing Method Based on LLE Dimension Reduction

doi:10.16182/j.issn1004731x.joss.20-FZ0328

Abstract

Abstract: In the natural computing method, the appearance of high-dimensional problem can make some existing optimization algorithms avoid falling into local optimum, but it makes the performance of the algorithm worse and the running time longer. On the basis of traditional natural calculation method, a natural calculation method based on LLE(Local Linear Embedding) algorithm is proposed, which analyzes the value of neighbor particle k and dimension d, and makes the algorithm get better optimization effect after dimension reduction. In the process, a small bias s is added to the data after dimension reduction to increase the diversity of the population. The strategy is applied to PSO and GA respectively, and its performance is verified by using classical test function and four mainstream algorithms for dimension optimization. The experimental results show that the improved algorithm has obvious improvement in solving accuracy and convergence speed.

Key words: high dimension, natural calculation method, LLE, dimension reduction

CLC Number:

TP301

Zhang Luyao, Ji Weidong, Cheng Hao. Natural Computing Method Based on LLE Dimension Reduction[J]. Journal of System Simulation, 2020, 32(10): 1943-1955.

References 30

[1]	Martín-Vide C, Vega-Rodríguez M A. Theory and practice of natural computing: fifth edition[J]. Soft Computing - A Fusion of Foundations, Methodologies and Applications (S1432-7643), 2019, 23(5): 1421.
[2]	张葛祥, 潘林强. 自然计算的新分支——膜计算[J]. 计算机学报, 2010, 33(2): 208-214.Zhang Gexiang, Pan Linqiang.A new branch of natural computing -- membrane computing[J]. Journal of Computer Science, 2010, 33(2): 208-214.
[3]	康琦, 安静, 汪镭, 等. 自然计算的研究综述[J].电子学报, 2012, 40(3): 548-558.Kang Qi, An Jing, Wang Lei, et al.Research summary of natural computation[J]. Journal of Electronic, 2012, 40(3): 548-558.
[4]	Rabinovich Z L.Natural Thinking Mechanisms and Computer Intelligence[J]. Cybernetics & Systems Analysis (S1060-0396), 2003, 39(5): 695-700.
[5]	Castro L N D. Fundamentals of natural computing: an overview[J]. Physics of Life Reviews (S1571-0645), 2007, 4(1): 1-36.
[6]	Bonabeau E, Théraulaz G.Swarm smarts[J]. Scientific American(S0036-8733), 2000, 282(3): 72-79.
[7]	段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005.Duan Haibin.Principle and application of ant colony algorithm[M]. Beijing: Science Press, 2005.
[8]	Zhang L, Zhou C, Liu X, et al.Solving multi objective optimization problems using particle swarm optimization[C]. The 2003 Congress on Evolutionary Computation, 2003. Canbella, ACT, Australia: IEEE, 2003: 2400-2405.
[9]	Yuan Q, Qian F, Du W.A hybrid genetic algorithm with the Baldwin effect[J]. Information Sciences (S0020-0255), 2010, 180(5): 640-652.
[10]	王蓉芳, 焦李成, 刘芳, 等. 自适应动态控制种群规模的自然计算方法[J]. 软件学报, 2012, 23(7): 1760-1772.Wang Rongfang, Jiao Licheng, Liu Fang, et al.Nature computation with self-adaptive dynamic control strategy of population size[J]. Journal of Software, 2012, 23(7): 1760-1772.
[11]	潘允敬. 求解高维复杂连续优化问题的粒子群算法研究[J]. 江西理工大学学报, 2018, 39(3): 102-106.Pan Yunjing.Particle swarm optimization for complex continuous optimization problems[J]. Journal of Jiangxi University of Science and Technology, 2018, 39(3): 102-106.
[12]	肖闪丽, 王宇嘉, 聂善坤. 动态邻居维度学习的多目标粒子群算法[J]. 计算机工程与应用, 2017, 53(20): 31-37, 60.Xiao Shanli, Wang Yujia, Nie Shankun.Multi-objective particle swarm optimization for dynamic neighbor dimension learning[J]. Computer Engineering and Application, 2017, 53(20): 31-37, 60.
[13]	徐桂萍. 基于维度学习策略的粒子群算法的研究与应用[D]. 长春: 吉林大学, 2019.Xu Guiping.Research and application of particle swarm optimization based on dimension learning strategy[D]. Changchun: Jilin University, 2019.
[14]	拓守恒. 一种基于人工蜂群的高维非线性优化算法[J].微电子学与计算机, 2012, 29(7): 42-46.Tuo Shouheng.A New High-Dimensional Nonlinear Optimization Algorithm Based on Artificial Bee Colony[J]. Microelectronics & Computer, 2012, 29(7): 42-46.
[15]	全亚民, 刘大勇, 邹良剑. 非线性边界和等式约束条件下的高维函数优化算法研究[J]. 科研信息化技术与应用, 2013, 4(5): 10-17.Quan Yamin, Liu Dayong, Zou Liangjian.Optimization algorithm of high-dimensional functions under nonlinear boundary and equality constraints[J]. Information Technology and Application in Scientific Research, 2013, 4(5): 10-17.
[16]	Sabar N R, Jemal A, Yearwood J, et al.Heterogeneous cooperative co-evolution memetic differential evolution algorithm for big data optimization problems[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2017, 21(2): 315-327.
[17]	梁静, 刘睿, 于坤杰, 等. 求解大规模问题协同进化动态粒子群优化算法[J]. 软件学报, 2018, 29(9): 2595-2605.Liang Jing, Liu Rui, Yu Kunjie, et al.Dynamic multi-swarm particle swarm optimization with cooperative coevolution for large scale global optimization[J]. Journal of Software, 2018, 29(9): 2595-2605.
[18]	Cheng R, Jin Y C.A social learning particle swarm optimization algorithm for scalable optimization[J]. Information Sciences (S0020-0255), 2015, 291(6): 43-60.
[19]	Cheng R, Jin Y C.A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics (S2168-2267), 2014, 45(2): 191-204.
[20]	Ridder D, Kouropteva O, Okun O.Supervised locally linear embedding[C]. Artificial Neural Networks and Neural Information Processing. Istanbul, Turkey: Springer, 2003: 333-341.
[21]	马瑞, 王家廞, 宋亦旭, 等. 基于局部线性嵌入(LLE)非线性降维的多流形学习[J]. 清华大学学报(自然科学版), 2008, 48(4): 582-585.Ma Rui, Wang Jiaxin, Song Yyixu, et al.Multi-manifold learning using locally linear embedding(LLE) nonlinear dimensionality reduction[J]. Journal of Tsinghua University (Science and Technology), 2008, 48(4): 582-585.
[22]	刘胜蓝, 闫德勤. 一种新的全局嵌入降维算法[J]. 自动化学报, 2011, 37(7): 828-835.Liu Shenglan, Yan Deqin.A new global embedding algorithm[J]. Acta Automatica Sinica, 2011, 37(7): 828-835.
[23]	Sahni J, Vidyarthi D.A Cost-Effective Deadline- Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment[J]. IEEE Transactions on Cloud Computing (S2168-7161), 2015, 34(2): 1-10.
[24]	Sun T, Xiao C, Xu X, et al.An Improved Budget-Deadline Constrained Workflow Scheduling Algorithm on Heterogeneous Resources[C]. IEEE International Conference on Cyber Security & Cloud Computing. New York: IEEE, 2017: 23-29.
[25]	Rowei S T, Lawrence K S.Nonlinear dimensionality reductionby locally linear embedding[J]. Science (S0036-8075), 2000, 290: 2323-2326.
[26]	Scholkopf B, Smola A, Müller K R.Nonlinear component analysis as a kernel eigenvalue problem[J]. Neural Computation (S0899-7667), 1996, 10(5): 1299-1319.
[27]	刘建. 高维数据的本征维数估计方法研究[D]. 北京: 国防科学技术大学, 2005.Liu Jian.Study on Eigen dimension estimation method of high-dimensional data[D]. Beijing: National University of Defense Technology, 2005.
[28]	李博, 杨丹, 雷明, 等. 基于近邻消息传递的自适应局部线性嵌入[J]. 光电子·激光, 2010, 21(5): 772-778.Li Bo, Yang Dan, Lei Ming, et al.Adaptive local linear embedding based on neighbor messaging[J]. Photoelectron Laser, 2010, 21(5): 772-778.
[29]	孟凡超, 初佃辉, 李克秋, 等. 基于混合遗传模拟退火算法的SaaS构件优化放置[J]. 软件学报, 2016, 27(4): 916-932.Meng Fanchao, Chu Dianhui, Li Keqiu, et al.Solving SaaS components optimization placement problem with hybrid genetic and simulated annealing algorithm[J]. Journal of Software, 2016, 27(4): 916-932.
[30]	James K, Russell E.Particle swarm optimization[C]. Proceedings of the IEEE International Conference on Neural Networks. Piscataway: IEEE Service Center, 1995: 1942-1948.