sasearch.java

java数据挖掘算法

package fss;

import shared.*;
import shared.Error;
import java.lang.*;
import java.util.*;
import java.io.*;

public class SASearch extends StateSpaceSearch{

//States are stored in graph member.

public static final int DEFAULT_MAX_STALE = 5;
public static final double DEFAULT_EPSILON = 0.001;
public static final double DEFAULT_INITIAL_LAMBDA = 0.001;
public static final int DEFAULT_MAX_EVALUATIONS = 5;
public static final int DEFAULT_MIN_EXP_EVALUATIONS = 5;
public static final int DEFAULT_SAS_SEED = 7258789;

public static final String MAX_NON_IMPROVING_EXPANSIONS_HELP = "Number of non-improving "
   +"expansions that cause the search to be considered stale (hence terminate)";
public static final String MIN_EXPANSION_IMPROVEMENT_HELP = "Improvement of less than this "
   +"epsilon is considered a non-improvement (search is still stale)";
public static final String INITIAL_LAMBDA_HELP = "The temperature in simulated annealing.  "
   +"Higher values cause more randomness";
public static final String MAX_EVALUATIONS_HELP = "Maximum evaluations per node";
public static final String MIN_EXP_EVALUATIONS_HELP = "Minimum evaluations before expanding";
public static final String SEED_HELP = "The seed for the simulated annealing random generator";




/** A random number generator. **/
   private Random randNumGen = new Random();

   int numNonImprovingExpansions;
   int maxNumberOfNonImprovingExpansions;
   double minIncreaseForImprovingExpansion;
   int maxEvaluations;
   int minExpEvaluations; // minimum evals before expanding a node
   int numReEvaluations;  // total number of reevaluations
   double initialLambda;
   int sasSeed;
//obs   DynamicArray<SANode> nodeList;
   Vector nodeList;



/***************************************************************************
  Returns the random number generator for this object.
@return The random number generator for this object.
***************************************************************************/
   public Random rand_num_gen() {return randNumGen;}

/***************************************************************************
  Sets the seed for the random number generator stored in this object.
@param seed	The new seed for the number generator.
***************************************************************************/
   public void init_rand_num_gen(long seed) {randNumGen.setSeed(seed);}

/***************************************************************************
  This class has no access to a copy constructor.
***************************************************************************/
   private SASearch(SASearch source){}

/***************************************************************************
  This class has no access to an assign method.
***************************************************************************/
   private void assign(SASearch source){}

//obs template <class LocalInfo, class GlobalInfo>
//obs SASearch<LocalInfo, GlobalInfo>::SASearch()
   public SASearch()
   {
      super();
      nodeList = new Vector();
      numReEvaluations = 0;
      set_defaults();
   }

//obs template <class LocalInfo, class GlobalInfo>
//obs void SASearch<LocalInfo, GlobalInfo>::set_defaults()
   public void set_defaults()
   {
      super.set_defaults();
      set_max_non_improving_expansions(DEFAULT_MAX_STALE);
      set_min_expansion_improvement(Globals.DEFAULT_EPSILON);
      set_max_evaluations(DEFAULT_MAX_EVALUATIONS);
      set_min_exp_evaluations(DEFAULT_MIN_EXP_EVALUATIONS);
      set_initial_lambda(DEFAULT_INITIAL_LAMBDA);
   }

/*public void set_user_options(String stem)
{
   super.set_user_options(stem);
   set_max_non_improving_expansions(
      get_option_int(stem + "MAX_STALE",
		     get_max_non_improving_expansions(),
		     MAX_NON_IMPROVING_EXPANSIONS_HELP,
		     true));
   set_min_expansion_improvement(
      get_option_real(stem + "EPSILON",
		      get_min_expansion_improvement(),
		      MIN_EXPANSION_IMPROVEMENT_HELP,
		      true));
   set_max_evaluations(
      get_option_int(stem + "MAX_EVALS",
		     get_max_evaluations(),
		     MAX_EVALUATIONS_HELP,
		     true));
   set_min_exp_evaluations(
      get_option_int(stem + "MIN_EXP_EVALS",
		     get_min_exp_evaluations(),
		     MIN_EXP_EVALUATIONS_HELP,
		     true));
   set_initial_lambda(
      get_option_real(stem + "LAMBDA",
		      get_initial_lambda(),
		      INITIAL_LAMBDA_HELP,
		      true));
   set_sas_seed(
      get_option_int(stem + "SAS_SEED",
		     DEFAULT_SAS_SEED,
		     SEED_HELP,
		     true));
}
*/





   protected boolean terminate()
   {
      if (nodeList.size() == 0) 
      {
         logOptions.LOG(2, "Terminating due to empty node list\n");
         return true;
      }
   
      MLJ.ASSERT(get_eval_limit() >= 0,"SASearch.terminate():get_eval_limit() < 0.");
      MLJ.ASSERT(graph.get_num_states() >= 0,"SASearch.terminate():graph.get_num_states() < 0.");
      MLJ.ASSERT(numNonImprovingExpansions >= 0,"SASearch.terminate():numNonImprovingExpansions < 0.");
      MLJ.ASSERT(get_max_non_improving_expansions() > 0,"SASearch.terminate():get_max_non_improving_expansions() <= 0.");

      if (numNonImprovingExpansions >= get_max_non_improving_expansions()) 
      {
         logOptions.LOG(2, "Terminating because number of non-improving expansions "
            +"hit the maximum ("+get_max_non_improving_expansions()
            +")\n");
         return true;
      }

      if ((get_eval_limit() != 0)&&(graph.get_num_states()+numReEvaluations > get_eval_limit()))
      {
         logOptions.LOG(2, "Terminating because more nodes were evaluated than "
            +"EVAL_LIMIT ("+graph.get_num_states()+numReEvaluations+">"
            +get_eval_limit()+")\n");
         return true;
      }
   
      return false;
   }

   public int get_max_non_improving_expansions()
   {
      return maxNumberOfNonImprovingExpansions;
   }

   public int get_sas_seed()
   {
      return sasSeed;
   }

   public void set_sas_seed(int newSeed)
   {
      sasSeed = newSeed;
      init_rand_num_gen(sasSeed);
   }

   void set_initial_lambda(double initLambda)
   {
      if (initLambda <= 0)
         Error.fatalErr("SASearch::set_initial_lambda: initLambda ("
            +initLambda+") must be greater than 0");
      initialLambda = initLambda;
   }

   void set_min_exp_evaluations(int minEval)
   {
      if (minEval < 1 || minEval > get_max_evaluations())
         Error.fatalErr("SASearch::set_min_exp_evaluations: minEval ("
            +minEval+") must be >0 and <max_evaluations"
            +get_max_evaluations());
      minExpEvaluations = minEval;
   }

   public void set_max_evaluations(int maxEval)
   {
      if (maxEval < 1)
         Error.fatalErr("SASearch::set_max_evaluations: maxEval ("
            +maxEval+") must be greater than 0");
      maxEvaluations = maxEval;
   }

   public int get_max_evaluations()
   {
      return maxEvaluations;
   }

   public void set_min_expansion_improvement(double minImprovement)
   {
      minIncreaseForImprovingExpansion = minImprovement;
   }

//obs template <class LocalInfo, class GlobalInfo>
//obs Real SASearch<LocalInfo, GlobalInfo>::get_min_expansion_improvement() const
   public double get_min_expansion_improvement()
   {
      return minIncreaseForImprovingExpansion;
   }

   public void set_max_non_improving_expansions(int maxExpansions)
   {
      if (maxExpansions < 1)
         Error.fatalErr("SASearch::set_max_non_improving_expansions: "
            +"maxExpansions ("+maxExpansions+") must be at least 1");
      maxNumberOfNonImprovingExpansions = maxExpansions;
   }

//obs Real SASearch<LocalInfo, GlobalInfo>::get_initial_lambda() const
   public double get_initial_lambda()
   {
      return initialLambda;
   }

//obs template <class LocalInfo, class GlobalInfo>
//obs int SASearch<LocalInfo, GlobalInfo>::get_min_exp_evaluations() const
   public int get_min_exp_evaluations()
   {
      return minExpEvaluations;
   }


//obs template <class LocalInfo, class GlobalInfo>
//obs void SASearch<LocalInfo, GlobalInfo>::reeval_node(int nodeNum,
//obs     GlobalInfo *gInfo, NodePtr& bestRetired,
//obs     StateSpace< State<LocalInfo, GlobalInfo> >& graph)
   private void reeval_node(int nodeNum,
      Object gInfo, Node bestRetired,
      StateSpace graph)

   {
      SANode saNode = (SANode)nodeList.get(nodeNum);
   // Re-evaluate node if it has not reached its max.
      if (saNode.numEvaluations < get_max_evaluations())
      {
         saNode.numEvaluations++;

      // when reevaluating, never get the real error
         saNode.fitness = graph.get_state(saNode.Node).eval(gInfo, false, true);
         logOptions.LOG(1, "re-evaluated node "+
            graph.get_state(saNode.Node)+"\n");
         logOptions.LOG(3, "Re-eval fitness = "+saNode.fitness
            +"\n");
         numReEvaluations++;
      }
      else
      {
         logOptions.LOG(2, "node "
            +graph.get_state(saNode.Node)
            +" has reached maximum number of evaluations ("
            +get_max_evaluations()+")\n");

      // if the newly retired node has a better evaluation than
      // the best retired node so far, replace the best retired node.
         if(bestRetired == null ||
               MLJ.approx_greater(saNode.fitness, graph.get_state(bestRetired).
               get_fitness()))
         {
            bestRetired = saNode.Node;
            logOptions.LOG(2, "new best node (" +(graph.get_num_states() + numReEvaluations)
               +" evals {retired}) "+graph.get_state(bestRetired)+"\n");