2.793

                    2018影響因子

                    (CJCR)

                    • 中文核心
                    • EI
                    • 中國科技核心
                    • Scopus
                    • CSCD
                    • 英國科學文摘

                    留言板

                    尊敬的讀者、作者、審稿人, 關于本刊的投稿、審稿、編輯和出版的任何問題, 您可以本頁添加留言。我們將盡快給您答復。謝謝您的支持!

                    姓名
                    郵箱
                    手機號碼
                    標題
                    留言內容
                    驗證碼

                    狀態轉移算法原理與應用

                    周曉君 陽春華 桂衛華

                    周曉君, 陽春華, 桂衛華. 狀態轉移算法原理與應用. 自動化學報, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    引用本文: 周曉君, 陽春華, 桂衛華. 狀態轉移算法原理與應用. 自動化學報, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its applications. Acta Automatica Sinica, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    Citation: Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its applications. Acta Automatica Sinica, 2020, 46(11): 2260?2274. 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, 61621062, 61860206014), 111項目(B17048), 湖南省自然科學基金(2018JJ3683)資助

                    The Principle of State Transition Algorithm and Its Applications

                    More Information
                    • Fund Project:  Supported by the National Natural Science Foundation of China (61873285, 61621062, 61860206014), the 111 Project (B17048) 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

                      360彩票
                    • [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] 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] Gao D Y. Canonical duality theory: Unified understanding and generalized solution for global optimization problems. Computers & Chemical Engineering, 2009, 33(12): 1964?1972
                      [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 J, Gao D Y, Yang C H. A comparative study of state transition algorithm with harmony search and artificial bee colony. In: Proceedings of the 8th International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013. Berlin, Heidelberg: 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. 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. Guilin, China: IEEE, 2016. 2115?2119
                      [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

                      Yang Chun-Hua, Tang Xiao-Lin, Zhou Xiao-Jun, Gui Wei-Hua. A discrete state transition algorithm for traveling salesman problem. Control Theory & Applications, 2013, 30(8): 1040?1046 doi:  10.7641/CTA.2013.12167
                      [10] 董天雪, 陽春華, 周曉君, 桂衛華. 一種求解企業員工指派問題的離散狀態轉移算法. 控制理論與應用, 2016, 33(10): 1378?1388 doi:  10.7641/CTA.2016.50982

                      Dong Tian-Xue, Yang Chun-Hua, Zhou Xiao-Jun, Gui Wei-Hua. A novel discrete state transition algorithm for staff assignment problem. Control Theory & Applications, 2016, 33(10): 1378?1388 doi:  10.7641/CTA.2016.50982
                      [11] Han J, Dong T X, Zhou X J, Yang C H, Gui W H. State transition algorithm for constrained optimization problems. In: Proceedings of the 33rd Chinese Control Conference. Nanjing, China: IEEE, 2014. 7543?7548
                      [12] Han J, Yang C H, Zhou X J, 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] 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, 2019: 4727168
                      [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. Dalian, China: IEEE, 2017. 9859?9864
                      [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] Zhou X J, Hanoun S, Gao D Y, Nahavandi S. A multiobjective state transition algorithm for single machine scheduling. Advances in Global Optimization. Cham, Germany: Springer, 2015. 79?88
                      [17] 周曉君, 周佳佳, 徐沖沖. 一種基于分解的多目標狀態轉移優化方法及系統, 中國CN201910313379.4, 2019年8月23日.

                      Zhou Xiao-Jun, Zhou Jia-Jia, Xu Chong-Chong. Decomposition-based Multi-objective State Transition Optimization Method and System, China CN201910313379.4, August 23, 2019
                      [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, 2019, 49(10): 3722?3730 doi:  10.1109/TCYB.2018.2850350
                      [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] 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] 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] 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] 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] 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: Proceedings of the 16th International Conference on Artificial Intelligence and Soft Computing. Zakopane, Poland: Springer, 2017. 209?220
                      [26] 王聰, 張宏立. 基于混沌策略狀態轉移算法的混沌系統參數辨識. 計算機應用研究, 2016, 33(5): 1346?1349 doi:  10.3969/j.issn.1001-3695.2016.05.015

                      Wang Cong, Zhang Hong-Li. Parameter identification in chaotic systems based on state transition algorithm combined with chaotic strategy. Application Research of Computers, 2016, 33(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: Proceedings of the 6th International Symposium on Advanced Control of Industrial Processes. Taipei, China: IEEE, 2017. 251?256
                      [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

                      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] 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] Murugesan R, Solaimalai J, Chandran K. Computer-aided controller design for a nonlinear process using a Lagrangian-based state transition algorithm. Circuits, Systems, and Signal Processing, 2020, 39(2): 977?996 doi:  10.1007/s00034-019-01139-5
                      [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] 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, Kadhar K M A. State Transition Algorithm (STA) based tuning of integer and fractional-order PID controller for benchmark system. In: Proceedings of the 2015 IEEE International Conference on Computational Intelligence and Computing Research. Madurai, India: IEEE, 2015. 1?5
                      [35] Saravanakumar G, Valarmathi K, Rajasekaran M P, Srinivasan S, Iruthayarajan M W, Balas V E. Tuning of multivariable decentralized PID controller using state transition algorithm. Studies in Informatics and Control, 2015, 24(4): 367?378
                      [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] 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

                      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] 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

                      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

                      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 & Applications, 2017, 34(10): 1388?1395 doi:  10.7641/CTA.2017.60621
                      [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. Dalian, China: IEEE, 2017. 4407?4412
                      [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, 10(12): 3499?3520 doi:  10.1007/s13042-019-00940-7
                      [45] 左健, 謝永芳, 王曉麗, 王峰, 陽春華. 基于分析的氧化鋁多效蒸發過程液位優化設定方法. 化工學報, 2017, 68(3): 1005?1013

                      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] 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

                      Wang 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, Wang Y L. Power consumption prediction for dynamic adjustment in hydrocracking process based on state transition algorithm and support vector machine. In: Proceedings of the 24th International Conference on Neural Information Processing. Guangzhou, China: Springer, 2017. 85?94
                      [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] 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, 2020, 12(2): 357?368 doi:  10.1007/s12559-019-09644-0
                      [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, 2019, 23(5): 1888?1898 doi:  10.1109/JBHI.2018.2872811
                      [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: 89?99 doi:  10.1016/j.neucom.2019.01.009
                      [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] Zhou X J, Gao D Y, Simpson A R. Optimal design of water distribution networks by a discrete state transition algorithm. Engineering Optimization, 2016, 48(4): 603?628 doi:  10.1080/0305215X.2015.1025775
                      [55] Mala-Jetmarova H, Sultanova N, Savic D. Lost in optimisation of water distribution systems? A literature review of system operation. Environmental Modelling & Software, 2017, 93: 209?254
                      [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] 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] 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] 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] 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(38): 12861?12870
                      [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

                      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] 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] 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(4): 47?59 doi:  10.4236/ijnm.2017.64004
                      [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] 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. Hangzhou, China: IEEE, 2015. 2662?2666
                      [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] 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. Neural Computing and Applications, 2020, 32(11): 7183?7199 doi:  10.1007/s00521-019-04208-7
                      [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, 2020, 17(2): 192?196 doi:  10.1109/LGRS.2019.2917784
                      [71] 劉亞東, 牛大鵬, 常玉清, 王福利, 張永京. 基于區間數的黃金濕法冶煉過程建模與優化研究. 自動化學報, 2019, 45(5): 927?940

                      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

                      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

                      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]. 自動化學報, 2020, 46(5): 957-970. doi: 10.16383/j.aas.c170657
                      [2] 王柳靜, 張貴軍, 周曉根. 基于狀態估計反饋的策略自適應差分進化算法[J]. 自動化學報, 2020, 46(4): 752-766. doi: 10.16383/j.aas.2018.c170338
                      [3] 孫天元, 王永才, 李德英. 圖實現算法綜述與評測分析[J]. 自動化學報, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561
                      [4] 龍文, 伍鐵斌, 唐明珠, 徐明, 蔡紹洪. 基于透鏡成像學習策略的灰狼優化算法[J]. 自動化學報, 2020, 46(10): 2148-2164. doi: 10.16383/j.aas.c180695
                      [5] 田夢楚, 薄煜明, 陳志敏, 吳盤龍, 趙高鵬. 螢火蟲算法智能優化粒子濾波[J]. 自動化學報, 2016, 42(1): 89-97. doi: 10.16383/j.aas.2016.c150221
                      [6] 周曉根, 張貴軍, 郝小虎. 局部抽象凸區域剖分差分進化算法[J]. 自動化學報, 2015, 41(7): 1315-1327. doi: 10.16383/j.aas.2015.c140680
                      [7] 張浩杰, 龔建偉, 姜巖, 熊光明, 陳慧巖. 基于變維度狀態空間的增量啟發式路徑規劃方法研究[J]. 自動化學報, 2013, 39(10): 1602-1610. doi: 10.3724/SP.J.1004.2013.01602
                      [8] 郭春釗, 山部尚孝, 三田誠一. 基于立體視覺平面單應性的智能車輛可行駛道路邊界檢測[J]. 自動化學報, 2013, 39(4): 371-380. doi: 10.3724/SP.J.1004.2013.00371
                      [9] 辛斌, 陳杰, 彭志紅. 智能優化控制:概述與展望[J]. 自動化學報, 2013, 39(11): 1831-1848. doi: 10.3724/SP.J.1004.2013.01831
                      [10] 江賀, 邱鐵, 胡燕, 李明楚, 羅鐘鉉. 啟發式算法設計中的骨架分析與應用[J]. 自動化學報, 2011, 37(3): 257-269. doi: 10.3724/SP.J.1004.2011.00257
                      [11] 張德富, 陳勝達, 劉艷娟. 求解矩形Packing問題的基于遺傳算法的啟發式遞歸策略[J]. 自動化學報, 2007, 33(9): 911-916. doi: 10.1360/aas-007-0911
                      [12] 李換琴, 萬百五. 基于填充函數算法的工業產品小波網絡質量模型[J]. 自動化學報, 2004, 30(2): 283-287.
                      [13] 薛雷, 郝躍. 基于Petri網的啟發式生產調度[J]. 自動化學報, 2002, 28(5): 827-831.
                      [14] 張偉, 劉積仁, 李華天. 基于函數逼近的學習式搜索[J]. 自動化學報, 1994, 20(2): 235-239.
                      [15] 崔國偉. 基于模糊啟發式搜索的漢字識別方法[J]. 自動化學報, 1993, 19(1): 126-128.
                      [16] 汪濤, 邢小良, 莊新華. 無對應點三維表面重建的全局優化算法[J]. 自動化學報, 1993, 19(4): 497-499.
                      [17] 何敏, 呂勇哉. 基于混合知識表達模型的啟發式優化控制策略及其應用[J]. 自動化學報, 1992, 18(3): 371-375.
                      [18] 胡慶, 楊靜宇, 張黔, 劉克. 基于知識的印鑒鑒別方法[J]. 自動化學報, 1991, 17(6): 696-704.
                      [19] 戴學東, 呂勇哉. 兩級多品種生產調度的專家系統[J]. 自動化學報, 1990, 16(2): 134-141.
                      [20] 楊永耀, 呂勇哉. 板坯加熱爐的遞階計算機控制[J]. 自動化學報, 1989, 15(4): 303-310.
                    • 加載中
                    圖(8)
                    計量
                    • 文章訪問數:  2767
                    • HTML全文瀏覽量:  3389
                    • PDF下載量:  115
                    • 被引次數: 0
                    出版歷程
                    • 收稿日期:  2019-09-03
                    • 錄用日期:  2019-12-15
                    • 網絡出版日期:  2020-01-17
                    • 刊出日期:  2020-11-20

                    狀態轉移算法原理與應用

                    doi: 10.16383/j.aas.c190624
                      基金項目:  國家自然科學基金(61873285, 61621062, 61860206014), 111項目(B17048), 湖南省自然科學基金(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(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    引用本文: 周曉君, 陽春華, 桂衛華. 狀態轉移算法原理與應用. 自動化學報, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its applications. Acta Automatica Sinica, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    Citation: Zhou Xiao-Jun, Yang Chun-Hua, Gui Wei-Hua. The principle of state transition algorithm and its applications. Acta Automatica Sinica, 2020, 46(11): 2260?2274. doi: 10.16383/j.aas.c190624
                    • 由于現實世界的復雜性, 很多實際工程最優化問題具有眾多的局部最優解, 而人們希望找到這些局部最優解中的最好解, 即全局最優解, 這使得全局優化在工程實際中得到了廣泛的應用[1]. 考慮到對于一般的最優化問題, 目前還不存在能保證找到全局最優解的統一有效算法(即多項式時間算法). 國內外學者主要從以下三個角度來研究全局優化: 1) 在非多項式時間找到一般優化問題的全局最優解, 比如分支定界法、分支切割法[2]等; 2) 在多項式時間內找到具有某些特定結構優化問題的全局最優解, 比如凸優化、對偶理論[3]等; 3) 在多項式時間內找到一般優化問題的近似最優解, 比如遺傳算法、粒子群優化、差分進化以及本文要介紹的狀態轉移算法等.

                      自上世紀70年代美國密歇根大學約翰·霍蘭德教授最早提出的遺傳算法以來, 以遺傳算法為代表的智能優化算法得到了長足的發展, 涌現了諸如模擬退火、蟻群算法、粒子群優化等眾多新型智能優化算法, 正在成為智能科學、信息科學、人工智能中最為活躍的研究方向之一, 并在諸多工程領域得到迅速推廣和應用. 目前大多數智能優化算法都是以行為主義模仿學習為主, 通過模擬自然界鳥群、蜂群、魚群等生物進化來求解復雜優化問題. 然而, 基于行為主義的智能優化算法主要是模仿, 帶有一定的機械性和盲從性. 一方面, 這種基于模仿表象學習的方法造成算法的可擴展性差, 大多數傳統智能優化算法在某些問題上低維時表現良好, 維度變高時效果顯著變差; 另一方面, 它使得算法容易出現諸如停滯或早熟收斂等現象, 即算法可能停滯在任意隨機點, 而不是嚴格意義上的最優解.

                      為了消除傳統智能優化算法容易陷入停滯現象、提高算法的可擴展性和拓寬智能優化算法的應用范圍, Zhou等[4]于2012年原創性地提出了一種基于結構主義學習的新型智能優化算法—狀態轉移算法. 它抓住最優化算法的本質、目的和要求, 以全局性、最優性、快速性、收斂性、可控性五大核心結構要素為體系框架. 它的基本思想是將最優化問題的一個解看成是一個狀態, 解的迭代更新過程看成是狀態轉移過程, 利用現代控制理論中的狀態空間表達式來作為產生候選解的統一框架, 基于此框架來設計狀態變換算子. 與大多數基于種群的智能優化算法不同, 基本的狀態轉移算法是一種基于個體的智能優化算法, 它基于給定當前解, 通過采樣方式, 多次獨立運行某種狀態變換算子產生候選解集, 并與當前解進行比較, 迭代更新當前解, 直到滿足某種終止條件. 值得一提的是, 基本狀態轉移算法中的每種狀態變換算子都能夠產生具有規則形狀、可控大小的幾何鄰域, 它設計了包括旋轉變換、平移變換、伸縮變換、軸向搜索等不同的狀態變換算子以滿足全局搜索、局部搜索以及啟發式搜索等功能需要, 并且以交替輪換的方式適時地使用各種不同算子, 使得狀態轉移算法能夠以一定概率很快找到全局最優解[5-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) $為目標函數或者評價函數.

                        具體來說, 一方面, 狀態轉移算法中專門設計了局部、全局和啟發式搜索算子, 其中全局搜索算子是為了保證有一定概率使產生的候選解集形成的鄰域中包含全局最優解; 局部搜索算子具有在較小鄰域進行精細搜索的功能; 啟發式搜索算子用來產生具有一定潛在更好價值的候選解, 避免搜索的盲目性. 另一方面, 狀態轉移算法中設計了特定的選擇與更新策略, 用來適應不同優化問題的需要. 更進一步地, 狀態轉移算法中實施了智能化策略, 比如全局和局部算子的交替調用, 可以很大程度上縮短尋找全局最優解的時間和避免陷入局部最優; 采樣方式的使用, 可以選擇有代表性的候選解, 避免窮舉鄰域內的所有解, 將極大地縮短搜索時間.

                        一般地, 狀態轉移算法的基本流程如下: 1) 從當前最好解出發, 通過某種狀態變換算子生成具有某種特定性質的鄰域; 2) 以某種采樣機制從該鄰域內采集一定數目的樣本; 3) 根據評價機制, 比較當前最好解與采集樣本中最好解的優劣, 并以某種更新機制更新當前最好解; 4) 返回步驟1), 并交替使用各種狀態變換算子, 直到滿足某種終止條件.

                        在狀態轉移算法的基本框架上, 尋優的最終結果可以從收斂性和全局性兩方面來考慮. 為了闡述其性質, 有以下兩個假設.

                        假設 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\nolimits_{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\nolimits_{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}}}, \;\;\;{\text{若}}\; f({{{newBest}}}) < f({{{Best}}}) \\ &{{{Best}}},\;\;\;\;\;\; \;\;\;\;\;{\text{其他}} \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} = 1\times10^{-4},$$\beta = 1, \gamma = 1, \delta = 1,$$SE = 30,$$fc = 2 $. 其中平移、伸縮和軸向因子都保持恒定, 旋轉因子$ \alpha $以指數的方式進行衰減, 底數為$ \frac{1}{fc} $, 并且以周期性的方式在最大值$ \alpha_{\max} $和最小值$ \alpha_{\min} $之間進行變化.

                      • 基本狀態轉移算法內在機理可以從以下五個特性進行闡述和解釋, 它包括:

                        1) 全局性, 狀態轉移算法具有在整個空間進行搜索的能力;

                        2) 最優性, 狀態轉移算法可以保證找到一個最優解;

                        3) 快速性, 狀態轉移算法盡可能地節省搜索時間;

                        4) 收斂性, 通過狀態轉移算法產生的解序列是收斂的;

                        5) 可控性, 狀態轉移算法可以控制搜索空間的幾何形狀與大小.

                      • 狀態轉移算法的全局性主要通過設計的伸縮變換算子保證. 伸縮算子具有在整個空間進行搜索的能力, 當前最好解通過伸縮變換作用, 得到的所有候選解集將分布在[$ -\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{split} &\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{split} $$ (13)

                        其中, $ f({{x}}) $表示目標函數, $ g_{i}({{x}}) $$ h_{j}({{x}}) $分別表示不等式約束和等式約束函數, 其個數分別為$ p $$ q $, $ u_{k} $$ l_{k} $分別表示決策變量$ {x}_{k} $的上下界.

                        為了求解約束優化問題, 需引入約束處理策略, 用來比較任意兩個候選解孰優孰劣. 常用的約束處理策略有如下幾種:

                        1) 罰函數法

                        罰函數法又稱乘子法, 它的適應度函數由目標函數和帶罰因子的約束違反度組成, 由此將約束優化問題轉化為無約束優化問題, 對候選解采用統一的適應度函數進行比較. 常用的罰函數如下

                        $$ F({ {x}}) = f({ {x}}) + \sigma\times 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.

                        2) 可行性優先法

                        可行性優先法是優先考慮候選解的可行性, 然后考慮其對應的目標函數值, 它給出了如下三條規則用來比較任意兩個候選解:

                        a) 若兩個候選解均為不可行解, 則選擇約束違反度較小的候選解;

                        b)若一個候選解為不可行解, 另一個為可行解, 則選擇可行的候選解;

                        c) 若兩個候選解均為可行解, 則選擇目標函數值較小的候選解.

                        3) 兩階段法

                        兩階段法是在處理約束的時候分階段采用不同的約束處理策略. 在第一階段, 采用可行性優先法, 迅速尋找可行解, 并進入可行域. 在第二階段, 采用靜態罰函數法, 如式(14). 文獻[11-12]提出了基于兩階段法的約束狀態轉移算法, 并將該方法用于求解幾種典型的工程約束優化問題, 與基于罰函數法和可行性優先法的約束狀態轉移算法相比, 獲得了更好的優化結果.

                        4) 偏好權衡策略法

                        文獻[13]提出了基于偏好權衡策略的狀態轉移算法, 該方法將狀態轉移算法和偏好權衡約束處理策略相結合成功用于求解鋅電解過程中的電力調度優化問題. 其基本思想是: 首先根據可行率權衡可行解及不可行解個數, 如式(16)和(17). 然后對可行解僅采用目標函數值進行排序, 偏好選擇目標函數值較小的候選解; 而不可行解使用歸一化的罰函數法進行權衡, 如式(18) ~ (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 \times 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)\cap \\ \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占優及基于分解的方法, 下面將分別介紹.

                        1) 基于Pareto占優的多目標狀態轉移算法

                        基于Pareto占優算法是以Pareto占優為比較準則的一類算法. 其基本思想如下: 首先通過狀態變換算子產生候選解集, 利用Pareto占優概念對候選解進行比較, 選擇出非占優的解, 此外還需要設計一些多樣性維護算子, 從非占優解中剔除處于密集區域的解, 保留分布較為均勻的解, 使得候選解分布較為均勻.

                        文獻[14]提出了基于開放檔案袋的多目標狀態轉移算法. 該算法將狀態變換算子、快速非支配排序和擁擠距離算子結合, 將搜索到的全部非占優解都儲存在檔案袋中, 不斷進行迭代進化, 直至算法終止. 具體來說, 首先在決策空間中均勻隨機產生初始候選解集, 利用快速非支配排序找到處于第一前沿的解并將其保存在檔案袋中, 之后利用擁擠距離從檔案袋中剔除處于密集區域的解, 之后利用狀態變換算子產生新的候選解集, 不斷進行上述步驟直至算法終止. 經過標準測試函數的測試, 該算法可以獲得具有較好的收斂性和分布性的最優解集.

                        文獻[15]提出一種基于相對擁擠距離的多目標狀態轉移算法, 同樣也采用了Pareto占優對候選解進行比較. 該算法利用檔案袋將候選解比較過程中的非占優解進行存儲, 采用基于相對擁擠距離的多樣性維護策略對候選解進一步選擇, 該策略通過計算相鄰候選解之間的擁擠距離, 對候選解之間的距離相對遠近做出判斷, 將相對距離較近的候選解進行剔除, 使得候選解可以較為均勻地分布在目標函數前沿上, 該算法成功應用于濕法煉鋅沉鐵過程的多目標優化控制問題.

                        文獻[16]提出一種基于Pareto占優的離散多目標狀態轉移算法, 該算法利用非支配排序策略從候選解集中選擇最好的候選解, 利用離散狀態變換算子搜索新的候選解集, 并設計Pareto檔案袋策略將找到的非占優解進行保存. 所提算法在一類單機器調度問題上展現出很好的性能, 并和其他算法對比的實驗結果驗證了該算法的有效性.

                        2) 基于分解的多目標狀態轉移算法

                        基于分解的多目標優化算法將多目標優化問題轉化成為多個等價的單目標優化子問題進行求解, 每一個單目標優化子問題的最優解都對應原問題的一個Pareto最優解, 最終獲得多目標優化問題的Pareto最優解集. 常見的分解方法如下:

                        a) 權重向量求和法

                        權重求和法是對每一個目標函數分配一個權重, 對所有的目標函數求權重和, 該方法具有明確的幾何意義, 其函數值等于候選解目標函數向量在權重方向上的投影. 其數學表達式如下

                        $$ {\rm {min}}\; 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}} \; g^{te}({{x}}|{{\lambda}}) = {\rm{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}} \; g^{pbi} = d_1 + \theta d_2 \\ & {\rm {s.t.}} \quad d_1 = \frac{{||({{F}}({{x}})-{{z}}^*)}^{\rm T}\lambda||}{||\lambda||} \\ & \qquad\; d_2 = ||{{F}}({{x}})-({{z}}^*-d_1 {\lambda})|| \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})}}-{{z}}^*||}-1) $$ (29)

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

                        $$ {\rm {min}} \; 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 \;{{\text{若}}\;c < {c_{\min }}}\\& {\frac{1}{{fc}} \times \alpha (\beta ),}\quad {{\text{若}}\;c > {c_{\max }}}\\& {\alpha (\beta ),}\qquad \quad \;\;{{\text{其他}}} \end{aligned}} \right. $$ (32)

                        其中, $ c $表示計數器, 定義如下:

                        $$ c = \left\{ {\begin{aligned} &{\max (0,c - 1),}\quad{{\text{若}}\;f({{Bes}}{{{t}}_k}) - f({{Bes}}{{{t}}_{k - 1}}) < \tau }\\ &{\max (0,c + 1),}\quad{{\text{其他}}} \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]提出了一種確定動態對象時變非線性模型參數的混合方法, 該方法首先利用狀態轉移算法建立多個局部模型, 然后應用遺傳規劃方法對模型進行連接和簡化, 這樣不需要計算就可以獲得具有較高精度的簡單模型. 王聰等[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控制器優化設計, 并將該控制策略成功應用在除銅過程和鋅電解過程中.

                        在其他優化控制方面, 陽春華等[38]在研究有色冶金過程不確定優化方法中, 使用狀態轉移算法求解鋅電解分時供電過程區間不確定優化問題. Wang等[21]提出了一種多目標優化模型來保持氧化鋁蒸發工藝中電力系統運行成本與能源效率的平衡, 并提出了一種基于精英群體搜索存檔策略的多目標狀態轉移算法來求解該多目標問題. Han等[39]提出了一種基于狀態轉移算法和帕累托占優的約束多目標優化方法, 用于解決針鐵礦工藝中成本和效率兩個目標的沖突問題, 實現針鐵礦工藝中氧氣和氧化鋅添加量的優化控制. 謝世文等[40]采用控制參數化方法將針鐵礦法沉鐵過程氧化速率優化控制問題轉化為非線性規劃問題, 并通過狀態轉移優化算法求取最優的氧氣和氧化鋅控制率. 張鳳雪等[41]針對除銅過程中控制周期與鋅粉添加量的不確定性, 研究了基于控制周期的除銅過程鋅粉添加優化控制方法, 并采用狀態轉移算法優化除銅過程鋅粉添加量. Wang等[42]為解決濕法煉鋅過程中微量的鎘離子和鈷離子小信號重疊到高濃度鋅離子大信號時線性掃描伏安峰重疊的問題, 研究了一種基于狀態轉移算法的重疊峰分離方法, 實現了多種離子的同時測定. Huang等[43]研究了一種基于改進狀態轉移算法的動態優化方法, 并成功應用于濕法煉鋅除銅過程動態優化問題中. Yue等[44]針對模糊Petri網難以接受專家的不一致認知和不同系統的個性化特點的問題, 提出了一種新型的自學習區間型模糊Petri網, 并將自學習問題轉化為優化問題, 采用狀態轉移算法對該問題進行求解, 并應用于鋁電解過程中. 左鍵等[45]結合蒸發流程物料平衡關系以及火用分析方法, 建立了綜合火用效率評價指標的能耗優化模型, 分別采用罰函數法和可行解優先法兩種不同約束處理技術對約束進行處理, 并采用狀態轉移算法對其進行優化, 實現了氧化鋁多效蒸發過程的液位控制. Yang等[46]提出了一種新的基于時間尺度變換的控制參數化方法, 將鋅電解最優控制問題轉化為多參數優化選擇問題, 并采用狀態轉移算法對參數自由初始時間、自由終端時間和系統切換控制值進行優化.

                      • 近年來, 機器學習有著越來越廣泛的應用, 其訓練過程直接影響學習效果的好壞, 而該過程可以建模成為一個模型參數優化問題. 王雅琳等[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-61]提出了一種基于時間配準和狀態轉移算法的非線性分層數據協調方法, 提高了測量精度, 并對未測變量進行了估計, 提高數據協調方法的魯棒性. 吳佳等[62]提出了一種基于狀態轉移算法的泡沫圖像特征優化設定方法. Wang等[63]將狀態轉移算法用于求解氧氣底吹銅熔煉過程的計算熱力學模型. Zhu等[64]提出了一種基于狀態轉移算法的時效爐鋁合金工件溫度預測方法. Huang等[65]提出了基于狀態轉移算法的自適應時間序列表示方法, 并應用于鋁電解過程中的一種時間序列數據陽極電流信號, 實驗表明, 在鋁電解陽極電流信號的時間序列降維中取得了較好的效果. Gui等[66]調研了包括狀態轉移算法等智能優化算法在有色冶金過程建模與優化控制中的應用. 此外, Han等[67-68]提出了一種基于狀態轉移算法的多閾值分割方法來進行圖像分析與處理. Huang等[69] 提出了基于狀態轉移算法的自適應過采樣方法. 在地球物理領域, Zhao等[70]將狀態轉移算法應用到基于引力場數據的水下多運動目標問題中.

                      • 與常規的基于行為主義模仿學習為主的智能優化算法不同, 狀態轉移算法是一種基于結構主義學習的新型智能全局優化算法, 它抓住最優化算法的本質、目的和要求, 從而不會陷入停滯點, 不容易陷入局部最優, 且具有全局搜索能強、尋優速度快、擴展性好、可控性高等顯著優點. 本文系統地闡述了狀態轉移算法的基本原理和內在特性, 并從理論研究與應用研究兩方面對狀態轉移算法進行了詳細介紹. 目前狀態轉移算法在有色冶金過程建模與優化控制中得到了很好的應用, 在其他領域的研究也有待進一步拓展[71-73].

                    參考文獻 (73)

                    目錄

                      /

                      返回文章
                      返回