群智能算法群智能算法優秀課件全文共97頁，當前為第1頁。6.1群智能

6.1.1群智能的概念

6.1.2群智能算法

6.2蟻群優化算法原理

6.2.1蟻群算法的起源

6.2.2蟻群算法的原理分析

6.3基本蟻群優化算法

6.3.1螞蟻系統的模型與實現

6.3.2螞蟻系統的參數設置和基本屬性6.4改進的蟻群優化算法

6.4.1螞蟻系統的優點與不足

6.4.2最優解保留策略螞蟻系統

6.4.3蟻群系統

6.4.4最大－最小螞蟻系統

6.4.5基于排序的螞蟻系統

6.4.6各種蟻群優化算法的比較智能優化計算群智能算法優秀課件全文共97頁，當前為第2頁。6.5蟻群優化算法的應用

6.5.1典型應用

6.5.2醫學診斷的數據挖掘6.6粒子群算法的基本原理

6.6.1粒子群算法的提出

6.6.2粒子群算法的原理描述6.7基本粒子群優化算法

6.7.1基本粒子群算法描述

6.7.2參數分析

6.7.3與遺傳算法的比較6.8改進粒子群優化算法

6.8.1離散二進制PSO

6.8.2慣性權重模型

6.8.3收斂因子模型

6.8.4研究現狀智能優化計算群智能算法優秀課件全文共97頁，當前為第3頁。6.9粒子群優化算法的應用

6.9.1求解TSP問題

6.9.2其它應用6.10群智能算法的特點與不足智能優化計算群智能算法優秀課件全文共97頁，當前為第4頁。6.1群智能

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

特點

個體的行為很簡單，但當它們一起協同工作時，卻能夠突現出非常復雜（智能）的行為特征。

6.1.1群智能的概念群智能算法優秀課件全文共97頁，當前為第5頁。6.1群智能

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

6.1.2群智能算法群智能算法優秀課件全文共97頁，當前為第6頁。6.1群智能

智能優化計算優點靈活性：群體可以適應隨時變化的環境；

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

6.1.2群智能算法群智能算法優秀課件全文共97頁，當前為第7頁。6.2蟻群優化算法原理

智能優化計算蟻群的自組織行為“雙橋實驗”通過遺留在來往路徑上的信息素（Pheromone）揮發的化學性物質來進行通信和協調。

6.2.1蟻群算法的起源群智能算法優秀課件全文共97頁，當前為第8頁。6.2蟻群優化算法原理

智能優化計算蟻群的自組織行為“雙橋實驗”

6.2.1蟻群算法的起源群智能算法優秀課件全文共97頁，當前為第9頁。6.2蟻群優化算法原理

智能優化計算提出蟻群系統1992年，意大利學者M.Dorigo在其博士論文中提出螞蟻系統（AntSystem）。近年來，M.Dorigo等人進一步將螞蟻算法發展為一種通用的優化技術——蟻群優化（antcolonyoptimization,ACO）。

6.2.1蟻群算法的起源群智能算法優秀課件全文共97頁，當前為第10頁。螞蟻從A點出發，隨機選擇路線ABD或ACD。經過9個時間單位時：走ABD的螞蟻到達終點，走ACD的螞蟻剛好走到C點。6.2蟻群優化算法原理

智能優化計算

6.2.2蟻群算法的原理分析蟻巢食物群智能算法優秀課件全文共97頁，當前為第11頁。6.2蟻群優化算法原理

智能優化計算經過18個時間單位時：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。

6.2.2蟻群算法的原理分析蟻巢食物群智能算法優秀課件全文共97頁，當前為第12頁。

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

智能優化計算

6.2.2蟻群算法的原理分析蟻巢食物群智能算法優秀課件全文共97頁，當前為第13頁。6.3基本蟻群優化算法

智能優化計算解決TSP問題

在算法的初始時刻，將m只螞蟻隨機放到n座城市;

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

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

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第14頁。6.3基本蟻群優化算法

智能優化計算解決TSP問題

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

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

6.3.1螞蟻系統的模型與實現下一步允許的城市的集合群智能算法優秀課件全文共97頁，當前為第15頁。6.3基本蟻群優化算法

智能優化計算解決TSP問題

當所有螞蟻完成一次周游后，各路徑上的信息素將進行更新：其中，ρ（0<ρ<1）表示路徑上信息素的蒸發系數，Q為正常數，Lk表示第k只螞蟻在本次周游中所走過路徑的長度。

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第16頁。6.3基本蟻群優化算法

智能優化計算算法流程

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第17頁。6.3基本蟻群優化算法

智能優化計算初始參數城市數30;螞蟻數30；

α=1;

β=5;

ρ=0.5;最大迭代代數200;

Q=100;

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第18頁。6.3基本蟻群優化算法

智能優化計算運行結果

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第19頁。6.3基本蟻群優化算法

智能優化計算運行結果

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第20頁。智能優化計算運行結果

6.3基本蟻群優化算法

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第21頁。6.3基本蟻群優化算法

智能優化計算運行結果

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第22頁。6.3基本蟻群優化算法

智能優化計算運行結果

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第23頁。6.3基本蟻群優化算法

智能優化計算運行結果

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第24頁。智能優化計算三種模型

ant-cycle：（蟻周）

ant-quantity：（蟻量）

ant-density:（蟻密）

6.3基本蟻群優化算法

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第25頁。智能優化計算三種模型在Ant-density和Ant-quantity中螞蟻在兩個位置節點間每移動一次后即更新信息素（局部信息），而在Ant-cycle中當所有的螞蟻都完成了自己的行程后（全局信息）才對信息素進行更新。6.3基本蟻群優化算法

6.3.1螞蟻系統的模型與實現群智能算法優秀課件全文共97頁，當前為第26頁。智能優化計算三種模型的比較模型ant-density,ant-quantity,ant-cycle的比較(M.Dorigo,1996)6.3基本蟻群優化算法

6.3.1螞蟻系統的模型與實現模型參數集最好參數集平均結果最好結果ant-densityα＝1,β=5,ρ=0.01426.740424.635ant-quantityα＝1,β=5,ρ=0.01427.315426.255?

ant-cycleα＝1,β=5,ρ=0.5424.250423.741群智能算法優秀課件全文共97頁，當前為第27頁。智能優化計算信息素的分布

6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性群智能算法優秀課件全文共97頁，當前為第28頁。智能優化計算信息素的分布

蒸發系數的影響：

6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性ρ＝0.05ρ＝0.95群智能算法優秀課件全文共97頁，當前為第29頁。智能優化計算參數α、β對算法性能的影響

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

6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性群智能算法優秀課件全文共97頁，當前為第30頁。智能優化計算參數α、β對算法性能的影響

α取較大值時，意味著在選擇路徑時，路徑上的信息素非常重要；當α取較小值時，變成隨機的貪婪算法。6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性群智能算法優秀課件全文共97頁，當前為第31頁。智能優化計算參數α、β對算法性能的影響

α＝0，螞蟻之間無協同作用；α＝1，有協同作用6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性α＝0α＝1群智能算法優秀課件全文共97頁，當前為第32頁。智能優化計算螞蟻數m對算法的影響

m≈n時，ant-cycle可以在最少迭代次數內找到最優解。

6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性m＝15m＝150m＝30群智能算法優秀課件全文共97頁，當前為第33頁。智能優化計算螞蟻的初始分布

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

6.3基本蟻群優化算法

6.3.2螞蟻系統的參數設置和基本屬性群智能算法優秀課件全文共97頁，當前為第34頁。智能優化計算優點

較強的魯棒性；分布式計算；易于與其他方法結合。缺點

搜索時間較長；容易出現停滯現象。6.4改進的蟻群優化算法

6.4.1螞蟻系統的優點與不足群智能算法優秀課件全文共97頁，當前為第35頁。智能優化計算最優解保留策略（AntSystemwithElitist,ASelite）

每次迭代完成后，對全局最優解更進一步地進行利用；信息素更新策略

σ為最優螞蟻數，Lgb為全局最優解。6.4改進的蟻群優化算法

6.4.2最優解保留策略螞蟻系統群智能算法優秀課件全文共97頁，當前為第36頁。智能優化計算最優解保留策略（AntSystemwithElitist,ASelite）

該策略能夠以更快的速度獲得最好解，但是如果選擇的精英過多則算法會由于較早收斂于局部次優解而導致搜索的過早停滯。6.4改進的蟻群優化算法

6.4.2最優解保留策略螞蟻系統群智能算法優秀課件全文共97頁，當前為第37頁。智能優化計算蟻群系統（AntColonySystem,ACS）的改進之處

（1）在選擇下一城市時，更多地利用了當前最好解；（2）只在全局最優解所屬邊上增加信息素；（3）每次螞蟻從城市i轉移到城市j時，邊ij上的信息素將會適當減少，從而實現一種信息素的局部調整以減少已選擇過的路徑再次被選擇的概率。6.4改進的蟻群優化算法

6.4.3蟻群系統群智能算法優秀課件全文共97頁，當前為第38頁。智能優化計算可行解的構造

偽隨機比率選擇規則：螞蟻以概率q0（0～1間的常數）移動到最大可能的城市

q為0～1的隨機數，S為一隨機變量，當q>q0時，S以以下概率來選擇：6.4改進的蟻群優化算法

6.4.3蟻群系統群智能算法優秀課件全文共97頁，當前為第39頁。智能優化計算局部信息素更新

使已選的邊對后來的螞蟻具有較小的影響力，從而使螞蟻對沒有選中的邊有更強的探索能力。當螞蟻從城市i轉移到城市j后，邊ij上的信息素更新為：其中，τ0為常數，ξ∈(0,1)為可調參數。6.4改進的蟻群優化算法

6.4.3蟻群系統群智能算法優秀課件全文共97頁，當前為第40頁。智能優化計算全局信息素更新

只針對全局最優解進行更新：

6.4改進的蟻群優化算法

6.4.3蟻群系統群智能算法優秀課件全文共97頁，當前為第41頁。智能優化計算最大－最小螞蟻系統（max-minantsystem,MMAS）的改進之處

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

,τmax]；（3）初始時刻，各路徑上信息素設置為τmax，在算法初始時刻，ρ取較小值時算法有更好的發現較好解的能力。6.4改進的蟻群優化算法

6.4.4最大－最小螞蟻系統群智能算法優秀課件全文共97頁，當前為第42頁。智能優化計算信息素的全局更新

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

6.4改進的蟻群優化算法

6.4.4最大－最小螞蟻系統群智能算法優秀課件全文共97頁，當前為第43頁。智能優化計算基于排序的螞蟻系統（rank-basedversionofantsystem,ASrank）

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

6.4.5基于排序的螞蟻系統群智能算法優秀課件全文共97頁，當前為第44頁。智能優化計算基于排序的螞蟻系統（rank-basedversionofantsystem,ASrank）

信息素更新：6.4改進的蟻群優化算法

6.4.5基于排序的螞蟻系統群智能算法優秀課件全文共97頁，當前為第45頁。智能優化計算優化結果比較

對對稱TSP各迭代10000次，對非對稱TSP各迭代20000次：6.4改進的蟻群優化算法

6.4.6各種蟻群優化算法的比較TSP實例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群智能算法優秀課件全文共97頁，當前為第46頁。智能優化計算典型應用列表

6.5蟻群優化算法的應用

6.5.1典型應用群智能算法優秀課件全文共97頁，當前為第47頁。智能優化計算如何應用

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

6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第48頁。智能優化計算如何應用分類的規則：IF<term1ANDterm2AND…>THEN<class>每個term是一個三元組（屬性、關系符、屬性取值）希望在一個規則中使用最少的判別語句，采用蟻群優化算法達到最優的選擇。6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第49頁。智能優化計算例：非典型肺炎考慮如下因素：

6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘屬性發熱職業胸部陰影流行病學史值（0,1,2,3）（0,1,2）（0,1,2）（0,1,2）說明0：不考慮該屬性1：37.5℃以下2：37.5℃～38.5℃3：38.5℃以上0：不考慮該屬性1：醫務人員2：其他人員0：不考慮該屬性1：無2：有0：不考慮該屬性1：無2：有群智能算法優秀課件全文共97頁，當前為第50頁。智能優化計算例：非典型肺炎結構圖：

一個螞蟻從始點行走至終點，得到一條路徑{0,2,1,0}，其對應的規則為IF（職業＝其他人員）AND（胸部陰影＝無）THEN（非典型肺炎）對此路徑，應給予非常差的評價。6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第51頁。智能優化計算蟻群算法的實現

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

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

yi=0表示不包含屬性i。6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第52頁。智能優化計算評價函數

解的評價函數定義為：

Q的數值越接近1，說明對該類的判斷越準確。TP—truepositivesTN—truenegativesFP—falsepositivesFN—falsenegatives6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘True：判斷結果，正確False：判斷結果，失誤Positives：真實屬性，屬于Negatives：真實屬性，不屬于群智能算法優秀課件全文共97頁，當前為第53頁。智能優化計算轉移概率

ηij表示每個條件項的啟發式參數值（信息熵），τij(t)表示第i個屬性的第j個取值在t時刻的信息素。6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第54頁。智能優化計算信息素增加

R是當前規則中所有包含的條件項；信息素揮發

減少沒被選中的三元組的信息量。6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘群智能算法優秀課件全文共97頁，當前為第55頁。智能優化計算結果分析

診斷準確度比較

6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘數據庫蟻群優化算法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群智能算法優秀課件全文共97頁，當前為第56頁。智能優化計算結果分析

診斷規則數比較

6.5蟻群優化算法的應用

6.5.2醫學診斷的數據挖掘數據庫蟻群優化算法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群智能算法優秀課件全文共97頁，當前為第57頁。智能優化計算由JamesKenney（社會心理學博士）和RussEberhart（電子工程學博士，/~eberhart/）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

6.6粒子群算法的基本原理

6.6.1粒子群算法的提出群智能算法優秀課件全文共97頁，當前為第58頁。智能優化計算源于對鳥群捕食行為的研究，是基于迭代的方法簡單易于實現，需要調整的參數相對較少在函數優化、神經網絡訓練、工業系統優化和模糊系統控制等領域得到了廣泛的應用。6.6粒子群算法的基本原理

6.6.1粒子群算法的提出群智能算法優秀課件全文共97頁，當前為第59頁。智能優化計算鳥群：假設一個區域，所有的鳥都不知道食物的位置，但是它們知道當前位置離食物還有多遠。PSO算法

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

6.6.2粒子群算法的原理描述群智能算法優秀課件全文共97頁，當前為第60頁。智能優化計算PSO算法

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

6.6.2粒子群算法的原理描述群智能算法優秀課件全文共97頁，當前為第61頁。智能優化計算粒子速度和位置的更新

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

6.7.1基本粒子群算法描述群智能算法優秀課件全文共97頁，當前為第62頁。智能優化計算粒子速度和位置的更新

其中，w稱為慣性權重，

c1和c2為兩個正常數，稱為加速因子。將vidk限制在一個最大速度vmax內。6.7基本粒子群優化算法

6.7.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+1群智能算法優秀課件全文共97頁，當前為第63頁。智能優化計算粒子速度和位置的更新

6.7基本粒子群優化算法

6.7.1基本粒子群算法描述“慣性部分”，對自身運動狀態的信任“認知部分”，對微粒本身的思考，即來源于自己經驗的部分“社會部分”，微粒間的信息共享，來源于群體中的其它優秀微粒的經驗群智能算法優秀課件全文共97頁，當前為第64頁。智能優化計算迭代過程

6.7基本粒子群優化算法

6.7.1基本粒子群算法描述群智能算法優秀課件全文共97頁，當前為第65頁。智能優化計算算法流程

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

6.7.1基本粒子群算法描述群智能算法優秀課件全文共97頁，當前為第66頁。智能優化計算慣性權重w

使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區域。表示微粒對當前自身運動狀態的信任，依據自身的速度進行慣性運動。較大的w有利于跳出局部極值，而較小的w有利于算法收斂。6.7基本粒子群優化算法

6.7.2參數分析群智能算法優秀課件全文共97頁，當前為第67頁。智能優化計算加速常數c1和c2

代表將微粒推向pbest和gbest位置的統計加速項的權重。表示粒子的動作來源于自己經驗的部分和其它粒子經驗的部分。低的值允許粒子在被拉回之前可以在目標區域外徘徊，而高的值則導致粒子突然沖向或越過目標區域。

6.7基本粒子群優化算法

6.7.2參數分析群智能算法優秀課件全文共97頁，當前為第68頁。智能優化計算加速常數c1和c2

將c1和c2統一為一個控制參數，φ=c1+c2

如果φ很小，微粒群運動軌跡將非常緩慢；如果φ很大，則微粒位置變化非常快；實驗表明，當φ=4.1（通常c1=2.0，c2=2.0）時，具有很好的收斂效果。6.7基本粒子群優化算法

6.7.2參數分析群智能算法優秀課件全文共97頁，當前為第69頁。智能優化計算粒子數

一般取20～40，對較難或特定類別的問題可以取100～200。最大速度vmax

決定粒子在一個循環中最大的移動距離，通常設定為粒子的范圍寬度。終止條件

最大循環數以及最小錯誤要求。6.7基本粒子群優化算法

6.7.2參數分析群智能算法優秀課件全文共97頁，當前為第70頁。智能優化計算共性

（1）都屬于仿生算法；（2）都屬于全局優化方法；（3）都屬于隨機搜索算法；（4）都隱含并行性；（5）根據個體的適配信息進行搜索，因此不受函數約束條件的限制，如連續性、可導性等；（6）對高維復雜問題，往往會遇到早熟收斂和收斂性能差的缺點，都無法保證收斂到最優點。6.7基本粒子群優化算法

6.7.3與遺傳算法的比較群智能算法優秀課件全文共97頁，當前為第71頁。智能優化計算差異

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

6.7.3與遺傳算法的比較群智能算法優秀課件全文共97頁，當前為第72頁。智能優化計算用途

基本PSO是用來解決連續問題優化的，離散二進制PSO用來解決組合優化問題。運動方程不同

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

6.8.1離散二進制PSO群智能算法優秀課件全文共97頁，當前為第73頁。智能優化計算思路

在考慮實際優化問題時，往往希望先采用全局搜索，使搜索空間快速收斂于某一區域，然后采用局部精細搜索以獲得高精度的解。研究發現，較大的w值有利于跳出局部極小點，而較小的w值有利于算法收斂，因此提出了自適應調整的策略，即隨著迭代的進行，線性地減小w的值。6.8改進粒子群優化算法

6.8.2慣性權重模型群智能算法優秀課件全文共97頁，當前為第74頁。智能優化計算變化的慣性權重

wmax、wmin分別是w的最大值和最小值；iter、itermax分別是當前迭代次數和最大迭代次數。6.8改進粒子群優化算法

6.8.2慣性權重模型群智能算法優秀課件全文共97頁，當前為第75頁。智能優化計算提出

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

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

通常將φ設為4.1，經計算k為0.729。6.8改進粒子群優化算法

6.8.3收斂因子模型群智能算法優秀課件全文共97頁，當前為第76頁。智能優化計算主要研究方向主要集中于對算法結構和性能的改善方面，包括：參數設置、粒子多樣性、種群結構和算法的融合。發展方向

目前大部分成果都是通過大量試驗獲得的，缺少對算法機理的研究，對PSO中的參數分析沒有實質性的認識，還處于試驗分析階段。6.8改進粒子群優化算法

6.8.4研究現狀群智能算法優秀課件全文共97頁，當前為第77頁。智能優化計算交換子和交換序設n個節點的TSP問題的解序列為s=(ai)，i=1…n。定義交換子SO(i1,i2)為交換解S中的點ai1和ai2，則S’=S+SO(i1,i2)為解S經算子SO(i1,i2)操作后的新解。一個或多個交換子的有序隊列就是交換序，記作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON等是交換子，之間的順序是有意義的,意味著所有的交換子依次作用于某解上。6.9粒子群優化算法的應用

6.9.1求解TSP問題群智能算法優秀課件全文共97頁，當前為第78頁。智能優化計算6.9粒子群優化算法的應用

6.9.1求解TSP問題符號的定義若干個交換序可以合并成一個新的交換序，定義為兩個交換序的合并算子。設兩個交換序SS1和SS2按先后順序作用于解S上，得到新解S’。假設另外有一個交換序SS’作用于同一解S上，能夠得到形同的解S’，可定義群智能算法優秀課件全文共97頁，當前為第79頁。智能優化計算6.9粒子群優化算法的應用

6.9.1求解TSP問題符號的定義和屬于同一等價集，在交換序等價集中，擁有最少交換子的交換序稱為該等價集的基本交換序。群智能算法優秀課件全文共97頁，當前為第80頁。智能優化計算解決TSP問題的速度算式定義

α、β為[0,1]上的隨機數。

vid表示交換序，xid表示路徑序列（解）。6.9粒子群優化算法的應用

6.9.1求解TSP問題群智能算法優秀課件全文共97頁，當前為第81頁。智能優化計算算法流程1.初始化粒子群，給每個粒子一個初始解(xid)和隨機的交換序(vid);2.如果滿足結束條件，轉步驟5;3.根據粒子當前位置xid計算下一新解xid’;4.如果整個群體找到一個更好的解，更新Pgd，轉步驟2;5.顯示結果。6.9粒子群優化算法的應用

6.9.1求解TSP問題群智能算法優秀課件全文共97頁，當前為第82頁。智能優化計算6.9粒子群優化算法的應用

6.9.1求解TSP問題算法流程3.根據粒子當前位置xid計算下一新解xid’:1）計算A=pid-xid，A是一個基本交換序，表示A作用于xid得到pid；2）計算B=pgd-xid，B也是一個基本交換序；3）更新速度，并將其轉換為一個基本交換序；4）更新解；5）如果找到一個更好得解，更新pid。群智能算法優秀課件全文共97頁，當前為第83頁。智能優化計算運行結果

α=0.25

β=0.25迭代次數=200粒子數=806.9粒子群優化算法的應用

6.9.1求解TSP問題10城市TSP問題（d*=2.691）0.40.