BinPacking
Class BinPacking

java.lang.Object
  AbstractClasses.ProblemDomain
      BinPacking.BinPacking

public class BinPacking
extends ProblemDomain

This class implements the Bin Packing 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

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

Method Summary

double	applyHeuristic(int heuristicID, int source, int destination) 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 source1, int source2, int destination) 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 index) 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	setMemorySize(int size) Sets the size of the array where the solutions are stored.
java.lang.String	solutionToString(int index) 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, setDepthOfSearch, setIntensityOfMutation

Methods inherited from class java.lang.Object

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

Constructor Detail

BinPacking

public BinPacking(long seed)

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

Parameters:

seed - The seed for the random number generator.

Method Detail

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.

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.

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.

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 source,
                             int destination)

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)

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

destination - 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 source1,
                             int source2,
                             int destination)

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)

destination - the position to store the resulting solutions at

Returns:

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

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.

solutionToString

public java.lang.String solutionToString(int index)

Description copied from class: ProblemDomain

Gets a String representation of a given solution in memory

Specified by:

solutionToString in class ProblemDomain

Parameters:

index - 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

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

getFunctionValue

public double getFunctionValue(int index)

Description copied from class: ProblemDomain

Gets the objective function value of the solution at index solutionIndex

Specified by:

getFunctionValue in class ProblemDomain

Parameters:

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

Returns:

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

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.

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.

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

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.

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.