mainrun.java

改进单亲遗传算法在TSP中的应用源码

import java.util.*;

class MainRun {
	public int  maxrun=500;
	public int  maxgen=500;
	final int POPSIZE=10;
	final double hwp=0.1;//换位概率  
	final double ywp=0.4;//移位概率
	final double dwp=0.5;//倒位概率
	public final int CITYSIZE=20;
    double[][] distance = new double[CITYSIZE][CITYSIZE];//城市中2点之间距离
	
	
	
	
	private class rst//单个染色体的表示 也是一条城市序列的表示 
	 {
	  int city[] = new int[CITYSIZE];		//单个基因的城市序列
	  double fitness;	//该基因的适应度
	  int tempnum[] = new int[CITYSIZE];
	 }
  
	
    rst[] citys = new rst[POPSIZE];
   
   
	
	private void initdistance()//初始化城市间距离
    {			
		double[] cityx=new double[]{5.294,4.286,4.719,4.185,0.915,4.771,1.524,3.447,3.718,2.649,4.399,4.660,1.232,5.036,2.710,1.072,5.855,0.194,1.762,2.682};
		double[] cityy=new double[]{1.588,3.622,2.744,2.230,3.821,6.041,2.871,2.111,3.665,2.556,1.194,2.949,6.440,0.244,3.140,3.454,6.203,1.862,2.693,6.097};
		for (int i = 0; i < CITYSIZE; i++)
		{
			for (int j = 0; j < CITYSIZE; j++)
			{
				    // distance[i][j] = Math.abs(i-j);
					distance[i][j] = Math.sqrt((cityx[i]-cityx[j])*(cityx[i]-cityx[j])+(cityy[i]-cityy[j])*(cityy[i]-cityy[j]));
					System.out.println(+i+"  "+j+"  "+distance[i][j]);
			}
			//System.out.println();
		}
    }

	
	private void calfitness() // 计算所有城市序列的适应度 以一个城市序列的各段距离和表示 
	   {
		int j;
		for (int i = 0; i < POPSIZE; i++) 
		  {
			for (j = 0; j <CITYSIZE-1 ;j++)
				citys[i].fitness  =  citys[i].fitness + distance[citys[i].city[j]] [citys[i].city[j+1]]; 
				citys[i].fitness  =  citys[i].fitness + distance[citys[i].city[0]] [citys[i].city[CITYSIZE - 1]];
			     System.out.println("测试用"+j);
		  }
	   }
	
	
	public MainRun()											//初始化种群第一代 构造方法
    {
    	for(int i=0;i<POPSIZE;i++)
    		{		
    				citys[i]=new rst();
    				int[] num = new int[CITYSIZE];
    			for(int t=0;t<CITYSIZE;t++)
    					{
    						num[t]=t;
    					}
    				int temp=CITYSIZE;		            //  临时变量，影响CITYSIZE
    			for(int j=0;j<CITYSIZE;j++)
    				{
    					  int r=(int)(Math.random()*temp);//随机产生0-19的数字
    						citys[i].city[j]=num[r];
    						num[r] = num[temp - 1];
								temp--;
    				}
    			citys[i].fitness=0;
    			
    		}
    	initdistance();
    	
    	//System.out.println("算法执行时间//////////");
    }
	
	
	 // 计算种群中每个染色体（城市序列）个体的适应度，选择概率，期望概率，和是否被选择。
 	public void calall() 
 	{
			for( int i = 0; i< POPSIZE; i++)
			{
				citys[i].fitness = 0;
			}
			
			calfitness();
				
  }
	
 	
 	public void hw()//基因换位基因换位基因换位基因换位基因换位基因换位基因换位
 	{
			float random;
			int temp;
			int temp1;
			int temp2;
			for( int i = 0 ; i< POPSIZE; i++)
			{
				random = (float)Math.random();
				if(random<=hwp)
				{
					temp1 = (int)(Math.random() * (CITYSIZE));
					temp2 = (int)(Math.random() * (CITYSIZE));
					temp = citys[i].city[temp1];
					citys[i].city[temp1] = citys[i].city[temp2];
					citys[i].city[temp2] = temp;
				}
			}	
			
			System.out.println("测试用测试用测试用测试用测试用测试用测试用测试用测试用测试用测试用测试用测试用测试用");
  }
 	
 	
 	public void yw(){
 		int t1;
		int t2;
		int temp=CITYSIZE;
		//int []tempnum = new int [CITYSIZE];//记录基因移位的临时数组
		
		do{
			t1=(int)(Math.random()*temp);//产生两个0-19之间的不同的整数
			t2=(int)(Math.random()*temp);
			/*if(t1>t2)
			 {
			 		t1=temp;
			 		temp=t2;
			 		t2=t1;
			 }*/
			}while((t2-t1)<2);
		
		for( int i = 0 ; i< POPSIZE; i++){
	 		for(int j=0;j<temp;j++){
	 			if(j==t1) citys[i].tempnum[j]=citys[i].city[t2];
	 			else if (j>t1 && j<=t2) citys[i].tempnum[j]=citys[i].city[j-1];
	 			else citys[i].tempnum[j]=citys[i].city[j];
	 		}
		}
		//System.out.println("测试用");
 	}
 	

 	public void dw(){
 		int t1;
		int t2;
		int temp=CITYSIZE;
		//int []tempnum = new int [CITYSIZE];//记录基因倒位的临时数组 基因倒位 基因倒位 基因倒位 基因倒位
		
		do{
			t1=(int)(Math.random()*temp);//产生两个0-19之间的  不同 相差3  的整数
			t2=(int)(Math.random()*temp);
			/*if(t1>t2)
			 {
			 		t1=temp;
			 		temp=t2;
			 		t2=t1;
			 }*/
			}while((t2-t1)<3);
		
 		int t12=t1+t2;
 		for(int j=0;j<POPSIZE;j++){
	 		for(int i=0;i<temp;i++){
	 			if (i>=t1 && i<=t12/2){
	 				citys[j].tempnum[i]=temp;
	 				temp=citys[j].city[t12-i];
	 				citys[j].city[t12-i]=citys[j].tempnum[i];
	 				}
	 		}
 	
 		}
 	}
 	
	public void run()  //运行程序
	{
	//double[] result = new double[maxrun];
	//result初始化为所有的数字都不相等
	//for( int i  = 0; i< maxrun; i++)
	//	result[i] = i;
	//int index = 0;		//数组中的位置
	int num = 1;		//第num代
	double temp = 100;
	while(maxgen>0)
	{
			System.out.println("-----------------  第  "+num+" 代  --------------------");
			calall();
			//print();
			hw();              //此处卡住了卡住了卡住了卡住了卡住了卡住了卡住了卡住了
			//System.out.println("测试用用用用用用用用用");
			yw();
			dw();
			maxgen--;
			
			//double temp = citys[0].fitness;
				for ( int i = 1; i< POPSIZE; i++){
					if(citys[i].fitness<temp)
					{
						temp = citys[i].fitness;
					}
				}
				
			System.out.println("最优的解："+temp);
			num++;
			//result[index] = temp;
				/*if(issame(result))
					break;
				  index++;
				if(index==maxrun)
					index = 0;
				num++;*/
	}
	//printbestroute();
}
	
	
	/*private boolean issame(double[] x)//return x数组的值是否全部相等，相等则表示x.length代的最优结果相同，则算法结束
	{
			for( int i = 0; i< x.length -1; i++)
				if(x[i]!=x[i+1])
					return false;
			return true;
	}*/
	
	
	public void caltime(Calendar a,Calendar b)//计算开始时间与结束时间
	{
		long x = b.getTimeInMillis() - a.getTimeInMillis();
		long y = x/1000;
		x = x - 1000*y;
		System.out.println("算法执行时间："+y+"."+x+" 秒");
	}
	
	
	
	public static void main(String[] args){
		/*try{
			
		}
		catch(Exception e){
			e.printStackTrace();
		}*/
		Calendar a = Calendar.getInstance();	//开始时间
		MainRun tsp = new MainRun();
		System.out.println("算法执行时间");
		tsp.run();
		Calendar b = Calendar.getInstance();	//结束时间
		tsp.caltime(a, b);
	}

}