sasearch.java

机器学习算法中的FSS算法

	 // if the best retired node has no test set error, give it one
	 // if we're in best error mode
            if(get_show_test_set_perf() == ShowTestSetPerf.showBestOnly &&
                  graph.get_state(bestRetired).get_test_set_fitness() < 0)
            {
               graph.get_state(bestRetired).eval(gInfo, true, false);
               logOptions.LOG(2, "needed test set error for best retired node\n");
            }
         }

      // yank the maxed-out node out of the list, then use
      // truncate to reduce the list's size
//obs      nodeList[nodeNum] = nodeList[nodeList.high()];
//obs      nodeList.truncate(nodeList.size() - 1);
         nodeList.setElementAt(nodeList.lastElement(),nodeNum);
         nodeList.remove(nodeList.size()-1);
      }
   }


   public State search(State initialState, Object gInfo)
   {
      return search(initialState,gInfo,Globals.EMPTY_STRING);
   }

   public State search(State initialState, Object gInfo,
      String displayFileName)
   {
   // Initial setup.
//obs   nodeList.truncate(0);   // make sure node list has 0 elements
      nodeList.clear();   // make sure node list has 0 elements
      graph = null;
//obs   graph = new StateSpace< State<LocalInfo, GlobalInfo> >;
      graph = new StateSpace();
      if(get_log_level() > 0)
         graph.set_log_level(get_log_level() - 1);
      double lambda = get_initial_lambda();
      Node bestRetired = null;
      numReEvaluations = 0;
      numExpansions = 0;
   
      numNonImprovingExpansions = 0;
   
   // Evalute initial node and put on node list.
      double initialEval = initialState.eval(gInfo,
         get_show_test_set_perf() == ShowTestSetPerf.showAlways);
      initialState.set_eval_num(graph.get_next_eval_num());
      Node initialNode = graph.create_node(initialState);
      MLJ.ASSERT(initialNode != null,"SASearch.search:initialNode == null.");
//obs   nodeList[nodeList.size()] = SANode(initialNode, initialEval);
      nodeList.add(new SANode(initialNode, initialEval));
      double bestEval = State.MIN_EVALUATION;
      Node bestNode = null;
      boolean lastIterationWasExpansion = false;

      logOptions.LOG(1, "Beginning SASearch\n");
      logOptions.LOG(1, "initial node = "
         +((State)graph.get_state(initialNode)).get_eval_num()+"\n"
         +graph.get_state(initialNode)+"\n");

      while (!terminate())
      {
      // Use the sim_anneal function to pick a node randomly.  Use the
      // standard-deviation of the first node to determine lambda.
      // If the first node has no standard deviation, always pick it.
         int nodeNum;

      // pick a lambda
         double saLambda = graph.get_state(((SANode)nodeList.get(0)).Node).get_std_dev();
         if(nodeList.size() > 1 && saLambda != 0 && saLambda != Globals.UNDEFINED_VARIANCE)
         {

	 // build a real array of fitnesses for sim_anneal
//obs	 double[] fitnessArray(nodeList.low(), nodeList.size());
            double[] fitnessArray = new double[nodeList.size()];
//obs	 for(int i=nodeList.low(); i<=nodeList.high(); i++)
            for(int i = 0; i < nodeList.size(); i++)
               fitnessArray[i] = graph.get_state(((SANode)nodeList.get(i)).Node).get_fitness();

	 // call sim_anneal to pick the slot
            nodeNum = sim_anneal.sim_anneal(fitnessArray, saLambda*lambda, rand_num_gen());
         }
         else
            nodeNum = 0;
      
         logOptions.LOG(2, "picked slot "+nodeNum+": "
            +graph.get_state(((SANode)nodeList.get(nodeNum)).Node)+"\n");

         if (((SANode)nodeList.get(nodeNum)).isExpanded ||
               ((SANode)nodeList.get(nodeNum)).numEvaluations < get_min_exp_evaluations())
         {
            lastIterationWasExpansion = false;
            reeval_node(nodeNum, gInfo, bestRetired, graph);
         }
         else
         {
	 // Evaluate all successors not already in the graph and add them
	 // to the node list.
            lastIterationWasExpansion = true;
            numNonImprovingExpansions++;
            logOptions.LOG(1, "expanded node "
               +graph.get_state(((SANode)nodeList.get(nodeNum)).Node)+"\n");
            ((SANode)nodeList.get(nodeNum)).isExpanded = true;
//obs	 DblLinkList<State<LocalInfo, GlobalInfo>*>* successors =
            LinkedList successors =
            graph.get_state(((SANode)nodeList.get(nodeNum)).Node).gen_succ(gInfo, graph,
               get_show_test_set_perf() == ShowTestSetPerf.showAlways);
//obs	 while (!successors.empty()) {
            while (!(successors.size() == 0))
            {
//obs	    State<LocalInfo, GlobalInfo>* childState = successors.remove_front();
//obs	    State childState = successors.remove_front();
               State childState = (State)successors.removeFirst();
               Node childNode = childState.get_node(graph);
               MLJ.ASSERT(childNode != null,"SASearch.search:childNode == null.");
               double childEval = childState.get_fitness();
               MLJ.ASSERT(childEval > State.MIN_EVALUATION,"SASearch.search:childEval <= State.MIN_EVALUATION.");
//obs	    nodeList[nodeList.size()] = SANode(childNode, childEval);
               nodeList.add(new SANode(childNode, childEval));
            }
            successors = null;
         }

      // Make sure firstNode has been evaluated enough times.
      // Sort list of nodes (best first) and display best node.
//obs      nodeList.sort();
         SANode.sort(nodeList);
//      IFLOG(3, display_nodelist(get_log_stream()));

      // If node 0 is the last node and gets retired, then we have
      // no nodes remaining in the nodeList and we must exit this
      // loop.
         while (nodeList.size() > 0 &&
            ((SANode)nodeList.get(0)).numEvaluations < get_min_exp_evaluations())
         {
            reeval_node(0, gInfo, bestRetired, graph);
//obs	 nodeList.sort();
            SANode.sort(nodeList);
//         IFLOG(3, display_nodelist(get_log_stream()));
         }
         if(nodeList.size() > 0)
         {
            Node firstNode = ((SANode)nodeList.get(0)).Node;
            MLJ.ASSERT(firstNode != null, "SASearch.search:firstNode == null.");
            double firstEval = ((State)graph.get_state(firstNode)).get_fitness();
	 // If two nodes have the same error, one gets evaluated
	 //    and drops, we have a new best node.
	 // Another possibility is that the first node's fitness changed.
            if (firstNode != bestNode || firstEval != bestEval)
            {
               bestEval = firstEval;
               if ((bestRetired != null)&&(((State)graph.get_state(bestRetired)).get_fitness()>bestEval))
               {
                  logOptions.LOG(2, "best node is retired "+graph.get_state(bestRetired)+"\n");
                  bestNode = firstNode;
               }
               else if (firstNode != bestNode)
               {
                  if(bestNode == null ||
                     Math.abs(firstEval - ((State)graph.get_state(bestNode)).get_fitness()) >
                     get_min_expansion_improvement())
                  {
                     numNonImprovingExpansions = 0;
                     if (bestNode != null)
                     {
                        logOptions.LOG(2, "Resetting stale to 0.  First is "+firstEval
                           +" best is "
                           +((State)graph.get_state(bestNode)).get_fitness()+"\n");
                     }
                  }
                  else
                     logOptions.LOG(3, "Non-stale improvement\n");
                  bestNode = firstNode;

	       // get real error for best node if called for
                  if(get_show_test_set_perf() == ShowTestSetPerf.showBestOnly)
                     ((State)graph.get_state(bestNode)).eval(gInfo, true, false);
	    
                  logOptions.LOG(1, "new best node ("+(graph.get_num_states() +
                     numReEvaluations)+" evals) "
                     +graph.get_state(bestNode)+"\n");
               }
               else
               {
                  logOptions.LOG(2, "re-evaluated best node ("+(graph.get_num_states() +
                     numReEvaluations)+" evals) "
                     +graph.get_state(bestNode)+"\n");
               }
            }
         }
         if(lastIterationWasExpansion)
            numExpansions++;
      
         logOptions.LOG(1, "Iteration complete.  ");
         if (lastIterationWasExpansion)
            logOptions.LOG(1, "Expansion ("+numNonImprovingExpansions+" stale).  ");
         else
            logOptions.LOG(1, "Reevaluation.  ");
         logOptions.LOG(1, "\n");

         logOptions.LOG(1, "Total evaluations: "+(graph.get_num_states()+numReEvaluations)
            +" (" +graph.get_num_states() +" new + " +
         numReEvaluations +"old)\n" );

         Node apparentBest;
         if((bestRetired != null)&&(((State)graph.get_state(bestNode)).get_fitness()<
            ((State)graph.get_state(bestRetired)).get_fitness()))
         {

            logOptions.LOG(1, "Current best (retired) ");
            apparentBest = bestRetired;
         }
         else
         {
            logOptions.LOG(1, "Current best ");
            apparentBest = bestNode;
         }

         logOptions.LOG(1, "(" +(graph.get_num_states() + numReEvaluations)+" evals) ");
         logOptions.LOG(1, graph.get_state(apparentBest) +"\n");
      }

   // get real error for final node if called for
      if((bestRetired != null)&&(((State)graph.get_state(bestRetired)).get_fitness() >=
            ((State)graph.get_state(bestNode)).get_fitness()))
      {
         logOptions.LOG(2, "Final best node is best retired node\n");
         bestNode = bestRetired;
      }
      if(get_show_test_set_perf() == ShowTestSetPerf.showFinalOnly)
         ((State)graph.get_state(bestNode)).eval(gInfo, true, false);
   // @@ temporary hack to get this working.  Should be an ASSERT
   // else if(get_show_test_set_perf() == ShowTestSetPerf.showBestOnly)
      // we're supposed to have a real error here, so make sure we
      // actually have one.
      // ASSERT(graph.get_state(bestNode).get_real_error() >= 0);
      else if(get_show_test_set_perf() == ShowTestSetPerf.showBestOnly && 
	   ((State)graph.get_state(bestNode)).get_test_set_fitness() < 0)
      {
         logOptions.LOG(1, "WARNING: final best node has no test set error! "
            +" computing now...\n");
         ((State)graph.get_state(bestNode)).eval(gInfo, true, false);
      }

      logOptions.LOG(1, "final best node = "
         +graph.get_state(bestNode)+"\n");

      logOptions.LOG(1, "expanded " +numExpansions +" nodes\n");
      logOptions.LOG(2, "evaluated " +(graph.get_num_states()+numReEvaluations)
         +" nodes\n");
      graph.set_final_node(bestNode);
   
   // display the state space, if called for
//obs      if(displayFileName != null)
      if(displayFileName != Globals.EMPTY_STRING)
      {
//obs      MLCOStream out(displayFileName);
         try
         {
            FileWriter out = new FileWriter(displayFileName);
            DotGraphPref pref = new DotGraphPref();
            graph.display(out, pref);
         }catch(IOException e){e.printStackTrace(); System.exit(1);}
      }
      MLJ.ASSERT(bestNode != null,"SASearch.search:bestNode == null.");
      return (State)graph.get_state(bestNode);
   }


/*
   // Private methods
   virtual void display_nodelist(MLCOStream& stream = Mcout) const;
   virtual void reeval_node(int nodeNum, GlobalInfo *gInfo,
			    NodePtr& bestRetired,
			    StateSpace< State<LocalInfo, GlobalInfo> >& graph);
public:
   
   virtual const State<LocalInfo, GlobalInfo>&
      search(State<LocalInfo, GlobalInfo>* initialState, GlobalInfo *gInfo,
	     const MString& displayFileName = EMPTY_STRING);
*/

}