第六章群智能算法

智能優(yōu)化計算第六章群智能算法智能優(yōu)化計算16.1群智能6.2蟻群優(yōu)化算法原理

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

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

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

6.6粒子群算法的基本原理

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

6.8改進粒子群優(yōu)化算法

6.9粒子群優(yōu)化算法的應(yīng)用6.10群智能算法的特點與不足智能優(yōu)化計算6.1群智能智能優(yōu)化計算26.1群智能

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

特點

個體的行為很簡單，但當(dāng)它們一起協(xié)同工作時，卻能夠突現(xiàn)出非常復(fù)雜（智能）的行為特征。6.1.1群智能的概念6.1群智能智能優(yōu)化計算群智能（SwarmInte36.1群智能

智能優(yōu)化計算描述

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

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

穩(wěn)健性：即使個體失敗，整個群體仍能完成任務(wù)；自我組織：活動既不受中央控制，也不受局部監(jiān)管。典型算法

蟻群算法（螞蟻覓食）

粒子群算法（鳥群捕食）6.1.2群智能算法6.1群智能智能優(yōu)化計算優(yōu)點6.1.2群智56.2蟻群優(yōu)化算法原理

智能優(yōu)化計算蟻群的自組織行為“雙橋?qū)嶒灐蓖ㄟ^遺留在來往路徑上的信息素（Pheromone）的揮發(fā)性化學(xué)物質(zhì)來進行通信和協(xié)調(diào)。6.2.1蟻群算法的起源6.2蟻群優(yōu)化算法原理智能優(yōu)化計算蟻群的自組織行為66.2蟻群優(yōu)化算法原理

智能優(yōu)化計算蟻群的自組織行為“雙橋?qū)嶒灐?.2.1蟻群算法的起源6.2蟻群優(yōu)化算法原理智能優(yōu)化計算蟻群的自組織行為76.2蟻群優(yōu)化算法原理

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

6.2.1蟻群算法的起源6.2蟻群優(yōu)化算法原理智能優(yōu)化計算提出蟻群系統(tǒng)8螞蟻從A點出發(fā)，隨機選擇路線ABD或ACD。經(jīng)過9個時間單位時：走ABD的螞蟻到達終點，走ACD的螞蟻剛好走到C點。6.2蟻群優(yōu)化算法原理

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

智能優(yōu)化計算經(jīng)過18個時間單位時：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。6.2.2蟻群算法的原理分析蟻巢食物6.2蟻群優(yōu)化算法原理智能優(yōu)化計算6.2.210

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

智能優(yōu)化計算6.2.2蟻群算法的原理分析蟻巢食物6.2蟻群優(yōu)化算法原理智能優(yōu)化計算6.2.2116.3基本蟻群優(yōu)化算法

智能優(yōu)化計算解決TSP問題

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

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

設(shè)各路徑上的信息素τij(0)=C（C為一較小的常數(shù)）;6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算解決TSP問題126.3基本蟻群優(yōu)化算法

智能優(yōu)化計算解決TSP問題

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

α、β分別表示信息素和啟發(fā)式因子的相對重要程度。6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)下一步允許的城市的集合6.3基本蟻群優(yōu)化算法智能優(yōu)化計算解決TSP問題136.3基本蟻群優(yōu)化算法

智能優(yōu)化計算解決TSP問題

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算解決TSP問題146.3基本蟻群優(yōu)化算法

智能優(yōu)化計算算法流程6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算算法流程6.156.3基本蟻群優(yōu)化算法

智能優(yōu)化計算初始參數(shù)城市數(shù)30;螞蟻數(shù)30；

α=1;

β=5;

ρ=0.5;最大迭代代數(shù)200;

Q=100;6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算初始參數(shù)6.166.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.176.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.186.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.196.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.206.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.216.3基本蟻群優(yōu)化算法

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

6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)6.3基本蟻群優(yōu)化算法智能優(yōu)化計算運行結(jié)果6.22智能優(yōu)化計算三種模型

ant-cycle：（蟻周）

ant-quantity：（蟻量）

ant-density:（蟻密）

6.3基本蟻群優(yōu)化算法6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)智能優(yōu)化計算三種模型6.3基本蟻群優(yōu)化算法6.23智能優(yōu)化計算三種模型在Ant-density和Ant-quantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素（局部信息），而在Ant-cycle中當(dāng)所有的螞蟻都完成了自己的行程后（全局信息）才對信息素進行更新。6.3基本蟻群優(yōu)化算法6.3.1螞蟻系統(tǒng)的模型與實現(xiàn)智能優(yōu)化計算三種模型6.3基本蟻群優(yōu)化算法6.24智能優(yōu)化計算三種模型的比較模型ant-density,ant-quantity,ant-cycle的比較(M.Dorigo,1996)6.3基本蟻群優(yōu)化算法6.3.1螞蟻系統(tǒng)的模型與實現(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)化計算三種模型的比較6.3基本蟻群優(yōu)化算法25智能優(yōu)化計算信息素的分布

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

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

6.3基本蟻群優(yōu)化算法6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性ρ＝0.05ρ＝0.95智能優(yōu)化計算信息素的分布6.3基本蟻群優(yōu)化算法27智能優(yōu)化計算參數(shù)α、β對算法性能的影響

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

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

α取較大值時，意味著在選擇路徑時，路徑上的信息素非常重要；當(dāng)α取較小值時，變成隨機的貪婪算法。6.3基本蟻群優(yōu)化算法6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計算參數(shù)α、β對算法性能的影響6.3基本蟻群優(yōu)29智能優(yōu)化計算參數(shù)α、β對算法性能的影響

α＝0，螞蟻之間無協(xié)同作用；α＝1，有協(xié)同作用6.3基本蟻群優(yōu)化算法6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性α＝0α＝1智能優(yōu)化計算參數(shù)α、β對算法性能的影響6.3基本蟻群優(yōu)30智能優(yōu)化計算螞蟻數(shù)m對算法的影響

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

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

兩種情況實驗：（1）所有螞蟻初始時刻放在同一城市；（2）螞蟻分布在不同城市中。第（2）中情況可獲得較高性能。

6.3基本蟻群優(yōu)化算法6.3.2螞蟻系統(tǒng)的參數(shù)設(shè)置和基本屬性智能優(yōu)化計算螞蟻的初始分布6.3基本蟻群優(yōu)化算法32智能優(yōu)化計算優(yōu)點

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

搜索時間較長；容易出現(xiàn)停滯現(xiàn)象。6.4改進的蟻群優(yōu)化算法6.4.1螞蟻系統(tǒng)的優(yōu)點與不足智能優(yōu)化計算優(yōu)點6.4改進的蟻群優(yōu)化算法6.433智能優(yōu)化計算最優(yōu)解保留策略（AntSystemwithElitist,ASelite）

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

σ為最優(yōu)螞蟻數(shù)，Lgb為全局最優(yōu)解。6.4改進的蟻群優(yōu)化算法6.4.2最優(yōu)解保留策略螞蟻系統(tǒng)智能優(yōu)化計算最優(yōu)解保留策略（AntSystemwith34智能優(yōu)化計算最優(yōu)解保留策略（AntSystemwithElitist,ASelite）

該策略能夠以更快的速度獲得最好解，但是如果選擇的精英過多則算法會由于較早收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。6.4改進的蟻群優(yōu)化算法6.4.2最優(yōu)解保留策略螞蟻系統(tǒng)智能優(yōu)化計算最優(yōu)解保留策略（AntSystemwith35智能優(yōu)化計算蟻群系統(tǒng)（AntColonySystem,ACS）的改進之處

（1）在選擇下一城市時，更多地利用了當(dāng)前最好解；（2）只在全局最優(yōu)解所屬邊上增加信息素；（3）每次螞蟻從城市i轉(zhuǎn)移到城市j時，邊ij上的信息素將會適當(dāng)減少，從而實現(xiàn)一種信息素的局部調(diào)整以減少已選擇過的路徑再次被選擇的概率。6.4改進的蟻群優(yōu)化算法6.4.3蟻群系統(tǒng)智能優(yōu)化計算蟻群系統(tǒng)（AntColonySystem,36智能優(yōu)化計算可行解的構(gòu)造

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

q為0～1的隨機數(shù)，S為一隨機變量，當(dāng)q>q0時，S以以下概率來選擇：6.4改進的蟻群優(yōu)化算法6.4.3蟻群系統(tǒng)智能優(yōu)化計算可行解的構(gòu)造6.4改進的蟻群優(yōu)化算法37智能優(yōu)化計算局部信息素更新

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

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

6.4改進的蟻群優(yōu)化算法6.4.3蟻群系統(tǒng)智能優(yōu)化計算全局信息素更新6.4改進的蟻群優(yōu)化算法39智能優(yōu)化計算最大－最小螞蟻系統(tǒng)（max-minantsystem,MMAS）的改進之處

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

,τmax]；（3）初始時刻，各路徑上信息素設(shè)置為τmax，在算法初始時刻，ρ取較小值時算法有更好的發(fā)現(xiàn)較好解的能力。6.4改進的蟻群優(yōu)化算法6.4.4最大－最小螞蟻系統(tǒng)智能優(yōu)化計算最大－最小螞蟻系統(tǒng)（max-minantsy40智能優(yōu)化計算信息素的全局更新

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

6.4改進的蟻群優(yōu)化算法6.4.4最大－最小螞蟻系統(tǒng)智能優(yōu)化計算信息素的全局更新6.4改進的蟻群優(yōu)化算法41智能優(yōu)化計算基于排序的螞蟻系統(tǒng)（rank-basedversionofantsystem,ASrank）

每次迭代完成后，螞蟻所經(jīng)路徑按從小到大的順序排列，并對它們賦予不同權(quán)值，路徑越短權(quán)值越大。全局最優(yōu)解權(quán)值為w，第r個最優(yōu)解的權(quán)值為max{0,w-r}。6.4改進的蟻群優(yōu)化算法6.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計算基于排序的螞蟻系統(tǒng)（rank-basedver42智能優(yōu)化計算基于排序的螞蟻系統(tǒng)（rank-basedversionofantsystem,ASrank）

信息素更新：6.4改進的蟻群優(yōu)化算法6.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計算基于排序的螞蟻系統(tǒng)（rank-basedver43智能優(yōu)化計算典型應(yīng)用列表

6.5蟻群優(yōu)化算法的應(yīng)用6.5.1典型應(yīng)用智能優(yōu)化計算典型應(yīng)用列表6.5蟻群優(yōu)化算44智能優(yōu)化計算由JamesKenney（社會心理學(xué)博士）和RussEberhart（電子工程學(xué)博士，/~eberhart/）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

6.6粒子群算法的基本原理6.6.1粒子群算法的提出智能優(yōu)化計算由JamesKenney（社會心理學(xué)博士）和R45智能優(yōu)化計算源于對鳥群捕食行為的研究，是基于迭代的方法簡單易于實現(xiàn)，需要調(diào)整的參數(shù)相對較少在函數(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)化計算源于對鳥群捕食行為的研究，是基于迭代的方法6.646智能優(yōu)化計算鳥群：假設(shè)一個區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當(dāng)前位置離食物還有多遠。PSO算法

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

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

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

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

c1和c2為兩個正常數(shù)，稱為加速因子。將vidk限制在一個最大速度vmax內(nèi)。6.7基本粒子群優(yōu)化算法6.7.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+1智能優(yōu)化計算粒子速度和位置的更新6.7基本粒子群優(yōu)化算法50智能優(yōu)化計算粒子速度和位置的更新

6.7基本粒子群優(yōu)化算法6.7.1基本粒子群算法描述“慣性部分”，對自身運動狀態(tài)的信任“認知部分”，對微粒本身的思考，即來源于自己經(jīng)驗的部分“社會部分”，微粒間的信息共享，來源于群體中的其它優(yōu)秀微粒的經(jīng)驗智能優(yōu)化計算粒子速度和位置的更新6.7基本粒子群優(yōu)化算法51智能優(yōu)化計算迭代過程

6.7基本粒子群優(yōu)化算法6.7.1基本粒子群算法描述智能優(yōu)化計算迭代過程6.7基本粒子群優(yōu)化算法6.52智能優(yōu)化計算算法流程

6.7基本粒子群優(yōu)化算法StartInitializeparticleswithrandompositionandvelocityvectors.Foreachparticle’sposition(xi)evaluatefitnessIffitness(xi)betterthanfitness(p)thenp=xiLoopuntilallparticlesexhaustSetbestofpsasgBestUpdateparticlesvelocityandpositionLoopuntilmaxiterStop:givinggBest,optimalsolution.6.7.1基本粒子群算法描述智能優(yōu)化計算算法流程6.7基本粒子群優(yōu)化算法StartI53智能優(yōu)化計算慣性權(quán)重w

使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。表示微粒對當(dāng)前自身運動狀態(tài)的信任，依據(jù)自身的速度進行慣性運動。較大的w有利于跳出局部極值，而較小的w有利于算法收斂。6.7基本粒子群優(yōu)化算法6.7.2參數(shù)分析智能優(yōu)化計算慣性權(quán)重w6.7基本粒子群優(yōu)化算法654智能優(yōu)化計算加速常數(shù)c1和c2

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

6.7基本粒子群優(yōu)化算法6.7.2參數(shù)分析智能優(yōu)化計算加速常數(shù)c1和c26.7基本粒子群優(yōu)化算法55智能優(yōu)化計算加速常數(shù)c1和c2

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

如果φ很小，微粒群運動軌跡將非常緩慢；如果φ很大，則微粒位置變化非常快；實驗表明，當(dāng)φ=4.1（通常c1=2.0，c2=2.0）時，具有很好的收斂效果。6.7基本粒子群優(yōu)化算法6.7.2參數(shù)分析智能優(yōu)化計算加速常數(shù)c1和c26.7基本粒子群優(yōu)化算法56智能優(yōu)化計算粒子數(shù)

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

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

最大循環(huán)數(shù)以及最小錯誤要求。6.7基本粒子群優(yōu)化算法6.7.2參數(shù)分析智能優(yōu)化計算粒子數(shù)6.7基本粒子群優(yōu)化算法6.757智能優(yōu)化計算共性

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

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

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

粒子的位置只有(0,1)兩種狀態(tài)。速度值越大，則粒子位置取1的可能性越大，反之越小。6.8改進粒子群優(yōu)化算法6.8.1離散二進制PSO智能優(yōu)化計算用途6.8改進粒子群優(yōu)化算法6.8.60智能優(yōu)化計算思路

在考慮實際優(yōu)化問題時，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部精細搜索以獲得高精度的解。研究發(fā)現(xiàn)，較大的w值有利于跳出局部極小點，而較小的w值有利于算法收斂，因此提出了自適應(yīng)調(diào)整的策略，即隨著迭代的進行，線性地減小w的值。6.8改進粒子群優(yōu)化算法6.8.2慣性權(quán)重模型智能優(yōu)化計算思路6.8改進粒子群優(yōu)化算法6.8.61智能優(yōu)化計算變化的慣性權(quán)重

wmax、wmin分別是w的最大值和最小值；iter、itermax分別是當(dāng)前迭代次數(shù)和最大迭代次數(shù)。6.8改進粒子群優(yōu)化算法6.8.2慣性權(quán)重模型智能優(yōu)化計算變化的慣性權(quán)重6.8改進粒子群優(yōu)化算法62智能優(yōu)化計算提出

1999年Clerc對算法的研究證明，采用收斂因子能夠確保算法的收斂。收斂因子模型

通常將φ設(shè)為4.1，經(jīng)計算k為0.729。6.8改進粒子群優(yōu)化算法6.8.3收斂因子模型智能優(yōu)化計算提出6.8改進粒子群優(yōu)化算法6.63智能優(yōu)化計算主要研究方向主要集中于對算法結(jié)構(gòu)和性能的改善方面，包括：參數(shù)設(shè)置、粒子多樣性、種群結(jié)構(gòu)和算法的融合。發(fā)展方向

目前大部分成果都是通過大量試驗獲得的，缺少對算法機理的研究，對PSO中的參數(shù)分析沒有實質(zhì)性的認識，還處于試驗分析階段。6.8改進粒子群優(yōu)化算法6.8.4研究現(xiàn)狀智能優(yōu)化計算主要研究方向6.8改進粒子群優(yōu)化算法64智能優(yōu)化計算交換子和交換序設(shè)n個節(jié)點的TSP問題的解序列為s=(ai)，i=1…n。定義交換子SO(i1,i2)為交換解S中的點ai1和ai2，則S’=S+SO(i1,i2)為解S經(jīng)算子SO(i1,i2)操作后的新解。一個或多個交換子的有序隊列就是交換序，記作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON等是交換子，之間的順序是有意義的,意味著所有的交換子依次作用于某解上。6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算交換子和交換序6.9粒子群優(yōu)化算法的應(yīng)用65智能優(yōu)化計算符號的定義若干個交換序可以合并成一個新的交換序，定義為兩個交換序的合并算子。設(shè)兩個交換序SS1和SS2按先后順序作用于解S上，得到新解S’。假設(shè)另外有一個交換序SS’作用于同一解S上，能夠得到形同的解S’，可定義6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算符號的定義6.9粒子群優(yōu)化算法的應(yīng)用66智能優(yōu)化計算符號的定義和屬于同一等價集，在交換序等價集中，擁有最少交換子的交換序稱為該等價集的基本交換序。6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算符號的定義6.9粒子群優(yōu)化算法的應(yīng)用67智能優(yōu)化計算解決TSP問題的速度算式定義

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

vid表示交換序，xid表示路徑序列（解）。6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算解決TSP問題的速度算式定義6.9粒子群68智能優(yōu)化計算算法流程1.初始化粒子群，給每個粒子一個初始解(xid)和隨機的交換序(vid);2.如果滿足結(jié)束條件，轉(zhuǎn)步驟5;3.根據(jù)粒子當(dāng)前位置xid計算下一新解xid’;4.如果整個群體找到一個更好的解，更新Pgd，轉(zhuǎn)步驟2;5.顯示結(jié)果。6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算算法流程6.9粒子群優(yōu)化算法的應(yīng)用69智能優(yōu)化計算算法流程3.根據(jù)粒子當(dāng)前位置xid計算下一新解xid’:1）計算A=pid-xid，A是一個基本交換序，表示A作用于xid得到pid；2）計算B=pgd-xid，B也是一個基本交換序；3）更新速度，并將其轉(zhuǎn)換為一個基本交換序；4）更新解；5）如果找到一個更好得解，更新pid。6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算算法流程6.9粒子群優(yōu)化算法的應(yīng)用70智能優(yōu)化計算運行結(jié)果

α=0.25

β=0.25迭代次數(shù)=200粒子數(shù)=806.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題10城市TSP問題（d*=2.691）0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634智能優(yōu)化計算運行結(jié)果6.9粒子群優(yōu)化算法的應(yīng)用71智能優(yōu)化計算運行結(jié)果

6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算運行結(jié)果6.9粒子群優(yōu)化算法的應(yīng)用72智能優(yōu)化計算運行結(jié)果

6.9粒子群優(yōu)化算法的應(yīng)用6.9.1求解TSP問題智能優(yōu)化計算運行結(jié)果6.9粒子群優(yōu)化算法的應(yīng)用73智能優(yōu)化計算運行結(jié)果

6.9粒子群優(yōu)化算法的應(yīng)用