ga_tsa.java

利用遗传算法解决TSP旅行商问题的Java原码

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

public class GA_TSA
{
	//define variable
	private static final int GENE_NUMBER=51;  //基因数目
	private static final int GNEERATION=300;  //定义代
	private static final int TRIBE=4*GENE_NUMBER;			//定义种群大小
	private static final double P_SELECT=0.5; //选择产生下一代概率	
	private static final double P_CROSSOVER=0.3; //	交配的概率	
	private static final double P_MUTATION=0.1;	//变异的概率
	private static CityMap[][] clan=new CityMap[TRIBE][GENE_NUMBER]; //city position
	//private static QuickSorter st=new QuickSorter();
	//defien variable over
	
	
	/*******************************main****************************************/
	public static void main(String args[])
	{
		CityMap[] citymap=new CityMap[GENE_NUMBER];
		construct(citymap);
		initialize(citymap);
		clan=getAncestorTribe(citymap);
		double mini=getMini(clan);
		System.out.println("最初最优路径长度:\t"+mini);
		int count=0;
		CityMap[] result=new CityMap[GENE_NUMBER];
		construct(result);
		while (count<GNEERATION)//while ________________1
		{	

			clan=generateNextTribe(clan);
			//
			System.out.print("  D:\t"+count);
			double temp=getMini(clan);
			if (temp<mini)
			{
				mini=temp;
				System.out.println("\t Change:\t"+temp);
				result=getMiniCityMap(clan);
			}
			else
			{
				System.out.println("\t No Change:\t");
			}
			//
			count++;
		}//while_over____________________1

		System.out.println("*******************");
		System.out.println("最优路径长度为："+mini);
		//showMap(result);

	}//main_over
	/********************************main over****************************************************/

	/*****************************the following is method**********************************/
	/**
	*method: generateNextTribe(CityMap[][] cm)
	*return: CityMap[][]
	*desp: based on a tribe and certain probility cross and mutation  to  generate another tribe!
	*/
	private static CityMap[][] generateNextTribe(CityMap[][] cm) 
	{	
		CityMap[][] chromosome_new=new CityMap[TRIBE][GENE_NUMBER];
		constructCityMap(chromosome_new,TRIBE,GENE_NUMBER);
		cmcopy(cm,0,(int)(TRIBE*P_SELECT),chromosome_new,0);

		CityMap[][] chromosome_select=new CityMap[(int)(TRIBE*P_SELECT)][GENE_NUMBER];
		constructCityMap(chromosome_select,(int)(TRIBE*P_SELECT),GENE_NUMBER);
		chromosome_select=selectChromosome(cm);
	
		
		int tribe_num=(int)(TRIBE*P_SELECT);
		
		do
		{
			// if crossover is seccess tribe_num+2
			if (crossover(chromosome_select,chromosome_new,tribe_num))
			{
				tribe_num+=2;
			}
			//if mutation is success,trive_num+1
			if (mutation(chromosome_select,chromosome_new,tribe_num))
			{
				tribe_num+=1;
			}
		}
		while (tribe_num<TRIBE);
		//test:
		//System.out.println("ntlizheng____last____chromosome_new");
		//showClan(chromosome_new);
		return chromosome_new;

		
		
	}//generateNextTribe(CityMap[][] cm) 

	/**
	*method: selectChromosome(cm)
	*return: CityMap[][]
	*description: select certain Chromosome to ready for generate next tribe;
	*/
	private static CityMap[][] selectChromosome(CityMap[][] cm)
	{
		//SORT the original tribe
//		getTime();


//		cm=sortChromosome(cm);	//nt_change 2006-4-3


//		QuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorter
//		QuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorterQuickSorter
		
		QuickSorter st=new QuickSorter();
		DoubleSortTool doubletool=new DoubleSortTool();
		st.Sort(cm,doubletool,true);

//		ShellSorterShellSorterShellSorterShellSorterShellSorterShellSorterShellSorterShellSorter
//		ShellSorterShellSorterShellSorterShellSorterShellSorterShellSorterShellSorterShellSorter

//		ShellSorter st=new ShellSorter();
//		DoubleSortTool doubletool=new DoubleSortTool();
//		st.Sort(cm,doubletool,true);



//		showClan(cm);
//		getTime();
//		System.exit(0);
		//
		CityMap[][] cm_=new CityMap[(int)(TRIBE*P_SELECT)][GENE_NUMBER];
		constructCityMap(cm_,(int)(TRIBE*P_SELECT),GENE_NUMBER);
		cmcopy(cm,0,(int)(TRIBE*P_SELECT),cm_,0);
		return cm_;
		
	}
	/**
	*method: sortChromosome(cm)
	*return: CityMap[][] 
	*description: sort the CityMap[][] ,get a CityMap[][] by descending
	*/
	private static CityMap[][] sortChromosome(CityMap[][] cm)
	{
		CityMap[][] cm_=new CityMap[TRIBE][GENE_NUMBER];
		constructCityMap(cm_,TRIBE,GENE_NUMBER);
		cmcopy(cm,0,TRIBE,cm_,0);
		for (int i=0;i<TRIBE;i++)
		{	
			int temp_small=i;
			for (int c=i+1;c<TRIBE;c++ )
			{
				double temp_c=getvalue(cm_[c]);
				double temp_d=getvalue(cm_[temp_small]);
				if (temp_c<temp_d)
				{
					temp_small=c;
				}
			}
			swap(cm_,i,temp_small);
		}
		return cm_;
	}

	/**
	*mehtod:crossover(CityMap[][] c_select,CityMap[][] c_new,int tribe_num)
	*return: boolean
	*description: crossover
	*/
	private static boolean crossover(CityMap[][] cm_select,CityMap[][] cm_new,int tribe_num)
	{
		
		if (tribe_num+1<TRIBE)
		{
			//
			double u_p_crossover=getRandomDouble();
			if (u_p_crossover<P_CROSSOVER)
			{
				//
				crossoverChromosome(cm_select,cm_new,tribe_num);

				return true;
			}
			else
			{
				return false;
			}
		}
		else
		{
			return false;
		}
	}
	/**
	*mehtod:mutation(CityMap[][] c_select,CityMap[][] c_new,int tribe_num)
	*return: boolean
	*description: mutation
	*/
	private static boolean mutation(CityMap[][] cm_select,CityMap[][] cm_new,int tribe_num)
	{
		
		if (tribe_num<TRIBE)
		{
			//
			double u_p_crossover=getRandomDouble();
			if (u_p_crossover<P_CROSSOVER)
			{
				//
				mutationChromosome(cm_select,cm_new,tribe_num);
				return true;
			}
			else
			{
				return false;
			}

		}
		else
		{
			return false;
		}
	}//method mutation
	
	/*wrong!!!!!!!!!!!!!*/
	private static void constructCityMap(CityMap[][] u_cm,int t,int cm)
	{	
		//CityMap[][] u_cm=new CityMap[t][cm];
		for (int m=0;m<t ;m++)
		{
			CityMap[] temp=new CityMap[cm];
			for (int n=0;n<cm ;n++ )
			{
				temp[n]=new CityMap();
			}
			u_cm[m]=temp;
		}
		//return u_cm;
	}
	/**
	*method:
	*description: copy a array to another
	*/
	private static void cmcopy(CityMap[][] cm_from,int start_f,int end,CityMap[][] cm_to,int start)
	{
		//CityMap[][] cm_new=new CityMap[end-start][GENE_NUMBER];
		if (end<=start_f)
		{
			System.out.println("Wrong! from method cmcopy!/n Note:end should bigger than start!");
			System.out.println("start="+start_f+"  end="+end);
			System.exit(1);
		}
		//constructCityMap(cm_new,end-start,GENE_NUMBER);
		for (int i=0;i<end-start_f ;i++)
		{
			cm_to[start+i]=cm_from[start_f+i];
		}
	}

	/**
	*method:
	*description: copy a array to another
	*/
	private static void cmcopy(CityMap[] cm_from,int start_f,int len,CityMap[] cm_to,int start)
	{
		//CityMap[]cm_new=new CityMap[end-start][GENE_NUMBER];

		//constructCityMap(cm_new,end-start,GENE_NUMBER);
		for (int i=1;i<len ;i++)
		{
			cm_to[(start+len-i)%GENE_NUMBER]=cm_from[(start_f+len-i)%GENE_NUMBER];
		}
	}
	/**
	*method:getvalue()
	*param:
	*return: double
	*/
	private static double getvalue(CityMap[] cm)
	{
		//CityMap[] cm=new CityMap[GENE_NUMBER];
		//cm=citymap;
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=0;i<GENE_NUMBER-1;i++)
		{
			px=cm[i].getxpos();
			py=cm[i].getypos();
			qx=cm[i+1].getxpos();
			qy=cm[i+1].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		}
		double first_end;
		px=cm[0].getxpos();
		py=cm[0].getypos();
		qx=cm[GENE_NUMBER-1].getxpos();
		qy=cm[GENE_NUMBER-1].getypos();
		first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		return routevalue+first_end;

	}
	private static double getvalue(CityMap[] cm,int t,int len)
	{
		//CityMap[] cm=new CityMap[GENE_NUMBER];
		//cm=citymap;
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=t;i<len-1;i++)
		{
			//System.out.println("i=  "+i);
			px=cm[(i%GENE_NUMBER)].getxpos();
			py=cm[(i%GENE_NUMBER)].getypos();
			qx=cm[((i+1)%GENE_NUMBER)].getxpos();
			qy=cm[(i+1)%GENE_NUMBER].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		}
		
		return routevalue;

	}
	/**
	*method:swap
	*description: swap the element of the citymap[][]
	*/
	private static void swap(CityMap[][] cm_,int m,int n)
	{
		if (m!=n)
		{
			CityMap[] temp_cm=new CityMap[GENE_NUMBER];
			//construct(CityMap[] temp_cm,GENE_NUMBER);
			temp_cm=cm_[m];
			cm_[m]=cm_[n];
			cm_[n]=temp_cm;
		}	
	}
	/**
	*method:swap
	*description: swap the element of the citymap[]
	*/
	private static void swap(CityMap[] cm_,int m,int n)
	{
		if (m!=n)
		{
			CityMap temp_cm=new CityMap();
			//construct(CityMap[] temp_cm,GENE_NUMBER);
			temp_cm=cm_[m];
			cm_[m]=cm_[n];
			cm_[n]=temp_cm;
		}	
	}
	/**
	*
	*/
	private static void initialize(CityMap[] cm)
	{
		//
		int n=0;
		try
		{
			n=getCityNumber();
		}
		catch (IOException e)
		{
			e.toString();
		}
		if (n!=GENE_NUMBER)
		{
			throw new NotEqulalException("\nCity number shouder be equal the "
			+"varial \"GENE_NUMBER\" you declare!\n"
			+"GENE_NUMBER="+GENE_NUMBER+"   city number="+n);
		}
		String[] _city=new String[GENE_NUMBER];
		try
		{
			_city=getCityString();
		}
		catch (IOException e)
		{
			e.toString();
		}
		
		for (int i=0;i<n;i++)
		{
			cm[i]=new CityMap(_city[i]);
		}		
	}
	/**
	*method:getCityNumber
	*param: null
	*return: int the number of the citytxt file
	*/
	private static int getCityNumber() throws IOException
	{
		BufferedReader br=new BufferedReader(new FileReader("array.txt"));
		int n=0;
		String Str_="";
		while ((Str_=br.readLine()) != null) 
        {
			n++;
		}
		return n;
	}
	/**
	*method: getCityString
	*param: null
	*return String[]
	*/
	private static String[] getCityString()throws IOException
	{
		//
		BufferedReader br=new BufferedReader(new FileReader("array.txt"));
		String Str="";
		String Str_="";

		char regx=';';
		int n=0;
		while ((Str_=br.readLine()) != null) 
        {
			n++;
			Str+=Str_;
			Str+=regx;

		}
		Str=removeLastRegx(Str);
		
		//get the line to a array[]
		String[] _array=new String[n];
		_array=splitString(Str,(int)regx);
		return _array;
	}
	/**
	*method: splitString
	*param: args the string to split
	*param: c	the char you want to match
	*return:  a array 
	*/
	public static String[] splitString(String arg,int c)
	{	
		String[] _array=new String[GENE_NUMBER];
		int cc=0;
		while(arg.indexOf(c)!=-1)
        {
			_array[cc]=arg.substring(0,arg.indexOf(c));
			arg=arg.substring(arg.indexOf(c)+1,arg.length());
			cc++;
        }
		_array[cc]=arg;