SAT
Class SAT

java.lang.Object
  AbstractClasses.ProblemDomain
      SAT.SAT

public class SAT
extends ProblemDomain

This class implements the SAT problem domain.

Author:

Matthew Hyde. mvh@cs.nott.ac.uk

Nested Class Summary

Nested classes/interfaces inherited from class AbstractClasses.ProblemDomain

ProblemDomain.HeuristicType

Field Summary

Fields inherited from class AbstractClasses.ProblemDomain

depthOfSearch, heuristicCallRecord, heuristicCallTimeRecord, intensityOfMutation, rng

Constructor Summary

SAT(long seed)
Constructs a new SAT object with a seed for the random number generator.

Method Summary

double	applyHeuristic(int heuristicID, int solutionSourceIndex, int solutionDestinationIndex) Applies the heuristic specified by heuristicID to the solution at position solutionSourceIndex and places the resulting solution at position solutionDestinationIndex in the solution array.
double	applyHeuristic(int heuristicID, int solutionSourceIndex1, int solutionSourceIndex2, int solutionDestinationIndex) Apply the heuristic specified by heuristicID to the solutions at position solutionSourceIndex1 and position solutionSourceIndex2 and put the resulting solution at position solutionDestinationIndex.
java.lang.String	bestSolutionToString() Gets a String representation of the best solution found so far by the HyperHeuristic.
boolean	compareSolutions(int solutionIndex1, int solutionIndex2) Compares two solutions in the memory for equality.
void	copySolution(int source, int destination) Copies a solution from one position in the solution array to another
double	getBestSolutionValue() Returns the objective function value of the best solution found so far by the HyperHeuristic.
double	getFunctionValue(int solutionIndex) Gets the objective function value of the solution at index solutionIndex
int[]	getHeuristicsOfType(ProblemDomain.HeuristicType hType) Gets an array of heuristicIDs of the type specified by heuristicType.
int[]	getHeuristicsThatUseDepthOfSearch() Gets an array of heuristicIDs that use the depthOfSearch parameter
int[]	getHeuristicsThatUseIntensityOfMutation() Gets an array of heuristicIDs that use the intensityOfMutation parameter
int	getNumberOfHeuristics() Gets the number of heuristics available in this problem domain
int	getNumberOfInstances() Gets the number of instances available in this problem domain
void	initialiseSolution(int index) Create an initial solution at a specified position in the memory array.
void	loadInstance(int instanceID) Loads the instance specified by instanceID.
void	setDepthOfSearch(double depthOfSearch) Sets the parameter specifying the extent to which a local search heuristic will modify the solution.
void	setIntensityOfMutation(double intensityOfMutation) Sets the parameter specifying the extent to which a mutation or ruin-recreate low level heuristic will mutate the solution.
void	setMemorySize(int size) Sets the size of the array where the solutions are stored.
java.lang.String	solutionToString(int solutionIndex) Gets a String representation of a given solution in memory
java.lang.String	toString() Gets the name of the problem domain.

Methods inherited from class AbstractClasses.ProblemDomain

getDepthOfSearch, getHeuristicCallRecord, getheuristicCallTimeRecord, getIntensityOfMutation

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SAT

public SAT(long seed)

Constructs a new SAT object with a seed for the random number generator.

Parameters:

seed -

Method Detail

setDepthOfSearch

public void setDepthOfSearch(double depthOfSearch)

Description copied from class: ProblemDomain

Sets the parameter specifying the extent to which a local search heuristic will modify the solution. This parameter is related to the number of improving steps to be completed by the local search heuristics.

Overrides:

setDepthOfSearch in class ProblemDomain

Parameters:

depthOfSearch - must be in the range 0 to 1. The initial value of 0.1 represents the default operation of the low level heuristic.

setIntensityOfMutation

public void setIntensityOfMutation(double intensityOfMutation)

Description copied from class: ProblemDomain

Sets the parameter specifying the extent to which a mutation or ruin-recreate low level heuristic will mutate the solution. For a mutation heuristic, this could mean the range of new values that a variable can take, in relation to its current value. It could mean how many variables are changed by one call to the heuristic. For a ruin-recreate heuristic, it could mean the percentage of the solution that is destroyed and rebuilt. For example, a value of 0.5 may indicate that half the solution will be rebuilt by a RUIN_RECREATE heuristic. The meaning of this variable is intentionally vaguely stated, as it depends on the heuristic in question, and the problem domain in question.

Overrides:

setIntensityOfMutation in class ProblemDomain

Parameters:

intensityOfMutation - must be in the range 0 to 1. The initial value of 0.1 represents the default operation of the low level heuristic.

getNumberOfHeuristics

public int getNumberOfHeuristics()

Description copied from class: ProblemDomain

Gets the number of heuristics available in this problem domain

Specified by:

getNumberOfHeuristics in class ProblemDomain

Returns:

The number of heuristics available in this problem domain

applyHeuristic

public double applyHeuristic(int heuristicID,
                             int solutionSourceIndex,
                             int solutionDestinationIndex)

Description copied from class: ProblemDomain

Applies the heuristic specified by heuristicID to the solution at position solutionSourceIndex and places the resulting solution at position solutionDestinationIndex in the solution array. If the heuristic is a CROSSOVER type then the solution at solutionSourceIndex is just copied to solutionDestinationIndex.

Specified by:

applyHeuristic in class ProblemDomain

Parameters:

heuristicID - The ID of the heuristic to apply (starts at zero)

solutionSourceIndex - The index of the solution in the memory array to which to apply the heuristic

solutionDestinationIndex - The index in the memory array at which to store the resulting solution

Returns:

the objective function value of the solution created by applying the heuristic

applyHeuristic

public double applyHeuristic(int heuristicID,
                             int solutionSourceIndex1,
                             int solutionSourceIndex2,
                             int solutionDestinationIndex)

Description copied from class: ProblemDomain

Apply the heuristic specified by heuristicID to the solutions at position solutionSourceIndex1 and position solutionSourceIndex2 and put the resulting solution at position solutionDestinationIndex. The heuristic can be of any type (including CROSSOVER).

Specified by:

applyHeuristic in class ProblemDomain

Parameters:

heuristicID - the heuristic to apply (starts at zero)

solutionDestinationIndex - the position to store the resulting solutions at

Returns:

the objective function value of the new solution created by applying the heuristic

bestSolutionToString

public java.lang.String bestSolutionToString()

Description copied from class: ProblemDomain

Gets a String representation of the best solution found so far by the HyperHeuristic. This is useful if the solution needs to be printed to the screen, or saved to a file.

Specified by:

bestSolutionToString in class ProblemDomain

Returns:

A String representation of the best solution found

copySolution

public void copySolution(int source,
                         int destination)

Description copied from class: ProblemDomain

Copies a solution from one position in the solution array to another

Specified by:

copySolution in class ProblemDomain

Parameters:

source - The position of the solution to copy

destination - The position in the array to copy the solution to.

getBestSolutionValue

public double getBestSolutionValue()

Description copied from class: ProblemDomain

Returns the objective function value of the best solution found so far by the HyperHeuristic.

Specified by:

getBestSolutionValue in class ProblemDomain

Returns:

The objective function value of the best solution.

getFunctionValue

public double getFunctionValue(int solutionIndex)

Description copied from class: ProblemDomain

Gets the objective function value of the solution at index solutionIndex

Specified by:

getFunctionValue in class ProblemDomain

Parameters:

solutionIndex - The index of the solution from which the objective function is required

Returns:

A double value of the solution's objective function value.

getHeuristicsOfType

public int[] getHeuristicsOfType(ProblemDomain.HeuristicType hType)

Description copied from class: ProblemDomain

Gets an array of heuristicIDs of the type specified by heuristicType.

Specified by:

getHeuristicsOfType in class ProblemDomain

Parameters:

hType - the heuristic type.

Returns:

An array containing the indices of the heuristics of the type specified. If there are no heuristics of this type it returns null.

getHeuristicsThatUseDepthOfSearch

public int[] getHeuristicsThatUseDepthOfSearch()

Description copied from class: ProblemDomain

Gets an array of heuristicIDs that use the depthOfSearch parameter

Specified by:

getHeuristicsThatUseDepthOfSearch in class ProblemDomain

Returns:

An array containing the indexes of the heuristics that use the depthOfSearch parameter, or null if there are no heuristics of this type.

getHeuristicsThatUseIntensityOfMutation

public int[] getHeuristicsThatUseIntensityOfMutation()

Description copied from class: ProblemDomain

Gets an array of heuristicIDs that use the intensityOfMutation parameter

Specified by:

getHeuristicsThatUseIntensityOfMutation in class ProblemDomain

Returns:

An array containing the indexes of the heuristics that use the intensityOfMutation parameter, or null if there are no heuristics of this type.

getNumberOfInstances

public int getNumberOfInstances()

Description copied from class: ProblemDomain

Gets the number of instances available in this problem domain

Specified by:

getNumberOfInstances in class ProblemDomain

Returns:

the number of instances available

initialiseSolution

public void initialiseSolution(int index)

Description copied from class: ProblemDomain

Create an initial solution at a specified position in the memory array. The method of initialising the solution depends on the specific problem domain, but it is a random process, which will produce a different solution each time. The initialisation process may randomise all of the elements of the problem, or it may use a constructive heuristic with a randomised input.

Specified by:

initialiseSolution in class ProblemDomain

Parameters:

index - The index of the memory array at which the solution should be initialised.

loadInstance

public void loadInstance(int instanceID)

Description copied from class: ProblemDomain

Loads the instance specified by instanceID.

Specified by:

loadInstance in class ProblemDomain

Parameters:

instanceID - Specifies the instance to load. The ID's start at zero.

setMemorySize

public void setMemorySize(int size)

Description copied from class: ProblemDomain

Sets the size of the array where the solutions are stored. The default size is 2.

Specified by:

setMemorySize in class ProblemDomain

Parameters:

size - The new size of the solution array.

solutionToString

public java.lang.String solutionToString(int solutionIndex)

Description copied from class: ProblemDomain

Gets a String representation of a given solution in memory

Specified by:

solutionToString in class ProblemDomain

Parameters:

solutionIndex - The index of the solution of which a String representation is required

Returns:

A String representation of the solution at solutionIndex in the solution memory

toString

public java.lang.String toString()

Description copied from class: ProblemDomain

Gets the name of the problem domain. For example, "Bin Packing"

Specified by:

toString in class ProblemDomain

Returns:

the name of the ProblemDomain

compareSolutions

public boolean compareSolutions(int solutionIndex1,
                                int solutionIndex2)

Description copied from class: ProblemDomain

Compares two solutions in the memory for equality.

Specified by:

compareSolutions in class ProblemDomain

Returns:

true if the solutions are identical, false otherwise.