weka.attributeSelection
Class TabuSearch

java.lang.Object
  extended by weka.attributeSelection.ASSearch
      extended by weka.attributeSelection.TabuSearch
All Implemented Interfaces:
java.io.Serializable, OptionHandler, RevisionHandler, TechnicalInformationHandler

public class TabuSearch
extends ASSearch
implements OptionHandler, TechnicalInformationHandler

Class for performing the TabuSearch method.

Tabu Search :

Performs a search through the space of attribute subsets. Evading local maximums by accepting bad and diverse solutions and make further search in the best soluions. Stops when there's not more improvement in n iterations
;For more information see:

Abdel-Rahman Hedar, Jue Wangy,, Masao Fukushima (2006). Tabu Search for Attribute Reduction in Rough Set Theory. .

Valid options are:

 -Z <numInitialSolution>
  Specify the number of attributes 
  in the initial Solution..
 -P <diversificationProb>
  Specify the diversification probabilities,
  if this value is near to 0 then the best attributes
   will have more probabilities of keeping in the new diverse solution
 -S <seed>
  Set the random number seed.
  (default = 1)
 -N <number of neighbors>
  Set the number of neighbors to generate.
BibTeX:
 @book{Abdel-RahmanHedar2006,
    author = {Abdel-Rahman Hedar, Jue Wangy, and Masao Fukushima},
    month = {July},
    title = {Tabu Search for Attribute Reduction in Rough Set Theory},
    year = {2006},
    language = {English}
 }
 

from the Book: Tabu Search for Attribute Reduction in Rough Set Theory, Abdel-Rahman Hedar, Jue Wangy, and Masao Fukushima.

Version:
$Revision: 4976 $
Author:
Adrian Pino (apinoa@facinf.uho.edu.cu)
See Also:
Serialized Form

Nested Class Summary
 class TabuSearch.Subset
           
 
Constructor Summary
TabuSearch()
           
 
Method Summary
 int[] attributeList(java.util.BitSet group)
          converts a BitSet into a list of attribute indexes
 java.util.List<TabuSearch.Subset> bubbleSubsetSort(java.util.List<TabuSearch.Subset> subsetList)
          Sort a List of subsets according to their merits
 java.lang.String diversificationProbTipText()
          Returns the tip text for this property
 java.util.BitSet diversify(java.util.List<TabuSearch.Subset> neighborhood)
          Generate a diverse Bitset given a List of Subset
 TabuSearch.Subset eliteReducts(java.util.List<TabuSearch.Subset> RedSet, int numSubset)
          Find a better solution by intersecting and SFS of the best elite Reducts found till that moment
 TabuSearch.Subset GenerateInitialSolution(TabuSearch.Subset initial, int size)
          Generate an initial solution based in a Sequential Forward Selection (SFS)
 double getDiversificationProb()
          get the probability of diversification
 int getInitialSize()
          get the number of of attributes that are going to be in the initial Solution
 int getNumNeighborhood()
          get the number of neighborhood
 java.lang.String[] getOptions()
          Gets the current settings of TabuSearch.
 java.lang.String getRevision()
          Returns the revision string.
 int getSeed()
          get the value of the random number generator's seed
 TechnicalInformation getTechnicalInformation()
          Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.
 java.lang.String globalInfo()
          Returns a string describing this search method
 java.lang.String initialSizeTipText()
          Returns the tip text for this property
 TabuSearch.Subset joinSubsets(TabuSearch.Subset subset1, TabuSearch.Subset subset2)
          Join two subsets
 java.util.Enumeration listOptions()
          Returns an enumeration of all the available options..
 java.lang.String numNeighborhoodTipText()
          Returns the tip text for this property
 java.lang.String printSubset(TabuSearch.Subset subset)
           
 int[] search(ASEvaluation ASEval, Instances data)
          Searches the attribute subset space using Tabu Search.
 java.lang.String seedTipText()
          Returns the tip text for this property
 void setDiversificationProb(double p)
          set the probability of diverification
 void setInitialSize(int n)
          set the number of attributes that are going to be in the initial Solution
 void setNumNeighborhood(int n)
          set the number of neighborhood
 void setOptions(java.lang.String[] options)
          Valid options are:

 void setSeed(int s)
          set the seed for random number generation
 java.lang.String toString()
          returns a description of the search.
 
Methods inherited from class weka.attributeSelection.ASSearch
forName, makeCopies
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

TabuSearch

public TabuSearch()
Method Detail

search

public int[] search(ASEvaluation ASEval,
                    Instances data)
             throws java.lang.Exception
Searches the attribute subset space using Tabu Search.

Specified by:
search in class ASSearch
Parameters:
ASEvaluator - the attribute evaluator to guide the search
data - the training instances.
Returns:
an array of selected attribute indexes
Throws:
java.lang.Exception - if the search can't be completed

diversify

public java.util.BitSet diversify(java.util.List<TabuSearch.Subset> neighborhood)
Generate a diverse Bitset given a List of Subset

Parameters:
neighborhood - the list from which are going to be generate the diverse solution
Returns:
a diverse Bitset

eliteReducts

public TabuSearch.Subset eliteReducts(java.util.List<TabuSearch.Subset> RedSet,
                                      int numSubset)
                               throws java.lang.Exception
Find a better solution by intersecting and SFS of the best elite Reducts found till that moment

Parameters:
RedSet - the Subset List of the Elite Reducted found till that moment
numSubset - number of elites to intersect
Returns:
a the resulting Subset
Throws:
java.lang.Exception - if any evaluation can't be completed

GenerateInitialSolution

public TabuSearch.Subset GenerateInitialSolution(TabuSearch.Subset initial,
                                                 int size)
                                          throws java.lang.Exception
Generate an initial solution based in a Sequential Forward Selection (SFS)

Parameters:
size - number of posible attributes in the initial Solution
Returns:
an initial Subset containing the initial Solution
Throws:
java.lang.Exception - if the evaluation can not be completed

bubbleSubsetSort

public java.util.List<TabuSearch.Subset> bubbleSubsetSort(java.util.List<TabuSearch.Subset> subsetList)
Sort a List of subsets according to their merits

Parameters:
subsetList - the subsetList to be ordered
Returns:
a List with ordered subsets

joinSubsets

public TabuSearch.Subset joinSubsets(TabuSearch.Subset subset1,
                                     TabuSearch.Subset subset2)
                              throws java.lang.Exception
Join two subsets

Parameters:
subset1 - one of the subsets
subset2 - the other subset
Returns:
a new Subset that is te result of the Join
Throws:
java.lang.Exception - if the evaluation of the subsets can not be completed

attributeList

public int[] attributeList(java.util.BitSet group)
converts a BitSet into a list of attribute indexes

Parameters:
group - the BitSet to convert
Returns:
an array of attribute indexes

printSubset

public java.lang.String printSubset(TabuSearch.Subset subset)

globalInfo

public java.lang.String globalInfo()
Returns a string describing this search method

Returns:
a description of the search suitable for displaying in the explorer/experimenter gui

getTechnicalInformation

public TechnicalInformation getTechnicalInformation()
Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.

Specified by:
getTechnicalInformation in interface TechnicalInformationHandler
Returns:
the technical information about this class

getRevision

public java.lang.String getRevision()
Returns the revision string.

Specified by:
getRevision in interface RevisionHandler
Overrides:
getRevision in class ASSearch
Returns:
the revision

seedTipText

public java.lang.String seedTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setSeed

public void setSeed(int s)
set the seed for random number generation

Parameters:
s - seed value

getSeed

public int getSeed()
get the value of the random number generator's seed

Returns:
the seed for random number generation

diversificationProbTipText

public java.lang.String diversificationProbTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setDiversificationProb

public void setDiversificationProb(double p)
set the probability of diverification

Parameters:
p - the probability of change of search subspace in an abrupt way

getDiversificationProb

public double getDiversificationProb()
get the probability of diversification

Returns:
the probability of diversification

numNeighborhoodTipText

public java.lang.String numNeighborhoodTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setNumNeighborhood

public void setNumNeighborhood(int n)
set the number of neighborhood

Parameters:
n - the number of neighborhood

getNumNeighborhood

public int getNumNeighborhood()
get the number of neighborhood

Returns:
the number of neighborhood

initialSizeTipText

public java.lang.String initialSizeTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setInitialSize

public void setInitialSize(int n)
set the number of attributes that are going to be in the initial Solution

Parameters:
n - the number of attributes

getInitialSize

public int getInitialSize()
get the number of of attributes that are going to be in the initial Solution

Returns:
the number of attributes

listOptions

public java.util.Enumeration listOptions()
Description copied from interface: OptionHandler
Returns an enumeration of all the available options..

Specified by:
listOptions in interface OptionHandler
Returns:
an enumeration of all available options.

setOptions

public void setOptions(java.lang.String[] options)
                throws java.lang.Exception
Valid options are:

 -Z <numInitialSolution>
  Specify the number of attributes 
  in the initial Solution..
 -P <diversificationProb>
  Specify the diversification probabilities,
  if this value is near to 0 then the best attributes
   will have more probabilities of keeping in the new diverse solution
 -S <seed>
  Set the random number seed.
  (default = 1)
 -N <number of neighbors>
  Set the number of neighbors to generate.

Specified by:
setOptions in interface OptionHandler
Parameters:
options - the list of options as an array of strings
Throws:
java.lang.Exception - if an option is not supported

getOptions

public java.lang.String[] getOptions()
Gets the current settings of TabuSearch.

Specified by:
getOptions in interface OptionHandler
Returns:
an array of strings suitable for passing to setOptions()

toString

public java.lang.String toString()
returns a description of the search.

Overrides:
toString in class java.lang.Object
Returns:
a description of the search as a String.