这个程序实现了模拟退火，用于计算att48数据集。
这个程序由两部分组成SA1和Line1。SA1是主程序，结合了蚁群算法改写的。主要思路是先用蚁群算法生成一个原始路径，然后随机交换两个城市的位置，如果得到的距离好于最优值或者满足退火条件就保留这次更改，不断迭代直到最优值到达要求。
Line1程序用于画图。
程序中一共有4个本地路径
d:/工业/hk/aaa.csv 保存SA1的计算结果
d:/工业/hk/统计.csv 保存每步的距离变化
d:/工业/hk/t/zz.csv 48个城市的坐标
d:/工业/hk/重排.csv 临时文件用于画图
性能测试数据
用这组参数进行性能测试
SA(48, 1000, 2000, 0.99815 , 1500, "d:/工业/hk/t/zz.csv" );
| 步 | 耗时ms | 耗时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 |
这个程序共运行了15次，达到10628平均需要288步，4.42分钟。每一步需要交换2百万次。也就是平均每次计算需要交换5.76亿次才能达到最优值。
SA1代码
Line1代码
d:/工业/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 {
//实现了退火算法
static int cityNum; // 城市数量，编码长度
static int N;// 每个温度迭代次数
static int T;// 重复降温次数
static double a;// 降温系数
static double t1;// 初始温度
static int[][] distance; // 距离矩阵
static int bestT=0;// 最佳出现代数
static int[] Ghh;// 初始路径编码
static int ge;
static int[] bestGhh;// 最好的路径编码
static int be;
static int[] tempGhh;// 存放临时编码
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;
}
// 读取数据
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+"************ ");
// 读取一行数据，数据格式1 6734 1453
strbuff = data.readLine();
// 字符分割
String[] strcol = strbuff.split(",");
x[i] = Integer.valueOf(strcol[1]);// x坐标
y[i] = Integer.valueOf(strcol[2]);// y坐标
}
// 计算距离矩阵
for (int i = 0; i < cityNum - 1; i++) {
distance[i][i] = 0; // 对角线为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;)// 编码长度
{
Ghh[i] = random.nextInt(65535) % cityNum; //得到是小于cityNum的数
// 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) { //检查没有重复
i++;
}
}
}
// 复制编码Gha到Ghb
public static void copyGh(int[] Gha, int[] Ghb) {
for (int i = 0; i < cityNum; i++) {
Ghb[i] = Gha[i];
}
}
// 计算距离
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;
}
// 邻域交换，得到邻域 ，随机两个值交换
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(); //用随机的方式生成原始数列
copyGh(Ghh, bestGhh);// 复制当前编码Ghh到最好编码bestGh
be = evaluate(Ghh);
ge = be;
int k = 0;// 降温次数
int n = 0;// 迭代步数
double t = t1;
double r = 0.0;
int count=0;
while (k < T) { //降温次数
n = 0;
while (n < N) { //每个温度迭代步长
Linju(Ghh, tempGhh);// 得到当前编码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);
//随着温度的降低这个冗余度也会逐渐减小，所以增大初始温度，减慢温度下降速度更有利收敛
if( Math.abs(Math.exp((ge - te) / t) -0)<0.00001 )
{
count++;
}
ge = te;
}
n++;
}
t = a * t;
//控制t值的可能范围，这个是最为核心的参数
if(k==T-1)
{
System.out.println(t+" "+a+" "+k+" "+count+ " "+bestT);
}
//0.08634329 2000
//0.043171644 1000
k++;
}
if(be<min)
{
min=be;
}
return be;
}
public static void route() throws IOException {
int max=100000;
FileWriter fileWriter1=new FileWriter("d:/工业/hk/aaa.csv");
FileWriter fileWriter2=new FileWriter("d:/工业/hk/统计.csv");
int count=0;
while(max>10628 )
{
count++;
//城市数量 每个温度迭代次数 重复 降温次数 初始温度 降温系数
max= SA(48, 1000, 2000, 0.99815 , 1500, "d:/工业/hk/t/zz.csv" );
// N T a t1
fileWriter2.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:/工业/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:/工业/hk/重排.csv");
String wee= read("d:/工业/hk/aaa.csv");
String[] tee=Pattern.compile(",").split(wee);
String we = read("d:/工业/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:/工业/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 |