蟻群算法程序代碼java 蟻群算法csdn

TSP解決之道——蟻群算法

蟻群算法java實(shí)現(xiàn)以及TSP問題蟻群算法求解

創(chuàng)新互聯(lián)公司從2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站建設(shè)、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元武鳴做網(wǎng)站,已為上家服務(wù),為武鳴各地企業(yè)和個人服務(wù),聯(lián)系電話:18982081108

蟻群算法原理與應(yīng)用講解

蟻群算法原理與應(yīng)用1 -自然計算與群體智能

1、蟻群算法(Ant Clony Optimization,ACO)是一種群智能算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問題提供了一個新的可能性。

2、是一種仿生學(xué)的算法，是由自然界中螞蟻覓食的行為而啟發(fā)。（artificial ants；雙橋?qū)嶒?yàn)）

3、運(yùn)作機(jī)理：當(dāng)一定路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度，而強(qiáng)度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機(jī)制。

4、蟻群算法歐化過程中的兩個重要原則：

?a、螞蟻在眾多路徑中轉(zhuǎn)移路線的選擇規(guī)則。

?b、全局化信息素更新規(guī)則。信息素更新的實(shí)質(zhì)就是人工螞蟻根據(jù)真實(shí)螞蟻在訪問過的邊上留下的信息素和蒸發(fā)的信息素來模擬真實(shí)信息素數(shù)量的變化，從而使得越好的解得到越多的增強(qiáng)。這就形成了一種自催化強(qiáng)化學(xué)習(xí)(Autocatalytic Reinforcement Learning)的正反饋機(jī)制。

1、描述：螞蟻數(shù)量m；城市之間的信息素矩陣pheromone；每次迭代的m個螞蟻的最短路徑 ? ?BestLength；最佳路徑BestTour。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 每只螞蟻都有 ：禁忌表(Tabu)存儲已訪問過的城市，允許訪問的城市表(Allowed)存儲還可以訪問的城市，矩陣（ Delta ）來存儲它在一個循環(huán)（或者迭代）中給所經(jīng)過的路徑釋放的信息素。

2、 狀態(tài)轉(zhuǎn)移概率 ：在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(tài)轉(zhuǎn)移概率。在t時刻螞蟻k由元素（城市）i轉(zhuǎn)移到元素（城市）j的狀態(tài)轉(zhuǎn)移概率：

τij (t) ：時刻路徑(i, j)上的信息量。ηij=1/dij ：啟發(fā)函數(shù)。

α為信息啟發(fā)式因子 ，表示軌跡的相對重要性，反映了螞蟻在運(yùn)動過程中積累的信息在螞蟻運(yùn)動時所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)；

β為期望啟發(fā)式因子 ，表示能見度的相對重要性，反映螞蟻在運(yùn)動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；

3、 息素更新規(guī)則 ：

ρ表示信息素?fù)]發(fā)系數(shù)；Δτij(t)表示本次循環(huán)中路徑(i, j)上的信息素增量，初始時刻Δτij(t) =0。

4、三種信息增量計算方法：

區(qū)別：第一種利用了全局信息，在走一圈后更新。二、三中都利用的是局部信息。通常使用第一種。

5、TSP中流程圖

蟻群算法求函數(shù)最大值

這里使用蟻群算法求函數(shù)的最大值，函數(shù)是：

步驟如下：

下面是主函數(shù)：

程序運(yùn)行結(jié)果繪圖如下，其中藍(lán)色點(diǎn)為第一代蟻群，紅色為最后一代蟻群：

函數(shù)說明如下：

下面計算函數(shù)的狀態(tài)轉(zhuǎn)移概率，進(jìn)行局部搜索和全局搜索：

之后約束邊界：

最后進(jìn)行選擇：

初始化蟻群函數(shù)：

計算目標(biāo)函數(shù)值函數(shù)：

繪制函數(shù)圖像函數(shù)：

蟻群算法求解TSP問題遇到“索引超出矩陣維度?！钡膯栴}跪求大神能解答

你檢查一下坐標(biāo)矩陣是否出現(xiàn)了重復(fù)數(shù)值。比如你給的例子中C矩陣的第二個和第三個數(shù)值就重復(fù)了。

蟻群算法JAVA版

說明：信息素權(quán)重，路徑權(quán)重和信息素蒸發(fā)率對最后的結(jié)果影響很大，需要微調(diào)。

目前發(fā)現(xiàn)2 / 5 / 0.5 能達(dá)到稍微讓人滿意的效果。本程序離完美的ACO還差很遠(yuǎn)，僅供參考。

本蟻群算法為AS算法。

用法：

1.new一個對象

ACOforTSP tsp = new ACPforTSP(tsp數(shù)據(jù)文件名,迭代次數(shù)，螞蟻數(shù)量，信息素權(quán)重，路徑權(quán)重，信息素蒸發(fā)率）;

2.用go()方法運(yùn)行

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;

//距離的倒數(shù)表

private double[][] heuristic;

//啟發(fā)信息表

private double[][] pheromone;

//權(quán)重

private int alpha, beta;

//迭代的次數(shù)

private int iterationTimes;

//螞蟻的數(shù)量

private int numbersOfAnt;

//蒸發(fā)率

private double rate;

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

//加載文件

this.initializeData(file);

//初始化參數(shù)

this.iterationTimes = iterationTimes;

//設(shè)置螞蟻數(shù)量

this.numbersOfAnt = numbersOfAnt;

//設(shè)置權(quán)重

this.alpha = alpha;

this.beta = beta;

//設(shè)置蒸發(fā)率

this.rate = rate;

}

private void initializeData(String filename) {

//定義內(nèi)部類

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保存讀取的坐標(biāo)信息

HashMapInteger, City map = new HashMapInteger, 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];

//分配距離倒數(shù)矩陣存儲空間

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

//計算距離倒數(shù)，并存入距離倒數(shù)矩陣

heuristic[i][j] = 1 / distance[i][j];

//初始化信息素矩陣

pheromone[i][j] = 1;

}

}

} catch (Exception exception) {

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

}

}

class Ant {

//已訪問城市列表

private boolean[] visited;

//訪問順序表

private int[] tour;

//已訪問城市的個數(shù)

private int n;

//總的距離

private double total;

Ant() {

//給訪問順序表分配空間

tour = new int[distance.length+1];

//已存入城市數(shù)量為n，剛開始為0

n = 0;

//將起始城市1,放入訪問結(jié)點(diǎn)順序表第一項(xiàng)

tour[++n] = 1;

//給已訪問城市結(jié)點(diǎn)分配空間

visited = new boolean[distance.length];

//第一個城市為出發(fā)城市，設(shè)置為已訪問

visited[tour[n]] = true;

}

private int chooseCity() {

//用來random的隨機(jī)數(shù)

double m = 0;

//獲得當(dāng)前所在的城市號放入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);

}

}

//保存隨機(jī)到的數(shù)

double p = m * random();

//尋找被隨機(jī)到的城市

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;

//將選取到的城市標(biāo)記為已訪問

visited[p] = true;

}

//回到起點(diǎn)

total += distance[tour[1]][tour[n]];

//將起點(diǎn)加入訪問順序表的最后

tour[++n] = tour[1];

}

private void releasePheromone() {

//釋放信息素的大小

double t = 1/total;

//釋放信息素

for (int i=1;itour.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];

//新建螞蟻數(shù)組，用來引用所創(chuàng)建的螞蟻

Ant[] ant = new Ant[numbersOfAnt];

//進(jìn)行iterationTimes次迭代

while (iterationTimes != 0) {

//初始化新的一批螞蟻（這里用構(gòu)造新的螞蟻代替重置螞蟻狀態(tài)）

for (int i=0; inumbersOfAnt; i++) {

ant[i] = new Ant();

}

//進(jìn)行一次迭代（即讓所有的螞蟻構(gòu)建一條路徑）

for (int i=0; inumbersOfAnt; i++) {

ant[i].constructSolution();

//如果螞蟻構(gòu)建的路徑長度比上次最好的還好，那么保存這個長度和它所走的路徑

if (ant[i].totalbestTotal) {

bestTotal = ant[i].total;

System.arraycopy(ant[i].tour, 1, bestTour, 1, bestTour.length-1);

}

}

//蒸發(fā)信息素

evaporatePheromone();

//釋放信息素

for (int i=0; inumbersOfAnt; i++) {

ant[i].releasePheromone();

}

//報告本次迭代的信息

System.out.format("本次為倒數(shù)第%d次迭代,當(dāng)前最優(yōu)路徑長度為%10.2f\n",iterationTimes,bestTotal);

//迭代總數(shù)減去1，進(jìn)行下次迭代

iterationTimes--;

}

//輸出最好的路徑長度

System.out.format("得到的最優(yōu)的路徑長度為:%10.2f\n",bestTotal);

//輸出最好的路徑

System.out.println("最優(yōu)路徑如下：");

for (int i=1; ibestTour.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;

}

}

}

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

該程序試圖對具有31個城市的VRP進(jìn)行求解，已知的最優(yōu)解為784.1，我用該程序只能優(yōu)化到810左右，應(yīng)該是陷入局部最優(yōu)，但我不知問題出在什么地方。請用過蟻群算法的高手指教。

蟻群算法的matlab源碼，同時請指出為何不能優(yōu)化到已知的最好解

%

%

% the procedure 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; % 螞蟻數(shù)

alpha=1;

belta=4;% 決定tao和miu重要性的參數(shù)

lmda=0;

rou=0.9; %衰減系數(shù)

q0=0.95;

% 概率

tao0=1/(31*841.04);%初始信息素

Q=1;% 螞蟻循環(huán)一周所釋放的信息素

defined_phrm=15.0; % initial pheromone level value

QV=100; % 車輛容量

vehicle_best=round(sum(g)/QV)+1; %所完成任務(wù)所需的最少車數(shù)

V=40;

% 計算兩點(diǎn)的距離

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; % 由螞蟻產(chǎn)生的路徑數(shù)量

M_vehicle=500;

t=0; %最佳路徑數(shù)組的元素數(shù)為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);%對所經(jīng)弧進(jìn)行局部更新

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; % 如果當(dāng)前點(diǎn)為車場,將當(dāng)前路徑中的已訪問用戶去掉后,開始產(chǎn)生新路徑

if setdiff(part_sol,1)~=[];

n_sol=n_sol+1; % 表示產(chǎn)生的路徑數(shù),n_sol=1,2,3,..5,6...,超過5條對其費(fèi)用加上車輛的派遣費(fèi)用

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','當(dāng)前的用戶需求量是:');

fprintf(fid,'%i\n',temp_load);

fprintf(fid,'------------------------------\n');

fclose(fid);

% 對所得路徑進(jìn)行路徑內(nèi)3-opt優(yōu)化

final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產(chǎn)生的路徑傳給一個數(shù)組

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)==[];% 產(chǎn)生最后一條終點(diǎn)不為1的路徑

n_sol=n_sol+1;

nl=length(part_sol);

part_sol(nl+1)=1;%將路徑的最后1位補(bǔ)1

% 對所得路徑進(jìn)行路徑內(nèi)3-opt優(yōu)化

final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產(chǎn)生的路徑傳給一個數(shù)組

temp(t+nt)=final_sol(nt);

end;

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

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; % 產(chǎn)生最小費(fèi)用的代數(shù)

best_ant=i; %產(chǎn)生最小費(fèi)用的螞蟻

best_solution=temp;

end;

if i==m; %如果所有螞蟻均完成一次循環(huán)，，則用最佳費(fèi)用所對應(yīng)的路徑對弧進(jìn)行整體更新

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','當(dāng)前的用戶需求量是:',temp_load);

fprintf(fid,'%s %f\n','總費(fèi)用是:',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;

我現(xiàn)在也在研究它,希望能共同進(jìn)步.建義可以看一下段海濱的關(guān)于蟻群算法的書.講的不錯,李士勇的也可以,還有一本我在圖書館見過,記不得名字了.

螞蟻算法原理及實(shí)現(xiàn)代碼

蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。

為什么小小的螞蟻能夠找到食物？他們具有智能么？設(shè)想，如果我們要為螞蟻設(shè)計一個人工智能的程序，那么這個程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因?yàn)槌绦虻腻e誤也許會讓你前功盡棄。這是多么不可思議的程序！太復(fù)雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。

然而，事實(shí)并沒有你想得那么復(fù)雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什么這么簡單的程序會讓螞蟻干這樣復(fù)雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進(jìn)行決策，這樣，在蟻群這個集體里，復(fù)雜性的行為就會凸現(xiàn)出來。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細(xì)說明：

1、范圍：

螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。

2、環(huán)境：

螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。

3、覓食規(guī)則：

在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點(diǎn)移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。

4、移動規(guī)則：

每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時候，螞蟻會按照自己原來運(yùn)動的方向慣性的運(yùn)動下去，并且，在運(yùn)動的方向有一個隨機(jī)的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過了，它就會盡量避開。

5、避障規(guī)則：

如果螞蟻要移動的方向有障礙物擋住，它會隨機(jī)的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。

7、播撒信息素規(guī)則：

每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。

根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實(shí)際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。

說了這么多，螞蟻究竟是怎么找到食物的呢？

在沒有螞蟻找到食物的時候，環(huán)境沒有有用的信息素，那么螞蟻為什么會相對有效的找到食物呢？這要?dú)w功于螞蟻的移動規(guī)則，尤其是在沒有信息素時候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個前方是隨機(jī)固定的一個方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動下去，而是有一個隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什么單個螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。

當(dāng)然，在有一只螞蟻找到了食物的時候，其他螞蟻會沿著信息素很快找到食物的。

螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說是計算機(jī)時鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞蟻多，這也無關(guān)緊要）。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實(shí)際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會被吸引過來。

引申:

跟著螞蟻的蹤跡，你找到了什么？通過上面的原理敘述和實(shí)際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡單行為規(guī)則，而這些規(guī)則綜合起來具有下面兩個方面的特點(diǎn)：

1、多樣性

2、正反饋

多樣性保證了螞蟻在覓食的時候不置走進(jìn)死胡同而無限循環(huán)，正反饋機(jī)制則保證了相對優(yōu)良的信息能夠被保存下來。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學(xué)習(xí)強(qiáng)化能力。正反饋的力量也可以比喻成權(quán)威的意見，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造性，正是這兩點(diǎn)小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來了。

引申來講，大自然的進(jìn)化，社會的進(jìn)步、人類的創(chuàng)新實(shí)際上都離不開這兩樣?xùn)|西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。如果多樣性過剩，也就是系統(tǒng)過于活躍，這相當(dāng)于螞蟻會過多的隨機(jī)運(yùn)動，它就會陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機(jī)制過強(qiáng)，那么系統(tǒng)就好比一潭死水。這在蟻群中來講就表現(xiàn)為，螞蟻的行為過于僵硬，當(dāng)環(huán)境變化了，螞蟻群仍然不能適當(dāng)?shù)恼{(diào)整。

既然復(fù)雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點(diǎn)，那么也許你會問這些規(guī)則是哪里來的？多樣性和正反饋又是哪里來的？我本人的意見：規(guī)則來源于大自然的進(jìn)化。而大自然的進(jìn)化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因?yàn)槟切┎荒軌蜻m應(yīng)環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！

!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" ""

html xmlns=""HEAD

meta http-equiv="Content-Type" content="text/html; charset=gb2312" /

style

.ant{

position:absolute;

background-color:#000000;

overflow:hidden;

width:2px;

height:2px;

}

.food{

position:absolute;

background-color:#0000ff;

overflow:hidden;

width:2px;

height:2px;

}

.nest{

position:absolute;

background-color:#ff0000;

overflow:hidden;

width:2px;

height:2px;

}

/style

script type="text/JavaScript"

//============================

//系統(tǒng)參數(shù)初始化

//----------------------------

//生命體數(shù)量與軌跡長度

Unit=10;Path=30;

//生命體速度上下限

v0=2;vM=10;

//生命體加速度變化范圍

Kr=0.1;Kv=0.1*(vM-v0);

//生命體運(yùn)動范圍

x0=0;xM=document.documentElement.clientWidth;

y0=0;yM=document.documentElement.clientHeight;

//生命體出生地(巢穴)

xi0=x0+(xM-x0)*Math.random();

yi0=y0+(yM-y0)*Math.random();

str0='div class="ant" style="left:'+xi0+';top:'+yi0+';"/div';

//食物所在地

xf=x0+(xM-x0)*Math.random();

yf=y0+(yM-y0)*Math.random();

//氣味感知范圍

R_2=5*5;

//============================

var r=new Array();

var v=new Array();

var dr=new Array();

var dv=new Array();

var x=new Array();

var y=new Array();

var life=new Array();

//單擊暫停

var xi0,yi0,xf,yf;

var Time0,str0;

window.status='pause';

function document.onclick(){

if(window.status=='pause'){

window.status=0;

nest.style.left=xi0;

nest.style.top=yi0;

food.style.left=xf;

food.style.top=yf;

//測試初始化時間用

Time0=(new Date()).getTime();

init(0);

}else{

window.status='pause';

}

}

//窗口大小調(diào)整后刷新頁面以調(diào)整系統(tǒng)參數(shù)

function window.onresize(){

// window.location.href=document.location;

}

//初始化函數(shù)

function init(i){

if(window.status!='pause'iUnit){

if(!life){

document.body.appendChild(life=document.createElement(str0));

x=xi0;

y=yi0;

r=Math.random();

v=1/Math.random();

dr=Kr*Math.random();

dv=Kv*Math.random();

}

Move(i);

window.status=i+1;

setTimeout('init('+(i+1)+')',i);

// }else{

// alert('生成耗時：'+((new Date()).getTime()-Time0)+'ms');

}

}

//運(yùn)動函數(shù)

Total=Unit*Path;

P2=2*Math.PI;

function Move(i){

if(window.status!='pause'){

k=i%Unit;

X=x[k];

Y=y[k];

R=r[k];

V=v[k];

if(!life){

str='div class="ant" style="left:'+X+';top:'+Y+';"/div';

document.body.appendChild(life=document.createElement(str));

}

obj=life;

R+=dr[k]*(2*Math.random()-1);

V+=dv[k]*(2*Math.random()-1);

X+=Math.sin(P2*R)*V;

Y+=Math.cos(P2*R)*V;

//遇到食物原路返回并減小角度變化

distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);

if(distanceR_2){

R+=0.5;

r/=2;

v*=2;

}

distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);

if(distanceR_2){

R+=0.5;

r/=2;

v*=2;

}

/*----------------------------------

/*================================*/

//碰撞邊界反彈

R=(Xx0||XxM)?-R:R;

R=(Yy0||YyM)?0.5-R:R;

X=x[k]+Math.sin(P2*R)*V;

Y=y[k]+Math.cos(P2*R)*V;

/*================================*/

//溢出邊界重生(類似流星效果)

if(Xx0||XxM||Yy0||YyM){

X=xi0;

Y=yi0;

}

/*----------------------------------

/*================================*/

//邊界限制

x[k]=X=(Xx0)?x0:(XxM)?xM-2:X;

y[k]=Y=(Yy0)?y0:(YyM)?yM-2:Y;

r[k]=R1?R-1:R0?R+1:R;

v[k]=V=(Vv0)?v0:((VvM)?V:vM);

/*================================*/

obj.style.left=x[k]=X;

obj.style.top=y[k]=Y;

setTimeout('Move('+(i+Unit)%Total+')',Unit);

}

}

//根據(jù)瀏覽器自動加載動畫

switch(navigator.appName.toLowerCase()){

case "netscape":

window.addEventListener("load",document.onclick,false);

break;

case "microsoft internet explorer":

default:

window.attachEvent("onload",document.onclick);

break;

}

/script

/head

body scroll="no"

div id="food" class="food"/div

div id="nest" class="nest"/div

/body

/html

本文名稱：蟻群算法程序代碼java 蟻群算法csdn
文章地址：http://muchs.cn/article8/docdsip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、搜索引擎優(yōu)化、品牌網(wǎng)站設(shè)計、云服務(wù)器、網(wǎng)站營銷、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)