tspsolutionwithsa.java

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

package test;

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

public class TSPSolutionWithSA extends SAImpl{
    CityInfo cityInfo;

    int[] paths;

    public TSPSolutionWithSA(CityInfo cInfo, double lRate, double kEnergy) {
	super(lRate, kEnergy);
	this.cityInfo = cInfo;
    }

    public double weight() {
	double p = weight(0, cityInfo.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 = cityInfo.cityCount - 1;
	if (i == cityInfo.cityCount) i = 0;
	if (j == -1) j = cityInfo.cityCount - 1;
	if (j == cityInfo.cityCount) j = 0;

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

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

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

	potentialEnergy = weight();
    }

    public void randomPath(int time) {
	for (int i = 0; i < time; i++) {
	    int p1 = (int) (cityInfo.cityCount * Math.random());
	    int p2 = (p1 + (int) (cityInfo.cityCount * Math.random())) %
		cityInfo.cityCount;

	    if (p1 != p2) {
		int temp = paths[p1];
		paths[p1] = paths[p2];
		paths[p2] = temp;
	    }
	}
    }

    public 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]);
//	}
    }

    public boolean disturb(int range) {
	int p1 = (int) (cityInfo.cityCount * Math.random());
	int p2 = (p1 + (int) (range * Math.random()))%cityInfo.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 == cityInfo.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 == cityInfo.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;
	}
    }

}