蟻周演算法問題

❶ 蟻群演算法求解TSP問題遇到「索引超出矩陣維度。」的問題跪求大神能解答

你檢查一下坐標矩陣是否出現了重復數值。比如你給的例子中C矩陣的第二個和第三個數值就重復了。

❷ 蟻群演算法求解TSP問題的源程序及簡要說明

簡單蟻群演算法求解TSP的源程序(我幫你找的)

蟻群演算法是新興的仿生演算法，最初是由義大利學者Dorigo M於1991年首次提出，由於具有較強的魯棒性，優良的分布式計算機制和易於與其它方法結合等優點，成為人工智慧領域的一個研究熱點。本程序是實現簡單的蟻群演算法，TSP問題取的是att48，可從http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95獲取，程序運行時間可能會比較長，在我的這台CPU 1.6G+內存256M的機器上運行時間大概是13分鍾左右。我用的語言是MATLAB 7.1。此程序僅供學習所用，如有問題請反饋。謝謝。（註：程序沒有計算最後一個城市回來起點城市的距離）

function [y,val]=QACS
tic
load att48 att48;
MAXIT=300; % 最大循環次數
NC=48; % 城市個數
tao=ones(48,48);% 初始時刻各邊上的信息最為1
rho=0.2; % 揮發系數
alpha=1;
beta=2;
Q=100;
mant=20; % 螞蟻數量
iter=0; % 記錄迭代次數
for i=1:NC % 計算各城市間的距離
for j=1:NC
distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);
end
end
bestroute=zeros(1,48); % 用來記錄最優路徑
routelength=inf; % 用來記錄當前找到的最優路徑長度
% for i=1:mant % 確定各螞蟻初始的位置
% end
for ite=1:MAXIT
for ka=1:mant %考查第K只螞蟻
deltatao=zeros(48,48); % 第K只螞蟻移動前各邊上的信息增量為零
[routek,lengthk]=travel(distance,tao,alpha,beta);
if lengthk<routelength % 找到一條更好的路徑
routelength=lengthk;
bestroute=routek;
end
for i=1:NC-1 % 第K只螞蟻在路徑上釋放的信息量
deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;
end
deltatao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk;
end
for i=1:NC-1
for j=i+1:NC
if deltatao(i,j)==0
deltatao(i,j)=deltatao(j,i);
end
end
end
tao=(1-rho).*tao+deltatao;
end
y=bestroute;
val=routelength;
toc

function [y,val]=travel(distance,tao,alpha,beta) % 某隻螞蟻找到的某條路徑
[m,n]=size(distance);
p=fix(m*rand)+1;
val=0; % 初始路徑長度設為 0
tabuk=[p]; % 假設該螞蟻都是從第 p 個城市出發的
for i=1:m-1
np=tabuk(length(tabuk)); % 螞蟻當前所在的城市號
p_sum=0;
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
p_sum=p_sum+tao(np,j)^alpha*ada^beta;
end
end
cp=zeros(1,m); % 轉移概率
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
cp(j)=tao(np,j)^alpha*ada^beta/p_sum;
end
end
NextCity=pchoice(cp);
tabuk=[tabuk,NextCity];
val=val+distance(np,NextCity);
end
y=tabuk;

function y=isin(x,A) % 判斷數 x 是否在向量 A 中，如在返回 1 ，否則返回 0
y=0;
for i=1:length(A)
if A(i)==x
y=1;
break;
end
end

function y=pchoice(A)
a=rand;
tempA=zeros(1,length(A)+1);
for i=1:length(A)
tempA(i+1)=tempA(i)+A(i);
end
for i=2:length(tempA)
if a<=tempA(i)
y=i-1;
break;
end
end

❸ 什麼是蟻群演算法

蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型技術。它由Marco Dorigo於1992年在他的博士論文中引入，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。
蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值.
蟻群演算法是一種求解組合最優化問題的新型通用啟發式方法，該方法具有正反饋、分布式計算和富於建設性的貪婪啟發式搜索的特點。通過建立適當的數學模型，基於故障過電流的配電網故障定位變為一種非線性全局尋優問題。由柳洪平創建。
預期的結果：
各個螞蟻在沒有事先告訴他們食物在什麼地方的前提下開始尋找食物。當一隻找到食物以後，它會向環境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物！有些螞蟻並沒有象其它螞蟻一樣總重復同樣的路，他們會另闢蹊徑，如果令開辟的道路比原來的其他道路更短，那麼，漸漸，更多的螞蟻被吸引到這條較短的路上來。最後，經過一段時間運行，可能會出現一條最短的路徑被大多數螞蟻重復著。
原理：
為什麼小小的螞蟻能夠找到食物？他們具有智能么？設想，如果我們要為螞蟻設計一個人工智慧的程序，那麼這個程序要多麼復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那麼需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程序。
然而，事實並沒有你想得那麼復雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什麼這么簡單的程序會讓螞蟻干這樣復雜的事情？答案是：簡單規則的涌現。事實上，每隻螞蟻並不是像我們想像的需要知道整個世界的信息，他們其實只關心很小范圍內的眼前信息，而且根據這些局部信息利用幾條簡單的規則進行決策，這樣，在蟻群這個集體里，復雜性的行為就會凸現出來。這就是人工生命、復雜性科學解釋的規律！那麼，這些簡單規則是什麼呢？下面詳細說明：
1、范圍：
螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是3*3個方格世界，並且能移動的距離也在這個范圍之內。
2、環境：
螞蟻所在的環境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環境信息。環境以一定的速率讓信息素消失。
3、覓食規則：
在每隻螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，並且比較在能感知的范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，並且每隻螞蟻多會以小概率犯錯誤，從而並不是往信息素最多的點移動。螞蟻找窩的規則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。
4、移動規則：
每隻螞蟻都朝向信息素最多的方向移，並且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，並且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發現要走的下一點已經在最近走過了，它就會盡量避開。
5、避障規則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，並且有信息素指引的話，它會按照覓食的規則行為。
7、播撒信息素規則：
每隻螞蟻在剛找到食物或者窩的時候撒發的信息素最多，並隨著它走遠的距離，播撒的信息素越來越少。
根據這幾條規則，螞蟻之間並沒有直接的關系，但是每隻螞蟻都和環境發生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯起來了。比如，當一隻螞蟻找到了食物，它並沒有直接告訴其它螞蟻這兒有食物，而是向環境播撒信息素，當其它的螞蟻經過它附近的時候，就會感覺到信息素的存在，進而根據信息素的指引找到了食物。
問題：
說了這么多，螞蟻究竟是怎麼找到食物的呢？
在沒有螞蟻找到食物的時候，環境沒有有用的信息素，那麼螞蟻為什麼會相對有效的找到食物呢？這要歸功於螞蟻的移動規則，尤其是在沒有信息素時候的移動規則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個前方是隨機固定的一個方向），而不是原地無謂的打轉或者震動；其次，螞蟻要有一定的隨機性，雖然有了固定的方向，但它也不能像粒子一樣直線運動下去，而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什麼單個螞蟻在復雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當然，在有一隻螞蟻找到了食物的時候，其他螞蟻會沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的？這一是要歸功於信息素，另外要歸功於環境，具體說是計算機時鍾。信息素多的地方顯然經過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數量同樣多（或者較長的路上螞蟻多，這也無關緊要）。當螞蟻沿著一條路到達終點以後會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復的頻率就快，因而在單位時間里走過的螞蟻數目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實際上螞蟻逐漸接近全局最短路的，為什麼呢？這源於螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另闢蹊徑，這可以理解為一種創新，這種創新如果能縮短路途，那麼根據剛才敘述的原理，更多的螞蟻會被吸引過來。
引申
跟著螞蟻的蹤跡，你找到了什麼？通過上面的原理敘述和實際操作，我們不難發現螞蟻之所以具有智能行為，完全歸功於它的簡單行為規則，而這些規則綜合起來具有下面兩個方面的特點：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環，正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現的創造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。
引申來講，大自然的進化，社會的進步、人類的創新實際上都離不開這兩樣東西，多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統過於活躍，這相當於螞蟻會過多的隨機運動，它就會陷入混沌狀態；而相反，多樣性不夠，正反饋機制過強，那麼系統就好比一潭死水。這在蟻群中來講就表現為，螞蟻的行為過於僵硬，當環境變化了，螞蟻群仍然不能適當的調整。
既然復雜性、智能行為是根據底層規則涌現的，既然底層規則具有多樣性和正反饋特點，那麼也許你會問這些規則是哪裡來的？多樣性和正反饋又是哪裡來的？我本人的意見：規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢？為什麼在你眼前呈現的世界是如此栩栩如生呢？答案在於環境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了，被環境淘汰了！
參數說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經存在於世界上的信息素會消減，這個數值越大，那麼消減的越快。
錯誤概率表示這個螞蟻不往信息素最大的區域走的概率，越大則表示這個螞蟻越有創新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉，停滯不前。而這個值越大那麼整個系統運行速度就慢，越小則螞蟻越容易原地轉圈。
蟻群演算法的實現
下面的程序開始運行之後，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。
其中，『F』點表示食物，『H』表示窩，白色塊表示障礙物，『+』就是螞蟻了。
參數說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經存在於世界上的信息素會消減，這個數值越大，那麼消減的越快。
錯誤概率表示這個螞蟻不往信息素最大的區域走的概率，越大則表示這個螞蟻越有創新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉，停滯不前。而這個值越大那麼整個系統運行速度就慢，越小則螞蟻越容易原地轉圈。

❹ 求帶注釋的蟻群演算法

Sorry，沒有注釋！
放不下，網站上有！

下面就是實現如此復雜性的七條簡單規則：
1、范圍：
螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是33個方格世界，並且能移動的距離也在這個范圍之內。
2、環境：
螞蟻所在的環境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環境信息。環境以一定的速率讓信息素消失。
3、覓食規則：
在每隻螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，並且比較在能感知的范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，並且每隻螞蟻多會以小概率犯錯誤，從而並不是往信息素最多的點移動。螞蟻找窩的規則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。
4、移動規則：
每隻螞蟻都朝向信息素最多的方向移，並且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，並且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發現要走的下一點已經在最近走過了，它就會盡量避開。
5、避障規則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，並且有信息素指引的話，它會按照覓食的規則行為。
7、播撒信息素規則：
每隻螞蟻在剛找到食物或者窩的時候撒發的信息素最多，並隨著它走遠的距離，播撒的信息素越來越少。

下面的程序開始運行之後，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。

其中，『F』點表示食物，『H』表示窩，白色塊表示障礙物，『+』就是螞蟻了。

參數說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經存在於世界上的信息素會消減，這個數值越大，那麼消減的越快。
錯誤概率表示這個螞蟻不往信息素最大的區域走的概率，越大則表示這個螞蟻越有創新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉，停滯不前。而這個值越大那麼整個系統運行速度就慢，越小則螞蟻越容易原地轉圈。

源代碼如下：

ant.c

#define SPACE 0×20
#define ESC 0×1b
#define ANT_CHAR_EMPTY 『+』
#define ANT_CHAR_FOOD 153
#define HOME_CHAR 『H』
#define FOOD_CHAR 『F』
#define FOOD_CHAR2 『f』
#define FOOD_HOME_COLOR 12
#define BLOCK_CHAR 177

#define MAX_ANT 50
#define INI_SPEED 3
#define MAXX 80
#define MAXY 23
#define MAX_FOOD 10000
#define TARGET_FOOD 200
#define MAX_SMELL 5000
#define SMELL_DROP_RATE 0.05
#define ANT_ERROR_RATE 0.02
#define ANT_EYESHOT 3
#define SMELL_GONE_SPEED 50
#define SMELL_GONE_RATE 0.05
#define TRACE_REMEMBER 50
#define MAX_BLOCK 100

#define NULL 0
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define SMELL_TYPE_FOOD 0
#define SMELL_TYPE_HOME 1

#include 「stdio.h」
#include 「conio.h」
#include 「dos.h」
#include 「stdlib.h」
#include 「dos.h」
#include 「process.h」
#include 「ctype.h」
#include 「math.h」

void WorldInitial(void);
void BlockInitial(void);
void CreatBlock(void);
void SaveBlock(void);
void LoadBlock(void);
void HomeFoodInitial(void);
void AntInitial(void);
void WorldChange(void);
void AntMove(void);
void AntOneStep(void);
void DealKey(char key);
void ClearSmellDisp(void);
void DispSmell(int type);
int AntNextDir(int xxx,int yyy,int ddir);
int GetMaxSmell(int type,int xxx,int yyy,int ddir);
int IsTrace(int xxx,int yyy);
int MaxLocation(int num1,int num2,int num3);
int CanGo(int xxx,int yyy,int ddir);
int JudgeCanGo(int xxx,int yyy);
int TurnLeft(int ddir);
int TurnRight(int ddir);
int TurnBack(int ddir);

int MainTimer(void);
char WaitForKey(int secnum);
void DispPlayTime(void);
int TimeUse(void);
void HideCur(void);
void ResetCur(void);

—————
struct HomeStruct
{
int xxx,yyy;
int amount;
int TargetFood;
}home;

struct FoodStruct
{
int xxx,yyy;
int amount;
}food;

struct AntStruct
{
int xxx,yyy;
int dir;
int speed;
int SpeedTimer;
int food;
int SmellAmount[2];
int tracex[TRACE_REMEMBER];
int tracey[TRACE_REMEMBER];
int TracePtr;
int IQ;
}ant[MAX_ANT];
int AntNow;
int timer10ms;
struct time starttime,endtime;
int Smell[2][MAXX+1][MAXY+1];
int block[MAXX+1][MAXY+1];
int SmellGoneTimer;
int SmellDispFlag;
int CanFindFood;
int HardtoFindPath;

—– Main ——–
void main(void)
{
char KeyPress;
int tu;

clrscr();
HideCur();
WorldInitial();
do
{
timer10ms = MainTimer();
if(timer10ms) AntMove();
if(timer10ms) WorldChange();
tu = TimeUse();
if(tu=60&&!CanFindFood)
{
gotoxy(1,MAXY+1);
printf(「Can not find food, maybe a block world.」);
WaitForKey(10);
WorldInitial();
}
if(tu=180&&home.amount100&&!HardtoFindPath)
{
gotoxy(1,MAXY+1);
printf(「God! it is so difficult to find a path.」);
if(WaitForKey(10)==0×0d) WorldInitial();
else
{
HardtoFindPath = 1;
gotoxy(1,MAXY+1);
printf(」 「);
}
}
if(home.amount=home.TargetFood)
{
gettime(&endtime);
KeyPress = WaitForKey(60);
DispPlayTime();
WaitForKey(10);
WorldInitial();
}
else if(kbhit())
{
KeyPress = getch();
DealKey(KeyPress);
}
else KeyPress = NULL;
}
while(KeyPress!=ESC);
gettime(&endtime);
DispPlayTime();
WaitForKey(10);
clrscr();
ResetCur();
}

❺ 用matlab編寫可靠性蟻群演算法!急用！！

function [Shortest_Route,Shortest_Length]=anttsp(city,iter_max,m,Alpha,Beta,Rho,Q)
%本函數用的蟻周模型
%city輸入城市的經緯度（n行2列)
%iter_max最大迭代次數
%m螞蟻數目
%三個參數alpha,beta,rho。
%Q信息素強度
%有問題聯系[email protected]

n=size(city,1);
d=zeros(n,n);
d=squareform(pdist(city));
Eta=1./d;
Tau=ones(n,n);
Tabu=zeros(m,n);
nC=1;
R_best=zeros(iter_max,n);
L_best=inf.*ones(iter_max,1);

while nC<=iter_max
route=[];
for i=1:ceil(m/n)
route=[route,randperm(n)];
end
Tabu(:,1)=(route(1,1:m))';
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));
J=zeros(1,(n-j+1));
P=J;
Jc=1;
for k=1:n
if isempty(find(visited==k, 1))
J(Jc)=k;
Jc=Jc+1;
end
end
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));

Pcum=cumsum(P);
Select=find(Pcum>=rand);
if isempty(Select)
Tabu(i,j)=round(1+(n-1)*rand);
else
next_visit=J(Select(1));
Tabu(i,j)=next_visit;
end
end
end
if nC>=2
Tabu(1,:)=R_best(nC-1,:);
end

L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+d(R(j),R(j+1));
end
L(i)=L(i)+d(R(1),R(n));
end
L_best(nC)=min(L);
pos=find(L==L_best(nC));
R_best(nC,:)=Tabu(pos(1),:);
nC=nC+1;

Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
Tabu=zeros(m,n);
end
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:);
Shortest_Length=L_best(Pos(1));
end

❻ 急求蟻群演算法解決 VRPTW問題的matlab代碼，最好是ACS或者MMAS的！

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%% 運行可能要很久，需要耐心等待
%%=========================================================================

n=length(C); %n 為市個數
for i=1:n %坐標矩陣轉換為距離矩陣
for j=1:n
D(i,j)=sqrt((x(i,1)-x(j,1))^2+(x(i,2)-x(j,2))^2);
end
end
for i=1:n %Eta為啟發因子，這里設為距離的倒數
for j=1:n %原文作者少考慮的當D=0是MATLAB提示出錯
if i~=j
Eta(i,j)=1./D(i,j);
end
end
end
for i=1:n
Eta(i,i)=0;
end
Tau=ones(n,n); %Tau為信息素矩陣
Tabu=zeros(m,n); %存儲並記錄路徑的生成
NC=1; %迭代計數器
R_best=zeros(NC_max,n); %各代最佳路線
L_best=inf.*ones(NC_max,1); %各代最佳路線的長度
L_ave=zeros(NC_max,1); %各代路線的平均長度

while NC<=NC_max %停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1)); %已訪問的城市
J=zeros(1,(n-j+1)); %待訪問的城市
P=J; %待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end

%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1;

%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;

%%第六步：禁忌表清零
Tabu=zeros(m,n);
end

%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:);
Shortest_Length=L_best(Pos(1));
DrawRoute(C,Shortest_Route) %調用函數繪圖

❼ 關於仿生學的文章

蒼蠅-----小型氣體分析儀。。
2。螢火蟲-----人工冷光；
3。電魚------伏特電池；
4。水母------水母耳風暴預測儀，
5。蛙眼------電子蛙眼
6。蝙蝠超聲定位器的原理------探路儀」。
7。藍藻-----光解水的裝置，
8。人體骨胳肌肉系統和生物電控制的研究，——步行機。
9。動物的爪子------現代起重機的掛鉤
10。動物的鱗甲------屋頂瓦楞
11。魚的鰭------槳
12。螳螂臂，或鋸齒草------鋸子
13。蒼耳屬植物-------尼龍搭扣。
14。龍蝦-------氣味探測儀。
15。壁虎腳趾------粘性錄音帶
16。貝-----外科手術的縫合到補船等-
17。鯊魚-----泳衣，
18。-鳥----飛機
19。魚------潛水艇
動物仿生學

生物學家通過對蛛絲的研究製造出高級絲線，抗撕斷裂降落傘與臨時吊橋用的高強度纜索。船和潛艇來自人們對魚類和海豚的模仿。

響尾蛇導彈等就是科學家模仿蛇的「熱眼」功能和其舌上排列著一種似照相機裝置的天然紅外線感知能力的原理，研製開發出來的現代化武器。

火箭升空利用的是水母、墨魚反沖原理。

科研人員通過研究變色龍的變色本領，為部隊研製出了不少軍事偽裝裝備。

科學家研究青蛙的眼睛，發明了電子蛙眼。

白蟻不僅使用膠粘劑建築它們的土堆，還可以通過頭部的小管向敵人噴射膠粘劑。於是人們按照同樣的原理製造了工作的武器—一塊干膠炮彈。

美國空軍通過毒蛇的「熱眼」功能，研究開發出了微型熱感測器。

我國紡織科技人員利用仿生學原理，借鑒陸地動物的皮毛結構，設計出一種KEG保溫面料，並具有防風和導濕的功能。

根據響尾蛇的頰窩能感覺到0.001℃的溫度變化的原理，人類發明了跟蹤追擊的響尾蛇導彈。人類還利用蛙跳的原理設計了蛤蟆夯。人類模仿警犬的高靈敏嗅覺製成了用於偵緝的「電子警犬」。科學家根據野豬的鼻子測毒的奇特本領製成了世界上第一批防毒面具。
仿生學是人類一直使用的方法，如模仿海豚皮而構造的"海豚皮游泳衣"、科學家研究鯨魚的皮膚時，發現其上有溝漕的結構，於是有個科學家就依照鯨魚皮構造，造成一個薄膜蒙在飛機的表面，據實驗可節約能源3%，若全國的飛機都蒙上這樣的表面，每年可節約幾十億。又如有科學家研究蜘蛛，發現蜘蛛的腿上沒有肌肉，有腳的動物會走，主要是靠肌肉的收縮，現在蜘蛛沒有肌肉為什麼會走路？經研究蜘蛛不是靠肌肉的收縮進行走路的，而是靠其中的"液壓"的結構進行走路，據此人們發明了液壓步行機……總之,從自然界得到啟迪,模仿其結構進行發明創造.這就是仿生學. 這是我們向自然界學習的一個方面。

另一方面,我們還可以從自然的規律中得到啟迪,利用其原理進行設計(包括設計演算法),這就是智能計算的思想。

智能計算

智能計算,也有人稱之為"軟計算"，就是借用自然界（生物界）規律的啟迪，根據其原理，模仿設計求解問題的演算法。如：人工神經網路技術、遺傳演算法、進化規劃、模擬煺火技術和群集智能技術等。

群集智能（Swarm Intelligence）

群居昆蟲以集體的力量，進行覓食、御敵、築巢的能力。這種群體所表現出來的"智能"，就稱之為群體智能。如蜜蜂采蜜、築巢、螞蟻覓食、築巢等。從群居昆蟲互相合作進行工作中，得到啟迪，研究其中的原理，以此原理來設計新的求解問題的演算法。

螞蟻演算法

螞蟻覓食時，在它走過的路上，留下外激素，這些外激素就象留下路標一樣，留給後來"蟻"一個路徑的標志。後面的螞蟻，就會沿著有外激素的路徑行走（外激素越多引誘螞蟻的能力就越強）。科學家們對此進行過試驗：用人造的外激素在紙上畫上一條路徑，對螞蟻進行試驗。結果螞蟻果然都沿畫有外激素的路徑行走。

B

D

蟻穴 A

C 食物

螞蟻尋食時，由蟻穴出發，可沿AC，也可沿ABC（見上圖），設各螞蟻尋到食物後沿原路回穴，並在路上留下外激素，那麼因AC路徑短，故當它們沿AC返回時，就在AC上留下兩次外激素。而沿ABC返回者，因其路徑長，僅回到D點，於是AD一段只留過一次外激素（即其上的外激素的濃度比AC上的濃度淡），故這時從蟻穴出來尋食者就會沿濃度大的路徑AC行走……最後大多數的螞蟻都會沿較短的路程進行尋食. 利用這個原理科學者們就設計了螞蟻演算法(進行求最短程)。

上面是個簡單的原理,當然要設計出切實可行的演算法,還要將模型進一步精確,如要計及外激素的揮發(即激素的濃度將隨時間而逐步降低等等).

用螞蟻演算法求最短程

1.一群螞蟻隨機從出發點出發，遇到食物，銜住食物，沿原路返回

2. 螞蟻在往返途中，在路上留下外激素標志

3. 外激素將隨時間逐漸蒸發（一般可用負指數函數來描述，即乘上因子e-at）

4. 由蟻穴出發的螞蟻,其選擇路徑的概率與各路徑上的外激素濃度成正比

螞蟻演算法還可以應用於很多實際問題，例如用於重建通訊路由，管理公司的電話網，對用戶記帳 收費等工作，任務分配問題等

不要停，繼續思索

進一步，將每個螞蟻看成是一個神經元，它們之間的通訊聯絡，看成是各神經元之間的連接，只不過這時的連接不是固定的，而是隨機的。即用一個隨機連接的神經網路來描述一個群體。這種神經網路所具有的性質，就是群體的智能
科學家們從蜻蜓翅膀末端的一塊比周圍略大一些的厚斑點得到了啟示，從而解決了飛機機翼因劇烈抖動而破碎的現象。

蝴蝶
五彩的蝴蝶顏色粲然，如重月紋鳳蝶、褐脈金斑蝶等，尤其是螢光翼鳳蝶，其後翊在陽光下時而金黃，時而翠綠，有時還由紫變藍。科學家通過對蝴蝶色彩的研究，為軍事防禦帶來了極大的稗益。在二戰期間，德軍包圍了列寧格勒，企圖用轟炸機摧毀其軍事目標和其他防禦設施。蘇聯昆蟲學家施萬維奇根據當時人們對偽裝缺乏認識的情況，提出利用蝴蝶的色彩在花叢中不易被發現的道理，在軍事設施上覆蓋蝴蝶花紋般的偽裝。因此，盡管德軍費盡心機，但列寧格勒的軍事基地仍然無恙，為贏得最後的勝利奠定了堅實的基礎。根據同樣的原理，後來人們還生產出了迷彩服，大大減少了戰斗中的傷亡。
人造衛星在太空中由於位置的不斷變化可引起溫度驟然變化，有時溫差可高達兩、三網路，嚴重影響許多儀器的正常工作。科學家們受蝴蝶身上的鱗片會隨陽光的照射方向自動變換角度而調節體溫的啟發，將人造衛星的控溫系統製成了葉片反兩面輻射、散熱能力相差很大的百葉窗樣式，在每扇窗的轉動位置安裝有對溫度敏感的金屬絲，隨溫度變化可調節窗的開合，從而保持了人造衛星內部溫度的恆定，解決了航天事業中的一大難題。

甲蟲
甲蟲自衛時，可噴射出具有惡臭的高溫液體「炮彈」，以迷惑、刺激和驚嚇敵害。科學家將其解剖後發現甲蟲體內有3個小室，分別儲有二元酚溶液、雙氧水和生物酶。二元酚和雙氧水流到第三小室與生物酶混合發生化學反應，瞬間就成為100℃的毒液，並迅速射出。這種原理目前已應用於軍事技術中。二戰期間，德國納粹為了戰爭的需要，據此機理製造出了一種功率極大且性能安全可靠的新型發動機，安裝在飛航式導彈上，使之飛行速度加快，安全穩定，命中率提高，英國倫敦在受其轟炸時損失慘重。美國軍事專家受甲蟲噴射原理的啟發研製出了先進的二元化武器。這種武器將兩種或多種能產生毒劑的化學物質分裝在兩個隔開的容器中，炮彈發射後隔膜破裂，兩種毒劑中間體在彈體飛行的8—10秒內混合並發生反應，在到達目標的瞬間生成致命的毒劑以殺傷敵人。它們易於生產、儲存、運輸，安全且不易失效。螢火蟲可將化學能直接轉變成光能，且轉化效率達100%，而普通電燈的發光效率只有6%。人們模仿螢火蟲的發光原理製成的冷光源可將發光效率提高十幾倍，大大節約了能量。另外，根據甲蟲的視動反應機制研製成功的空對地速度計已成功地應用於航空事業中。

蜻蜓
蜻蜓通過翅膀振動可產生不同於周圍大氣的局部不穩定氣流，並利用氣流產生的渦流來使自己上升。蜻蜓能在很小的推力下翱翔，不但可向前飛行，還能向後和左右兩側飛行，其向前飛行速度可達72公里/小時。此外，蜻蜓的飛行行為簡單，僅靠兩對翅膀不停地拍打。科學家據此結構基礎研製成功了直升飛機。飛機在高速飛行時，常會引起劇烈振動，甚至有時會折斷機翼而引起飛機失事。蜻蜓依靠加重的翅膀在高速飛行時安然無恙，於是人們效仿蜻蜓在飛機的兩翼加上了平衡重錘，解決了因高速飛行而引起振動這個令人棘手的問題。
為了研究滑翔飛行和碰撞的空氣動力學以及其飛行的效率，一個四葉驅動，用遠程水平儀控制的機動機翼（翅膀）模型被研製，並第一次在風洞內測試了各項飛行參數。
第二個模型試圖安裝一個以更快頻率飛行的翅膀，達到每秒18次震動的速度。有特色的是，這個模型採用了可變可調節前後兩對機翼之間相差的裝置。
研究的中心和長遠目標，是要研究使用「翅膀」驅動的飛機表現，以及與傳統的螺旋推動器驅動的飛機效率的比較等等。

蒼蠅
家蠅的特別之處在於它的快速的飛行技術，這使得它很難被人類抓住。即使在它的後面也很難接近它。它設想到了每一種情況，非常小心，並能快速移動。那麼，它是怎麼做到的呢？
昆蟲學家研究發現，蒼蠅的後翅退化成一對平衡棒。當它飛行時，平衡棒以一定的頻率進行機械振動，可以調節翅膀的運動方向，是保持蒼蠅身體平衡導航儀。科學家據此原理研製成一代新型導航儀——振動陀螺儀，大在改進了飛機的飛行性能，可使飛機自動停止危險的滾翻飛行，在機體強烈傾斜時還能自動恢復平衡，即使是飛機在最復雜的急轉彎時也萬無一失。蒼蠅的復眼包含4000個可獨立成像的單眼，能看清幾乎360度范圍內的物體。在蠅眼的啟示下，人們製成了由1329塊小透鏡組成的一次可拍1329張高解析度照片的蠅眼照像機，在軍事、醫學、航空、航天上被廣泛應用。蒼蠅的嗅覺特別靈敏並能對數十種氣味進行快速分析且可立即作出反應。科學家根據蒼蠅嗅覺器官的結構，把各種化學反應轉變成電脈沖的方式，製成了十分靈敏的小型氣體分析儀，目前已廣泛應用於宇宙飛船、潛艇和礦井等場所來檢測氣體成分，使科研、生產的安全系數更為准確、可靠。

蜂類
蜂巢由一個個排列整齊的六稜柱形小蜂房組成，每個小蜂房的底部由3個相同的菱形組成，這些結構與近代數學家精確計算出來的——菱形鈍角109○28』，銳角70○32』完全相同，是最節省材料的結構，且容量大、極堅固，令許多專家贊嘆不止。人們仿其構造用各種材料製成蜂巢式夾層結構板，強度大、重量輕、不易傳導聲和熱，是建築及製造太空梭、宇宙飛船、人造衛星等的理想材料。蜜蜂復眼的每個單眼中相鄰地排列著對偏振光方向十分敏感的偏振片，可利用太陽准確定位。科學家據此原理研製成功了偏振光導航儀，被廣泛用於航海事業中。

蒼蠅、螢火蟲、電魚、水母，見下詳述。
第五個：章魚的吸盤~

仿生學是一門模仿生物的特殊本領，利用生物的結構和功能原理來研製機械或各種新技術的科學。據傳說，我國古代著名工匠魯班，上山伐樹時，被絲矛草割破了手。他覺得奇怪，一棵小草怎麼會這樣厲害？經過仔細觀察，他發現絲茅草葉子的邊緣長著許多鋒利的細齒。於是魯班發明了木工用的鋸子。據推測，古代木船的發明，是從魚類的游泳得到了啟示。在發明飛機的過程中，人們也從蟲、鳥的飛行中學到了許多有用的知識。

現在，科學家們正帶著定向、導航、探測、能量轉換、信息處理、生物合成、結構力學和流體力學等眾多的科學難題，到生物界中去尋找啟示和答案。

蒼蠅與宇宙飛船

令人討厭的蒼蠅，與宏偉的航天事業似乎風馬牛不相及，但仿生學卻把它們緊密地聯系起來了。

蒼蠅是聲名狼藉的「逐臭之夫」，凡是腥臭污穢的地方，都有它們的蹤跡。蒼蠅的嗅覺特別靈敏，遠在幾千米外的氣味也能嗅到。但是蒼蠅並沒有「鼻子」，它靠什麼來充當嗅覺的呢? 原來，蒼蠅的「鼻子」——嗅覺感受器分布在頭部的一對觸角上。

每個「鼻子」只有一個「鼻孔」與外界相通，內含上百個嗅覺神經細胞。若有氣味進入「鼻孔」，這些神經立即把氣味刺激轉變成神經電脈沖，送往大腦。大腦根據不同氣味物質所產生的神經電脈沖的不同，就可區別出不同氣味的物質。因此，蒼蠅的觸角像是一台靈敏的氣體分析儀。

仿生學家由此得到啟發，根據蒼蠅嗅覺器的結構和功能，仿製成功一種十分奇特的小型氣體分析儀。這種儀器的「探頭」不是金屬，而是活的蒼蠅。就是把非常纖細的微電極插到蒼蠅的嗅覺神經上，將引導出來的神經電信號經電子線路放大後，送給分析器；分析器一經發現氣味物質的信號，便能發出警報。這種儀器已經被安裝在宇宙飛船的座艙里，用來檢測艙內氣體的成分。

這種小型氣體分析儀，也可測量潛水艇和礦井裡的有害氣體。利用這種原理，還可用來改進計算機的輸入裝置和有關氣體色層分析儀的結構原理中。

從螢火蟲到人工冷光

自從人類發明了電燈，生活變得方便、豐富多了。但電燈只能將電能的很少一部分轉變成可見光，其餘大部分都以熱能的形式浪費掉了，而且電燈的熱射線有害於人眼。那麼，有沒有隻發光不發熱的光源呢? 人類又把目光投向了大自然。

在自然界中，有許多生物都能發光，如細菌、真菌、蠕蟲、軟體動物、甲殼動物、昆蟲和魚類等，而且這些動物發出的光都不產生熱，所以又被稱為「冷光」。

在眾多的發光動物中，螢火蟲是其中的一類。螢火蟲約有1 500種,它們發出的冷光的顏色有黃綠色、橙色，光的亮度也各不相同。螢火蟲發出冷光不僅具有很高的發光效率，而且發出的冷光一般都很柔和，很適合人類的眼睛，光的強度也比較高。因此，生物光是一種人類理想的光。

科學家研究發現，螢火蟲的發光器位於腹部。這個發光器由發光層、透明層和反射層三部分組成。發光層擁有幾千個發光細胞，它們都含有熒光素和熒光酶兩種物質。在熒光酶的作用下，熒光素在細胞內水分的參與下，與氧化合便發出熒光。螢火蟲的發光，實質上是把化學能轉變成光能的過程。

早在40年代，人們根據對螢火蟲的研究，創造了日光燈，使人類的照明光源發生了很大變化。近年來，科學家先是從螢火蟲的發光器中分離出了純熒光素，後來又分離出了熒光酶，接著，又用化學方法人工合成了熒光素。由熒光素、熒光酶、ATP(三磷酸腺苷)和水混合而成的生物光源,可在充滿爆炸性瓦斯的礦井中當閃光燈。由於這種光沒有電源，不會產生磁場，因而可以在生物光源的照明下，做清除磁性水雷等工作。

現在，人們已能用摻和某些化學物質的方法得到類似生物光的冷光，作為安全照明用。

電魚與伏特電池

自然界中有許多生物都能產生電，僅僅是魚類就有500餘種 。人們將這些能放電的魚，統稱為「電魚」。

各種電魚放電的本領各不相同。放電能力最強的是電鰩、電鯰和電鰻。中等大小的電鰩能產生70伏左右的電壓,而非洲電鰩能產生的電壓高達220伏；非洲電鯰能產生350伏的電壓；電鰻能產生500伏的電壓，有一種南美洲電鰻竟能產生高達880伏的電壓，稱得上電擊冠軍,據說它能擊斃像馬那樣的大動物。

電魚放電的奧秘究竟在哪裡?經過對電魚的解剖研究， 終於發現在電魚體內有一種奇特的發電器官。這些發電器是由許多叫電板或電盤的半透明的盤形細胞構成的。由於電魚的種類不同，所以發電器的形狀、位置、電板數都不一樣。電鰻的發電器呈棱形，位於尾部脊椎兩側的肌肉中；電鰩的發電器形似扁平的腎臟，排列在身體中線兩側，共有200萬塊電板;電鯰的發電器起源於某種腺體，位於皮膚與肌肉之間,約有500萬塊電板。單個電板產生的電壓很微弱，但由於電板很多，產生的電壓就很大了。

電魚這種非凡的本領，引起了人們極大的興趣。19世紀初，義大利物理學家伏特，以電魚發電器官為模型，設計出世界上最早的伏打電池。因為這種電池是根據電魚的天然發電器設計的,所以把它叫做「人造電器官」。對電魚的研究，還給人們這樣的啟示：如果能成功地模仿電魚的發電器官，那麼，船舶和潛水艇等的動力問題便能得到很好的解決。

水母的順風耳

「燕子低飛行將雨，蟬鳴雨中天放晴。」生物的行為與天氣的變化有一定關系。沿海漁民都知道，生活在沿岸的魚和水母成批地游向大海，就預示著風暴即將來臨。

水母，又叫海蜇，是一種古老的腔腸動物，早在5億年前,它就漂浮在海洋里了。這種低等動物有預測風暴的本能，每當風暴來臨前，它就游向大海避難去了。

原來，在藍色的海洋上，由空氣和波浪摩擦而產生的次聲波 (頻率為每秒8—13次)，總是風暴來臨的前奏曲。這種次聲波人耳無法聽到，小小的水母卻很敏感。仿生學家發現，水母的耳朵的共振腔里長著一個細柄，柄上有個小球，球內有塊小小的聽石，當風暴前的次聲波沖擊水母耳中的聽石時，聽石就剌激球壁上的神經感受器，於是水母就聽到了正在來臨的風暴的隆隆聲。

仿生學家仿照水母耳朵的結構和功能，設計了水母耳風暴預測儀，相當精確地模擬了水母感受次聲波的器官。把這種儀器安裝在艦船的前甲板上，當接受到風暴的次聲波時，可令旋轉360°的喇叭自行停止旋轉,它所指的方向，就是風暴前進的方向；指示器上的讀數即可告知風暴的強度。這種預測儀能提前15小時對風暴作出預報，對航海和漁業的安全都有重要幫助

❽ 求生物學 蟻群演算法

蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值。

下面詳細說明：
1、范圍：
螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是3*3個方格世界，並且能移動的距離也在這個范圍之內。
2、環境：
螞蟻所在的環境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內的環境信息。環境以一定的速率讓信息素消失。
3、覓食規則：
在每隻螞蟻能感知的范圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，並且比較在能感知的范圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，並且每隻螞蟻都會以小概率犯錯誤，從而並不是往信息素最多的點移動。螞蟻找窩的規則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。
4、移動規則：
每隻螞蟻都朝向信息素最多的方向移，並且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，並且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發現要走的下一點已經在最近走過了，它就會盡量避開。
5、避障規則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，並且有信息素指引的話，它會按照覓食的規則行為。
6、播撒信息素規則：
每隻螞蟻在剛找到食物或者窩的時候撒發的信息素最多，並隨著它走遠的距離，播撒的信息素越來越少。
根據這幾條規則，螞蟻之間並沒有直接的關系，但是每隻螞蟻都和環境發生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯起來了。比如，當一隻螞蟻找到了食物，它並沒有直接告訴其它螞蟻這兒有食物，而是向環境播撒信息素，當其它的螞蟻經過它附近的時候，就會感覺到信息素的存在，進而根據信息素的指引找到了食物。

❾ 遺傳演算法和蟻群演算法在求解TSP問題上的對比分析

【原創】比遺傳演算法性能更好：蟻群演算法TSP(旅行商問題)通用matlab程序
聲明：本程序為本人原創，在研學論壇首次發表，本人保留一切權利，僅供學習交流用，如轉載請註明原作者！

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%%=========================================================================

%%第一步：變數初始化
n=size(C,1);%n表示問題的規模（城市個數）
D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta為啟發因子，這里設為距離的倒數
Tau=ones(n,n);%Tau為信息素矩陣
Tabu=zeros(m,n);%存儲並記錄路徑的生成
NC=1;%迭代計數器
R_best=zeros(NC_max,n);%各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度

while NC<=NC_max%停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已訪問的城市
J=zeros(1,(n-j+1));%待訪問的城市
P=J;%待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end

%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1

%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;

%%第六步：禁忌表清零
Tabu=zeros(m,n);
end

%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)

function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 畫路線圖的子函數
%%-------------------------------------------------------------------------
%% C Coordinate 節點坐標，由一個N×2的矩陣存儲
%% R Route 路線
%%=========================================================================

N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end

設置初始參數如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐標為：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975

運行後得到15602的巡遊路徑，

❿ 蟻群演算法，退火演算法這些東西究竟屬於什麼，這些東西要從哪裡才能系統學習

第1章緒論
1.1螞蟻的基本習性
1.1.1螞蟻的信息系統
1.1.2蟻群社會的遺傳與進化
1.2蟻群覓食行為與覓食策略
1.2.1螞蟻的覓食行為
1.2.2螞蟻的覓食策略
1.3人工蟻群演算法的基本思想
1.3.1人工蟻與真實螞蟻的異同
1.3.2人工蟻群演算法的實現過程
1.4蟻群優化演算法的意義及應用
1.4.1蟻群優化演算法的意義
l.4.2蟻群演算法的應用
1.5蟻群演算法的展望
第2章螞蟻系統——蟻群演算法的原型
2.1螞蟻系統模型的建立
2.2蟻量系統和蟻密系統的模型
2.3蟻周系統模型
第3章改進的蟻群優化演算法
3.1帶精英策略的螞蟻系統
3.2基於優化排序的螞蟻系統
3.3蟻群系統
3.3.1蟻群系統狀態轉移規則
3.3.2蟻群系統全局更新規則
3.3.3蟻群系統局部更新規則
3.3.4候選集合策略
3.4最大一最小螞蟻系統
3.4.1信息素軌跡更新
3.4.2信息素軌跡的限制
3.4.3信息素軌跡的初始化
3.4.4信息素軌跡的平滑化
3.5最優一最差螞蟻系統
3.5.1最優一最差螞蟻系統的基本思想
3.5.2最優一最差螞蟻系統的工作過程
第4章蟻群優化演算法的模擬研究
4.1螞蟻系統三類模型的模擬研究
4.1.1三類模型性能的比較
4.2.2基於統計的參數優化
4.2基於蟻群系統模型的模擬研究
4.2.1局部優化演算法的有效性
4.2.2蟻群系統與其他啟發演算法的比較
4.3最大一最小螞蟻系統的模擬研究
4.3.1信息素軌跡初始化研究
4.3.2信息素軌跡量下限的作用
4.3.3蟻群演算法的對比
4.4最優一最差螞蟻系統的模擬研究
4.4.1參數ε的設置
4.4.2幾種改進的蟻群演算法比較
第5章蟻群演算法與遺傳、模擬退火演算法的對比
5.1遺傳演算法
5.1.1遺傳演算法與自然選擇
5.1.2遺傳演算法的基本步驟
5.1.3旅行商問題的遺傳演算法實現
5.2模擬退火演算法
5.2.1物理退火過程和Metroplis准則
5.2.2模擬退火法的基本原理
5.3蟻群演算法與遺傳演算法、模擬退火演算法的比較
5.3.1三種演算法的優化質量比較
5.3.2三種演算法收斂速度比較
5.3.3三種演算法的特點與比較分析
第6章蟻群演算法與遺傳、免疫演算法的融合
6.1遺傳演算法與螞蟻演算法融合的GAAA演算法
6.1.1遺傳演算法與螞蟻演算法融合的基本思想
……
第7章自適應蟻群演算法
第8章並行蟻群演算法
第9章蟻群演算法的收斂性與蟻群行為模型
第10章蟻群演算法在優化問題中的應用
附錄
參考文獻