戴月+張榮軍

【摘要】 粒子群在搜索過程中容易陷入局部而無法找到全局最優(yōu)值，且算法后期的粒子速度下降過快而失去搜索能力等缺陷，為了解決此早熟問題，提出了一種基于混沌思想的新型粒子群算法，并通過控制粒子平均速度保證算法的搜索趨勢。

【關(guān)鍵詞】 粒子群 最優(yōu)值 混沌 搜索能力

一、引言

粒子群優(yōu)化算法（PSO）是基于群體智能原理的優(yōu)化算法，是由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出的一種進化計算技術(shù)[1，[2]，源于對鳥群覓食過程中的遷徙和聚集的模擬。雖然PSO算法起步較晚，但其優(yōu)良的性能受到不少學者的重視。Shi等提出了慣性因子w線性遞減的改進算法[3]，使算法在搜索初期具有較大搜索能力，而在后期又能夠得到較精確的結(jié)果，此改進方案大大提高了基本PSO算法的性能。Van den Bergh通過使粒子群中最佳粒子始終處于運動狀態(tài)，得到保證收斂到具備最優(yōu)的改進算法，但其性能不佳[4]。Mendes等研究粒子群的拓撲結(jié)構(gòu)，分析粒子間的信息流，提出了一系列的拓撲結(jié)構(gòu)[5]。Zhang將選擇算子引入到PSO中，選擇每次迭代后較好的例子并復制到下一代，以保證每次迭代的粒子群都具有較好的性能[6]。PSO算法的優(yōu)勢在于收斂速度快，易實現(xiàn)并且僅有少量參數(shù)需要調(diào)整，但是，該算法仍然存在著一些需要完善的地方，本文將混沌的思想引入到PSO算法以提高其局搜索能力，并通過控制粒子平均速度保證算法的搜索趨勢。

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

2.1 基本粒子群算法原理

與大多數(shù)優(yōu)化方法相同，粒子群也是以迭代的形式進行搜索的。粒子群中的粒子是以搜索到的粒子個體最優(yōu)值點和種群找到的最優(yōu)值點位目標進行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新兩部分，具體如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp為粒子所經(jīng)歷過的最好位置；Xg為整個粒子群體所經(jīng)歷的最好位置；C2R2（Xg-Xi）是社會項，C1R1（Xp-Xi）是認知項；W是慣性權(quán)重，通常W∈[0，1]；不同的C1、C2描述了粒子對可行域的開發(fā)程度；R1、R2是均勻分布在（0，1）的隨機數(shù)。

2.2 混沌思想

盡管改進的粒子群優(yōu)化算法比標準的粒子群優(yōu)化算法有了很大的改進，但是由于初始化粒子的隨機性，某些粒子的位置及其pbest接近群體的gbest時，這些粒子會因為它以前的速度和慣性因子不為零而遠離最佳位置，而導致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

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

為了平衡算法的全局搜索能力和局部搜索能力對慣性因子進行的改進，在標準粒子群優(yōu)化算法中，慣性權(quán)重w是用來控制歷史速度對當前速度的影響程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w較大，則粒子有能力擴展搜索空間，全局搜索能力強，若w較小，主要是在當前解的附近搜索，局部搜索能力強；當w=0時，粒子沒有記憶性，它將飛向個體最優(yōu)位置和全局最優(yōu)位置的加權(quán)中心，而處于全局最優(yōu)位置的粒子將保持靜止。

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

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

3.1 混沌初始化與區(qū)間處理

搜索空間指的是粒子能夠飛行的區(qū)域，一般問題對粒子的狀態(tài)參數(shù)都有約束區(qū)間，但標準粒子群算法一般不約束搜索空間，利用算法的收斂特性使得粒子自動回歸到最優(yōu)區(qū)間。初始化時一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系數(shù)α∈（0，1]為常數(shù)，即根據(jù)問題可以設(shè)置最大速度的大小。粒子初始化時，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個粒子第d維參數(shù)初始化時所選取的均勻分布的偽隨機函數(shù)。α取值越大，粒子具有的初始速度區(qū)間越大，粒子可能具有的初始速度越大，搜索范圍越廣。

3.2 混沌慣性權(quán)重

慣性權(quán)重w是影響PSO算法收斂性的重要因素。較大的慣性權(quán)重可以提高PSO算法的全局搜索能力，而較小的慣性權(quán)重則增加PSO算法的局部搜索能力。

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

■ （5）

由上式生成的混沌序列在[0，1]之間，然而PSO算法的慣性權(quán)重一般在[0.1，0.9]之間取值，所以要將該混沌序列空間限定在該范圍之內(nèi)，則混沌慣性權(quán)重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0為首代初始速度，max_generation為最大迭代次數(shù)，k為當前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點，從而提高算法的全局搜索能力。

參 考 文 獻

[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

【摘要】 粒子群在搜索過程中容易陷入局部而無法找到全局最優(yōu)值，且算法后期的粒子速度下降過快而失去搜索能力等缺陷，為了解決此早熟問題，提出了一種基于混沌思想的新型粒子群算法，并通過控制粒子平均速度保證算法的搜索趨勢。

【關(guān)鍵詞】 粒子群 最優(yōu)值 混沌 搜索能力

一、引言

粒子群優(yōu)化算法（PSO）是基于群體智能原理的優(yōu)化算法，是由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出的一種進化計算技術(shù)[1，[2]，源于對鳥群覓食過程中的遷徙和聚集的模擬。雖然PSO算法起步較晚，但其優(yōu)良的性能受到不少學者的重視。Shi等提出了慣性因子w線性遞減的改進算法[3]，使算法在搜索初期具有較大搜索能力，而在后期又能夠得到較精確的結(jié)果，此改進方案大大提高了基本PSO算法的性能。Van den Bergh通過使粒子群中最佳粒子始終處于運動狀態(tài)，得到保證收斂到具備最優(yōu)的改進算法，但其性能不佳[4]。Mendes等研究粒子群的拓撲結(jié)構(gòu)，分析粒子間的信息流，提出了一系列的拓撲結(jié)構(gòu)[5]。Zhang將選擇算子引入到PSO中，選擇每次迭代后較好的例子并復制到下一代，以保證每次迭代的粒子群都具有較好的性能[6]。PSO算法的優(yōu)勢在于收斂速度快，易實現(xiàn)并且僅有少量參數(shù)需要調(diào)整，但是，該算法仍然存在著一些需要完善的地方，本文將混沌的思想引入到PSO算法以提高其局搜索能力，并通過控制粒子平均速度保證算法的搜索趨勢。

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

2.1 基本粒子群算法原理

與大多數(shù)優(yōu)化方法相同，粒子群也是以迭代的形式進行搜索的。粒子群中的粒子是以搜索到的粒子個體最優(yōu)值點和種群找到的最優(yōu)值點位目標進行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新兩部分，具體如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp為粒子所經(jīng)歷過的最好位置；Xg為整個粒子群體所經(jīng)歷的最好位置；C2R2（Xg-Xi）是社會項，C1R1（Xp-Xi）是認知項；W是慣性權(quán)重，通常W∈[0，1]；不同的C1、C2描述了粒子對可行域的開發(fā)程度；R1、R2是均勻分布在（0，1）的隨機數(shù)。

2.2 混沌思想

盡管改進的粒子群優(yōu)化算法比標準的粒子群優(yōu)化算法有了很大的改進，但是由于初始化粒子的隨機性，某些粒子的位置及其pbest接近群體的gbest時，這些粒子會因為它以前的速度和慣性因子不為零而遠離最佳位置，而導致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

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

為了平衡算法的全局搜索能力和局部搜索能力對慣性因子進行的改進，在標準粒子群優(yōu)化算法中，慣性權(quán)重w是用來控制歷史速度對當前速度的影響程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w較大，則粒子有能力擴展搜索空間，全局搜索能力強，若w較小，主要是在當前解的附近搜索，局部搜索能力強；當w=0時，粒子沒有記憶性，它將飛向個體最優(yōu)位置和全局最優(yōu)位置的加權(quán)中心，而處于全局最優(yōu)位置的粒子將保持靜止。

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

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

3.1 混沌初始化與區(qū)間處理

搜索空間指的是粒子能夠飛行的區(qū)域，一般問題對粒子的狀態(tài)參數(shù)都有約束區(qū)間，但標準粒子群算法一般不約束搜索空間，利用算法的收斂特性使得粒子自動回歸到最優(yōu)區(qū)間。初始化時一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系數(shù)α∈（0，1]為常數(shù)，即根據(jù)問題可以設(shè)置最大速度的大小。粒子初始化時，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個粒子第d維參數(shù)初始化時所選取的均勻分布的偽隨機函數(shù)。α取值越大，粒子具有的初始速度區(qū)間越大，粒子可能具有的初始速度越大，搜索范圍越廣。

3.2 混沌慣性權(quán)重

慣性權(quán)重w是影響PSO算法收斂性的重要因素。較大的慣性權(quán)重可以提高PSO算法的全局搜索能力，而較小的慣性權(quán)重則增加PSO算法的局部搜索能力。

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

■ （5）

由上式生成的混沌序列在[0，1]之間，然而PSO算法的慣性權(quán)重一般在[0.1，0.9]之間取值，所以要將該混沌序列空間限定在該范圍之內(nèi)，則混沌慣性權(quán)重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0為首代初始速度，max_generation為最大迭代次數(shù)，k為當前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點，從而提高算法的全局搜索能力。

參 考 文 獻

[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

【摘要】 粒子群在搜索過程中容易陷入局部而無法找到全局最優(yōu)值，且算法后期的粒子速度下降過快而失去搜索能力等缺陷，為了解決此早熟問題，提出了一種基于混沌思想的新型粒子群算法，并通過控制粒子平均速度保證算法的搜索趨勢。

【關(guān)鍵詞】 粒子群 最優(yōu)值 混沌 搜索能力

一、引言

粒子群優(yōu)化算法（PSO）是基于群體智能原理的優(yōu)化算法，是由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出的一種進化計算技術(shù)[1，[2]，源于對鳥群覓食過程中的遷徙和聚集的模擬。雖然PSO算法起步較晚，但其優(yōu)良的性能受到不少學者的重視。Shi等提出了慣性因子w線性遞減的改進算法[3]，使算法在搜索初期具有較大搜索能力，而在后期又能夠得到較精確的結(jié)果，此改進方案大大提高了基本PSO算法的性能。Van den Bergh通過使粒子群中最佳粒子始終處于運動狀態(tài)，得到保證收斂到具備最優(yōu)的改進算法，但其性能不佳[4]。Mendes等研究粒子群的拓撲結(jié)構(gòu)，分析粒子間的信息流，提出了一系列的拓撲結(jié)構(gòu)[5]。Zhang將選擇算子引入到PSO中，選擇每次迭代后較好的例子并復制到下一代，以保證每次迭代的粒子群都具有較好的性能[6]。PSO算法的優(yōu)勢在于收斂速度快，易實現(xiàn)并且僅有少量參數(shù)需要調(diào)整，但是，該算法仍然存在著一些需要完善的地方，本文將混沌的思想引入到PSO算法以提高其局搜索能力，并通過控制粒子平均速度保證算法的搜索趨勢。

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

2.1 基本粒子群算法原理

與大多數(shù)優(yōu)化方法相同，粒子群也是以迭代的形式進行搜索的。粒子群中的粒子是以搜索到的粒子個體最優(yōu)值點和種群找到的最優(yōu)值點位目標進行搜索方向和位置的迭代更新，它主要包括速度更新和位置更新兩部分，具體如式（1）（2）所示。

■ （1）

■ （2）

式（1）是粒子速度更新式，其中：Xp為粒子所經(jīng)歷過的最好位置；Xg為整個粒子群體所經(jīng)歷的最好位置；C2R2（Xg-Xi）是社會項，C1R1（Xp-Xi）是認知項；W是慣性權(quán)重，通常W∈[0，1]；不同的C1、C2描述了粒子對可行域的開發(fā)程度；R1、R2是均勻分布在（0，1）的隨機數(shù)。

2.2 混沌思想

盡管改進的粒子群優(yōu)化算法比標準的粒子群優(yōu)化算法有了很大的改進，但是由于初始化粒子的隨機性，某些粒子的位置及其pbest接近群體的gbest時，這些粒子會因為它以前的速度和慣性因子不為零而遠離最佳位置，而導致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

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

為了平衡算法的全局搜索能力和局部搜索能力對慣性因子進行的改進，在標準粒子群優(yōu)化算法中，慣性權(quán)重w是用來控制歷史速度對當前速度的影響程度，平衡PSO算法的全局搜索能力和局部搜索能力的；若w較大，則粒子有能力擴展搜索空間，全局搜索能力強，若w較小，主要是在當前解的附近搜索，局部搜索能力強；當w=0時，粒子沒有記憶性，它將飛向個體最優(yōu)位置和全局最優(yōu)位置的加權(quán)中心，而處于全局最優(yōu)位置的粒子將保持靜止。

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

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

3.1 混沌初始化與區(qū)間處理

搜索空間指的是粒子能夠飛行的區(qū)域，一般問題對粒子的狀態(tài)參數(shù)都有約束區(qū)間，但標準粒子群算法一般不約束搜索空間，利用算法的收斂特性使得粒子自動回歸到最優(yōu)區(qū)間。初始化時一般取Vmax=α（Xmax d-Xmin d），其中取最大速度系數(shù)α∈（0，1]為常數(shù)，即根據(jù)問題可以設(shè)置最大速度的大小。粒子初始化時，采用如下公式：

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個粒子第d維參數(shù)初始化時所選取的均勻分布的偽隨機函數(shù)。α取值越大，粒子具有的初始速度區(qū)間越大，粒子可能具有的初始速度越大，搜索范圍越廣。

3.2 混沌慣性權(quán)重

慣性權(quán)重w是影響PSO算法收斂性的重要因素。較大的慣性權(quán)重可以提高PSO算法的全局搜索能力，而較小的慣性權(quán)重則增加PSO算法的局部搜索能力。

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

■ （5）

由上式生成的混沌序列在[0，1]之間，然而PSO算法的慣性權(quán)重一般在[0.1，0.9]之間取值，所以要將該混沌序列空間限定在該范圍之內(nèi)，則混沌慣性權(quán)重采用如下公式生成：

■ （6）

速度下限如下式所示：

■ （7）

其中V0為首代初始速度，max_generation為最大迭代次數(shù)，k為當前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點，從而提高算法的全局搜索能力。

參 考 文 獻

[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