GAO-web-ch



生成式对抗优化方法(GAO)

  1. 引言
    1. 优化问题

优化问题一直是数学以及计算机科学领域中的重要问题,其可以被粗略定义为在所有的可行解中寻找最优解。

在实践中,根据约束条件、变量类型、优化目标的个数以及是否存在随机因素(?random factor等,优化问题可以被更加系统而详细地分类。

优化问题被广泛应用于多个领域,诸如工程学、经济学、金融学、力学以及深度学习

1.2    连续优化问题

变量连续的优化问题被称作连续优化问题,其一般形式如下:

其中

是最小化的目标函数,为搜索空间,

是不等式约束条件

是等式约束条件

连续优化问题的主要难点在于如何寻找全局最优解,而避免陷入局部最优解。

就连续优化问题而言,根据函数的峰值,其可以分为单模态优化问题以及多模态优化问题。多模态函数存在多个局部最优解。为了在有限步的迭代中找到全局最优解,算法必须在勘探性exploration)开采性exploitation)之间寻求平衡,进而不至于在局部最优上浪费过多时间与资源。

  1. 相关工作
    1. 连续最优算法

连续最优算法可以根据其机制划分为三类:

第一类是基于梯度的方法,这类方法利用目标函数的梯度逐渐逼近最优解。例如梯度下降法、牛顿法、拟牛顿法、共轭梯度法等。

第二类是群体智能方法,该类方法受启发于自然世界中生物群体的行为。例如粒子群优化算法、蚁群算法、人工鱼群算法、烟花算法等。

第三类是演化算法,该类算法受启发于自然演化。例如遗传算法、模拟退火、差分进化、进化策略等。

2.2    生成式对抗网络(GAN)


生成式对抗网络是由Lan Goodfellow于2014年提出的新一代模型。其广泛应用于图像处理、视频处理、自然语言处理以及半监督学习。

实际上,GAN的目的就在于通过对抗习得该数据分布的生成式模型。如上图所示,生成器生成尽可能真实的样本,判别器则尽可能去将真实样本与生成的假样本区分开来。生成器与判别器通常均使用神经网络进行建模。

GAN模型没有损失函数,其优化过程为一个极大极小二人博弈问题


其中D(x)表示x来自真实数据集而非由生成器生成的概率。

在训练期间,其中一个网络(生成器或判别器)是固定的,只有另一个网络(判别器或生成器)的参数是在更新的,这样交替迭代以最小化每个网络的损失。生成模型G隐式地定义了概率分布,我们希望可以收敛于数据的真实分布

GAN在连续域的问题中被广泛应用,相关任务包括图像及视频生成、图像风格转换、高分辨率图像合成、医学影像处理等。本文将不再对这些领域进行深入探究。GAN在离散域上的相关工作的开展相对晚一些,但其中也不发令人印象深刻者,这些工作主要集中于序列生成(例如自然语言生成、音乐序列生成)以及强化学习。

  1. 基于对抗学习的全新优化框架
    1. 模型结构

GAO的总体结构如下图所示:

生成器从添加了现有解(现有解可选)的噪声向量中生成一个生成解,而判别器的目的则在于判断生成解是否优于现有解。目标函数为现有解和生成解添加标签后,开始对判别器进行训练。生成器训练的目标则最大化判别器判断生成解优于现有解的可能。而判别器的训练则是希望能够最小化分类误差。

生成器的结构如下图所示:


生成解的过程可以用如下等式表示:

其中FC表示图中的全连接网络,表示现有解。

判别器的结构如下图所示:

区分一对生成解与现有解的过程可以由下述等式表示:

其中,表示图中的全连接层1,表示图中的全连接层2。

3.2    模型细节

算法的全部流程如下:

-          首先,在搜索空间随机生成μ个解作为初始解。

-          然后开始迭代,在每次迭代中:

-          第一,使用生成器生成新的解:

1)  将一个随机高斯噪声与一个现有解(可选)输入生成器,并输出一个生成解;

2)  每次生成过程会生成个解。

-          第二,使用目标函数给一对生成解和现有解添加标签:

1)      对于一对生成解与现有解,标签y的计算如下:

-          第三,使用有标签的数据对判别器进行训练

1)      对于有标签数据集判别器训练的损失函数为:

-          第四,判别器固定不变,训练生成器

1)  固定判别器的网络参数,并将其与生成器相连;

2)  使用下述损失函数对生成器进行训练:

-          第五,从现有解与生成解当中选取留存解(?)

1)      为了平衡勘探性开采性,我们计算了每个候选解被保留的概率:

2)      其中表示在所有解中对的适应度的一个从小至大的排序

3)      α是控制这概率分布的超参数,α越大,有更好适应度的解被保留下来的可能性越大;

-          最后,判断是否达到了终止条件,如果未达到终止条件,那么继续迭代。

 

α取不同值时,被保留可能最大的5个候选解的保留概率如下图所示:

α=0时,五个候选解的保留概率是相等的。当α逐渐增大时,适应度更小的解保留概率显著增高。

  1. 基于引导向量的候选解生成方法
    1. 模型结构

目标函数的分布通常是非常复杂的,因而直接通过噪声和现有解生成完备解是十分困难的,这也继而会导致生成解质量不一、训练不稳定以及模型坍塌问题。

为了解决这个问题,我们引入了GFWA中的引导向量这一概念。生成器用于为现有解生成一个拥有良好方向与长度的引导向量,并基于此构造一个新的生成解。

由于生成器是为一个固定的现有解生成引导向量,因此输入必须包含一个现有解。

为了更好的控制生成的引导向量的长度,我们引入了随着迭代变化的步长。生成器首先生成一个方向向量,随后将其与现在的步长相乘,得到引导向量。

在搜索过程中,为了保持勘探性开采性的平衡,采用如下两点:

1)  在一开始,尽可能去勘探足够多的搜索空间是十分必要的,通过这种方式避免错过可能存在全局最优解的局部最优区域;

2)  在搜索的进程中,算法累积了一定的搜索空间的信息。此时,应当在现有局部最优区域进行更深的开采以实现更加精细的搜索。

4.2    模型细节

为了获得完备解,步长需要在算法执行的过程中逐步减小。

如上图所示,将对步长的控制加入到算法当中。当新模型使用生成器生成一个新的解时,需要同时将现在的步长也输入生成器,该过程可以表示为下式:

生成解即可获取自

为了逐步减小步长,我们将步长通过一个单调函数由迭代数字映射至区间。其中代表初始步长,在我们的模型中代表一个值为1e-12的小正实数。

上图展示了使用不同函数时步长的减小情况:

· 使用指数函数时步长减小得最快。

· 随着幂函数的幂次越小,步长减小得越快。

 

  1. 实验与分析

5.1 实验函数集

我们在实验中采用了CEC2013与CEC2017基准组,并在CEC2013上执行对比实验。(维数30)

CEC2013基准组包含5个单模态函数、15个多模态函数以及8个复合函数(?)。搜索空间为,其中D代表实验的维数。

CEC2017基准组白喊3个单模态函数、7个初等多模态函数(?)、10个hybrid function以及10个复合函数。搜索空间与CEC2013相同。
 CEC2013和CEC2017明确了统一的实验设置,因此不同的算法能够在同样的条件下进行比较,设置如下:

-          实验维数:10、30、50;

-          验证:51次,且不能选择最好的51次;

-          最大评估次数(MaxFES):10000*D,其中D是实验维数

-          搜索空间:

-          初始化:使用标准随机分布随搜索空间进行初始化

-          终止条件:当总的评估次数达到MaxFES或误差小于

 

5.2 实验方法以及参数设置

生成器与判别器的网络设置:

为了防止模型在训练期间产生过拟合的问题,我们采用了两种正则化方法:

- 在隐层中使用Batch Normalization;

- 在输出层上使用dropout(drop_rate=0.5)

参数设置如下:

-          现有解的数量:为算法在每一次生成中保留的解的个数,主要用于控制勘探性开采性间的平衡,我们在模型中设=5;

-          生成器生成的解的数量:为算法在每一次生成中生成的解的数量。由于训练判别器需要通过目标函数计算解的适应度,it will consume MaxFES,因此迭代的总次数应当少于。我们在模型中设β=30

-          用于控制保留的概率分布的超参数:当越大,拥有更好适应度的解被保留的概率越大,相反的,保留更好的解与更坏的解(?)的概率也就越小。我们在模型中设

-          步长的设置:当步长比较大时,算法更倾向于勘探,反之亦然。总的来说,初始时算法应当做更多的勘探,这就需要较大的步长。在随后的迭代过程中,在局部的搜索上应当更加精细,需要跟小的步长。

上图比较了使用不同幂次(2,3,4,5,6,7)的幂函数与指数函数对步长进行投影后的平均排序,可知:

·幂函数优于指数函数,这是因为指数函数会使得步长减小过快,算法过快地陷入局部最优;

·总的来说,幂次选为4或5时幂函数有着最好的表现。

上图比较了幂次介于4和5之间的幂函数的平均排序,可知:

·单模态函数与多模态函数的最佳幂次是不同的;

·当幂次取4.5时,总的表现是最好的。因此,我们使用幂函数对步长进行映射,并将幂次设为4.5.

5.3 实验结果及分析

我们在CEC2013基准组上对GAO与其他优化算法进行了比较。(维数30)

其他用于比较的优化算法包括人工蜂群算法(ABC)、标准粒子群优化算法2011(SPSO2011)、the restart CMA-ES with increasing population size (IPOP-CMA-ES)(?)、差分进化算法以及LoT-FWA(?)。

用于比较的算法的超参数均按其原论文所推荐的进行了设置,且GAO与其他算法的实验环境保证完全一致,从而保证了比较的公平性。

在CEC2013上对每个算法进行了51轮优化,其结果的平均误差与标准偏差如下页的表格所示。

此外,表格给出了所有算法的平均排名,包括单模态函数的平均排名、多模态复合函数的平均排名以及所有函数的平均排名。

GAO在所有函数上取得了2.64的平均排名,位列第二,稍逊于IPOP=CMAES(2.54),略高于LoT-FWA(2.82)。在单模态函数上,GAO取得了3.4的平均排名,低于IPOP-CMAES 的1.0以及DE3.2,与SPSO2011相同,高于LoT-FWA3.8。 在多模态复合函数上,GAO 取得了最靠前的排名(2.48),低于LoT-FWA的2.61 IPOP-CMAES的2.87, 并远超其他算法。

GAO在6个函数上获得了最优的平均误差,其中5个是多模态复合函数。GAO并没有在任何一个函数上取得最坏的优化平均误差,这表明GAO有着非常稳定的表现,并且能够处理任何形式的函数。

我们比较了GAO与ABC、IPOP-CMAES以及LoTFWA在每个函数上的表现,并统计了在全部28个函数上GAO表现优于及劣于其他算法的次数。

可以看到在全部28个函数中,GAO相较ABC在16个函数上表现较优,在10个函数上表现较差;相较IPOP-CMAES有9个函数表现较优,17个函数表现较差;相较LoT-FWA有15个函数表现较优,9个表现较差。这表明GAO整体上而言有着较优的优化表现。与IPOP-CMAES相比,GAO在独立函数(?)上的搜索能力有所欠缺,但在其他函数上的表现则更加稳定。

 

  1.     总结与展望
    1. 总结

该模型的主要贡献包括:

·首次提出了基于对抗学习的优化框架。

·提出了基于引导向量的生成候选解的方法,从而提升了模型的生成质量。

6.2  展望

今后的工作可在如下几部分进行:

  1. 我们在模型中采用了较为简单的网络结构,主要是全连接网络以及一些正则化方法。随着近些年GAN的高速发展,许多新的网络结构被提出。在将来,更复杂的网络结构会被采用以进一步提升算法的搜索能力。
  2. 我们在实验中采用了集中较为简单的机制去减小步长。在未来,可以探索更加复杂的减小步长的机制,例如在不同的搜索区域采用不同的机制,从而提升生成解的多样性。
  3. 在CEC2013上的实验结果表明GAO在单模态函数上的表现需要提高,这一点受限于GAO更多的关注生成的多样性。未来可以引入能够提高局部搜索能力的机制,来增强算法在单模态函数上的表现。
  1.     出版物及专利申请

          Publications

        Ying Tan and Bo Shi, " Generative Adversarial Optimization (GAO) ". 2019 International Conference on Swarm Intelligence (ICSI’2019), Springer-Nature, accepted. 

          Patent applications

        Tan Ying, Shi Bo. An Optimization Model Method and Application Based on Generating Adversarial Network: China, 201910250457.0[P]. 2019-03-29.