Heuristic

public interface Heuristic<S extends HeuristicSolution<?>>

Provides the methods to be used for implementation of heuristics to find solution for complex problems where the solution space to search is large. These problems are usually NP-Hard ones which the time to find a solution increases, for instance, in exponential time. Such problems can be, for instance, mapping a set of VMs to existing Hosts or mapping a set of Cloudlets to VMs. A heuristic implementation thus provides an approximation of an optimal solution (a suboptimal solution).

Different heuristic can be implemented, such as Tabu search, Simulated annealing, Hill climbing or Ant colony optimization, to name a few.

Author:

Manoel Campos da Silva Filho

Parameters:

Fields

NULL

Heuristic NULL

A property that implements the Null Object Design Pattern for Heuristic objects.

Methods

createNeighbor

S createNeighbor(S source)

Creates a neighbor solution cloning a source one and randomly changing some of its values. A neighbor solution is one that is close to the current solution and has just little changes.

Parameters:
  • source – the source to create a neighbor solution
Returns:

the cloned and randomly changed solution that represents a neighbor solution

getAcceptanceProbability

double getAcceptanceProbability()

Computes the acceptance probability to define if a neighbor solution has to be accepted or not, compared to the getBestSolutionSoFar().

Returns:the acceptance probability, in scale from [0 to 1] where 0 is to maintain the current solution, 1 is to accept the neighbor solution, while intermediate values defines the probability that the neighbor solution will be randomly accepted.

getBestSolutionSoFar

S getBestSolutionSoFar()
Returns:best solution found out up to now

getInitialSolution

S getInitialSolution()

Gets the initial solution that the heuristic will start from in order to try to improve it. If not initial solution was generated yet, one should be randomly generated.

Returns:the initial randomly generated solution

getNeighborSolution

S getNeighborSolution()
Returns:latest neighbor solution created

See also: .createNeighbor(HeuristicSolution)

getNeighborhoodSearchesByIteration

int getNeighborhoodSearchesByIteration()
Returns:the number of times a neighbor solution will be searched at each iteration of the solution find.

getRandomValue

int getRandomValue(int maxValue)

Gets a random number between 0 (inclusive) and maxValue (exclusive).

Parameters:
  • maxValue – the max value to get a random number (exclusive)
Returns:

the random number

getSolveTime

double getSolveTime()
Returns:the time taken to finish the solution search (in seconds).

See also: .solve()

isToStopSearch

boolean isToStopSearch()

Checks if the solution search can be stopped.

Returns:true if the solution search can be stopped, false otherwise.

setNeighborhoodSearchesByIteration

void setNeighborhoodSearchesByIteration(int numberOfNeighborhoodSearches)

Sets the number of times a neighbor solution will be searched at each iteration of the solution find.

Parameters:
  • numberOfNeighborhoodSearches – number of neighbor searches to perform at each iteration

solve

S solve()

Starts the heuristic to find a suboptimal solution. After the method finishes, you can call the getBestSolutionSoFar() to get the final solution.

Returns:the final solution

See also: .getBestSolutionSoFar()