高维全局优化 |
您所在的位置:网站首页 › 超高维空间 › 高维全局优化 |
一、背景介绍
1.1 问题背景
由于机器学习和深层人工神经网络的兴起,出现了超过十亿个变量的优化问题。数据的普遍性也导致了在很多数据分析和学习问题上出现了大规模优化问题,如:飞机机翼和涡轮叶片的目标形状设计,卫星布局设计,大规模生物系统的评估,地震波形反演,供水系统的参数设定等。 高维优化问题的一个主要难点在于,当决策变量增加时,搜索空间是呈指数增长的,称为“维度灾难”。当前处理高维问题的方法有:降维,局部搜索,代理建模,分治法等。 1.2 算法背景分解策略是一种解决高维问题比较常用的策略,它将高维问题分解为一系列规模较小并且简单的子问题,每个子问题以迭代的方式进行优化。在演化算法中,协同演化利用了高维问题的模块化特性而被广泛应用,但是在协同演化的算法中,一个主要的困难在于如何对问题进行正确的划分。在理想情况下,一个给出的目标函数,划分出的子集相互之间应该交互最小化,在黑盒问题中,交互信息无法使用,所以需要特定的算法来识别决策变量的底层交互结构。 本问题中介绍的算法是对差分分组 (DG) 算法的改进,DG 算法在 2.2 中介绍,DG 算法可以识别连续的目标函数中交互成分,并且在 CEC 2010 大规模优化问题中取得了较好的结果,然而在 CEC 2013 大规模优化问题中表现较差,其缺点如下: 在完全可分的函数中,消耗过多的评估次数,计算成本高; 无法检测具有重叠组件的目标函数,即多个组件共享决策变量; 对于计算舍入误差敏感; 要求用户指定阈值参数 ( 分解策略利用的是函数自身的性质,这需要目标函数的可分性结构为特征,定义如下: 定义1: 成立,其中
加性可分是部分可分的一种特殊形式,其定义如下: 定义2: 其中, DG 算法使用函数本身的性质来检测变量之间的交互,使用的定理如下, 定理1: 令 其中: 表示函数 等式 (1) 可以简写为 DG2 算法包括了三个部分: 1. 生成原始交互结构矩阵 2. 找到最合适的阈值 3. 根据节点连接矩阵 对于一个 而事实上,我们可以大大减少这种评估次数,因为点是可以重用的。首先,我们假定一个三维问题 其中, 上述点的选取可以在上图中直观显示。我们只取了 7 个点便完成了这次操作,而不用取 12 个点。这其中,点 对上述情况可以推广到更一般的情形: 于是,总的冗余评估次数为(证明见原文): 在2.2中,提到的分组精确度依赖于阈值 CEC2013 中的问题相较于 CEC2010 的一个区别在于每个组件的权重值是不一样的, 因此在当阈值 DG2 算法不采用唯一的静态阈值 1. 浮点数表示的误差: 根据 IEEE 754 标准, 实数 其中,边界 2. 浮点数计算的误差: 在 IEEE 标准中, 3. 上界和下界的推导: 在计算舍入误差的最大下界时,假定 在上式中, 误差来源于 在等式 (3) 中,我们假设函数值域是非负的,更一般的情况有: 估算舍入误差的上界时,需要考虑函数计算的误差。而由于函数是黑盒的,我们无法得知误差项 在等式 (5) 中,我们无法知道浮点操作次数 4. 动态阈值的设定 在 3 中计算了阈值的上界和下界,在区间 其中 [1] Omidvar M N, Yang M, Mei Y, et al. DG2: A faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(6): 929-942.
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |