用混沌粒子群算法求解函数优化问题

戴月+张荣军

【摘要】 粒子群在搜索过程中容易陷入局部而无法找到全局最优值，且算法后期的粒子速度下降过快而失去搜索能力等缺陷，为了解决此早熟问题，提出了一种基于混沌思想的新型粒子群算法，并通过控制粒子平均速度保证算法的搜索趋势。

【关键词】 粒子群 最优值 混沌 搜索能力

一、引言

粒子群优化算法（PSO）是基于群体智能原理的优化算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出的一种进化计算技术[1，[2]，源于对鸟群觅食过程中的迁徙和聚集的模拟。虽然PSO算法起步较晚，但其优良的性能受到不少学者的重视。Shi等提出了惯性因子w线性递减的改进算法[3]，使算法在搜索初期具有较大搜索能力，而在后期又能够得到较精确的结果，此改进方案大大提高了基本PSO算法的性能。Van den Bergh通过使粒子群中最佳粒子始终处于运动状态，得到保证收敛到具备最优的改进算法，但其性能不佳[4]。Mendes等研究粒子群的拓扑结构，分析粒子间的信息流，提出了一系列的拓扑结构[5]。Zhang将选择算子引入到PSO中，选择每次迭代后较好的例子并复制到下一代，以保证每次迭代的粒子群都具有较好的性能[6]。PSO算法的优势在于收敛速度快，易实现并且仅有少量参数需要调整，但是，该算法仍然存在着一些需要完善的地方，本文将混沌的思想引入到PSO算法以提高其局搜索能力，并通过控制粒子平均速度保证算法的搜索趋势。

二、基本粒子群算法与混沌思想

2.1 基本粒子群算法原理

与大多数优化方法相同，粒子群也是以迭代的形式进行搜索的。粒子群中的粒子是以搜索到的粒子个体最优值点和种群找到的最优值点位目标进行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新两部分，具体如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp为粒子所经历过的最好位置；Xg为整个粒子群体所经历的最好位置；C2R2（Xg-Xi）是社会项，C1R1（Xp-Xi）是认知项；W是惯性权重，通常W∈[0，1]；不同的C1、C2描述了粒子对可行域的开发程度；R1、R2是均匀分布在（0，1）的随机数。

2.2 混沌思想

尽管改进的粒子群优化算法比标准的粒子群优化算法有了很大的改进，但是由于初始化粒子的随机性，某些粒子的位置及其pbest接近群体的gbest时，这些粒子会因为它以前的速度和惯性因子不为零而远离最佳位置，而导致算法不收敛。这种描述确定系统不确定性的理论有非常良好的非线性性质，如对初始值敏感和对可行域的遍历等。

三、改进的混沌粒子群算法

为了平衡算法的全局搜索能力和局部搜索能力对惯性因子进行的改进，在标准粒子群优化算法中，惯性权重w是用来控制历史速度对当前速度的影响程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w较大，则粒子有能力扩展搜索空间，全局搜索能力强，若w较小，主要是在当前解的附近搜索，局部搜索能力强；当w=0时，粒子没有记忆性，它将飞向个体最优位置和全局最优位置的加权中心，而处于全局最优位置的粒子将保持静止。

Logistic映射的表达式如下式所示：

Xn+1=αXn（1-Xn） 其中：Xn∈（0，1），0<α<4.

3.1 混沌初始化与区间处理

搜索空间指的是粒子能够飞行的区域，一般问题对粒子的状态参数都有约束区间，但标准粒子群算法一般不约束搜索空间，利用算法的收敛特性使得粒子自动回归到最优区间。初始化时一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系数α∈（0，1]为常数，即根据问题可以设置最大速度的大小。粒子初始化时，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i个粒子第d维参数初始化时所选取的均匀分布的伪随机函数。α取值越大，粒子具有的初始速度区间越大，粒子可能具有的初始速度越大，搜索范围越广。

3.2 混沌惯性权重

惯性权重w是影响PSO算法收敛性的重要因素。较大的惯性权重可以提高PSO算法的全局搜索能力，而较小的惯性权重则增加PSO算法的局部搜索能力。

混沌序列采用如下Logistic映射：

■ （5）

由上式生成的混沌序列在[0，1]之间，然而PSO算法的惯性权重一般在[0.1，0.9]之间取值，所以要将该混沌序列空间限定在该范围之内，则混沌惯性权重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0为首代初始速度，max_generation为最大迭代次数，k为当前迭代数。该速度公式为平均速度的下限。

四、小结

该算法首先通过混沌方法初始化粒子的初始位置和速度，增强了粒子的搜索能力。算法还通过混沌序列得到的惯性权重取代传统的线性递减的惯性权重，使粒子速度呈现多样性的特点，从而提高算法的全局搜索能力。

参 考 文 献

[1] Kennedy J，Eberhart RC.Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on Neural Networks，1995：1942-1948

[2] Kennedy J，Eberhart RC.A discrete binary version of the Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on systems，man，and cybernetics.piscataway：IEEE Press，1997：4104-4108

[3] Shi Y，Eberhart RC.A Modified Particle Swarm Optimizer[C]||Proc of the IEEE Int lConf on Evolutionary Computation，1997：303-308

[4] van den Bergh F，An Analysis of Particle Swarm Optimizer[C] Proc of the 1998 Conf of Evolutionary Computation，1998：67-73

[5] Menders R.Population Topologies and Their Influence in Particle Swarm Performance Ph D Disserlation 2004 104-108

[6] Zhang Xiaoji Dai Guangzhong Xu Naiping Study of Diversity of Population in Genetic Algorithm.Control Theory and Application 1998 2（1）：17-23（in Chinese）endprint

【摘要】 粒子群在搜索过程中容易陷入局部而无法找到全局最优值，且算法后期的粒子速度下降过快而失去搜索能力等缺陷，为了解决此早熟问题，提出了一种基于混沌思想的新型粒子群算法，并通过控制粒子平均速度保证算法的搜索趋势。

【关键词】 粒子群 最优值 混沌 搜索能力

一、引言

粒子群优化算法（PSO）是基于群体智能原理的优化算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出的一种进化计算技术[1，[2]，源于对鸟群觅食过程中的迁徙和聚集的模拟。虽然PSO算法起步较晚，但其优良的性能受到不少学者的重视。Shi等提出了惯性因子w线性递减的改进算法[3]，使算法在搜索初期具有较大搜索能力，而在后期又能够得到较精确的结果，此改进方案大大提高了基本PSO算法的性能。Van den Bergh通过使粒子群中最佳粒子始终处于运动状态，得到保证收敛到具备最优的改进算法，但其性能不佳[4]。Mendes等研究粒子群的拓扑结构，分析粒子间的信息流，提出了一系列的拓扑结构[5]。Zhang将选择算子引入到PSO中，选择每次迭代后较好的例子并复制到下一代，以保证每次迭代的粒子群都具有较好的性能[6]。PSO算法的优势在于收敛速度快，易实现并且仅有少量参数需要调整，但是，该算法仍然存在着一些需要完善的地方，本文将混沌的思想引入到PSO算法以提高其局搜索能力，并通过控制粒子平均速度保证算法的搜索趋势。

二、基本粒子群算法与混沌思想

2.1 基本粒子群算法原理

与大多数优化方法相同，粒子群也是以迭代的形式进行搜索的。粒子群中的粒子是以搜索到的粒子个体最优值点和种群找到的最优值点位目标进行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新两部分，具体如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp为粒子所经历过的最好位置；Xg为整个粒子群体所经历的最好位置；C2R2（Xg-Xi）是社会项，C1R1（Xp-Xi）是认知项；W是惯性权重，通常W∈[0，1]；不同的C1、C2描述了粒子对可行域的开发程度；R1、R2是均匀分布在（0，1）的随机数。

2.2 混沌思想

尽管改进的粒子群优化算法比标准的粒子群优化算法有了很大的改进，但是由于初始化粒子的随机性，某些粒子的位置及其pbest接近群体的gbest时，这些粒子会因为它以前的速度和惯性因子不为零而远离最佳位置，而导致算法不收敛。这种描述确定系统不确定性的理论有非常良好的非线性性质，如对初始值敏感和对可行域的遍历等。

三、改进的混沌粒子群算法

为了平衡算法的全局搜索能力和局部搜索能力对惯性因子进行的改进，在标准粒子群优化算法中，惯性权重w是用来控制历史速度对当前速度的影响程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w较大，则粒子有能力扩展搜索空间，全局搜索能力强，若w较小，主要是在当前解的附近搜索，局部搜索能力强；当w=0时，粒子没有记忆性，它将飞向个体最优位置和全局最优位置的加权中心，而处于全局最优位置的粒子将保持静止。

Logistic映射的表达式如下式所示：

Xn+1=αXn（1-Xn） 其中：Xn∈（0，1），0<α<4.

3.1 混沌初始化与区间处理

搜索空间指的是粒子能够飞行的区域，一般问题对粒子的状态参数都有约束区间，但标准粒子群算法一般不约束搜索空间，利用算法的收敛特性使得粒子自动回归到最优区间。初始化时一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系数α∈（0，1]为常数，即根据问题可以设置最大速度的大小。粒子初始化时，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i个粒子第d维参数初始化时所选取的均匀分布的伪随机函数。α取值越大，粒子具有的初始速度区间越大，粒子可能具有的初始速度越大，搜索范围越广。

3.2 混沌惯性权重

惯性权重w是影响PSO算法收敛性的重要因素。较大的惯性权重可以提高PSO算法的全局搜索能力，而较小的惯性权重则增加PSO算法的局部搜索能力。

混沌序列采用如下Logistic映射：

■ （5）

由上式生成的混沌序列在[0，1]之间，然而PSO算法的惯性权重一般在[0.1，0.9]之间取值，所以要将该混沌序列空间限定在该范围之内，则混沌惯性权重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0为首代初始速度，max_generation为最大迭代次数，k为当前迭代数。该速度公式为平均速度的下限。

四、小结

该算法首先通过混沌方法初始化粒子的初始位置和速度，增强了粒子的搜索能力。算法还通过混沌序列得到的惯性权重取代传统的线性递减的惯性权重，使粒子速度呈现多样性的特点，从而提高算法的全局搜索能力。

参 考 文 献

[1] Kennedy J，Eberhart RC.Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on Neural Networks，1995：1942-1948

[2] Kennedy J，Eberhart RC.A discrete binary version of the Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on systems，man，and cybernetics.piscataway：IEEE Press，1997：4104-4108

[3] Shi Y，Eberhart RC.A Modified Particle Swarm Optimizer[C]||Proc of the IEEE Int lConf on Evolutionary Computation，1997：303-308

[4] van den Bergh F，An Analysis of Particle Swarm Optimizer[C] Proc of the 1998 Conf of Evolutionary Computation，1998：67-73

[5] Menders R.Population Topologies and Their Influence in Particle Swarm Performance Ph D Disserlation 2004 104-108

[6] Zhang Xiaoji Dai Guangzhong Xu Naiping Study of Diversity of Population in Genetic Algorithm.Control Theory and Application 1998 2（1）：17-23（in Chinese）endprint

【摘要】 粒子群在搜索过程中容易陷入局部而无法找到全局最优值，且算法后期的粒子速度下降过快而失去搜索能力等缺陷，为了解决此早熟问题，提出了一种基于混沌思想的新型粒子群算法，并通过控制粒子平均速度保证算法的搜索趋势。

【关键词】 粒子群 最优值 混沌 搜索能力

一、引言

粒子群优化算法（PSO）是基于群体智能原理的优化算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出的一种进化计算技术[1，[2]，源于对鸟群觅食过程中的迁徙和聚集的模拟。虽然PSO算法起步较晚，但其优良的性能受到不少学者的重视。Shi等提出了惯性因子w线性递减的改进算法[3]，使算法在搜索初期具有较大搜索能力，而在后期又能够得到较精确的结果，此改进方案大大提高了基本PSO算法的性能。Van den Bergh通过使粒子群中最佳粒子始终处于运动状态，得到保证收敛到具备最优的改进算法，但其性能不佳[4]。Mendes等研究粒子群的拓扑结构，分析粒子间的信息流，提出了一系列的拓扑结构[5]。Zhang将选择算子引入到PSO中，选择每次迭代后较好的例子并复制到下一代，以保证每次迭代的粒子群都具有较好的性能[6]。PSO算法的优势在于收敛速度快，易实现并且仅有少量参数需要调整，但是，该算法仍然存在着一些需要完善的地方，本文将混沌的思想引入到PSO算法以提高其局搜索能力，并通过控制粒子平均速度保证算法的搜索趋势。

二、基本粒子群算法与混沌思想

2.1 基本粒子群算法原理

与大多数优化方法相同，粒子群也是以迭代的形式进行搜索的。粒子群中的粒子是以搜索到的粒子个体最优值点和种群找到的最优值点位目标进行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新两部分，具体如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp为粒子所经历过的最好位置；Xg为整个粒子群体所经历的最好位置；C2R2（Xg-Xi）是社会项，C1R1（Xp-Xi）是认知项；W是惯性权重，通常W∈[0，1]；不同的C1、C2描述了粒子对可行域的开发程度；R1、R2是均匀分布在（0，1）的随机数。

2.2 混沌思想

尽管改进的粒子群优化算法比标准的粒子群优化算法有了很大的改进，但是由于初始化粒子的随机性，某些粒子的位置及其pbest接近群体的gbest时，这些粒子会因为它以前的速度和惯性因子不为零而远离最佳位置，而导致算法不收敛。这种描述确定系统不确定性的理论有非常良好的非线性性质，如对初始值敏感和对可行域的遍历等。

三、改进的混沌粒子群算法

为了平衡算法的全局搜索能力和局部搜索能力对惯性因子进行的改进，在标准粒子群优化算法中，惯性权重w是用来控制历史速度对当前速度的影响程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w较大，则粒子有能力扩展搜索空间，全局搜索能力强，若w较小，主要是在当前解的附近搜索，局部搜索能力强；当w=0时，粒子没有记忆性，它将飞向个体最优位置和全局最优位置的加权中心，而处于全局最优位置的粒子将保持静止。

Logistic映射的表达式如下式所示：

Xn+1=αXn（1-Xn） 其中：Xn∈（0，1），0<α<4.

3.1 混沌初始化与区间处理

搜索空间指的是粒子能够飞行的区域，一般问题对粒子的状态参数都有约束区间，但标准粒子群算法一般不约束搜索空间，利用算法的收敛特性使得粒子自动回归到最优区间。初始化时一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系数α∈（0，1]为常数，即根据问题可以设置最大速度的大小。粒子初始化时，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i个粒子第d维参数初始化时所选取的均匀分布的伪随机函数。α取值越大，粒子具有的初始速度区间越大，粒子可能具有的初始速度越大，搜索范围越广。

3.2 混沌惯性权重

惯性权重w是影响PSO算法收敛性的重要因素。较大的惯性权重可以提高PSO算法的全局搜索能力，而较小的惯性权重则增加PSO算法的局部搜索能力。

混沌序列采用如下Logistic映射：

■ （5）

由上式生成的混沌序列在[0，1]之间，然而PSO算法的惯性权重一般在[0.1，0.9]之间取值，所以要将该混沌序列空间限定在该范围之内，则混沌惯性权重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0为首代初始速度，max_generation为最大迭代次数，k为当前迭代数。该速度公式为平均速度的下限。

四、小结

该算法首先通过混沌方法初始化粒子的初始位置和速度，增强了粒子的搜索能力。算法还通过混沌序列得到的惯性权重取代传统的线性递减的惯性权重，使粒子速度呈现多样性的特点，从而提高算法的全局搜索能力。

参 考 文 献

[1] Kennedy J，Eberhart RC.Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on Neural Networks，1995：1942-1948

[2] Kennedy J，Eberhart RC.A discrete binary version of the Particle Swarm Optimization[C]||Proc of the IEEE IntlConf on systems，man，and cybernetics.piscataway：IEEE Press，1997：4104-4108

[3] Shi Y，Eberhart RC.A Modified Particle Swarm Optimizer[C]||Proc of the IEEE Int lConf on Evolutionary Computation，1997：303-308

[4] van den Bergh F，An Analysis of Particle Swarm Optimizer[C] Proc of the 1998 Conf of Evolutionary Computation，1998：67-73

[5] Menders R.Population Topologies and Their Influence in Particle Swarm Performance Ph D Disserlation 2004 104-108

[6] Zhang Xiaoji Dai Guangzhong Xu Naiping Study of Diversity of Population in Genetic Algorithm.Control Theory and Application 1998 2（1）：17-23（in Chinese）endprint