蟻群算法代碼就java 蟻群算法偽代碼
蟻群算法求解TSP問題遇到“索引超出矩陣維度?！钡膯栴}跪求大神能解答
你檢查一下坐標矩陣是否出現(xiàn)了重復數(shù)值。比如你給的例子中C矩陣的第二個和第三個數(shù)值就重復了。
成都創(chuàng)新互聯(lián)主營南山網(wǎng)站建設的網(wǎng)絡公司,主營網(wǎng)站建設方案,成都App定制開發(fā),南山h5微信平臺小程序開發(fā)搭建,南山網(wǎng)站營銷推廣歡迎南山等地區(qū)企業(yè)咨詢
蟻群算法JAVA版
說明：信息素權重，路徑權重和信息素蒸發(fā)率對最后的結果影響很大，需要微調(diào)。
目前發(fā)現(xiàn)2 / 5 / 0.5 能達到稍微讓人滿意的效果。本程序離完美的ACO還差很遠，僅供參考。
本蟻群算法為AS算法。
用法：
1.new一個對象
ACOforTSP tsp = new ACPforTSP(tsp數(shù)據(jù)文件名,迭代次數(shù)，螞蟻數(shù)量，信息素權重，路徑權重，信息素蒸發(fā)率）;
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;
//距離的倒數(shù)表
private double[][] heuristic;
//啟發(fā)信息表
private double[][] pheromone;
//權重
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ù)量
this.numbersOfAnt = numbersOfAnt;
//設置權重
this.alpha = alpha;
this.beta = beta;
//設置蒸發(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保存讀取的坐標信息
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,放入訪問結點順序表第一項
tour[++n] = 1;
//給已訪問城市結點分配空間
visited = new boolean[distance.length];
//第一個城市為出發(fā)城市，設置為已訪問
visited[tour[n]] = true;
}
private int chooseCity() {
//用來random的隨機數(shù)
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);
}
}
//保存隨機到的數(shù)
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;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];
//進行iterationTimes次迭代
while (iterationTimes != 0) {
//初始化新的一批螞蟻（這里用構造新的螞蟻代替重置螞蟻狀態(tài)）
for (int i=0; inumbersOfAnt; i++) {
ant[i] = new Ant();
}
//進行一次迭代（即讓所有的螞蟻構建一條路徑）
for (int i=0; inumbersOfAnt; i++) {
ant[i].constructSolution();
//如果螞蟻構建的路徑長度比上次最好的還好，那么保存這個長度和它所走的路徑
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次迭代,當前最優(yōu)路徑長度為%10.2f\n",iterationTimes,bestTotal);
//迭代總數(shù)減去1，進行下次迭代
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;
}
}
}
螞蟻算法原理及實現(xiàn)代碼
蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型技術。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。
為什么小小的螞蟻能夠找到食物？他們具有智能么？設想，如果我們要為螞蟻設計一個人工智能的程序，那么這個程序要多么復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當?shù)牡匦谓o它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那么需要計算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多么不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。
然而，事實并沒有你想得那么復雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什么這么簡單的程序會讓螞蟻干這樣復雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實上，每只螞蟻并不是像我們想象的需要知道整個世界的信息，他們其實只關心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策，這樣，在蟻群這個集體里，復雜性的行為就會凸現(xiàn)出來。這就是人工生命、復雜性科學解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細說明：
1、范圍：
螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。
2、環(huán)境：
螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。
3、覓食規(guī)則：
在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。
4、移動規(guī)則：
每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開。
5、避障規(guī)則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。
7、播撒信息素規(guī)則：
每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。
根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。
說了這么多，螞蟻究竟是怎么找到食物的呢？
在沒有螞蟻找到食物的時候，環(huán)境沒有有用的信息素，那么螞蟻為什么會相對有效的找到食物呢？這要歸功于螞蟻的移動規(guī)則，尤其是在沒有信息素時候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個前方是隨機固定的一個方向），而不是原地無謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機性，雖然有了固定的方向，但它也不能像粒子一樣直線運動下去，而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什么單個螞蟻在復雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當然，在有一只螞蟻找到了食物的時候，其他螞蟻會沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的？這一是要歸功于信息素，另外要歸功于環(huán)境，具體說是計算機時鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞蟻多，這也無關緊要）。當螞蟻沿著一條路到達終點以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會被吸引過來。
引申:
跟著螞蟻的蹤跡，你找到了什么？通過上面的原理敘述和實際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡單行為規(guī)則，而這些規(guī)則綜合起來具有下面兩個方面的特點：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環(huán)，正反饋機制則保證了相對優(yōu)良的信息能夠被保存下來。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現(xiàn)的創(chuàng)造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現(xiàn)出來了。
引申來講，大自然的進化，社會的進步、人類的創(chuàng)新實際上都離不開這兩樣東西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統(tǒng)過于活躍，這相當于螞蟻會過多的隨機運動，它就會陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機制過強，那么系統(tǒng)就好比一潭死水。這在蟻群中來講就表現(xiàn)為，螞蟻的行為過于僵硬，當環(huán)境變化了，螞蟻群仍然不能適當?shù)恼{(diào)整。
既然復雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點，那么也許你會問這些規(guī)則是哪里來的？多樣性和正反饋又是哪里來的？我本人的意見：規(guī)則來源于大自然的進化。而大自然的進化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環(huán)境的多樣性與正反饋的結合都已經(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);
//生命體運動范圍
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');
}
}
//運動函數(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 蟻群算法偽代碼
分享鏈接：http://muchs.cn/article38/hjsgsp.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站改版、軟件開發(fā)、、網(wǎng)站建設、域名注冊
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 域名注冊可以賺錢嗎？怎么注冊域名賺錢？ 2021-02-27
- 企業(yè)網(wǎng)站建設沒有域名 選擇域名注冊時多考慮這些小心機 2022-05-21
- 域名過期后多少天可以注冊？企業(yè)域名注冊過期了怎么辦？ 2021-05-26
- 注冊域名后接下來怎么建站？ 2016-05-19
- 域名注冊成功后最好做次域名檢查。 2019-08-08
- 注冊域名需要注意什么 2016-09-15
- 企業(yè)網(wǎng)站建設中的域名注冊解析及服務器配置 2021-02-21
- .SITE域名注冊量突破100萬 2021-02-14
- 域名注冊使用中需要了解的幾個問題 2021-02-08
- Radix注冊局.SITE域名注冊量突破100萬 2021-02-01
- 域名注冊中需要遵循的一些原則 2021-02-13
- 新頂級域名注冊去哪兒？ 2022-07-15