开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > DNA > 查看源码
SA_TSA.java
资源名称：SA_TSA.zip　[点击查看]
上传用户：fstxyy
上传日期：2018-01-04
资源大小：11k
文件大小：13k
源码类别：

DNA

开发平台：

Java

SA_TSA.java：源码内容
  1. import java.lang.*;
  2. import java.io.*;
  3. import java.util.*;
  6. /**
  7. *class SA_TSA.java
  8. * author: nt
  9. * data: 2006-3-22
  10. *51 city
  11. * mini=result_______________: 11.180339887498949
  12. */
  13. public class SA_TSA
  14. {
  15. //the city 
  16. //String[][] map;
  17. private static double T=1000.0; //init the T
  18. private static final double CONTROL_T=0.995; //change the T
  19. private static final double T_e=0.01; //control the T
  20. private static final int CYCLE_NUMBER=560;  //search length
  21. private static final int CITY_NUMBER=51;  //city number
  22. private static CityMap[] citymap=new CityMap[CITY_NUMBER]; //city position
  24. public static void main(String args[])
  25. {
  26. SA_TSA tsa=new SA_TSA();
  27. // tsa.init(); 
  29. CityMap[] _citymap=new CityMap[CITY_NUMBER];
  30. CityMap[] temp_citymap=new CityMap[CITY_NUMBER];
  31. for (int init=0;init< CITY_NUMBER;init++ )
  32. {
  33. _citymap[init]=new CityMap();
  34. temp_citymap[init]=new CityMap();
  35. }
  36. getTime();
  37. System.out.println("开始初始化路径：....");
  38. _citymap=copy(citymap);
  39. for (int cyc=0;cyc<50;cyc++)
  40. {
  41. _citymap=getRoute(_citymap);
  42. }
  43. _citymap=tsa.getFirstRoute(_citymap);
  44. //get time
  45. System.out.println("初始化路径结束!");
  46. setcitymap(_citymap);
  47. System.out.println("初始路径长度"+": "+getRouteValue(citymap));
  48. getTime();
  50. Date begin=new Date();
  51. //
  52. //setcitymap(_citymap);
  53. //showMap(citymap);
  55. temp_citymap=tsa.settempcitymap(citymap);
  59. boolean terminate=false;
  60. /*
  61. _citymap=tsa.getRoute(citymap);
  62. System.out.println("__________第一次变换______________");
  63. //showMap(citymap);
  64. double way_value=getRouteValue(_citymap);
  65. double delta_v=way_value-routeValue;
  66. System.out.println("delta_v:"+delta_v);
  67. System.out.println("old_Value:"+routeValue);
  68. System.out.println("new_value:"+way_value);
  69. //System.out.println("random_d:"+random_d);
  71. */
  72. System.out.println("正在查找最优路径：....");
  73. double newvalue,oldValue,delta_v;
  75. while (T>T_e)
  76. {
  77. int cycle=0;
  78. //System.out.println("_______ldfkgdlfkg_______: ");
  79. //_citymap=tsa.getRoute(_citymap);
  80. //showMap(_citymap);
  82. //System.out.println("routeValue____2: "+getRouteValue(_citymap));
  83. _citymap=tsa.getRoute(citymap);
  84. do
  85. {
  86. //_citymap=tsa.getRoute(citymap);
  87. //System.out.println("routeValue____"+cycle+"_: "+tsa.getRouteValue(citymap));
  88. //System.out.println("T ____"+T);
  89. //System.out.println("查找过程"+cycle+": "+getRouteValue(_citymap));
  90. oldValue=getRouteValue(citymap);
  91. newvalue=getRouteValue(_citymap);
  92. delta_v=newvalue-oldValue;
  93. //System.out.println("old____"+cycle+"_: "+routeValue);
  94. //System.out.println("new____"+cycle+"_: "+way_value);
  95. //System.out.println("delta_v____"+cycle+"_: "+delta_v);
  96. if (delta_v <0)
  97. {
  98. //System.out.println("T _______________"+T);
  99. setcitymap(_citymap);
  100. _citymap=tsa.getRoute(citymap);
  102. }
  103. else
  104. {
  105. double random_d=tsa.getRandomDouble();
  106. double delta_e=get_exp(-delta_v);
  107. // System.out.println("delta_v:"+delta_v);
  108. ////
  109. // System.out.println("delta_e:"+delta_e);
  110. // System.out.println("random_d:"+random_d);
  111. //if (delta_e>random_d)
  112. if (delta_e>random_d)
  113. {
  116. setcitymap(_citymap);
  117. //System.out.println("________^^^^^^^______________");
  119. }
  120. _citymap=tsa.getRoute(citymap);
  122. }//if (delta_v<0)
  123. cycle++;
  124. //
  125. }
  126. while (cycle<CYCLE_NUMBER);
  127. double old_=tsa.getRouteValue(temp_citymap);
  128. double new_=getRouteValue(citymap);
  130. if (new_<old_)
  131. {
  132. // if (old_/new_ <1.00000001)
  133. // {
  134. // //terminate=true;
  135. // T=newT(T);
  136. // }
  137. // else
  138. // {
  139. // temp_citymap=settempcitymap(citymap);
  140. // T=newT(T);
  141. // }
  142. temp_citymap=settempcitymap(citymap);
  143. T=newT(T);
  144. System.out.println("change:"+new_);
  146. }
  147. else
  148. {
  149. T=newT(T);
  150. }
  155. // if (T<=T_e)
  156. // {
  157. // terminate=true;
  158. // }
  159. }/**/
  161. System.out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
  162. //System.out.println("||||||||||||||||||||||||||||||");
  163. Date end=new Date();
  164. System.out.println("查找结果：");
  166. System.out.println("最优路径长度"+": "+getRouteValue(temp_citymap));
  167. //getTime();
  168. long waste=end.getTime() - begin.getTime();
  169. System.out.println("耗时： " +waste/1000+" 秒！");
  170. //showMap(temp_citymap);
  172. //showMap(citymap);
  179. }//main over
  180. /**
  181. *constrator: 
  182. */
  183. public SA_TSA()
  184. {
  185. try
  186. {
  187. init();
  188. }
  189. catch (IOException e)
  190. {
  191. System.out.println(e.toString());
  192. }
  194. }
  196. /**
  197. *method: initialize city map
  198. */
  199. private static void init()throws IOException
  200. {
  201. //init the citymap based on the array.txt
  202. int n;//the city number
  203. n=getCityNumber();
  204. //System.err.println("_____________"+n+"_____________");
  205. if (n!=CITY_NUMBER)
  206. {
  207. throw new NotEqulalException("city number shouder be equal the varial "CITY_NUMBER" you declare"+n);
  208. }
  209. String[] _city=getCityString();
  210. for (int i=0;i<n;i++)
  211. {
  212. citymap[i]=new CityMap(_city[i]);
  213. }
  215. }
  216. /**
  217. *method:getCityNumber
  218. *param: null
  219. *return: int the number of the citytxt file
  220. */
  221. private static int getCityNumber() throws IOException
  222. {
  223. BufferedReader br=new BufferedReader(new FileReader("array.txt"));
  224. int n=0;
  225. String Str_="";
  226. while ((Str_=br.readLine()) != null) 
  227.         {
  228. n++;
  229. }
  230. return n;
  231. }
  232. /**
  233. *method: getCityString
  234. *param: null
  235. *return String[]
  236. */
  237. private static String[] getCityString()throws IOException
  238. {
  239. //
  240. BufferedReader br=new BufferedReader(new FileReader("array.txt"));
  241. String Str="";
  242. String Str_="";
  244. char regx=';';
  245. int n=0;
  246. while ((Str_=br.readLine()) != null) 
  247.         {
  248. n++;
  249. Str+=Str_;
  250. Str+=regx;
  252. }
  253. Str=removeLastRegx(Str);
  255. //get the line to a array[]
  256. String[] _array=new String[n];
  257. _array=splitString(Str,(int)regx);
  258. return _array;
  259. }
  260. /**
  261. *method: splitString
  262. *param: args the string to split
  263. *param: c the char you want to match
  264. *return:  a array 
  265. */
  266. public static String[] splitString(String arg,int c)
  267. {
  268. String[] _array=new String[CITY_NUMBER];
  269. int cc=0;
  270. //System.out.println(arg.indexOf(c));
  272. while(arg.indexOf(c)!=-1)
  273.         {
  274. _array[cc]=arg.substring(0,arg.indexOf(c));
  275. arg=arg.substring(arg.indexOf(c)+1,arg.length());
  276. cc++;
  277.         }
  278. _array[cc]=arg;
  280.      return _array;
  281. }
  282. /**
  283. *method: cut the last char form the String
  284. */
  285. public static String removeLastRegx(String args)
  286. {
  287. //return args.substring(0,args.length()-1);
  288. if (args!=null)
  289. {
  290. return args.substring(0,args.length()-1);
  291. }
  292. else
  293. {
  294. return args;
  295. }
  296. }
  298. /**
  299. *method: getFirstRoute
  300. *param: CityMap
  301. *return: CityMap
  302. */
  303. private static CityMap[] getFirstRoute(CityMap[] cm)
  304. {
  305. //
  307. return getRoute(cm); 
  308. }
  311. /**
  312. *method: newT
  313. *param: double T
  314. *return: double a lower T
  315. */
  316. private static double newT(double t)
  317. {
  318. return t*CONTROL_T;
  319. }
  320. /**
  321. *method: get_exp
  322. *param: double_________________________________________________________________________-
  323. *return: double
  324. */
  325. private static double get_exp(double del)
  326. {
  327. //
  328. //System.out.println("Math.E"+Math.E);
  329. //System.out.println("del/T"+del/T);
  330. return Math.pow(Math.E,100*del/T);
  332. }
  333. /**
  334. *method: showMap(citymap)
  335. *param: CityMap[]
  336. *return: void
  337. */
  338. private static void showMap(CityMap[] cm)
  339. {
  340. System.out.println("the city map is:n______start________");
  341. int n=CITY_NUMBER;
  342. int count=0;
  343. for (int i=0;i<n;i++)
  344. {
  345. if (count % 18==0)
  346. {
  347. System.out.print("n");
  348. }
  349. count++;
  350. //System.out.print("--"+cm[i].getcity()+"("+cm[i].getxpos()+", "+cm[i].getypos()+")");
  351. System.out.print("--"+cm[i].getcity());
  352. }
  353. System.out.println("n_______end_________");
  355. }
  356. /**
  357. *method:getRandomInt
  358. */
  359. private static int getRandomInt()
  360. {
  361. Random random1 = new Random();
  362. return 1+(int)(Math.abs(random1.nextDouble())*(CITY_NUMBER-1))%(CITY_NUMBER-1);
  363. }
  364. /**
  365. *method: getRandomDouble()
  366. */
  367. private static double getRandomDouble()
  368. {
  369. Random random1 = new Random();
  370. return Math.abs(random1.nextDouble());
  371. }
  372. /**
  373. *method:getRouteValue()
  374. *param:
  375. *return: double
  376. */
  377. private static double getRouteValue()
  378. {
  379. CityMap[] cm=new CityMap[CITY_NUMBER];
  380. cm=copy(citymap);
  381. double routevalue=0.0;
  382. double px,py,qx,qy;
  383. for (int i=0;i<CITY_NUMBER-1;i++)
  384. {
  385. px=cm[i].getxpos();
  386. py=cm[i].getypos();
  387. qx=cm[i+1].getxpos();
  388. qy=cm[i+1].getypos();
  389. routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
  391. }
  392. double first_end;
  393. px=cm[0].getxpos();
  394. py=cm[0].getypos();
  395. qx=cm[CITY_NUMBER-1].getxpos();
  396. qy=cm[CITY_NUMBER-1].getypos();
  397. first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
  398. return routevalue+first_end;
  400. }
  401. /**
  402. *method:getRouteValue()
  403. *param:
  404. *return: double
  405. */
  406. private static double getRouteValue(CityMap[] cm)
  407. {
  408. //CityMap[] cm=new CityMap[CITY_NUMBER];
  409. //cm=citymap;
  410. double routevalue=0.0;
  411. double px,py,qx,qy;
  412. for (int i=0;i<CITY_NUMBER-1;i++)
  413. {
  414. px=cm[i].getxpos();
  415. py=cm[i].getypos();
  416. qx=cm[i+1].getxpos();
  417. qy=cm[i+1].getypos();
  418. routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
  419. // System.out.print("city_"+cm[i].getcity()+"   city_"+cm[i+1].getcity());
  420. // System.out.println("    "+(Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5)));
  421. //
  423. }
  424. double first_end;
  425. px=cm[0].getxpos();
  426. py=cm[0].getypos();
  427. qx=cm[CITY_NUMBER-1].getxpos();
  428. qy=cm[CITY_NUMBER-1].getypos();
  429. first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
  430. // System.out.print("city_"+cm[0].getcity()+"   city_"+cm[CITY_NUMBER-1].getcity());
  431. // System.out.println("    "+(Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5)));
  432. // System.out.println("_____________");
  433. return routevalue+first_end;
  435. }
  436. /**
  437. *method: setcitymap(CityMap[])
  438. *param:
  439. *return: void
  440. */
  441. private static void setcitymap(CityMap[] cm)
  442. {
  443. for (int i=0;i<CITY_NUMBER;i++)
  444. {
  445. citymap[i].setcity(cm[i].getcity());
  446. citymap[i].setxpos(cm[i].getxpos());
  447. citymap[i].setypos(cm[i].getypos());
  448. }
  449. }
  451. /**
  452. *method: settempcitymap(_citymap)
  453. *param:
  454. *return: void
  455. */
  457. private static CityMap[] settempcitymap(CityMap[] cm)
  458. {   
  460. CityMap[] c_m=new CityMap[CITY_NUMBER];
  461. for (int i=0;i<CITY_NUMBER;i++)
  462. {
  463. c_m[i]=new CityMap();
  464. c_m[i].setcity(cm[i].getcity());
  465. c_m[i].setxpos(cm[i].getxpos());
  466. c_m[i].setypos(cm[i].getypos());
  467. }
  468. return c_m;
  469. }
  470. /**
  471. *method: get time
  472. *param:
  473. *return: void
  474. */
  475. private static void getTime()
  476. {
  477. Date date = new Date(System.currentTimeMillis());
  478. String strdat="";
  479. strdat = date.toLocaleString();
  480. System.out.println("系统时间:"+strdat);
  482. }
  483. /**
  484. *method: copy a array
  485. */
  486. private static CityMap[] copy(CityMap[] cm)
  487. {
  488. CityMap[] c_m=new CityMap[CITY_NUMBER];
  489. for (int i=0;i<CITY_NUMBER;i++)
  490. {
  491. c_m[i]=new CityMap();
  492. c_m[i].setcity(cm[i].getcity());
  493. c_m[i].setxpos(cm[i].getxpos());
  494. c_m[i].setypos(cm[i].getypos());
  495. }
  496. return c_m;
  498. }
  500. /**
  501. *method: get another citymap from now citymap
  502. *param:  CityMap[]
  503. *return:  CityMap[]
  504. *change: 2006-3-27
  505. */
  506. private static CityMap[] getRoute(CityMap[] cmap)
  507. {
  508. CityMap[] cm=new CityMap[CITY_NUMBER];
  509. cm=copy(cmap);
  510. int n,m;
  511. n=getRandomInt();
  512. m=getRandomInt();
  513. //System.out.println("m=:"+m);
  514. //System.out.println("n=:"+n);
  515. while(m==n)
  516. {
  517. n=getRandomInt();
  518. m=getRandomInt();
  519. }
  520. //System.out.print("m=:"+m);
  521. //System.out.println("  n=:"+n);
  522. //CityMap[] _cm=new CityMap[CITY_NUMBER];
  523. //_cm=swap(cm);
  524. //System.out.print("m:"+m+" n:"+n);
  525. String TEMP_pc=cm[m].getcity();
  526. double TEMP_px=cm[m].getxpos();
  527. double TEMP_py=cm[m].getypos();
  528. cm[m].setcity(cm[n].getcity());
  529. cm[m].setxpos(cm[n].getxpos());
  530. cm[m].setypos(cm[n].getypos());
  531. cm[n].setcity(TEMP_pc);
  532. cm[n].setxpos(TEMP_px);
  533. cm[n].setypos(TEMP_py);
  535. return cm;
  537. }
  540. /**
  541. *method: get another citymap from now citymap
  542. *param:  CityMap[]
  543. *return:  CityMap[]
  544. *change: 2006-3-27 add
  545. */
  546. private static CityMap[] getRoute_(CityMap[] cmap)
  547. {
  548. CityMap[] cm=new CityMap[CITY_NUMBER];
  549. cm=copy(cmap);
  550. int a,b,c;
  551. a=getRandomInt();
  552. b=getRandomInt();
  553. c=getRandomInt();
  554. System.out.println("a=:"+a);
  555. System.out.println("b=:"+b);
  556. System.out.println("c=:"+c);
  557. while(a==b||a==c||b==c)
  558. {
  559. a=getRandomInt();
  560. b=getRandomInt();
  561. c=getRandomInt();
  562. }
  563. //System.out.print("m=:"+m);
  564. //System.out.println("  n=:"+n);
  565. //CityMap[] _cm=new CityMap[CITY_NUMBER];
  566. //_cm=swap(cm);
  567. //System.out.print("m:"+m+" n:"+n);
  568. String TEMP_pc=cm[a].getcity();
  569. double TEMP_px=cm[a].getxpos();
  570. double TEMP_py=cm[a].getypos();
  571. cm[a].setcity(cm[b].getcity());
  572. cm[a].setxpos(cm[b].getxpos());
  573. cm[a].setypos(cm[b].getypos());
  574. cm[b].setcity(cm[c].getcity());
  575. cm[b].setxpos(cm[c].getxpos());
  576. cm[b].setypos(cm[c].getypos());
  577. cm[c].setcity(TEMP_pc);
  578. cm[c].setxpos(TEMP_px);
  579. cm[c].setypos(TEMP_py);
  581. return cm;
  583. }
  587. };