坚毅不屈的比较研究和PBIL大规模全局优化问题

文摘

分布估计算法(eda)使用全局统计信息有效样本后代无视位置信息到目前为止发现的局部最优解。进化算法与引导突变(各地)结合全局统计信息和位置信息样本的后代,瞄准这个杂交提高了搜索和优化的过程。论述了基于人口的增量学习的比较研究(PBIL), eda的代表,各地大规模的全局优化问题。我们实现了PBIL和各地建立一个实验装置模拟运行。分析了这些算法的性能质量和计算成本的解决方案。我们发现,东亚运动会中表现优于PBIL获得一个高质量的解决方案,但后者表现更好的计算成本。我们也与MA-SW-Chains坚毅不屈的性能和PBIL相比,获胜者CEC的2010年,发现坚毅不屈的总体性能与MA-SW-Chains相提并论。

1。介绍

已研制出许多搜索和优化技术来解决复杂的优化问题,如旅行推销员问题。一个广泛研究的方法在这一领域是分布估计算法(eda) [1- - - - - -3]。的主要区别传统进化算法(4- - - - - -6),例如,遗传算法和eda在于他们的后代一代策略。传统进化算法使用交叉和变异产生新的解决方案,而eda使用概率模型样本的后代。概率模型是基于全局统计信息,提取人口。根据近似最优性原理(7),假设好解决方案也有类似的结构,一个理想的后代发电机应该能够生成一个解决方案,接近到目前为止所发现的最好的解决方案。在这方面,进化算法和eda都有自己的优缺点。进化算法允许新的解决方案不会远离到目前为止所发现的最好的解决方案,而eda没有机制来直接控制一个子女及其父母之间的相似性。另一方面,eda更好地控制解决方案之间的相似性在当前人口,因为他们使用的全局统计信息有效样本的后代。

进化算法与引导突变(各地)8全球统计信息(即)结合。,the EDA approach) and location information (i.e., the traditional evolutionary algorithmic approach) to sample offspring. The authors evaluated the performance of EAG on maximum clique problem and showed promising results. In [9(汗),使用数值优化功能10,11和标准遗传算法测试问题12,13)比较的性能对两个经典的eda坚毅不屈,以人群为基础的增量学习(PBIL) [14)和紧凑的遗传算法(15]。先前的研究表明,东亚运动会比竞争对手做的更好。然而,到目前为止,坚毅不屈的性能是衡量小规模优化问题。因此,我们目前尚不清楚可伸缩的坚毅不屈。

在这项研究中,我们评估彻底坚毅不屈的性能对PBIL大规模全局优化问题的一组基准函数(16]。这两种算法的结果也与MA-SW-Chains [17,CEC 2010年竞争的赢家16]。本文用两种不同的方式。首先,我们的研究结果进一步加强先前的调查结果,结合eda和传统进化算法比独立的eda或进化算法更有效。第二,我们的发现表明,最初为离散优化问题,各地也适合连续优化问题。算法是可伸缩的,其性能与MA-SW-Chains,获胜者CEC的2010。

本文的其余部分组织如下。节2,我们给一个背景概述PBIL,坚毅不屈,其他EDA方法密切相关,和大规模的全局优化问题。实证研究部分中概述3。我们将讨论主要发现和我们的方法的局限性4。本文的结论部分5。

2。背景

2.1。PBIL

PBIL是进化计算的统计方法解表示成固定长度的二进制字符串。一个概率向量用于样品的后代。在这个向量,措施1 s的分布(因此0)th模拟人口的位置在一个给定的搜索空间。最初,这些概率设置为0。5在每一个职位给一个在搜索空间均匀分布。生成解决方案使用;对于每一个解决方案在位置1生成的概率。的概率然后逐渐向1或0作为搜索进展。PBIL算法伪代码中所示1。

除了阻止标准及最佳解决方案的数量()用于更新概率向量,PBIL四个主要敏感参数:学习速率(),突变率()、突变转变(),人口规模()。在这其中,和保存低(例如,0.1和0.02,分别地。)(14]。

2.2。届东亚运动会

东亚运动会(与引导突变进化算法)是一种混合进化算法和eda。变异算子在进化算法直接使用局部最优解的位置信息发现到目前为止,无视有前途的解决方案在搜索空间的分布。产生的后代因此接近他们的父母,但是他们可以远离其他当前人口最好的解决方案。这是因为进化算法不从全局统计信息中受益。另一方面,使用eda全球统计信息有效样本的后代,但他们不顾位置信息到目前为止发现的最优解。在eda这是一个重要的限制,因为没有机制来直接控制新的解决方案之间的相似性和当前“好”的解决方案。各地结合全球统计信息和位置信息的最优解样本后代,针对这个杂交会提高解决方案的质量。开发一个新的变异算子”引导突变”坚毅不屈。坚毅不屈的伪代码类似于PBIL除了解决方案使用guided-mutation运营商产生下一代。guided-mutation操作符是伪代码中所示2。

guided-mutation运营商guided-mutation率敏感。操作员决定的基础上新样品的后代通过复制的位置信息从父母或概率向量;更大的价值,更多的后代的基因(从概率向量)取样。各地学习敏感率(),guided-mutation率(),人口规模()[8]。

2.3。其他相关方法

大量的工作已经发表在eda (1- - - - - -3,14,15,18- - - - - -26]。这里我们回顾一块工作,致力于混合方法在eda (18,21- - - - - -25];eda的详细审查,请参阅[27]。Mahnig Muhlenbein使用混合方法的变异算子引入eda使用贝叶斯之前(18]。他们发现突变的引入eda的依赖大大降低最优人口规模。在另一项研究中,手中变异算子并入到EDA保持EDA人口的多样性(21]。他的结果表明,突变提高了eda的搜索能力,即使有小的人口规模。在[23)、桑塔纳等人结合EDA和可变邻域搜索(VNS)启发式,发现这种混合方法相比表现相当好简单的EDA或简单的迷走神经刺激法方法。这里值得一提的是,问题维度探讨这些研究都相对较小;例如,在[21问题维度都不超过70人。在另一个研究[24),瓦尔迪兹等人开发了一种混合算法与支持向量机相结合的EDA基因选择的关键特性。他们比较他们的方法与其他混合eda和发现它有效。在最近的一项研究[25),作者提出了一种基于高斯概率分布的EDA。他们表明,在更高的维度问题算法提供比竞争对手更好的性能。

2.4。大规模全局优化

在任何进化算法的实证调查,测试问题的选择永远是至关重要的。必须小心尝试和选择问题,将希望证明照明的调查。作为一个经验法则,至少两个因素往往被认为在选择测试问题:(a)比较与先前的发现/结果和(b)的代表性。通常,研究和广泛的问题是合适的,因为他们可以提供有用的手段,与前面的实验结果进行比较。

近年来,进化计算社区出现了大量的研究,以评估的性能进化算法在大规模的全局优化问题,比如具有一百多个决策变量(16,28]。这些测试问题构成重大挑战,不仅因为他们的高维度,也就是说,“维度”的诅咒29日),还因为他们中的大多数不可分的。的函数变量可分离的如果它可以写成一笔众多变量的函数。

在这项研究中,我们比较PBIL和坚毅不屈的性能基准测试函数提供了CEC的2010 (16]。他们的不同特点可分不可分的和单峰多通道功能。此外,所有这些功能都是转移、可伸缩和最小化问题,全球的最小值是已知的,这是0。这些函数提供了表1;,(16]。

3所示。实证研究

我们用实证的方法来比较坚毅不屈的力量和PBIL大规模全局优化问题。三个主要目标是追求在这项研究:(a)实验装置的模拟运行,(b)最优参数设置为坚毅不屈和PBIL(的实验),和(c)统计分析比较与PBIL坚毅不屈的性能选择测试问题(总结性实验)。每个算法的性能进行了分析解决方案的质量和总占用时间。在下面,我们将讨论实验设置中,最佳的参数设置,并分析结果。

3.1。实验装置

实证调查需要一个系统的实验运行。我们在Matlab-R2009a实现系统。这个实现的简要描述概述如下。(我)解决方案被编码为二进制字符串。一个字符串的长度设置为10次测试问题的维数(在这项研究中,总结性的实验中,问题的维数为每个测试函数设置为1000)。(2)保持一致性,向量的概率是0.5 PBIL和坚毅不屈的初始化。(3)初始种群是随机抽样两种算法使用相同的初始概率向量;100年人口规模一直在研究。(iv)因为健康个体表型值的计算,一个函数binry2真正的是实现二进制值(基因型)映射到对应的十进制值(表现型)。(v)在每一代中,最好的和平均健康的人口记录;对于每一个算法时间,时间也记录下来。

两种算法终止时代的最大数量超过预设的限制,这将为造型的实验和10000代一代又一代的总结性的实验。

3.2。造型的实验

在正常运行实验之前,我们进行了一项试点研究,为东亚运动会和PBIL找到最优参数值。由于进化算法中的参数优化系统是一个具有挑战性的任务,为此原则的方法是必需的。在这项研究中,我们感兴趣的坚毅不屈优化三个参数,学习速率(),guided-mutation率(),人口规模(PBIL)和四个参数,学习速率(),突变率(),突变的转变(),人口规模()。我们使用下面的数值优化函数为每个算法寻找最优参数值;,(30.]。(我们这些函数为300位的字符串进行编码,连续10位为每个维度。)(我)球面函数。这是一个光滑,单峰函数。它是分离和相对容易优化。(2)。海涅的功能。这是一个复杂的优化函数,它遵循一个抛物线轨迹。(3)Rastrigin的功能。这个函数有很多局部最小值,但只有一个全局最小值。(iv)Griewank的功能。这是一个多峰函数的指数越来越多的局部最小值作为其尺寸增加。(v)《护理的功能。这是一个多峰函数。它是不可分的,难以优化。

找到最优值选择的敏感参数,以有序的方式改变他们和记录所示的健身价值的算法1。

我们运行了两种算法在每个测试问题反过来最多10000代;10个独立进行稳定运行参数设置。关于东亚运动会,我们观察到一个更小的值(主要是0.1),一个更大的价值(主要是0.9),和一个更大的价值(主要是)提供更好的结果。我们进一步调整参数β;保持和,这是观察到给更好的结果;在这个参数值的组合,东亚运动会能够找到每个测试函数的全局最优值。同样,PBIL,观察到的参数值(,,,在(),一样的报告14),给出更好的结果。因此,在总结性的实验中,我们使用,,作为坚毅不屈的参数值(在本研究中,坚毅不屈,我们使用突变率= 0.02,突变的转变= 0.05,消极的学习速率= 0.075 (8])。也为PBIL,使用以下参数值的组合:,,,。

3.3。总结性的实验

进化算法的性能可以表现在不同的方式。我们感兴趣的两个性能:(a)质量改进和(b)速度提高。然而,我们主要集中在前。这很重要,因为尽管大多数进化算法使用复杂的策略,找到好的解决方案,找到一个可接受的解决方案是“足够好”地没有保证的。所以,如果解决方案质量不是“足够好的”然后二级速度等方面产生的后果很小。我们定义一个算法拍一个算法根据质量标准如果算法达到健身高于算法的融合的解决方案。同样,一个算法拍一个算法如果算法在速度标准达到解决给定的质量/健身在较小的时间比算法。这是有可能的,不过,获得质量可以获得的时间,反之亦然。因此,为了证明一个算法的整体性能是更好的比之一,我们必须显示以下命题是正确的。P1:算法执行比算法在速度和质量。P2:算法性能更好的速度不超过质量。P3:算法性能更好的质量不超过速度。

为了测试这些命题,一系列的实验运行在Matlab-R2009a系统上,索尼Vaio Core i5 - 2430 m,以2.4 GHz的速度和4 GB RAM (DDR3)。我们记录(一)解决方案每一代的健康,(b)最好的健身跑步,年底(c)各点(最好的健身,,,,)在进化过程中,(d)运行的总时间。

3.4。结果与讨论

在本节中,我们目前的仿真结果PBIL和坚毅不屈的每个测试问题。测试性能的明显差异是否显著,我们也报告的小动物——一张长有成对以及。

我们测量的质量解决方案函数误差值定义为,在那里是已知的全球最佳的(31日]。表2显示了两种算法的仿真结果在25个独立运行每一个测试问题,包括整体最佳解决方案(最好),best-of-run解决方案的意思是平均超过25分(平均),标准偏差在best-of-run解决方案(),值的小动物——一张长有以及(价值的措施是否成对差异每个算法在25个独立运行的最佳解决方案是统计学意义;此外,在这项研究中,是我们的标准价值统计学意义)。

很明显从表2两种算法未能发现已知的全球任何函数的最优值。然而,坚毅不屈的表现看起来比PBIL所有功能。有趣的是,在分离功能,即,,,两种算法提供了竞争的性能。在剩下的17功能,坚毅不屈的性能远远优于PBIL。

图1描述了一些选择功能的演进方案。很明显的数据,坚毅不屈的表现比PBIL在搜索过程中。这是观察到,对于功能坚毅不屈的平均解质量在不同的点(,,,,在PBIL)是大大提高了。

我们也比较坚毅不屈的表现和PBIL MA-SW-Chains [17),获胜者CEC的201016]。很明显从表2比东亚运动会和PBIL MA-SW-Chains表现得更好。然而,有趣的是,我们发现,两个可分离函数(和)和七个部分不可分的函数(和),最好的坚毅不屈的结果比最好的意思MA-SW-Chains (cf。表的结果2,结果以粗体显示)。

单向方差分析是用来测试是否明显差异竞争算法中最好的解决方案很重要。结果如表所示3。跨三个算法选择20日结果显著不同的功能:,关键= 2.83,。为了进一步分析坚毅不屈的性能和PBIL,我们报告两两比较使用以及。两两比较显示,东亚运动会表现PBIL函数(17日):。在剩下的三个函数(),不过坚毅不屈和PBIL不显著的区别:。

来测试我们的第二个性能标准(速度增益),我们记录的时间(以毫秒为单位)所采取的每个算法完成搜索过程。正如前面所讨论的,PBIL和坚毅不屈终止固定数量的代后,设置为。再一次,所有的仿真结果都是平均超过25独立运行。结果如表所示4,这表明PBIL聚合比东亚运动会在所有函数要快多了。再一次,一个单向方差分析测试表明,东亚运动会和PBIL之间的速度差异显著:,关键= 2.09,(表5)。进一步两两比较显示,PBIL明显的收敛时间更快比东亚运动会在所有功能。这些结果表明,东亚运动会比PBIL计算更加昂贵。

没有我们的命题(P1, P2, P3)被发现真实,因为东亚运动会表现比PBIL质量的解决方案,但后者优于前者的速度。但如前所述,在这项研究中,解决方案质量是我们的首要目标;因此我们可以得出结论,比PBIL东亚运动会提供了更好的性能。这个努力,我们还探讨了另一个维度的速度增加,第一代的最佳解决方案。有趣的是,这是观察到整体坚毅不屈比PBIL早找到最好的解决方案;这些结果也明显在图1。

4所示。一般讨论

这里的研究显示两个主要结果。首先,东亚运动会表现PBIL在获得一个高质量的解决方案。这表明,在抽样的后代,结合全球的统计信息和位置信息到目前为止发现的解决方案比只使用全局统计信息。我们观察到,在分离功能,两种算法提供竞争力的性能,但在东亚运动会比PBIL不可分的功能。这表明,潜在的假设在eda问题变量是独立的可能防止有效的收敛到全局最优问题变量相互作用强烈。

第二,PBIL被发现比坚毅不屈。这表明,东亚运动会在计算上昂贵。这种高价的原因是guided-mutation运营商在东亚运动会涉及很多计算用于抽样的后代。我们也观察到,坚毅不屈的速度变得与染色体长度的增长进一步放缓。

如果解决方案质量和计算时间,这就提出了一个问题:这两个维度应该如何相互抵消。如果一个算法的输出比另一但被发现的较为缓慢,应该采用两种算法?也许解决方案质量应给予更多的重量比速度。

最后,很高的区别已知的全球最佳解决方案和解决方案发现PBIL和东亚运动会可能会因为我们的次优的编码方案。我们编码解决方案(基因型),位串,但健身这些解决方案是计算从他们的表型值。因此,二进制(基因型)十进制(表现型)转换是必要的,和这种转换可能导致足够的精度损失。也观察到这种转换需要大量时间和作为一个整体降低算法在速度方面的性能。

5。结论

本文描述了一种坚毅不屈的比较研究和PBIL大规模全局优化问题。简而言之,我们发现,结合全球的统计信息和位置信息到目前为止发现的解决方案极大地提高了搜索/优化过程的质量。我们观察到,在分离功能,两种算法提供竞争力的性能,但在东亚运动会比PBIL不可分的功能。这些发现表明,应该使用位置信息,它是不够的使用非常有限数量的依赖关系(即。eda的方法)来解决优化和搜索问题。我们也观察到,东亚运动会取得了更好的解决方案质量更多的计算成本为代价的。我们得出结论,计算开销不应该惩罚坚毅不屈,因为如果没有足够好的质量解决方案(例如,在fault-critical情况下),那么二级速度等方面产生的后果很小。

结果表明,最初开发的离散优化问题,各地也适合连续优化问题。我们发现坚毅不屈的解决方案质量可比MA-SW-Chains,获胜者CEC的2010。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是由阿卜杜勒阿齐兹国王大学(考)资助(批准号611 - 009 d1433)。作者感谢考他们的财政支持。作者还感谢编辑和匿名评论者的宝贵意见。

引用

1. h . Muhlenbein和g . Paaß从重组的基因分布即二进制参数的估计施普林格,页178 - 187年,1996年。
2. Baluja和戴维斯,“快速概率为组合优化建模,”15国家关于人工智能的会议,第476 - 469页,1998年。视图:谷歌学术搜索
3. p的票数和j·a . Lozano分布估计算法:一种新的进化计算的工具,Kluwer学术出版商、波士顿、质量,美国,2001年。
4. Rechenberg,Evolutionsstrategie: Optimierung科技和去Prinzipien der Biologischen进化Frommann-Holzboog斯图加特,德国,1973年。
5. j . h .荷兰,适应在自然和人工系统,密歇根大学出版社,安阿伯市,密歇根州,美国,1975年。视图:MathSciNet
6. j . r . Koza和r波里,遗传规划:在计算机的编程通过自然选择、复杂自适应系统,麻省理工学院出版社,剑桥,质量,美国,1992年。
7. f·格洛弗和m .拉古纳禁忌搜索,Norwell Kluwer学术出版商质量,美国,1998年。
8. 问:张、j .太阳和e .曾荫权“进化算法与引导变异最大的派系问题,“IEEE进化计算,9卷,不。2、192 - 200年,2005页。视图:出版商的网站|谷歌学术搜索
9. i . h .汗”,进化算法的比较研究”,国际人工智能杂志》上,12卷,不。1,1卷,2014页。视图:谷歌学术搜索
10. X.-S。杨:“优化测试问题,”工程优化:与Metaheuristic应用程序的介绍,X.-S。杨,艾德,约翰威利& Sons,纽约,纽约,美国,2010年。视图:谷歌学术搜索
11. p . n . Suganthan n .汉森j。j梁et al .,“问题定义和评估标准cec - 2005特别会议的实参的优化,“技术。代表,南洋理工大学,新加坡,2005。视图:谷歌学术搜索
12. g . t . ReineltTsplib1995年,海德堡大学,http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp。
13. a .肖勒和r·克莱恩”BPP-1装箱资料处理2系统”,2003年,http://www.wiwi.uni-jena.de/entscheidung/binpp/bin2dat.htm。视图:谷歌学术搜索
14. s . Baluja“基于人口的增量学习:集成基于遗传搜索函数优化方法和竞争学习,“技术。众议员cmu - cs - 94 - 163,卡内基梅隆大学,匹兹堡,宾夕法尼亚州,美国,1994年。视图:谷歌学术搜索
15. g . r . Harik f . g . Lobo d·e·戈德堡,“紧凑遗传算法”IEEE会议程序进化计算,第528 - 523页,1998年。视图:谷歌学术搜索
16. k . Tang李x p . n . Suganthan z, t·威尔斯,“水准函数cec - 2010特别会议在大规模全局优化和竞争,“技术。代表,自然启发的计算和应用实验室,中国科技大学,合肥,中国,2010。视图:谷歌学术搜索
17. d·莫利纳m . Lozano, f . Herrera”MA-SW-Chains:基于本地搜索链的迷因算法对大规模连续全局优化”《IEEE世界大会对计算智能(WCCI 10)西班牙巴塞罗那,3160年,p . 3153年,2010年7月。视图:出版商的网站|谷歌学术搜索
18. t . Mahnig和h . Muhlenbein最佳突变率使用贝叶斯先验分布估计算法,”随机算法:基础和应用国际研讨会,2001年柏林,德国,2001年12月13日- 14日诉讼,艾德。k . Steinhofel卷,2264在计算机科学的课堂讲稿页33-48 Springer,柏林,德国,2001年。视图:出版商的网站|谷歌学术搜索
19. j·m·佩纳诉罗伯斯,p的票数,诉赫夫·罗萨莱斯和m . s . Perez”GA-EDA:混合进化算法利用基因和分布估计算法,”《17创新应用人工智能国际会议施普林格,页361 - 371年,2004年。视图:谷歌学术搜索
20. 问:张和h . Muhlenbein”一类分布估计算法的收敛,“IEEE进化计算,8卷,不。2、127 - 136年,2004页。视图:出版商的网站|谷歌学术搜索
21. h .手中,“与突变分布估计算法,”在组合优化进化计算施普林格,页112 - 121年,柏林,德国,2005年。视图:谷歌学术搜索
22. a•奥乔亚和m·索托”链接熵分布估计算法,”对一种新的进化计算j . a . Lozano, p .票数Inza,大肠Bengoetxea, Eds。卷,192研究模糊性和软计算页1-38 Springer,柏林,德国,2006年。视图:出版商的网站|谷歌学术搜索
23. r·桑塔纳、p的票数和j . a . Lozano”的变邻域搜索和分布估计算法相结合的蛋白质侧链的位置问题,“杂志的启发式,14卷,不。5,519 - 547年,2008页。视图:出版商的网站|谷歌学术搜索
24. 美国瓦尔迪兹,A·埃尔南德斯和s . Botello“基于玻耳兹曼分布估计算法,信息科学卷,236年,第137 - 126页,2013年。视图:出版商的网站|谷歌学术搜索|MathSciNet
25. c·h·l . Li Chen刘et al .,”一个健壮的混合方法基于分布估计算法和支持向量机用于狩猎候选致病基因,”科学世界日报ID 393570条,卷。2013年,7页,2013。视图:出版商的网站|谷歌学术搜索
26. 问:徐、c . Zhang和l .张“快速精英主义高斯分布估计算法和PID优化,申请”科学世界日报ID 597278条,卷。2014年,14页,2014。视图:出版商的网站|谷歌学术搜索
27. p c s h . Chen Chang,张问:“自导flowshop调度问题的遗传算法,”《IEEE国会进化计算(CEC ' 09)特隆赫姆,页471 - 478年,挪威,2009年5月。视图:出版商的网站|谷歌学术搜索
28. k . Tang x姚明,p . n . Suganthan et al .,“基准函数cec - 2008特别会议在大规模全局优化和竞争,“技术。代表,自然启发的计算和应用实验室,中国科技大学,北京,中国,2007。视图:谷歌学术搜索
29. r·e·贝尔曼动态规划多佛数学书籍,多佛出版物,普林斯顿,纽约,美国,2003年。
30. p . n . Suganthan n .汉森j。j梁et al .,“问题定义和评估标准cec - 2005特别会议的实参的优化,“技术。代表,南洋理工大学,新加坡,2005。视图:谷歌学术搜索
31. j·布雷斯特,a . Zamuda拳头,和m . s . Maučec,“大规模使用自适应差分进化算法的全局优化,”学报第六届IEEE世界大会对计算智能(WCCI 10)2010年7月、西班牙的巴塞罗那。视图:出版商的网站|谷歌学术搜索

版权

版权©2014 Imtiaz Hussain汗。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。