基于增强学习的动态优化问题模型及算法研究

Many real-world applications are dynamic optimization problems (DOPs) in nature, whose global optimal solutions are dynamic and time-varying. At present, unfortunately, there is not a uniform understanding about the essence of DOPs. All existing methods have failed to adapt characteristics of various DOPs automatically. Thus, the computational results are not so satisfactory..In this project, the essential characteristics of DOPs will be studied from the idea of multiple-decision-making in Reinforcement Learning (RL) community and a decision model of DOPs will be proposed. On the basis of the decision model, the connection of Evolutionary Dynamic Optimization (EDO) and Reinforcement Learning (RL), which are applied to (semi-) DOPs and decision problems respectively, is established. A more general and more efficient hybrid algorithm framework for solving DOPs will be proposed combining advantages of both methods. Moreover, the multi-objective features of DOPs will be studied. And the construction method of artificial functions which characterize the multi-objective features of DOPs will also be studied. Then, combining techniques of multi-objective optimization and chaos mapping techniques, some self-adaptive algorithms for solving different type of DOPs will be proposed..Through the research in this project, the essential of DOPs will be discovered. And a united decision model of DOPs will be presented. Moreover, a more general and more efficient hybrid algorithm framework which can automatically adapt to various DOPs will be established.

许多现实世界的应用实际上是动态的、具有时变的全局最优解的动态优化问题。但目前对动态优化问题的本质还没有统一的认识。现有的求解方法不能自动适应不同类型的动态优化问题的特点，得到的结果不尽如人意。.本项目从增强学习领域中决策思想出发，探究动态优化问题的本质特征，尝试建立动态优化问题的决策模型。在此基础上，建立用于求解动态优化问题的演化动态优化方法与用于求解(半)马尔科夫决策问题的增强学习方法之间的联系，综合两种方法的优点，提出求解动态优化问题的更一般、更有效的混合算法框架。本项目进一步研究动态优化问题的多目标特性，研究刻画其多目标特性的人工目标函数的构造方法，结合演化多目标优化和混沌映射技术，探索求解不同类型动态优化问题的自适应算法。.通过本项目的研究，期望揭示动态优化问题的本质，建立动态优化问题的决策模型，提出能够自动适应不同类型动态优化问题的更一般、更有效的混合算法框架。

许多生产实践中的优化问题都表现出动态性质，即优化的目标函数或待求解的问题会随时间而发生(随机)变化。演化计算方法被广泛应用于求解动态优化问题。然而，目前的演化动态优化算法在运行过程中会逐步收敛，其收敛性使得它难以应对变化的环境，失去了对新环境的适应能力。研究并设计新的策略来帮助提升演化动态优化算法在动态环境中的适应能力具有重要的理论和实践价值。为此，本项目完成了以下研究内容：. (1) 基于决策论思想，研究动态优化问题的本质特征，尝试建立动态优化问题与(半)马尔科夫决策问题之间的联系，把动态优化问题和决策问题纳入到一个统一的框架中。提出能够抓住动态优化问题与静态优化问题本质区别的表示方法，设计能够体现动态优化问题本质特征的benchmark 问题的生成器，为进一步研究求解动态优化问题的方法奠定基础。. (2) 根据增强学习方法和演化动态优化方法的基本思想，深入研究两种方法的本质特点，分析各自擅长求解的动态优化问题类型。尝试建立增强学习方法与演化动态优化方法之间的联系，综合两种方法的优点，提出更一般、更高效的混合方法。. (3) 研究达成动态优化问题的两个目标的基于多群的方法。一方面研究快速准确定位当前环境的最优解的方法；另一方面研究追踪最优解的动态变化的方法。更好地平衡求解算法搜索过程的探索(exploration)和利用(exploitation)两个方面，从而提出求解动态优化问题的自适应算法。. 本项目针对研究内容(1)，归纳了动态优化问题的几个本质特征，在此基础上基于马尔科夫决策过程建立了其数学模型。针对研究内容(2)，提出了基于强化学习的演化动态优化算法框架。针对研究内容(3)，提出了自适应的多群动态优化算法框架。提出来的框架在不同峰数MPB问题上取得了与现有最佳算法一样好的结果。