群智能算法完整版本

第六章群智能算法智能優(yōu)化計(jì)算皖西學(xué)院應(yīng)用數(shù)學(xué)學(xué)院周本達(dá)bendazhou@2010年12月6.1群智能

6.1.1群智能的概念

6.1.2群智能算法

6.2蟻群優(yōu)化算法原理

6.2.1蟻群算法的起源

6.2.2蟻群算法的原理分析

6.3基本蟻群優(yōu)化算法

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性6.4改進(jìn)的蟻群優(yōu)化算法

6.4.1螞蟻系統(tǒng)的優(yōu)點(diǎn)與不足

6.4.2最優(yōu)解保留策略螞蟻系統(tǒng)

6.4.3蟻群系統(tǒng)

6.4.4最大－最小螞蟻系統(tǒng)

6.4.5基于排序的螞蟻系統(tǒng)

6.4.6各種蟻群優(yōu)化算法的比較智能優(yōu)化計(jì)算6.5蟻群優(yōu)化算法的應(yīng)用

6.5.1典型應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘6.6粒子群算法的基本原理

6.6.1粒子群算法的提出

6.6.2粒子群算法的原理描述6.7基本粒子群優(yōu)化算法

6.7.1基本粒子群算法描述

6.7.2參數(shù)分析

6.7.3與遺傳算法的比較6.8改進(jìn)粒子群優(yōu)化算法

6.8.1離散二進(jìn)制PSO

6.8.2慣性權(quán)重模型

6.8.3收斂因子模型

6.8.4研究現(xiàn)狀智能優(yōu)化計(jì)算6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題

6.9.2其它應(yīng)用6.10群智能算法的特點(diǎn)與不足智能優(yōu)化計(jì)算6.1群智能

智能優(yōu)化計(jì)算群智能（SwarmIntelligence,SI）人們把群居昆蟲的集體行為稱作“群智能”（“群體智能”、“群集智能”、“集群智能”等）

特點(diǎn)

個(gè)體的行為很簡(jiǎn)單，但當(dāng)它們一起協(xié)同工作時(shí)，卻能夠突現(xiàn)出非常復(fù)雜（智能）的行為特征。

6.1.1群智能的概念6.1群智能

智能優(yōu)化計(jì)算描述群智能作為一種新興的演化計(jì)算技術(shù)已成為研究焦點(diǎn)，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的關(guān)系。特性指無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性，在沒有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題求解方案提供了基礎(chǔ)。

6.1.2群智能算法6.1群智能

智能優(yōu)化計(jì)算優(yōu)點(diǎn)靈活性：群體可以適應(yīng)隨時(shí)變化的環(huán)境；

穩(wěn)健性：即使個(gè)體失敗，整個(gè)群體仍能完成任務(wù)；自我組織：活動(dòng)既不受中央控制，也不受局部監(jiān)管。典型算法蟻群算法（螞蟻覓食）粒子群算法（鳥群捕食）

6.1.2群智能算法6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算蟻群的自組織行為“雙橋?qū)嶒?yàn)”通過(guò)遺留在來(lái)往路徑上的信息素（Pheromone）揮發(fā)的化學(xué)性物質(zhì)來(lái)進(jìn)行通信和協(xié)調(diào)。

6.2.1蟻群算法的起源6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算蟻群的自組織行為“雙橋?qū)嶒?yàn)”

6.2.1蟻群算法的起源6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算提出蟻群系統(tǒng)

1992年，意大利學(xué)者M(jìn).Dorigo在其博士論文中提出螞蟻系統(tǒng)（AntSystem）。近年來(lái)，M.Dorigo等人進(jìn)一步將螞蟻算法發(fā)展為一種通用的優(yōu)化技術(shù)——蟻群優(yōu)化（antcolonyoptimization,ACO）。

6.2.1蟻群算法的起源螞蟻從A點(diǎn)出發(fā)，隨機(jī)選擇路線ABD或ACD。經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)：走ABD的螞蟻到達(dá)終點(diǎn)，走ACD的螞蟻剛好走到C點(diǎn)。6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算

6.2.2蟻群算法的原理分析蟻巢食物6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。

6.2.2蟻群算法的原理分析蟻巢食物

最后的極限是所有的螞蟻只選擇ABD路線。（正反饋過(guò)程）6.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算

6.2.2蟻群算法的原理分析蟻巢食物6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算解決TSP問(wèn)題

在算法的初始時(shí)刻，將m只螞蟻隨機(jī)放到n座城市;

將每只螞蟻k的禁忌表tabuk(s)的第一個(gè)元素tabuk(1)設(shè)置為它當(dāng)前所在城市;

設(shè)各路徑上的信息素τij(0)=C（C為一較小的常數(shù)）;

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算解決TSP問(wèn)題

每只螞蟻根據(jù)路徑上的信息素和啟發(fā)式信息（兩城市間距離）獨(dú)立地選擇下一座城市：在時(shí)刻t，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為

α、β分別表示信息素和啟發(fā)式因子的相對(duì)重要程度。

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)下一步允許的城市的集合6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算解決TSP問(wèn)題

當(dāng)所有螞蟻完成一次周游后，各路徑上的信息素將進(jìn)行更新：其中，ρ（0<ρ<1）表示路徑上信息素的蒸發(fā)系數(shù)，Q為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過(guò)路徑的長(zhǎng)度。

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算算法流程

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算初始參數(shù)

城市數(shù)30;

螞蟻數(shù)30；

α=1;

β=5;

ρ=0.5;

最大迭代代數(shù)200;

Q=100;

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3基本蟻群優(yōu)化算法

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)6.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算運(yùn)行結(jié)果

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)智能優(yōu)化計(jì)算三種模型

ant-cycle：（蟻周）

ant-quantity：（蟻量）

ant-density:

（蟻密）

6.3基本蟻群優(yōu)化算法

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)智能優(yōu)化計(jì)算三種模型在Ant-density和Ant-quantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素（局部信息），而在Ant-cycle中當(dāng)所有的螞蟻都完成了自己的行程后（全局信息）才對(duì)信息素進(jìn)行更新。6.3基本蟻群優(yōu)化算法

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)智能優(yōu)化計(jì)算三種模型的比較模型ant-density,ant-quantity,ant-cycle的比較(M.Dorigo,1996)6.3基本蟻群優(yōu)化算法

6.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)模型參數(shù)集最好參數(shù)集平均結(jié)果最好結(jié)果ant-densityα＝1,β=5,ρ=0.01426.740424.635ant-quantityα＝1,β=5,ρ=0.01427.315426.255?

ant-cycleα＝1,β=5,ρ=0.5424.250423.741智能優(yōu)化計(jì)算信息素的分布

6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計(jì)算信息素的分布

蒸發(fā)系數(shù)的影響：

6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性ρ＝0.05ρ＝0.95智能優(yōu)化計(jì)算參數(shù)α、β對(duì)算法性能的影響

停滯現(xiàn)象（Stagnationbehavior）：所有螞蟻都選擇相同的路徑，即系統(tǒng)不再搜索更好的解。原因在于較好路徑上的信息素遠(yuǎn)大于其他邊上的，從而使所有螞蟻都選擇該路徑。

6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計(jì)算參數(shù)α、β對(duì)算法性能的影響

α取較大值時(shí)，意味著在選擇路徑時(shí)，路徑上的信息素非常重要；當(dāng)α取較小值時(shí)，變成隨機(jī)的貪婪算法。6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計(jì)算參數(shù)α、β對(duì)算法性能的影響

α＝0，螞蟻之間無(wú)協(xié)同作用；α＝1，有協(xié)同作用6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性α＝0α＝1智能優(yōu)化計(jì)算螞蟻數(shù)m對(duì)算法的影響

m≈n時(shí)，ant-cycle可以在最少迭代次數(shù)內(nèi)找到最優(yōu)解。

6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性m＝15m＝150m＝30智能優(yōu)化計(jì)算螞蟻的初始分布

兩種情況實(shí)驗(yàn)：（1）所有螞蟻初始時(shí)刻放在同一城市；（2）螞蟻分布在不同城市中。第（2）中情況可獲得較高性能。（3）在不同城市分布時(shí)，隨機(jī)分布與統(tǒng)一分布的差別不大。

6.3基本蟻群優(yōu)化算法

6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計(jì)算優(yōu)點(diǎn)

較強(qiáng)的魯棒性；分布式計(jì)算；易于與其他方法結(jié)合。缺點(diǎn)

搜索時(shí)間較長(zhǎng)；容易出現(xiàn)停滯現(xiàn)象。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.1螞蟻系統(tǒng)的優(yōu)點(diǎn)與不足智能優(yōu)化計(jì)算最優(yōu)解保留策略（AntSystemwithElitist,ASelite）

每次迭代完成后，對(duì)全局最優(yōu)解更進(jìn)一步地進(jìn)行利用；信息素更新策略

σ為最優(yōu)螞蟻數(shù)，Lgb為全局最優(yōu)解。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.2最優(yōu)解保留策略螞蟻系統(tǒng)智能優(yōu)化計(jì)算最優(yōu)解保留策略（AntSystemwithElitist,ASelite）

該策略能夠以更快的速度獲得最好解，但是如果選擇的精英過(guò)多則算法會(huì)由于較早收斂于局部次優(yōu)解而導(dǎo)致搜索的過(guò)早停滯。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.2最優(yōu)解保留策略螞蟻系統(tǒng)智能優(yōu)化計(jì)算蟻群系統(tǒng)（AntColonySystem,ACS）的改進(jìn)之處

（1）在選擇下一城市時(shí)，更多地利用了當(dāng)前最好解；（2）只在全局最優(yōu)解所屬邊上增加信息素；（3）每次螞蟻從城市i轉(zhuǎn)移到城市j時(shí)，邊ij

上的信息素將會(huì)適當(dāng)減少，從而實(shí)現(xiàn)一種信息素的局部調(diào)整以減少已選擇過(guò)的路徑再次被選擇的概率。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算可行解的構(gòu)造

偽隨機(jī)比率選擇規(guī)則：螞蟻以概率q0（0～1間的常數(shù)）移動(dòng)到最大可能的城市

q為0～1的隨機(jī)數(shù)，S為一隨機(jī)變量，當(dāng)q>q0時(shí)，S以以下概率來(lái)選擇：6.4改進(jìn)的蟻群優(yōu)化算法

6.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算局部信息素更新

使已選的邊對(duì)后來(lái)的螞蟻具有較小的影響力，從而使螞蟻對(duì)沒有選中的邊有更強(qiáng)的探索能力。當(dāng)螞蟻從城市i轉(zhuǎn)移到城市j后，邊ij上的信息素更新為：其中，τ0為常數(shù)，ξ∈(0,1)為可調(diào)參數(shù)。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算全局信息素更新

只針對(duì)全局最優(yōu)解進(jìn)行更新：

6.4改進(jìn)的蟻群優(yōu)化算法

6.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算最大－最小螞蟻系統(tǒng)（max-minantsystem,MMAS）的改進(jìn)之處

（1）每次迭代后，只有最優(yōu)解（最優(yōu)螞蟻）所屬路徑上的信息被更新；（2）為了避免過(guò)早收斂，將各條路徑可能的信息素限制于[τmin

,τmax]；（3）初始時(shí)刻，各路徑上信息素設(shè)置為τmax

，在算法初始時(shí)刻，ρ取較小值時(shí)算法有更好的發(fā)現(xiàn)較好解的能力。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.4最大－最小螞蟻系統(tǒng)智能優(yōu)化計(jì)算信息素的全局更新

使所有螞蟻完成一次迭代后，進(jìn)行信息素更新：

6.4改進(jìn)的蟻群優(yōu)化算法

6.4.4最大－最小螞蟻系統(tǒng)智能優(yōu)化計(jì)算基于排序的螞蟻系統(tǒng)（rank-basedversionofantsystem,ASrank）

每次迭代完成后，螞蟻所經(jīng)路徑按從小到大的順序排列，并對(duì)它們賦予不同權(quán)值，路徑越短權(quán)值越大。全局最優(yōu)解權(quán)值為w，第r個(gè)最優(yōu)解的權(quán)值為max{0,w-r}。6.4改進(jìn)的蟻群優(yōu)化算法

6.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計(jì)算基于排序的螞蟻系統(tǒng)（rank-basedversionofantsystem,ASrank）

信息素更新：6.4改進(jìn)的蟻群優(yōu)化算法

6.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計(jì)算優(yōu)化結(jié)果比較

對(duì)對(duì)稱TSP各迭代10000次，對(duì)非對(duì)稱TSP各迭代20000次：6.4改進(jìn)的蟻群優(yōu)化算法

6.4.6各種蟻群優(yōu)化算法的比較TSP實(shí)例MMASACSASeliteASEil51.tsp427.6428.1428.3437.3kroA100.tsp21320.321420.021522.8322471.4D198.tsp15972.516054.016205.016705.6Lin31842220.242570.043422.845535.2Ry48p.atsp14553.214565.414685.215296.4Ft70.atsp39040.239099.039261.839596.3Kro124p.atsp36773.536857.037510.238733.1Ftv170.atsp2828.82826.52952.43154.5智能優(yōu)化計(jì)算典型應(yīng)用列表

6.5蟻群優(yōu)化算法的應(yīng)用

6.5.1典型應(yīng)用智能優(yōu)化計(jì)算如何應(yīng)用

用蟻群算法解決數(shù)據(jù)分類（數(shù)據(jù)挖掘任務(wù)中的一種）的問(wèn)題：預(yù)先定義一組類，然后把數(shù)據(jù)系中的每一個(gè)數(shù)據(jù)根據(jù)該數(shù)據(jù)的屬性，歸入這些類中的一個(gè)。當(dāng)數(shù)據(jù)量很大時(shí)，難以人為判別分類。

6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算如何應(yīng)用分類的規(guī)則：

IF<term1ANDterm2AND…>THEN<class>

每個(gè)term是一個(gè)三元組（屬性、關(guān)系符、屬性取值）希望在一個(gè)規(guī)則中使用最少的判別語(yǔ)句，采用蟻群優(yōu)化算法達(dá)到最優(yōu)的選擇。6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算例：非典型肺炎考慮如下因素：

6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘?qū)傩园l(fā)熱職業(yè)胸部陰影流行病學(xué)史值（0,1,2,3）（0,1,2）（0,1,2）（0,1,2）說(shuō)明0：不考慮該屬性1：37.5℃以下2：37.5℃～38.5℃3：38.5℃以上0：不考慮該屬性1：醫(yī)務(wù)人員2：其他人員0：不考慮該屬性1：無(wú)2：有0：不考慮該屬性1：無(wú)2：有智能優(yōu)化計(jì)算例：非典型肺炎結(jié)構(gòu)圖：

一個(gè)螞蟻從始點(diǎn)行走至終點(diǎn)，得到一條路徑{0,2,1,0}，其對(duì)應(yīng)的規(guī)則為

IF（職業(yè)＝其他人員）AND（胸部陰影＝無(wú)）THEN（非典型肺炎）對(duì)此路徑，應(yīng)給予非常差的評(píng)價(jià)。6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算蟻群算法的實(shí)現(xiàn)

假設(shè)a表示屬性的總個(gè)數(shù)，第i個(gè)屬性的取值域中可取bi個(gè)數(shù)值。一只螞蟻的行走k步的路徑可以表示為

route[k]=(y1,y2,…,ya)

yi=0表示不包含屬性i。6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算評(píng)價(jià)函數(shù)

解的評(píng)價(jià)函數(shù)定義為：

Q的數(shù)值越接近1，說(shuō)明對(duì)該類的判斷越準(zhǔn)確。

TP—truepositivesTN—truenegativesFP—falsepositivesFN—falsenegatives6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘True：判斷結(jié)果，正確False：判斷結(jié)果，失誤Positives：真實(shí)屬性，屬于Negatives：真實(shí)屬性，不屬于智能優(yōu)化計(jì)算轉(zhuǎn)移概率

ηij表示每個(gè)條件項(xiàng)的啟發(fā)式參數(shù)值（信息熵），τij(t)表示第i個(gè)屬性的第j個(gè)取值在t時(shí)刻的信息素。6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算信息素增加

R是當(dāng)前規(guī)則中所有包含的條件項(xiàng)；信息素?fù)]發(fā)

減少?zèng)]被選中的三元組的信息量。6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算結(jié)果分析

診斷準(zhǔn)確度比較

6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘數(shù)據(jù)庫(kù)蟻群優(yōu)化算法CN2LjubljanabreastcancerWisconsinbreastcancerTic-tac-toeDermatologyHepatitisClevelandheartdisease75.28±2.2496.04±0.9373.04±2.5394.29±1.2090.00±3.1159.67±2.5067.69±3.5994.88±0.8897.38±0.5290.38±1.6690.00±2.5057.48±1.78智能優(yōu)化計(jì)算結(jié)果分析

診斷規(guī)則數(shù)比較

6.5蟻群優(yōu)化算法的應(yīng)用

6.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘數(shù)據(jù)庫(kù)蟻群優(yōu)化算法CN2LjubljanabreastcancerWisconsinbreastcancerTic-tac-toeDermatologyHepatitisClevelandheartdisease7.10±0.316.20±0.258.50±0.627.30±0.153.40±0.169.50±0.9255.40±2.0718.60±0.4539.70±2.5218.50±0.477.20±0.2542.40±0.71智能優(yōu)化計(jì)算由JamesKenney（社會(huì)心理學(xué)博士）和RussEberhart（電子工程學(xué)博士，http:///~eberhart/

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

6.6粒子群算法的基本原理

6.6.1粒子群算法的提出智能優(yōu)化計(jì)算源于對(duì)鳥群捕食行為的研究，是基于迭代的方法簡(jiǎn)單易于實(shí)現(xiàn)，需要調(diào)整的參數(shù)相對(duì)較少在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、工業(yè)系統(tǒng)優(yōu)化和模糊系統(tǒng)控制等領(lǐng)域得到了廣泛的應(yīng)用。6.6粒子群算法的基本原理

6.6.1粒子群算法的提出智能優(yōu)化計(jì)算鳥群：假設(shè)一個(gè)區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當(dāng)前位置離食物還有多遠(yuǎn)。PSO算法

每個(gè)解看作一只鳥，稱為“粒子(particle)”，所有的粒子都有一個(gè)適應(yīng)值，每個(gè)粒子都有一個(gè)速度決定它們的飛翔方向和距離，粒子們追隨當(dāng)前最優(yōu)粒子在解空間中搜索。6.6粒子群算法的基本原理

6.6.2粒子群算法的原理描述智能優(yōu)化計(jì)算PSO算法

初始化為一群隨機(jī)粒子，通過(guò)迭代找到最優(yōu)。每次迭代中，粒子通過(guò)跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來(lái)更新自己的位置。6.6粒子群算法的基本原理

6.6.2粒子群算法的原理描述智能優(yōu)化計(jì)算粒子速度和位置的更新

假設(shè)在D維搜索空間中，有m個(gè)粒子；其中第i個(gè)粒子的位置為矢量其飛翔速度也是一個(gè)矢量，記為第i個(gè)粒子搜索到的最優(yōu)位置為整個(gè)粒子群搜索到的最優(yōu)位置為第i個(gè)粒子的位置和速度更新為：6.7基本粒子群優(yōu)化算法

6.7.1基本粒子群算法描述智能優(yōu)化計(jì)算粒子速度和位置的更新

其中，w稱為慣性權(quán)重，

c1和c2為兩個(gè)正常數(shù)，稱為加速因子。將vidk

限制在一個(gè)最大速度vmax

內(nèi)。6.7基本粒子群優(yōu)化算法

6.7.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+1智能優(yōu)化計(jì)算粒子速度和位置的更新

6.7基本粒子群優(yōu)化算法

6.7.1基本粒子群算法描述“慣性部分”，對(duì)自身運(yùn)動(dòng)狀態(tài)的信任“認(rèn)知部分”，對(duì)微粒本身的思考，即來(lái)源于自己經(jīng)驗(yàn)的部分“社會(huì)部分”，微粒間的信息共享，來(lái)源于群體中的其它優(yōu)秀微粒的經(jīng)驗(yàn)智能優(yōu)化計(jì)算迭代過(guò)程

6.7基本粒子群優(yōu)化算法

6.7.1基本粒子群算法描述智能優(yōu)化計(jì)算算法流程

6.7基本粒子群優(yōu)化算法StartInitializeparticleswithrandompositionandvelocityvectors.Foreachparticle’sposition(xi)evaluatefitnessIffitness(xi)betterthanfitness(p)thenp=xiLoopuntilallparticlesexhaustSetbestofpsasgBestUpdateparticlesvelocityandpositionLoopuntilmaxiterStop:givinggBest,optimalsolution.

6.7.1基本粒子群算法描述智能優(yōu)化計(jì)算慣性權(quán)重w

使粒子保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。表示微粒對(duì)當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)。較大的w有利于跳出局部極值，而較小的w有利于算法收斂。6.7基本粒子群優(yōu)化算法

6.7.2參數(shù)分析智能優(yōu)化計(jì)算加速常數(shù)c1和c2

代表將微粒推向pbest和gbest位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)重。表示粒子的動(dòng)作來(lái)源于自己經(jīng)驗(yàn)的部分和其它粒子經(jīng)驗(yàn)的部分。低的值允許粒子在被拉回之前可以在目標(biāo)區(qū)域外徘徊，而高的值則導(dǎo)致粒子突然沖向或越過(guò)目標(biāo)區(qū)域。

6.7基本粒子群優(yōu)化算法

6.7.2參數(shù)分析智能優(yōu)化計(jì)算加速常數(shù)c1和c2

將c1和c2統(tǒng)一為一個(gè)控制參數(shù)，φ=c1+c2

如果φ很小，微粒群運(yùn)動(dòng)軌跡將非常緩慢；如果φ很大，則微粒位置變化非常快；實(shí)驗(yàn)表明，當(dāng)φ=4.1（通常c1=2.0，c2=2.0）時(shí)，具有很好的收斂效果。6.7基本粒子群優(yōu)化算法

6.7.2參數(shù)分析智能優(yōu)化計(jì)算粒子數(shù)

一般取20～40，對(duì)較難或特定類別的問(wèn)題可以取

100～200。最大速度vmax

決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)定為粒子的范圍寬度。終止條件

最大循環(huán)數(shù)以及最小錯(cuò)誤要求。6.7基本粒子群優(yōu)化算法

6.7.2參數(shù)分析智能優(yōu)化計(jì)算共性

（1）都屬于仿生算法；（2）都屬于全局優(yōu)化方法；（3）都屬于隨機(jī)搜索算法；（4）都隱含并行性；（5）根據(jù)個(gè)體的適配信息進(jìn)行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性、可導(dǎo)性等；（6）對(duì)高維復(fù)雜問(wèn)題，往往會(huì)遇到早熟收斂和收斂性能差的缺點(diǎn)，都無(wú)法保證收斂到最優(yōu)點(diǎn)。6.7基本粒子群優(yōu)化算法

6.7.3與遺傳算法的比較智能優(yōu)化計(jì)算差異

（1）PSO有記憶，所有粒子都保存較優(yōu)解的知識(shí)，而GA，以前的知識(shí)隨著種群的改變被改變；（2）PSO中的粒子是一種單向共享信息機(jī)制。而GA中的染色體之間相互共享信息，使得整個(gè)種群都向最優(yōu)區(qū)域移動(dòng)；（3）GA需要編碼和遺傳操作，而PSO沒有交叉和變異操作，粒子只是通過(guò)內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、參數(shù)更少、實(shí)現(xiàn)更容易。6.7基本粒子群優(yōu)化算法

6.7.3與遺傳算法的比較智能優(yōu)化計(jì)算用途

基本PSO是用來(lái)解決連續(xù)問(wèn)題優(yōu)化的，離散二進(jìn)制PSO用來(lái)解決組合優(yōu)化問(wèn)題。運(yùn)動(dòng)方程不同

粒子的位置只有(0,1)兩種狀態(tài)。速度值越大，則粒子位置取1的可能性越大，反之越小。6.8改進(jìn)粒子群優(yōu)化算法

6.8.1離散二進(jìn)制PSO智能優(yōu)化計(jì)算思路

在考慮實(shí)際優(yōu)化問(wèn)題時(shí)，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部精細(xì)搜索以獲得高精度的解。研究發(fā)現(xiàn)，較大的w

值有利于跳出局部極小點(diǎn)，而較小的w

值有利于算法收斂，因此提出了自適應(yīng)調(diào)整的策略，即隨著迭代的進(jìn)行，線性地減小w

的值。6.8改進(jìn)粒子群優(yōu)化算法

6.8.2慣性權(quán)重模型智能優(yōu)化計(jì)算變化的慣性權(quán)重

wmax、wmin分別是w的最大值和最小值；iter、itermax分別是當(dāng)前迭代次數(shù)和最大迭代次數(shù)。6.8改進(jìn)粒子群優(yōu)化算法

6.8.2慣性權(quán)重模型智能優(yōu)化計(jì)算提出

1999年Clerc對(duì)算法的研究證明，采用收斂因子能

夠確保算法的收斂。收斂因子模型

通常將φ設(shè)為4.1，經(jīng)計(jì)算k為0.729。6.8改進(jìn)粒子群優(yōu)化算法

6.8.3收斂因子模型智能優(yōu)化計(jì)算主要研究方向

主要集中于對(duì)算法結(jié)構(gòu)和性能的改善方面，包括：參數(shù)設(shè)置、粒子多樣性、種群結(jié)構(gòu)和算法的融合。發(fā)展方向

目前大部分成果都是通過(guò)大量試驗(yàn)獲得的，缺少對(duì)算法機(jī)理的研究，對(duì)PSO中的參數(shù)分析沒有實(shí)質(zhì)性的認(rèn)識(shí)，還處于試驗(yàn)分析階段。6.8改進(jìn)粒子群優(yōu)化算法

6.8.4研究現(xiàn)狀智能優(yōu)化計(jì)算交換子和交換序

設(shè)n個(gè)節(jié)點(diǎn)的TSP問(wèn)題的解序列為s=(ai)，i=1…n。定義交換子SO(i1,i2)為交換解S中的點(diǎn)ai1和ai2，則S’=S+SO(i1,i2)為解S經(jīng)算子SO(i1,i2)操作后的新解。一個(gè)或多個(gè)交換子的有序隊(duì)列就是交換序，記作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON等是交換子，之間的順序是有意義的,意味著所有的交換子依次作用于某解上。6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題智能優(yōu)化計(jì)算6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題符號(hào)的定義

若干個(gè)交換序可以合并成一個(gè)新的交換序，定義為兩個(gè)交換序的合并算子。設(shè)兩個(gè)交換序SS1和SS2按先后順序作用于解S上，得到新解S’。假設(shè)另外有一個(gè)交換序SS’作用于同一解S上，能夠得到形同的解S’，可定義智能優(yōu)化計(jì)算6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題符號(hào)的定義

和屬于同一等價(jià)集，在交換序等價(jià)集中，擁有最少交換子的交換序稱為該等價(jià)集的基本交換序。智能優(yōu)化計(jì)算解決TSP問(wèn)題的速度算式定義

α、β為[0,1]上的隨機(jī)數(shù)。

vid表示交換序，xid表示路徑序列（解）。6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題智能優(yōu)化計(jì)算算法流程

1.初始化粒子群，給每個(gè)粒子一個(gè)初始解(xid)和隨機(jī)的交換序(vid);2.如果滿足結(jié)束條件，轉(zhuǎn)步驟5;3.根據(jù)粒子當(dāng)前位置xid計(jì)算下一新解xid’;4.如果整個(gè)群體找到一個(gè)更好的解，更新Pgd，轉(zhuǎn)步驟2;5.顯示結(jié)果。6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題智能優(yōu)化計(jì)算6.9粒子群優(yōu)化算法的應(yīng)用

6.9.1求解TSP問(wèn)題算法流程

3.根據(jù)粒子當(dāng)前位置xid計(jì)算下一新解xid’:1）計(jì)算A=pid-xid，A是一個(gè)基本交換序，表示A作用于xid得到pid；

2）計(jì)算B=pgd-xid，B也是一個(gè)基本交換序；

3）更新速度，并將其轉(zhuǎn)換為一個(gè)基本交換序；

4）更新解；

5）如果找到一個(gè)更好得解，更新pid。智能優(yōu)化計(jì)算運(yùn)行結(jié)果