第二章蟻群算法

第二章蟻群算法

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

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

特點(diǎn)

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

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

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

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

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

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

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

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

2.2.1蟻群算法的起源

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

智能優(yōu)化計(jì)算2.2.2蟻群算法的原理分析蟻巢食物2.2蟻群優(yōu)化算法原理

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

經(jīng)過18個(gè)時(shí)間單位時(shí)：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。2.2.2蟻群算法的原理分析蟻巢食物

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

智能優(yōu)化計(jì)算2.2.2蟻群算法的原理分析蟻巢食物假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。2.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算2.2.2蟻群算法的原理分析基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。2.2蟻群優(yōu)化算法原理

智能優(yōu)化計(jì)算2.2.2蟻群算法的原理分析TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為其中為城市1,2，…n的一個(gè)排列，。2.2.2蟻群算法與TSP問題2.2.2蟻群算法與TSP問題

TSP問題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1信息素值也稱信息素痕跡。2可見度，即先驗(yàn)值。信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素。2.2.2蟻群算法與TSP問題螞蟻向下一個(gè)目標(biāo)的運(yùn)動是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動，逐此往復(fù)，越來越接近最優(yōu)解。螞蟻在尋找過程中，或者找到一個(gè)解后，會評估該解或解的一部分的優(yōu)化程度，并把評價(jià)信息保存在相關(guān)連接的信息素中。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）初始的蟻群算法是基于圖的蟻群算法，graph-basedantsystem,簡稱為GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的.算法步驟如下：STEP0

對n個(gè)城市的TSP問題，城市間的距離矩陣為，給TSP圖中的每一條弧賦信息素初值，假設(shè)m只螞蟻在工作，所有螞蟻都從同一城市出發(fā)。當(dāng)前最好解是 。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）STEP1

（外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻s從起點(diǎn)出發(fā)，用表示螞蟻s行走的城市集合，初始為空集，。STEP2(內(nèi)循環(huán))按螞蟻的順序分別計(jì)算。當(dāng)螞蟻在城市i，若 完成第s只螞蟻的計(jì)算。否則，若，則以概率 ， 到達(dá)j， ；若則到達(dá) 重復(fù)STEP2。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）STRP3

對 ，若，按中城市的順序計(jì)算路徑程度；若，路徑長度置為一個(gè)無窮大值（即不可達(dá)）。比較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若，則。用如下公式對W路徑上的信息素痕跡加強(qiáng)，對其他路徑上的信息素進(jìn)行揮發(fā)。得到新的，重復(fù)步驟STEP1。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）在STEP3

中，揮發(fā)因子對于一個(gè)固定的，滿足并且

經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉(zhuǎn)移。算法中包括信息素更新的過程

1信息素?fù)]發(fā)（evaporation）信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動逐漸減弱的過程，由表示，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。

2信息素增強(qiáng)（reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的信息素更新稱為離線的信息素更新。在STEP3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。圖的蟻群系統(tǒng)（GBAS）可以驗(yàn)證，下式滿足：即是一個(gè)隨機(jī)矩陣。四個(gè)城市的非對稱TSP問題，距離矩陣和城市圖示如下：2023/2/2222.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）假設(shè)共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子。此時(shí)，觀察GBAS的計(jì)算過程。矩陣共有12條弧，初始信息素記憶矩陣為：2023/2/2232.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）執(zhí)行GBAS算法的步驟2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）重復(fù)外循環(huán)，由于W2全局最優(yōu)解，GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：2.2.3初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息素的更新在STEP3完成，并隨K而變化。假設(shè)第K次外循環(huán)后得到信息素矩陣，得到當(dāng)前最優(yōu)解。第K次循環(huán)前的信息素和最優(yōu)解為，經(jīng)過第K次外循環(huán)后，得到。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從到也是隨機(jī)的，是一個(gè)馬爾可夫過程。2.2.3一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個(gè)組成部分：蟻群的活動；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉(zhuǎn)移概率公式和信息素更新公式。2.3基本蟻群優(yōu)化算法

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

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

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

設(shè)各路徑上的信息素τij(0)=C（C為一較小的常數(shù)）;2.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)2.3基本蟻群優(yōu)化算法

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

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

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

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

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

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

智能優(yōu)化計(jì)算算法流程2.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)2.3基本蟻群優(yōu)化算法

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

螞蟻數(shù)30；

α=1;

β=5;

ρ=0.1;

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

Q=1;2.3.1螞蟻系統(tǒng)的模型與實(shí)現(xiàn)2.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算%%清空環(huán)境變量clearallclc

%%導(dǎo)入數(shù)據(jù)loadcitys_data.mat%%計(jì)算城市間相互距離n=size(citys,1);D=zeros(n,n);fori=1:nforj=1:nifi~=jD(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));elseD(i,j)=1e-4;endendend

程序分析2.3基本蟻群優(yōu)化算法

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

%%初始化參數(shù)m=30;%螞蟻數(shù)量alpha=1;%信息素重要程度因子beta=5;%啟發(fā)函數(shù)重要程度因子rho=0.1;%信息素?fù)]發(fā)因子Q=1;%常系數(shù)Eta=1./D;%啟發(fā)函數(shù)Tau=ones(n,n);%信息素矩陣Table=zeros(m,n);%路徑記錄表iter=1;%迭代次數(shù)初值iter_max=200;%最大迭代次數(shù)Route_best=zeros(iter_max,n);%各代最佳路徑Length_best=zeros(iter_max,1);%各代最佳路徑的長度Length_ave=zeros(iter_max,1);%各代路徑的平均長度2.3基本蟻群優(yōu)化算法

智能優(yōu)化計(jì)算%%迭代尋找最佳路徑whileiter<=iter_max

%隨機(jī)產(chǎn)生各個(gè)螞蟻的起點(diǎn)城市start=zeros(m,1);fori=1:mtemp=randperm(n);start(i)=temp(1);endTable(:,1)=start;

%構(gòu)建解空間citys_index=1:n;

%在iter循環(huán)中還有以下三個(gè)重要步驟：%1、逐個(gè)螞蟻路徑選擇%2、計(jì)算各個(gè)螞蟻路徑距離及最短距離%3、更新信息素end2.3基本蟻群優(yōu)化算法

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

%逐個(gè)螞蟻路徑選擇fori=1:m

%逐個(gè)城市路徑選擇forj=2:ntabu=Table(i,1:(j-1));%已訪問的城市集合(禁忌表)allow_index=~ismember(citys_index,tabu);allow=citys_index(allow_index);%待訪問的城市集合P=allow;

%計(jì)算城市間轉(zhuǎn)移概率fork=1:length(allow)P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;endP=P/sum(P);

%輪盤賭法選擇下一個(gè)訪問城市Pc=cumsum(P);target_index=find(Pc>=rand);target=allow(target_index(1));Table(i,j)=target;endend2.3基本蟻群優(yōu)化算法

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

%計(jì)算各個(gè)螞蟻的路徑距離Length=zeros(m,1);fori=1:mRoute=Table(i,:);forj=1:(n-1)Length(i)=Length(i)+D(Route(j),Route(j+1));endLength(i)=Length(i)+D(Route(n),Route(1));end2.3基本蟻群優(yōu)化算法

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

%計(jì)算最短路徑距離及平均距離ifiter==1[min_Length,min_index]=min(Length);Length_best(iter)=min_Length;Length_ave(iter)=mean(Length);Route_best(iter,:)=Table(min_index,:);else[min_Length,min_index]=min(Length);Length_best(iter)=min(Length_best(iter-1),min_Length);Length_ave(iter)=mean(Length);ifLength_best(iter)==min_LengthRoute_best(iter,:)=Table(min_index,:);elseRoute_best(iter,:)=Route_best((iter-1),:);endend2.3基本蟻群優(yōu)化算法

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

%更新信息素Delta_Tau=zeros(n,n);

%逐個(gè)螞蟻計(jì)算fori=1:m

%逐個(gè)城市計(jì)算forj=1:(n-1)Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);endDelta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,n),Table(i,1))+Q/Length(i);endTau=(1-rho)*Tau+Delta_Tau;2.3基本蟻群優(yōu)化算法

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

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

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

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

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

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

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

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

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

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

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

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

ant-cycle：（蟻周）

ant-quantity：（蟻量）

ant-density:

（蟻密）

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

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

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

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

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

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

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

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

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

2.3基本蟻群優(yōu)化算法2.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)一分布的差別不大。

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

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

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

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

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

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

上的信息素將會適當(dāng)減少，從而實(shí)現(xiàn)一種信息素的局部調(diào)整以減少已選擇過的路徑再次被選擇的概率。2.4改進(jìn)的蟻群優(yōu)化算法2.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算可行解的構(gòu)造

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

q為0～1的隨機(jī)數(shù)，S為一隨機(jī)變量，當(dāng)q>q0時(shí)，S以以下概率來選擇：2.4改進(jìn)的蟻群優(yōu)化算法2.4.3蟻群系統(tǒng)智能優(yōu)化計(jì)算局部信息素更新

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

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

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

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

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

，在算法初始時(shí)刻，ρ取較小值時(shí)算法有更好的發(fā)現(xiàn)較好解的能力。2.4改進(jìn)的蟻群優(yōu)化算法2.4.4最大－最小螞蟻系統(tǒng)智能優(yōu)化計(jì)算信息素的全局更新

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

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

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

信息素更新：2.4改進(jìn)的蟻群優(yōu)化算法2.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計(jì)算優(yōu)化結(jié)果比較

對對稱TSP各迭代10000次，對非對稱TSP各迭代20000次：2.4改進(jìn)的蟻群優(yōu)化算法2.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)用列表

2.5蟻群優(yōu)化算法的應(yīng)用2.5.1典型應(yīng)用智能優(yōu)化計(jì)算如何應(yīng)用

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

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

IF<term1ANDterm2AND…>THEN<class>

每個(gè)term是一個(gè)三元組（屬性、關(guān)系符、屬性取值）希望在一個(gè)規(guī)則中使用最少的判別語句，采用蟻群優(yōu)化算法達(dá)到最優(yōu)的選擇。2.5蟻群優(yōu)化算法的應(yīng)用2.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘智能優(yōu)化計(jì)算例：非典型肺炎考慮如下因素：

2.5蟻群優(yōu)化算法的應(yīng)用2.5.2醫(yī)學(xué)診斷的數(shù)據(jù)挖掘?qū)傩园l(fā)熱職業(yè)胸部陰影流行病學(xué)史值（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：醫(yī)務(wù)人員2：其他人員0：不考慮該屬性1：無2：有0：不考慮該屬性1：無2：有智能優(yōu)化計(jì)算例：非典型肺炎結(jié)構(gòu)圖：

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

IF（職業(yè)＝其他人員）