AbstractClasses
Class ProblemDomain

java.lang.Object
  AbstractClasses.ProblemDomain

Direct Known Subclasses:

BinPacking, FlowShop, PersonnelScheduling, SAT

public abstract class ProblemDomain
extends java.lang.Object

Problem domain is an abstract class containing methods for applying heuristics and managing solutions. These methods are used by a hyper-heuristic in order to progress the search. Sub-classes of ProblemDomain provide the representations of the various problem domains for the competition.

Author:

Antonio Vázquez, Matthew Hyde, Gabriela Ochoa, Tim Curtois. [jav,mvh,gxo,tec]@cs.nott.ac.uk

Nested Class Summary

static class

ProblemDomain.HeuristicType An enumeration of the different types of low-level heuristics implemented in the software.

Field Summary

protected double	depthOfSearch A parameter specifying the extent to which a local search heuristic will modify the solution.
protected int[]	heuristicCallRecord A record of the number of times that each low level heuristic has been called.
protected int[]	heuristicCallTimeRecord A record of the length of time that each low level heuristic has been running for.
protected double	intensityOfMutation A parameter specifying the extent to which a mutation or ruin-recreate low level heuristic will mutate the solution.
protected java.util.Random	rng The random number generator used by the problem domain object.

Constructor Summary

ProblemDomain(long seed)
Creates a new problem domain and creates a new random number generator using the seed provided.

Method Summary

abstract 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.
abstract 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.
abstract java.lang.String	bestSolutionToString() Gets a String representation of the best solution found so far by the HyperHeuristic.
abstract boolean	compareSolutions(int solutionIndex1, int solutionIndex2) Compares the two solutions on their structure (i.e. in the solution space, not in the objective/fitness function space).
abstract void	copySolution(int solutionSourceIndex, int solutionDestinationIndex) Copies a solution from one position in the solution array to another
abstract double	getBestSolutionValue() Returns the objective function value of the best solution found so far by the HyperHeuristic.
double	getDepthOfSearch() Gets the current value of the "depth of search" parameter.
abstract double	getFunctionValue(int solutionIndex) Gets the objective function value of the solution at index solutionIndex
int[]	getHeuristicCallRecord() Shows how many times each low level heuristic has been called.
int[]	getheuristicCallTimeRecord() Shows the total time that each low level heuristic has been operating on the problem.
abstract int[]	getHeuristicsOfType(ProblemDomain.HeuristicType heuristicType) Gets an array of heuristicIDs of the type specified by heuristicType.
abstract int[]	getHeuristicsThatUseDepthOfSearch() Gets an array of heuristicIDs that use the depthOfSearch parameter
abstract int[]	getHeuristicsThatUseIntensityOfMutation() Gets an array of heuristicIDs that use the intensityOfMutation parameter
double	getIntensityOfMutation() Gets the current intensity of mutation parameter.
abstract int	getNumberOfHeuristics() Gets the number of heuristics available in this problem domain
abstract int	getNumberOfInstances() Gets the number of instances available in this problem domain
abstract void	initialiseSolution(int index) Create an initial solution at a specified position in the memory array.
abstract 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.
abstract void	setMemorySize(int size) Sets the size of the array where the solutions are stored.
abstract java.lang.String	solutionToString(int solutionIndex) Gets a String representation of a given solution in memory
abstract java.lang.String	toString() Gets the name of the problem domain.

Methods inherited from class java.lang.Object

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

Field Detail

rng

protected java.util.Random rng

The random number generator used by the problem domain object. It is initialised in the constructor.

depthOfSearch

protected double depthOfSearch

A parameter specifying the extent to which a local search heuristic will modify the solution. It could mean the size of the neighbourhood that is sampled by the heuristic, or the length of time that a low level heuristic runs for in order to improve the solution. The meaning of this variable is intentionally vaguely stated, as it depends on the heuristic in question, and the problem domain in question.

intensityOfMutation

protected double intensityOfMutation

A 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. The meaning of this variable is intentionally vaguely stated, as it depends on the heuristic in question, and the problem domain in question.

heuristicCallRecord

protected int[] heuristicCallRecord

A record of the number of times that each low level heuristic has been called. Can be retrieved by a HyperHeuristic object by calling the getHeuristicCallRecord() method of this class.

heuristicCallTimeRecord

protected int[] heuristicCallTimeRecord

A record of the length of time that each low level heuristic has been running for. Can be retrieved by a HyperHeuristic object by calling the getHeuristicCallTimeRecord() method of this class.

Constructor Detail

ProblemDomain

public ProblemDomain(long seed)

Creates a new problem domain and creates a new random number generator using the seed provided. If the seed takes the value -1, the seed is generated taking the current System time. The random number generator is used for all stochastic operations, so the problem will be initialised in the same way if the seed is the same. Sets the solution memory size to 2.

Parameters:

seed - a random seed

Method Detail

getHeuristicCallRecord

public int[] getHeuristicCallRecord()

Shows how many times each low level heuristic has been called.

Returns:

an int[] which contains an integer value for each low level heuristic, representing the number of times that heuristic has been called by the HyperHeuristic object.

getheuristicCallTimeRecord

public int[] getheuristicCallTimeRecord()

Shows the total time that each low level heuristic has been operating on the problem.

Returns:

an int[] which contains an integer value representing the total number of milliseconds used by each low level heuristic.

setDepthOfSearch

public void setDepthOfSearch(double depthOfSearch)

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.

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)

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.

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.

getDepthOfSearch

public double getDepthOfSearch()

Gets the current value of the "depth of search" parameter.

Returns:

The current value of the depth of search parameter.

getIntensityOfMutation

public double getIntensityOfMutation()

Gets the current intensity of mutation parameter.

Returns:

the current value of the intensity of mutation parameter.

getHeuristicsOfType

public abstract int[] getHeuristicsOfType(ProblemDomain.HeuristicType heuristicType)

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

Parameters:

heuristicType - 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.

getHeuristicsThatUseIntensityOfMutation

public abstract int[] getHeuristicsThatUseIntensityOfMutation()

Gets an array of heuristicIDs that use the intensityOfMutation parameter

Returns:

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

getHeuristicsThatUseDepthOfSearch

public abstract int[] getHeuristicsThatUseDepthOfSearch()

Gets an array of heuristicIDs that use the depthOfSearch parameter

Returns:

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

loadInstance

public abstract void loadInstance(int instanceID)

Loads the instance specified by instanceID.

Parameters:

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

setMemorySize

public abstract void setMemorySize(int size)

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

Parameters:

size - The new size of the solution array.

initialiseSolution

public abstract void initialiseSolution(int index)

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.

Parameters:

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

getNumberOfHeuristics

public abstract int getNumberOfHeuristics()

Gets the number of heuristics available in this problem domain

Returns:

The number of heuristics available in this problem domain

applyHeuristic

public abstract 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. If the heuristic is a CROSSOVER type then the solution at solutionSourceIndex is just copied to solutionDestinationIndex.

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 abstract 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. The heuristic can be of any type (including CROSSOVER).

Parameters:

heuristicID - the heuristic to apply (starts at zero)

solutionSourceIndex1 -

solutionSourceIndex2 -

solutionDestinationIndex - the position to store the resulting solutions at

Returns:

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

copySolution

public abstract void copySolution(int solutionSourceIndex,
                                  int solutionDestinationIndex)

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

Parameters:

solutionSourceIndex - The position of the solution to copy

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

toString

public abstract java.lang.String toString()

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

Overrides:

toString in class java.lang.Object

Returns:

the name of the ProblemDomain

getNumberOfInstances

public abstract int getNumberOfInstances()

Gets the number of instances available in this problem domain

Returns:

the number of instances available

bestSolutionToString

public abstract java.lang.String bestSolutionToString()

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.

Returns:

A String representation of the best solution found

getBestSolutionValue

public abstract double getBestSolutionValue()

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

Returns:

The objective function value of the best solution.

solutionToString

public abstract java.lang.String solutionToString(int solutionIndex)

Gets a String representation of a given solution in memory

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

getFunctionValue

public abstract double getFunctionValue(int solutionIndex)

Gets the objective function value of the solution at index solutionIndex

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.

compareSolutions

public abstract boolean compareSolutions(int solutionIndex1,
                                         int solutionIndex2)

Compares the two solutions on their structure (i.e. in the solution space, not in the objective/fitness function space).

Parameters:

solutionIndex1 -

solutionIndex2 -

Returns:

true if the solutions are identical, false otherwise.