高级搜索

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

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

引用本文: 季伟东, 孙小晴, 林平, 罗强, 徐浩天. 基于非线性降维的自然计算方法[J]. 电子与信息学报, doi: 10.11999/JEIT190623 shu
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, doi: 10.11999/JEIT190623 shu

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

    作者简介: 季伟东: 男,1978年生,教授,研究方向为人工智能和大数据;
    孙小晴: 女,1994年生,硕士生,研究方向为群体智能和人工智能;
    林平: 男,1962年生,研究方向为应用心理学和医学人工智能;
    罗强: 男,1992年生,硕士生,研究方向为机器学习和神经网络;
    徐浩天: 男,1996年生,硕士生,研究方向为群体智能和人工智能
    通讯作者: 孙小晴,sunxiaoqing2649@163.com
  • 基金项目: 国家自然科学基金(31971015),哈尔滨市科技局科技创新人才研究专项资助(2017RAQXJ050),哈尔滨师范大学硕士研究生学术创新基金(HSDSSCX2019-08)

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

English

    1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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]. Proceedings of the 25th Australasian Joint Conference on Artificial Intelligence, Sydney, Australia, 2012: 313–325.

    15. [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. [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. [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. [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. [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. [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. [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. [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. [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. [24]

      KENNEDY J and EBERHART E. Particle swarm optimization[C]. The 1995 International Conference on Neural Networks, Perth, Australia, 1995: 1942–1948.

    25. [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. [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. [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. [1]

      于波, 陈客松, 朱盼, 王国强. 稀布圆阵的降维优化方法. 电子与信息学报,

    2. [2]

      康士峰, 曹仲晴, 王红光, 郭相明. 基于目标函数的微波超视距雷达天线高度优化方法. 电子与信息学报,

    3. [3]

      詹鹏, 秦开宇, 蔡顺燕. 单路反馈射频功放预失真线性化方法. 电子与信息学报,

    4. [4]

      周延, 冯大政, 朱国辉, 向平叶. 空域数据分解的两级降维自适应处理方法. 电子与信息学报,

    5. [5]

      吕晖, 冯大政, 和洁, 向聪. 机载MIMO雷达两级降维杂波抑制方法. 电子与信息学报,

    6. [6]

      陈思宝, 陈道然, 罗斌. 基于L1-范数的二维线性判别分析. 电子与信息学报,

    7. [7]

      袁庆军, 王安, 王永娟, 王涛. 基于流形学习能量数据预处理的模板攻击优化方法. 电子与信息学报,

    8. [8]

      郑适, 张安学, 岳思橙, 蒋延生. 基于改进粒子群优化的探地雷达波形反演算法. 电子与信息学报,

    9. [9]

      唐智灵, 杨小牛, 李建东. 基于顺序统计的窄带通信辐射源指纹特征抽取方法. 电子与信息学报,

    10. [10]

      陈立福, 韦立登, 向茂生, 韩松涛. 机载双天线干涉SAR非线性近似自配准成像算法. 电子与信息学报,

    11. [11]

      王长城, 戚国庆, 李银伢, 盛安冬. 量化状态信息下多智能体Gossip算法及分布式优化. 电子与信息学报,

    12. [12]

      许瑞琛, 蒋挺. 一种认知无线电周期数据传输优化机制. 电子与信息学报,

    13. [13]

      杨晓超, 刘宏伟, 王勇, 纠博. 一种两级机载MIMO雷达空时自适应处理方法. 电子与信息学报,

    14. [14]

      俞璐, 谢钧, 朱磊. 一种基于目标空间的局部判别投影方法. 电子与信息学报,

    15. [15]

      王娟, 王萍. 一种自适应数据逐层分解的Reed-Solomon码迭代纠错方法及应用. 电子与信息学报,

    16. [16]

      张志亮, 沈莹, 邵士海, 潘文生, 唐友喜. 一种线性化的全双工MIMO收发器设计. 电子与信息学报,

    17. [17]

      高阳, 王雪松, 程玉虎. 基于非负稀疏图的高光谱数据降维. 电子与信息学报,

    18. [18]

      周凌云, 丁立新, 马懋德, 唐菀. 一种正交反向学习萤火虫算法. 电子与信息学报,

    19. [19]

      杜春, 邹焕新, 孙即祥, 周石琳, 赵晶晶. 基于改进局部切空间排列的流形学习算法. 电子与信息学报,

    20. [20]

      王永茂, 徐正光, 赵珊. 基于自适应近邻图嵌入的局部鉴别投影算法. 电子与信息学报,

  • 图 1  各算法对标准测试函数进行优化的收敛曲线

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

    图 3  PSO和NDRPSO仿真时间对比

    图 4  GA和NDRGA仿真时间对比

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

     算法1 非线性降维的自然计算方法(NDR)
     (1) 初始化N, G, T 等参数,随机产生第一代种群$\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*\left( {2{x_i}^2 - {x_{i - 1} } } \right)} ^2}$1000[–10, 10]n
    ${F_3} = \displaystyle\sum\limits_{i = 1}^D {{{\left| {{x_i}} \right|}^{i + 1}}} $1000[–1, 1]n
    $\begin{array}{l}{F_4} = - a*\exp \left( { - b\sqrt {\dfrac{1}{D}\displaystyle\sum\limits_{i = 1}^D { {x_i}^2} } } \right) - \exp \left( {\dfrac{1}{D}\displaystyle\sum\limits_{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\limits_{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
  • 加载中
图(4)表(4)
计量
  • PDF下载量:  9
  • 文章访问数:  1021
  • HTML全文浏览量:  264
文章相关
  • 通讯作者:  孙小晴, sunxiaoqing2649@163.com
  • 收稿日期:  2019-08-12
  • 录用日期:  2020-02-18
  • 网络出版日期:  2020-03-18
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章