說(shuō)明信息素權(quán)重,路徑權(quán)重和信息素蒸發(fā)率對(duì)最后的結(jié)果

1、說(shuō)明：信息素權(quán)重，路徑權(quán)重和信息素蒸發(fā)率對(duì)最后的結(jié)果影響很大，需要微調(diào)。 目前發(fā)現(xiàn)2 / 5 / 0.5 能達(dá)到稍微讓人滿意的效果。本程序離完美的ACO還差很遠(yuǎn)，僅供參考。 本蟻群算法為AS算法。 用法： 1.new一個(gè)對(duì)象 ACOforTSP tsp = new ACPforTSP(tsp數(shù)據(jù)文件名,迭代次數(shù)，螞蟻數(shù)量，信息素權(quán)重，路徑權(quán)重，信息素蒸發(fā)率）; 2.用go()方法運(yùn)行 tsp.go(); ACOforTSP.java _ import java.io.File; import static java.lang.Math.pow; import static java.lang.

2、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; /權(quán)重 private int alph

3、a, 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è)置螞蟻數(shù)量 this.numbersOfA

4、nt = numbersOfAnt; /設(shè)置權(quán)重 this.alpha = alpha; this.beta = beta; /設(shè)置蒸發(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(

5、pow(x - city.x), 2) + pow(y - city.y), 2); try /定義HashMap保存讀取的坐標(biāo)信息 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() /將讀到

6、的信息保存入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(data0), Double.parseDouble(data1), Double.parseDouble(data2); map.put(city.no, city); /分配距離矩陣存儲(chǔ)空間 distance = new doublemap.size()

7、 + 1map.size() + 1; /分配距離倒數(shù)矩陣存儲(chǔ)空間 heuristic = new doublemap.size() + 1map.size() + 1; /分配信息素矩陣存儲(chǔ)空間 pheromone = new doublemap.size() + 1map.size() + 1; for (int i = 1; i < map.size() + 1; i+) for (int j = 1; j < map.size() + 1; j+) /計(jì)算城市間的距離，并存入距離矩陣 distanceij = map.get(i).getDistance(map.get(j

8、); /計(jì)算距離倒數(shù)，并存入距離倒數(shù)矩陣 heuristicij = 1 / distanceij; /初始化信息素矩陣 pheromoneij = 1; catch (Exception exception) System.out.println("初始化數(shù)據(jù)失敗！"); class Ant /已訪問(wèn)城市列表 private boolean visited; /訪問(wèn)順序表 private int tour; /已訪問(wèn)城市的個(gè)數(shù) private int n; /總的距離 private double total; Ant() /給訪問(wèn)順序表分配空間 tour = new i

9、ntdistance.length+1; /已存入城市數(shù)量為n，剛開(kāi)始為0 n = 0; /將起始城市1,放入訪問(wèn)結(jié)點(diǎn)順序表第一項(xiàng) tour+n = 1; /給已訪問(wèn)城市結(jié)點(diǎn)分配空間 visited = new booleandistance.length; /第一個(gè)城市為出發(fā)城市，設(shè)置為已訪問(wèn) visitedtourn = true; private int chooseCity() /用來(lái)random的隨機(jī)數(shù) double m = 0; /獲得當(dāng)前所在的城市號(hào)放入j,如果和j相鄰的城市沒(méi)有被訪問(wèn)，那么加入m for (int i = 1, j = tourn; i < pheromo

10、ne.length; i+) if (!visitedi) m += pow(pheromoneji, alpha) * pow(heuristicji, beta); /保存隨機(jī)到的數(shù) double p = m * random(); /尋找被隨機(jī)到的城市 double k = 0; /保存找到的城市 int q = 0; for (int i = 1, j = tourn; k < p; i+) if (!visitedi) k += pow(pheromoneji, alpha) * pow(heuristicji, beta); q = i; return q; private

11、void constructSolution () while (n != (distance.length-1) ) /選取下一個(gè)城市 int p = chooseCity(); /計(jì)算總的距離 total += distancetournp; /將選取到的城市放入已訪問(wèn)列表 tour+n = p; /將選取到的城市標(biāo)記為已訪問(wèn) visitedp = true; /回到起點(diǎn) total += distancetour1tourn; /將起點(diǎn)加入訪問(wèn)順序表的最后 tour+n = tour1; private void releasePheromone() /釋放信息素的大小 double t

12、 = 1/total; /釋放信息素 for (int i=1;i<tour.length-1;i+) pheromonetouritouri+1 += t; pheromonetouri+1touri += t; public void go() /保存最好的路徑和路徑長(zhǎng)度 double bestTotal = Double.MAX_VALUE; int bestTour = new intdistance.length+1; /新建螞蟻數(shù)組，用來(lái)引用所創(chuàng)建的螞蟻 Ant ant = new AntnumbersOfAnt; /進(jìn)行iterationTimes次迭代 while (it

13、erationTimes != 0) /初始化新的一批螞蟻（這里用構(gòu)造新的螞蟻代替重置螞蟻狀態(tài)） for (int i=0; i<numbersOfAnt; i+) anti = new Ant(); /進(jìn)行一次迭代（即讓所有的螞蟻構(gòu)建一條路徑） for (int i=0; i<numbersOfAnt; i+) anti.constructSolution(); /如果螞蟻構(gòu)建的路徑長(zhǎng)度比上次最好的還好，那么保存這個(gè)長(zhǎng)度和它所走的路徑 if (anti.total<bestTotal) bestTotal = anti.total; System.arraycopy(ant

14、i.tour, 1, bestTour, 1, bestTour.length-1); /蒸發(fā)信息素 evaporatePheromone(); /釋放信息素 for (int i=0; i<numbersOfAnt; i+) anti.releasePheromone(); /報(bào)告本次迭代的信息 System.out.format("本次為倒數(shù)第%d次迭代,當(dāng)前最優(yōu)路徑長(zhǎng)度為%10.2fn",iterationTimes,bestTotal); /迭代總數(shù)減去1，進(jìn)行下次迭代 iterationTimes-; /輸出最好的路徑長(zhǎng)度 System.out.format("得到的最優(yōu)的路徑長(zhǎng)度為:%10.2fn",bestTotal); /輸出最好的路徑 System.out.println("最優(yōu)路徑如下："); for