ant.java

一个非常好的

/* Applet to solve the Traveling Salesman Problem
 * Copyright (C) 2002 Tobias Oetzel ([e-mail])
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published by the 
 * Free Software Foundation; either version 2 of the License, or (at your option)
 * any later version. This program is distributed in the hope that it will be 
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 
 * You should have received a copy of the GNU General Public License along with this program;
 * if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 
 * Boston, MA 02111-1307, USA. 
*/



// Ant Colony Optimization
import java.util.*;
import java.awt.event.*;
import java.text.*;
import java.awt.*;

class aant
{
                
  public Vector // Tabulist for already visited cities
                TabuList,
                // Cities which are allowed to visit
                AllowedCities;
  public double LastTourLength;              
  
  public aant()
  {
    TabuList      = new Vector();
    AllowedCities = new Vector();
    LastTourLength=0;
  }
  
  public int GetLastCity()
  {
    int LastElement = TabuList.size()-1;
    return ((Integer)TabuList.elementAt(LastElement)).intValue();
  }  
    
}  

class edges
{
  protected double     InitialTrailIntensity = 0.1;
  protected int        HowMany               = 0;
  protected double[][] TrailIntensity, 
                       TrailSubstance,
                       CityDistance;
  private ant          AntInstance;
  protected  double    MaximumTrail,
                       MinimumTrail;
  
  public edges(int count, ant MyInstance)
  {
    AntInstance=MyInstance;
    HowMany=count;
    MaximumTrail=InitialTrailIntensity;
    MinimumTrail=InitialTrailIntensity;
    TrailIntensity = new double  [HowMany][HowMany];
    TrailSubstance = new double  [HowMany][HowMany];
    CityDistance   = new double  [HowMany][HowMany];   
  }  
  
  public void InitEdges()
  {
    for (int i=0;i<HowMany;i++)
    {
      for (int j=0;j<HowMany;j++)
      {
        if (j!=i)
        {
          TrailIntensity[i][j]=InitialTrailIntensity;
          TrailSubstance[i][j]=0;
          CityDistance[i][j]  =AntInstance.TspInstance.MyCities.GetDistanceCity(AntInstance.GetCityAt(i),AntInstance.GetCityAt(j));
        }
        else
        {
          TrailIntensity[i][j]=-1;
          TrailSubstance[i][j]=0;
          CityDistance[i][j]  =0;
        }  
      }  
    }
  }  
  
  public void SetTrailIntensity(int i, int j,double d)
  {
    TrailIntensity[i][j]=d;
    if (d>MaximumTrail) 
    {
      MaximumTrail=d;
    }
    if (d<MinimumTrail) 
    {
      MinimumTrail=d;
    }
      
  }  
  
  public void SetTrailSubstance(int i, int j,double d)
  {
    TrailSubstance[i][j]=d;
  }  

   public void EchoEdgesTrailIntensity()
   {
     System.out.print("TrailIntensity");
     for(int i=0;i<HowMany;i++)
     {
       System.out.println("");
       for(int j=0;j<HowMany;j++)
       {
         System.out.print(TrailIntensity[i][j]+" ");
       } 
     } 
     System.out.println("");
     System.out.println("");
   }  
  
   public void EchoEdgesTrailSubstance()
   {
     System.out.print("TrailSubstance");
     for(int i=0;i<HowMany;i++)
     {
       System.out.println("");
       for(int j=0;j<HowMany;j++)
       {
         System.out.print(TrailSubstance[i][j]+" ");
       } 
     } 
     System.out.println("");
     System.out.println("");
   }  

   public void EchoEdgesCityDistance()
   {
     System.out.print("CityDistance");
     for(int i=0;i<HowMany;i++)
     {
       System.out.println("");
       for(int j=0;j<HowMany;j++)
       {
         System.out.print(CityDistance[i][j]+" ");
       } 
     } 
     System.out.println("");
     System.out.println("");
   }  
  

}

public class ant extends Thread
{
  
  private int     ActStep               = 0, 
                  MaxSteps              = 0,
                  HowMany               = 0,
                  DelayTime             = 0;

  private double  ImpTrail              = 0,
                  ImpVisibility         = 0,
                  TrailPersistence      = 0,
                  TrailQuantity         = 0,
                  StartConfigDistance   = 0,
                  BestConfigDistance    = 0;

  private Vector  StartConfig,
                  BestConfig,
                  MyAnts;
  
  private edges   MyEdges;
  
  private boolean BestSolutions         = true,
                  StopThread            = false,
                  Finish                = false;
  protected tsp   TspInstance;                  
  private Vector MyCities;


  public ant(tsp MyInstance)
  {
    TspInstance=MyInstance;
  }  
 
  private void MakeDelay (int i) 
  {
    try 
    {
      Thread.sleep(i);
    }
    catch (InterruptedException e) { }
  }

  public void SetRandomConfiguration(Vector Config)
  {
    StartConfig = new Vector(Config);
    StartConfigDistance = TspInstance.MyCities.GetConfigurationDistance(StartConfig);
  }
  

  public void SetImpTrail(String S)
  {
    ImpTrail=Double.parseDouble(S);
  }
  
  public void SetImpVisibility(String S)
  {
    ImpVisibility=Double.parseDouble(S);
  }

  public void SetTrailPersistence(String S)
  {
    TrailPersistence=Double.parseDouble(S);
  }

  public void SetTrailQuantity(String S)
  {
    TrailQuantity=Double.parseDouble(S);
  }

  public void SetDelayTime(int S)
  {
    DelayTime=S;
  }  
  
  public void SetBestSolutions(boolean S)
  {
    BestSolutions=S;
  }  
  
  public void SetMyCities(Vector K)
  {
    MyCities=K;
  }  

  public void SetMaxCycles(String S)
  {
    MaxSteps=Integer.parseInt(S);
  }


  public void SetStopFlag()
  {
    StopThread=true;
    Finish=true;
  }  
  
  public boolean IsRunning()
  {
    if (!StopThread)
    {
      return true;
    }
    else
    {
      return false;
    }
  }    
      
  private void SetStartConfigDistance()
  {
    DecimalFormat df = new DecimalFormat("####00.000");
    String S = df.format(StartConfigDistance);
    TspInstance.SetOrgDistanceValue(S);
  }  

  private void SetBestConfigDistance()
  {
    DecimalFormat df = new DecimalFormat("####00.000");
    String S = df.format(BestConfigDistance);
    TspInstance.SetNowDistanceValue(S);
  }  
            
  private void SetPerConfigDistance()
  {
    double BestPercentValue=100-((100/StartConfigDistance)*BestConfigDistance);
    DecimalFormat df = new DecimalFormat("####00.00");
    String S = df.format(BestPercentValue);
    TspInstance.SetPerDistanceValue(S+"%");
  }  

  private void SetStepCount(int count)
  {
    TspInstance.SetStepCountValue(Integer.toString(count));
  }  
  
  public city GetCityAt(int i)
  {
    return ((city)MyCities.elementAt(i));
  }  

  public void InitialAntsPos()
  {

    Vector TempCities,
           TempCities2;
    
    TempCities=new Vector();  
    for (int j=0;j<MyCities.size();j++)
    {
      TempCities.add(new Integer(j));
    }  

    // Generate Random Start Positions for Ants
    int tempmany;
    tempmany=TempCities.size();
    int i=0;
    while (tempmany>0)
    { 
      int index;
      index=(int)(java.lang.Math.random()*tempmany);

      // start city
      //  All cities allowed but the start city
      TempCities2=new Vector();

      for (int j=0;j<MyCities.size();j++)
      {
        TempCities2.add(new Integer(j));
      }  
      int realindex=((Integer)TempCities.elementAt(index)).intValue();
      TempCities2.removeElementAt(realindex);
      ((aant)MyAnts.elementAt(i)).AllowedCities = new Vector(TempCities2);
      ((aant)MyAnts.elementAt(i)).TabuList = new Vector();
      ((aant)MyAnts.elementAt(i)).TabuList.add(new Integer(realindex));
      
      TempCities.removeElementAt(index);
      tempmany=TempCities.size();
      i++;
    }  
  }

  public void Repaint()
  {
    if (ActStep>0)
    {
      if (!BestSolutions)
      { 
         TspInstance.MyDraw.DrawAnts(MyEdges.TrailIntensity,MyEdges.MaximumTrail,MyEdges.MinimumTrail); 
      }
      else
      { 
        TspInstance.MyDraw.DrawConfiguration(BestConfig); 
      }  
    }  
  }  

 
  private int CheckProbs(Vector p) 
  {
    double d=Math.random();
    double sum=0;
    for (int i=0;i<p.size();i++) 
    { 
      if (!Double.isNaN(((Double)p.elementAt(i)).doubleValue()))
      { 
        sum += ((Double)p.elementAt(i)).doubleValue();
      } 
      else
      {
        return 0;
      }  
      if (d<sum) 
      {
        return i;
      }
    } 
    return -1;
  }

  
  private void GetNextCity(int k)
  {
     
     Vector prob = new Vector();
     int ResultIndex = -1;
     int LastCity;
     LastCity=((aant)MyAnts.elementAt(k)).GetLastCity();
      
      // calculate probabilities
      
     double bottom1      =0;     
     double bottom2      =0;     
     double bottom       =0;
     
     for (int i=0;i<((aant)MyAnts.elementAt(k)).AllowedCities.size();i++)
     {
      int realindex=((Integer)((aant)MyAnts.elementAt(k)).AllowedCities.elementAt(i)).intValue();
//     System.out.println("["+LastCity+"]["+realindex+"]  "+MyEdges.TrailIntensity[LastCity][realindex]);
      
      bottom1=Math.pow(MyEdges.TrailIntensity[LastCity][realindex],ImpTrail);
      bottom2=Math.pow((1/MyEdges.CityDistance[LastCity][realindex]),ImpVisibility);
      bottom+=(bottom1*bottom2);
     }

     for (int i=0;i<((aant)MyAnts.elementAt(k)).AllowedCities.size();i++)
     {
       double above      =0;
       double above1     =0;
       double above2     =0;
       double value      =0;
 
       int realindex=((Integer)((aant)MyAnts.elementAt(k)).AllowedCities.elementAt(i)).intValue();
       above1=Math.pow(MyEdges.TrailIntensity[LastCity][realindex],ImpTrail);
       above2=Math.pow((1/MyEdges.CityDistance[LastCity][realindex]),ImpVisibility);
       above=above1*above2;

       value=above/bottom;
//       System.out.println("["+LastCity+"]["+realindex+"]  "+value);
       prob.add(new Double(value));

     } 

/*
     double test=0;
     for (int i=0;i<prob.size();i++)
     {
       test+=((Double)prob.elementAt(i)).doubleValue();
     }
     System.out.println("Result: "+test);
*/
     
     while (ResultIndex==-1)
     {
       ResultIndex=CheckProbs(prob);
     }  
//     System.out.println("Choose City: "+ResultIndex);

     
     int realindex=((Integer)((aant)MyAnts.elementAt(k)).AllowedCities.elementAt(ResultIndex)).intValue();
     ((aant)MyAnts.elementAt(k)).AllowedCities.removeElementAt(ResultIndex);
     ((aant)MyAnts.elementAt(k)).TabuList.add(new Integer(realindex));
  }  
  
  public void run()
  {
    
    StopThread=false;

    // Initialisation - Step 1
    HowMany=MyCities.size();
    ActStep=0;

    BestConfig=new Vector(StartConfig);
    BestConfigDistance=StartConfigDistance;

    SetStartConfigDistance();
    SetBestConfigDistance();
    SetPerConfigDistance();

    MyEdges = new edges(HowMany,this);
    MyEdges.InitEdges();
    MyAnts = new Vector();
    
    for (int i=0;i<HowMany;i++)
    {
      MyAnts.add(new aant());
    }  
    
    TspInstance.MyDraw.DrawAllCities();
   
    Finish=false;

    while (!StopThread)
    {
      // random placing of one ant per city
      InitialAntsPos();
   
      while (!Finish)
      {

        if (!BestSolutions)
        { 
          TspInstance.MyDraw.DrawAnts(MyEdges.TrailIntensity,MyEdges.MaximumTrail,MyEdges.MinimumTrail); 
        }
        else
        { 
          TspInstance.MyDraw.DrawConfiguration(BestConfig); 
        }  
 
        // Find complete tour for each ant
        // city iteration ( citycount-1 --> StartCity already given )
        for (int i=0;i<MyCities.size()-1 && !Finish;i++)
        {
          // each ant wanna have a new city
          for (int j=0;j<MyAnts.size() && !Finish;j++)
          {
            GetNextCity(j);
          }  
        }  

        // Tour Complete - checking distance
	if( !Finish ){
	  for (int k=0;k<MyAnts.size();k++)
	  {
	    ((aant)MyAnts.elementAt(k)).LastTourLength=TspInstance.MyCities.GetConfigurationDistance(((aant)MyAnts.elementAt(k)).TabuList);
	   
	    if (((aant)MyAnts.elementAt(k)).LastTourLength<BestConfigDistance)
	    {
	      BestConfigDistance=((aant)MyAnts.elementAt(k)).LastTourLength;
	      BestConfig=new Vector(((aant)MyAnts.elementAt(k)).TabuList);
	      SetBestConfigDistance();
	      SetPerConfigDistance();
	    }  
	  }
	}

        // Update Trails
        for (int i=0;i<MyAnts.size() && !Finish;i++)
        {
          // go through ant tour and update trail
          for (int j=0;j<((aant)MyAnts.elementAt(i)).TabuList.size()-1;j++)
          {
            int a=((Integer)((aant)MyAnts.elementAt(i)).TabuList.elementAt(j)).intValue();
            int b=((Integer)((aant)MyAnts.elementAt(i)).TabuList.elementAt(j+1)).intValue();
            double TempSubstance=MyEdges.TrailSubstance[a][b];
            TempSubstance+=(TrailQuantity/(((aant)MyAnts.elementAt(i)).LastTourLength));
            MyEdges.SetTrailSubstance(a,b,TempSubstance);
          }  
        }
        
        // finally update edges
        for (int i=0;i<MyEdges.HowMany && !Finish;i++)
        {
          for (int j=0;j<MyEdges.HowMany && !Finish;j++)
          {
            if (i!=j)
            {
              MyEdges.SetTrailIntensity(i,j,(TrailPersistence*MyEdges.TrailIntensity[i][j])+MyEdges.TrailSubstance[i][j]);
              MyEdges.SetTrailSubstance(i,j,0);
            }  
          } 
        }  
       
        for (int i=0;i<MyAnts.size() && !Finish;i++)
        {
          int tempstartcity=((Integer)((aant)MyAnts.elementAt(i)).TabuList.elementAt(0)).intValue();
          ((aant)MyAnts.elementAt(i)).TabuList.clear();
          ((aant)MyAnts.elementAt(i)).TabuList.add(new Integer(tempstartcity));
          ((aant)MyAnts.elementAt(i)).AllowedCities = new Vector();
          
          for (int j=0;j<MyCities.size();j++)
          {
            ((aant)MyAnts.elementAt(i)).AllowedCities.add(new Integer(j));
          }  
         
          ((aant)MyAnts.elementAt(i)).AllowedCities.removeElementAt(tempstartcity);
        }  
        
        ActStep++;
        SetStepCount(ActStep);
      
        if (ActStep==MaxSteps)
        {
          Finish=true;
          SetStopFlag();
        }   

        MakeDelay(DelayTime);
      }  
    }  
    TspInstance.MakeReady();
    TspInstance.MyCities.SetStartSolution(BestConfig,true);
    
  }
  




}