這個(gè)程序?qū)崿F(xiàn)了模擬退火，用于計(jì)算att48數(shù)據(jù)集。

這個(gè)程序由兩部分組成SA1和Line1。SA1是主程序，結(jié)合了蟻群算法改寫的。主要思路是先用蟻群算法生成一個(gè)原始路徑，然后隨機(jī)交換兩個(gè)城市的位置，如果得到的距離好于最優(yōu)值或者滿足退火條件就保留這次更改，不斷迭代直到最優(yōu)值到達(dá)要求。

Line1程序用于畫圖。

?

程序中一共有4個(gè)本地路徑

d:/工業(yè)/hk/aaa.csv?? 保存SA1的計(jì)算結(jié)果

d:/工業(yè)/hk/統(tǒng)計(jì).csv? 保存每步的距離變化

d:/工業(yè)/hk/t/zz.csv?? 48個(gè)城市的坐標(biāo)

d:/工業(yè)/hk/重排.csv? 臨時(shí)文件用于畫圖

?

性能測(cè)試數(shù)據(jù)

用這組參數(shù)進(jìn)行性能測(cè)試

SA(48, 1000, 2000,? 0.99815 , 1500, "d:/工業(yè)/hk/t/zz.csv" );

?

?	步	耗時(shí)ms	耗時(shí)min
1	422	316819	5.2803167
2	530	399003	6.65005
3	92	74823	1.24705
4	435	423858	7.0643
5	53	51973	0.8662167
6	143	139023	2.31705
7	137	133736	2.2289333
8	493	474521	7.9086833
9	388	378521	6.3086833
10	241	234907	3.9151167
11	39	37827	0.63045
12	509	488905	8.1484167
13	38	37292	0.6215333
14	125	124406	2.0734333
15	677	665224	11.087067

這個(gè)程序共運(yùn)行了15次，達(dá)到10628平均需要288步，4.42分鐘。每一步需要交換2百萬(wàn)次。也就是平均每次計(jì)算需要交換5.76億次才能達(dá)到最優(yōu)值。

?

SA1代碼

Line1代碼

d:/工業(yè)/hk/t/zz.csv

package plan;import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.Random; public class SA1 {//實(shí)現(xiàn)了退火算法static int cityNum; // 城市數(shù)量，編碼長(zhǎng)度 static int N;// 每個(gè)溫度迭代次數(shù)static int T;// 重復(fù)降溫次數(shù) static double a;// 降溫系數(shù) static double t1;// 初始溫度 static int[][] distance; // 距離矩陣 static int bestT=0;// 最佳出現(xiàn)代數(shù) static int[] Ghh;// 初始路徑編碼 static int ge; static int[] bestGhh;// 最好的路徑編碼 static int be; static int[] tempGhh;// 存放臨時(shí)編碼 static int te; static int min=100000;private static Random random; //退火算法即照顧了廣度也照顧了深度public static int SA(int cn, int n, int t, double aa, float tt ,String filename ) throws IOException { cityNum = cn; N = n; T = t; a = aa; t1 = tt; int fan=0;init( filename);fan=solve();return fan;} // 讀取數(shù)據(jù) public static void init(String filename) throws IOException { int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cityNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { //System.out.println(i+"************ ");// 讀取一行數(shù)據(jù)，數(shù)據(jù)格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(","); x[i] = Integer.valueOf(strcol[1]);// x坐標(biāo) y[i] = Integer.valueOf(strcol[2]);// y坐標(biāo) } // 計(jì)算距離矩陣 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 對(duì)角線為0 for (int j = i + 1; j < cityNum; j++) { double rij = Math.sqrt(((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/10); // 四舍五入，取整 int tij = (int) Math.round(rij); if (tij < rij) { distance[i][j] = tij + 1; distance[j][i] = distance[i][j]; } else { distance[i][j] = tij; distance[j][i] = distance[i][j]; } } } distance[cityNum - 1][cityNum - 1] = 0; Ghh = new int[cityNum]; bestGhh = new int[cityNum]; be = Integer.MAX_VALUE; tempGhh = new int[cityNum]; te = Integer.MAX_VALUE; bestT = 0; random = new Random(System.currentTimeMillis()); // System.out.println(cityNum+","+N+","+T+","+a+","+t0); } // 初始化編碼Ghh public static void initGroup() { int i, j; Ghh[0] = random.nextInt(65535) % cityNum; for (i = 1; i < cityNum;)// 編碼長(zhǎng)度 { Ghh[i] = random.nextInt(65535) % cityNum; //得到是小于cityNum的數(shù)// System.out.println( Ghh[i]+" "+i+" " );for (j = 0; j < i; j++) { if (Ghh[i] == Ghh[j]) { break; } }// System.out.println( Ghh[i]+" "+i+" * " );if (j == i) { //檢查沒(méi)有重復(fù)i++; } } } // 復(fù)制編碼Gha到Ghb public static void copyGh(int[] Gha, int[] Ghb) { for (int i = 0; i < cityNum; i++) { Ghb[i] = Gha[i]; } } // 計(jì)算距離public static int evaluate(int[] chr) { int len = 0; // 編碼，起始城市,城市1,城市2...城市n for (int i = 1; i < cityNum; i++) { len += distance[chr[i - 1]][chr[i]]; } // 城市n,起始城市 len += distance[chr[cityNum - 1]][chr[0]]; return len; } // 鄰域交換，得到鄰域 ，隨機(jī)兩個(gè)值交換public static void Linju(int[] Gh, int[] tempGh) { int i, temp; int ran1, ran2; for (i = 0; i < cityNum; i++) { tempGh[i] = Gh[i]; } ran1 = random.nextInt(65535) % cityNum; ran2 = random.nextInt(65535) % cityNum; while (ran1 == ran2) { ran2 = random.nextInt(65535) % cityNum; } temp = tempGh[ran1]; tempGh[ran1] = tempGh[ran2]; tempGh[ran2] = temp; } public static int solve() { // 初始化編碼Ghh initGroup(); //用隨機(jī)的方式生成原始數(shù)列copyGh(Ghh, bestGhh);// 復(fù)制當(dāng)前編碼Ghh到最好編碼bestGh be = evaluate(Ghh); ge = be; int k = 0;// 降溫次數(shù) int n = 0;// 迭代步數(shù) double t = t1; double r = 0.0; int count=0;while (k < T) { //降溫次數(shù) n = 0; while (n < N) { //每個(gè)溫度迭代步長(zhǎng) Linju(Ghh, tempGhh);// 得到當(dāng)前編碼Ghh的鄰域編碼tempGhh te = evaluate(tempGhh); if (te < be) { copyGh(tempGhh, bestGhh); bestT = k; be = te; } Random rand =new Random();r = rand.nextDouble(); if (te < ge ||Math.exp((ge - te) /t) > r // || (GhhEvaluation == tempEvaluation) ) { copyGh(tempGhh, Ghh); //隨著溫度的降低這個(gè)冗余度也會(huì)逐漸減小，所以增大初始溫度，減慢溫度下降速度更有利收斂if( Math.abs(Math.exp((ge - te) / t) -0)<0.00001 ){count++;}ge = te; } n++; } t = a * t; //控制t值的可能范圍，這個(gè)是最為核心的參數(shù)if(k==T-1){System.out.println(t+" "+a+" "+k+" "+count+ " "+bestT);}//0.08634329 2000//0.043171644 1000k++; } if(be<min){min=be;}return be;} public static void route() throws IOException {int max=100000;FileWriter fileWriter1=new FileWriter("d:/工業(yè)/hk/aaa.csv"); FileWriter fileWriter2=new FileWriter("d:/工業(yè)/hk/統(tǒng)計(jì).csv"); int count=0;while(max>10628 ){count++;//城市數(shù)量 每個(gè)溫度迭代次數(shù) 重復(fù) 降溫次數(shù) 初始溫度 降溫系數(shù) max= SA(48, 1000, 2000, 0.99815 , 1500, "d:/工業(yè)/hk/t/zz.csv" ); // N T a t1fileWriter2.write( max+","+min +"\r\n ");fileWriter2.flush();System.out.println( max +" ** ** "+count);} for (int i = 0; i < cityNum ; i++) {// System.out.println(bestTour[i][0]+" *** ");fileWriter1.write( bestGhh[i] +"\r\n ");fileWriter1.flush();}fileWriter1.write( bestGhh[0] +"\r\n ");fileWriter1.flush();new Line1(); }public static void main(String[] args) throws IOException { long sysDate1 = System.currentTimeMillis();route();long sysDate2 = System.currentTimeMillis(); System.out.println( (sysDate2-sysDate1) +" ** ** " );} } package plan;import java.awt.Color; import java.awt.Graphics; import java.awt.event.WindowAdapter; import java.awt.event.WindowEvent; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.text.ParseException; import java.util.LinkedList; import java.util.List; import java.util.regex.Pattern; import javax.swing.JFrame;public class Line1 extends JFrame {public Line1() { super(); setBounds(0, 0, 2000, 2000); addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent ev) { dispose(); System.exit(0); } }); setVisible(true); }public static String read(String a) throws IOException{String as;{ String tops="";BufferedReader ins=new BufferedReader(new FileReader(a));String ss;List<String> nns=new LinkedList<String>();while((ss=ins.readLine())!=null)nns.add(ss);String kps = nns.toString();kps = kps.substring(1,kps.length()-1);tops=kps;ins.close();as=tops;}as=as.trim();return as;}public void paint(Graphics g) { g.setColor(Color.white); //底色g.setColor(Color.blue); int r1=8;int r=7;String we;try {coordinate( );we = read("d:/工業(yè)/hk/重排.csv");String[] te=Pattern.compile(",").split(we);double des=0.0;for (int b =1 ;b<te.length/3 ;b++) {int bx=Integer.parseInt(te[(b-1)*3+1].trim())/r1;int by=Integer.parseInt(te[(b-1)*3+2].trim())/r;int cx=Integer.parseInt(te[b*3+1].trim())/r1;int cy=Integer.parseInt(te[b*3+2].trim())/r;des=des+ Math.pow((Math.pow( (cx*r1-bx*r1) , 2) +Math.pow(cy*r-by*r, 2)),0.5);int pyh=180; //（+向右 -向左）int pyz=800; //(-向上 +向下)g.drawLine((pyh+bx),(pyz-by),(pyh+cx),(pyz-cy));}g.setColor(Color.red); // g.drawLine(0,0,100,200);// g.drawLine(0,0,6743/20,1543/20);} catch (IOException e) {e.printStackTrace();} } public static void coordinate( ) throws IOException{FileWriter fileWriter1=new FileWriter("d:/工業(yè)/hk/重排.csv"); String wee= read("d:/工業(yè)/hk/aaa.csv");String[] tee=Pattern.compile(",").split(wee);String we = read("d:/工業(yè)/hk/t/zz.csv");String[] te=Pattern.compile(",").split(we);for (int z =0 ; z<tee.length ; z++) {// System.out.println( z+" z " +Integer.parseInt( tee[z].trim()) );int d=Integer.parseInt( tee[z].trim());for (int b =0 ;b<te.length/3 ;b++) {if(Integer.parseInt(te[b*3].trim())==(d +1) ){fileWriter1.write( te[b*3] +","+te[b*3+1]+","+te[b*3+2]+"\r\n ");fileWriter1.flush();}}}}public static void main(String[] args) throws IOException, ParseException { //SA1.route();new Line1(); } }

d:/工業(yè)/hk/t/zz.csv

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

?

總結(jié)

以上是生活随笔為你收集整理的java模拟退火程序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。