论文部分内容阅读
大数据环境的需求下，研究对象一般具有非线性、非凸、高维、超多目标等多种性质或者其中一种。如何对具有高维甚至超高维特征的优化问题进行有效求解，成为目前计算智能领域的一个严峻挑战。受物质在不同相态下丰富运动规律的启发，通过对其运动特性的观察和分析，抽象出自然现象中所蕴含与之相关联的搜索特性及其内在信息处理机制，提出了一种基于物态运动原理的计算模型，在此基础上设计了几种不同类型的优化算法，以解决传统智能算法在求解不同类型高维优化问题中的不足。本论文在系统分析智能算法设计中搜索策略功能互补性等方面的一些关键问题的基础上，构建了适用于高维问题求解的物态计算模型，设计了几类有效求解具有一般高维、变量耦合高维以及具有大规模变量的多目标等特性优化问题的优化算法，旨在有力地推动智能优化算法在大规模优化领域方面的理论研究，进而为新型大规模智能系统的设计提供方法支撑。本论文主要在以下几个方面展开了研究工作：
（1）受物质在不同相态（气、液和固）下丰富运动规律的启发，构建了一种基于物态运动特性的计算模型，并提出了一种新型的自然启发式算法—物态优化算法(Phase Based Optimization,PBO)，用于求解连续大优化问题。首先，通过不断观察、挖掘不同相态下物质的运动规律，提炼出气态、液态和固态物质的运动特性，分析相应的搜索机理，建立物态计算模型；其次，在搜索机理的基础上设计相应的演化操作算子，构建基本的PBO算法；再次，为验证模型和算法的可用性和效率，对CEC2016大优化竞赛中6个大优化问题进行了仿真实验，与其它先进的智能优化算法进行比较分析。实验结果表明，所提出的P BO针对具有高维特性的问题有较好的优化性能，表现出良好的潜力。
（2）为进一步揭示PBO算法求解优化问题的本质，对PBO算法的逐步动态实现过程和三种相态的搜索行为进行分析，并在此基础上，采用随机过程和马尔科夫理论对群体的状态转移过程进行分析，证明其在种群规模无穷大的情况下是以概率1收敛到满意种群，此外对算法进行了时间复杂度的理论分析。最后在经典的23个基准测试函数上与基于生物进化、基于群体智能和基于其它自然现象等三大类启发式算法中的经典算法进行比较，验证了P BO算法的有效性和先进性；并对问题进行维数扩展，实验结果显示P BO算法在解决高维实际优化问题上具有一定优势。
（3）为使PBO算法在求解问题的维度上更具扩展性，以适用于更大规模的优化问题，一种集成完全随机搜索和全局逐维引导搜索的混合策略被提出。该策略在求解高维优化问题时，能较好的平衡种群多样性和搜索收敛速度的关系。为避免混淆，命名改进算法为全局引导的物态优化算法(Global-best guided PBO,GPBO)。7个广泛使用的可扩展基准测试函数（从100、500到1000维）和一个126维的大规模输电定价实际优化问题被用于验证GPBO的性能，并与目前求解大规模优化问题中先进的6个优化算法进行对比。实验结果表明，在基准测试函数和实际优化问题上，GPBO都能够提供较好的求解精度和更快的收敛速度。
（4）为使PBO算法适合于求解更为复杂的变量耦合高维问题，设计了一种全局搜索能力更为有效的混合PBO算法(Hybrid PBO,HPBO)，并结合合作性协同演化(Cooperative Coevolution,CC)在求解大规模问题的分而治之优势，提出了一种融合自适应局部搜索的CC框架(CC with Global and Local Search,CC-GLS)。在全局协同演化阶段，采用HPBO算法作为搜索优化引擎，并引入了一种命名为序列滑动窗口(Sequential Slid ing Window,SSW)的变量分组方法进行种群的协同演化。当全局搜索的性能达到偏差容差而无显著性变化时，能够自适应采用更有效的局部搜索算法搜索更多的大规模优化问题的解空间，进一步提升搜索性能。将全局和局部搜索策略结合到CC框架中，可以有效地提高处理大规模变量耦合和不可分问题的能力。在CEC2010大规模优化基准测试的实验结果表明，该框架比现有的主流CC框架更有效。
（5）为使PBO算法适合于求解具有大规模决策变量的多目标优化问题(MOPs with a large scale decision variables,LS-MOPs)，基于演化算法中组合多个算子将会给算法带来更好综合性能的这一思想，提出了一种基于多搜索策略的分解多目标物态演化算法(Multi-Objective Evolutionary Algorithms based on Decomposition and PBO,MOEA/D-PBO)。多搜索策略采用PBO算法中的气、液和固态搜索算子，MOEA/D-PBO中，根据个体与参照点之间的距离大小把种群划分为三个子种群，在此基础上，根据参考点为中心的个体的位置特征，执行三种不同的搜索策略以产生更好的候选解。在9个两目标（200维）和9个三目标LS-MOPs（300维）上的实验结果表明，MO EA/D-PBO可以提供优于MOEA/D-DE和IM-MOEA等主流MOEAs算法的IGD指标性能。
最后，对全文的研究工作进行了总结，并对下一步研究的方向进行展望。
（1）受物质在不同相态（气、液和固）下丰富运动规律的启发，构建了一种基于物态运动特性的计算模型，并提出了一种新型的自然启发式算法—物态优化算法(Phase Based Optimization,PBO)，用于求解连续大优化问题。首先，通过不断观察、挖掘不同相态下物质的运动规律，提炼出气态、液态和固态物质的运动特性，分析相应的搜索机理，建立物态计算模型；其次，在搜索机理的基础上设计相应的演化操作算子，构建基本的PBO算法；再次，为验证模型和算法的可用性和效率，对CEC2016大优化竞赛中6个大优化问题进行了仿真实验，与其它先进的智能优化算法进行比较分析。实验结果表明，所提出的P BO针对具有高维特性的问题有较好的优化性能，表现出良好的潜力。
（2）为进一步揭示PBO算法求解优化问题的本质，对PBO算法的逐步动态实现过程和三种相态的搜索行为进行分析，并在此基础上，采用随机过程和马尔科夫理论对群体的状态转移过程进行分析，证明其在种群规模无穷大的情况下是以概率1收敛到满意种群，此外对算法进行了时间复杂度的理论分析。最后在经典的23个基准测试函数上与基于生物进化、基于群体智能和基于其它自然现象等三大类启发式算法中的经典算法进行比较，验证了P BO算法的有效性和先进性；并对问题进行维数扩展，实验结果显示P BO算法在解决高维实际优化问题上具有一定优势。
（3）为使PBO算法在求解问题的维度上更具扩展性，以适用于更大规模的优化问题，一种集成完全随机搜索和全局逐维引导搜索的混合策略被提出。该策略在求解高维优化问题时，能较好的平衡种群多样性和搜索收敛速度的关系。为避免混淆，命名改进算法为全局引导的物态优化算法(Global-best guided PBO,GPBO)。7个广泛使用的可扩展基准测试函数（从100、500到1000维）和一个126维的大规模输电定价实际优化问题被用于验证GPBO的性能，并与目前求解大规模优化问题中先进的6个优化算法进行对比。实验结果表明，在基准测试函数和实际优化问题上，GPBO都能够提供较好的求解精度和更快的收敛速度。
（4）为使PBO算法适合于求解更为复杂的变量耦合高维问题，设计了一种全局搜索能力更为有效的混合PBO算法(Hybrid PBO,HPBO)，并结合合作性协同演化(Cooperative Coevolution,CC)在求解大规模问题的分而治之优势，提出了一种融合自适应局部搜索的CC框架(CC with Global and Local Search,CC-GLS)。在全局协同演化阶段，采用HPBO算法作为搜索优化引擎，并引入了一种命名为序列滑动窗口(Sequential Slid ing Window,SSW)的变量分组方法进行种群的协同演化。当全局搜索的性能达到偏差容差而无显著性变化时，能够自适应采用更有效的局部搜索算法搜索更多的大规模优化问题的解空间，进一步提升搜索性能。将全局和局部搜索策略结合到CC框架中，可以有效地提高处理大规模变量耦合和不可分问题的能力。在CEC2010大规模优化基准测试的实验结果表明，该框架比现有的主流CC框架更有效。
（5）为使PBO算法适合于求解具有大规模决策变量的多目标优化问题(MOPs with a large scale decision variables,LS-MOPs)，基于演化算法中组合多个算子将会给算法带来更好综合性能的这一思想，提出了一种基于多搜索策略的分解多目标物态演化算法(Multi-Objective Evolutionary Algorithms based on Decomposition and PBO,MOEA/D-PBO)。多搜索策略采用PBO算法中的气、液和固态搜索算子，MOEA/D-PBO中，根据个体与参照点之间的距离大小把种群划分为三个子种群，在此基础上，根据参考点为中心的个体的位置特征，执行三种不同的搜索策略以产生更好的候选解。在9个两目标（200维）和9个三目标LS-MOPs（300维）上的实验结果表明，MO EA/D-PBO可以提供优于MOEA/D-DE和IM-MOEA等主流MOEAs算法的IGD指标性能。
最后，对全文的研究工作进行了总结，并对下一步研究的方向进行展望。