文摘

本文提出一种混合分散搜索算法(SS)连续全局优化问题,将差分进化(DE)的进化机制的参考集更新过程SS作为新解决方案生成方法。该混合算法称为DE-based SS(仪)算法。自不同的变异算子的德提出了文学和他们显示不同的搜索能力不同的问题,四个传统的变异操作采用混合算法介绍了。的变异算子自适应地选择最适合当前问题,候选人变异算子的自适应机制。此外,增强仪的探测能力,仅采用方法创建一个新的人口和随后构建一套新的引用时介绍的搜索过程陷入局部最优。计算实验表明,该基准问题介绍了竞争或优于文献中一些先进的算法。

1。介绍

近年来,许多研究成果已用于不同的杂交算法由于采用单个算法的最佳特性通常会导致一个新的强大的和有效的混合算法。在设计这样的混合算法,每个人都应该检查和评估不同的算法的特性和搜索机制,以及其潜在的组合。

分散搜索(SS)首先提出了格洛弗(1整数规划)。它是一个基于进化算法相结合的一组解决方案构建新的解决方案。分散的搜索模板(格洛弗2)对于大多数党卫军的实现提供了基础。种群初始化后,学生选择的一个子集从人口作为参考集解决方案,然后作用于参考集生成新的试验解决方案相结合的解决方案在参考集。相比其他进化算法如遗传算法、引用的内存特征集能够准确地把握当前优化状态,减少使用随机搜索的频率,从而大大提高了全局搜索能力。此外,学生的多样性维护机制保证了搜索多样性在进化过程中。由于它的灵活性和有效性,党卫军已广泛应用于解决组合优化问题,如基于排列问题(“政府改造”和Aleao [3]),流水车间调度问题(山田和Nakano [4],Nowicki和Smutnicki [5(Taillard[]),车辆路径问题6]),二次分配问题(Chung et al。7]),车辆路径(Greistorfer [8],罗素和蒋介石[9])。虽然学生在解决组合优化问题,取得了良好的性能很少文献关注党卫军在连续优化问题的应用。Herrera et al。10]研究连续SS与两种组合方法的性能,即BLX -α和平均的组合。Ugray et al。11)提出了全局优化multistart框架通过嵌入SS与非线性规划求解器进行求解。

尽管差分进化(DE)是一个新成员的群进化算法,它已成为一个最强大的随机搜索算法在文献(Das和Suganthan [12])。由于其简单和易于实现,表现在许多简略优化问题(张和桑德森(13),秦et al。14])和工程优化问题(先生和Angira [15张),和巴16])。德的主要优势是,它使学习更好的解决方案的解决方案(例如,DE /最好/ 1变异算子),同时保持搜索多样性(例如,德/兰特/ 1变异算子)。

由于SS和德的力量,一些研究人员开始调查他们的杂交来构造一个新的强大的算法。Davendra和Onwubolu17)和Davendra et al。18)提出了一个混合DE与SS等离散优化问题的二次分配问题(QAP),旅行商问题(TSP),和置换流水车间调度问题(PFSP)。然而,这种混合算法实际上是一个两阶段方法,在第一阶段由德获得一个很好的解决方案,第二阶段是改善这个解决方案由党卫军。史等。19)开发了一种真正的混合SS与德将DE嵌入党卫军生成新的参考集。该混合算法用于解决离散项目调度问题。

在本文中,我们提出一种新的混合算法基于SS和德,叫混合SS与德(仪)。党卫军的主要框架,但是使用DE组合解决方案参考,然后产生新的解决方案。不同于史等。19),我们的混合算法是专为连续的算法。此外,我们的混合仪算法采用多个突变运营商提出了古典DE和利用一种自适应机制来选择最合适的变异算子在进化过程中。这一策略使不同种类的混合仪非常健壮的优化问题。

本文的其余部分组织如下。部分2给出了背景描述SS和德,在部分3的程序和组件混合仪中所描述的细节。计算实验进行的部分4和我们介绍其他先进的进化算法相比,在文学上基准测试问题。最后,本文的结论部分5。

2。背景

2.1。规范分散搜索

党卫军一般包括五个组件的框架(见算法1)。党卫军第一代生成解决方案使用人口的多样化的方法,认为解决方案质量和多样性。然后参考更新方法用于建立和维护参考集通过选择一些解决方案具有良好的质量和其他解决方案具有良好的多样性的人口(注意,参考集的大小是一个预设的固定值)。基于参考集,子集生成方法是用于生产大量的子集的解决方案为基础创建组合解决方案(例如,所有的两种解决方案和三个解决方案选择的参考设置通常作为子集)。对于每个子集,解决方案组合方法用于转换成一个子集的解决方案相结合的解决方案。最后,改进方法应用于进一步提高每个解决方案相结合。如果没有新的解决方案添加到引用集,算法终止;否则,算法的子集生成过程并开始一个新的迭代。

2.2。规范微分进化

DE算法是一种简单、快速、健壮的进化算法。它始于一个人口的解决方案,并在每一代人口更新连续通过三个主要步骤:变异、交叉和选择。在下面,解决方案在一代的人口表示为,。

突变步骤首先随机选择三个解决方案从人口的一代为目标个体然后产生扰动向量根据选定的三个解决方案如下: 在哪里,,,三个不同的数字随机选择来自哪里和是控制参数。

交叉试验步骤生成解决方案基于摄动的向量和目标的解决方案如下: 在哪里,和是一个随机选择的索引确保试验解决方案不复制目标解决方案吗。用户设定的交叉概率。

一旦生成试验方案,选择步骤比较它与目标的解决方案。如果试验解决方案有一个目标函数值等于或低于其目标的解决方案吗在下一代,它取代目标向量;否则,目标解决方案保留其在人口至少一代。即解决方案在选择下一代根据以下规则:

3所示。提出介绍了算法

在本节中,我们首先将混合介绍了算法在算法的总体框架2然后描述了每个组件的细节在下面几节中。在算法2,表示人口的规模。

3.1。初始种群生成方法

获得一个良好的初始种群多样性,我们开发了一个多样化的主要思想方法后20.]。这种方法的详细信息如下,其中维度和的总和吗和是下界和上界的维度。基于这种方法,可以保证初始种群的多元化。

步骤1。每个维度的划分范围 成相等的子范围。

步骤2。从维度来,请执行以下操作步骤。

步骤2.1。集和每个子范围的选择概率是。

步骤2.2。随机选择一个附属的区域,即在这个范围内,然后生成一个随机的值。

步骤2.3。为选定的子范围,设置,其他没有附属的区域设置。

步骤2.4。集。如果,然后去步骤2.1;否则,转到步骤2.2。

3.2。参考更新方法

规范党卫军算法,参考集一般的解决方案包括两个部分:一部分是一组解决方案与优质的目标函数值和另一部分是一组解决方案具有良好的多样性。这是一个很好的选择离散的解决方案;然而,对于连续优化问题这种环境下往往会恶化的搜索效率。如果两个解决方案解决方案空间相互远离,然后产生的后代往往不如它们。在我们的初步实验,结果表明,采用该设置往往导致收敛速度慢,从而使算法无法达成一个很好的解决方案在一个给定的数量评估函数。因此,在我们的混合动力仪中,引用集只有最好的在人口的解决方案。在每一代,参考集更新是最好的在新的人口的解决方案。

3.3。变异操作符用于混合动力仪

正如上面提到的,一些变异算子提出了德采用混合介绍了算法。这些变异算子的定义如下。在这些方程,表示到目前为止所发现的最好的解决方案的算法:(1)德兰特/ 1:;(2)德/最好/ 1:;(3)德/ rand-to-best / 1:;(4)德/最好/ 2:。

3.4。变异算子的自适应选择方法

选择变异算子,提出一种自适应机制通过引入解决生存的概念用于玉(13和萨德14]。萨德的成功和失败的记忆也用于混合动力仪。在我们的介绍,选择变异算子的应用解决方案被视为成功的从这个操作符(只有在新的解决方案了在算法2)优于。一个列表与一个固定的长度(也称为学习时期)建立存储成功的计数器和失败的计数器每个交叉算子。在第一次代,每个变异算子的选择概率等于(变异算子的总和)。这个预热期用于训练算法来分析每一个变异算子的性能和适用性为当前优化问题。在每一代,和为每个交叉算子计算,然后添加到列表的最后。然后从一代的头节点列表将被删除的新记录和可以添加到年底吗。

每个变异算子的选择概率在一代(表示为根据萨德()计算如下14]:

3.5。人口仅

在进化过程中,混合仪算法可能会陷入局部最优区域,进而将杂交仪的性能恶化。进一步提高摆脱局部最优的能力区域,一个仅采用方法。在进化过程中,我们将记录的数量连续几代人最好的解决方案发现到目前为止还没有更新。当这个数字超过了极限,然后我们将重新启动如下。首先,人口的解决方案升序排序的目标函数值。其次,删除下半年的人口的解决方案有更糟糕的目标函数值。第三,随机选择两个解决方案从左边的一半然后执行操作符(20.)来生成两个后代解决方案。我们将重复第三步次生成新的解决方案,然后选择最好的并将它们添加到解决方案。

的过程运营商可以根据Deb和Agrawal[描述如下20.]。对两种解决方案和,墨操作符会导致两个新的解决方案和如下。首先,生成一个随机的统一编号然后生成一个新的随机数β基于和一个分布指数根据 最后每个维度的两个生成新的解决方案使用以下方程:和,。

4所示。计算实验和结果

在本节中,我们首先介绍实验环境的部分4所示。1然后测试部分中存在的问题4所示。2。最后,部分4所示。5致力于开展我们之间的比较研究介绍和其他先进的进化算法。

4.1。实验设置

提出介绍了算法在c++中实现的,和所有的实验是进行个人电脑的英特尔酷睿2双核2.8 GHz CPU和4 GB内存。

参数设置如下根据我们的初步实验。100年人口规模将参考集的大小将35,控制参数是由交叉概率是由,连续几代人的数量将50。

4.2。测试问题

测试提出介绍了算法的性能,从文献10基准选择问题。表中给出了这些问题的定义1,最后一列是最优目标函数值为每个测试问题。在我们的实验中,我们使用。

在实验中,共有50独立运行执行每个测试问题收集每个算法的统计性能。《独立报》以及用于显示统计区别不同的算法并给出每个问题的结果在最后一列的表吗2,3,4。在最后一列表示信号“+”表示,我们介绍了之间的性能差异和最好的表中其他算法重要的置信水平为95%,而信号“−”表示,他们的性能差异不显著。

4.3。效率分析的自适应选择方法

在本节中,我们首先进行了一个实验显示自适应选择方法的效率。我们比较我们提出介绍了算法和四个介绍算法都只采用一个变异算子。这四个算法分别表示,,,根据四个变异算子。

提出介绍了算法的比较结果,另介绍了只有一个变异算子给出了表2,一个更好的结果是粗体所示。第二列创表示使用的代算法的停止准则,和的意思是(性病Dev)代表了每个算法获得的平均值和标准差为每个测试问题。

从表2,可以看出,介绍算法的自适应选择方法可以获得最好的结果,显示几乎所有最好的鲁棒性测试问题。它比其他四个算法更好的9 10测试问题。这一现象背后的原因是,这一策略可以自适应地选择最合适的变异算子对当前问题。此外,采用多个类型的变异算子也有助于改善仪的探测能力,因为这种策略可以帮助提高算法摆脱局部最优区域的能力。

4.4。介绍了混合架构的效率分析

测试的影响,采用德作为新的解决方案的生成方法,在本节中我们实现了另一种党卫军的新解决方案生成的模拟二进制交叉(墨)。也就是说,从10到20线算法2替换为以下步骤:首先,随机选择两个解决方案的参考;其次,应用墨算子的两个解决方案来生成两个新的解决方案;第三,选择最好的一个新的解决方案。这个算法来标示SS-SBX。

党卫军的两种算法的比较结果展示在表3,一个更好的结果是粗体所示。从这个表中,可以看出,虽然SS-SBX获得最好的结果,,,,,其他问题,其性能更加糟糕。介绍了算法获得最好的结果为6的10个问题,及其性能的其他四个问题也很好。因此,可以得出结论,介绍了算法优越SS-SBX,特别是对鲁棒性。

4.5。比较与其他先进的算法

在上面的部分中,我们已经表明,自适应选择机制基于多个变异算子,采用德SS可以帮助改善党卫军的搜索性能和鲁棒性。在本节中,我们进一步比较仪和其他先进的进化算法在文献中。这些算法包括萨德提出(14和归档提出的玉13]。进化算法在参数自适应策略控制或突变策略选择在进化过程中。给出了比较结果表4。

从表4,可以发现,我们介绍了获得更好的结果为7的10问题比较萨德算法(14](性能差异是重要的所有7问题)和4的10个问题相比玉算法(13]。的问题和,我们介绍了算法可以达到最优的解决方案,而其他两个算法萨德和玉表现更糟。此外,它还显示我们介绍了算法更健壮的不同种类的问题。平均来看,可以得出的结论是,我们的介绍了玉算法具有竞争力但的萨德算法优于10基准测试问题。

给一个图形化的例子分析,我们重新实现萨德算法和比较仪之间的进化过程和前六的萨德问题。对比结果如图1,纵坐标是日志₁₀ 在这是最好的解决方案的目标函数值在每个迭代中找到。请注意,当该算法达到最优解,图中的演化过程线将终止,因为每一个问题的最优目标函数值为零。从这个图中,可以看出,我们介绍的收敛速度要快得多,萨德的所有六个测试问题。

5。结论

在本文中,我们开发了一个混合分散搜索算法,通过融合微分进化算法作为新的解决方案生成方法。使该混合算法更健壮的不同类型的优化问题,开发一种自适应选择机制为多个突变策略。人口仅方法还用于帮助该算法从局部最优。基于基准测试问题的计算结果表明,该混合仪算法非常有效,竞争激烈,其性能甚至优于文献中两个最先进的进化算法。

利益冲突

本文作者声明,没有利益冲突。

确认

这项研究部分由中国国家自然科学基金(批准号61403277)和高校人文社会科学研究项目在天津(批准号20132151)。