高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于非线性降维的自然计算方法

季伟东 孙小晴 林平 罗强 徐浩天

季伟东, 孙小晴, 林平, 罗强, 徐浩天. 基于非线性降维的自然计算方法[J]. 电子与信息学报, 2020, 42(8): 1982-1989. doi: 10.11999/JEIT190623
引用本文: 季伟东, 孙小晴, 林平, 罗强, 徐浩天. 基于非线性降维的自然计算方法[J]. 电子与信息学报, 2020, 42(8): 1982-1989. doi: 10.11999/JEIT190623
Weidong JI, Xiaoqing SUN, Ping LIN, Qiang LUO, Haotian XU. Natural Computing Method Based on Nonlinear Dimension Reduction[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1982-1989. doi: 10.11999/JEIT190623
Citation: Weidong JI, Xiaoqing SUN, Ping LIN, Qiang LUO, Haotian XU. Natural Computing Method Based on Nonlinear Dimension Reduction[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1982-1989. doi: 10.11999/JEIT190623

基于非线性降维的自然计算方法

doi: 10.11999/JEIT190623
基金项目: 国家自然科学基金(31971015),哈尔滨市科技局科技创新人才研究专项资助(2017RAQXJ050),哈尔滨师范大学硕士研究生学术创新基金(HSDSSCX2019-08)
详细信息
    作者简介:

    季伟东:男,1978年生,教授,研究方向为人工智能和大数据

    孙小晴:女,1994年生,硕士生,研究方向为群体智能和人工智能

    林平:男,1962年生,研究方向为应用心理学和医学人工智能

    罗强:男,1992年生,硕士生,研究方向为机器学习和神经网络

    徐浩天:男,1996年生,硕士生,研究方向为群体智能和人工智能

    通讯作者:

    孙小晴 sunxiaoqing2649@163.com

  • 中图分类号: TP301.6

Natural Computing Method Based on Nonlinear Dimension Reduction

Funds: The National Natural Science Foundation of China (31971015), Harbin Science and Technology Bureau’s Special Subsidy for Scientific and Technological Innovation Talents Research (2017RAQXJ050), Harbin Normal University Master’s Academic Innovation Fund (HSDSSCX2019-08)
  • 摘要: 随着人工智能的发展,许多优化问题发展为高维的大规模优化问题。在自然计算方法中,针对高维问题虽然能避免算法陷入局部最优,但是在收敛速度和时间可行性上却不占优势。该文在传统自然计算方法的基础上,提出了非线性降维的自然计算方法(NDR),该策略不依赖具体的算法,具有普适性。该方法将初始化的N个个体看做一个ND列的矩阵,然后对矩阵的列向量求最大线性无关组,从而减少矩阵的冗余度,达到降低维度的目的。在此过程中,由于剩余的任意列向量组均可由最大线性无关组表示,所以通过对最大线性无关组施加一个随机系数来维持种群的多样性和完整性。将该文所提策略分别应用到标准遗传算法(GA)和粒子群优化算法(PSO)中,并与标准粒子群算法、遗传算法以及目前主流的对维数进行优化的4个算法对比,实验证明,改进的算法对大部分标准测试函数都具有很强的全局收敛能力,其寻优能力超过了上述6个算法,同时改进后的算法在运行时间上远优于对比算法。
  • 图  1  各算法对标准测试函数进行优化的收敛曲线

    图  2  ${F_8}$的2维图像

    图  3  PSO和NDRPSO仿真时间对比

    图  4  GA和NDRGA仿真时间对比

    表  1  非线性降维的自然计算方法(NDR)

     种群规模为N,终止进化代数为G,测试次数为T
     (1) 初始化N, G, T 等参数,随机产生第1代种群$\bf{pop}$;
     (2) 将生成的种群$\bf{pop}$做线性变换,求得列向量的最大线性无关
       组,即为新的种群$\bf{newpop}$;
     (3) 对新种群$\bf{newpop}$的各维乘以随机系数${r_i}$,更新$\bf{newpop}$;
     (4) 将得到的$\bf{newpop}$使用基于种群的自然计算方法进化;
     (5) 结束。
    下载: 导出CSV

    表  2  标准测试函数

    测试函数维数可行解空间
    ${F_1} = \displaystyle\sum\nolimits_{i = 1}^D { {x_i}^2} $1000[–100, 100]n
    ${F_2} = {\left( { {x_1} - 1} \right)^2} + {\displaystyle\sum\nolimits_{i = 1}^D {i\cdot \left( {2{x_i}^2 - {x_{i - 1} } } \right)} ^2}$1000[–10, 10]n
    ${F_3} = \displaystyle\sum\nolimits_{i = 1}^D { { {\left| { {x_i} } \right|}^{i + 1} } }$1000[–1, 1]n
    $\begin{array}{l}{F_4} = - a\cdot\exp \left( { - b\sqrt {\dfrac{1}{D}\displaystyle\sum\nolimits_{i = 1}^D { {x_i}^2} } } \right) - \exp \left( {\dfrac{1}{D}\displaystyle\sum\nolimits_{i = 1}^D {\cos \left( {c{x_i} } \right)} } \right) + a + \exp \left( 1 \right), a = 20,b = 0.2,c = 2\pi \end{array}$1000[–32.768, 32.768]n
    ${F_5} = \displaystyle\sum\nolimits_{i = 1}^D {({x_i}^2 - 10 \cos (2 \pi {x_i})} + 10)$1000[–5.12, 5.12]n
    ${F_6} = \displaystyle\sum\limits_{i = 1}^D {\frac{ { {x_i}^2} }{ {4000} } - \prod\limits_{i = 1}^D {\cos \left( {\frac{ { {x_i} } }{ {\sqrt i } } } \right)} } + 1$1000[–600,600]n
    $\begin{array}{l}{F_7} = {\sin ^2}\left( {\pi {\omega _1} } \right) + {\displaystyle\sum\nolimits_{i = 1}^{D - 1} {\left( { {\omega _i} - 1} \right)} ^2}\left[ {1 + 10{ {\sin }^2}\left( {\pi {\omega _i} + 1} \right)} \right]\\ \quad\ \ + {\left( { {\omega _D} - 1} \right)^2}\left[ {1 + { {\sin }^2}\left( {2\pi {\omega _D} } \right)} \right]{\omega _i} = 1 + \dfrac{ { {\omega _i} - 1} }{4}\end{array}$1000[–10, 10]n
    ${F_8} = 418.9829D - \displaystyle\sum\nolimits_{i = 1}^D { {x_i}\sin \left( {\sqrt {\left| { {x_i} } \right|} } \right)}$1000[–500, 500]n
    ${F_9} = \displaystyle\sum\nolimits_{i = 1}^{D - 1} {\left[ {100{ {\left( { {x_{i + 1} } - x_i^2} \right)}^2} + { {\left( { {x_i} - 1} \right)}^2} } \right]} $1000[–5, 10]n
    ${F_{10} } = \displaystyle\sum\nolimits_{i = 1}^{D/4} {\left[ { { {\left( { {x_{4i - 3} } + 10{x_{4i - 2} } } \right)}^2} + 5{ {\left( { {x_{4i - 1} } - {x_{4i} } } \right)}^2} + { {\left( { {x_{4i - 2} } - 2{x_{4i - 1} } } \right)}^4} + 10{ {\left( { {x_{4i - 3} } - {x_{4i} } } \right)}^4} } \right]} $1000[–4, 5]n
    ${F_{11} }{\rm{ = } }\displaystyle\sum\nolimits_{i = 1}^D {ix_i^2} $1000[–10, 10]n
    ${F_{12} } = \displaystyle\sum\nolimits_{i = 1}^D {x_i^2 + { {\left( {\displaystyle\sum\nolimits_{i = 1}^D {0.5i{x_i} } } \right)}^2} + { {\left( {\displaystyle\sum\nolimits_{i = 1}^D {0.5i{x_i} } } \right)}^4} } $1000[–5, 10]n
    下载: 导出CSV

    表  3  各算法对12个标准测试函数进行优化结果

    函数平均结果及标准方差
    PSONDRPSOGANDRGA
    F14.92e+05±5.09e+04345.2211±96.78911.78e+05±6.12e+0312.7059±3.2681
    F21.18e+08±2.47e+07301.8188±114.05393.65e+07±1.85e+063.8379±2.8421
    F36.71e-08±7.10e-086.48e-09±8.88e-091.11e-07±1.84e-073.17e-08±4.51e-08
    F417.1198±0.51857.0752±0.741713.2492±0.13235.2058±0.5977
    F59.72e+03±464.6314115.6225±21.71669.68e+03±86.5390104.5187±18.5246
    F64.34e+03±366.17413.6991±0.77141.61e+03±64.09151.4019±0.1196
    F71.66e+04±1.45e+0313.0269±5.81308.62e+03±366.16710.4960±0.1577
    F83.47e+05±7.50e+039.58e+03±866.12303.70e+05±2.42e+039.92e+03±619.0421
    F99.20e+06±2.18e+06694.6303±588.98503.48e+06±2.40e+05103.1690±45.9190
    F101.16e+05±1.50e+0414.2205±5.10532.48e+04±1.50e+030.3623±0.2182
    F112.82e+06±2.62e+0580.1161±31.82987.96e+05±2.70e+042.8521±1.2240
    F121.31e+04±3.41e+0353.57±12.842.18e+19±3.03e+0927.9986±12.1954
    下载: 导出CSV

    表  4  各算法的实验对比结果

    ${F_1}$${F_3}$${F_4}$${F_5}$${F_6}$${F_8}$
    DMS-CCbest13.25.88e+051.60e+142.30e+062.20e+042.00e+11
    SLPSObest4.78e-143.82e+061.90e+145.15e+099.42e+06
    DMS-PSObest1.66e+011.14e+084.36e+071.68e+099.23e+044.51e+10
    CSObest2.43e-093.71e+064.61e+143.25e+099.68e+062.13e+11
    NDRPSObest6.541.11e-082.8912.910.882.02e+03
    下载: 导出CSV
  • [1] DE CASTRO L N. Fundamentals of natural computing: An overview[J]. Physics of Life Reviews, 2007, 4(1): 1–36. doi:  10.1016/j.plrev.2006.10.002
    [2] 刘鑫, 李大海. 基于遗传算法的相位差异技术图像恢复[J]. 四川大学学报: 自然科学版, 2018, 55(4): 745–751. doi:  10.3969/j.issn.0490-6756.2018.04.015

    LIU Xin and LI Dahai. Recovering image using a genetic algorithm based phase diversity technology[J]. Journal of Sichuan University:Natural Science Edition, 2018, 55(4): 745–751. doi:  10.3969/j.issn.0490-6756.2018.04.015
    [3] 魏鹏, 罗红波, 赵康, 等. 基于蚁群算法的运动时间优化算法研究[J]. 四川大学学报: 自然科学版, 2018, 55(6): 1171–1179. doi:  10.3969/j.issn.0490-6756.2018.06.008

    WEI Peng, LUO Hongbo, ZHAO Kang, et al. Optimization of multi-joint robot motion of hydraulic drilling vehicle based on ant colony algorithm[J]. Journal of Sichuan University:Natural Science Edition, 2018, 55(6): 1171–1179. doi:  10.3969/j.issn.0490-6756.2018.06.008
    [4] 邓昌明, 李晨, 邓可君, 等. 基因遗传算法在文本情感分类中的应用[J]. 四川大学学报: 自然科学版, 2019, 56(1): 45–49. doi:  10.3969/j.issn.0490-6756.2019.01.010

    DENG Changming, LI Chen, DENG Kejun, et al. Application of genetic algorithm in text sentiment classification[J]. Journal of Sichuan University:Natural Science Edition, 2019, 56(1): 45–49. doi:  10.3969/j.issn.0490-6756.2019.01.010
    [5] 王蓉芳, 焦李成, 刘芳, 等. 自适应动态控制种群规模的自然计算方法[J]. 软件学报, 2012, 23(7): 1760–1772. doi:  10.3724/SP.J.1001.2012.04151

    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. doi:  10.3724/SP.J.1001.2012.04151
    [6] SUN Wei, LIN Anping, YU Hongshan, et al. All-dimension neighborhood based particle swarm optimization with randomly selected neighbors[J]. Information Sciences, 2017, 405: 141–156. doi:  10.1016/j.ins.2017.04.007
    [7] 刘云, 易松. 双变换算法在多维序列数据分析中的优化研究[J]. 四川大学学报: 自然科学版, 2019, 56(4): 633–638. doi:  10.3969/j.issn.0490-6756.2019.04.009

    LIU Yu and YI Song. Research on optimization of double transform algorithm in multidimensional sequence data analysis[J]. Journal of Sichuan University:Natural Science Edition, 2019, 56(4): 633–638. doi:  10.3969/j.issn.0490-6756.2019.04.009
    [8] 贺毅朝, 王熙照, 张新禄, 等. 基于离散差分演化的KPC问题降维建模与求解[J]. 计算机学报, 2019, 42(10): 267–2280.

    HE Yichao, WANG Xizhao, ZHANG Xinlu, et al. Modeling and solving by dimensionality reduction of kpc problem based on discrete differential evolution[J]. Chinese Journal of Computers, 2019, 42(10): 267–2280.
    [9] WANG Xuesong, KONG Yi, CHENG Yuhu, et al. Dimensionality reduction for hyperspectral data based on sample-dependent repulsion graph regularized auto-encoder[J]. Chinese Journal of Electronics, 2017, 26(6): 1233–1238. doi:  10.1049/cje.2017.07.012
    [10] XU Guiping, CUI Quanlong, SHI Xiaohu, et al. Particle swarm optimization based on dimensional learning strategy[J]. Swarm and Evolutionary Computation, 2019, 45: 33–51. doi:  10.1016/j.swevo.2018.12.009
    [11] WEI Jingxuan and WANG Yuping. A dynamical particle swarm algorithm with dimension mutation[C]. 2006 International Conference on Computational Intelligence and Security, Guangzhou, China, 2006: 254–257. doi: 10.1109/ICCIAS.2006.294131.
    [12] 纪震, 周家锐, 廖惠莲, 等. 智能单粒子优化算法[J]. 计算机学报, 2010, 33(3): 556–561. doi:  10.3724/SP.J.1016.2010.00556

    JI Zhen, ZHOU Jiarui, LIAO Huilian, et al. A novel intelligent single particle optimizer[J]. Chinese Journal of Computers, 2010, 33(3): 556–561. doi:  10.3724/SP.J.1016.2010.00556
    [13] 拓守恒, 邓方安, 周涛. 一种利用膜计算求解高维函数的全局优化算法[J]. 计算机工程与应用, 2011, 47(19): 27–30. doi:  10.3778/j.issn.1002-8331.2011.19.009

    TUO Shouheng, DENG Fang’an, and ZHOU Tao. Algorithm for solving global optimization problems of multi-dimensional function based on membrane computing[J]. Computer Engineering and Applications, 2011, 47(19): 27–30. doi:  10.3778/j.issn.1002-8331.2011.19.009
    [14] CERVANTE L, XUE Bing, SHANG Lin, et al. A dimension reduction approach to classification based on particle swarm optimisation and rough set theory[C]. The 25th Australasian Joint Conference on Artificial Intelligence, Sydney, Australia, 2012: 313–325.
    [15] 拓守恒. 一种基于人工蜂群的高维非线性优化算法[J]. 微电子学与计算机, 2012, 29(7): 42–46. doi:  10.19304/j.cnki.issn1000-7180.2012.07.010

    TUO Shouheng. A new high-dimensional nonlinear optimization algorithm based on artificial bee colony[J]. Microelectronics &Computer, 2012, 29(7): 42–46. doi:  10.19304/j.cnki.issn1000-7180.2012.07.010
    [16] JIN Xin, LIANG Yongquan, TIAN Dongping, et al. Particle swarm optimization using dimension selection methods[J]. Applied Mathematics and Computation, 2013, 219(10): 5185–5197. doi:  10.1016/j.amc.2012.11.020
    [17] 梁静, 刘睿, 于坤杰, 等. 求解大规模问题协同进化动态粒子群优化算法[J]. 软件学报, 2018, 29(9): 2595–2605. doi:  10.13328/j.cnki.jos.005398

    LIANG Jing, LIU Run, 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. doi:  10.13328/j.cnki.jos.005398
    [18] YANG Chenghong, YANG Huaishuo, CHUANG L, et al. PBMDR: A particle swarm optimization-based multifactor dimensionality reduction for the detection of multilocus interactions[J]. Journal of Theoretical Biology, 2019, 461: 68–75. doi:  10.1016/j.jtbi.2018.10.012
    [19] 宋丹, 石勇, 邓宸伟. 一种结合PCA与信息熵的SIFT特征向量自适应降维算法[J]. 小型微型计算机系统, 2017, 38(7): 1636–1641. doi:  10.3969/j.issn.1000-1220.2017.07.039

    SONG Dan, SHI Yong, DENG Chenwei, et al. Self -adaptive descending dimension algorithm of sift feature vector combined with PCA and information entropy[J]. Journal of Chinese Computer Systems, 2017, 38(7): 1636–1641. doi:  10.3969/j.issn.1000-1220.2017.07.039
    [20] CHEN Sibao, DING C H O, and LUO Bin. Linear regression based projections for dimensionality reduction[J]. Information Sciences, 2018, 467: 74–86. doi:  10.1016/j.ins.2018.07.066
    [21] ARIYARATNE M K A, FERNANDO T G I, and WEERAKOON S. Solving systems of nonlinear equations using a modified firefly algorithm (MODFA)[J]. Swarm and Evolutionary Computation, 2019, 48: 72–92. doi:  10.1016/j.swevo.2019.03.010
    [22] 刘振焘, 徐建平, 吴敏, 等. 语音情感特征提取及其降维方法综述[J]. 计算机学报, 2018, 41(12): 2833–2851. doi:  10.11897/SP.J.1016.2018.02833

    LIU Zhentao, XU Jianping, WU Min, et al. Review of emotional feature extraction and dimension reduction method for speech emotion recognition[J]. Chinese Journal of Computers, 2018, 41(12): 2833–2851. doi:  10.11897/SP.J.1016.2018.02833
    [23] 孟凡超, 初佃辉, 李克秋, 等. 基于混合遗传模拟退火算法的SaaS构件优化放置[J]. 软件学报, 2016, 27(4): 916–932. doi:  10.13328/j.cnki.jos.004965

    MENG Fanchao, CHU Dianhui, LI Keqiu, et al. Solving SaaS components optimization placement problem with hybird genetic and simulated annealing algorithm[J]. Journal of Software, 2016, 27(4): 916–932. doi:  10.13328/j.cnki.jos.004965
    [24] KENNEDY J and EBERHART E. Particle swarm optimization[C]. 1995 International Conference on Neural Networks, Perth, Australia, 1995: 1942–1948.
    [25] CHENG Ran and JIN Yaochu. A social learning particle swarm optimization algorithm for scalable optimization[J]. Information Sciences, 2015, 291: 43–60. doi:  10.1016/j.ins.2014.08.039
    [26] SABAR N R, ABAWAJY J, and YEARWOOD J. Heterogeneous cooperative co-evolution memetic differential evolution algorithm for big data optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(2): 315–327. doi:  10.1109/TEVC.2016.2602860
    [27] CHENG Ran and JIN Yaochu. A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics, 2015, 45(2): 191–204. doi:  10.1109/TCYB.2014.2322602
  • [1] 钱宇宁, 曹欣荣, 陈亚伟, 孙俊, 张翔宇.  被动声呐盲分离自适应-自适应波束形成算法研究, 电子与信息学报. doi: 10.11999/JEIT170099
    [2] 张志亮, 沈莹, 邵士海, 潘文生, 唐友喜.  一种线性化的全双工MIMO收发器设计, 电子与信息学报. doi: 10.11999/JEIT151363
    [3] 王娟, 王萍.  一种自适应数据逐层分解的Reed-Solomon码迭代纠错方法及应用, 电子与信息学报. doi: 10.11999/JEIT140907
    [4] 陈思宝, 陈道然, 罗斌.  基于L1-范数的二维线性判别分析, 电子与信息学报. doi: 10.11999/JEIT141093
    [5] 周延, 冯大政, 朱国辉, 向平叶.  空域数据分解的两级降维自适应处理方法, 电子与信息学报. doi: 10.11999/JEIT140508
    [6] 王长城, 戚国庆, 李银伢, 盛安冬.  量化状态信息下多智能体Gossip算法及分布式优化, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00297
    [7] 郑适, 张安学, 岳思橙, 蒋延生.  基于改进粒子群优化的探地雷达波形反演算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01979
    [8] 康士峰, 曹仲晴, 王红光, 郭相明.  基于目标函数的微波超视距雷达天线高度优化方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01039
    [9] 于波, 陈客松, 朱盼, 王国强.  稀布圆阵的降维优化方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00526
    [10] 刘忠宝, 潘广贞, 赵文娟.  流形判别分析, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01552
    [11] 王永茂, 徐正光, 赵珊.  基于自适应近邻图嵌入的局部鉴别投影算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00793
    [12] 张昊, 平西建.  Markov隐写检测特征的一种新设计, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01508
    [13] 高阳, 王雪松, 程玉虎.  基于非负稀疏图的高光谱数据降维, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01082
    [14] 许瑞琛, 蒋挺.  一种认知无线电周期数据传输优化机制, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01361
    [15] 杨晓超, 刘宏伟, 王勇, 纠博.  一种两级机载MIMO雷达空时自适应处理方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00992
    [16] 俞璐, 谢钧, 朱磊.  一种基于目标空间的局部判别投影方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00939
    [17] 唐智灵, 杨小牛, 李建东.  基于顺序统计的窄带通信辐射源指纹特征抽取方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01058
    [18] 詹鹏, 秦开宇, 蔡顺燕.  单路反馈射频功放预失真线性化方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01347
    [19] 吕晖, 冯大政, 和洁, 向聪.  机载MIMO雷达两级降维杂波抑制方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00704
    [20] 陈立福, 韦立登, 向茂生, 韩松涛.  机载双天线干涉SAR非线性近似自配准成像算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.01162
  • 加载中
  • 图(4) / 表ll (4)
    计量
    • 文章访问数:  1315
    • HTML全文浏览量:  477
    • PDF下载量:  30
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-08-12
    • 修回日期:  2020-02-18
    • 网络出版日期:  2020-03-18
    • 刊出日期:  2020-08-18

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注