蚁群算法&模拟退火算法 解决TSP JAVA

package com.color.tsp.ant; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.regex.Matcher; import java.util.regex.Pattern; public class AcoAlg { /** * 旅行商的数目m,当城市数量（规模）是蚂蚁数量的 1.5 倍左右时，算法的性能比较好。<br> * att48中城市数量是48 */ public final static int TRAVLEER_COUNT=32; /** * 信息素浓度因子α，推荐[1,4] */ public final static double PHER_ALPHA=1.0; /** * 期望启发因子β,推荐[3,5] */ public final static double EXPE_BATE=3.0; /** * 信息素挥发系数ρ,推荐[0.4,0.6] */ public final static double PHER_EXPIRED=0.5; /** * 信息素浓度Q,推荐[10,8000] */ public final static double PHER_CON=3000; /** * 城市总数 */ public static int CITY_COUNT=0; /** * 获取城市编号 x坐标 y坐标的正则表达式 */ private Pattern pattern = Pattern.compile("^\\d+[\\ ]+\\d+[\\ ]+\\d+$"); /** * 保存每条路径上的残余信息素浓度 */ private static double[][] pher; /** * 保存文件中读取的城市信息 */ private List<City> cityArr; /** * 参与算法的旅行者，人工蚂蚁 */ private Traveler[] travelers; /** * 最终的结果 */ private Traveler bestTraveler; /** * 初始化之前，读入文本，获取城市信息 * @return */ private List<City> beforeInit(){ List<City> cities=new ArrayList<City>(); FileReader fr = null; try { //读取项目根目录/data/att48.tsp文件 fr=new FileReader(System.getProperty("user.dir")+File.separator+"data"+File.separator+"att48.tsp"); BufferedReader br = new BufferedReader(fr); String line=null; while((line=br.readLine())!=null){ if(line.trim().length()>0){ Matcher matcher=pattern.matcher(line); if(matcher.find()){ String[] s=line.split(" "); City city=new City(Integer.valueOf(s[0]), Integer.valueOf(s[1]), Integer.valueOf(s[1])); cities.add(city); } } } CITY_COUNT=cities.size(); return cities; } catch (Exception e) { e.printStackTrace(); return null; }finally { if(fr!=null){ try { fr.close(); } catch (IOException e) { e.printStackTrace(); } } } } /** * 初始化数据 */ private void init(){ bestTraveler = new Traveler(); cityArr=beforeInit(); int size=cityArr.size(); travelers=new Traveler[TRAVLEER_COUNT]; Random random=new Random(); System.out.print("随机投放"+TRAVLEER_COUNT+"位旅行者分别到城市："); for(int i=0;i<TRAVLEER_COUNT;i++){ travelers[i]=new Traveler(); //将人工蚂蚁，也就是旅行商随机分配到随机的城市里 City targetCity=cityArr.get(random.nextInt(size)); System.out.print("编号："+targetCity.getNo()+"\t"); travelers[i].addCity(targetCity); } System.out.println("\n初始化所有路径的信息素是：0.01\n"); /** * 初始化所有路径的信息素为0.01，实际上应该为0，但是0的化影响计算，所以采用小一点的数字来表示几乎没有 * att48中，城市编号是1~48，所以对应于pher的索引是0~47 */ pher=new double[size][size]; for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ pher[i][j] = 0.01; } } } /** * 更新整体信息素矩阵 * @param traveler 完成一次旅行后的旅行者 */ public void updatePher(Traveler traveler){ System.out.println("\n更新路径上的信息素...."); //当前旅行者完成一次旅行并回到出发点的总路径，用于Δτ=Q/L double distance=traveler.getDistance(); List<City> tempCities=traveler.cloneCities(traveler.getCities()); //更新每个路径的信息素 for(int i=0;i<cityArr.size();i++){ for(int j=0;j<cityArr.size();j++){ double t=0; if(isNearBy(tempCities,i+1,j+1)){ //Δτ=Q/L t=PHER_CON/distance; } pher[i][j]=(1-PHER_EXPIRED)*pher[i][j]+t; } } } /** * 旅行者经过的城市顺序中是否有从某个城市city1到紧接着的下一个城市city2的这条路径 * @param cities 旅行者经过的城市顺序，不含有最后回到出发点的城市 * @param city1 开始城市编号 * @param city2 邻居城市编号 * @return */ private boolean isNearBy(List<City> cities,int city1, int city2){ //加入开始的城市，形成一个从开始城市，最后回到开始城市的闭环 cities.add(cities.get(0)); if(cities.size()>1){ for(int i=0;i<cities.size()-1;i++){ if(cities.get(i).getNo()==city1&&cities.get(i+1).getNo()==city2){ return true; } } } return false; } public static double[][] getPher() { return pher; } /** * 执行蚁群算法 */ public void exec(){ init(); for(int i=0;i<travelers.length;i++){ //初始化的时候，加入了一个城市 Traveler tlr=travelers[i]; for(int j=0;j<CITY_COUNT-1;j++){ List<City> t_cities=tlr.cloneCities(this.cityArr); travelers[i].moveToNext(t_cities); } //当前旅行者的旅行距离 double distance=tlr.getDistance(); //目前保存的最短的旅行距离，如果是0，标识是初始化时候设置的值 double bestDistance=bestTraveler.getDistance(); if(bestDistance==0||bestDistance>distance){ bestTraveler=tlr; } //计算每个旅行商的信息素，也就是更新路径信息素 updatePher(tlr); } //所有旅行者旅行完毕 System.out.println("最短城市旅游路线是："); bestTraveler.toString(); } }