用蚁群算法解决TSP问题

package TSP; import java.io.File; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class ACO { static double[][] DT = null;//距离矩阵 static int antSum = 32;//蚂蚁数量 static double[][] pheromonetable = null;//信息素矩阵 static double[][] enlighten = null;//启发函数矩阵 static int alpha = 1; static int beta = 5; static double rho = 0.8; static double Q = 1; static int itermax = 200;//迭代次数 static int citySum = 0;//城市数量 static double constant = 1;// 初始信息素 //一个类实例化后才生成 static class ant implements Cloneable{ double length = 0; int[] path = new int[citySum+1]; int[] mark = new int[citySum]; public void init() { for(int i=0; i<citySum; i++) { this.mark[i] = 0; this.path[i+1] = 0; } this.length = 0; this.mark[this.path[0]] = 1; } public int curCity() { for(int i=1; i<this.path.length; i++) { if(this.path[i]==0) { return this.path[i-1]; } } return 0; } public Object clone(){ ant at = null; try { at = (ant) super.clone(); } catch (CloneNotSupportedException e) { // TODO Auto-generated catch block e.printStackTrace(); } at.mark = new int[citySum]; for(int r=0; r<citySum; r++){ at.mark[r] = this.mark[r]; } at.path = new int[citySum+1]; for(int r=0; r<=citySum; r++){ at.path[r] = this.path[r]; } return at; } @Override public String toString() { return "ant [length=" + length + ", path=" + Arrays.toString(path) + ", mark=" + Arrays.toString(mark) + "]"; } } static List<ant> antList = null; static void init() { antList = new ArrayList<ant>(); File file = new File("E:\\Java\\arithmetic\\src\\resource\\att48.xls"); List<city> cityList = inputData.input_att48(file); System.out.println("city [城市编号 城市X坐标 城市Y坐标]"); for(int i=0; i<citySum; i++) { System.out.println(cityList.get(i).toString()); } DT = new double[citySum][citySum]; pheromonetable = new double[citySum][citySum]; enlighten = new double[citySum][citySum]; for(int i=0; i<citySum; i++) { for(int j=i; j<citySum; j++) { if(i==j) { DT[i][j] = 0; pheromonetable[i][j] = constant; enlighten[i][j] = Double.MIN_VALUE; } else { double dertX = cityList.get(i).getX()-cityList.get(j).getX(); double dertY = cityList.get(i).getY()-cityList.get(j).getY(); DT[i][j] = Math.sqrt(dertX*dertX + dertY*dertY); DT[j][i] = DT[i][j]; pheromonetable[i][j] = pheromonetable[j][i] = constant; enlighten[i][j] = enlighten[j][i] = 1.0/DT[i][j]; } } } for(int i=0; i<antSum; i++) { ant temp = new ant(); temp.path[0] = (int) (Math.random()*citySum); temp.mark[temp.path[0]] = 1; antList.add(temp); } } //选择城市 static void selectCity() { //遍历每一个蚂蚁 for(int i=0; i<antSum; i++) { //连续访问剩下的城市citySum-1个 for(int s=1; s<citySum; s++) { int o = antList.get(i).path[s-1];//o是蚂蚁当前访问的城市//在变化 double t2 = 0;//选择概率函数的分母 // System.out.println(citySum); for(int k=0; k<citySum; k++) { if(antList.get(i).mark[k]==0) { t2 += Math.pow(pheromonetable[o][k], alpha)*Math.pow(enlighten[o][k], beta); } } //计算选择函数（创建一个轮盘） double[][] Poj = new double[citySum][2];//每个城市的选择概率,第二维表示一个区间 double l = 0; double r = 0; for(int j=0; j<citySum; j++) { double t1 = 0;//选择概率函数的分子 if(antList.get(i).mark[j]==0) { t1 += Math.pow(pheromonetable[o][j], alpha)*Math.pow(enlighten[o][j], beta); double p = t1/t2; r = l + p; Poj[j][0] = l; Poj[j][1] = r; l = r; } } //选择下一个访问的城市 double p = Math.random(); // int c = 0; for(int j=0; j<citySum; j++) { if(p>Poj[j][0] && p<=Poj[j][1] && antList.get(i).mark[j]==0) {//(a,b],左开右闭 antList.get(i).path[s] = j; antList.get(i).length += DT[o][j]; antList.get(i).mark[j] = 1; // c = 5; break; } } } // 回到出发点 antList.get(i).length += DT[antList.get(i).path[citySum-1]][antList.get(i).path[0]]; antList.get(i).path[citySum] = antList.get(i).path[0]; } } // 更新信息矩阵表 static void updatePeromone() { for(int i=0; i<citySum; i++) { for(int j=0; j<citySum; j++) { double dreta = 0; for(int k=0; k<antList.size(); k++) { dreta += Q/antList.get(k).length; } pheromonetable[i][j] = rho*pheromonetable[i][j] + dreta; } } } static ant bestAnt() { ant t = new ant(); t.length = Double.MAX_VALUE; for(int i=0; i<antList.size(); i++) { if(antList.get(i).length < t.length) { t = (ant) antList.get(i).clone(); } } return t; } @SuppressWarnings("resource") public static void main(String[] args) { System.out.println("----------------蚁群算法解决TSP问题----------------"); Scanner in = new Scanner(System.in); while(true) { System.out.println(); System.out.println("请输入城市数："); citySum = in.nextInt(); if(citySum > 48) { System.out.println("样例有限，城市数不能超过48！"); return; } //--------- init(); if(citySum > 25) { System.out.println("请稍等......"); } int iter = 0; ant ans = new ant(); ans.length = Double.MAX_VALUE; while(iter++ < itermax) { //清空禁忌表 for(int i=0; i<antList.size(); i++) { antList.get(i).init(); } selectCity(); updatePeromone(); ant t = bestAnt(); if(t.length < ans.length) { ans = (ant) t.clone(); } // System.out.println(t.toString()); } // ant ans = bestAnt(); //---------------- System.out.println("旅行路线："); System.out.print(ans.path[0]); for(int i=1; i<=citySum; i++) { System.out.print("->"); System.out.print(ans.path[i]); } System.out.println(); System.out.print("路线长度："); System.out.println(ans.length); } } }