多峰分布估计算法 Multimodal Estimation of Distribution Algorithms

引言

多峰优化，即旨在同时找出多个最优解，在近些年来越来越受到研究人员的重视。在现实生活中诸如蛋白质结构预测、电路设计、数据挖掘等实际应用都需要算法同时找出多个最优解。与普通的最优化问题不同，多峰优化问题中多个最优解的同时定位更具挑战性。

由于多峰优化问题的特殊性，传统的进化算法不能够直接用于解决该问题。原因在于进化算法倾向于将整个种群收敛于一个全局最优解上，因此不能定位到其他符合条件的最优解。为了解决此缺陷，研究人员提出了划分小生境(niching)这一辅助策略来帮助进化算法解决多峰问题。一般来说，划分小生境的做法是将整个种群划分为若干小生境，小生境包含一个小种群，每个小生境的子种群负责找出问题的一个或多个最优解。

近些年来，有学者提出了一种新的进化算法——分布估计算法（Estimation of Distribution Algorithms），该算法很好地维持了种群层面的多样性。一般来说，分布估计算法按照种群中优秀的个体概率分布统计来随机产生后代。然而，目前的分布估计算法多被用来解决最优化问题。到目前为止，文献中仍没有关于运用分布估计算法来处理多峰优化问题的文献出现。

由于分布估计算法能够很好地维持种群的高多样性，因此用其来解决多峰优化问题应是可行的。沿着上述研究方向，我们提出了一个改良的针对多峰优化问题的分布估计算法，称之为多峰分布估计算法（Multimodal Estimation of Distribution Algorithms，MEDA）。本研究提出的多峰分布估计算法有如下4个特征：

MEDA可运用“crowding”或“speciation”两种划分策略来划分小生境，根据选用策略不同可将MEDA细分为MCEDA或MSEDA。与传统EDA不同，MEDAs(MCEDA、MSEDA)在小生境的子种群层面上进行操作。此外，另一个与传统EDA算法的不同点是，每一个小生境的个体都参与了所属小生境的分布估计。
本研究提出了一种动态调整小生境规模的策略。通过结合小生境划分策略，平衡算法的探索能力(exploration)和开发能力(exploitation)，而且还降低了小生境对子种群的个体数的敏感性。
本研究结合高斯分布和柯西分布来产生小生境的后代。与传统EDA单独采用高斯分布产生后代不同，结合两种分布的优点在于此举能够更好地平衡算法的探索能力(exploration)和开发能力(exploitation)。
一个基于高斯分布的局部搜索策略将会被用来增加获得的最优解的质量。值得注意的是，该局部搜索只会有概率地在小生境的最优个体上进行，进行局部搜索的概率取决于这些最优个体的适应度。

本文剩余的章节安排如下，第二部分简要地回顾了多峰优化及分布估计算法，第三部分详细描述了本研究提出的多峰优化算法（MEDA）。在文章的最后，我们对本文进行了总结。

二、多峰优化及分布估计算法

A. 多峰优化算法

一般地，为了有效地处理多峰优化问题，以下两个关键点首先需要被解决：

diversification
intensification

为了解决上述两个关键点，不同的划分小生境策略已经被提出并且也已经结合进化算法来处理多峰问题。目前，“crowding”和“speciation”是最被人广泛使用的两个划分策略。

虽然“crowding”和“speciation”策略具备良好的有效性及较高的划分效率，但是上述两个策略皆存在以下两个不足之处。第一，划分的性能很大程度上取决于其参数的选择。第二，以上策略不适用于复杂大规模的多峰优化问题。上述两个缺陷是“crowding”和“speciation”策略不能广泛应用在实际问题上的主要原因。

为了减少划分策略对参数的敏感度，有学者提出基于拓补结构的划分策略。例如，Ursem 等人提出“hill-valley”方法，即通过测量两个抽样个体之间的适应度的“地形”来划分小生境。假如存在第三个点，其适应度均低于两个抽样点的适应度，则这意味着算法发现了一个“山谷”，因此“山谷”两边的个体应该归到两个不同的小生境中去。虽然上述方法有能力自适应地决定小生境的数量，但是其不足之处在于其需要耗费大量额外的适应度评估次数。为了解决此问题，Li和tang等人提出了“history-based topo-logical speciation method”，其方法在找“山谷”时不需要检测的适应度评估次数。但是，他们的方法不保证找到所有的“山谷”。为了改善划分的效果，Gao等人和Qu等人运用聚类策略来划分小生境。

随后，正如上文所述，许多结合小生境的改进的进化算法被用来解决多峰问题。然而，目前所有针对多峰优化问题的进化算法都是基于DE、GA或者PSO算法，并且这些算法都存在一定缺陷，例如不适用于大规模问题、不能处理具备很多局部最优解的问题等。此外，尽管EDA能够很好地维持种群的高度多样性，但是目前并没有研究人员将EDA用于多峰优化问题。

B．分布估计算法

通过概率分布来产生后代的分布估计算法（EDA）已经在最优化问题上被研究的较为透彻。其伪代码如下所示：

Algorithm 1 EDA
Input: population size NP, the number of selected individuals K
Randomly initialize the population;
While the termination criteria is not satisfied
    Select K best individuals from the population;
    Estimate the probability distribution of the population according to the selected individuals;
    Sample new individuals according to the estimated distribution;
    Combine the sampled individuals and the old population to create a new population with NP individuals;
End While
Output: the best individual and its fitness

分布估计算法在处理连续优化问题和组合优化问题都已经获得了较大的成功，但是这些算法均为针对于最优化问题，目前基本上没有一个分布估计算法能够处理多峰优化问题。抓住分布估计算法能够保持种群的高度多样性这一优点，本研究提出多峰优化算法MEDA来处理多峰优化问题。

三、多峰优化算法

从Algorithm 1我们可以看出，传统的分布估计算法不能处理多峰问题。为了解决此问题，我们将分布估计算法与小生境策略相结合，构成一个全新的多峰优化算法MEDA。特别地，根据采取的划分策略的不同（crowding或者speciation），我们可以得到两个不同版本的MEDA，分别称之为MCEDA和MSEDA。为了平衡算法的探索性和局部开发性，MEDA运用动态的小生境大小来划分小生境。同时，为了更好地维持小生境的多样性，算法将会结合高斯分布及柯西分布来产生小生境的后代。此外，算法采用基于高斯分布的局部搜索策略辅助小生境进化，以提高获得的解的精度。

A．动态小生境大小

一般地，给定种群大小，小生境的个体数越少，整体小生境的数目则越大，这对于全局探索十分有利，但是此举可能会导致每个小生境的多样性较低，导致最终得到的最优解质量不高、容易陷入小生境的局部最优等问题的出现。相反地，假如小生境中个体数越大，小生境的数量越小，尽管小生境的种群多样性增大，但是相应地算法的探测能力也随之降低。因此，为了平衡算法的探索能力和局部开发能力，本研究提出了一种能够动态调节小生境大小的策略。具体来说，当种群获得的有希望存在最优解的区域数目较少时，小生境的尺寸就随之增加以增加其种群多样性，即通过增强小生境的局部开发能力从而得到精度更高的解。相反地，当潜在的存在最优解的区域的数量较多时，小生境的大小将随之减少，以更好地搜索最优区域。由于缺乏对优化问题的先验知识，本研究在该策略上做了一个妥协，即每一次划分时都从候选集合里面随机挑选小生境的大小，这样能够在一定程度上平衡算法的探索能力和局部开发能力。通过上述策略，MEDA打破小生境大小的限制，从而提供更高的多样性，同时平衡算法的探索能力和局部开发能力，也降低了算法对参数设置的敏感性。

B. 分布估计及产生后代

待种群划分为小生境后，MEDA便开始统计每个小生境的个体的概率分布。首先，与传统EDA不同的是，MEDA在小生境的层次上对所有个体进行分布统计，因为小生境的个体数不会很高，因此小生境里的每个个体都是有潜在意义的，因此都应参与其中。

文献中存在许多分布模型，例如单一变量的高斯分布、多变量的高斯分布、直方图模型等等。一般来说，任意统计模型皆可应用于MEDA。本研究为了简明起见，采用了单变量的高斯分布，因为其具有较低的计算复杂度。因此，每个小生境的高斯分布可以独立地按下面的公式进行统计： formular
其中 μi 和 δi 分别是种群里第i个小生境的平均值和方差向量。待分布统计完成后，小生境即可根据分布统计的结构来产生后代。大部分传统的EDA算法都使用高斯分布来采样点以产生后代，然而，由于高斯分布的采样空间通常比较窄，仅采用高斯分布产生后代会降低算法的探索性能。为了克服这一点，本研究将注意力转移到采样空间更广的柯西分布上。结合柯西分布，EDA不容易陷入局部最优。综上所述，我们发现高斯分布更适用于开发阶段，而凭借着较宽的采样空间，柯西分布更加适合于算法的探索阶段。这也促使本研究交替使用这上述两个分布来为小生境产生后代。MEDA的后代产生阶段在小生境的层次上进行，也就是说每个小生境随机选择其中一个分布模型来产生各自的后代。为了简单起见，小生境选择两个分布模型产生后代的概率相同。

当各个小生境都成功产生各自后代之后，接下来要进行的步骤为个体筛选。本研究直接采用CDE的筛选策略，具体做法为：将小生境的每个后代与距其最相近（欧氏距离最短）的父代个体相比较，留下两者中适应度较高的个体。

C．局部搜索

一般来说，分布估计算法（EDA）具备强大的全局探索能力，但是相应地缺乏局部开发能力，故不能很好地改善解的精度。为了解决该缺陷，研究人员通过为EDA引入局部搜索技术以提高其局部开发能力。MEDA采用基于高斯分布的局部搜索技术。采用高斯分布的原因是，高斯分布拥有较窄的采样空间，而当高斯分布的标准偏差σ越小时，其采样空间也就越窄，因此采取一个较小的标准差σ将有利于局部开发。因此，基于高斯分布的局部搜索的标准差的值通常较小。特别地，本研究将σ的值设为1.0E-4。此外，局部搜索将只会在每个小生境最优秀的个体上进行。

一般地，局部搜索可以表现为如下形式： (3)

其中是局部搜索过程中生成的N个新解，N是预先定义好的新解的数量。特别地，本研究将N设为5。S_i代表着第i个小生境的最优秀个体。如上所属，局部搜索的结果取决于各个小生境的最优个体。

总体上看，局部搜索的伪代码总结如下：

Algorithm 2  Local Search
Input: seeds set S, the number of seeds s, fitness of these seeds F, local std value σ, the number of sampled individuals N
F_min= min(F), F_max = max(F), flag = false;
If F_min ≤ 0
  F_max = F_max + |F_min| + ξ;
  flag = true;
End If
//Calculate the probability for each seed to perform local search
For i = 1:s
  If flag
    Pr[i] = (F[i]+ |F_min|+ξ)/ F_max;
  else
   Pr[i] = F[i]/ F_max;
 End If
End For
For i = 1:s
  If rand( ) ≤ Pr[i]
    For j = 1:N
      Generate a new individual 〖 LC 〗_jusing Gaussian(S[i], σ);
      If〖 LC 〗_jis better than S[i]
        Replace S[i] with〖 LC 〗_j;
      End If
    End For
  End If
End For
Output: Seeds S and their fitness F

四、结论

针对多峰优化问题，本研究提出多峰分布估计算法MEDA来定位多个全局最优解。该算法有效地将分布估计算法与划分小生境结合，能够获得令人满意的效果。该算法对多峰优化问题的优越性能源于本研究提出的三种技术：

动态小生境大小
轮流使用两个分布模型来产生后代
围绕小生境最优个体的局部搜索策略

具体而言，动态调整小生境的大小能有效地平衡算法的探索能力及开发能力，并且也降低了MEDA对小生境大小的敏感性。此外，与传统分布估计算法（EDA）不同，在统计分布阶段中，MEDA在小生境层面上对个体进行分布估计，并且每个小生境的所有个体都参与了该小生境分布的估计。另外，MEDA随机采用高斯分布和柯西分布来产生小生境后代，由于高斯分布更适用于开发阶段而柯西分布则更擅长于探测，因此此举能很好地平衡算法的探索能力及开发能力。最后，通过基于高斯分布的局部搜索策略，算法能够根据不同小生境的最优个体进行局部搜索以提高最优解的精度。