文摘

人口结构在进化算法(EAs)是一个重要的研究跟踪一个人只有与周边的人在繁殖的一步。这背后的主要理由是提供一个高水平的多样性克服遗传漂变。细胞自动机的概念已被嵌入的过程EA为了提供一个分散的方法为了保持人口结构。和谐搜索(HS)是最近的EA,认为整个个人在繁殖的一步。摘要细胞自动机概念嵌入HS算法提出一种叫做细胞和谐搜索(cHS)的新版本。cHS的人口安排作为一个二维曲面网格,在网格中的每个细胞,只有与它的邻居。内存的考虑和人口更新修改根据细胞EA理论。使用基准函数实验结果表明,嵌入细胞自动机的概念与海关流程直接影响性能。最后,cHS变异分析的参数敏感性分析和比较评价显示cHS的成功。

1。介绍

优化技术导航搜索空间的实用程序使用有效的运营商的控制参数。棘手的任何优化方法的成功是能够达成一个合适的平衡勘探(多元化)和开发(强化)问题的搜索空间(1]。探索是导航的优化方法功能搜索空间的一个有前途的地区,如果有必要,而开发指的是微调的能力进行导航区域收敛到局部最适条件(1]。

和谐的搜索算法(HS)是最近提出的进化算法(EA) Geem et al。2)模仿音乐即兴创作的过程。由于其优于其他优化方法,它规定较少的数学要求在初始搜索(3]。它有一个新颖的随机微分降低收敛所需的迭代次数对局部最小值(4),除了简单,适应性强,一般和可伸缩5]。因此,HS算法已深入定制数优化问题,如制定时间表(6,7恢复[],护士8,空间分配9),和许多其他人10- - - - - -13]。然而,由于一些优化问题的复杂性和避免过早收敛情况,修改商品理论(14]。此外,控制参数适应海关也是研究[5,15- - - - - -17]。

在程序上的上下文中,海关,这是一个迭代的改进算法,提升者人口和谐个体随机存储在内存(HM)。在每个迭代中,生成一个新的个人基于三个运营商:(i)内存考虑,选择变量的新个体从整个HM个人;(2)调整,负责当地的改进,和(3)随机考虑,用于提供随机元素为新个体。新的个人然后评估并取代了最严重的个人嗯,如果它是更好。这个过程是循环,直到满足所需的条件(见表3)。

随着其他东亚峰会,HS算法与个人在HM每个繁殖步骤。更新过程选择最差的个体从一个HM和替换一个新的,如果更好。分散的方法用于其他结构化东亚峰会表明,EA的性能得到了改进。例子包括细胞遗传算法(cGA) [18)、分布式EA (dEA) (19),细胞PSO (20.),和其他(21]。这些结构化方法的主要思想是将人口划分成几个与共同的特征集22]。

尤其是细胞遗传算法(cGA),是一种分散的方法,在人口表示成一个环形网格的二维,如图3(23,24]。个人都位于这在一个预定义的环形拓扑和只与最近的邻居在繁殖[步22]。请注意,所有的社区有相同的大小,相同的形状。这个概念嵌入注册会计师提供有用的优势优化域(23[]和并行实现25,26),因为它有助于提供一个高级的多样性和收益率一小扩散通过搜索解决方案。的注册会计师提供了一个适当的开发力量在每个社区的个体经营者的GA (22]。理论上,它已经表明,非随机交配继续以更高水平的遗传多样性,从而防止算法过早收敛到本地最适条件(27]。

本文的主要目的是将元胞自动机的概念嵌入HS算法优化框架,HM的安排作为一个二维曲面网格。人口扩散将如所预期地保存、维护一个高级的多样性搜索,从而避免遗传漂变。HS算法调整的即兴创作过程与特定个人的社区互动。HM的更新过程是社区内的个人来完成的。结果表明,新的分散版本的商品(即。,cHS) algorithm improves the performance of HS using standard benchmark functions.

剩下的纸是组织如下。介绍了HS算法的基础部分2。提出细胞和谐搜索(cHS)节中讨论3。节中给出了实验的结果4。最后,得出结论,并承诺未来的研究方向提供了部分5。

2。和声搜索算法

和谐的搜索算法(HS)是最近进化方法提出Geem et al。2]。它开始与一组个人存储在一个增广矩阵称为和谐记忆(HM)。这是一个集中式算法,在每个繁殖一步,它生成一个新的个体与整个个人在HM交互。HS遵循三条规则在繁殖步骤生成一个新的个人:记忆的考虑,随机的考虑,调整音高。如果新的个体比最差的个体在整个嗯,更换过程触发。这个过程重复多次HS是停滞不前。的台阶HS算法流程图如图1,每一步详细描述如下。

步骤1(初始化参数)。优化问题是最初表示为,在那里目标函数和吗是决策变量的集合。为每个决策变量,可能值的范围在哪里,和是决策变量的上下界限分别为,是决策变量的数量。HS算法的参数也在预定义的以下步骤。(一)和谐内存考虑率(HMCR),用于育种一步确定决策变量的值是否被选中的个体和谐存储在内存(HM)。(b)和谐内存大小(HMS)决定了HM的个体数量。(c)音高调整率(PAR),这是用于决定的调整决策变量选择从内存。(d)带宽(BW)的距离决定的距离调整个人在场上发生的调整操作。(e)即兴的数量(倪),类似于后代的数量。

步骤2(初始化和谐内存(HM))。和谐的内存(HM)是一个矩阵的大小其中包括套个人由HMS(见(1))。在这一步中,这些个体随机生成如下:,尽管和所有,生成一个随机数在0和1之间。考虑

第三步(即兴创作一个新的个人)。HS算法生成一个新个体,,使用三个运营商:记忆的考虑,随机的考虑,音量调整。

记忆的考虑。在内存中考虑,第一个决策变量的值在新个体是随机选择从历史价值,个人,存储在整个英国。其他决策变量的值,以类似的方式,按顺序分配HMCR概率,。值得一提的是,这一过程与整个人嗯可能导致过早收敛情况由于遗传漂变。

随机的考虑。决策变量,不分配值根据内存考虑随机分配根据随机考虑其可能的范围的概率(1-HMCR)如下:

距调整。每个决策变量一个新的个体,,赋值的内存考虑与PAR的概率,音高调整如下:

在距调整,如果决定是的,的价值和相邻的修改如下:。

步骤4 (HM)更新。如果新的个体,目标函数值比,最严重的人存储在HM(例如,HM排序),最严重的个人将被新的取代。注意,最严重的个人选择整个HM的分散结构的人口没有观察到。

第五步(检查终止规则)。HS算法将重复步骤3和4海关直到满足终止规则,通常是由倪参数的值决定。

3所示。细胞和谐搜索(cHS)算法

有很多的兴趣来自不同领域的研究人员和科学家利用细胞自动机(CA)在物理、生物、社会科学、计算机科学等。CA的最初概念是由纽曼(28),是一种有效的研究工具与多种学科整合。

细胞自动机(CA)的概念通常是关心个人的视角。从CA的主要思想是提供一个特定的人口结构制定作为一个环形网格。细胞在环形网格是指一个人与他最亲密的邻国个人通信,这样所有的个体都具有完全相同数量的邻居。这让我们一种位置被称为隔离的距离。通常,曼哈顿距离是用来测量任何个人和他的邻居之间的距离。注意,邻近个人有相同的形状和大小相同(22]。

存在两种不同类型的细胞模型基于个体繁殖周期是如何执行的。换句话说,如果整个执行周期个人同时,细胞模型是同步的,下一代的个体同时构建。另一方面,如果个人的人口与一个特定的顺序依次更新政策,异步细胞模型。讨论细胞自动机理论,相关论文中可以看到[22,29日]。

细胞和谐搜索(cHS)算法可以被视为一个新的分散的变化取决于结构化HM的商品。HM的个人被安排在二维曲面网格的形式。这是为了保持一个高水平的多样性在育种步骤,从而增加了收敛到全局最小点的机会。这可以通过避免遗传漂变和提供一个更合适的人口扩散在搜索。

cHS算法的一些步骤的原始版本HS算法提出了部分2已调整。调整流程图,如图2。cHS的繁殖步骤完全与邻近的一个随机选择的个体个人使用“细胞记忆考虑”操作符。HM一步的更新调整来代替最差个体在邻近的个人用一个新的个体,但并不是在整个英国。图3显示了人口在细胞结构(环形网格数量),而激发的概念小细胞自动机附近地区。特别是社区提供了隐式的重叠技术迁移到人口。因此,最好的解决方案是顺利扩散在整个人口,在细胞的多样性和谐搜索是保存在搜索。细胞HS模型包括几个组件。(1)细胞:人群中随机选择的个体(个人HMS的数量)。(2)细胞空间:整个人在HM的集合。(3)社区:一组潜在伴侣的任何个人。(4)附近的形状:细胞的选择社区的方法见图5。(5)离散时间限制:一代又一代的数量HS算法通常是由倪参数。

cHS的详细步骤进行下面的步骤。

步骤1 (cHS进行初始化参数和优化问题)。很明显,成功搜索任何metaheuristic方法是基于技术参数设置。对优化方案的参数有不同的影响。cHS是和谐的参数内存大小(HMS)和谐记忆考虑率(HMCR),距调整率(PAR),即兴创作(倪),社区(NH)的大小取决于细胞结构(见图5),如果,这意味着邻居结构长度和8的邻居。

步骤2(初始化和谐内存(HM))。这一步是一样的步骤2在海关的原始版本。注意个人HM排列的二维曲面网格如图4。

步骤3邻域矩阵(NM)(初始化)。纳米是一个二进制矩阵的大小(见(4))。二进制值分配给每个元素基于NH参数。这个矩阵是使用在育种一步确定邻近个体随机选择的个体。的纳米矩阵是由二进制值(5)。考虑

的个人是一组所有邻近个体安排在二维环形网。这组是基于确定的附近的形状见图5。

图4显示了HM个体映射到环形网格。注意,该元素反映出个人的指数1嗯,虽然反映了个体指数在HM HMS。HMS值的平方值K(例如,)。

映射元素在环形网格Y和个体指数在英国,将使用以下:

映射的索引HM的元素(在矩阵纳米),将使用如下:

HM的个体指数之间的映射机制和元素Y是非常有用的,以确定任何个人在HM的邻国。如图5,有几个街区形状来确定任何个人的邻居。例如,L5街区形状需要最近的邻居的一个给定的细胞轴向方向。因此,确定各个指标在HM属于个人的邻居指数使用L5,和计算使用(7)和(8)。和邻居的个体的集合被称为,然后(8)用于地图的元素Y在HM对应的单个索引。使用相同的步骤如果不同街区形状(即。,L9, C9,…) are used to determine the neighboring individuals of。

可以指出,个体的集合将分配1纳米对个人而另一些人将被分配0。

步骤4(从HM选择随机个体)。一个随机选择的个体,,做是为了确定邻近个体从矩阵纳米(例如,),邻近个体的数量;也就是说,。邻近个体交互在一起,以便在下一步中生成新个体。

第五步(生成一个新的个人)。在这一步中,一个新的个体,,生成基于三个运营商:细胞记忆的考虑,距调整,随机的考虑。整个过程在图绘制6。

音高调整和随机考虑运营商cHS算法是相同的原始版本HS算法。然而,考虑修改内存与元胞自动机的概念内联如下。

细胞记忆的考虑。在细胞,细胞记忆只考虑与亲密的人来自的集合。另人不习惯在繁殖的一步。第一个决策变量的值是随机选择从历史价值,、存储个人设置。另一个决策变量,以类似的方式,按顺序分配HMCR概率,。

值得一提的是,手机内存考虑能够控制HM的个体之间的扩散,因此,它能够保存cHS多样性只要迭代搜索过程。通过这一战略,人口结构和可以改进的数值行为cHS算法。

步骤6(更新和谐内存)。这一步是修改cHS算法。最糟糕的个人设置的邻居,也就是说,,取而代之的是新的个体,如果更好。注意,更换过程中考虑到邻近的个人设置只有。

步骤7(检查停止准则)。在这一步中,cHS将停止如果迭代的最大数目(即。、镍)达到;否则算法重复步骤4来6。cHS是在算法的伪代码1。

4所示。实验和比较评价

在本节中,cHS算法评估使用基准函数流传在文献中用于评估HS算法的不同。比较评估的灵敏度分析演示了该方法的控制参数。

4.1。比较评估

在本节中,一组测试函数设计特别会议的实参的优化组织在2005年IEEE国会进化计算(CEC 2005) (30.),使用。2005由25个测试函数包括5单峰CEC和20多峰函数,如表所示1。注意,一个完整的讨论这些功能可以从Sunganthan et al。30.]。CEC 2005提供了一个合适的数量的比较方法,该方法可以评估,略表2。

实验完成后2005年CEC的条件(30.),25日重复运行每个测试函数执行了。25已经总结了运行的平均误差()最好的个人(例如,)。请注意,是已知的最优解而么25分的平均获得的最佳解决方案。维度cHS迭代100000适应度函数的评估。

值得注意的是,大部分的赢家比较方法是混合动力版本的一个特定的EA,结果非常有效的测试功能。出现的AE HS和cHS很近有时比通过比较的方法。特别是,HS算法能够实现非常强大的结果对于大多数测试函数和擅长一些最好的结果报告的比较方法。例如,商品已经实现了最小的为,。

它是指出通过cHS在大多数情况下并不是最好的。这是因为提出的主要观点cHS是确保高层的多样性,因此,所需的cHS更高数量的评估达到更好的结果。然而,cHS的结果非常接近冠军的结果。

4.2。cHS参数的敏感性分析

所有的实验运行使用电脑与英特尔酷睿2四核2.66 4 GB的RAM。使用的操作系统是微软windows Vista Enterprise Service Pack 1。使用MATLAB实现源代码版本7.6.0.324 (R2008a)。

常见的参数设置在所有实验中使用的算法基于经验准则(2]。为了研究不同参数设置的影响,一般来说,参数设置用于评估cHS方法如下:,,,,,。附近的形状使用C9,呈现在图5。

所有的功能都实现在30维(30 d)。可扩展性研究的部分4.2。6,实现的功能是10个维度(10 d), 50维度(50 d), 100维(100 d)。使用的停止准则是即兴创作的最大数量(NI)。

所有的结果在这一节中介绍了表4来8的平均值和标准偏差,展示30独立运行。最好的解决方案已经以粗体突出显示。cHS算法之间的比较分析和HS为了共同的原始变量参数也进行了。

4.2.1。准备基准测试函数

全球最小化基准函数是用来研究的参数的灵敏度分析方法(cHS)的原始版本HS算法。五是由惠特利等功能。42)和其他五个被姚明et al。(43]。这些函数提供一个单峰和多峰函数之间的平衡。这些函数通常用来评估和声搜索算法的最先进的变化(5,44,45]。

大多数基准测试函数的标准解决方案空间范围的目标函数。否则,不对称这些函数用于初始化范围的全球最佳状态在解空间的中心。这些基准函数如下。

球函数,定义为 全球最佳和(搜索范围)(图7(一))。

Schwefel的2.22问题,定义为 全球最佳和(搜索范围)(图7 (b))。

一步函数,定义为 全球最佳和(搜索范围)(图7 (c))。

。函数,定义为 全球最佳和(搜索范围)(图7 (d))。

旋转hyper-ellipsoid函数,定义为 全球最佳和(搜索范围)(图7 (e))。

广义Schwefel的2.26问题,定义为 全球最佳和(搜索范围)(图7 (f))。

Rastrigin函数,定义为 全球最佳和(搜索范围)(图7 (g))。

《护理的函数,定义为 全球最佳和(搜索范围)(图7 (h))。

Griewank函数,定义为 全球最佳和(搜索范围)(图7(我))。

Six-Hump Camel-Back函数,定义为 全球最佳,和(搜索范围)(图7 (j))。

图7描述了相应的每个函数的搜索空间景观46]。

4.2.2。HMCR的影响

表4总结了cHS的HMCR对性能的影响和HS的原始版本使用四个HMCR值(即。,0.7,0.9,0.94,0.98)。最好的解决方案获得在每个相应的值以粗体突出显示。图8是一盒须图可视化效果的各种价值观的HMCR cHS的行为使用十全局最小化函数算法。

结果表明,增加HMCR价值提高了性能cHS的所有功能,除了six-hump相反的功能是正确的。使用一个较小的值,HMCR增加了多样性,从而阻止cHS融合(即。,它在随机搜索结果)。因此,它通常是最好使用一个较大的值HMCR(即。,≤0.98)。

HMCR的高价值意味着使用和谐内存导致的高概率减少搜索空间的探索。使用概率HMCR接近1(高值)可能导致算法陷入局部最小值。用更少的概率HMCR允许更多随机生成的解决方案。因此,增加多样性的方式阻止了收敛。研究结果表明,cHS和HS相同的灵敏度的不同价值观HMCR所有功能,并在0.98概率使用HMCR他们得到最好的结果对于大多数优化功能。此外,cHS产生的结果比那些由海关在几乎所有测试功能。

4.2.3。HMS的影响

表5总结了cHS的HMS对性能的影响和基本商品使用HMS的四值(即。16日,25日,36,100)。最好的解决方案获得在每个相应的值以粗体突出显示。图9是一盒须图可视化效果的各种价值观的HMS cHS的行为使用十全局最小化函数算法。

这是表明cHS和HMS的基本商品不敏感。(),cHS获得最好的结果当HMS的价值很大(见图9)。显然,不同价值观的HMS cHS性能更好的功能,因为重叠社区提供了一个隐式的cHS的迁移机制。以来最好的解决方案顺利传遍整个人口,保留了cHS结构化种群的多样性超过HS算法的经典版本。

嗯类似于短期记忆是小的一个音乐家。一个合理的解释可能依赖于大量的类似的和声在HM HMS时大,导致多样性和短缺,因此,导致陷入局部最小值。因此,cHS可能能够维持细胞结构的多样性比商品。

4.2.4。一样的效果

表6总结了cHS的PAR对性能的影响和基本商品使用四个PAR值(0.1,0.3,0.7和0.9)。在每个对应的值是最好的解决方案以粗体突出显示。图10是一盒须图可视化的效果不同的PAR值cHS的行为使用十全局最小化函数算法。

看来,使用相对较小的票面价值(即。≤0.5)提高了车的性能和商品。大多数结果大票面价值可以增加HS算法的收敛速度,而一个小的价值增加多样性HM不相上下。另一方面,小的价值标准允许更多的搜索空间的探索,和PAR的较大的值会导致一个较低的勘探,多样性的减少,那么该算法可能被困在当地的最适条件。可以看出cHS能够得到最好的结果比原来的版本的HS算法对于一些基准函数(例如,,,,),但其他人并不这样想。

4.2.5。NH的邻居数量的影响

表7总结了影响邻居的数量(NH)根据细胞结构cHS的性能。表7也为(展品NH的影响来NH)使用四个值(),其中的价值。在每个对应的值是最好的解决方案以粗体突出显示。最好的结果与原始版本比较cHS HS以粗体突出显示。图11是一盒须图可视化的效果不同NH值cHS的行为使用十全局最小化函数算法。

结果表明,cHS获得最佳结果当邻居的数量很大,除了(),获得最好的结果当邻居的数量很小。一般来说,这通常导致cHS的结论显示更好的性能在大值之间的NH 8和12。图11显示了箱形图的记录结果显示30的分布测试运行对NH的各种价值。

4.2.6。可扩展性的研究

在本节中,cHS和商品生产的结果,当函数集的维数,,,如表所示8都会被记录下来。

一般来说,降低维数在cHS和HS导致更好的结果。这是符合先前的理论。然而,观察结果(表8)提出了cHS算法优于HS当维数大的多数指标优化功能。这表明,增加问题的维数像cHS需要一个更好的算法。

5。结论和未来的工作

本文的新版本HS算法称为细胞和声搜索算法(cHS)。cHS是一种HS算法嵌入和细胞自动机的概念。提出cHS算法的主要思想是提供一个结构化的人口保持高水平的多样性在搜索。cHS, HM个人安排作为一个二维曲面网格,其中每个个体生成,只有与周边的人。HS算法的原始版本的运营商调整观察细胞遗传算法理论,在细胞和细胞搜索空间的概念。

使用十全局优化函数流传的文学,cHS是评估。结果支持细胞自动机理论,在几乎所有情况下,cHS优于HS算法。cHS参数的敏感性分析表明,HMCR cHS敏感值,,和北半球。比较评价也进行了HS算法提出的两个版本(44,45),类似的结果。

这是一个初步调查使用元胞自动机的概念在HS算法优化框架。未来,的确,等几个研究方向,怀孕了(我)分析了cHS算法的选择压力和时间复杂度的概念,(2)研究社区形状对cHS的性能的影响,(3)学习一个新的迁移策略赋予个人和他们的邻居之间的交互。

承认

第一作者是感谢授予博士后研究奖学金的学校计算机科学()。本文支持批准号203 / PTS6728001(格兰特类型:有)。