import java.io.BufferedReader;
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; /** * 蚁群优化算法，用来求解TSP问题 * * */ public class ACO { // 定义蚂蚁群 Ant[] ants; int antcount;// 蚂蚁的数量 int[][] distance;// 表示城市间距离 double[][] tao;// 信息素矩阵 int citycount;// 城市数量 int[] besttour;// 求解的最佳路径 int bestlength;// 求的最优解的长度 /** * 初始化函数 * * @param filename * tsp数据文件 * @param antnum * 系统用到蚂蚁的数量 * @throws 如果文件不存在则抛出异常 */ public void init(String filename, int antnum) throws FileNotFoundException, IOException { antcount = antnum; ants = new Ant[antcount]; citycount = 48; for (int i = 0; i < ants.length; i++) { ants[i] = new Ant(citycount); } // 读取数据 int[] x; int[] y; String strbuff; BufferedReader tspdata = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); distance = new int[citycount][citycount]; x = new int[citycount]; y = new int[citycount]; for (int citys = 0; citys < citycount; citys++) { strbuff = tspdata.readLine(); String[] strcol = strbuff.split(" "); x[citys] = Integer.valueOf(strcol[1]); y[citys] = Integer.valueOf(strcol[2]); } tao = new double[citycount][citycount]; for (int i = 0; i < x.length; i++) { for (int j = 0; j < y.length; j++) { distance[i][j] = (int) Math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); tao[i][j] = 1.0; } } besttour = new int[citycount]; bestlength = 0; for (int i = 0; i < citycount; i++) { besttour[i] = i; } for (int i = 0; i < citycount; i++) { bestlength += distance[besttour[i]][besttour[(i + 1) % besttour.length]]; } } /** * ACO的运行过程 * * @param maxgen * ACO的最多循环次数 * */ public void run(int maxgen) { for (int i = 0; i < maxgen; i++) { for (int antIndex = 0; antIndex < ants.length; antIndex++) { ants[antIndex].RandomSelectCity(citycount); for (int cityIndex = 0; cityIndex < citycount - 1; cityIndex++) { ants[antIndex].SelectNextCity(cityIndex, tao, distance); } ants[antIndex].CalTourLength(distance); if (ants[antIndex].tourlength < bestlength) { bestlength = ants[antIndex].tourlength; for (int c = 0; c < citycount; c++) { besttour[c] = ants[antIndex].tour[c]; } System.out.println("找到了一条更好的路径，路径长度是：" + bestlength); } } UpdateTao(); } } /** * 更新信息素矩阵 */ private void UpdateTao() { double rou = 0.2; for (int i = 0; i < citycount; i++) { for (int j = 0; j < citycount; j++) { tao[i][j] = rou * tao[i][j]; } } for (int antIndex = 0; antIndex < ants.length; antIndex++) { for (int cityIndex = 0; cityIndex < citycount; cityIndex++) { int firstCity = ants[antIndex].tour[cityIndex]; int secondCtiy = ants[antIndex].tour[(cityIndex + 1) % citycount]; tao[firstCity][secondCtiy] += 1.0 / ants[antIndex].tourlength; tao[secondCtiy][firstCity] += 1.0 / ants[antIndex].tourlength; } } } /** * 输出程序运行结果 */ public void ReportResult() { System.out.println("最优路径长度是" + bestlength); }}
import java.io.FileNotFoundException;import java.io.IOException;import java.util.logging.Level;import java.util.logging.Logger;/** * 主程序 调用ACO求解问题 * */public class Main { /** * @param args * the command line arguments */ public static void main(String[] args) { // TODO code application logic here ACO aco; aco = new ACO(); try { aco.init("e://att48.tsp", 50); aco.run(4000); aco.ReportResult(); } catch (FileNotFoundException ex) { Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex); } catch (IOException ex) { Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex); } }}import java.util.Random;/** * 蚂蚁类 * */public class Ant { /** * 蚂蚁获得的路径 */ public int[] tour; // unvisitedcity 取值是0或1， // 1表示没有访问过，0表示访问过 int[] unvisitedcity; /** * 蚂蚁获得的路径长度 */ public int tourlength; int citys; Random random = new Random(); int currentCityIndex; public Ant(int n) { citys = n; tour = new int[n]; unvisitedcity = new int[n]; for (int i = 0; i < n; i++) { unvisitedcity[i] = 1; } } /** * 随机分配蚂蚁到某个城市中 同时完成蚂蚁包含字段的初始化工作 * * @param citycount * 总的城市数量 */ public void RandomSelectCity(int citycount) { for (int i = 0; i < citycount; i++) { unvisitedcity[i] = 1; } int startCity = random.nextInt(citys); tour[0] = startCity; currentCityIndex = 0; unvisitedcity[startCity] = 0; } /** * 选择下一个城市 * * @param index * 需要选择第index个城市了 * @param tao * 全局的信息素信息 * @param distance * 全局的距离矩阵信息 */ public void SelectNextCity(int index, double[][] tao, int[][] distance) { double[] cityp = new double[citys]; double sum = 0; int currentCity = tour[currentCityIndex]; for (int i = 0; i < cityp.length; i++) { if (unvisitedcity[i] == 0) { cityp[i] = 0; } else { cityp[i] = tao[currentCity][i] * tao[currentCity][i] * (1.0 / distance[currentCity][i]); } sum += cityp[i]; } for (int i = 0; i < cityp.length; i++) { cityp[i] = cityp[i] / sum; } double p = random.nextDouble(); sum = 0; for (int i = 0; i < cityp.length; i++) { sum += cityp[i]; if (sum >= p) { unvisitedcity[i] = 0; currentCityIndex++; tour[currentCityIndex] = i; break; } } } /** * 计算蚂蚁获得的路径的长度 * * @param distance * 全局的距离矩阵信息 */ public void CalTourLength(int[][] distance) { tourlength = 0; for (int i = 0; i < tour.length; i++) { tourlength += distance[tour[i]][tour[(i + 1) % tour.length]]; } }}
