2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

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

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

状态转移算法原理与发展

周晓君 阳春华 桂卫华

周晓君, 阳春华, 桂卫华. 状态转移算法原理与发展. 自动化学报, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
引用本文: 周晓君, 阳春华, 桂卫华. 状态转移算法原理与发展. 自动化学报, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its development. Acta Automatica Sinica, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
Citation: Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its development. Acta Automatica Sinica, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624

状态转移算法原理与发展


DOI: 10.16383/j.aas.c190624
详细信息
    作者简介:

    中南大学自动化学院副教授. 2014年获得澳大利亚联邦大学应用数学博士学位. 主要研究方向为复杂工业过程建模、优化与控制, 优化理论与算法, 状态转移算法, 对偶理论及其应用. E-mail: michael.x.zhou@csu.edu.cn

    中南大学自动化学院教授. 2002年获得中南大学博士学位. 主要研究方向为复杂工业过程建模与优化, 分析检测与自动化装置, 智能化系统. 本文通信作者. E-mail: ychh@csu.edu.cn

    中国工程院院士, 中南大学自动化学院教授. 1981年获得中南矿冶学院硕士学位. 主要研究方向为工业大系统递阶和分散控制理论及应用, 复杂工业过程建模, 优化与控制应用和知识自动化. E-mail: gwh@csu.edu.cn

  • 基金项目:  国家自然科学基金(61873285, 61533021, 61621062, 61860206014), 111项目(B17048), 中南大学创新驱动计划(2018CX012), 湖南省自然科学基金(2018JJ3683)

The Principle of State Transition Algorithm and Its Development

More Information
  • Fund Project:  Supported by the National Natural Science Foundation of China (61873285, 61533021, 61621062, 61860206014), the 111 Project (B17048), the Innovation-Driven Plan in Central South University (2018CX012) and Hunan Provincial Natural Science Foundation of China (2018JJ3683)
  • 摘要: 状态转移算法是基于状态和状态转移的概念及现代控制理论中状态空间表示法提出的一种智能型随机性全局优化方法, 由于其优良的全局搜索能力和快速收敛性, 在许多优化问题中得到了很好的应用. 本文系统地阐述了基本状态转移算法的原理和内在特性, 从理论研究与应用研究两方面综述了状态转移算法的发展历程与现状, 并对其未来发展趋势进行了展望.
  • 图  1  状态变换算子快速性示意图

    Fig.  1  The rapidity of state transformation operators

    图  2  旋转变换算子可控示意图

    Fig.  2  The controllability of rotation transformation operator

    图  3  坐标搜索变换算子可控示意图

    Fig.  3  The controllability of axesion transformation operator

    图  4  下标表示法示意图

    Fig.  4  Illustration of subscript representation

    图  5  离散状态变换算子示意图

    Fig.  5  Illustration of discrete state transformation operators

    图  6  “二次状态转移”策略

    Fig.  6  “Second transition” strategy

    图  7  “冒险与恢复”策略

    Fig.  7  “Risk and restoration in probability” strategy

    图  8  “停滞回溯”策略

    Fig.  8  “Stagnation backtracking” strategy

  • [1] 1 Floudas C A, Gounaris C E. A review of recent advances in global optimization. Journal of Global Optimization, 2009, 45(1): 3−38 doi:  10.1007/s10898-008-9332-8
    [2] 2 Tawarmalani M, Sahinidis N V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 2005, 103(2): 225−249 doi:  10.1007/s10107-005-0581-8
    [3] 3 Gao D Y. Canonical duality theory: Unified understanding and generalized solution for global optimization problems. Computers & Chemical Engineering, 2009, 33(12): 1964−1972
    [4] 4 Zhou X J, Yang C H, Gui W H. State transition algorithm. Journal of Industrial and Management Optimization, 2012, 8(4): 1039−1056 doi:  10.3934/jimo.2012.8.1039
    [5] Zhou X, Gao D Y, Yang C. A comparative study of state transition algorithm with harmony search and artificial bee colony. In: Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). Heidelberg, Berlin: Springer, 2013. 651−659
    [6] Zhou X J, Yang C H, Gui W H. A matlab toolbox for continuous state transition algorithm. In: Proceedings of the 35th Chinese Control Conference (CCC). Chengdu, China: IEEE, 2016. 9172−9177
    [7] Zhou X J, Yang C H, Gui W H. A comparative study of STA on large scale global optimization. In: Proceedings of the 12th World Congress on Intelligent Control and Automation (WCICA). Guilin, China: IEEE, 2016. 2115−2119
    [8] 8 Zhou X J, Gao D Y, Yang C H, Gui W H. Discrete state transition algorithm for unconstrained integer optimization problems. Neurocomputing, 2016, 173: 864−874 doi:  10.1016/j.neucom.2015.08.041
    [9] 阳春华, 唐小林, 周晓君, 桂卫华. 一种求解旅行商问题的离散状态转移算法. 控制理论与应用, 2013, 30(8): 1040−1046 doi:  10.7641/CTA.2013.12167

    9 Yang Chun-Hua, Tang Xiao-Lin, Zhou Xiao-Jun, Gui Wei-Hua. A discrete state transition algorithm for traveling salesman problem. Control Theory and Applications, 2013, 30(8): 1040−1046 doi:  10.7641/CTA.2013.12167
    [10] 董天雪, 阳春华, 周晓君, 桂卫华. 一种求解企业员工指派问题的离散状态转移算法. 控制理论与应用, 2016, 33(10): 1378−1388 doi:  10.7641/CTA.2016.50982

    10 Dong Tian-Xue, Yang Chun-Hua, Zhou Xiao-Jun, Gui Wei-Hua. A novel discrete state transition algorthm for staff assign problem. Control Theory and Applications, 2016, 33(10): 1378−1388 doi:  10.7641/CTA.2016.50982
    [11] Han J, Dong T, Zhou X, Yang C H, Gui W H. State transition algorithm for constrained optimization problems. In: Proceedings of the 33rd Chinese Control Conference (CCC). Nanjing, China: IEEE, 2014. 7543−7548
    [12] 12 Han J, Yang C H, Zhou X, Gui W H. A two-stage state transition algorithm for constrained engineering optimization problems. International Journal of Control, Automation and Systems, 2018, 16(2): 522−534 doi:  10.1007/s12555-016-0338-6
    [13] 13 Zhou X J, Long J P, Xu C C, Jia G B. An external archive-based constrained state transition algorithm for optimal power dispatch. Complexity, 2019, 4727168: 1−11
    [14] Zhou J J, Zhou X J, Yang C H, Gui W H. A multi-objective state transition algorithm for continuous optimization. In: Proceedings of the 36th Chinese Control Conference (CCC). Dalian, China: IEEE, 2017. 9859−9864
    [15] 15 Zhou X J, Zhou J J, Yang C H, Gui W H. Set-point tracking and multi-objective optimization-based PID control for the goethite process. IEEE Access, 2018, 6: 36683−36698 doi:  10.1109/ACCESS.2018.2847641
    [16] 16 Zhou X J, Hanoun S, Gao D Y, et al. A multiobjective state transition algorithm for single machine scheduling. Advances in global optimization, 2015: 79−88
    [17] 周晓君, 周佳佳, 徐冲冲, 一种基于分解的多目标状态转移优化方法及系统, 中国. 201910313379.4, 2019

    Zhou Xiao-Jun, Zhou Jia-Jia, Xu Chong-Chong. A decomposition-based multi-objective state transition optimization method and system, China. Patent ZL201910313379.4, 2019
    [18] 18 Zhou X J, Yang C H, Gui W H. A statistical study on parameter selection of operators in continuous state transition algorithm. IEEE Transactions on Cybernetics, 2018 doi:  10.1109/TCYB.2018.2850350
    [19] 19 Huang M, Zhou X J, Huang T W, Yang C H, Gui W H. Dynamic optimization based on state transition algorithm for copper removal process. Neural Computing and Applications, 2019, 31(7): 2827−2839 doi:  10.1007/s00521-017-3232-0
    [20] 20 Zhou X J, Shi P, Lim C C, Yang C H, Gui W H. A dynamic state transition algorithm with application to sensor network localization. Neurocomputing, 2018, 273: 237−250 doi:  10.1016/j.neucom.2017.08.010
    [21] 21 Wang Y L, He H M, Zhou X J, Yang C H, Xie Y F. Optimization of both operating costs and energy efficiency in the alumina evaporation process by a multi-objective state transition algorithm. The Canadian Journal of Chemical Engineering, 2016, 94(1): 53−65 doi:  10.1002/cjce.22353
    [22] 22 Wang C, Zhang H L, Fan W H. Volterra Series identification based on state transition algorithm with orthogonal transformation. Telkomnika, 2016, 14(1): 171−180 doi:  10.12928/telkomnika.v14i1.2663
    [23] 23 Han X X, Dong Y C, Yue L, Xu Q X. State transition simulated annealing algorithm for discrete-continuous optimization problems. IEEE Access, 2019, 7: 44391−44403 doi:  10.1109/ACCESS.2019.2908961
    [24] 24 Zhou X J, Yang C H, Gui W H. Nonlinear system identification and control using state transition algorithm. Applied Mathematics and Computation, 2014, 226: 169−179 doi:  10.1016/j.amc.2013.09.055
    [25] Bartczuk Ł, Dziwiński P, Red'ko V G. The concept on nonlinear modelling of dynamic objects based on state transition algorithm and genetic programming. In: International Conference on Artificial Intelligence and Soft Computing. Springer, Cham, 2017. 209−220
    [26] 王聪, 张宏立. 基于混沌策略状态转移算法的混沌系统参数辨识. 计算机应用研究, 2016, 5: 1346−1349 doi:  10.3969/j.issn.1001-3695.2016.05.015

    26 Wang Chong, Zhang Hong-Li. Parameter identification in chaotic systems based on state transition algorithm combined with chaotic strategy. Application Research of Computers, 2016, 5: 1346−1349 doi:  10.3969/j.issn.1001-3695.2016.05.015
    [27] Wang Y L, Peng K, Yuan X F, Chen G Y, Li L. Parameter identification for breakage distribution function of bauxite based on state transition algorithm. In: the 6th International Symposium on Advanced Control of Industrial Processes (AdCONIP). Taipei, Taiwan: IEEE, 2017. 251−256
    [28] 28 Xie Y F, Wei S M, Wang X L, Xie S, Yang C H. A new prediction model based on the leaching rate kinetics in the alumina digestion process. Hydrometallurgy, 2016, 164: 7−14 doi:  10.1016/j.hydromet.2016.05.005
    [29] 闫雨晴, 谢永芳, 王晓丽, 尉思谜, 张杏婵. 基双流法溶出过程操作参数优化方法. 化工学报, 2017, 68(3): 1014−1022

    29 Yan Yu-Qing, Xie Yong-Fang, Wang Xiao-Li, Wei Si-Mi, Zhang Xing-Chan. Optimization method of double-stream alumina digestion process parameters. CIESC Journal, 2017, 68(3): 1014−1022
    [30] 30 Rajalakshmi M, Karthik C, Jeyadevi S. Constraint STA optimization for nonlinear modeling and modified MRAC of drying process in paper industry. TAGA Journal, 2018, 14: 2585−2599
    [31] 31 Rajalakshmi M, Jeyadevi S, Karthik C. Computer-aided controller design for a nonlinear process using a Lagrangian-based state transition algorithm. Circuits, Systems, and Signal Processing, 2019: 1−20
    [32] 32 Zhang F X, Yang C H, Zhou X J, Gui W H. Fractional-order PID controller tuning using continuous state transition algorithm. Neural Computing and Applications, 2018, 29(10): 795−804 doi:  10.1007/s00521-016-2605-0
    [33] 33 Zhang F X, Yang C H, Zhou X J, Zhu H Q. Fractional order fuzzy PID optimal control in copper removal process of zinc hydrometallurgy. Hydrometallurgy, 2018, 178: 60−76 doi:  10.1016/j.hydromet.2018.03.021
    [34] Saravanakumar G, Valarmathi K, Rajasekaran M P, Seshadhri S, Mohaideen A K K. State Transition Algorithm (STA) based tuning of integer and fractional-order PID controller for benchmark system. In: IEEE International Conference on Computational Intelligence and Computing Research (ICCIC). Tamilnadu, India: IEEE, 2015. 1−5
    [35] 35 Saravanakumar G, Valarmathi K, Rajasekaran M P, Seshadhri S, Iruthayarajan M W, Balas V E. Tuning Multivariable Decentralized PID Controller Using State Transition Algorithm. Studies in Informatics and Control, 2015, 24(4): 367−378
    [36] 36 Saravanakumar G, Valarmathi K, Iruthayarajan M W, Srinivasan S. Lagrangian-based state transition algorithm for tuning multivariable decentralised controller. International Journal of Advanced Intelligence Paradigms, 2016, 8(3): 303−317 doi:  10.1504/IJAIP.2016.077497
    [37] 37 Zhang F X, Yang C H, Zhou X J, Gui W H. Optimal Setting and Control Strategy for Industrial Process Based on Discrete-Time Fractional-Order PI λDμ. IEEE Access, 2019, 7: 47747−47761 doi:  10.1109/ACCESS.2019.2909816
    [38] 阳春华, 韩洁, 周晓君, 张润东, 桂卫华. 有色冶金过程不确定优化方法探讨. 控制与决策, 2018, 33(5): 856−865

    38 Yang Chun-Hua, Han Jie, Zhou Xiao-Jun, Zhang Run-Dong, Gui Wei-Hua. Discussion on uncertain optimization methods for nonferrous metallurgical processes. Control and Decision, 2018, 33(5): 856−865
    [39] 39 Han J, Yang C H, Zhou X J, Gui W H. Dynamic multi-objective optimization arising in iron precipitation of zinc hydrometallurgy. Hydrometallurgy, 2017, 173: 134−148 doi:  10.1016/j.hydromet.2017.08.007
    [40] 谢世文, 谢永芳, 李勇刚, 阳春华, 桂卫华. 湿法炼锌沉铁过程氧化速率优化控制. 自动化学报, 2015, 41(12): 2036−2046

    40 Xie Shi-Wen, Xie Yong-Fang, Li Yong-Gang, Yang Chun-Hua, Gui Wei-Hua. Optimal Control of Oxidizing Rate for Iron Precipitation Process in Zinc Hydrometallurgy. Acta Automatica Sinica, 2015, 41(12): 2036−2046
    [41] 张凤雪, 阳春华, 周晓君, 桂卫华. 基于控制周期计算的锌液净化除铜过程优化控制. 控制理论与应用, 2017, 34(10): 1388−1395 doi:  10.7641/CTA.2017.60621

    41 Zhang Feng-Xue, Yang Chun-Hua, Zhou Xiao-Jun, Gui Wei-Hua. Optimal control based on control period calculation for copper removal process of zinc solution purification. Control Theory & Application, 2017, 34(10): 1388−1395 doi:  10.7641/CTA.2017.60621
    [42] 42 Wang G W, Yang C H, Zhu H Q, Li Y G, Peng X W, Gui W H. State-transition-algorithm-based resolution for overlapping linear sweep voltammetric peaks with high signal ratio. Chemometrics and Intelligent Laboratory Systems, 2016, 151: 61−70 doi:  10.1016/j.chemolab.2015.12.008
    [43] Huang M, Zhou X J, Yang C H, Gui W H. Dynamic optimization using control vector parameterization with state transition algorithm. In: Proceedings of the 36th Chinese Control Conference (CCC). Dalian, China: IEEE, 2017. 4407−4412
    [44] 44 Yue W C, Gui W H, Chen X F, Zeng Z H, Xie Y F. Knowledge representation and reasoning using self-learning interval type-2 fuzzy Petri nets and extended TOPSIS. International Journal of Machine Learning and Cybernetics, 2019 doi:  10.1007/s13042-019-00940-7
    [45] 左健, 谢永芳, 王晓丽, 王峰, 阳春华. 基于火用分析的氧化铝多效蒸发过程液位优化设定方法. 化工学报, 2017, 68(3): 1005−1013

    45 Zuo Jian, Xie Yong-Fang, Wang Xiao-Li, Wang Feng, Yang Chun-Hua. Liquid level optimal-setting for alumina multi-effect evaporation process based on exergy analysis. CIESC Journal, 2017, 68(3): 1005−1013
    [46] 46 Yang C H, Deng S J, Li Y G, Zhu H Q, Li F B. Optimal control for zinc electrowinning process with current switching. IEEE Access, 2017, 5: 24688−24697 doi:  10.1109/ACCESS.2017.2768068
    [47] 王雅琳, 黄凯华, 黄天红, 周晓君, 阳春华. 基于改进小波神经网络的极谱法多金属离子浓度检测信号的在线解析. 中南大学学报(自然科学版), 2016, 47(1): 100−107 doi:  10.11817/j.issn.1672-7207.2016.01.015

    47 Wie Ya-Lin, Huang Kai-Hua, Huang Tian-Hong, Zhou Xiao-Jun, Yang Chun-Hua. Online analysis on polarographic detection signal of multi-metal ion concentrations based on improved wavelet neural networks. Journal of Central South University (Science and Technology), 2016, 47(1): 100−107 doi:  10.11817/j.issn.1672-7207.2016.01.015
    [48] Chen X F, Qian Y C, Wamg Y L. Power consumption prediction for dynamic adjustment in hydrocracking process based on state transition algorithm and support vector machine. In: International Conference on Neural Information Processing (ICONIP). Guangzhou, China: Springer, 2017. 85−94
    [49] 49 Wang Q A, Huang M, Zhou X J. Feature selection in froth flotation for production condition recognition. IFAC-PapersOnLine, 2018, 51(21): 123−128 doi:  10.1016/j.ifacol.2018.09.403
    [50] 50 Huang Z K, Yang C H, Zhou X J, Yang S X. Energy consumption forecasting for the nonferrous metallurgy industry using hybrid support vector regression with an adaptive state transition algorithm. Cognitive Computation, 2019 doi:  10.1007/s12559-019-09644-0
    [51] 51 Huang Z K, Yang C H, Zhou X J, Huang T W. A hybrid feature selection method based on binary state transition algorithm and ReliefF. IEEE Journal of Biomedical and Health Informatics, 2018 doi:  10.1109/JBHI.2008.2872811
    [52] 52 Zhou X J, Yang K, Xie Y F, Yang C H, Huang T W. A novel modularity-based discrete state transition algorithm for community detection in networks. Neurocomputing, 2019, 334
    [53] 53 Zhang H L, Wang C, Fan W H. A new filter collaborative state transition algorithm for two-objective dynamic reactive power optimization. Tsinghua Science and Technology, 2019, 24(1): 30−43 doi:  10.26599/TST.2018.9010068
    [54] 54 Zhou X J, Gao D Y, Simpson A R. Optimal design of water distribution networks by discrete state transition algorithm. Engineering Optimization, 2013, 18(4): 603−628
    [55] 55 Mala-Jetmarova H, Sultanova N, Savic D. Lost in optimisation of water distribution systems? A literature review of system design. Environmental Modelling & Software, 2017, 93: 209−254
    [56] 56 Huang Z K, Yang C H, Zhou X J, Gui W H. A novel cognitively inspired state transition algorithm for solving the linear bi-level programming problem. Cognitive Computation, 2018, 10(5): 816−826 doi:  10.1007/s12559-018-9561-1
    [57] 57 Pan D, Jiang Z H, Chen Z P, Gui W H, Xie Y F, Yang C H. A novel method for compensating temperature measurement error caused by dust using infrared thermal imager. IEEE Sensors Journal, 2018, 19(5): 1730−1739
    [58] 58 Xie S, Yang C H, Wang X L, Xie Y F. Data reconciliation strategy with time registration for the evaporation process in alumina production. The Canadian Journal of Chemical Engineering, 2018, 96(1): 189−204 doi:  10.1002/cjce.22893
    [59] 59 Xie S, Yang C H, Yuan X F, Wang X L, Xie Y F. Layered online data reconciliation strategy with multiple modes for industrial processes. Control Engineering Practice, 2018, 77: 63−72 doi:  10.1016/j.conengprac.2018.05.002
    [60] 60 Yang C H, Xie S, Yuan X F, Wang X L, Xie Y F. A New data reconciliation strategy based on mutual information for industrial processes. Industrial & Engineering Chemistry Research, 2018, 57: 12861−12870
    [61] 61 Xie S, Yang C H, Yuan X F, Wang X L, Xie Y F. A novel robust data reconciliation method for industrial processes. Control Engineering Practice, 2019, 83: 203−212 doi:  10.1016/j.conengprac.2018.11.006
    [62] 吴佳, 谢永芳, 阳春华, 桂卫华. 数据驱动的锑粗选泡沫图像特征优化设定. 控制与决策, 2016, 31(7): 1206−1212

    62 Wu Jia, Xie Yong-Fang, Yang Chun-Hua, Gui Wei-Hua. Data-driven optimal setting for froth image features of stibium rougher flotation. Control and Decision, 2016, 31(7): 1206−1212
    [63] 63 Wang Q M, Guo X Y, Wang S S, Liao L L, Tian Q H. Multiphase equilibrium modeling of oxygen bottom-blown copper smelting process. Transactions of Nonferrous Metals Society of China, 2017, 27(11): 2503−2511 doi:  10.1016/S1003-6326(17)60277-2
    [64] 64 Zhu Q, Shen L, He J J, Gui W H. Temperature prediction of aluminum alloy work-pieces in aging furnaces based on improved case-based reasoning. International Journal of Nonferrous Metallurgy, 2017, 6: 47−59 doi:  10.4236/ijnm.2017.64004
    [65] 65 Huang Z K, Yang C H, Chen X F, Zeng Z H. An adaptive time series representation method for anode current signals in aluminium electrolysis. IFAC-PapersOnLine, 2018, 51(21): 213−218 doi:  10.1016/j.ifacol.2018.09.420
    [66] 66 Gui W H, Yang C H, Chen X F, Wang Y L. Modeling and optimization problems and challenges arising in nonferrous metallurgical processes. Acta Automatica Sinica, 2013, 39(3): 197−207 doi:  10.1016/S1874-1029(13)60022-1
    [67] Han J, Zhou X J, Yang C H, Gui W H. A multi-threshold image segmentation approach using state transition algorithm. In: Proceedings of the 34th Chinese Control Conference (CCC). Hangzhou, China: IEEE, 2015. 2662−2666
    [68] 68 Han J, Yang C H, Zhou X J, Gui W H. A new multi-threshold image segmentation approach using state transition algorithm. Applied Mathematical Modelling, 2017, 44: 588−601 doi:  10.1016/j.apm.2017.02.015
    [69] 69 Huang Z K, Yang C H, Chen X F, Huang K K, Xie Y F. Adaptive over-sampling method for classification with application to imbalanced datasets in aluminum electrolysis. , 2019 doi:  10.1007/s00521-019-04208-7
    [70] 70 Zhao T T, Tang J T, Hu S G, Lu G Y, Zhou X J, Zhong Y Y. State-Transition-Algorithm based underwater multiple objects localization with gravitational field and its gradient tensor. IEEE Geoscience and Remote Sensing Letters, 2019 doi:  10.1109/LGRS.2.19.2917784
    [71] 刘亚东, 牛大鹏, 常玉清, 王福利, 张永京. 基于区间数的黄金湿法冶炼过程建模与优化研究. 自动化学报, 2019, 45(5): 927−940

    71 Liu Ya-Dong, Niu Da-Peng, Chang Yu-Qing, Wang Fu-Li, Zhang Yong-Jing. Study on process modelling and optimizing based on interval number for gold hydrometallurgy. Acta Automatica Sinica, 2019, 45(5): 927−940
    [72] 高开来, 丁进良. 蒸馏与换热协同的约束多目标在线操作优化方法. 自动化学报, 2019, 45(9): 1679−1690

    72 Gao Kai-Lai, Ding Jin-Liang. A constrained multi-objective online operation optimization method of collaborative distillation and heat exchanger network. Acta Automatica Sinica, 2019, 45(9): 1679−1690
    [73] 代伟, 陆文捷, 付俊, 马小平. 工业过程多速率分层运行优化控制. 自动化学报, 2019, 45(10): 1946−1959

    73 Dai Wei, Lu Wen-Jie, Fu Jun, Ma Xiao-Ping. Multi-rate layered optimal operational control of industrial processes. Acta Automatica Sinica, 2019, 45(10): 1946−1959
  • [1] 董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析[J]. 自动化学报, doi: 10.16383/j.aas.2017.c160703
    [2] 田梦楚, 薄煜明, 陈志敏, 吴盘龙, 赵高鹏. 萤火虫算法智能优化粒子滤波[J]. 自动化学报, doi: 10.16383/j.aas.2016.c150221
    [3] 陈世明, 化俞新, 祝振敏, 赖强. 邻域交互结构优化的多智能体快速蜂拥控制算法[J]. 自动化学报, doi: 10.16383/j.aas.2015.c150254
    [4] 周晓根, 张贵军, 郝小虎. 局部抽象凸区域剖分差分进化算法[J]. 自动化学报, doi: 10.16383/j.aas.2015.c140680
    [5] 张浩杰, 龚建伟, 姜岩, 熊光明, 陈慧岩. 基于变维度状态空间的增量启发式路径规划方法研究[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.01602
    [6] 郭春钊, 山部尚孝, 三田诚一. 基于立体视觉平面单应性的智能车辆可行驶道路边界检测[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.00371
    [7] 辛斌, 陈杰, 彭志红. 智能优化控制:概述与展望[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.01831
    [8] 江贺, 邱铁, 胡燕, 李明楚, 罗钟铉. 启发式算法设计中的骨架分析与应用[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00257
    [9] 张德富, 陈胜达, 刘艳娟. 求解矩形Packing问题的基于遗传算法的启发式递归策略[J]. 自动化学报, doi: 10.1360/aas-007-0911
    [10] 李换琴, 万百五. 基于填充函数算法的工业产品小波网络质量模型[J]. 自动化学报
    [11] 薛雷, 郝跃. 基于Petri网的启发式生产调度[J]. 自动化学报
    [12] 李兵, 蒋慰孙. SAGACIA全局优化方法及应用[J]. 自动化学报
    [13] 张伟, 刘积仁, 李华天. 基于函数逼近的学习式搜索[J]. 自动化学报
    [14] 崔国伟. 基于模糊启发式搜索的汉字识别方法[J]. 自动化学报
    [15] 汪涛, 邢小良, 庄新华. 无对应点三维表面重建的全局优化算法[J]. 自动化学报
    [16] 何敏, 吕勇哉. 基于混合知识表达模型的启发式优化控制策略及其应用[J]. 自动化学报
    [17] 胡庆, 杨静宇, 张黔, 刘克. 基于知识的印鉴鉴别方法[J]. 自动化学报
    [18] 戴学东, 吕勇哉. 两级多品种生产调度的专家系统[J]. 自动化学报
    [19] 杨永耀, 吕勇哉. 板坯加热炉的递阶计算机控制[J]. 自动化学报
  • 加载中
图(8)
计量
  • 文章访问数:  292
  • HTML全文浏览量:  260
  • PDF下载量:  50
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-03
  • 录用日期:  2019-12-15
  • 网络出版日期:  2020-01-17

状态转移算法原理与发展

doi: 10.16383/j.aas.c190624
    基金项目:  国家自然科学基金(61873285, 61533021, 61621062, 61860206014), 111项目(B17048), 中南大学创新驱动计划(2018CX012), 湖南省自然科学基金(2018JJ3683)
    作者简介:

    中南大学自动化学院副教授. 2014年获得澳大利亚联邦大学应用数学博士学位. 主要研究方向为复杂工业过程建模、优化与控制, 优化理论与算法, 状态转移算法, 对偶理论及其应用. E-mail: michael.x.zhou@csu.edu.cn

    中南大学自动化学院教授. 2002年获得中南大学博士学位. 主要研究方向为复杂工业过程建模与优化, 分析检测与自动化装置, 智能化系统. 本文通信作者. E-mail: ychh@csu.edu.cn

    中国工程院院士, 中南大学自动化学院教授. 1981年获得中南矿冶学院硕士学位. 主要研究方向为工业大系统递阶和分散控制理论及应用, 复杂工业过程建模, 优化与控制应用和知识自动化. E-mail: gwh@csu.edu.cn

摘要: 状态转移算法是基于状态和状态转移的概念及现代控制理论中状态空间表示法提出的一种智能型随机性全局优化方法, 由于其优良的全局搜索能力和快速收敛性, 在许多优化问题中得到了很好的应用. 本文系统地阐述了基本状态转移算法的原理和内在特性, 从理论研究与应用研究两方面综述了状态转移算法的发展历程与现状, 并对其未来发展趋势进行了展望.

English Abstract

周晓君, 阳春华, 桂卫华. 状态转移算法原理与发展. 自动化学报, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
引用本文: 周晓君, 阳春华, 桂卫华. 状态转移算法原理与发展. 自动化学报, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its development. Acta Automatica Sinica, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
Citation: Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its development. Acta Automatica Sinica, 2020, 46(x): 1−15. doi: 10.16383/j.aas.c190624
  • 人们总会面临各种各样的选择, 需要从众多的方案中选择出最佳方案, 这里面所说的选择问题就是最优化问题. 由于现实世界的复杂性, 很多实际工程的最优化问题具有众多的局部最优解, 而人们希望找到这些局部最优解中的最好解, 即全局最优解, 这使得全局优化在工程实际中得到了广泛的应用[1].

    考虑到对于一般的最优化问题, 目前还不存在能保证找到全局最优解的统一有效算法(即多项式时间算法). 国内外学者主要从以下三个角度来研究全局优化: i) 在非多项式时间找到一般优化问题的全局最优解, 比如分支定界法、分支切割法[2]等; ii) 在多项式时间内找到具有某些特定结构优化问题的全局最优解, 比如凸优化、对偶理论[3]等; iii) 在多项式时间内找到一般优化问题的近似最优解, 比如遗传算法、粒子群优化、差分进化以及本文要介绍的状态转移算法等.

    状态转移算法是由周晓君博士等[4]于2012年正式提出的一种新颖的智能型随机性全局优化方法, 它的基本思想是将最优化问题的一个解看成是一个状态, 解的迭代更新过程看成是状态转移过程, 利用现代控制理论中的状态空间表达式来作为产生候选解的统一框架, 基于此框架来设计状态变换算子. 与大多数基于种群的进化算法不同, 基本的状态转移算法是一种基于个体的进化算法, 它基于给定当前解, 通过采样方式, 多次独立运行某种状态变换算子产生候选解集, 并与当前解进行比较, 迭代更新当前解, 直到满足某种终止条件. 值得一提的是, 基本状态转移算法中的每种状态变换算子都能够产生具有规则形状、可控大小的几何邻域, 它设计了包括旋转变换、平移变换、伸缩变换、坐标轴搜索等不同的状态变换算子以满足全局搜索、局部搜索以及启发式搜索等功能需要, 并且以交替轮换的方式适时地使用各种不同算子, 使得状态转移算法能够以一定概率很快找到全局最优解[5, 6, 7].

    本文阐述了基本状态转移算法的原理并分析了其内在特性, 综述了从基本状态转移算法演变到离散、约束和多目标状态转移算法的发展历程, 分类概述了状态转移算法在几类典型的工程优化问题中的应用, 并对状态转移算法未来发展趋势进行了展望.

    • 状态转移算法是一种智能型随机性全局优化算法, 它的基本思想是将优化问题的一个解当作一个状态, 解的产生和更新看作是状态转移过程. 借鉴现代控制理论中状态空间模型的表示法, 状态转移算法中候选解产生的统一框架如下:

      $$ \left \{ \begin{aligned} &{ {x}}_{k+1} = A_{k} { {x}}_{k} + B_{k} { {u}}_{k}\\ & y_{k+1} = f({ {x}}_{k+1}) \end{aligned} \right. $$ (1)

      其中, $ { {x}}_{k} = [x_1, x_2, \cdots, x_n]^{\rm T} $为当前状态, 代表优化问题的一个候选解; $ A_{k} $$ B_{k} $为状态转移矩阵, 为随机矩阵, 可以看成是优化算法中的算子; $ { {u}}_k $为当前状态及历史状态的函数, 可以看成是控制变量; $ f(\cdot) $为目标函数或者评价函数.

      具体来说, 一方面, 状态转移算法中专门设计了局部、全局和启发式搜索算子, 其中全局搜索算子是为了保证有一定概率使产生的候选解集形成的邻域中包含全局最优解; 局部搜索算子具有在较小邻域进行精细搜索的功能; 启发式搜索算子用来产生具有一定潜在价值的候选解, 避免搜索的盲目性. 另一方面, 状态转移算法中设计了特定的选择与更新策略, 用来适应不同优化问题的需要. 更进一步地, 状态转移算法中实施了智能化策略, 比如全局和局部算子的交替调用, 可以很大程度上缩短寻找全局最优解的时间和避免陷入局部最优; 采样方式的使用, 可以选择有代表性的候选解, 避免穷举邻域内的所有解, 将极大地缩短搜索时间.

      一般地, 状态转移算法的基本流程如下: i) 从当前最好解出发, 通过某种状态变换算子生成具有某种特定性质的邻域; ii) 以某种采样机制从该邻域内采集一定数目的样本; iii) 根据评价机制, 比较当前最好解与采集样本中最好解的优劣, 并以某种更新机制更新当前最好解; iv) 返回步骤i), 并交替使用各种状态变换算子, 直到满足某种终止条件.

      在状态转移算法的基本框架上, 寻优的最终结果可以从收敛性和全局性两方面来考虑. 为了阐述其性质, 有以下两个假设.

      假设1: 待求解最优化问题的全局最优解是存在的, 即$ f({ {x}}) $有下界.

      假设2: 在全局搜索算子作用下, 基于任意当前解产生的邻域中包含全局最优解, 即

      $$ P({ {x}}^{*} \in N_{{{\widetilde {x}}}}|{{\widetilde {x}}}) > 0 $$ (2)

      上式中, $ {{\widetilde {x}}} $为任意当前解, $ { {x}}^{*} $为全局最优解, $ N_{{{\widetilde {x}}}} $为在全局搜索算子作用下以$ {{\widetilde {x}}}_{k} $为基产生的邻域.

      设定$ {{{Best}}}_{k} $为当前最优解, 状态转移算法中采用如下的“贪婪准则”作为更新机制

      $$ f({{{Best}}}_{k+1}) \leq f({{{Best}}}_{k}) $$ (3)

      基于以上的假设和采用的更新机制, 我们有以下两个定理.

      定理1. 在假设1和更新机制(3)下, 由状态转移算法产生的序列$ \{f({{{Best}}}_{k})\}_{k = 0}^{\infty} $是收敛的.

      证明: 考虑到序列$ \{f({{{Best}}}_{k})\}_{k = 0}^{\infty} $是单调递减且有下界的, 由单调收敛定理可知, 该序列是收敛的.

      定理2. 在假设1、2, 更新机制(3)和随机均匀采样机制下, 由状态转移算法产生的序列$ \{{{{Best}}}_{k}\}_{k = 0}^{\infty} $依概率收敛到全局最优解.

      证明: 首先, 容易理解随机过程$ \{{{{Best}}}_{k}:k \geq 0\} $为马尔可夫链. 设定$ N_{{ {x}}^{*}} $, $ {\bar{N}}_{{ {x}}^{*}} $分别为包含全局最优解的集合及其补集, 由假设1、2, 更新机制(3)及随机均匀采样机制, 有

      $$ \begin{array}{l} P({{{Best}}}_{k+1} \in N_{{ {x}}^{*}} |{{{Best}}}_{k} \in N_{{ {x}}^{*}}) = 1 \\ P({{{Best}}}_{k+1} \in {\bar{N}}_{{ {x}}^{*}} |{{{Best}}}_{k} \in N_{{ {x}}^{*}}) = 0 \\ P({{{Best}}}_{k+1} \in N_{{ {x}}^{*}} |{{{Best}}}_{k} \in {\bar{N}}_{{ {x}}^{*}}) = c(k) \\ P({{{Best}}}_{k+1} \in {\bar{N}}_{{ {x}}^{*}} |{{{Best}}}_{k} \in {\bar{N}}_{{ {x}}^{*}}) = 1 - c(k) \end{array} $$

      其中, $ c(k) \in (c_{\min}, c_{\max}) \subset (0, 1) $, 表示从其它状态转移到全局最优状态的概率. 从而可得第$ n $步状态转移概率矩阵为

      $$\begin{array}{*{20}{l}} {P(n) = \left[ {\begin{array}{*{20}{c}} 1&0\\ \displaystyle {1 - \prod\limits_{k = 1}^n {(1 - c(} k))}&\displaystyle {\prod\limits_{k = 1}^n {(1 - c(} k))} \end{array}} \right]} \end{array}$$

      $ n \rightarrow \infty $, 考虑到

      $$0 \!=\! \prod\limits_{k = 1}^\infty {(1 \!-\! {c_{\max }})} \!\le\! \prod\limits_{k = 1}^\infty {(1 \!-\! c(k))} \!\le\! \prod\limits_{k = 1}^\infty {(1 \!-\! {c_{\min }})} \! =\! 0$$

      我们有$ \displaystyle \prod_{k = 1}^{\infty} (1\!-\! c(k)) = 0 $, 从而

      $$\mathop {\lim }\limits_{n \to \infty } P(n) = \left[ {\begin{array}{*{20}{c}} 1&0\\ 1&0 \end{array}} \right]$$

      由以上极限分布可知, $ \lim\limits_{k \rightarrow \infty} P({{{Best}}}_{k} \in N_{{ {x}}^{*}}) = 1 $.

    • 基本状态转移算法主要针对无约束连续优化问题, 它的主体实现从以下三个方面进行阐述, 其中状态变换算子、邻域与采样用于产生候选解, 选择和更新用于当前最优解的替换, 交替轮换策略用于不同状态变换算子的调用.

    • (1) 旋转变换(Rotation Transformation, RT)

      $$ { {x}}_{k+1} = { {x}}_{k}+\alpha \frac{1}{n \|{ {x}}_{k}\|_{2}} R_{r} { {x}}_{k}, $$ (4)

      其中, $ \alpha > 0 $为旋转因子; $ R_{r} \in {\bf R}^{n\times n} $是一个其元素取值在$ [-1,1] $之间均匀分布的随机矩阵; $ \|\cdot\|_2 $为向量2-范数或欧氏范数. 可以证明, 旋转变换具有在以$ \alpha $为半径的超球内进行搜索的功能[4].

      (2) 平移变换(Translation Transformation, TT)

      $$ { {x}}_{k+1} = { {x}}_{k}+ \beta R_{t} \frac{{ {x}}_{k}- { {x}}_{k-1}}{\|{ {x}}_{k}- { {x}}_{k-1}\|_{2}}, $$ (5)

      其中, $ \beta > 0 $为平移因子; $ R_{t} \in {\bf R} $是一个其元素取值在$ [0,1] $之间均匀分布的随机数. 平移变换具有在沿着从点$ { {x}}_{k-1} $到点$ { {x}}_{k} $的直线上并以$ { {x}}_{k} $为起点、$ \beta $为最大长度进行搜索的功能.

      (3) 伸缩变换(Expansion Transformation, ET)

      $$ { {x}}_{k+1} = { {x}}_{k}+ \gamma R_{e} { {x}}_{k}, $$ (6)

      其中, $ \gamma > 0 $为伸缩因子; $ R_{e} \in \mathbf{R}^{n\times n} $是一个其非零元素取值服从高斯分布的随机对角矩阵. 从理论上看, 伸缩变换能够把$ { {x}}_{k} $中的每个元素伸缩到$(-\infty, $$ +\infty) $的范围内.

      (4) 坐标变换(Axesion Transformation, AT)

      $$ { {x}}_{k+1} = { {x}}_{k}+ \delta R_{a} { {x}}_{k}, $$ (7)

      其中, $ \delta > 0 $为坐标因子; $ R_{a} \in \mathbf{R}^{n\times n} $是一个其非零元素取值服从高斯分布的稀疏随机对角矩阵(基本连续状态转移算法中, 只有一个随机位置为非零元素). 坐标变换的功能是增强单一维度的搜索.

    • 从某个当前状态$ { {x}}_k $出发, 通过状态变换算子的作用, 由于随机性, 产生的候选状态$ { {x}}_{k+1} $不是唯一的. 不难想象, 对一个固定的当前$ { {x}}_k $, 在某种特定的状态变换算子作用下, 所有产生的候选解将构成一个集合, 形成一个邻域, 记作$ N^{operator}_{{ {x}}_k} $, 其中$ operator $代表某种特定算子. 容易理解, 邻域$ N^{operator}_{{ {x}}_k} $中的元素具有同质性, 它们是由固定的当前$ { {x}}_k $和特定的状态变换算子$ operator $共同作用产生的.

      考虑到邻域$ N^{operator}_{{ {x}}_k} $中候选解的同质性, 利用采样策略从该邻域中以一定的机制随机采集有限个候选解, 可以节省搜索时间、避免穷举带来的时间复杂度过高的问题. 以旋转变换为例, 基本连续状态转移算法中随机均匀采样策略的伪代码如下所示:

      1: for $ i\gets 1 $, SE do

      2: $ {State}(:,i) \gets {{{{Best}}}_k} +\alpha \frac{1}{n \| {{{{Best}}}_k} \|_{2}} R_{r} {{{{Best}}}_k} $

      3: end for

      其中, $ {{{Best}}}_k $表示当前最优解; SE可以理解为搜索强度、采样力度或样本大小; $ {State} $表示在给定的$ {{{Best}}}_k $和旋转变换作用下产生的样本大小为SE的状态集.

    • 基本连续状态转移算法采用单个个体的方式进行演化, 它首先从当前最优解$ {{{Best}}}_k $出发, 在某种状态变换算子$ operator $的作用下, 自动产生具有同质性的邻域$ N^{operator}_{{{{Best}}}_k} $, 然后以一定的采样策略从该邻域中采集样本大小为SE的状态集$ {State} $. 在状态转移算法中, 一方面需要从含有SE个样本的状态集$ {State} $中选择“最优解”, 另一方面需要比较该“最优解”和当前最优解$ {{{Best}}}_k $的优劣, 从而更新当前最优解.

      在基本连续状态转移算法中, 均采用“贪婪准则”来选择和更新最优解, 如下所示

      $$ {{{Best}}} = \left\{ \begin{align} &{{{newBest}}}, \;\;\;{\rm{if}}\; f({{{newBest}}}) < f({{{Best}}}) \\ &{{{Best}}},\;\;\;\;\;\; \;\;\;{\rm{otherwise}} \end{align} \right. $$ (8)

      其中, $ {{{newBest}}} $是从状态集$ {State} $中选择的“最优解”.

    • 为达到全局优化的本质要求, 即在最短的时间内找到全局最优解, 状态转移算法中专门设计了全局搜索算子和局部搜索算子, 并采用了交替轮换的机制使用各种算子. 基本连续状态转移算法的伪代码如下:

      1: $ {{{Best}}} \gets {{{Best}}}_0 $

      2: repeat

      3: if $ \alpha < \alpha_{\min} $ then

      4: $ \alpha \gets \alpha_{\max} $

      5: end if

      6: $ {{{Best}}} \gets expansion(funfcn,{{{Best}}},SE,\beta,\gamma )$

      7: $ {{{Best}}} \gets rotation(funfcn,{{{Best}}},SE,\beta,\alpha )$

      8: $ {{{Best}}} \gets axesion(funfcn,{{{Best}}},SE,\beta,\delta )$

      9: $ \alpha \gets \frac{\alpha}{fc} $

      10: until最大迭代次数

      其中$ {{{Best}}}_0 $为随机产生的初始解, expansion, rotation以及axesion函数分别实现了伸缩变换、旋转变换和坐标变换并包括选择和更新功能. 值得注意的是, 状态转移算法中采用了交替轮换的机制使用各种搜索算子, 即旋转、伸缩变换和坐标搜索轮换进行, 并且在分别使用旋转、伸缩变换和坐标变换后调用了平移变换. 采用的交替轮换机制是为了适应不同结构类型优化问题的需要, 它的一大好处是在未达到全局最优解邻域时, 避免浪费过多的时间进行局部搜索, 增强搜索过程的活跃性.

      此外, 基本状态转移算法的参数设置如下, $ \alpha_{\max} = 1, \alpha_{\min} = 1e -4, $$ \beta = 1, \gamma = 1, \delta = 1 $, $ SE = 30, $$fc = 2 $. 其中平移、伸缩和坐标因子都保持恒定, 旋转因子$ \alpha $以指数的方式进行衰减, 底数为$ \frac{1}{fc} $, 并且以周期性的方式在最大值$ \alpha_{\max} $和最小值$ \alpha_{\min} $之间进行变化.

    • 基本状态转移算法内在机理可以从以下五个特性进行阐述和解释, 它包括:

      • 全局性, 状态转移算法具有在整个空间进行搜索的能力;

      • 最优性, 状态转移算法可以保证找到一个最优解;

      • 快速性, 状态转移算法尽可能地节省搜索时间;

      • 收敛性, 通过状态转移算法产生的解序列是收敛的;

      • 可控性, 状态转移算法可以控制搜索空间的几何形状与大小.

    • 状态转移算法的全局性主要通过设计的伸缩变换算子保证. 伸缩算子具有在整个空间进行搜索的能力, 当前最好解通过伸缩变换作用, 得到的所有候选解集将分布在[$ -\infty $,$ +\infty $]整个可行域内, 降低了状态转移算法陷入局部最优的可能性.

    • 通常, 对于优化算法而言, 最优性是指在迭代过程中当前点目标函数值优于其邻域内任何一点的目标函数值.

      定理3. 当采样样本足够大时, 状态转移算法产生的候选解可以收敛至最优解.

      证明: 状态转移算法中最终迭代解的最优性由旋转算子保证, 当旋转算子的参数$ \alpha $足够小时, 当前的最好解$ {{{Best}}}_k $满足如下局部最优性:

      $$ \begin{split} & f({{Best}}_k) \leq f( z), \\ & \forall z \in \Omega = \{ z \in {\bf R}^{n} | \| z - {{Best}}_k \| \leq \alpha_{\min} \} \end{split} $$ (9)

      即在一个足够小的邻域内, 旋转变换算子一定可以找到当前邻域内的最优值.

    • 一般地, 对于最优化算法而言, 收敛性是指该算法在迭代过程中达到或趋向一个不动点.

      定理4. 假设最优化问题的全局最优解存在, 状态转移算法产生的候选解序列是收敛的.

      证明: 状态转移算法利用贪婪准则来更新当前最优解, 即

      $$ f({{{Best}}}_{k+1}) \leq f({{{Best}}}_k) $$ (10)

      $ f({{{Best}}}_{k+1}) $是一个单调递减序列, 又由于最优化问题的全局最优解存在, 由单调收敛定理可知: 单调递减有下界的序列必收敛, 必定存在当迭代次数$ M $, 当前最优解不会再更新, 即:

      $$ f({{{Best}}}_{k+1}) = f({{{Best}}}_k), \forall k \geq M$$ (11)

      结合上面最优性的证明可知, 状态转移算法至少会收敛到一个局部最优解.

    • 状态转移算法的快速性得益于算法的各种智能策略设计. 利用当前最好解$ {{{Best}}}_k $, 通过状态变换算子, 随机采样$ SE $次, 避免在搜索空间内穷举候选解. 同时, 状态转移算法设计了交替轮换策略, 每一次迭代都同时进行局部搜索和全局搜索, 加快了搜索进程, 节省了搜索时间. 具体来说, 状态转移算法设计的旋转、平移、伸缩和坐标四个变换算子, 分别用于局部搜索和全局搜索; 交替轮换策略使得在搜索过程中四个算子交替使用, 局部搜索和全局搜索相结合, 利用全局搜索算子保证了状态转移算法的全局性, 避免了一直使用局部搜索算子导致搜索速率慢和陷入局部最优的情况, 利用局部搜索算子保证了算法的局部最优性, 在保证全局性和最优性的前提下, 交替轮换策略使得算法具有快速性, 可以以较快的收敛速率寻得优化问题的最优解.

      图1是以具有多极值的单目标函数最小化问题为例, 说明状态转移算法的快速性. 若仅仅使用旋转变换算子进行搜索, 由于旋转变换是局部搜索算子, 则搜索路径可以表示为$ a \rightarrow b \rightarrow c \rightarrow d \rightarrow e $, 搜索进程缓慢且有较大陷入局部最优的风险; 而状态转移算法设计的交替轮换策略使得旋转、平移、伸缩和坐标四个变换算子交替使用, 搜索路径可以表示为$ a \rightarrow b \rightarrow c ' \rightarrow d ' \rightarrow e ' $, 可以看出搜索速率大大加快, 且陷入局部最优的可能性减小. 因此, 状态转移算法具有快速性.

      图  1  状态变换算子快速性示意图

      Figure 1.  The rapidity of state transformation operators

    • 状态转移算法中对状态变换算子中的参数调整可以控制搜索空间的几何形状与大小, 以旋转变换算子和坐标搜索算子为例对状态转移算法的可控性进行说明. 旋转变换算子是以当前最好解为球心, 在参数$ \alpha $为半径的超球体内进行搜索, 通过设定$ \alpha $的数值, 可以扩大或者缩小旋转变换算子的搜索范围. 坐标搜索算子侧重单维坐标搜索, 参数$ \delta $越大, 沿着当前解为坐标原点的坐标各维搜索范围越广. 图2是设置当前最好解$ {{Best}}_k $ = [1, 1], 在参数$ \alpha $分别等于1和2时, 利用旋转变换算子进行搜索的示意图, 图3是将当前最好解$ {{Best}}_k $ = [1, 1, 1], 在参数$ \delta $分别等于1和2时, 利用坐标搜索变换算子进行搜索的示意图, 其搜索范围的变化可以很好体现状态转移算法的可控性.

      图  2  旋转变换算子可控示意图

      Figure 2.  The controllability of rotation transformation operator

      图  3  坐标搜索变换算子可控示意图

      Figure 3.  The controllability of axesion transformation operator

    • 基本状态转移算法从本质上来讲是针对连续优化问题提出的一种无约束优化方法, 它侧重设计产生候选解的搜索算子. 而针对离散优化、约束优化、多目标优化及其它不同特点的优化问题, 状态转移算法一方面需要设计新的搜索算子, 另一方面还需要设计特定的选择与更新机制, 实施面向问题需要的智能化策略, 下面章节将概述状态转移算法的演变与提升.

    • 离散状态转移算法用于求解决策变量为离散变量的优化问题. 其与基本状态转移算法的主要差别是候选解的产生和编码方式有所不同. 离散状态转移算法中设计了交换、平移、对称和替换算子四种具有特定几何功能的算子[8], 对候选解采用独特的下标表示法作为候选解的编码方式, 促使利用搜索算子得到的候选解均为可行解, 避免了算法在迭代求解过程中对不可行解的修正, 缩短了离散优化问题的求解时间. 该算法有效地求解了背包问题、员工指派问题等典型的离散优化问题[9, 10].

      为了介绍基本离散状态转移算法的主要思想, 考虑如下的离散优化问题:

      $$ \min\limits_{x_{i} \in {K}}f({ {x}}) $$ (12)

      其中$ {{x}} = [x_1, x_2, \cdots, x_i, \cdots,x_n]^{\rm T} $, $ {K} = \{\kappa_1, \kappa_2, \cdots, $ $ \kappa_m\} $是每个元素$ x_i $取值的集合.

    • 为了方便求解离散优化问题, 加快搜索速率, 离散状态转移算法采用下标表示法对候选解进行编码. 对于如式(12) 所示的离散最优选择问题, 下标表示法将$ n $ 维决策变量的取值$ \{\kappa_1, \kappa_2, \cdots,\kappa_m\} $$ \{1,2, \cdots ,m\} $中的数字一一对应, 将决策变量$ {{x}} $编码成一种包含$ \{1,2, \cdots , m\} $这些数字的序列. 以三维离散优化问题为例, 下标表示法的示意图如图4所示, 当$ {{x}} $取不同值时, 对应的编码方式有6种. 下标表示法具有可拓展性, 可以根据离散优化问题的具体形式, 做出相应的变化. 此外, 采用下标表示法也可以降低部分离散优化问题的求解难度[10].

      图  4  下标表示法示意图

      Figure 4.  Illustration of subscript representation

    • 离散状态转移算法设计了四种典型离散状态变换算子, 同样具有一定的几何搜索功能、全局搜索和局部搜索能力. 各种算子的示意图如图5所示.

      图  5  离散状态变换算子示意图

      Figure 5.  Illustration of discrete state transformation operators

      (1) 交换变换算子

      $$ {{ {x}}}_{k+1} = A_k^{swap}(m_a){{ {x}}}_k, $$

      其中$ A_k^{swap}\in {\bf Z}^{n\times n} $称为交换变换矩阵, 是一个带有交换变换功能的随机布尔矩阵. 该算子具有交换$ {{ {x}}}_k $$ m_a $个元素的能力. $ m_a $称为交换变换因子, 具有控制交换变换元素的个数的作用.

      (2) 移动变换算子

      $$ {{ {x}}}_{k+1} = A_k^{shift}(m_b){{ {x}}}_k, $$

      其中$ A_k^{shift}\in {\bf Z}^{n\times n} $称为移动变换矩阵, 是一个带有移动变换功能的随机布尔矩阵. 该算子具有将$ {{ {x}}}_k $中连续$ m_b $个元素移动到另一个随机位置后面的能力. $ m_b $为移动因子, 具有控制候选解中最多连续移动元素的作用.

      (3) 对称变换算子

      $$ {{ {x}}}_{k+1} = A_k^{sym}(m_c){{ {x}}}_k, $$

      其中$ A_k^{sym}\in {\bf Z}^{n\times n} $称为对称变换矩阵, 一个带有交换变换功能的随机布尔矩阵. 该算子具有将$ {{ {x}}}_k $中连续$ m_c $个元素翻转到另一个随机位置对面的能力. $ m_c $为对称因子, 具有控制候选解对称变换元素个数的作用.

      (4) 替代变换算子

      $$ {{ {x}}}_{k+1} = A_k^{sub}(m_d){{ {x}}}_k, $$

      其中$ A_k^{sub}\in {\bf Z}^{n\times n} $称为对称变换矩阵, 一个带有替代变换功能的随机布尔矩阵. 该算子具有将$ {{ {x}}}_k $中的$ m_d $个元素进行替换的能力. $ m_d $为替代因子, 具有控制候选解中被替代元素个数的作用.

    • 单目标约束优化问题的表达式如下所示:

      $$ \begin{array}{l} \min \quad f({{x}}) \\ {\rm{s.t.}} \; \quad g_{i}({{x}}) = 0,\quad i = 1,2, \cdots,p \\ \quad \quad \; \; h_{j}({{x}}) \leq 0,\quad j = 1,2, \cdots,q \\ \quad \quad \; \; l_{k} \leq {x}_{k} \leq u_{k}, \quad k = 1,2, \cdots ,n \end{array} $$ (13)

      其中, $ f({{x}}) $表示目标函数, $ g_{i}({{x}}) $$ h_{j}({{x}}) $分别表示不等式约束和等式约束函数, 其个数分别为$ p $$ q $, $ u_{k} $$ l_{k} $分别表示决策变量$ {x}_{k} $的上下界.

      为了求解约束优化问题, 需引入约束处理策略, 用来比较任意两个候选解孰优孰劣. 常用的约束处理策略有如下几种:

      • 罚函数法

      罚函数法又称乘子法, 它的适应度函数由目标函数和带罚因子的约束违反度组成, 由此将约束优化问题转化为无约束优化问题, 对候选解采用统一的适应度函数进行比较. 常用的罚函数如下

      $$ F({ {x}}) = f({ {x}}) + \sigma*G({ {x}}), $$ (14)

      其中, $ \sigma $是罚因子, $ G({ {x}}) $表示约束违反度, 其表达式如下所示:

      $$ G({ {x}}) = \sum\limits_{i = 1}^p \max\{0, g_i({ {x}})\}^\kappa + \sum_{j = 1}^q \max\{0, |h_j({ {x}})| - \epsilon\}^\kappa $$ (15)

      其中, $ g_i({ {x}}),h_j({ {x}}) $分别表示不等式约束与等式约束, $ \epsilon $为容忍误差, $ \kappa $通常取1或2.

      • 可行性优先法

      可行性优先法是优先考虑候选解的可行性, 然后考虑其对应的目标函数值, 它给出了如下三条规则用来比较任意两个候选解:

      a. 若两个候选解均为不可行解, 则选择约束违反度较小的候选解;

      b.若一个候选解为不可行解, 另一个为可行解, 则选择可行的候选解;

      c. 若两个候选解均为可行解, 则选择目标函数值较小的候选解.

      • 两阶段法

      两阶段法是在处理约束的时候分阶段采用不同的约束处理策略. 在第一阶段, 采用可行性优先法, 迅速寻找可行解, 并进入可行域. 在第二阶段, 采用静态罚函数法, 如公式(14). 文献[11, 12]提出了基于两阶段法的约束状态转移算法, 并将该方法用于求解几种典型的工程约束优化问题, 与基于罚函数法和可行性优先法的约束状态转移算法相比, 获得了更好的优化结果.

      • 偏好权衡策略法

      文献[13]提出了基于偏好权衡策略的状态转移算法, 该方法将状态转移算法和偏好权衡约束处理策略相结合成功用于求解锌电解过程中的电力调度优化问题. 其基本思想是: 首先根据可行率权衡可行解及不可行解个数, 如公式(16)和(17). 然后对可行解仅采用目标函数值进行排序, 偏好选择目标函数值较小的候选解; 而不可行解使用归一化的罚函数法进行权衡, 如公式(18)、(19)和(20), 偏好选择适应度函数较小的解, 将选出的精英候选解存入设定的档案袋中. 候选解的选择及归一化的罚函数法表达式如下:

      $$ \begin{array}{l} feasi\_num = \left \{ \begin{array}{lcl} SA \times (1 - fp), &0 < fp < 1 \\ SA, &fp = 1 \end{array} \right. \end{array} $$ (16)
      $$ \begin{array}{l} infeasi\_num = \left \{ \begin{array}{lcl} SA \times fp, &0 < fp < 1 \\ SA, &fp = 0 \end{array} \right. \end{array} $$ (17)
      $$ \begin{array}{l} f_{norm}({ {x}}) \! = \! \displaystyle \frac{f({ {x}}) \!-\! \min f({ {x}})}{\max f({ {x}}) \!-\! \min f({ {x}})}, { {x}} \in S \end{array}\quad \quad $$ (18)
      $$ \begin{array}{l} G_{norm}({ {x}}) \! = \! \displaystyle \frac{G({ {x}}) \!-\! \min G({ {x}})}{\max G({ {x}}) \!-\! \min G({ {x}})}, { {x}} \in S \end{array} $$ (19)
      $$ \begin{array}{l} F_{norm}({ {x}}) = f_{norm}({ {x}}) + \sigma * G_{norm}({ {x}}) \end{array} \quad$$ (20)

      其中, $ feasi\_num $$ infeasi\_{num} $分别表示选出的可行解及不可行解个数, $ SA $表示档案袋的大小, $ fp $表示当前候选解集的可行率, $ f_{norm}({ {x}}) $, $ G_{norm}({ {x}}) $分别是归一化的目标函数值和约束违反度值, $ S $表示不可行解集.

    • 考虑如下的多目标优化问题:

      $$ \begin{array}{l} \min\limits_{{ {x}} \in {\Omega}} F({ {x}}) = [f_1({ {x}}),f_2({ {x}}), \cdots ,f_m({ {x}})]^{\rm T} \end{array} $$ (21)

      其中, $ f_1({ {x}}),f_2({ {x}}), \cdots ,f_m({ {x}}) $$ m $个待优化的目标函数, $ \Omega $是决策变量的寻优空间.

      多目标优化问题同时优化多个目标函数, 多个目标之间是相互冲突的, 因而这些目标不能同时达到最优, 即不存在一个候选解使得所有的目标达到最优. 求解多目标优化问题得到的是一个针对所有目标相互权衡之下的一组Pareto最优解集, 并期望该解集中的解在目标函数空间分布均匀. 与Pareto最优的相关概念具体表述如下:

      定义1. (Pareto占优) 对任意两个候选解$ { {x}}_A $$ { {x}}_B $, 称$ { {x}}_A $占优(或支配)$ { {x}}_B $, 记作$ { {x}}_A \prec { {x}}_B $, 当且仅下式成立:

      $$ \begin{array}{l} \forall i = 1,2, \cdots ,m, f_i({ {x}}_A)\leq f_i({ {x}}_B) \\ \wedge \;\; \exists j = 1,2, \cdots ,m, f_j({ {x}}_A) < f_j({ {x}}_B) \end{array} $$ (22)

      定义2. (Pareto最优解) $ {{x}}^* $为Pareto最优解(或非支配解), 当且仅当在决策空间内, 不存在其他候选解$ {{x}} $支配它, 即

      $$ \neg \exists {{x}}\in \Omega: {{x}} \prec {{x}}^* $$ (23)

      定义3. (Pareto最优解集) 所有的Pareto最优解$ {{x}}^* $组成Pareto最优解集$ PS $, 即

      $$ PS: = \{{{x}}^* \in \Omega | \neg \exists {{x}}\in \Omega, {{x}} \prec {{x}}^* \} $$ (24)

      定义4. (Pareto前沿) Pareto最优解集中所有Pareto最优解在目标空间的映射形成的解集, 组成Pareto最优解的目标向量值集合, 即

      $$ PF: = \{ F({{x}})| {{x}}\in PS\}. $$ (25)

      目前状态转移算法在多目标优化领域的研究主要是基于Pareto占优及基于分解的方法, 下面将分别介绍.

      • 基于Pareto占优的多目标状态转移算法

      基于Pareto占优算法是以Pareto占优为比较准则的一类算法. 其基本思想如下: 首先通过状态变换算子产生候选解集, 利用Pareto占优概念对候选解进行比较, 选择出非占优的解, 此外还需要设计一些多样性维护算子, 从非占优解中剔除处于密集区域的解, 保留分布较为均匀的解, 使得候选解分布较为均匀.

      文献[14]提出了基于开放档案袋的多目标状态转移算法. 该算法将状态变换算子、快速非支配排序和拥挤距离算子结合, 将搜索到的全部非占优解都储存在档案袋中, 不断进行迭代进化, 直至算法终止. 具体来说, 首先在决策空间中均匀随机产生初始候选解集, 利用快速非支配排序找到处于第一前沿的解并将其保存在档案袋中, 之后利用拥挤距离从档案袋中剔除处于密集区域的解, 之后利用状态变换算子产生新的候选解集, 不断进行上述步骤直至算法终止. 经过标准测试函数的测试, 该算法可以获得具有较好的收敛性和分布性的最优解集.

      文献[15]提出一种基于相对拥挤距离的多目标状态转移算法, 同样也采用了Pareto占优对候选解进行比较. 该算法利用档案袋将候选解比较过程中的非占优解进行存储, 采用基于相对拥挤距离的多样性维护策略对候选解进一步选择, 该策略通过计算相邻候选解之间的拥挤距离, 对候选解之间的距离相对远近做出判断, 将相对距离较近的候选解进行剔除, 使得候选解可以较为均匀的分布在目标函数前沿上, 该算法成功应用于湿法炼锌沉铁过程的多目标优化控制问题.

      文献[16]提出一种基于Pareto占优的离散多目标状态转移算法, 该算法利用非支配排序策略从候选解集中选择最好的候选解, 利用离散状态变换算子搜索新的候选解集, 并设计Pareto档案袋策略将找到的非占优解进行保存. 所提算法在一类单机器调度问题上展现出很好的性能, 并和其他算法对比的实验结果验证了该算法的有效性.

      • 基于分解的多目标状态转移算法

      基于分解的多目标优化算法将多目标优化问题转化成为多个等价的单目标优化子问题进行求解, 每一个单目标优化子问题的最优解都对应原问题的一个Pareto最优解, 最终获得多目标优化问题的Pareto最优解集. 常见的分解方法如下:

      a. 权重向量求和法

      权重求和法是对每一个目标函数施加一个权重, 对所有的目标函数求权重和, 该方法具有明确的几何意义, 其函数值等于候选解目标函数向量在权重方向上的投影. 其数学表达式如下

      $$ {\rm {min}}\qquad g^{ws}({{x}}|{{\lambda}}) = \sum\limits_{i = 1}^m{\lambda_i f_i({{x}})} $$ (26)

      其中, $ { \lambda} $ = [$ \lambda_1 $, $ \lambda_2 , \cdots$, $ \lambda_m $]是权重向量求和法的权重向量.

      b. 切比雪夫分解方法

      该方法利用参考点和权重向量, 通过最小化单个目标在权重下与理想点之间的差距, 使得候选解不断进化. 其数学表达式如下

      $$ {\rm {min}} \qquad g^{te}({{x}}|{{\lambda}}) = max \{\lambda_i (f_i({{x}})-z_i^* )\} $$ (27)

      其中, $ \lambda $ = [$ \lambda_1 $, $ \lambda_2 ,\cdots$, $ \lambda_m $]是切比雪夫分解方法的权重向量, $ {{x}} $是候选解, $ {{z^*}} $ = [$ z_1^* $, $ z_2^* ,\cdots$, $ z_m^*]^{\rm T} $是当前理想的参考点.

      c. 惩罚边界法

      该方法是计算候选解的目标函数向量在权重方向上的投影长度和其与权重向量的垂直距离的二者的和, 选择两者和较小的候选解, 使得候选解不断朝向Pareto最优的方向进行进化.

      $$ \begin{split} &{\rm {min}} \qquad g^{pbi} = d_1 + \theta d_2 \\ & {\rm {s.t.}} \quad d_1 = \frac{{||({{F}}({{x}})-{{z}}^*)}^{\rm T}\lambda_i||}{||\lambda_i||} \\ & d_2 = ||{{F}}({{x}})-({{z}}^*-d_1 \frac{\lambda_i}{||\lambda_i||})|| \end{split} $$ (28)

      其中, $ \lambda $ = [$ \lambda_1 $, $ \lambda_2 ,\cdots$, $ \lambda_m $]是惩罚边界法的权重向量, $ {{z^*}} $ = [$ z_1^* $, $ z_2^* ,\cdots$, $ z_m^*]^{\rm T} $, $ d_1 $用来表征候选解的目标函数与理想参考点组成的向量在权重向量上的投影距离, $ d_2 $用于表征候选解在目标函数空间距离权重向量的垂直距离.

      针对分解框架下存在候选解与权重向量匹配不当的问题, 文献[17]利用候选解目标函数与权重向量及理想点之间的几何关系, 定义了如下的候选解与权重向量匹配的匹配度:

      $$ \phi = abs( \frac{{{\omega}}\cdot {({{F({x}|{\lambda})-{z^*})}}}}{||{{\omega}}||\cdot||{{F({x}|{\lambda})}}||}-1) $$ (29)

      其中, $ {{\omega}} $ = $ [1/\lambda_1, 1/\lambda_2,\cdots,1/\lambda_m]^{\rm T} $. 更进一步, 基于匹配度, 提出了基于匹配度的修正切比雪夫聚合函数:

      $$ {\rm {min}} \qquad g^{tmd}({{x}}|{{\lambda}}) = g^{te}({{x}}|{{\lambda}}) \cdot(1+\phi) $$ (30)

      可以证明, 该聚合函数与传统切比雪夫聚合函数具有等价性. 整体说来, 该算法利用状态变换算子产生候选解, 利用匹配度的修正切比雪夫聚合函数进行候选解的选择, 通过标准测试函数的测试, 该算法被验证可行有效.

    • 在状态转移算法中, 主要参数包括旋转因子、平移因子、伸缩因子、坐标因子和采样力度等, 这些参数对算法性能有一定的影响. 其中, 对状态变换因子的研究尤其重要, 因为状态变换算子形成的邻域主要受变换因子的控制. 但在基本状态转移算法中, 变换因子在寻优的过程大多是固定不变的, 无法较好地满足迭代过程中各阶段中算法性能对控制参数的特殊要求, 因此有必要研究状态变换因子自适应变化策略.

      Zhou等[18]提出了一种具有最优参数自适应选择策略的连续状态转移算法. 将最优参数表示为$ \tilde{a}^{*} $, 其选择策略如下:

      $$ \tilde{a}^{*} = \arg \min_{\tilde{a}_k \in \Omega} f({ {x}}_k + \tilde{a}_k \tilde{ d_k}) $$ (31)

      其中, $ \tilde{ d_k} $为各种状态变换算子所等效的搜索方向, $ \tilde{a}_k $为等效的搜索步长. 为简化参数选择并加速搜索过程, 该算法中的状态变换因子$ \tilde{a}_k $的值都取自一个固定的集合$ \Omega $. 在迭代过程中, 选择具有相应最小目标函数值的参数值, 并将所选参数值保持一段时间.

      Huang等[19]提出了另一种自适应变化策略, 旋转因子和伸缩因子将根据目标函数值之间的相对改进而自适应地改变. 具体来说, 旋转因子$ \alpha $和伸缩因子$ \beta $将按照如下公式更新:

      $$ \alpha (\beta ) = \left\{ {\begin{aligned} &{fc \times \alpha (\beta ),}\quad \;{{\rm{if}}\;c < {c_{\min }}}\\& {\frac{1}{{fc}} \times \alpha (\beta ),}\quad {{\rm{if}}\;c > {c_{\max }}}\\& {\alpha (\beta ),}\qquad \quad \;\;{{\rm{else}}} \end{aligned}} \right. $$ (32)

      其中, $ c $表示计数器, 定义如下:

      $$ c = \left\{ {\begin{aligned} &{\max (0,c - 1),}\quad{{\rm{if}}\;f({{Bes}}{{{t}}_k}) - f({{Bes}}{{{t}}_{k - 1}}) > \tau }\\ &{\max (0,c + 1),}\quad{{\rm{else}}} \end{aligned}} \right. $$ (33)

      $ c_{\min} $$ c_{\max} $表示计数器的下限和上限阈值, $ fc $为变化因子, $ \tau $是指定的公差, $ f({{{Best}}}_k) $是第$ k $次迭代的目标函数值. 如果计数器小于$ c_{\min} $, 则该因子将乘以$ fc $以促进全局搜索, 如果计数器大于$ c_{\max} $, 该因子将除以$ fc $以促进局部搜索.

    • 状态变换算子是状态转移算法的核心基础, 算子的搜索能力与算法的优化性能息息相关. 近年来, 在旋转、平移、伸缩及坐标四个算子的基础上, 一些研究者对状态变换算子进行了深入的拓展研究, 以提高状态转移算法的搜索性能.

      Zhou等[20]针对旋转变换随机矩阵生成耗时的问题, 提出了快速旋转变换(Fast rotation transformation, FRT)以降低计算复杂度, 其表达式如下:

      $$ { {x}}_{k+1} = { {x}}_k+\alpha { {\hat{R}}}_r \frac{{ {u}}}{\|{ {u}}\|_2} $$ (34)

      其中$ \hat{R}_r $是一个均匀分布在$ [-1,1] $之间的随机变量, $ { {u}} $是一个$ n $维随机向量, 里面元素都均匀分布在$ [-1,1] $之间. 与初始的旋转变换算子相比, 快速旋转变换算子中的随机变量$ \hat{R}_r $是标量而不是一个矩阵, 因此具有较低的时间复杂度.

      Wang等[21]改进了旋转变换算子, 如下所式:

      $$ { {x}}_{k+1} = { {x}}_k+\alpha R_r \frac{{ {x}}_k+\varphi}{n \| { {x}}_k \|_2} $$ (35)

      其中, $ \varphi $是一个小的正常数, 设置为一定精度. 此改进后的算子加大了原算子跳出停滞点$ { {x}}_0 [0,0,=$$ \cdots,0]^{\rm T} $的概率.

      Wang等[21]提出了一个变异算子(mutation operator, MO)以增强多种群状态转移算法的全局搜索性能, 其数学表达式如下:

      $$ { {x}}_{k+1} = { {x}}_k+ R_{ce} R_{ak} $$ (36)

      其中$ R_{ce} $是一个$ n $维向量, 其中元素均符合在[0,1]中的均匀分布. $ R_{ak} $是一个随机变量, 服从在$ [Lb-{ {x}}_k,$$ Ub-{ {x}}_k] $内的均匀分布, $ Lb $$ Ub $分别为决策变量的上下界. 因此, 变异算子能在整个定义域内进行随机搜索. 为了避免进行过多无意义的全局搜索, 当且仅当相邻迭代的群体个数趋于一致时执行变异算子.

      Zhou等[13]提出了一个改进的平移变换, 如下所示:

      $$ { {x}}_{k+1} = { {x}}_k+\beta R_t ({ {x}}_k - { {x}}_d) $$ (37)

      其中$ \beta $为平移因子, $ R_t $为一个在$ [0,1] $区间符合均匀分布的随机数, $ { {x}}_d $是从精英候选解集中随机挑选的一个解. 该算子增加了群体之间的沟通交流, 能充分利用精英候选解集之间的信息实现启发式搜索.

    • 为了进一步提高状态转移算法的全局性和最优性, 一些借鉴于人类智慧的智能化策略也被引入状态转移算法中.

      董天雪等[10]提出了“二次状态转移”策略来增强算法的全局搜索能力. 该策略首先基于当前最优解$ { {x}}_k $进行一次状态变换, 得到了一次候选解集$ { {x}}_{temp} $, 并对此解集中的每一个解再次进行一次状态变换, 从而得到二次候选解集$ { {x}}_{k+1} $. 图6展示了求解员工指派问题时, 以$ \{1,2,3,4\} $为当前最优解并利用交换变换算子进行的二次状态转移. 此策略仅需使用一种状态变换算子就能产生具有高多样性的候选解集.

      图  6  “二次状态转移”策略

      Figure 6.  “Second transition” strategy

      文献[8]提出了“冒险与恢复”的更新策略, 算法总体上采用“贪婪准则”来保留最佳解, 而在内部算子操作时以一定概率“冒险接受”坏解, 同时在外部以另一概率“恢复”到最佳解. 如图7, 该策略允许算法在某些时刻不按适应值减小的方向演化, 使其有机会跳出局部极小并向全局极小演化, “冒险接受”坏解旨在提供摆脱局部最优的概率, “贪婪准则”和“恢复”最佳解机制保证了算法的收敛.

      图  7  “冒险与恢复”策略

      Figure 7.  “Risk and restoration in probability” strategy

      董天雪等[10]提出了“停滞回溯”的更新策略, 以提高算法跳出局部最优解的能力. 如图8, 该策略首先记录算法迭代过程中出现停滞次数$ i_c>c $的停滞解$ { {x}}_k $, $ c $为指定常数. 当前最优解停滞次数$ i_c>3c $时, 从历史停滞解集中随机选择一个作为当前最优解, 再进行下一步迭代. 实验结果表明具有“停滞回溯”策略的状态转移算法有利于缓解当前最优解重复的问题, 具有较强的全局寻优能力.

      图  8  “停滞回溯”策略

      Figure 8.  “Stagnation backtracking” strategy

      此外, Wang等[22]引入“ 正交变换”策略, 该策略旨在对算子产生的群体中适应值低的若干个较差解群体进行变异, 并根据变异后适应值贪婪更新较差解, 以增加个体多样性, 保持种群的搜索广度. Han等[23]将模拟退火思想引入状态转移算法中, 当最新状态的适应值未更优时, 以一定概率接受此状态, 其中接受概率与退火温度即算法迭代次数相关, 也增加了避免陷入局部最优的可能性.

    • 状态转移算法自提出以后, 在诸多工程实际优化问题中得到应用, 下面分别从非线性系统辨识、工业过程控制、机器学习与数据挖掘等几个方面进行概述.

    • 状态转移算法已在非线性系统辨识中获得了一些成功的应用. Zhou等[24]利用最小二乘方法将非线性系统的辨识问题转化为最优化问题, 并利用状态转移算法进行求解, 与其它进化算法的实验结果表明了该方法能有效地对非线性系统进行辨识, 是一种很有前途的非线性系统辨识方法. Bartczuk等[25]提出了一种确定动态对象时变非线性模型参数的混合方法, 该方法首先利用状态转移算法建立多个局部模型, 然后应用遗传规划方法对模型进行连接和简化, 这样不需要计算就可以获得具有较高精度的简单模型. Wang等[26]为解决混沌系统的参数辨识这一个多维参数的优化问题, 提出了基于混沌策略状态转移算法的混沌系统参数辨识方法. 该方法是在初始化时以混沌序列初始化种群, 在搜索过程中引入混沌变异机制, 利用遍历性对状态进行变异操作, 避免了过早收敛, 提高了全局搜索能力. 利用该算法辨识Lorenz混沌系统参数, 并与粒子群算法和基本状态转移算法进行比较. 仿真结果表明, 在有无噪声干扰的情况下, 该算法比粒子群算法和基本状态转移算法具有更好的辨识精度, 且比粒子群算法具有更好的收敛速度, 体现了该算法的有效性和抗干扰性, 对混沌理论的发展有重要的意义.

      Wang等[27]针对球磨过程提出了一种两阶段建模的方法, 将多个单模型划分为围绕直线对称的两部分, 与此同时, 将两阶段模型中破碎函数的参数辨识问题转化为一个复杂非线性优化问题, 并利用状态转移算法进行求解, 实验结果表明, 状态转移算法可以更快更精准的获得较好的优化结果, 在球磨过程的参数辨识中具有明显的优势. Xie等[28]通过对铝石双流溶出过程的力学分析, 结合铝石的溶出动力学, 将实验室建立的动力学模型推广到工业生产中, 利用状态转移算法对工业数据进行未知模型参数估计, 建立了基于核极值学习机的误差补偿模型, 并将动力学模型与补偿模型并行连接, 建立了氧化铝浸出率的预测模型, 并取得了理想的预测效果. Yan等[29]建立了双流法溶出过程的优化模型, 在一个酸洗周期内根据结疤程度将溶出过程分为3个阶段, 并提出一种自适应状态转移算法分别对双流法溶出过程的3个阶段进行操作参数的优化, 得到有利于节能降耗的操作条件, 为生产提供操作指导, 从而降低了生产成本, 提高了经济效益. Rajalakshmi等[30, 31]等提出了一种基于拉格朗日方法的约束状态转移算法, 并应用于造纸工艺的干燥过程及制糖工艺中的澄清过程模型参数辨识, 均取得较高的辨识精度.

    • 目前, 状态转移算法已经被应用到许多工业过程优化控制问题中. 在工业过程PID控制方面, Zhang等[32, 33] 采用状态转移算法优化分数阶PID控制器的参数, 提出一种模糊分数阶PID控制器并应用于湿法炼锌除铜过程锌粉添加量的控制. Saravanakumar等[34]采用状态转移算法优化单输入单输出基准系统中整数阶和分数阶PID控制器的参数, 在文献[35, 36]中采用状态转移算法对多输入多输出系统中多变量分散PID参数进行整定, 并提出了一种基于拉格朗日乘子法的约束状态转移算法. Zhou等[15]利用设定点跟踪策略将针铁矿生产过程中复杂的状态约束转化为附加目标, 将单优化控制问题转化为双目标优化控制问题, 并使用多目标状态转移算法求解针铁矿生产过程中PID控制器的比例系数、积分系数和微分系数. Zhang等[37]针对复杂工业过程的技术要求, 提出了一种新的离散时间分数阶PID控制策略, 采用状态转移算法实现了离散时间分数阶PID控制器优化设计, 并将该控制策略成功应用在除铜过程和锌电解过程中.

      在其它优化控制方面, Yang等[38]在研究有色冶金过程不确定优化方法中, 使用状态转移算法求解锌电解分时供电过程区间不确定优化问题. Wang等[21]提出了一种多目标优化模型来保持氧化铝蒸发工艺中电力系统运行成本与能源效率的平衡, 并提出了一种基于精英群体搜索存档策略的多目标状态转移算法来求解该多目标问题. Han等[39]提出了一种基于状态转移算法和帕累托占优的约束多目标优化方法, 用于解决针铁矿工艺中成本和效率两个目标的冲突问题, 实现针铁矿工艺中氧气和氧化锌添加量的优化控制. Xie等[40]采用控制参数化方法将针铁矿法沉铁过程氧化速率优化控制问题转化为非线性规划问题, 并通过状态转移优化算法求取最优的氧气和氧化锌控制率. Zhang等[41]针对除铜过程中控制周期与锌粉添加量的不确定性, 研究了基于控制周期的除铜过程锌粉添加优化控制方法, 并采用状态转移算法优化除铜过程锌粉添加量. Wang等[42]为解决湿法炼锌过程中微量的镉离子和钴离子小信号重叠到高浓度锌离子大信号时线性扫描伏安峰重叠的问题, 研究了一种基于状态转移算法的重叠峰分离方法, 实现了三种离子的同时测定. Huang等[43]研究了一种基于改进状态转移算法的动态优化方法, 并成功应用于湿法炼锌除铜过程动态优化问题中. Yue等[44]针对模糊Petri网难以接受专家的不一致认知和不同系统的个性化特点的问题, 提出了一种新型的自学习区间型模糊Petri网, 并将自学习问题转化为优化问题, 采用状态转移算法对该问题进行求解, 并应用于铝电解过程中. Zuo等[45]结合蒸发流程物料平衡关系以及火用分析方法, 建立了综合火用效率评价指标的能耗优化模型, 分别采用罚函数法和可行解优先法两种不同约束处理技术对约束进行处理, 并采用状态转移算法对其进行优化, 实现了氧化铝多效蒸发过程的液位控制. Yang等[46]提出了一种新的基于时间尺度变换的控制参数化方法, 将锌电解最优控制问题转化为多参数优化选择问题, 并采用状态转移算法对参数自由初始时间、自由终端时间和系统切换控制值进行优化.

    • 近年来, 机器学习有着越来越广泛的应用, 其训练过程直接影响学习效果的好坏, 而该过程可以建模成为一个模型参数优化问题. Wang等[47]提出了一种改进的状态转移算法用于小波神经网络的参数优化, 进而得到了改进状态转移算法优化的小波神经网络(state transition algorithm-wavelet neural networks, STA-WNN), 并将基于STA-WNN的极谱法应用于多金属离子浓度检测信号的在线解析, 相较于传统的基于曲线拟合和基于BP神经网络的方法, 该方法得到了更优的锌质量浓度和钴质量浓度测定结果. Chen等[48]将状态转移算法应用于一种机器学习算法——支持向量机(Support vector machine, SVM)的核参数和罚参数的寻优, 实验结果表明, 相较于遗传算法或粒子群算法, 基于状态转移算法的SVM的预测结果更为精确、稳定, 用于加氢裂化过程的动态调整能耗预测, 取得了更好的实时预测效果. Wang等[49]对最小二乘支持向量机(Least squares support vector machine, LSSVM) 进行了改进, 使用状态转移算法对其核参数与正则化参数进行优化. 其结果表明, 基于状态转移算法的LSSVM有着较高的稳定性和分类准确率. Huang等[50]利用一种新型的状态转移算法——自适应状态转移算法, 对其提出的混合支持向量回归模型中的正则化参数、核参数、不敏感空间参数、支持向量参数以及权重参数进行寻优. 实验表明, 基于自适应状态转移算法的混合支持向量回归算法有着较强的稳定性, 并在有铝电解工业电力消耗和有色冶金行业能耗的预测中取得了较好的效果.

      特征选择是数据挖掘工作中一种常见的数据预处理方法. 该过程需要从原始的特征集中寻找到最为有效的特征子集, 寻找最优特征子集的过程可以建模成一个离散最优化问题. Huang等[51]提出了一种基于二值状态转移算法和ReliefF方法的混合特征选择方法, 其中根据ReliefF方法得到的特征权重提出了一种基于特征权重的替代算子, 提高了二值状态转移算法选出特征的有效性, 最终结果在分类准确率和选出的特征数目这两个指标上都优于基于粒子群算法、遗传算法等优化算法的特征选择方法.

      复杂网络社区挖掘是数据挖掘领域的重要方向之一, 其目的是挖掘得到网络中的社区结构信息, 进而帮助人们认识复杂网络的功能和特点. 社区划分的质量可以用模块度指标度量, 通过优化模块度, 社区划分问题可转化为离散优化问题. Zhou等[52]提出了一种以模块度为目标函数的离散状态转移算法用于求解社区挖掘问题. 首先, 在全局搜索阶段, 算法设计了节点替换算子和社区替换算子两种启发式搜索算子对初始化种群进行迭代进化, 以得到更优的网络社区结构. 随后, 算法选择进化后的种群中适应度较高的个体组成精英种群. 最后, 在局部搜索阶段, 算法对精英种群采用了双路交叉策略用于产生更优解, 以帮助算法尽可能跳出局部最优解. 为验证算法性能, 算法在多个人工复杂网络和现实复杂网络中分别进行了多次测试, 测试结果表明该方法较于其他社区发现方法具有求解精度高、结果稳定等显著优点.

    • 状态转移算法在其它领域也有许多应用. Zhang等[53]提出了一种新的滤波协同状态转移算法来求解双目标动态无功优化问题. Zhou等[54]提出了一种求解水资源网络管道优化的离散状态转移算法, 在某些水资源网络实例中取得了比已有最好解更优的结果, 并在文献综述[55]中得到报道. Huang等[56]提出了一种基于认知启发的状态转移算法的来求解线性双层规划问题. Pan等[57]提出了一种基于状态转移算法的温度测量新方法用于补偿粉尘引起的测量误差. Xie等[58, 59, 60, 61]提出了一种基于时间配准和状态转移算法的非线性分层数据协调方法, 提高了测量精度, 并对未测变量进行了估计, 提高数据协调方法的鲁棒性. 吴佳等[62]提出了一种基于状态转移算法的泡沫图像特征优化设定方法. Wang等[63]将状态转移算法用于求解氧气底吹铜熔炼过程的计算热力学模型. Zhu等[64]提出了一种基于状态转移算法的时效炉铝合金工件温度预测方法. Huang等[65]提出了基于状态转移算法的自适应时间序列表示方法, 并应用于铝电解过程中的一种时间序列数据阳极电流信号, 实验表明, 在铝电解阳极电流信号的时间序列降维中取得了较好的效果. Gui等[66]调研了包括状态转移算法等智能优化算法在有色冶金过程建模与优化控制中的应用. 此外, Han等[67, 68]提出了一种基于状态转移算法的多阈值分割方法来进行图像分析与处理. Huang等[69]提出了基于状态转移算法的自适应过采样方法. 在地球物理领域, Zhao等[70]将状态转移算法应用到基于引力场数据的水下多运动目标问题中.

    • 尽管目前状态转移算法的研究取得了一定的成果, 但状态转移算法的研究尚处于探索阶段, 其在理论与应用方面的研究都有待进一步挖掘.

      1) 状态转移算法的理论研究

      现阶段状态转移算法还可以从以下几个方面进行研究: 针对变换因子的选取, 可以考虑变换因子的动态自适应调整; 针对采样策略的变换, 将有规则采样如拉丁超立方等采样方式代替随机采样; 针对状态变换算子的调用研究, 可考虑不同算子的组合使用及算子使用的先后顺序; 针对候选解的选择策略, 增加一类非贪婪选择策略, 如以一定的概率接收非最优解; 针对当前最优解的更新策略, 研究一类智能化的自调节更新策略, 如计算当前最优解未被更新的次数, 判断是否需要用其他的次优解代替当前最优解; 针对基于种群的状态转移算法, 可以从种群的信息交换、信息共享等方面着手研究等.

      状态转移算法框架的理论研究, 可以从以下几点展开: 针对多目标优化问题, 可以进一步深入研究多目标状态转移算法, 以提升多目标优化问题在分布性与收敛性上的性能, 同时, 也需要对离散多目标状态转移算法、多目标约束状态转移算法及区间多目标状态转移算法进行拓展研究; 针对约束优化问题, 着重加强算法的全局与局部搜索能力, 如状态转移算法与其他算法的结合或者算子的改进与创造, 以克服约束优化中的可行域不连续、可行域狭小等一系列难点.

      2) 状态转移算法的应用研究

      目前状态转移算法在有色冶金建模与优化控制中得到了很好的应用, 但由于有色金属冶炼工艺机理复杂, 生产过程不确定性严重, 反应过程各工艺参数之间耦合严重等复杂特性, 而考虑单一特性的有冶金生产过程自动化的建模、控制与优化不足以反映整个生产过程的实质. 因此, 状态转移算法在该领域的研究有待进一步深入, 在其它领域的研究也有待进一步拓展[71, 72, 73].

参考文献 (73)

目录

    /

    返回文章
    返回