模拟退火Java实现

本代码为用Java实现的模拟退火求解旅行商问题，希望对大家有帮助

/**
 * 实现Inter.java接口中的函数
 * 不要添加 package语句
 */
import java.util.*;
import java.io.*;

public class Annealing implements Inter{
		/**
		 * 不要定义static 的变量
		 */
	/*
	 初始参数的确定
	康立山等人的方法：
	初始温度t0=280；
	 在每个温度下采用固定的迭代次数，Lk=100n，n为城市数；
	温度的衰减系数＝0.92，即tk+1=0.92×tk；
	算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。*/

	class city{
		public String name;
		public double x;
		public double y;
		public city（String s）
		{
			String[] tmp = s.split（“\\s+“）;
			name = tmp[0];
			x = Double.parseDouble（tmp[1]）;
			y = Double.parseDouble（tmp[2]）;
		}
	}

	
	Vector vec = new Vector（）;
	int n  = 0;
	int num = 0;
	public void getStrategy（String inputFile）{
		try{
			File f = new File（inputFile）;
			FileReader fr = new FileReader（f）;
			BufferedReader br = new BufferedReader（fr）;
			String line = br.readLine（）;
			n = Integer.parseInt（line）;
			while（（line = br.readLine（）） != null）
			{
				vec.add（new city（line））;
			}
		}catch （IOException e） {
			// TODO Auto-generated catch block
			e.printStackTrace（）;
		}
		
		int route1[] = new int[n];
		int route2[] = new int[n];
		
		double t = 2;	
		double best;
		int a[] = new int[n];
		for（int i = 0;i < n;i++）
		{
			a[i] = i;
		}
		double f  = getValue（a）;
		best = f;
		while（t >= 0.001）
		{		
			for（int i = 0;i < 10*n;i ++）
			{
				int aa[] = getPath（a）;
				double ff = getValue（aa）;
				if（ff < f）
				{
					num ++;
					f = ff;
					a = aa;
					route1 = a;
					if（best > f）
					{
						best = f;
						route2 = a;
					}
				}
				if（ff >= f ）
				{
					double db = Math.exp（-1*（ff-f）/t）;
					if （db > Math.random（））
					{
						num ++;
						f = ff;
						a = aa;
						route1 = a;
					}
				}
			}
			t *= 0.95;
		}
		System.out.print（“（“）;
		for（int i = 0;i < n-1;i ++）
			System.out.print（vec.get（route1[i]）.name + ““）;
		System.out.println（vec.get（route1[n-1]）.name + “） “+f）;
		
		System.out.print（“（“）;
		for（int i = 0;i < n-1;i ++）
			System.out.print（vec.get（route2[i]）.name + ““）;
		System.out.println（vec.get（route2[n-1]）.name + “） “ + best）;
		
		System.out.println（num）;
	}
	public int[] getPath（int a[]）
	{
		int s = a.length;
		int b[] = new int[s];
		Random r = new Random（）;
		int x = r.nextInt（10）;
		int y =  r.nextInt（10）;
		while（y == x）
			y = r.nextInt（10）;
		if（x < y）{
		int k = 0;
		for（int i = 0;i < s;i++）
		{
			if（i < x）
				b[i] = a[i];
			else if（i > y）
				b[i] = a[i];
			else {
				b[i] = a[y - k];
				k++;
			}
		}
		}
		else {
			int yy = yk = 1;
			for（int i = 0;i < n;i ++）
			{
				if（i <= yy）
				{
					b[i] = a[y];
					y -- ;
				}
				else if（i >= x）
				{
					b[i] = a[s-k];
					k ++;
				}
				else
					b[i] = a[i];
				
			}
		}
		if（Arrays.equals（a b））
			return getPath（a）;	
		else
			return b;
	}

	public double getValue（int a[]）	
	{
		double length = 0;
		int k = a.length - 1;
		for（int i = 0;i < k;i++）
		{
			double tmp

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3493  2009-12-15 10:49  模拟退火\Annealing.java

     文件        152  2009-12-08 23:34  模拟退火\Inter.java

     文件        287  2009-12-15 10:33  模拟退火\Test.java

     文件      26112  2010-05-26 20:13  模拟退火\说明.doc

     目录          0  2010-05-26 20:13  模拟退火

----------- ---------  ---------- -----  ----

                30044                    5