content: /*
   * 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., 675 Mass Ave, Cambridge, MA 02139, USA.
   */
  
  /*
   * LAGDHillClimber.java
   * Copyright (C) 2005 Manuel Neubach
   * 
   */
  
  package weka.classifiers.bayes.net.search.local;
  
  import weka.classifiers.bayes.BayesNet;
  import weka.core.Instances;
  import weka.core.Option;
  import weka.core.RevisionUtils;
  import weka.core.Utils;
  
  import java.util.Enumeration;
  import java.util.Vector;
  
  /** 
   <!-- globalinfo-start -->
   * This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing. Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. The search is not restricted by an order on the variables (unlike K2). The difference with B and B2 is that this hill climber also considers arrows part of the naive Bayes structure for deletion.
   * <p/>
   <!-- globalinfo-end -->
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -L &lt;nr of look ahead steps&gt;
   *  Look Ahead Depth</pre>
   * 
   * <pre> -G &lt;nr of good operations&gt;
   *  Nr of Good Operations</pre>
   * 
   * <pre> -P &lt;nr of parents&gt;
   *  Maximum number of parents</pre>
   * 
   * <pre> -R
   *  Use arc reversal operation.
   *  (default false)</pre>
   * 
   * <pre> -N
   *  Initial structure is empty (instead of Naive Bayes)</pre>
   * 
   * <pre> -mbc
   *  Applies a Markov Blanket correction to the network structure, 
   *  after a network structure is learned. This ensures that all 
   *  nodes in the network are part of the Markov blanket of the 
   *  classifier node.</pre>
   * 
   * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
   *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
   * 
   <!-- options-end -->
   * 
   * @author Manuel Neubach
   * @version $Revision: 1.7 $
   */
  public class LAGDHillClimber 
      extends HillClimber {
    
      /** for serialization */
      static final long serialVersionUID = 7217437499439184344L;
  
      /** Number of Look Ahead Steps **/
      int m_nNrOfLookAheadSteps = 2;
  
      /** Number of Good Operations per Step **/
      int m_nNrOfGoodOperations = 5;
  
     /**
       * search determines the network structure/graph of the network
       * 
       * @param bayesNet the network
       * @param instances the data to use
       * @throws Exception if something goes wrong
       */
     protected void search(BayesNet bayesNet, Instances instances) throws Exception {
          int k=m_nNrOfLookAheadSteps;  // Number of Look Ahead Steps
          int l=m_nNrOfGoodOperations; // Number of Good Operations per step
          lookAheadInGoodDirectionsSearch(bayesNet, instances, k, l);
     } // search
  
  
     /**
      * lookAheadInGoodDirectionsSearch determines the network structure/graph of the network
      * with best score according to LAGD Hill Climbing
      * 
      * @param bayesNet the network
      * @param instances the data to use
      * @param nrOfLookAheadSteps
      * @param nrOfGoodOperations
      * @throws Exception if something goes wrong
      */
      protected void lookAheadInGoodDirectionsSearch(BayesNet bayesNet, Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations) throws Exception {
           System.out.println("Initializing Cache");
           initCache(bayesNet, instances);
  
           while (nrOfLookAheadSteps>1) {         
              System.out.println("Look Ahead Depth: "+nrOfLookAheadSteps);
              boolean legalSequence = true;
              double sequenceDeltaScore = 0;
              Operation [] bestOperation=new Operation [nrOfLookAheadSteps];
           
              bestOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps, nrOfGoodOperations);
              for (int i = 0; i < nrOfLookAheadSteps; i++) {
                 if (bestOperation [i] == null) {
                    legalSequence=false;
                 } else {
                    sequenceDeltaScore += bestOperation [i].m_fDeltaScore;
                 }
              }
              while (legalSequence && sequenceDeltaScore > 0) {
                 System.out.println("Next Iteration..........................");
                 for (int i = 0; i < nrOfLookAheadSteps; i++) {
                    performOperation(bayesNet, instances,bestOperation [i]);
                 }
                 bestOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps, nrOfGoodOperations);
                 sequenceDeltaScore = 0;
                 for (int i = 0; i < nrOfLookAheadSteps; i++) {
                    if (bestOperation [i] != null) {
                       System.out.println(bestOperation [i].m_nOperation + " " + bestOperation [i].m_nHead + " " + bestOperation [i].m_nTail);
                       sequenceDeltaScore += bestOperation [i].m_fDeltaScore;
                    } else {
                       legalSequence = false;
  
                    }
                    System.out.println("DeltaScore: "+sequenceDeltaScore);
                 }
              }
              --nrOfLookAheadSteps;
           }
  
           /** last steps with greedy HC **/          
           Operation oOperation = getOptimalOperation(bayesNet, instances);
           while ((oOperation != null) && (oOperation.m_fDeltaScore > 0)) {
  	    performOperation(bayesNet, instances, oOperation);
              System.out.println("Performing last greedy steps");
              oOperation = getOptimalOperation(bayesNet, instances);
           }               
  	 // free up memory
  	 m_Cache = null;
      } // lookAheadInGoodDirectionsSearch
  
      /**
        * getAntiOperation determines the Operation, which is needed to cancel oOperation
        * 
        * @param oOperation Operation to cancel
        * @return antiOperation to oOperation
        * @throws Exception if something goes wrong
        */
      protected Operation getAntiOperation(Operation oOperation) throws Exception {
          if (oOperation.m_nOperation == Operation.OPERATION_ADD)
             return (new Operation (oOperation.m_nTail, oOperation.m_nHead, Operation.OPERATION_DEL));
          else {
             if (oOperation.m_nOperation == Operation.OPERATION_DEL)
                return (new Operation (oOperation.m_nTail, oOperation.m_nHead, Operation.OPERATION_ADD));
             else {
                return (new Operation (oOperation.m_nHead, oOperation.m_nTail, Operation.OPERATION_REVERSE));
             }
           }
      } // getAntiOperation
  
  
      /**
        * getGoodOperations determines the nrOfGoodOperations best Operations, which are considered for
        * the calculation of an optimal operationsequence
        * @param bayesNet Bayes network to apply operation on
        * @param instances data set to learn from
        * @param nrOfGoodOperations number of good operations to consider
        * @return good operations to consider
        * @throws Exception if something goes wrong
        **/
      protected Operation [] getGoodOperations(BayesNet bayesNet, Instances instances, int nrOfGoodOperations) throws Exception {
  		Operation [] goodOperations=new Operation [nrOfGoodOperations];
         		for (int i = 0; i < nrOfGoodOperations; i++) {
                     goodOperations [i] = getOptimalOperation(bayesNet, instances);
                     if (goodOperations[i] != null) {
                        m_Cache.put(goodOperations [i], -1E100);
                     } else i=nrOfGoodOperations;
                  }
                  for (int i = 0; i < nrOfGoodOperations; i++) {
                     if (goodOperations[i] != null) {
                        if (goodOperations [i].m_nOperation!=Operation.OPERATION_REVERSE) {
                           m_Cache.put(goodOperations [i], goodOperations [i].m_fDeltaScore);
                        } else {
                           m_Cache.put(goodOperations [i], goodOperations [i].m_fDeltaScore - m_Cache.m_fDeltaScoreAdd[goodOperations[i].m_nHead] [goodOperations [i].m_nTail]);
                        }
                     } else i=nrOfGoodOperations;
                  }
                  return goodOperations;
      } // getGoodOperations
  
      /**
        * getOptimalOperations determines an optimal operationsequence in respect of the parameters 
        * nrOfLookAheadSteps and nrOfGoodOperations
        * @param bayesNet Bayes network to apply operation on
        * @param instances data set to learn from
        * @param nrOfLookAheadSteps number of lood ahead steps to use
        * @param nrOfGoodOperations number of good operations to consider
        * @return optimal sequence of operations in respect to nrOfLookAheadSteps and nrOfGoodOperations
        * @throws Exception if something goes wrong
        **/
      protected Operation [] getOptimalOperations(BayesNet bayesNet, Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations) throws Exception {
         if (nrOfLookAheadSteps == 1) { // Abbruch der Rekursion
            Operation [] bestOperation = new Operation [1];
            bestOperation [0] = getOptimalOperation(bayesNet, instances);
            return(bestOperation);  // Abbruch der Rekursion
         } else {
            double bestDeltaScore = 0;
            double currentDeltaScore = 0;
            Operation [] bestOperation = new Operation [nrOfLookAheadSteps];
            Operation [] goodOperations = new Operation [nrOfGoodOperations];
            Operation [] tempOperation = new Operation [nrOfLookAheadSteps-1];
            goodOperations = getGoodOperations(bayesNet, instances, nrOfGoodOperations);
            for (int i = 0; i < nrOfGoodOperations; i++) {
             if (goodOperations[i] != null) {
               performOperation(bayesNet, instances, goodOperations [i]);
               tempOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps-1, nrOfGoodOperations); // rekursiver Abstieg
               currentDeltaScore = goodOperations [i].m_fDeltaScore;
               for (int j = 0; j < nrOfLookAheadSteps-1; j++) {
                  if (tempOperation [j] != null) {
                     currentDeltaScore += tempOperation [j].m_fDeltaScore;
                  }
               }
               performOperation(bayesNet, instances, getAntiOperation(goodOperations [i]));
                        if (currentDeltaScore > bestDeltaScore) {
                          bestDeltaScore = currentDeltaScore;
                          bestOperation [0] = goodOperations [i];
                          for (int j = 1; j < nrOfLookAheadSteps; j++) {
                            bestOperation [j] = tempOperation [j-1];
                          }
                      }
              } else i=nrOfGoodOperations;
             }
             return(bestOperation);
         }
      } // getOptimalOperations
  
  
  	/**
  	 * Sets the max number of parents
  	 *
  	 * @param nMaxNrOfParents the max number of parents
  	 */
  	public void setMaxNrOfParents(int nMaxNrOfParents) {
  	  m_nMaxNrOfParents = nMaxNrOfParents;
  	} 
  
  	/**
  	 * Gets the max number of parents.
  	 *
  	 * @return the max number of parents
  	 */
  	public int getMaxNrOfParents() {
  	  return m_nMaxNrOfParents;
  	} 
  
  	/**
  	 * Sets the number of look-ahead steps
  	 *
  	 * @param nNrOfLookAheadSteps the number of look-ahead steps
  	 */
  	public void setNrOfLookAheadSteps(int nNrOfLookAheadSteps) {
  	  m_nNrOfLookAheadSteps = nNrOfLookAheadSteps;
  	} 
  
  	/**
  	 * Gets the number of look-ahead steps
  	 *
  	 * @return the number of look-ahead step
  	 */
  	public int getNrOfLookAheadSteps() {
  	  return m_nNrOfLookAheadSteps;
  	} 
  
  	/**
  	 * Sets the number of "good operations"
  	 *
  	 * @param nNrOfGoodOperations the number of "good operations"
  	 */
  	public void setNrOfGoodOperations(int nNrOfGoodOperations) {
  	  m_nNrOfGoodOperations = nNrOfGoodOperations;
  	} 
  
  	/**
  	 * Gets the number of "good operations"
  	 *
  	 * @return the number of "good operations"
  	 */
  	public int getNrOfGoodOperations() {
  	  return m_nNrOfGoodOperations;
  	} 
  
  
  	/**
  	 * Returns an enumeration describing the available options.
  	 *
  	 * @return an enumeration of all the available options.
  	 */
  	public Enumeration listOptions() {
  		Vector newVector = new Vector();
  
  		newVector.addElement(new Option("\tLook Ahead Depth", "L", 2, "-L <nr of look ahead steps>"));
  		newVector.addElement(new Option("\tNr of Good Operations", "G", 5, "-G <nr of good operations>"));
  
  		Enumeration enm = super.listOptions();
  		while (enm.hasMoreElements()) {
  			newVector.addElement(enm.nextElement());
  		}
  		return newVector.elements();
  	} // listOptions
  
  	/**
  	 * Parses a given list of options. Valid options are:<p>
  	 *
  	 <!-- options-start -->
  	 * Valid options are: <p/>
  	 * 
  	 * <pre> -L &lt;nr of look ahead steps&gt;
  	 *  Look Ahead Depth</pre>
  	 * 
  	 * <pre> -G &lt;nr of good operations&gt;
  	 *  Nr of Good Operations</pre>
  	 * 
  	 * <pre> -P &lt;nr of parents&gt;
  	 *  Maximum number of parents</pre>
  	 * 
  	 * <pre> -R
  	 *  Use arc reversal operation.
  	 *  (default false)</pre>
  	 * 
  	 * <pre> -N
  	 *  Initial structure is empty (instead of Naive Bayes)</pre>
  	 * 
  	 * <pre> -mbc
  	 *  Applies a Markov Blanket correction to the network structure, 
  	 *  after a network structure is learned. This ensures that all 
  	 *  nodes in the network are part of the Markov blanket of the 
  	 *  classifier node.</pre>
  	 * 
  	 * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
  	 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
  	 * 
  	 <!-- options-end -->
  	 *
  	 * @param options the list of options as an array of strings
  	 * @throws Exception if an option is not supported
  	 */
  	public void setOptions(String[] options) throws Exception {
  	  	String sNrOfLookAheadSteps = Utils.getOption('L', options);
  		if (sNrOfLookAheadSteps.length() != 0) {
  		  setNrOfLookAheadSteps(Integer.parseInt(sNrOfLookAheadSteps));
  		} else {
  		  setNrOfLookAheadSteps(2);
  		}
  
                  String sNrOfGoodOperations = Utils.getOption('G', options);
  		if (sNrOfGoodOperations.length() != 0) {
  		  setNrOfGoodOperations(Integer.parseInt(sNrOfGoodOperations));
  		} else {
  		  setNrOfGoodOperations(5);
  		}
  		
  		super.setOptions(options);
  	} // setOptions
  
  	/**
  	 * Gets the current settings of the search algorithm.
  	 *
  	 * @return an array of strings suitable for passing to setOptions
  	 */
  	public String[] getOptions() {
  		String[] superOptions = super.getOptions();
  		String[] options = new String[9 + superOptions.length];
  		int current = 0;
  
  		options[current++] = "-L";
  		options[current++] = "" + m_nNrOfLookAheadSteps;
  		
  		options[current++] = "-G";
  		options[current++] = "" + m_nNrOfGoodOperations;
  
  		// insert options from parent class
  		for (int iOption = 0; iOption < superOptions.length; iOption++) {
  			options[current++] = superOptions[iOption];
  		}
  
  		// Fill up rest with empty strings, not nulls!
  		while (current < options.length) {
  			options[current++] = "";
  		}
  		return options;
  	} // getOptions
  
  
  	/**
  	 * This will return a string describing the search algorithm.
  	 * @return The string.
  	 */
  	public String globalInfo() {
  	  return "This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing." +
  	  " Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) " + 
  	  "but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely " +
  	  "higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. " +
  	  "The search is not restricted by an order " +
  	  "on the variables (unlike K2). The difference with B and B2 is that this hill " +
            "climber also considers arrows part of the naive Bayes structure for deletion.";
  	} // globalInfo
  
  	/**
  	 * @return a string to describe the Number of Look Ahead Steps option.
  	 */
  	public String nrOfLookAheadStepsTipText() {
  	  return "Sets the Number of Look Ahead Steps. 'nrOfLookAheadSteps = 2' means that all network structures in a " +
  	  "distance of 2 (from the current network structure) are taken into account for the decision which arcs to add, " +
  	  "remove or reverse. 'nrOfLookAheadSteps = 1' results in Greedy Hill Climbing." ;
  	} // nrOfLookAheadStepsTipText
  
  	/**
  	 * @return a string to describe the Number of Good Operations option.
  	 */
  	public String nrOfGoodOperationsTipText() {
  	  return "Sets the Number of Good Operations per Look Ahead Step. 'nrOfGoodOperations = 5' means that for the next " +
  	  "Look Ahead Step only the 5 best Operations (adding, deleting or reversing an arc) are taken into account for the " +
  	  "calculation of the best sequence consisting of nrOfLookAheadSteps operations." ;
  	} // nrOfGoodOperationsTipText
  
  	/**
  	 * Returns the revision string.
  	 * 
  	 * @return		the revision
  	 */
  	public String getRevision() {
  	  return RevisionUtils.extract("$Revision: 1.7 $");
  	}
  
  } // LAGDHillClimber
  