simann.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. 
*/



// Simulated Annealing
import java.util.*;
import java.awt.event.*;
import java.text.*;

public class simann extends Thread
{
  private int     // actual step count
                  ActStep               = 0, 
                  // 0 = Transposition <->  1 = 2-opt
                  Neighbourhood         = 0,
                  // City count
                  HowMany               = 0,
                  // Inner loop no better config count
                  TimesNoBetterConfig   = 0,
                  // delay between steps
                  DelayTime             = 0,
                  // Break inner loop after x steps
                  InnerLoopBreak        = 0;
                  
  private double  // start temperature
                  InitTemperature       = 0,
                  // actual temperature
                  Temperature           = 0,
                  // cooling rate
                  CoolingRate           = 0,
                  // Distance of first random config
                  StartConfigDistance   = 0,
                  // Best distance while running
                  BestConfigDistance    = 0, 
                  // actual distance
                  ActConfigDistance     = 0,
                  // modified actual config distance
                  NewConfigDistance     = 0,
                  // (NewConfigDistance-ActConfigDistance)
                  ConfigDifference      = 0;

  private Vector  // Initial random config, remember just integer values
                  StartConfig,
                  // Best config so far                  
                  BestConfig,
                  // Act config to work with
                  ActConfig,
                  // modified Act config                  
                  NewConfig;
  
  private boolean NeedNewConfigDistance = true,
                  BestSolutions         = true,
                  StopThread            = false;
  private tsp     TspInstance;
                  
  public simann(tsp MyInstance)
  {
    TspInstance=MyInstance;
  }                    
                 

  public void SetNeighbourhoodType(String S)
  {
    if (S=="Transposition")
    {
      Neighbourhood=0;
    } 
    else if (S=="2-opt")
    {  
      Neighbourhood=1;
    }  
  }
  
  private void MakeDelay (int i) 
  {
    try 
    {
      Thread.sleep(i);
    }
    catch (InterruptedException e) { }
  }

  public void SetStartConfiguration(Vector Config)
  {
    StartConfig = new Vector(Config);
    StartConfigDistance = TspInstance.MyCities.GetConfigurationDistance(StartConfig);
    HowMany=StartConfig.size();
   
  }
  
  public void SetInitalTemperature(String S)
  {
    InitTemperature=Double.parseDouble(S);
  }
  
  public void SetCoolingRate(String S)
  {
    CoolingRate=Double.parseDouble(S);
  }  
  
  public void SetInnerLoopBreak(String S)
  {
    InnerLoopBreak=Integer.parseInt(S); 
  }  
  
  public void SetDelayTime(int S)
  {
    DelayTime=S;
  }  
  
  public void SetBestSolutions(boolean S)
  {
    BestSolutions=S;
  }  
  
  public void SetStopFlag()
  {
    StopThread=true;
  }  
  
  public boolean IsRunning()
  {
    if (!StopThread)
    {
      return true;
    }
    else
    {
      return false;
    }
  }    
      
  private int Trunc(double value)
  {
    int result=0;
    value=value-0.5;
    result=(int)Math.round(value);
    return result;
  }
  
  private Vector GiveNewConfig(Vector OldConfig)
  {
    Vector NewConfig = new Vector(OldConfig);
    
    if (Neighbourhood==0)  //Transposition
    {

      int oldindex=(int)(java.lang.Math.random()*HowMany);
      int newindex=(int)(java.lang.Math.random()*HowMany);
      while (oldindex==newindex)
      {
        newindex=(int)(java.lang.Math.random()*HowMany);
      }
      int newvalue = ((Integer)NewConfig.elementAt(newindex)).intValue();
      int oldvalue = ((Integer)NewConfig.elementAt(oldindex)).intValue();
      NewConfig.setElementAt(new Integer(newvalue),oldindex);
      NewConfig.setElementAt(new Integer(oldvalue),newindex);

    }
    else if (Neighbourhood==1) // 2-opt
    {

/*
      int index1=(int)(java.lang.Math.random()*HowMany);
      int index2=(int)(java.lang.Math.random()*HowMany);
      while (index1==index2)
      {
        index2=(int)(java.lang.Math.random()*HowMany);        
      }
      
      System.out.println("---------------------------");
      System.out.println(index1+" "+index2);
      for (int i=0;i<OldConfig.size();i++)
      {
        int x = ((Integer)OldConfig.elementAt(i)).intValue();
        System.out.print(x);
        System.out.print(" ");
      }  
      System.out.println();

      int tempindex1=0;
      int tempindex2=0;
      boolean changeall=false;
      if (index1<index2)
      {
        tempindex1=index1;
        tempindex2=index2;
        changeall=false;
      }
      else if(index1>index2)
      {
        tempindex1=index2+1;
        tempindex2=index1-1;
        if (tempindex1>tempindex2)
        {
          int tempvalue=tempindex1;
          tempindex1=tempindex2;
          tempindex2=tempvalue;
        }  
        changeall=true;
      }  
      
      Vector tempvector=new Vector();
      int testindex1=tempindex1;
      int testindex2=tempindex2;
      while (testindex1!=testindex2+1)
      {
        int newvalue = ((Integer)NewConfig.elementAt(testindex1)).intValue();
        tempvector.add(new Integer(newvalue));
        testindex1++;
      }     
      
      for (int i=0;i<tempvector.size();i++)
      {
        int x = ((Integer)tempvector.elementAt(i)).intValue();
        System.out.print(x);
        System.out.print(" ");
      }  
      System.out.println();
      
      
      
      for (int i=0;i<tempvector.size();i++)
      {
        int tempvalue=((Integer)tempvector.elementAt(tempvector.size()-i-1)).intValue();
        NewConfig.setElementAt(new Integer(tempvalue),i+tempindex1);
      }  
      
      if (changeall)
      {
        tempvector=new Vector(NewConfig);
        for (int i=0;i<NewConfig.size();i++)
        {
          int tempvalue=((Integer)tempvector.elementAt(NewConfig.size()-i-1)).intValue();
          NewConfig.setElementAt(new Integer(tempvalue),i);
        }  
      }  
        
//      if (changeall)
//      {  


      for (int i=0;i<NewConfig.size();i++)
      {
        int x = ((Integer)NewConfig.elementAt(i)).intValue();
        System.out.print(x);
        System.out.print(" ");
      }  
      System.out.println("");
      System.out.println("ENDE");
      
//      }

      
    }    
*/
      int index1=(int)(java.lang.Math.random()*HowMany);
      int index2=(int)(java.lang.Math.random()*HowMany);
      while (index1==index2)
      {
        index2=(int)(java.lang.Math.random()*HowMany);        
      }
      int tempindex1=index1;
      int tempindex2=index2;
      Vector tempvector = new Vector();
      while (tempindex1!=tempindex2)
      {
        int newvalue = ((Integer)NewConfig.elementAt(tempindex1)).intValue();
        tempvector.add(new Integer(newvalue));
        if ((tempindex1+1)<=(HowMany-1))
        {
          tempindex1+=1;
        }
        else
        {
          tempindex1=0;
        }  
      }       
      tempindex1=index1;
      tempindex2=index2;
      int temphowmany=0;
      while (tempindex1!=tempindex2)
      {
        temphowmany=tempvector.size();
        int tempvalue=((Integer)tempvector.elementAt(temphowmany-1)).intValue();
        NewConfig.setElementAt(new Integer(tempvalue),tempindex1);
        tempvector.removeElementAt(temphowmany-1);
        if ((tempindex1+1)<=(HowMany-1))
        {
          tempindex1+=1;
        }
        else
        {
          tempindex1=0;
        }  
      }  
    }
    

    return NewConfig;
  }  
  
  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));
  }  
  
  private void SetTemperature(double temp)
  {
    DecimalFormat df = new DecimalFormat("####0.00");
    String S = df.format(temp);
    TspInstance.SetTemperatureValue(S);
  }  
  
  public void Repaint()
  {
    if (ActStep>0)
    {
      if (!BestSolutions)
      {
        TspInstance.MyDraw.DrawConfiguration(NewConfig);
      }  
      else if (BestSolutions)
      {
        TspInstance.MyDraw.DrawConfiguration(BestConfig);
      }   
    }  
  }    
  

  private boolean AcceptNewConfig(double diff)
  {
    double randomnumber = java.lang.Math.random();
    return (randomnumber < Math.exp(-diff/Temperature));
  }

  public void run()
  {
    ActConfig  = new Vector(StartConfig);
    BestConfig = new Vector(StartConfig);
    BestConfigDistance = StartConfigDistance;
  
    Temperature=InitTemperature;
    ActStep=0;
    NeedNewConfigDistance=true;
    StopThread=false;

    SetStartConfigDistance();
    SetBestConfigDistance();
    SetPerConfigDistance();
    SetStepCount(ActStep);
    SetTemperature(Temperature);

    while ((Trunc(Temperature*100)>0) && (!StopThread))
    {

      TimesNoBetterConfig=0;
      NeedNewConfigDistance=true;
      
      while ((TimesNoBetterConfig<InnerLoopBreak) && (!StopThread))
      {
        ActStep++;
        SetStepCount(ActStep);

        if (NeedNewConfigDistance)
        {
          ActConfigDistance=TspInstance.MyCities.GetConfigurationDistance(ActConfig);
        }

        NewConfig=new Vector(GiveNewConfig(ActConfig));
        NewConfigDistance=TspInstance.MyCities.GetConfigurationDistance(NewConfig);

        ConfigDifference=NewConfigDistance-ActConfigDistance;
        
        if (ConfigDifference<0)
        {

          NeedNewConfigDistance=false;
          ActConfig= new Vector(NewConfig);
          ActConfigDistance=NewConfigDistance;

          if (ActConfigDistance<BestConfigDistance)
          {
             BestConfig = new Vector(NewConfig);
             BestConfigDistance=NewConfigDistance;
          
             SetBestConfigDistance();
             SetPerConfigDistance();
             TspInstance.MyDraw.DrawConfiguration(BestConfig);
           }  
            
        }
        else
        {  
          if (AcceptNewConfig(ConfigDifference))
          {
            NeedNewConfigDistance=false;
            ActConfig= new Vector(NewConfig);
            ActConfigDistance=NewConfigDistance;
          } 
          else
          {
            TimesNoBetterConfig+=1;
          }  
        }  
        if (!BestSolutions)
        {
          TspInstance.MyDraw.DrawConfiguration(ActConfig);
        }  
        else if (BestSolutions)
        {
          TspInstance.MyDraw.DrawConfiguration(BestConfig);
        }  
        
        MakeDelay(DelayTime);
      }

      Temperature=(Temperature*CoolingRate);
      SetTemperature(Temperature);
    }
    SetTemperature(0);
    TspInstance.MakeReady();
    TspInstance.MyCities.SetStartSolution(BestConfig,true);
  }
  

}