用混沌粒子群算法求解函數(shù)優(yōu)化問題

戴月+張榮軍

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

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

一、引言

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

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

2.1 基本粒子群算法原理

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

■ （1）

■ （2）

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

2.2 混沌思想

盡管改進(jìn)的粒子群優(yōu)化算法比標(biāo)準(zhǔn)的粒子群優(yōu)化算法有了很大的改進(jìn)，但是由于初始化粒子的隨機(jī)性，某些粒子的位置及其pbest接近群體的gbest時(shí)，這些粒子會因?yàn)樗郧暗乃俣群蛻T性因子不為零而遠(yuǎn)離最佳位置，而導(dǎo)致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

三、改進(jìn)的混沌粒子群算法

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

Logistic映射的表達(dá)式如下式所示：

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

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

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

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個(gè)粒子第d維參數(shù)初始化時(shí)所選取的均勻分布的偽隨機(jī)函數(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為當(dāng)前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強(qiáng)了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點(diǎ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和社會心理學(xué)家Kennedy于1995年提出的一種進(jìn)化計(jì)算技術(shù)[1，[2]，源于對鳥群覓食過程中的遷徙和聚集的模擬。雖然PSO算法起步較晚，但其優(yōu)良的性能受到不少學(xué)者的重視。Shi等提出了慣性因子w線性遞減的改進(jìn)算法[3]，使算法在搜索初期具有較大搜索能力，而在后期又能夠得到較精確的結(jié)果，此改進(jìn)方案大大提高了基本PSO算法的性能。Van den Bergh通過使粒子群中最佳粒子始終處于運(yùn)動狀態(tài)，得到保證收斂到具備最優(yōu)的改進(jìn)算法，但其性能不佳[4]。Mendes等研究粒子群的拓?fù)浣Y(jié)構(gòu)，分析粒子間的信息流，提出了一系列的拓?fù)浣Y(jié)構(gòu)[5]。Zhang將選擇算子引入到PSO中，選擇每次迭代后較好的例子并復(fù)制到下一代，以保證每次迭代的粒子群都具有較好的性能[6]。PSO算法的優(yōu)勢在于收斂速度快，易實(shí)現(xiàn)并且僅有少量參數(shù)需要調(diào)整，但是，該算法仍然存在著一些需要完善的地方，本文將混沌的思想引入到PSO算法以提高其局搜索能力，并通過控制粒子平均速度保證算法的搜索趨勢。

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

2.1 基本粒子群算法原理

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

■ （1）

■ （2）

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

2.2 混沌思想

盡管改進(jìn)的粒子群優(yōu)化算法比標(biāo)準(zhǔn)的粒子群優(yōu)化算法有了很大的改進(jìn)，但是由于初始化粒子的隨機(jī)性，某些粒子的位置及其pbest接近群體的gbest時(shí)，這些粒子會因?yàn)樗郧暗乃俣群蛻T性因子不為零而遠(yuǎn)離最佳位置，而導(dǎo)致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

三、改進(jìn)的混沌粒子群算法

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

Logistic映射的表達(dá)式如下式所示：

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

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

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

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個(gè)粒子第d維參數(shù)初始化時(shí)所選取的均勻分布的偽隨機(jī)函數(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為當(dāng)前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強(qiáng)了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點(diǎ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和社會心理學(xué)家Kennedy于1995年提出的一種進(jìn)化計(jì)算技術(shù)[1，[2]，源于對鳥群覓食過程中的遷徙和聚集的模擬。雖然PSO算法起步較晚，但其優(yōu)良的性能受到不少學(xué)者的重視。Shi等提出了慣性因子w線性遞減的改進(jìn)算法[3]，使算法在搜索初期具有較大搜索能力，而在后期又能夠得到較精確的結(jié)果，此改進(jìn)方案大大提高了基本PSO算法的性能。Van den Bergh通過使粒子群中最佳粒子始終處于運(yùn)動狀態(tài)，得到保證收斂到具備最優(yōu)的改進(jìn)算法，但其性能不佳[4]。Mendes等研究粒子群的拓?fù)浣Y(jié)構(gòu)，分析粒子間的信息流，提出了一系列的拓?fù)浣Y(jié)構(gòu)[5]。Zhang將選擇算子引入到PSO中，選擇每次迭代后較好的例子并復(fù)制到下一代，以保證每次迭代的粒子群都具有較好的性能[6]。PSO算法的優(yōu)勢在于收斂速度快，易實(shí)現(xiàn)并且僅有少量參數(shù)需要調(diào)整，但是，該算法仍然存在著一些需要完善的地方，本文將混沌的思想引入到PSO算法以提高其局搜索能力，并通過控制粒子平均速度保證算法的搜索趨勢。

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

2.1 基本粒子群算法原理

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

■ （1）

■ （2）

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

2.2 混沌思想

盡管改進(jìn)的粒子群優(yōu)化算法比標(biāo)準(zhǔn)的粒子群優(yōu)化算法有了很大的改進(jìn)，但是由于初始化粒子的隨機(jī)性，某些粒子的位置及其pbest接近群體的gbest時(shí)，這些粒子會因?yàn)樗郧暗乃俣群蛻T性因子不為零而遠(yuǎn)離最佳位置，而導(dǎo)致算法不收斂。這種描述確定系統(tǒng)不確定性的理論有非常良好的非線性性質(zhì)，如對初始值敏感和對可行域的遍歷等。

三、改進(jìn)的混沌粒子群算法

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

Logistic映射的表達(dá)式如下式所示：

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

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

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

■ （3）

■ （4）

式中，εd，δd∈U[0，1]，εd，δd是第i個(gè)粒子第d維參數(shù)初始化時(shí)所選取的均勻分布的偽隨機(jī)函數(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為當(dāng)前迭代數(shù)。該速度公式為平均速度的下限。

四、小結(jié)

該算法首先通過混沌方法初始化粒子的初始位置和速度，增強(qiáng)了粒子的搜索能力。算法還通過混沌序列得到的慣性權(quán)重取代傳統(tǒng)的線性遞減的慣性權(quán)重，使粒子速度呈現(xiàn)多樣性的特點(diǎ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