ga_tsa.java

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

    	return _array;
	}
	/**
	*method: cut the last char form the String
	*/
	public static String removeLastRegx(String args)
	{
		//return args.substring(0,args.length()-1);
		if (args!=null)
		{
			return args.substring(0,args.length()-1);
		}
		else
		{
			return args;
		}
	}
	/**
	*
	*/
	private static void construct(CityMap[] cm)
	{
		for (int i=0;i<GENE_NUMBER;i++)
		{
			cm[i]=new CityMap();
		}
	}
		/**
	*method: showMap(citymap)
	*param: CityMap[]
	*return: void
	*/
	private static void showMap(CityMap[] cm)
	{
		System.out.println("/nthe city map is:______start________");
		int n=GENE_NUMBER;
		int count=1;
		for (int i=0;i<n;i++)
		{	
			if (count % 18==0)
			{
				System.out.print("\n");
			}
			count++;
			//System.out.print("--"+cm[i].getcity()+"("+cm[i].getxpos()+", "+cm[i].getypos()+")");
			System.out.print("--"+cm[i].getcity());
		}
		System.out.println("\n_______end_________");

	}
	/**
	*method: get another citymap from now citymap
	*param:  CityMap[]
	*return:  CityMap[]
	*change: 2006-3-27
	*/
	private static CityMap[] getRoute(CityMap[] cmap)
	{
		CityMap[] cm=new CityMap[GENE_NUMBER];
		cm=copy(cmap);
		int n,m;
		n=getRandomInt();
		m=getRandomInt();
		//System.out.println("m=:"+m);
		//System.out.println("n=:"+n);
		while(m==n)
		{
			n=getRandomInt();
			m=getRandomInt();
		}
		String TEMP_pc=cm[m].getcity();
		double TEMP_px=cm[m].getxpos();
		double TEMP_py=cm[m].getypos();
		cm[m].setcity(cm[n].getcity());
		cm[m].setxpos(cm[n].getxpos());
		cm[m].setypos(cm[n].getypos());
		cm[n].setcity(TEMP_pc);
		cm[n].setxpos(TEMP_px);
		cm[n].setypos(TEMP_py);
		
		return cm;
		
	}
	/**
	*method: copy a array
	*/
	private static CityMap[] copy(CityMap[] cm)
	{
		CityMap[] c_m=new CityMap[GENE_NUMBER];
		for (int i=0;i<GENE_NUMBER;i++)
		{	
			c_m[i]=new CityMap();
			c_m[i].setcity(cm[i].getcity());
			c_m[i].setxpos(cm[i].getxpos());
			c_m[i].setypos(cm[i].getypos());
		}
		return c_m;

	}
	/**
	*method: getRandomDouble()
	*/
	private static double getRandomDouble()
	{
		Random random1 = new Random();
		return Math.abs(random1.nextDouble());
	}
	/**
	*method:getRandomInt
	*/
	private static int getRandomInt()
	{
		Random random1 = new Random();
		return (int)(Math.abs(random1.nextDouble())*(GENE_NUMBER))%(GENE_NUMBER);
	}
	private static int getRandomInt(int n)
	{
		Random random1 = new Random();
		return (int)(Math.abs(random1.nextDouble())*(n))%(n);
	}
	private static int getSelectRandomInt()
	{
		Random random1 = new Random();
		return (int)(Math.abs(random1.nextDouble())*((int)(TRIBE*P_SELECT)))%((int)(TRIBE*P_SELECT));
	}
	/***********************crossover & mutation start*******************************/
	/**
	*i want find three way to cross!
	*/

	/*

	private static void crossoverChromosome(CityMap[][] cm_select,CityMap[][] cm_new,int p)
	{//1
		
		
		CityMap[] cm_x=new CityMap[GENE_NUMBER];
		construct(cm_x);
		CityMap[] cm_y=new CityMap[GENE_NUMBER];
		construct(cm_y);
		int m,n;
		m=getSelectRandomInt();
		n=getSelectRandomInt();
		while(m==n)
		{
			n=getSelectRandomInt();
			m=getSelectRandomInt();
		}
		cm_x=copy(cm_select[m]);
		cm_y=copy(cm_select[n]);
		//
		int a, b;
		int c, d;
		a=getRandomInt();
		b=getRandomInt();
		while(a==b)
		{
			a=getRandomInt();
			b=getRandomInt();
		}
		
		c=getNo(cm_y,cm_x[a].getcity());
		d=getNo(cm_y,cm_x[b].getcity());
		
		swap(cm_x,c,d);
		swap(cm_y,a,b);
		//add to clan
		cm_new[p]=cm_x;
		cm_new[p+1]=cm_y;
		//test:
		//System.out.println("cm_new["+p+"]"+getvalue(cm_new[p]));
		//System.out.println("cm_new["+(p+1)+"]"+getvalue(cm_new[p+1]));
	}
	*/
	////////////////////////////////////
	private static void crossoverChromosome(CityMap[][] cm_select,CityMap[][] cm_new,int p)
	{//2
		
		
		CityMap[] cm_x=new CityMap[GENE_NUMBER];
		construct(cm_x);
		CityMap[] cm_y=new CityMap[GENE_NUMBER];
		construct(cm_y);
		int m,n;
		m=getSelectRandomInt();
		n=getSelectRandomInt();
		while(m==n)
		{
			n=getSelectRandomInt();
			m=getSelectRandomInt();
		}
		cm_x=copy(cm_select[m]);
		cm_y=copy(cm_select[n]);
		//
		int a, len;
		int c, d;
		double d_x,d_y;
		String str;
//		a=getRandomInt();
//		len=getRandomInt(6);
//		String str=getCityName(cm_x,a);
//		c=getNo(cm_y,str);
		//System.out.println("a= "+a+ "  name "+str+"   c= "+c);

		while (true)
		{
			a=getRandomInt();
			len=getRandomInt(6);
			str=getCityName(cm_x,a);
			c=getNo(cm_y,str);
			d_x=getvalue(cm_x,a,len);
			d_y=getvalue(cm_y,c,len);
			if (d_x>d_y)
			{
				
			//generate a new and put into cm_x
				generateNew(cm_y,a,cm_x,c,len);
				break;
			}
		}
		while (true)
		{
			a=getRandomInt();
			len=getRandomInt(6);
			str=getCityName(cm_y,a);
			c=getNo(cm_x,str);
			d_x=getvalue(cm_y,a,len);
			d_y=getvalue(cm_x,c,len);
			if (d_y>d_x)
			{
				
			//generate a new and put into cm_x
				generateNew(cm_x,a,cm_y,c,len);
				break;
			}
		}
		


		//add to clan
		cm_new[p]=cm_x;
		cm_new[p+1]=cm_y;
		//test:
		//System.out.println("cm_new["+p+"]"+getvalue(cm_new[p]));
		//System.out.println("cm_new["+(p+1)+"]"+getvalue(cm_new[p+1]));
	}
	/**
	*
	*/
	private static void mutationChromosome(CityMap[][] cm_select,CityMap[][] cm_new,int p)
	{
		//
		CityMap[] cm_=new CityMap[GENE_NUMBER];
		construct(cm_);
		int r=getSelectRandomInt();
		cm_=copy(cm_select[r]);
		int m,n;
		m=getRandomInt();
		n=getRandomInt();
		while(m==n)
		{
			n=getRandomInt();
			m=getRandomInt();
		}
		//
		//inverseCityMap(cm_,m,n);
		swap(cm_,m,n);

		cm_new[p]=cm_;	

	}
	/*********************crossover & mutation end***************************/
	/**
	*method:getAncestorTribe(citymap);
	*param: CityMap[]
	*return: CityMap[][]
	*description: generate the originality tribe based on a citymap by certain way
	*/
	private static CityMap[][] getAncestorTribe(CityMap[] cm)
	{
		//System.out.println("____________123");
		CityMap[][] originality=new CityMap[TRIBE][GENE_NUMBER];
		constructCityMap(originality,TRIBE,GENE_NUMBER);
		for (int i=0;i<TRIBE;i++ )
		{
			originality[i]=getRoute(cm);
		}
		return originality;
	}

	private static double getMini(CityMap [][] clan)
	{
		double mini=getvalue(clan[0]);
		double temp;
		for (int i=1;i<clan.length;i++)
		{	
			temp=getvalue(clan[i]);
			if (temp<mini)
			{
				mini=temp;
			} 
		}
		return mini;
	}
	private static CityMap[] getMiniCityMap(CityMap [][] clan)
	{
		CityMap[] mini_cm=new CityMap[GENE_NUMBER];
		construct(mini_cm);
		double mini=getvalue(clan[0]);
		double temp;
		int r_mini=0;
		for (int i=1;i<clan.length;i++)
		{
			temp=getvalue(clan[i]);
			if (temp<mini)
			{
				mini=temp;
				r_mini=i;
			} 
		}
		mini_cm=copy(clan[r_mini]);
		return mini_cm;
	}
	/**
	*
	*/
	private static void inverseCityMap(CityMap[] cm_,int m,int n)
	{
		CityMap cm_temp=new CityMap();
		int a=m<n?m:n;
		int b=m>n?m:n;
		for (int i=0;i<(b-a)/2;i++ )
		{
			cm_temp=cm_[a+i];
			cm_[a+i]=cm_[b-i];
			cm_[b-i]=cm_temp;
		}
	}
	private static int getNo(CityMap[] cm,String str)
	{
		//
		for (int i=0;i<GENE_NUMBER;i++)
		{
			if (cm[i].getcity().equals(str))
			{
				return i;
			}
			
		}
		showMap(cm);
		return -1;

	}
	private static String getCityName(CityMap[] cm,int n)
	{
		//

		if (0<=n && n<GENE_NUMBER)
		{
			return cm[n].getcity();
		}
		else
		{
			throw(new IllegalArgumentException("IllegalArgumentException! n= "+n)); 
		}

	}
	/**
	generateNew(cm_x,a,cm_y,c,len);
	*/
	private static void generateNew(CityMap[] cm_x,int a,CityMap[] cm_y,int c,int len)
	{
		String str=cm_y[c].getcity();
		//showMap(cm_x);
		for (int i=0;i<len-1 ;i++ )
		{
			for (int n=0;n<GENE_NUMBER;n++)
			{
				if (cm_x[n].getcity().equals(cm_y[c+i+1].getcity()))
				{
					
					fit(cm_x,n);					

				}
			}

		}
		//showMap(cm_x);
		
		//
		int f=getNo(cm_x,str);
		//System.out.print("f=  "+f);
		cmcopy(cm_x,f,GENE_NUMBER-f-len+1,cm_x,f+len-1);
		//showMap(cm_x);
		
		
		cmcopy(cm_y,c,len,cm_x,f);
		//showMap(cm_x);
		//System.exit(1);
		
		

	}
	/**
	
	*/
	private static void fit(CityMap[] cm_x,int n)
	{
		for (int i=n;i<GENE_NUMBER;i++ )
		{
			cm_x[i%GENE_NUMBER]=cm_x[(i+1)%GENE_NUMBER];
			
		}
	}


	/*******************测试用函数***************************/
	private static void showClan(CityMap[][] cl)
	{
		int m=cl.length;
		//System.out.println("dd"+m);
		for (int x=0;x<m;x++ )
		{
			System.out.print("the value of clan "+(x)+"  is:\t"+getvalue(cl[x])+"\n");
		}
	
	}
	/**
	*method: get time
	*param:
	*return: void
	*/
	private static void getTime()
	{
		Date date = new Date(System.currentTimeMillis());
		String strdat="";
		strdat = date.toLocaleString();
		System.out.println("系统时间:"+strdat);

	}
	

	/*******************end测试用函数end*************************/




};/*****************************class ga_tsa_over***********************/