being.java

产生式系统中旅行商问题的求解

public class Being
{Vector g=new Vector(4);
 PointPlus[] point={new PointPlus(10,13),new PointPlus(12,12),new PointPlus(12,6),
					new PointPlus(10,5),new PointPlus(5,5),new PointPlus(11,10)};
 PointPlus beginPoint=new PointPlus(5,10);
 int n;

 public Being(PointPlus[] points)
 {n=points.length-1;
  this.point=new PointPlus[n];
  for(int i=0;i<point.length;i++)point[i]=points[i+1];
  beginPoint=points[0];
  
	 
  int[] a=new int[n];
  int[] b=new int[n];
  int[] c=new int[n];
  int[] d=new int[n];
  for(int i=0;i<n;i++)a[i]=b[i]=c[i]=d[i]=i;
  //int[] c={2,0,3,4,5,1};
  //int[] d={1,5,4,3,0,2};
  g.setElement(a,0);
  g.setElement(b,1);
  g.setElement(c,2);
  g.setElement(d,3);
 }
 
 
 public void pirnt()
 {for(int i=0;i<4;i++)
  {for(int j=0;j<n;j++)
   {System.out.print(((int[])g.elementAt(i))[j]+" ");}
   System.out.println();}
}
 
 public double sum()
 {double sum=0;
  for(int i=0;i<4;i++) sum+=f(i);
  return sum;
 }
 
 public double f(int i)
 {double f=PointPlus.distance(beginPoint,point[((int[])g.elementAt(i))[0]]);
  for(int j=0;j<n-1;j++){f+=PointPlus.distance(point[((int[])g.elementAt(i))[j]],point[((int[])g.elementAt(i))[j+1]]);}
         f+=PointPlus.distance(point[((int[])g.elementAt(i))[5]],beginPoint);
  return f;
 }
 
 public Object bestIndividual()
 {double best=99999999;int bestIndex=0;
  for(int i=0;i<4;i++){if (best>=f(i)) {best=f(i);bestIndex=i;}}
  return this.g.elementAt(bestIndex);
 }
 
 public double bestIndividualValue()
 {double best=99999999;int bestIndex=0;
  for(int i=0;i<4;i++){if (best>=f(i)) {best=f(i);bestIndex=i;}}
  return f(bestIndex);
 }
 
 public String bestIndividualString()
 {double best=99999999;int bestIndex=0;
  for(int i=0;i<4;i++){if (best>=f(i)) {best=f(i);bestIndex=i;}}
  StringBuffer s=new StringBuffer();
  for(int i=0;i<point.length;i++){s.append( ((int[])g.elementAt(bestIndex))[i]);}
  return s.toString();
 }
 
  public Being NaturalChoose(PointPlus[] points)
 {
  Vector newG=new Vector(4);
  java.util.Random generator=new java.util.Random();
  double[] midSum={0,0,0,0};
	  for(int i=0;i<4;i++)
		  for (int j=i;j<4;j++)
			  midSum[j]+=100/f(i);
  
  //for (int i=0;i<4;i++)System.out.print(midSum[i]+" ");
  //System.out.println();
  for (int i=0;i<4;i++)
  {double random=(Math.abs(generator.nextDouble())*400)%(100/f(0)+100/f(1)+100/f(2)+100/f(3));
   //System.out.println(random);
   int j;
   for (j=0;j<4;j++){if (midSum[j]>=random) break;}
   newG.addElement(g.elementAt(j));}
   Being other=new Being(points);
   other.g=newG;
   return other;
 }
  
   public Being Exchange(PointPlus[] points)
 {
	 Vector newG=new Vector(4);
	 java.util.Random generator=new java.util.Random((new java.util.Random()).nextLong());
	 boolean[] flag={true,true,true,true};
	 int[] random=new int[4];
	 
	 for (int i=0;i<4;i++)
	 {
	 while (!flag[random[i]])
	 {random[i]=Math.abs(generator.nextInt())%4;}
	 flag[random[i]]=false;}
	 //for(int i=0;i<4;i++)System.out.print(random[i]);System.out.println();
	 int[] a=((int[])g.elementAt(random[0]));
	 int[] b=((int[])g.elementAt(random[1]));
	 ExchangePathIfPossible(a,b);
	 //int changePlace=(Math.abs(generator.nextInt())%5);
	 ////System.out.println(changePlace);
	 //for (int i=changePlace;i>=0;i--)
	 //{int temp=a[i];a[i]=b[i];b[i]=temp;}
	 
	 int[] c=((int[])g.elementAt(random[2]));
	 int[] d=((int[])g.elementAt(random[3]));
	 ExchangePathIfPossible(c,d);
	 //changePlace=(Math.abs(generator.nextInt())%5);
	 ////System.out.println(changePlace);
	 //for (int i=changePlace;i>=0;i--)
	 //{int temp=c[i];c[i]=d[i];d[i]=temp;}
	 ////for (int i=0;i<4;i++)System.out.println(random[i]+" ");
	 
	 newG.addElement(a);
	 newG.addElement(b);
	 newG.addElement(c);
	 newG.addElement(d);
         
	 Being other=new Being(points);
	 other.g=newG;
	 return other;
 }
 
public  boolean ExchangePathIfPossible(int[] a,int[] b)
{//System.out.println("Begin");
	int begin=0,end=this.n-2;boolean changed=false;
  for(begin=0;begin<this.n-1;++begin)
  { end=this.n-2;Vector container1=new Vector();Vector container2=new Vector();
	for(int i=begin;i<=end;i++)
	{container1.addElement(new Integer(a[i]));container2.addElement(new Integer(b[i]));}
    while (begin<end)
	{if(container1.equalVector(container2))
	 {//for(int i=begin;i<=end;i++)System.out.print(container1.elementAt(i-begin));System.out.println();
	  //for(int i=begin;i<=end;i++)System.out.print(container2.elementAt(i-begin));System.out.println();
	  //System.out.println("Begin="+begin+" End="+end);
	  break;}
	 else {
		   container1.removeElement(new Integer(a[end]));
		   container2.removeElement(new Integer(b[end]));
		   end--;} 
	}

  if(container1.equalVector(container2))
  {   //System.out.println("Begin="+begin+" End="+end);
	  for(int i=begin;i<=end;i++){int temp=a[i];a[i]=b[i];b[i]=temp;}changed=true;
  }
	   
	
   }
  //System.out.println("End");
  return changed;
}

 public Being Evalution(PointPlus[] points)
 {    
	 Vector newG=new Vector(4);
	 java.util.Random generator=new java.util.Random((new java.util.Random()).nextLong());

	 for(int i=0;i<4;i++)
	 {   int[] a=new int[n];
		 System.arraycopy(g.elementAt(i),0,a,0,n);
		 for (int j=0;j<n;j++)
		 {
		  int random=Math.abs(generator.nextInt())%6;
		  int randomIndex=Math.abs(generator.nextInt())%6;
		  //System.out.print(random+" ");
		  if(random==0) {int temp=a[j];a[j]=a[randomIndex];a[randomIndex]=temp;}
		 }
		 newG.addElement(a);}//System.out.println();
	 
	Being other=new Being(points);
	 other.g=newG;
		 return other;
 }

    public double  fmin()
	{double fmin=999999;
	 for(int i=0;i<4;i++){if (fmin>=f(i)) fmin=f(i);}
	 return fmin;
	}

  public void printOneLine(int i)
 {for(int j=0;j<=n-1;j++)
  System.out.print(((int[])g.elementAt(i))[j]+" ");System.out.print("   ");
 }

   public void print()
{for(int i=0;i<4;i++)
  {printOneLine(i);
   System.out.println();}
}

	
}