實現蟻群演算法

⑴ 什麼是蟻群演算法，神經網路演算法，遺傳演算法

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

神經網路
思維學普遍認為，人類大腦的思維分為抽象（邏輯）思維、形象（直觀）思維和靈感（頓悟）思維三種基本方式。
邏輯性的思維是指根據邏輯規則進行推理的過程；它先將信息化成概念，並用符號表示，然後，根據符號運算按串列模式進行邏輯推理；這一過程可以寫成串列的指令，讓計算機執行。然而，直觀性的思維是將分布式存儲的信息綜合起來，結果是忽然間產生想法或解決問題的辦法。這種思維方式的根本之點在於以下兩點:1.信息是通過神經元上的興奮模式分布儲在網路上;2.信息處理是通過神經元之間同時相互作用的動態過程來完成的。
人工神經網路就是模擬人思維的第二種方式。這是一個非線性動力學系統，其特色在於信息的分布式存儲和並行協同處理。雖然單個神經元的結構極其簡單，功能有限，但大量神經元構成的網路系統所能實現的行為卻是極其豐富多彩的。
神經網路的研究內容相當廣泛，反映了多學科交叉技術領域的特點。目前，主要的研究工作集中在以下幾個方面：
（1）生物原型研究。從生理學、心理學、解剖學、腦科學、病理學等生物科學方面研究神經細胞、神經網路、神經系統的生物原型結構及其功能機理。
（2）建立理論模型。根據生物原型的研究，建立神經元、神經網路的理論模型。其中包括概念模型、知識模型、物理化學模型、數學模型等。
（3）網路模型與演算法研究。在理論模型研究的基礎上構作具體的神經網路模型，以實現計算機饃擬或准備製作硬體，包括網路學習演算法的研究。這方面的工作也稱為技術模型研究。
（4）人工神經網路應用系統。在網路模型與演算法研究的基礎上，利用人工神經網路組成實際的應用系統，例如，完成某種信號處理或模式識別的功能、構作專家系統、製成機器人等等。
縱觀當代新興科學技術的發展歷史，人類在征服宇宙空間、基本粒子，生命起源等科學技術領域的進程中歷經了崎嶇不平的道路。我們也會看到，探索人腦功能和神經網路的研究將伴隨著重重困難的克服而日新月異。
遺傳演算法，是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它最初由美國Michigan大學J.Holland教授於1975年首先提出來的，並出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳演算法（SGA）。

⑵ 蟻群演算法難學嗎

難學。
一些超級難的演算法有遺傳演算法，蟻群演算法。蟻群演算法基本原理：在自然界中，生物群體所表現出的智能得到越來越多的關注，許多的群智能優化演算法都是通過對群體智能的模擬而實現的。其中模擬螞蟻群體覓食的蟻群演算法成為一種主要的群智能演算法。演算法原理：在自然界中，對於覓食的螞蟻群體，其可以在任何和沒有提示的情況下找到食物和巢穴之間的最短路徑。並且能夠根據和環境的變遷，自適應地找到新的最優路徑。根據生物學家研究，螞蟻群體這一行為的根本原因是：螞蟻在尋找食物的過程中，能在其走過的路徑上釋放一種特殊的物質信息素，隨著時間的推移，這種信息素會逐漸地揮發，而對於後來的螞蟻，選擇某條路徑的概率與該路徑上信息素的濃度成正比。當某一條路徑上通過的螞蟻越多的時候，這條路徑上的信息素的濃度就會累積越大，後來的螞蟻選擇此路徑的概率也就越大。路徑上螞蟻越多，導致信息素濃度越高，從而會吸引更多的螞蟻，從而形成一種正反饋機制，通過這種機制，最終蟻群可以發現最短路徑。

⑶ 蟻群演算法中轉移概率是怎麼用的.不同的螞蟻為什麼會選擇不同的路徑

因為不同路徑的信息素和啟發信息不同，所以向每條路徑轉移的概率也不同；
具體實現可以運用輪盤賭選擇，轉移概率越大的路徑就會有更多的螞蟻選擇.。
Prime 演算法和 Kruskal 演算法都是用來求加權連通簡單圖中權和最小的支撐樹（即最小樹）的，Prime演算法的時間復雜度為O(n^2) （n 為頂點數），Kruskal 演算法的時間復雜度為 O(eln(e)) （e為邊數），這兩種演算法都是多項式時間演算法，也就是說，最小樹問題已經有了有效演算法去求解，屬於P問題。
Dijkstra 演算法求解的是加權連通簡單圖中一個頂點到其它每個頂點的具有最小權和的有向路，最簡單版本的時間復雜度是O(n^2)，也是多項式時間演算法。
而蟻群演算法是一種近似演算法，它不是用來解決已存在精確有效演算法的問題的，而是用來解決至今沒有找到精確的有效演算法的問題的，比如旅行商問題（TSP）。
旅行商問題也可以說是求「最短路徑」，但它是求一個完全圖的最小哈密頓圈，這個問題至今未找到多項式時間演算法，屬於NPC問題，也就是說，當問題規模稍大一點，現有的精確演算法的運算量就會急劇增加。
文中的某些觀點引自知乎大神余幸恩，感謝幫忙！~

⑷ 蟻群演算法java版

說明：信息素權重，路徑權重和信息素蒸發率對最後的結果影響很大，需要微調。
目前發現2 / 5 / 0.5 能達到稍微讓人滿意的效果。本程序離完美的ACO還差很遠，僅供參考。
本蟻群演算法為AS演算法。

用法：

1.new一個對象
ACOforTSP tsp = new ACPforTSP(tsp數據文件名,迭代次數，螞蟻數量，信息素權重，路徑權重，信息素蒸發率）;
2.用go()方法運行
tsp.go();

ACOforTSP.java
___________________________________________________________________
import java.io.File;
import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
import static java.lang.Math.random;
import java.util.HashMap;
import java.io.FileReader;
import java.io.BufferedReader;
/**
*
* @author dvdface
*/

public class ACOforTSP {

//城市的距離表
private double[][] distance;
//距離的倒數表
private double[][] heuristic;
//啟發信息表
private double[][] pheromone;
//權重
private int alpha, beta;
//迭代的次數
private int iterationTimes;
//螞蟻的數量
private int numbersOfAnt;
//蒸發率
private double rate;

ACOforTSP (String file, int iterationTimes, int numbersOfAnt, int alpha, int beta, double rate) {

//載入文件
this.initializeData(file);
//初始化參數
this.iterationTimes = iterationTimes;
//設置螞蟻數量
this.numbersOfAnt = numbersOfAnt;
//設置權重
this.alpha = alpha;
this.beta = beta;
//設置蒸發率
this.rate = rate;
}

private void initializeData(String filename) {

//定義內部類
class City {

int no;
double x;
double y;

City(int no, double x, double y) {

this.no = no;
this.x = x;
this.y = y;
}

private double getDistance(City city) {

return sqrt(pow((x - city.x), 2) + pow((y - city.y), 2));
}
}

try {
//定義HashMap保存讀取的坐標信息
HashMap<Integer, City> map = new HashMap<Integer, City>();
//讀取文件
BufferedReader reader = new BufferedReader(new FileReader(new File(filename)));
for (String str = reader.readLine(); str != null; str = reader.readLine()) {
//將讀到的信息保存入HashMap
if (str.matches("([0-9]+)(\\s*)([0-9]+)(.?)([0-9]*)(\\s*)([0-9]+)(.?)([0-9]*)")) {

String[] data = str.split("(\\s+)");
City city = new City(Integer.parseInt(data[0]),
Double.parseDouble(data[1]),
Double.parseDouble(data[2]));

map.put(city.no, city);
}
}
//分配距離矩陣存儲空間
distance = new double[map.size() + 1][map.size() + 1];
//分配距離倒數矩陣存儲空間
heuristic = new double[map.size() + 1][map.size() + 1];
//分配信息素矩陣存儲空間
pheromone = new double[map.size() + 1][map.size() + 1];
for (int i = 1; i < map.size() + 1; i++) {
for (int j = 1; j < map.size() + 1; j++) {
//計算城市間的距離，並存入距離矩陣
distance[i][j] = map.get(i).getDistance(map.get(j));
//計算距離倒數，並存入距離倒數矩陣
heuristic[i][j] = 1 / distance[i][j];
//初始化信息素矩陣
pheromone[i][j] = 1;
}
}

} catch (Exception exception) {

System.out.println("初始化數據失敗！");
}
}

class Ant {

//已訪問城市列表
private boolean[] visited;
//訪問順序表
private int[] tour;
//已訪問城市的個數
private int n;
//總的距離
private double total;

Ant() {
//給訪問順序表分配空間
tour = new int[distance.length+1];
//已存入城市數量為n，剛開始為0
n = 0;
//將起始城市1,放入訪問結點順序表第一項
tour[++n] = 1;
//給已訪問城市結點分配空間
visited = new boolean[distance.length];
//第一個城市為出發城市，設置為已訪問
visited[tour[n]] = true;
}

private int chooseCity() {

//用來random的隨機數
double m = 0;
//獲得當前所在的城市號放入j,如果和j相鄰的城市沒有被訪問，那麼加入m
for (int i = 1, j = tour[n]; i < pheromone.length; i++) {

if (!visited[i]) {
m += pow(pheromone[j][i], alpha) * pow(heuristic[j][i], beta);
}
}

//保存隨機到的數
double p = m * random();
//尋找被隨機到的城市
double k = 0;
//保存找到的城市
int q = 0;
for (int i = 1, j = tour[n]; k < p; i++) {

if (!visited[i]) {

k += pow(pheromone[j][i], alpha) * pow(heuristic[j][i], beta);
q = i;
}
}

return q;
}

private void constructSolution () {

while (n != (distance.length-1) ) {

//選取下一個城市
int p = chooseCity();
//計算總的距離
total += distance[tour[n]][p];
//將選取到的城市放入已訪問列表
tour[++n] = p;
//將選取到的城市標記為已訪問
visited[p] = true;
}

//回到起點
total += distance[tour[1]][tour[n]];
//將起點加入訪問順序表的最後
tour[++n] = tour[1];
}

private void releasePheromone() {

//釋放信息素的大小
double t = 1/total;
//釋放信息素
for (int i=1;i<tour.length-1;i++) {

pheromone[tour[i]][tour[i+1]] += t;
pheromone[tour[i+1]][tour[i]] += t;
}
}

}

public void go() {

//保存最好的路徑和路徑長度
double bestTotal = Double.MAX_VALUE;
int[] bestTour = new int[distance.length+1];

//新建螞蟻數組，用來引用所創建的螞蟻
Ant[] ant = new Ant[numbersOfAnt];

//進行iterationTimes次迭代
while (iterationTimes != 0) {
//初始化新的一批螞蟻（這里用構造新的螞蟻代替重置螞蟻狀態）
for (int i=0; i<numbersOfAnt; i++) {
ant[i] = new Ant();
}

//進行一次迭代（即讓所有的螞蟻構建一條路徑）
for (int i=0; i<numbersOfAnt; i++) {

ant[i].constructSolution();
//如果螞蟻構建的路徑長度比上次最好的還好，那麼保存這個長度和它所走的路徑
if (ant[i].total<bestTotal) {

bestTotal = ant[i].total;
System.array(ant[i].tour, 1, bestTour, 1, bestTour.length-1);
}
}

//蒸發信息素
evaporatePheromone();

//釋放信息素
for (int i=0; i<numbersOfAnt; i++) {

ant[i].releasePheromone();
}

//報告本次迭代的信息
System.out.format("本次為倒數第%d次迭代,當前最優路徑長度為%10.2f\n",iterationTimes,bestTotal);

//迭代總數減去1，進行下次迭代
iterationTimes--;
}

//輸出最好的路徑長度
System.out.format("得到的最優的路徑長度為:%10.2f\n",bestTotal);
//輸出最好的路徑
System.out.println("最優路徑如下：");
for (int i=1; i<bestTour.length; i++) {

System.out.print("→"+bestTour[i]);
}
}

private void evaporatePheromone() {

for (int i = 1; i < pheromone.length; i++)
for (int j = 1; j < pheromone.length; j++) {

pheromone[i][j] *= 1-rate;
}

}
}

⑸ 求帶注釋的蟻群演算法

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();
}

⑹ 蟻群演算法的定義

各個螞蟻在沒有事先告訴他們食物在什麼地方的前提下開始尋找食物。當一隻找到食物以後，它會向環境釋放一種揮發性分泌物pheromone (稱為信息素,該物質隨著時間的推移會逐漸揮發消失，信息素濃度的大小表徵路徑的遠近)來實現的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻並沒有像其它螞蟻一樣總重復同樣的路，他們會另闢蹊徑，如果另開辟的道路比原來的其他道路更短，那麼，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最後，經過一段時間運行，可能會出現一條最短的路徑被大多數螞蟻重復著。

⑺ 如何用蟻群演算法來計算固定時間內走更多的城市且路程最短

概念：蟻群演算法(ant colony optimization,ACO),又稱螞蟻演算法,是一種用來在圖中尋找優化路徑的機率型演算法.它由Marco Dorigo於1992年在他的博士論文中提出,其靈感來源於螞蟻在尋找食物過程中發現路徑的行為.蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值
其原理：為什麼小小的螞蟻能夠找到食物?他們具有智能么?設想,如果我們要為螞蟻設計一個人工智慧的程序,那麼這個程序要多麼復雜呢?首先,你要讓螞蟻能夠避開障礙物,就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物,其次,要讓螞蟻找到食物,就需要讓他們遍歷空間上的所有點；再次,如果要讓螞蟻找到最短的路徑,那麼需要計算所有可能的路徑並且比較它們的大小,而且更重要的是,你要小心翼翼的編程,因為程序的錯誤也許會讓你前功盡棄.這是多麼不可思議的程序!太復雜了,恐怕沒人能夠完成這樣繁瑣冗餘的程序
應用范圍：螞蟻觀察到的范圍是一個方格世界,螞蟻有一個參數為速度半徑（一般是3）,那麼它能觀察到的范圍就是3*3個方格世界,並且能移動的距離也在這個范圍之內
引申：跟著螞蟻的蹤跡,你找到了什麼?通過上面的原理敘述和實際操作,我們不難發現螞蟻之所以具有智能行為,完全歸功於它的簡單行為規則,而這些規則綜合起來具有下面兩個方面的特點：1、多樣性 2、正反饋 多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環,正反饋機制則保證了相對優良的信息能夠被保存下來.我們可以把多樣性看成是一種創造能力,而正反饋是一種學習強化能力.正反饋的力量也可以比喻成權威的意見,而多樣性是打破權威體現的創造性,正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了.引申來講,大自然的進化,社會的進步、人類的創新實際上都離不開這兩樣東西,多樣性保證了系統的創新能力,正反饋保證了優良特性能夠得到強化,兩者要恰到好處的結合.如果多樣性過剩,也就是系統過於活躍,這相當於螞蟻會過多的隨機運動,它就會陷入混沌狀態；而相反,多樣性不夠,正反饋機制過強,那麼系統就好比一潭死水.這在蟻群中來講就表現為,螞蟻的行為過於僵硬,當環境變化了,螞蟻群仍然不能適當的調整.既然復雜性、智能行為是根據底層規則涌現的,既然底層規則具有多樣性和正反饋特點,那麼也許你會問這些規則是哪裡來的?多樣性和正反饋又是哪裡來的?我本人的意見：規則來源於大自然的進化.而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合.而這樣的巧妙結合又是為什麼呢?為什麼在你眼前呈現的世界是如此栩栩如生呢?答案在於環境造就了這一切,之所以你看到栩栩如生的世界,是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了,被環境淘汰了!蟻群演算法的實現 下面的程序開始運行之後,螞蟻們開始從窩里出動了,尋找食物；他們會順著屏幕爬滿整個畫面,直到找到食物再返回窩.其中,『F』點表示食物,『H』表示窩,白色塊表示障礙物,『+』就是螞蟻了.

⑻ 蟻群演算法信息素在路由協議中的實現

述了。
目前蟻群演算法主要用在組合優化方面，基本蟻群演算法的思路是這樣的：
1.
在初始狀態下，一群螞蟻外出，此時沒有信息素，那麼各自會隨機的選擇一條路徑。
2.
在下一個狀態，每隻螞蟻到達了不同的點，從初始點到這些點之間留下了信息素，螞蟻繼續走，已經到達目標的螞蟻開始返回，與此同時，下一批螞蟻出動，它們都會按照各條路徑上信息素的多少選擇路線(selection)，更傾向於選擇信息素多的路徑走（當然也有隨機性）。
3.
又到了再下一個狀態，剛剛沒有螞蟻經過的路線上的信息素不同程度的揮發掉了(evaporation)，而剛剛經過了螞蟻的路線信息素增強(reinforcement)。然後又出動一批螞蟻，重復第2個步驟。
每個狀態到下一個狀態的變化稱為一次迭代，在迭代多次過後，就會有某一條路徑上的信息素明顯多於其它路徑，這通常就是一條最優路徑。
關鍵的部分在於步驟2和3：
步驟2中，每隻螞蟻都要作出選擇，怎樣選擇呢？
selection過程用一個簡單的函數實現：
螞蟻選擇某條路線的概率＝該路線上的信息素÷所有可選擇路線的信息素之和
假設螞蟻在i點，p(i,j)表示下一次到達j點的概率，而τ(i,j)表示ij兩點間的信息素，則：
p(i,j)＝τ(i,j)/∑τ(i)
（如果所有可選路線的信息素之和∑τ(i)＝0，即前面還沒有螞蟻來過，概率就是一個[0,1]上的隨機值，即隨機選擇一條路線）
步驟3中，揮發和增強是演算法的關鍵所在（也就是如何數學定義信息素的）
evaporation過程和reinforcement過程定義了一個揮發因子，是迭代次數k的一個函數
ρ(k)＝1－lnk/ln(k+1)
最初設定每條路徑的信息素τ(i,j,0)為相同的值
然後，第k+1次迭代時，信息素的多少
對於沒有螞蟻經過的路線：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)，顯然信息素減少了
有螞蟻經過的路線：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)＋ρ(k)/|W|，W為所有點的集合
為什麼各個函數要如此定義，這個問題很難解釋清楚，這也是演算法的精妙所在。如此定義信息素的揮發和增強，以及路徑選擇，根據馬爾可夫過程（隨機過程之一）能夠推導出，在迭代了足夠多次以後，演算法能夠收斂到最佳路徑。
組合優化很有意思的，像禁忌搜索、模擬退火、蟻群演算法、遺傳演算法、神經網路這些演算法能夠解決很多生活中的實際問題，樓主有空可以招本書看看。

⑼ 蟻群演算法怎樣用MATLAB模擬

蟻群演算法採用matlab開發的模擬平台：演算法實現，路徑顯示，人機交互控制等
希望對你有幫助！
是可以運行的
% the procere of ant colony algorithm for VRP
%
% % % % % % % % % % %

%initialize the parameters of ant colony algorithms
load data.txt;
d=data(:,2:3);
g=data(:,4);
m=31; % 螞蟻數
alpha=1;
belta=4;% 決定tao和miu重要性的參數
lmda=0;
rou=0.9;%衰減系數
q0=0.95;
% 概率
tao0=1/(31*841.04);%初始信息素
Q=1;%螞蟻循環一周所釋放的信息素
defined_phrm=15.0; % initial pheromone level value
QV=100; % 車輛容量
vehicle_best=round(sum(g)/QV)+1;%所完成任務所需的最少車數
V=40;
% 計算兩點的距離
for i=1:32;
for j=1:32;
dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2);
end;
end;
%給tao miu賦初值
for i=1:32;
for j=1:32;
if i~=j;
%s(i,j)=dist(i,1)+dist(1,j)-dist(i,j);
tao(i,j)=defined_phrm;
miu(i,j)=1/dist(i,j);
end;
end;
end;

for k=1:32;
for k=1:32;
deltao(i,j)=0;
end;
end;
best_cost=10000;
for n_gen=1:50;
print_head(n_gen);
for i=1:m;
%best_solution=[];
print_head2(i);
sumload=0;
cur_pos(i)=1;
rn=randperm(32);
n=1;
nn=1;
part_sol(nn)=1;
%cost(n_gen,i)=0.0;
n_sol=0; % 由螞蟻產生的路徑數量
M_vehicle=500;
t=0; %最佳路徑數組的元素數為0

while sumload<=QV;

for k=1:length(rn);
if sumload+g(rn(k))<=QV;
gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV;
A(n)=rn(k);
n=n+1;
end;
end;
fid=fopen('out_customer.txt','a+');
fprintf(fid,'%s %i\t','the current position is:',cur_pos(i));
fprintf(fid,'\n%s','the possible customer set is:')
fprintf(fid,'\t%i\n',A);
fprintf(fid,'------------------------------\n');
fclose(fid);

p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i);
maxp=1e-8;
na=length(A);
for j=1:na;
if p(j)>maxp
maxp=p(j);
index_max=j;
end;
end;

old_pos=cur_pos(i);
if rand(1)<q0
cur_pos(i)=A(index_max);
else
krnd=randperm(na);
cur_pos(i)=A(krnd(1));
bbb=[old_pos cur_pos(i)];
ccc=[1 1];
if bbb==ccc;
cur_pos(i)=A(krnd(2));
end;
end;

tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0);%對所經弧進行局部更新

sumload=sumload+g(cur_pos(i));

nn=nn+1;
part_sol(nn)=cur_pos(i);
temp_load=sumload;

if cur_pos(i)~=1;
rn=setdiff(rn,cur_pos(i));
n=1;
A=[];
end;

if cur_pos(i)==1; % 如果當前點為車場,將當前路徑中的已訪問用戶去掉後,開始產生新路徑
if setdiff(part_sol,1)~=[];
n_sol=n_sol+1; % 表示產生的路徑數,n_sol=1,2,3,..5,6...,超過5條對其費用加上車輛的派遣費用
fid=fopen('out_solution.txt','a+');
fprintf(fid,'%s%i%s','NO.',n_sol,'條路徑是:');
fprintf(fid,'%i ',part_sol);
fprintf(fid,'\n');
fprintf(fid,'%s','當前的用戶需求量是:');
fprintf(fid,'%i\n',temp_load);
fprintf(fid,'------------------------------\n');
fclose(fid);

% 對所得路徑進行路徑內3-opt優化
final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產生的路徑傳給一個數組
temp(t+nt)=final_sol(nt);
end;
t=t+length(final_sol)-1;

sumload=0;
final_sol=setdiff(final_sol,1);
rn=setdiff(rn,final_sol);
part_sol=[];
final_sol=[];
nn=1;
part_sol(nn)=cur_pos(i);
A=[];
n=1;

end;
end;

if setdiff(rn,1)==[];% 產生最後一條終點不為1的路徑
n_sol=n_sol+1;
nl=length(part_sol);
part_sol(nl+1)=1;%將路徑的最後1位補1

% 對所得路徑進行路徑內3-opt優化
final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產生的路徑傳給一個數組
temp(t+nt)=final_sol(nt);
end;

cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best); %計算由螞蟻i產生的路徑總長度

for ki=1:length(temp)-1;
deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i);
end;

if cost(n_gen,i)<best_cost;
best_cost=cost(n_gen,i);
old_cost=best_cost;
best_gen=n_gen; % 產生最小費用的代數
best_ant=i; %產生最小費用的螞蟻
best_solution=temp;
end;

if i==m;%如果所有螞蟻均完成一次循環，，則用最佳費用所對應的路徑對弧進行整體更新
for ii=1:32;
for jj=1:32;
tao(ii,jj)=(1-rou)*tao(ii,jj);
end;
end;

for kk=1:length(best_solution)-1;

tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1));
end;
end;

fid=fopen('out_solution.txt','a+');
fprintf(fid,'%s%i%s','NO.',n_sol,'路徑是:');
fprintf(fid,'%i ',part_sol);
fprintf(fid,'\n');
fprintf(fid,'%s %i\n','當前的用戶需求量是:',temp_load);
fprintf(fid,'%s %f\n','總費用是:',cost(n_gen,i));
fprintf(fid,'------------------------------\n');
fprintf(fid,'%s\n','最終路徑是:');
fprintf(fid,'%i-',temp);
fprintf(fid,'\n');
fclose(fid);
temp=[];
break;
end;
end;

end;
end;

⑽ 你知道怎麼用matlab實現蟻群演算法么

PSO演算法嗎？網上很多源代碼，自己寫的話也很快。核心就是那幾個迭代公式