tsp1.java

新型模拟退火算法解决TSP优化问题。自能退火。可用于大多数情况下的优化问题。

package test;

import java.io.*;
import java.util.*;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class TSP1 {
    int cityCount = 24978;
//    int cityCount = 100;
//    int cityCount = 724;

    double[] xcoords;
    double[] ycoords;
    int[] paths;
    double leakRate = .001;
    double potentialEnergy = 0; //势能
    double kineticEnergy = 100000; //动能


    public TSP1() {
	readCoords();
	initPath();
    }

    void optimize(int range, long limit) {
	int count = 0;
	long tcount = 0;
	while (count < limit) {
	    if (disturb(range)) {
		count = 0;
	    }
	    else {
		count += 1;
	    }

	    if (tcount++ % 1000000 == 0) {
		System.out.println("tpower = " + (potentialEnergy + kineticEnergy) +
				   "; Potential Energy = " +
				   potentialEnergy + "; Kinetic Energy = " + kineticEnergy);
	    }
	}

	System.out.println("");
	System.out.println("Potential Energy = " + potentialEnergy);
	System.out.println("weight = " + weight());
//	for (int i = 0; i < paths.length; i++) {
//	    System.out.println("paths[" + i + "] = " + paths[i]);
//	}
    }

    boolean disturb(int range) {
	int p1 = (int) (cityCount * Math.random());
	int p2 = (p1 + (int) (range * Math.random()))%cityCount;

	if (p1 == p2)return false;

	//let p2 > p1
	if(p2 < p1){
	    int tmp = p2;
	    p2 = p1;
	    p1 = tmp;
	}

	double change = 0;

	int dist = p2-p1;

	if (dist == 1) {
		change = weight(p2 + 1, p2) + weight(p1, p1 - 1) -
		    weight(p1, p2 + 1) - weight(p2, p1 - 1);
	}
	else if (dist == cityCount - 1) {
		change = weight(p2 - 1, p2) + weight(p1, p1 + 1) -
		    weight(p1, p2 - 1) - weight(p2, p1 + 1);
	}
	else {
	    change =
		weight(p1 - 1, p1) + weight(p1, p1 + 1) +
		weight(p2 - 1, p2) + weight(p2, p2 + 1) -
		weight(p1 - 1, p2) - weight(p2, p1 + 1) -
		weight(p2 - 1, p1) - weight(p1, p2 + 1);
	    if (change > 0) {
		potentialEnergy -= change;
		kineticEnergy += change * (1 - leakRate);
		int temp = paths[p1];
		paths[p1] = paths[p2];
		paths[p2] = temp;
		return true;
	    }
	    change =
		weight(p1, p1 + 1) + weight(p2, p2 + 1) -
		weight(p1, p2) - weight(p2 + 1, p1 + 1);
	}

	if (change + kineticEnergy < 0)
	    return false;

	if (change > 0) {
	    potentialEnergy -= change;
	    kineticEnergy += change * (1 - leakRate);
	}
	else {
	    potentialEnergy -= change;
	    kineticEnergy += change;
	}

	if (dist == 1 || dist == cityCount - 1) {
	    int temp = paths[p1];
	    paths[p1] = paths[p2];
	    paths[p2] = temp;
	}
	else {
	    reverse(paths, p1+1, p2-p1);
	}
	return true;
    }
    void reverse(int[] paths, int offset, int length){
	int count = length/2;
	int temp = 0 ;
	int right = offset+length-1;
	for(int i=0; i<count; i++){
	    temp = paths[offset + i];
	    paths[offset+i] = paths[right-i];
	     paths[right-i] = temp;
	}
    }

    public void readCoords() {
	xcoords = new double[cityCount];
	ycoords = new double[cityCount];

	try {
	    BufferedReader br = new BufferedReader(new InputStreamReader(new
		FileInputStream(cityCount+".txt")));

	    for (int i = 0; i < cityCount; i++) {
		String line = br.readLine();

		if (line == null) {
		    break;
		}

		StringTokenizer st = new StringTokenizer(line, " ");
		String index =  st.nextToken();
		xcoords[i] = Double.parseDouble(st.nextToken());
		ycoords[i] = Double.parseDouble(st.nextToken());
//		System.out.println("read coord " + index + " " + xcoords[i] + " " + ycoords[i]);
	    }

	    br.close();
	}
	catch (Exception ex) {
	    ex.printStackTrace();
	}

    }

    public void initPath() {
	paths = new int[cityCount];
	for (int i = 0; i < paths.length; i++) {
	    paths[i] = i;
	}

	potentialEnergy = weight();
    }

    double weight() {
	double p = weight(0, cityCount - 1);
	for (int i = 0; i < paths.length - 1; i++) {
	    p += weight(i, i + 1);
	}
	return p;
    }
    double weight(int i, int j) {
	if (i == -1) i = cityCount - 1;
	if (i == cityCount) i = 0;
	if (j == -1) j = cityCount - 1;
	if (j == cityCount) j = 0;

	double dx = xcoords[paths[i]] - xcoords[paths[j]];
	double dy = ycoords[paths[i]] - ycoords[paths[j]];

	return Math.sqrt(dx * dx + dy * dy);
    }

    public static void main(String[] args) {
//	for(int i=1; i<=72;i++){
//	    for(int j=1; j<=24; j++){
//		String name = "ftp://srtm.csi.cgiar.org/SRTM_Data_ArcAscii/";
//		name += "srtm_";
//		if(i<10){
//		    name += "0";
//		}
//		name += i;
//		name += "_";
//		if(j<10){
//		    name += "0";
//		}
//		name += j;
//		name += ".zip";
//		System.out.println(name);
//	    }
//	}


	TSP1 tsp = new TSP1();
	tsp.optimize(tsp.cityCount, 1000000);
   }

}