tsp_g.java

TSP问题的源代码及城市信息

import java.awt.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
import javax.swing.*;
import java.util.Random;

/*
 * Created on 2004-10-8
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */

/**
 * @author Bluewater
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
class TSP_g {

	 double[][] city;
	 int[][] oldparent1={},newparent;
	 int[] bestsequence;
	 int gen,maxgen,citynum,popsize;
	 double pmutation,pcross,pselect;
	 double[] pfitness,poldfitness;
	 public TSP_g()
	 {
	   this.citynum=20;
	   this.popsize=100;
	   bestsequence=new int[citynum];
	   this.pmutation=0.35;
	   this.pcross=1.0;
	   this.pselect=0.2;
	   this.gen=0;
	   this.city=new double[20][2];
	   oldparent1=new int[popsize][citynum];
	   newparent=new int[popsize][citynum];
	   initial(this.citynum);
	   poldfitness=calculate_fitness(oldparent1,this.popsize);
	   while(gen<5)
	   {
	   	for(int i=0;i<popsize;i+=2)
	   	{
	   		cross();
	   		gen++;
	   	}
	   	/*

	   	随机从P（t）中产生两个父体交叉操作后产生两个后代；

	   	把这两个后代加入中间群体P′（t）中；

	   	}

	   	对中间群体P′（t）中的每个个体进行变异操作；

	   	从P（t）和P′（t）中进行选择操作得到N个个体赋予新群体P（t+1）中；

	   	计算P（t+1）中每个个体的适应度；

	   	t++；*/
	   }
	 }


	 public void cross()
	 {
	 	Random rr=new Random();
   		double probablity=0.0;
   		int num1,num2,crossposition;
   		num1=0;num2=0;crossposition=0;
   		try
		{
   			probablity=rr.nextDouble();
   			num1=rr.nextInt(popsize-1);
   			num2=rr.nextInt(popsize-1);
   			crossposition=rr.nextInt(citynum-1);
		}
   		catch(IllegalArgumentException ex)
		{
   			ex.printStackTrace();
		}
   		for(int i=0;i<popsize;i++)
   			for(int j=0;j<citynum;j++)
   				newparent[i][j]=oldparent1[i][j];
   		//进行交叉操作
   		if(probablity<=pcross)
   		{
   			crossaction(newparent[num1],newparent[num2],crossposition);
   		}
   		System.out.println("交叉后");
   		calculate_fitness(newparent,popsize);
   		System.out.println("交叉wanbi");
	 }

	 public void crossaction(int[] first,int[] second,int position)
	 {
	 	int i,j;
	 	int[] temp1=new int[citynum];
	 	int[] temp2=new int[citynum];
	 	for(i=0;i<citynum;i++)
	 	{
	 		temp1[i]=first[i];
	 		temp2[i]=second[i];
	 	}
	 	changeorder(temp1,position);
	 	changeorder(temp2,position);
	 	for(i=0;i<position;i++)
	 		for(j=0;j<citynum;j++)
	 		{
	 			if(temp2[j]==first[i])
	 				temp2[j]=-1;
	 			if(temp1[j]==second[i])
	 				temp1[j]=-1;
	 		}
	 	int position_num=position;
	 	for(i=0;i<citynum;i++)
	 	{
	 		if(temp2[i]!=-1)
	 			{first[position_num]=temp2[i];
	 			 position_num++;
	 			}
	 		if(temp1[i]!=-1)
	 			{second[position]=temp1[i];
	 			 position++;
	 			}
	 	}
	 }

	 public void changeorder(int[] data,int position)
	 {
	 	int temp;
	 	for(int i=0;i<position;i++)
	 	{
	 		temp=data[1];
	 		for(int j=0;j<citynum-1;j++)
	 			data[j]=data[j+1];
	 		data[citynum-1]=temp;
	 	}
	 }

	 //从文本中读数据
	 public void readdata(int citynum) throws IOException
	 {
	 	String str_temp;

	 	try
		{
	 		RandomAccessFile file=new RandomAccessFile("g:\\javapro\\data.txt","r");
	 		for(int i=0;i<citynum;i++)
	 		{
	 			try
				{
	 				str_temp=file.readLine();
	 				this.city[i][0]=(Double.valueOf(str_temp)).doubleValue();
	 				str_temp=file.readLine();
	 				this.city[i][1]=(Double.valueOf(str_temp)).doubleValue();
	 			}
	 			catch(IOException ex)
				{
	 				ex.printStackTrace();
				}
	 			catch(ArrayIndexOutOfBoundsException ex)
				{
	 				ex.printStackTrace();
				}
	 		}

		}
	 	catch(FileNotFoundException ex)
		{
	 		ex.printStackTrace();
		}
	 }

	 public void initial(int citynum)
	 {
	 	int[] sequence=new int[citynum];
	 	int i,j,nextnum;
	 	try{
	 		readdata(citynum);
	 	}
	 	catch(IOException ex)
		{
			ex.printStackTrace();
		}
	 	Random rr=new Random();
	 	//产生第一代个体
	 	for(i=0;i<popsize;i++)
	 		for(j=0;j<citynum;j++)
	 		{
	 			oldparent1[i][j]=0;
	 		}
	   for(j=0;j<popsize;j++)
	   {
	     //初始化序列
	     for(i=0;i<citynum;i++)
	        sequence[i]=i;
	     int length=citynum-1;
	     //随机产生的序列
	     for(i=0;i<citynum;i++)
	     {
	     	try
			{
	       	nextnum=rr.nextInt(length+1);

	        oldparent1[j][i]=sequence[nextnum];

	        for(int k=nextnum;k<length;k++)
	        	sequence[k]=sequence[k+1];

	        length--;

			}
	     	catch(IllegalArgumentException ex)
			{
		       	ex.printStackTrace();
			}
	     }
	   }
	 }

	 public double[] calculate_fitness(int[][] parent,int size)
	 {
	   double[] cityfitness=new double[size];//记录种群的适应度值
	   double sum=0.0;
	   //计算适应度
	   for(int i=0;i<size;i++)
	     {
	   		for(int j=0;j<citynum-1;j++)
	   		{
	         sum+=distance(parent[i][j],parent[i][j+1]);
	   		}
	   		try{
	   			cityfitness[i]=1/sum;
System.out.print("第"+(i+1)+"个 : ");
for(int j=0;j<citynum;j++)
	System.out.print(parent[i][j]+",");
System.out.println("   "+cityfitness[i]);
	   		}
	   		catch(Exception ex)
			{
	   			ex.printStackTrace();
			}
	   		sum=0.0;
	     }
	   return cityfitness;
	 }


	 //x,y为城市的序号,此函数计算x，y之间的距离
	 public double distance(int x,int y)
	 {

	   double result=0.0;
	   result+=(city[x][0]-city[y][0])*(city[x][0]-city[y][0])+(city[x][1]-city[y][1])*(city[x][1]-city[y][1]);
	   return Math.sqrt(result);

	 }


public static void main(String args[]){
	TSP_g test1=new TSP_g();
}

}