进化优化中的变量约简策略研究

In response to the bottlenecks of “curse of dimensionality” and insufficiency in dealing with equality constraint problem, this project proposes a variable reduction strategy based on the variable relationships extracting from the equality optimality condition of an optimization problem. The variable reduction strategy follows the principle of “integrating evolutionary algorithms (EAs) with problem domain knowledge” and is able to shrink solution space, eliminate equality constraints and improve the efficiency of EAs, hence it provides an effective approach for conquering the aforementioned bottlenecks. To realize the goal above, it is necessary to finish the following three research aspects. First, we refine the general form of equation system for equality optimality conditions of an optimization problem, analyze the reduction potential of an equation system and construct the framework of variable reduction process. Second, we propose a method for detecting and extracting variable types and variable relationships from equation systems. Based on the explicit variable relationships, we develop an exact variable reduction strategy and according to the implicit variable relationships, we design an approximate variable reduction strategy. Third, we design an effective mechanism for combining the variable reduction strategies and EAs and analyze the impacts of variable reduction strategies on the complexities of optimization problems and the efficiency of EAs. We apply the variable reduction strategies to large-scale non-convex sparse optimization problems and optimization problems in power systems. This project is very meaningful in enhancing the application capabilities of EAs and provides a new paradigm in exploring the integration of EAs and domain knowledge of optimization problems.

针对进化算法易于遭遇“维度诅咒”和难以处理等式约束这两个瓶颈，本项目立足于“进化算法与优化问题领域知识有效融合”的基本思想，利用优化问题的等式最优性条件提取变量关系，提出变量约简策略来缩减解空间、消除等式约束和提高进化算法性能，为突破上述瓶颈提供有效手段。为实现这一目标，需要完成以下三个关键研究内容：首先，凝练出等式最优性条件的一般等式方程组形式，分析等式方程组的可约简性，构建变量约简策略的实现框架。然后，提出等式方程组中变量类型和变量关系检测和提取算法。基于显性变量关系，提出精确型变量约简策略；基于隐性变量关系，提出近似型变量约简策略。最后，设计变量约简策略与进化算法的融合机制，分析变量约简策略对问题复杂度和算法性能的影响，将变量约简策略应用于大规模非凸稀疏优化问题和电力系统优化问题。本项目研究成果对增强进化算法的应用能力具有重要意义，为探索进化算法与一般性问题领域知识融合提供新的范式。

本项目以优化复杂系统调度问题为背景，以变量约减理论为基础，研究融合问题领域知识的优化算法，包括三个方面的研究：融合问题领域知识的集成优化算法、融合问题领域知识的多目标进化算法、融合问题领域知识设计高性能智能优化算法解决复杂系统调度问题。针对这些研究内容，获得主要成果如下：提出了变量约简理论加速优化进程，利用优化问题的等式最优性条件，挖掘变量与变量之间的关系。提出了多种群分解协作的集成优化算法设计框架，在该框架下实现优化算法组件大规模集成与优势互补。提出了基于图结构搜索的优化算法自动配置框架，实现对优化算法的搜索策略与参数值协同自适应调整。提出了多目标优化问题的超平面辅助进化算法，研究了多级进化搜索，提出了一种两阶段进化算法，在不同的搜索阶段突出收敛性和多样性来解决多目标优化问题。针对多目标优化问题的Pareto前沿形状复杂，研究了一种基于压力点的空间压缩策略来优化选择过程。利用问题领域知识，提出了考虑任务聚类的蚁群优化算法来解决多星观测调度问题。设计了结合自适应性、记忆性和全局寻优性的高性能智能优化算法，实现“探索—利用”的自适应平衡。提出了基于有限集中的对地观测平台层次化体系架构和任务规划方法解决空天平台的协同任务规划问题。针对中继卫星系统任务规划问题，提出了一种考虑断点续传的两阶段调度算法，通过实验验证了在天线利用率和任务完成率等方面的增益。通过三年的研究，项目组培养博士生1名，硕士生1名；发表学术论文20篇，以第一作者和通讯作者发表在在IEEE Transaction等高水平期刊上发表文章12篇，有1篇进入ESI前1%高被引论文。项目负责人获得了吴文俊人工智能自然科学二等奖、中国仿真学会优秀科技工作者称号、湖南省自然科学三等奖等多个奖项。