一种基于单纯形局部搜索的群体智能最优化加速方法

摘要

本发明公开了一种基于单纯形局部搜索的群体智能最优化加速方法。本发明解决群体智能优化全局优化能力强但收敛速度慢问题。该方法引入单纯形局部搜索并引入至群体智能优化对候选解的更新策略中，一方面保留了群体智能优化方法的全局收敛性，另一方面则提升了算法的局部搜索能力，对整体优化方法的收敛进行了加速。

说明书

技术领域

本发明涉及群体智能最优化加速方法技术领域，具体涉及一种基于单纯形局部搜索的群体智能最优化加速方法。

背景技术

最优化方法是基于目标函数对候选解集合进行搜索获取最优解的过程，在任务规划、资源分配、路径规划、系统控制等多个领域有着大量的重要应用。实际问题中的优化问题往往是NP难的，因此只能通过不断试错的方法来逼近最优解，而群体智能最优化是其中一种重要的方法。群体智能最优化是受生物启发，通过研究自然界中生物群体觅食、寻路等协作行为进而设计了与其类似的群体仿生优化策略。基于简单的群体信息交互、群体协作规则，群体中的个体能够在获知自身周边信息的同时认知群体中的重要信息，能够相应地根据集体的知识调整自己的行为，从而使得整个群体具备良好的自学习能力和自适应性。较之于传统基于局部搜索的优化方法，群体智能优化最大的优势是通过来自于广泛的个体信息交互实现了全局信息的获知，进而具备良好的全局最优的能力。

通过研究蚁群利用信息素作为信息交互媒介产生间接的社会交互和自组织性，蚁群优化(ACO)算法模拟了蚁群释放、追踪信息素进而使集体实现食物找寻路径最短化的过程。粒子群优化(PSO)是受鸟群和鱼群集体行动的启发，群体中的每个个体被视为一个粒子，其位置代表了一个候选解。在粒子群优化的过程中，每个粒子权衡其个体惯性、个体历史最佳位置、集体最佳位置，进而决定其下一步移动的方向和速度。鸽群优化(PIO)则是受鸽群优越的位置找寻和导航能力的启发，较之于粒子群算法，该方法有着更快的收敛速度和更好的避免局部极值的能力。

然而，较之于传统局部搜索优化，群体智能优化的一大弊端是其相对更慢的收敛速度，这是由于其在优化过程中会考虑大量冗余的、甚至由随机性带来偏差的个体信息。

发明内容

针对现有技术中的上述不足，本发明提供的一种基于单纯形局部搜索的群体智能最优化加速方法解决了现有群体智能优化方法收敛速度相对较慢的问题。

为了达到上述发明目的，本发明采用的技术方案为：一种基于单纯形局部搜索的群体智能最优化加速方法，包括以下步骤：

S1、构建群体初始位置，根据各位置点候选解的目标函数值的大小将群体划分为单纯形局部搜索子群和群体智能优化子群；

S2、对单纯形局部搜索子群进行基于单纯形算法的位置更新获取该子群最优候选解，并对群体智能优化子群执行相应的群体智能优化算法获取该子群最优候选解，选择单纯形局部搜索子群最优候选解和群体智能优化子群最优候选解中更好的作为当前迭代周期中的全局最优位置并更新群体智能优化子群的位置；

S3、重复迭代步骤S1和S2直至优化收敛或达到最多迭代次数。

进一步地：所述步骤S1中群体初始位的构建具体为：设定一个正整数M作为种群数，即对于待求解的优化问题一共有M个初始位置作为候选解。

进一步地：所述步骤S1中目标函数值的计算方法为：根据待求解优化问你的目标函数，计算M个候选解的目标函数值，并对目标函数值优劣进行排序。

进一步地：所述步骤S1中单纯形局部搜索子群和群体智能优化子群的划分方法为：选择排序后最好的D+1个候选解作为单纯形局部搜索子群，记为G

进一步地：所述步骤S2中单纯形算法的具体步骤为：对G

a、计算反射点x

上式中，

其中，D维单纯形的质心

上式中，x

若g

b、若g

上式中，χ为参数，取值为2；

若g

若g

c、若g

上式中，γ为参数，取值为0.5；

若g

若g

若g

d、若g

x

上式中，σ为参数，取值为0.5。

进一步地：所述步骤S2中群体智能优化算法的具体步骤为：

通过对G

进一步地：所述步骤S3的具体方法为：将所有候选解位置更新后的G

本发明的有益效果为：本发明提供一种基于单纯形局部搜索的群体智能最优化加速方法，解决群体智能优化全局优化能力强但收敛速度慢问题。该方法引入单纯形局部搜索并引入至群体智能优化对候选解的更新策略中，一方面保留了群体智能优化方法的全局收敛性，另一方面则提升了算法的局部搜索能力，对整体优化方法的收敛进行了加速。

附图说明

图1为本发明流程图；

图2为本发明实施例中二维Rosenbrock测试函数的曲面图；

图3为本发明实施例中二维peaks测试函数的曲面图。

具体实施方式

下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。

如图1所示，一种基于单纯形局部搜索的群体智能最优化加速方法，包括以下步骤：

S1、构建群体初始位置，设定一个正整数M作为种群数，即对于待求解的优化问题一共有M个初始位置作为候选解。

根据各位置点候选解的目标函数值的大小将群体划分为单纯形局部搜索子群和群体智能优化子群；根据待求解优化问你的目标函数，计算M个候选解的目标函数值，并对目标函数值优劣进行排序。对于最小化问题，候选解目标函数值越小越好；对于最大化问题，则越大越好。选择排序后最好的D+1个候选解作为单纯形局部搜索子群，记为G

S2、对单纯形局部搜索子群进行基于单纯形算法的位置更新获取该子群最优候选解，并对群体智能优化子群执行相应的群体智能优化算法获取该子群最优候选解，选择单纯形局部搜索子群最优候选解和群体智能优化子群最优候选解中更好的作为当前迭代周期中的全局最优位置并更新群体智能优化子群的位置；

单纯形算法的具体步骤为：对G

a、计算反射点x

上式中，

其中，D维单纯形的质心

上式中，x

若g

b、若g

上式中，χ为参数，取值为2；

若g

若g

c、若g

上式中，γ为参数，取值为0.5；

若g

若g

若g

d、若g

x

上式中，σ为参数，取值为0.5。

群体智能优化算法的具体步骤为：

这些方法包括但不限于蚁群、粒子群、鸽群最优化算法，通过对G

S3、重复迭代步骤S1和S2直至优化收敛或达到最多迭代次数。将所有候选解位置更新后的G

为了验证本发明的有效性：将本发明提出的基于单纯形局部搜索的群体智能最优化加速方法应用于标准粒子群优化算法，并在两个二维测试函数上对优化算法的收敛速度、全局优化能力进行比对验证。实现流程如图1所示，具体的实施步骤如下：

群体位置初始化：设定M＝8作为种群数量，即对于待求解的优化问题一共有8个初始位置作为候选解，候选解的位置在[-2,2]×[-2,2]的区域中随机选择。

候选解目标函数值计算及排序：用于测试的目标函数分别为Rosenbrock函数和Peaks函数，定义如下。

Rosenbrock函数：g(x,y)＝(1-x)

Peaks函数：

根据待求解优化问题的目标函数，计算上一步骤生成的8个候选解的目标函数值，并以目标函数值优劣进行排序。对于最小化问题，候选解目标函数值越小越好。

对于D＝2维的优化问题，选择排序后最好的D+1＝3个候选解作为单纯形局部搜索子群，记为G

a.反射。计算反射点x

b.扩展。如果g

c.压缩。如果g

d.收缩。如果g

参数设置为：ρ＝1,χ＝2,γ＝σ＝0.5。

对G

令

v

其中B(k)表示在第k轮迭代中，G

将所有候选解位置更新后的G

为了验证本发明的有效性，在实施实例中，基于Rosenbrock和Peaks两个测试函数，对本发明提出的方法和标准的粒子群优化算法进行了收敛速度和全局收敛能力进行了比对测试。为了降低由初始化候选解位置的随机性带来的影响，对每个测试函数，执行20次优化计算，取最优解误差和迭代次数的平均值作为用于比对的结果。图2是二维Rosenbrock测试函数的曲面图，图3是二维Peaks测试函数的曲面图。

标准粒子群方法和应用了本发明加速后的粒子群方法在二维Rosenbrock测试函数上的测试结果比对如表1所示。

表1二维Rosenbrock测试函数优化结果比对

标准粒子群方法和应用了本发明加速后的粒子群方法在二维Peaks测试函数上的测试结果比对如表2所示。

表2二维Peaks测试函数优化结果比对

从表1、表2显示的结果中可以看到，应用了本发明提出的基于单纯形局部搜索的群体智能最优化加速方法之后，优化算法最终收敛的最优解平均误差略微优于标准方法，但平均迭代次数降低了50％左右，证明了本发明提出的方法在保持全局最优的情况下对群体智能优化算法的进行收敛加速的效果。