蟻群算法解決TSP問題的JAVA實作（二）

3.代碼實作

3.1.代碼下載下傳位址

代碼

3.2.代碼整體結構圖

1. 采用MVC結構，其中vc_1是對model層的一種顯示實作；後續計劃還将加入另一種實作vc_2。
2. 代碼中的所有常量都被寫入static代碼塊中，若無大的改動之後會全部遷移到xml檔案中。

3.2.1.整體結構介紹：

包名	描述
main	程式運作入口
model	model層
vc_1	顯示一次蟻群算法的結果的VC層
tool	用到的工具檔案

3.3.model層

3.3.1.結構圖

3.3.2 model.ACO.java

model層唯一的入口；一個ACO對象隻進行一次蟻群算法的運算，得出一個運算最優解釋。

package model;

import tool.Point;
import model.world.World;

/**
 * 求解TSP問題的蟻周系統
 * @author WangYikai
 */
public class ACO {
    /**
     * int型，循環輪數
     */
    private static final int N_CMAX;

    /**
     * double型，各路徑資訊素強度初始值
     */
    private static final double TAU_INIT;

    /**
     * double型，重新整理資訊素時之前資訊素保留的百分比
     */
    private static final double RHO;

    /**
     * double[][]型，(i, j)代表城市i到城市j的資訊素強度
     */
    private double[][] tau_s;

    /**
     * Round[]型，本次蟻群算法所有實作的輪數
     */
    private Round[] rounds;

    /**
     * int型，蟻群系統時刻
     */
    private int t;

    /**
     * Way型，最佳路徑
     */
    private Way best_way;

    static {
        N_CMAX = ;
        TAU_INIT = ;
        RHO = ;
    }

    public ACO() {
        this.t = ;

        this.tau_s = new double[World.getCITY_ARRAY().length][World.getCITY_ARRAY().length];
        for(int i = ; i < this.tau_s.length; i++) {
            for(int j = ; j < this.tau_s[i].length; j++) {
                if(i == j) {
                    this.tau_s[i][j] = ;
                } else {
                    this.tau_s[i][j] = ACO.TAU_INIT;
                }
            }
        }

        this.rounds = new Round[ACO.N_CMAX];
        for(int i = ; i < this.rounds.length; i++) {
            this.rounds[i] = null;
        }

        this.best_way = null;
    }

    /**
     * 獲得城市坐标資訊
     * @return Point[]型，城市坐标資訊
     */
    public Point[] getCityPoints() {
        Point[] back = new Point[World.getCITY_ARRAY().length];
        for(int i = ; i < back.length; i++) {
            back[i] = World.getCITY_ARRAY()[i].getPoint();
        }
        return back;
    }

    /**
     * 開始蟻群算法的第x輪
     * @param x int型
     */
    public void new_round_x(int x) {
        this.rounds[x] = new Round(this);

        // 重新整理最佳路徑
        if(this.best_way == null || this.best_way.getL() > this.rounds[x].getBest_way().getL()) {
            this.best_way = this.rounds[x].getBest_way();
        }

        //System.out.println(this.best_way.getL());

        // 将該輪的資訊素資訊更新到算法中
        for(int i = ; i < this.tau_s.length; i++) {
            for(int j = ; j < this.tau_s[i].length; j++) {
                this.tau_s[i][j] = ACO.RHO * this.tau_s[i][j] + this.rounds[x].getDelta_tau_s()[i][j];
            }
        }

        // 将本輪結束後的資訊素情況寫回本輪
        double[][] temp = new double[World.getCITY_ARRAY().length][World.getCITY_ARRAY().length];
        for(int i = ; i < temp.length; i++) {
            for(int j = ; j < temp.length; j++) {
                temp[i][j] = this.tau_s[i][j];
            }
        }
        this.rounds[x].setTau_s(temp);
    }

    /**
     * 獲得目前最佳路徑城市id按順序構成的數組，沒有則為null
     * @return int[]型，目前最佳路徑城市id按順序構成的數組
     */
    public int[] getBest_way_id() {
        int[] back = null;
        if(this.best_way != null) {
            back = new int[this.best_way.getWay().length];
            for(int i = ; i < back.length; i++) {
                back[i] = this.best_way.getWay()[i].getId();
            }
        }
        return back;
    }

    /**
     * 獲得曆史上曾出現過的最大資訊素強度
     * @return double型，曆史上曾出現過的最大資訊素強度
     */
    public double getMax_pheromone() {
        double back = ;

        for(int i = ; i < this.rounds.length; i++) {
            if(this.rounds[i] != null) {

                for(int x = ; x < this.rounds[i].getTau_s().length; x++) {
                    for(int y = ; y < this.rounds[i].getTau_s()[x].length; y++) {
                        if(this.rounds[i].getTau_s()[x][y] > back) {
                            back = this.rounds[i].getTau_s()[x][y];
                        }
                    }
                }

            }
        }

        return back;
    }

    public static int getnCmax() {
        return N_CMAX;
    }

    public int getT() {
        return t;
    }

    public void setT(int t) {
        this.t = t;
    }

    public Round[] getRounds() {
        return rounds;
    }

    public double[][] getTau_s() {
        return tau_s;
    }

    public static double getTauInit() {
        return TAU_INIT;
    }

    public Way getBest_way() {
        return best_way;
    }
}
           

3.3.3 model.ChooseCity.java

例如，目前螞蟻在城市0，選擇下一個到訪城市時将判斷每座城市的機率資訊存入該類。

可達城市編号	選擇機率	選擇區間
1	0.3	[0, 0.3)
2	0.2	[0.3, 0.5)
3	0.5	[0.5, 1)

随後産生一個[0, 1)的随機數，該數落在某區間則選擇對應城市。

package model;

import model.world.City;

/**
 * 選擇輔助判斷類
 * @author WangYikai
 */
public class ChooseCity {
    /**
     * City型，待選擇城市
     */
    private final City city;

    /**
     * double型，開始機率
     */
    private final double begin_p;

    /**
     * double型，結束機率
     */
    private final double end_p;

    /**
     * 構造函數
     * @param begin_p double型，開始機率
     * @param end_p double型，結束機率
     * @param city_choose City型，待選擇城市
     */
    public ChooseCity(double begin_p, double end_p, City city_choose) {
        this.city = city_choose;
        this.begin_p = begin_p;
        this.end_p = end_p;
    }

    public City getCity() {
        return city;
    }

    /**
     * 判斷某[0, 1]随機數是否在該随即空間内部
     * @param random double型，[0, 1]随機數
     * @return boolean型，true：在；false：不在
     */
    public boolean random_in(double random) {
        boolean back = false;
        if(random >= this.begin_p && random < this.end_p) {
            back = true;
        }
        return back;
    }
}
           

3.3.4 model.Round.java

一次蟻群算法中的一輪，對應了2.2.2.循環中【循環層1】所發生的事件。

package model;

import java.util.ArrayList;
import java.util.List;

import model.antcolony.Ant;
import model.antcolony.AntColony;
import model.world.City;
import model.world.World;

/**
 * 蟻群算法中的一輪
 * @author WangYikai
 */
public class Round {
    /**
     * double型，資訊素資訊對螞蟻選擇城市的影響程度
     */
    private static final double ALPHA;

    /**
     * double型，環境資訊對螞蟻選擇城市的影響程度
     */
    private static final double BETA;

    /**
     * double型，每隻螞蟻每輪播撒的資訊素總量
     */
    private static final double Q;

    /**
     * AntColony型，蟻群
     */
    private AntColony antColony;

    /**
     * ACO型，本輪所屬的蟻群算法
     */
    private final ACO aco;

    /**
     * double[][]型，(i, j)代表城市i到城市j的資訊素強度在本輪中的增量
     */
    private double[][] delta_tau_s;

    /**
     * double[][]型，(i, j)代表本輪結束後城市i到城市j的資訊素強度
     */
    private double[][] tau_s;

    /**
     * Way型，本輪最佳路徑
     */
    private Way best_way;

    static {
        ALPHA = ;
        BETA = ;
        Q = ;
    }

    /**
     * 構造函數
     * @param aco ACO型，本輪所屬的蟻群算法
     */
    public Round(ACO aco) {
        this.aco = aco;

        // 生成蟻群
        this.antColony = new AntColony();

        this.delta_tau_s = new double[World.getCITY_ARRAY().length][World.getCITY_ARRAY().length];
        for(int i = ; i < this.delta_tau_s.length; i++) {
            for(int j = ; j < this.delta_tau_s[i].length; j++) {
                this.delta_tau_s[i][j] = ;
            }
        }

        for(int i = ; i < (World.getCITY_ARRAY().length - ); i++) {
            // 過了一個機關時間
            aco.setT(aco.getT() + );

            // 在這一個機關時間内每隻螞蟻的動作
            for(int k = ; k < this.antColony.getAnt_array().length; k++) {
                // 到達下一個要通路的城市
                City next_city = this.choose_next_city(i, this.antColony.getAnt_array()[k]);
                // 将新到達的城市放入禁忌表
                this.antColony.getAnt_array()[k].getTabu()[i + ] = next_city;
                // 更新爬過的路徑長度
                this.antColony.getAnt_array()[k].setL(this.antColony.getAnt_array()[k].getL() + World.d_city(this.antColony.getAnt_array()[k].getTabu()[i], next_city));
            }
        }

        // 将每一隻螞蟻的資訊回報給蟻群系統
        this.best_way = new Way(this.antColony.getAnt_array()[].getTabu(), this.antColony.getAnt_array()[].getL());
        for(int k = ; k < this.antColony.getAnt_array().length; k++) {
            if(this.antColony.getAnt_array()[k].getL() < this.best_way.getL()) {
                this.best_way = new Way(this.antColony.getAnt_array()[k].getTabu(), this.antColony.getAnt_array()[k].getL());
            }

            // 更新該螞蟻産生的資訊素
            double tau_k = Round.Q / this.antColony.getAnt_array()[k].getL();
            int city_1_index = ;
            int city_2_index = ;
            while(city_2_index < this.antColony.getAnt_array()[k].getTabu().length) {
                int city_1_id = this.antColony.getAnt_array()[k].getTabu()[city_1_index].getId();
                int city_2_id = this.antColony.getAnt_array()[k].getTabu()[city_2_index].getId();
                this.delta_tau_s[city_1_id][city_2_id] = this.delta_tau_s[city_1_id][city_2_id] + tau_k;
                this.delta_tau_s[city_2_id][city_1_id] = this.delta_tau_s[city_1_id][city_2_id];

                city_1_index++;
                city_2_index++;
            }
        }

        // 休整一個機關時間
        aco.setT(aco.getT() + );
    }

    /**
     * 某隻螞蟻選擇下一個要前往的城市
     * @param step int型，本輪中某隻螞蟻已爬的步數
     * @param ant Ant型，螞蟻
     * @return City型，下一個要前往的城市
     */
    private City choose_next_city(int step, Ant ant) {
        City back = null;

        // 得到該螞蟻所有可選擇的城市
        List<City> allowed_city = new ArrayList<City>();
        for(int i = ; i < World.getCITY_ARRAY().length; i++) {
            if(!ant.inTabu(step, World.getCITY_ARRAY()[i])) {
                allowed_city.add(World.getCITY_ARRAY()[i]);
            }
        }

        // 計算每一個可達城市的機率資訊的分子及分母
        double[] numerator = new double[allowed_city.size()];
        double denominator = ;
        for(int i = ; i < numerator.length; i++) {
            // 兩城市間的距離
            double d = World.d_city(ant.getTabu()[step], allowed_city.get(i));
            // 兩城市間的啟發式資訊
            double eta =  / d;
            // 分子
            numerator[i] = Math.pow(this.aco.getTau_s()[ant.getTabu()[step].getId()][allowed_city.get(i).getId()], Round.ALPHA) + Math.pow(eta, Round.BETA);
            // 累加分母
            denominator = denominator + numerator[i];
        }

        // 得到每一個可達城市的機率
        double[] p = new double[allowed_city.size()];
        for(int i = ; i < p.length; i++) {
            p[i] = numerator[i] / denominator;
        }

        // 存儲每一個可達城市的機率資訊
        double begin_p = ;
        double end_p = ;
        ChooseCity[] p_allowed_city = new ChooseCity[allowed_city.size()];
        for(int i = ; i < p_allowed_city.length; i++) {
            if(i == p_allowed_city.length -) {
                end_p = ;
            } else {
                end_p = begin_p + p[i];
            }
            p_allowed_city[i] = new ChooseCity(begin_p, end_p, allowed_city.get(i));
            begin_p = end_p;
        }

        // 依機率選擇一個城市
        double random = Math.random();
        for(int i = ; i < p_allowed_city.length; i++) {
            if(p_allowed_city[i].random_in(random)) {
                back = p_allowed_city[i].getCity();
            }
        }
        return back;
    }

    public AntColony getAntColony() {
        return antColony;
    }

    public double[][] getDelta_tau_s() {
        return delta_tau_s;
    }

    public Way getBest_way() {
        return best_way;
    }

    public double[][] getTau_s() {
        return tau_s;
    }

    public void setTau_s(double[][] tau_s) {
        this.tau_s = tau_s;
    }
}
           

3.3.5 model.Way.java

記錄了某隻螞蟻完成爬行後所走過的一條通路，實為問題的一個解。

package model;

import model.world.City;

/**
 * 一條通路
 * @author WangYikai
 */
public class Way {
    /**
     * City[]型，通路
     */
    private final City[] way;

    /**
     * double型，通路長度
     */
    private final double l;

    /**
     * 構造函數
     * @param way City[]型，通路
     * @param l double型，通路長度
     */
    public Way(City[] way, double l) {
        this.way = way;
        this.l = l;
    }

    public City[] getWay() {
        return way;
    }

    public double getL() {
        return l;
    }
}
           

3.3.6 model.antcolony.Ant.java

螞蟻類

package model.antcolony;

import model.world.City;
import model.world.World;

/**
 * 螞蟻
 * @author WangYikai
 */
public class Ant {
    /**
     * int型，id
     */
    private final int id;

    /**
     * City[]型，禁忌表：螞蟻已通路完成的城市
     */
    private City[] tabu;

    /**
     * double型，螞蟻經過的路徑長度
     */
    private double l;

    /**
     * 構造函數
     * @param id int型，id
     * @param tabu_0 City型，螞蟻的出生城市
     */
    public Ant(int id, City tabu_0) {
        this.id = id;
        this.tabu = new City[World.getCITY_ARRAY().length];

        this.tabu[] = tabu_0;

        this.l = ;
    }

    /**
     * 判斷某城市是否在該螞蟻的禁忌表中
     * @param step int型，本輪中某隻螞蟻已爬的步數
     * @param city City型，城市
     * @return true：在；false：不在
     */
    public boolean inTabu(int step, City city) {
        boolean back = false;
        for(int i = ; i < (step + ); i++) {
            if(city.getId() == this.tabu[i].getId()) {
                back = true;
                break;
            }
        }
        return back;
    }

    public City[] getTabu() {
        return tabu;
    }

    public int getId() {
        return id;
    }

    public double getL() {
        return l;
    }

    public void setL(double l) {
        this.l = l;
    }
}
           

3.3.7 model.antcolony.AntColony.java

蟻群類

package model.antcolony;

import model.world.World;

/**
 * 蟻群
 * @author WangYikai
 */
public class AntColony {
    /**
     * int型，蟻群規模
     */
    private static final int ANT_ARRAY_LENGTH;

    /**
     * Ant[]型，蟻群中的所有螞蟻
     */
    private final Ant[] ant_array;

    static {
        ANT_ARRAY_LENGTH = World.getCITY_ARRAY().length;
    }

    /**
     * 構造函數
     */
    public AntColony() {
        this.ant_array = new Ant[AntColony.ANT_ARRAY_LENGTH];

        // 将螞蟻均勻放入所有城市中
        for(int i = ; i < this.ant_array.length; i++) {
            this.ant_array[i] = new Ant(i, World.getCITY_ARRAY()[(i % World.getCITY_ARRAY().length)]);
        }
    }

    public Ant[] getAnt_array() {
        return ant_array;
    }
}
           

3.3.8 model.world.City.java

城市類

package model.world;

import tool.Point;

/**
 * 城市
 * @author WangYikai
 */
public class City {
    /**
     * int型，城市在數組中的編号
     */
    private final int id;

    /**
     * double型，城市坐标點
     */
    private final Point point;

    /**
     * 構造函數
     * @param x double型，x坐标
     * @param y double型，y坐标
     * @param id int型，城市在數組中的編号
     */
    public City(int id, double x, double y) {
        this.id = id;
        this.point = new Point(x, y);
    }

    public int getId() {
        return id;
    }

    public Point getPoint() {
        return point;
    }
}
           

3.3.9 model.world.World.java

世界類。也是蟻群所存在的環境。在本問題中即為所有城市。

該類沒有公有的構造函數；所有資訊都在本類第一次通路時通過static代碼塊導入。

關于城市資料的擷取參考了CSDN上Fashionxu所寫的名為 蟻群優化算法的JAVA實作[2] 的部落格，其中提到可從TSPLIB中下載下傳，得到*ALL_tsp.tar.gz壓縮包，解壓後其中有很多TSP城市的資料檔案，以att48.tsp為例，下載下傳下來的檔案内容如下：

NAME : att48
COMMENT :  capitals of the US (Padberg/Rinaldi)
TYPE : TSP
DIMENSION : 
EDGE_WEIGHT_TYPE : ATT
NODE_COORD_SECTION
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
EOF
           

這裡我們仿照Fashionxu的方法，對該檔案做以下處理，變為：

48
1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16 6107 669
17 7611 5184
18 7462 3590
19 7732 4723
20 5900 3561
21 4483 3369
22 6101 1110
23 5199 2182
24 1633 2809
25 4307 2322
26 675 1006
27 7555 4819
28 7541 3981
29 3177 756
30 7352 4506
31 7545 2801
32 3245 3305
33 6426 3173
34 4608 1198
35 23 2216
36 7248 3779
37 7762 4595
38 7392 2244
39 3484 2829
40 6271 2135
41 4985 140
42 1916 1569
43 7280 4899
44 7509 3239
45 10 2676
46 6807 2993
47 5185 3258
48 3023 1942
           

簡單解釋如下：

1. 第一行的48即為城市數；以下的48行分别代表48個具體城市的參數
2. 每個表示城市的行都有3個參數，以空格分割，第一個是序号，從1~48；後兩個依次為直角坐标系下的x，y坐标
3. Java可直接讀取.tsp檔案（詳見代碼）；和讀取txt的方式類似；先讀取一行，而後以空格符分割一行中的内容；

package model.world;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 螞蟻的活動空間
 * @author WangYikai
 */
public class World {
    /**
     * String型，存放城市資訊的tsp檔案路徑
     */
    private static final String CITY_FILE;

    /**
     * BufferedReader型，城市tsp檔案中的城市基本資訊
     */
    private static BufferedReader CITY_DATA;

    /**
     * int型，城市規模
     */
    private static int CITY_COUNT;

    /**
     * City[]型，城市數組
     */
    private static City[] CITY_ARRAY;

    static {
        // 存儲城市資訊檔案的路徑
        CITY_FILE = "data/city20.tsp";

        // 城市資訊
        try {
            CITY_DATA = new BufferedReader(new InputStreamReader(new FileInputStream(World.CITY_FILE)));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        // 城市規模
        try {
            CITY_COUNT = Integer.valueOf(World.CITY_DATA.readLine());
        } catch (NumberFormatException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 城市數組
        String str_buff = null;
        CITY_ARRAY = new City[World.CITY_COUNT];
        for(int i = ; i < World.CITY_ARRAY.length; i++) {
            try {
                str_buff = World.CITY_DATA.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            String[] coordinate = str_buff.split(" ");
            World.CITY_ARRAY[i] = new City(i, Double.valueOf(coordinate[]), Double.valueOf(coordinate[]));
        }
    }

    public static City[] getCITY_ARRAY() {
        return CITY_ARRAY;
    }

    /**
     * 計算兩城市間的距離
     * @param city_1 City型，城市
     * @param city_2 City型，城市
     * @return 兩城市間的距離
     */
    public static double d_city(City city_1, City city_2) {
        double back = Math.sqrt(Math.pow(city_1.getPoint().getX() - city_2.getPoint().getX(), ) + Math.pow(city_1.getPoint().getY() - city_2.getPoint().getY(), ));
        return back;
    }
}
           

model層結束，該層為算法的核心部分，實作了算法所有的理論功能。

參考文獻

[1] 李世勇等.蟻群算法及其應用.哈爾濱.哈爾濱工業大學出版社.2004

[2]Fashionxu.CSDN.蟻群優化算法的JAVA實作.2010