第二章蟻群算法

第二章蟻群算法

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

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

特點

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

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

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

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

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

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

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

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

2.2.1蟻群算法的起源

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

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

智能優(yōu)化計算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

螞蟻數(shù)30；

α=1;

β=5;

ρ=0.1;

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

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

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

%%導入數(shù)據(jù)loadcitys_data.mat%%計算城市間相互距離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)化計算

%%初始化參數(shù)m=30;%螞蟻數(shù)量alpha=1;%信息素重要程度因子beta=5;%啟發(fā)函數(shù)重要程度因子rho=0.1;%信息素揮發(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)化計算%%迭代尋找最佳路徑whileiter<=iter_max

%隨機產(chǎ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)中還有以下三個重要步驟：%1、逐個螞蟻路徑選擇%2、計算各個螞蟻路徑距離及最短距離%3、更新信息素end2.3基本蟻群優(yōu)化算法

智能優(yōu)化計算

%逐個螞蟻路徑選擇fori=1:m

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

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

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

智能優(yōu)化計算

%計算各個螞蟻的路徑距離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)化計算

%計算最短路徑距離及平均距離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)化計算

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

%逐個螞蟻計算fori=1:m

%逐個城市計算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)化計算運行結(jié)果

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

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

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

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

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

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

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

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

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

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

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

ant-cycle：（蟻周）

ant-quantity：（蟻量）

ant-density:

（蟻密）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4改進的蟻群優(yōu)化算法2.4.4最大－最小螞蟻系統(tǒng)智能優(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}。2.4改進的蟻群優(yōu)化算法2.4.5基于排序的螞蟻系統(tǒng)智能優(yōu)化計算基于排序的螞蟻系統(tǒng)（rank-basedversionofantsystem,ASrank）

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

對對稱TSP各迭代10000次，對非對稱TSP各迭代20000次：2.4改進的蟻群優(yōu)化算法2.4.6各種蟻群優(yōu)化算法的比較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智能優(yōu)化計算典型應用列表

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

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

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

IF<term1ANDterm2AND…>THEN<class>

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

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

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

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