基于LLE降维思想的自然计算方法

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

摘要/Abstract

摘要： 在自然计算方法中,高维问题的出现使现有一些优化算法虽然能够避免算法陷入局部最优,但是使得算法的性能变差、运行时间变长。在传统自然计算方法的基础上,提出基于LLE ( Local Linear Embedding)算法的自然计算方法,通过对算法中邻居粒子k和维数d的取值进行分析,降维后使算法得到较好的寻优效果。在此过程中,将降维后的数据增加一个小偏置s来增加种群的多样性。将该策略分别应用于粒子群算法和遗传算法中,采用经典测试函数以及主流针对维数进行优化的4个算法来验证其性能。实验结果表明,改进的算法在求解精度和收敛速度上均有明显的提升。

关键词: 高维, 自然计算方法, LLE, 降维

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

中图分类号:

TP301

张潞瑶, 季伟东, 程昊. 基于LLE降维思想的自然计算方法[J]. 系统仿真学报, 2020, 32(10): 1943-1955.

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

参考文献 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.