基于粒子群优化算法求解大尺度问题的动态开发空间缩减
摘要：
当问题的维数大幅度增加至大尺度时，粒子群优化算法可能会失去搜索效率。对于高维搜索空间，算法可能不容易定位在含有良好解的区域。高维搜索空间也降低了开发能力。“无免费午餐”定理意味着，如果一个算法知道问题所在，我们就可以做出更好的算法。算法应该具有学习解决不同问题的能力，换句话说，算法可以自适应地改变以适应问题的发展。本文运用动态开发空间减缩策略，对问题背景进行了研究。同时，采用部分重初始化策略，提高了算法的搜索能力。实验结果表明，采用这两种策略的粒子群优化算法在大规模问题上的性能优于标准粒子群优化算法。讨论和分析了变异粒子群算法的群体多样性，包括位置多样性、速度多样性和认知多样性。从多样性分析可以看出，利用空间缩减策略可以提高算法的开发能力。
1. 介绍
群体智能是一种由自然启发的搜索技术的集合，它以个体为基础。粒子群优化（PSO）是一种群体智能算法，由Eberhart和Kennedy于1995年提出[1]，[2]。这是一种基于群体的随机算法，模拟了成群鸟类的社会行为。每一个代表一个解的粒子，都以一种根据其自身及其同伴的历史行为动态调整的速度在搜索空间中飞行。在搜索过程中，粒子倾向于朝着更好的搜索区域飞去[3]。
一般来说，优化涉及到为给定问题找到“最佳可用”的解决方案，并且问题可能有几个或多个最优解，其中许多是局部最优解。由于多模态问题可能出现过早收敛，进化优化算法通常很难找到全局最优解。
粒子在搜索空间中飞行。如果粒子在短时间内很容易聚集在一起，粒子将失去其“搜索潜力”。对于基于种群的算法来说，围绕局部最优点的种群过早收敛是一个常见的问题。这是个体匆忙聚集在搜索空间的一个小区域的结果。当过早收敛时，算法的搜索能力会降低，粒子探索新搜索区域的可能性很小。通常，由于粒子聚集在一起而失去的多样性不容易恢复。一个算法可能由于过早的收敛而失去搜索效果。当总体收敛时，算法将花费大部分迭代在一个小区域中搜索。
Wolpert和Macready[4]提出的“无免费午餐”（NFL）优化定理证明了在某些假设下，对于所有问题，没有一种算法比其他算法平均更好。这意味着没有先验知识，我们就找不到适合所有问题的算法。然而，NFL定理也意味着，如果一个算法知道问题的信息，我们可以做出更好的算法。算法应该具有学习解决不同问题的能力，换句话说，算法可以自适应地改变以适应问题的发展。
一个好的算法会收敛。群体智能中的收敛概念不是意味着所有个体都聚集在一起，而是在寻找“足够好”的解决方案的过程中，适应值越来越高。也就是说，在客观空间中应该关注收敛性。局部重新初始化的粒子群优化算法是提高粒子多样性的有效方法，可以增加粒子跳出局部最优解的可能性，并且保持算法寻找“足够好”解的能力。
与其他进化算法相比，例如遗传算法，粒子群优化算法具有更多的搜索信息，不仅包括解（位置），还包括速度和以前的最佳解（认知）。利用群体多样性包括位置多样性、速度多样性和认知多样性分别测量这些信息。关于种群多样性的测量这里有几个定义[5]–[7]。
本文的组织结构如下。第二部分介绍了粒子群优化算法的基本原理和种群多样性的定义。在第三节分析了收敛的概念，介绍了保持多样性的两种机制，并描述了动态开发空间缩减。第四节描述了实验设置，其中包括使用的测试函数、优化器配置和结果。第五节分析了原始粒子群优化算法和具有开发空间缩减的粒子群优化算法的种群多样性。最后，第六部分总结了本文的一些看法和今后的研究方向。
2. 前期准备
A. 粒子群优化
原始的粒子群优化算法概念简单，易于实现[8]，[9]。基本方程如下：
其中w表示惯性重量且小于1，c1和c2是两个正加速度常数，rand（）和Rand（）是在[0,1]范围内生成均匀分布随机数的函数，vij和xij表示第i个粒子在第j维的速度和位置，pi是指第i个粒子找到的最佳位置，pn是指它的邻域成员所发现的，到目前为止具有最佳适应值的位置。
粒子群优化算法可以采用不同的拓扑结构，不同的拓扑结构对每个粒子都有不同的搜索信息共享策略。全局星和局部环是两种最常用的结构。具有全局星结构的粒子群算法，其中所有粒子相互连接，在群中的平均距离最小；相反，具有局部环形结构的粒子群算法，其中每个粒子都连接到两个近粒子，在群中的平均距离最大[10]，[11]。
B. 人口多样性
影响优化算法性能的最重要因素是其勘探和开发能力。勘探能力意味着搜索算法能够探索搜索空间的不同区域，以便有很高的概率找到有很好前途的解决方案。另一方面，开发能力意味着能够将搜索集中在一个有希望的区域周围，以便改进候选解决方案。一个好的优化算法应该使两个冲突目标达到最佳平衡。
粒子群优化算法的种群多样性有助于衡量和动态调整算法的勘探开发能力。Shi和Eberhart给出了三个关于种群多样性的定义，即位置多样性、速度多样性和认知多样性[5]、[6]。位置、速度和认知多样性分别用于测量粒子的当前位置、当前速度和最佳p（迄今为止每个粒子的最佳位置）的分布。Cheng和Shi介绍了基于L1规范[7]，[12]的三种多样性度量的修改定义。
从分集测量中可以得到有用的信息。粒子群优化算法群体多样性的详细定义如下[7]，[12]：
1）位置多样性：位置多样性测量粒子当前位置的分布，因此可以反映粒子的动态。位置多样性给出了粒子的当前位置分布信息。基于范数L1的位置多样性定义如下：
其中，表示每个维度上粒子当前位置的平均值。，其根据每个维度的L1范数测量粒子位置的多样性。Dp测量了整个粒子群的种群多样性。
2）速度多样性：速度多样性，代表粒子的“运动势”的多样性，测量粒子的流速分布。换句话说，速度多样性测量粒子的“活动”信息。通过对速度多样性的测量，可以揭示粒子的膨胀或收敛趋势。基于L1范数的速度多样性定义如下：
其中 ，表示每个维度上粒子的平均流速；，Dv测量每个维度上所有粒子的速度差异。Dv代表整个种群的速度多样性。
3）认知多样性：代表粒子“移动目标”分布的认知多样性，测量所有粒子历史最佳位置的分布。认知多样性的测量定义与位置多样性的测量定义相同，只是它利用了每个粒子当前的个人最佳位置而不是当前位置。粒子群优化算法认知多样性的定义如下：
其中，表示所有粒子在每个维度上的个人历史最佳位置（p best）的平均值；，它代表了基于L1范数的粒子在各个维度上的认知多样性。Dc衡量整个种群的认知多样性。
在不丧失一般性的前提下，本文对每一个维度都进行了同等的考虑。设置所有权重w j=1/n，则整个群的位置多样性、速度多样性和认知多样性可改写为：
3. 多样性维持
A. 收敛性分析
目标函数是从解空间到目标空间的映射。优化（或搜索）过程是在目标空间中找到最优目标函数值，或在解空间中找到与最优目标函数值相对应的最佳位置。收敛性是衡量算法性能的一个指标，在数学上有着明确的定义，但在优化中仍存在一些误区。收敛并不意味着所有粒子都聚集在一个小的区域内，但全局最优或具有最佳适配值的粒子接近“足够好”的解。
数学中收敛的定义是：Rn中的序列是一个点isin;对于每个整数kisin;，在Rn中，点的序列称为收敛到极限x（写为→x），如果和x之间的距离d（，x）趋向于零，因为k变为无穷大，也就是说，如果对于所有ϵgt;0，存在整数k（ϵ），这样对于所有kge;k（ϵ），我们有d（，x）lt;ϵ [13]；
然而，进化算法是用于优化和搜索问题的基于人群的算法。同时存在许多解决方案。与数学中的定义不同，算法只有有限的计算资源，这意味着迭代次数k不能无穷大。当算法找到一个“好”的解决方案或达到预先定义的最大迭代次数时，演化停止。
张等人。说明如果算法全局收敛，总体中几乎所有单个点都将移动到全局最优点，因为时间趋于无穷大[14]。陈等人。给出了收敛的定义：如果给定算法的=，其中是第t代生成中个体的平均适配度，是全局最优的适配度，则我们认为该算法收敛到全局最优[15]。
在算法全局收敛后，个体可能聚集在一起，但这些并不相关。个体聚集在一起并不意味着算法收敛，个体可能“坚持”在局部最优。相反，如果最佳适应值越来越好，并且在搜索结束时找到“足够好”的解，则可以说该算法已经收敛。这种融合并不要求所有人都找到“足够好”的解决方案。一个具有最佳适应值的个体足以证明算法已经收敛。
收敛性与个体的分布无关，它与目标空间中的适应值有关。如果最佳适应值越来越好，并且在搜索结束时找到“足够好”的解，我们可以说该算法已经收敛。然后我们可以将快速收敛定义为使用少量迭代来找到“足够好”的解的算法，如果一个算法在独立运行中多次达到“足够好”的解，该算法将具有很高的收敛潜力。
B. 多元化推广
多样性在算法搜索中很重要。由于多样性低，早熟更容易发生。收敛只涉及具有最佳适配值的粒子，其他粒子的搜索信息可能对搜索是多余的。当粒子进入一个很小的区域时，群会失去“搜索潜力”，大多数粒子都变得无用，停止飞行。当时，人口的多样性是一个很小的价值。因此，我们需要向群中注入能量，例如重新初始化一些粒子。
通过重新初始化策略，提高了算法的多样性。该方法的思想是增加粒子“跳出”局部最优的可能性，保持算法寻找“足够好”解的能力。算法1列出了带重新初始化的PSO的伪代码。经过多次迭代，部分粒子在整个搜索空间中重新初始化其位置和速度，增加了粒子“跳出”局部最优的可能性。根据保留某些粒子的方式，这种机制可分为两类[16]。
bull; 随机局部重新初始化，顾名思义，随机局部重新初始化就是随机保留粒子。这种方法可以获得很大的探测能力，因为大部分粒子都是重新初始化的
bull; 精英部分重初始化，相反，精英部分重初始化使粒子具有更好的适应值。算法在粒子重新初始化整个搜索空间的同时，提高了粒子的搜索能力，同时，粒子被具有更好适应值的粒子所吸引。
算法1即使改变了开发空间，也保留了搜索边界以避免过早收敛。
当问题的维数大幅度增加时，算法可能会失去搜索效率。局部重新初始化可以提高算法的搜索能力，因为它可以搜索更多的区域。开发能力在搜索中也很重要，它有助于算法优化解。提出了一种提高开发能力的学习策略。
对于粒子群优化，粒子在搜索空间中飞行。如果许多粒子停留在一个区域，我们可以得出这个区域可能存在好的解。相反，如果粒子很少停留在一个区域，或者很快离开这个区域，我们可以得出结论，这个区域可能不包含好的解。在此假设下，提出了一种动态减少开发空间的策略。
开发空间分为四等分。我们计算每次迭代中出现在不同部分的粒子数。如果粒子在第一部分出现的次数多于最后一部分，那么我们认为最后一部分可能没有很好的解决方案，并放弃最后一部分。如果最后一部分出现的粒子多于第一部分，我们将放弃第一部分。粒子将在新空间中部分重新初始化。新的空间将在下一次迭代中分为四个部分。与整个搜索空间相比，该空间缩小为一个小区域。
|
算法1 |
粒子群优化中的开发空间动态约简 |
|
1： 2： 3： 4： 5： 6： 7： 8： 9： 10： 11： 12： 13： 14： |
为每个维度中的每个粒子随机初始化速度和位置 while没有找到“足够好”的解决方案或没有达到最大迭代次数 do 计算每个粒子的适合度值 比较当前值和历史最佳位置（个人最佳，称为PBEST）之间的适应值。对于每个粒子，如果当前位置的适合度值优于pbest，则将pbest更新为当前位置。 从当前粒子的邻域中选择一个具有最佳适应值的粒子。 for每个粒子 do 分别根据方程（1）和（2）更新粒子的速度和位置。 将开发空间分为四个部分，对每个维度的每个部分出现的粒子数进行计数。 if满足某些条件或在每次特定迭代之后 then 比较每一维度中出现在两个边上的粒子数，移除包含较少粒子的一侧。将剩余空间设置为开发空间。 保留一些粒子的位置和速度，在新的开发空间中随机重新初始化其他粒子。 End if End for End while |
这个策略可以看作是一个学习过程的PSO。引导粒子搜索更具前景的区域，提高了算法的开发能力。本文在每次迭代次数固定的情况下对粒子进行局部重新初始化，并比较了在整个搜索空间和动态缩减空间中粒子重新初始化的结果。
4. 实验研究
A. 基准测试功能及参数设置
英语原文共 8 页
资料编号：[5163]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
