tsp.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 TSP {
  int cityCount = 42;
  int[][] weights;
  int[] paths;
  double kpower = 0;
  double leakRate = .01;
  double freeCharge = 10000;

  public TSP() {
    readWeights();
    initPath();
  }

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

//      if (tcount++ % 1000000 == 0) {
//        System.out.println("tpower = " + (kpower + freeCharge) + "; kpower = " +
//                           kpower + "; freeCharge = " + freeCharge);
//      }
    }

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

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

    if (p1 == p2)return false;

    double change = 0;

    if (Math.abs(p1 - p2) == 1) {
      if (p1 > p2) {
	change = weight(p2 - 1, p2) + weight(p1, p1 + 1) -
	    weight(p1, p2 - 1) - weight(p2, p1 + 1);
      }
      else {
	change = weight(p2 + 1, p2) + weight(p1, p1 - 1) -
	    weight(p1, p2 + 1) - weight(p2, p1 - 1);
      }
    }
    else if (Math.abs(p1 - p2) == cityCount - 1) {
      if (p1 == 0) {
	change = weight(p2 - 1, p2) + weight(p1, p1 + 1) -
	    weight(p1, p2 - 1) - weight(p2, p1 + 1);
      }
      else {
	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) {
      kpower -= change;
      freeCharge += change * (1 - leakRate);
//      freeCharge += change * (1 - change/kpower);

      int temp = paths[p1];
      paths[p1] = paths[p2];
      paths[p2] = temp;
      return true;
    }
    else if (change + freeCharge >= 0) {

//      double poss = Math.exp(change*5/kpower);
//      if(Math.random() > poss)
//        return false;

      kpower -= change;
      freeCharge += change;

      int temp = paths[p1];
      paths[p1] = paths[p2];
      paths[p2] = temp;

      if(change ==0)
	return false;

      return true;
    }

    return false;
  }

  public void readWeights() {
    weights = new int[cityCount][];

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

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

	if (line == null) {
	  break;
	}

	StringTokenizer st = new StringTokenizer(line, " ");
	for (int j = 0; j < cityCount; j++) {
	  weights[i][j] = Integer.parseInt(st.nextToken());
	}
      }

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

//    for (int i = 0; i < cityCount; i++) {
//      System.out.println("");
//      for (int j = 0; j < cityCount; j++) {
//        System.out.print(weights[i][j] + " ");
//      }
//    }

  }

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

  double weight() {
    double p = weights[paths[0]][paths[weights.length - 1]];
    for (int i = 0; i < paths.length - 1; i++) {
      p += weights[paths[i]][paths[i + 1]];
    }
    return p;
  }

  int 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;

    return weights[paths[i]][paths[j]];
  }

  public static void main(String[] args) {
//    for(int i=0; i<100; i++){
//      TSP tsp = new TSP();
//      tsp.optimize();
//    }
    TSP tsp = new TSP();
    for(int i=0; i<100; i++){
      tsp.freeCharge = tsp.kpower*10 ;
      tsp.optimize();
    }
  }

}