waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          http://qzone.qq.com/blog/5128646-1214662948
          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[j] = map.get(i).getDistance(map.get(j));
          //計算距離倒數,并存入距離倒數矩陣
          heuristic[j] = 1 / distance[j];
          //初始化信息素矩陣
          pheromone[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) {
          m += pow(pheromone[j], alpha) * pow(heuristic[j], beta);
          }
          }

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

          if (!visited) {

          k += pow(pheromone[j], alpha) * pow(heuristic[j], 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][tour[i+1]] += t;
          pheromone[tour[i+1]][tour] += 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 = new Ant();
          }

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

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

          bestTotal = ant.total;
          System.arraycopy(ant.tour, 1, bestTour, 1, bestTour.length-1);
          }
          }

          //蒸發信息素
          evaporatePheromone();

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

          ant.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);
          }
          }

          private void evaporatePheromone() {

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

          pheromone[j] *= 1-rate;
          }

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

          ACOforTSP.java
          posted on 2009-04-15 23:12 weesun一米陽光 閱讀(1689) 評論(3)  編輯  收藏 所屬分類: JAVA源碼總結備用

          評論

          # re: 蟻群算法java實現[收藏] 2010-05-22 16:07 dsaf
          為什么代碼是錯誤的?是故意做錯的?  回復  更多評論
            

          # re: 蟻群算法java實現[收藏] 2010-05-22 16:08 dsaf
          為什么數組的中括號被去掉了呢?

          為什么呢?

          為什么呢?


          為什么呢?


          為什么呢?


          為什么呢?


          為什么呢?

            回復  更多評論
            

          # re: 蟻群算法java實現[收藏] 2010-05-22 18:42 nm1504
          你好,這段代碼不是我寫的,也是我收藏的,呵呵!只是看算法的基本實現吧,至于是否能運行,也是要自己去實踐的才行!  回復  更多評論
            

          主站蜘蛛池模板: 噶尔县| 洪泽县| 忻州市| 靖宇县| 麟游县| 潞城市| 集安市| 龙胜| 玉田县| 井冈山市| 勐海县| 龙山县| 金华市| 股票| 军事| 三台县| 大宁县| 同心县| 鹰潭市| 罗甸县| 长海县| 合山市| 磐石市| 江北区| 朝阳区| 杭锦后旗| 南溪县| 柯坪县| 鄂托克旗| 扶余县| 扶沟县| 巴马| 湟源县| 尖扎县| 徐水县| 石河子市| 天峻县| 兴海县| 公安县| 高碑店市| 淳化县|