Class LocalSearchCachedBestImprovement<M extends Move<S,I> & RefreshableMove<M,S,I>, S extends Solution<S,I>, I extends Instance>

java.lang.Object

es.urjc.etsii.grafo.improve.Improver<S,I>

es.urjc.etsii.grafo.improve.ls.LocalSearch<M,S,I>

es.urjc.etsii.grafo.improve.ls.LocalSearchCachedBestImprovement<M,S,I>

Type Parameters:

M - the type of move

S - the type of problem solution

I - the type of problem instances

public class LocalSearchCachedBestImprovement<M extends Move<S,I> & RefreshableMove<M,S,I>, S extends Solution<S,I>, I extends Instance>
extends LocalSearch<M,S,I>

Cached best improvement local search.

When the cache is empty, this strategy explores the full neighborhood and stores the best cacheSize improving moves. It executes the best move immediately. In later iterations, it refreshes cached candidates one by one and executes the first refreshed candidate that still improves. If no cached candidate improves, it explores the full neighborhood again.

This is a heuristic variant of best improvement: cached candidates are ordered by their score when originally explored, and may not be the best moves after the solution changes.

Nested Class Summary

Nested classes/interfaces inherited from class Improver

Improver.NullImprover<S,I>, Improver.SequentialImprover<S,I>

Field Summary

Fields inherited from class LocalSearch

neighborhood, objective

Constructor Summary

Constructors

Constructor	Description
LocalSearchCachedBestImprovement(Neighborhood<M,S,I> neighborhood, int cacheSize)	Create a new cached best improvement local search method using the given neighborhood.
LocalSearchCachedBestImprovement(Objective<M,S,I> objective, Neighborhood<M,S,I> neighborhood, int cacheSize)	Create a new cached best improvement local search method using the given neighborhood.

Method Summary

Modifier and Type	Method	Description
M	getMove(S solution)	Get next move to execute, different strategies are possible
S	improve(S solution)	Improves a model.Solution Iterates until we run out of time, or we cannot improve the current es.urjc.etsii.grafo.solution any further

Methods inherited from class LocalSearch

improves, iteration, toString

Methods inherited from class Improver

getObjective, nul, serial, serial

Methods inherited from class Object

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

Constructor Details

LocalSearchCachedBestImprovement

@AutoconfigConstructor
public LocalSearchCachedBestImprovement(Neighborhood<M,S,I> neighborhood,
 @IntegerParam(min=1,max=1000000)
 int cacheSize)

Create a new cached best improvement local search method using the given neighborhood. Uses the method Move::getValue as the guiding function, with fMaximize = fmode.

Parameters:

neighborhood - neighborhood to use

cacheSize - number of best moves to keep after each full neighborhood exploration

LocalSearchCachedBestImprovement

public LocalSearchCachedBestImprovement(Objective<M,S,I> objective,
 Neighborhood<M,S,I> neighborhood,
 int cacheSize)

Create a new cached best improvement local search method using the given neighborhood.

Parameters:

objective - objective function to optimize

neighborhood - neighborhood to use

cacheSize - number of best moves to keep after each full neighborhood exploration

Method Details

improve

public S improve(S solution)

Description copied from class: LocalSearch

Improves a model.Solution Iterates until we run out of time, or we cannot improve the current es.urjc.etsii.grafo.solution any further

Improves a model.Solution Iterates until we run out of time, or we cannot improve the current solution any further

Overrides:

improve in class LocalSearch<M extends Move<S,I> & RefreshableMove<M,S,I>, S extends Solution<S,I>, I extends Instance>

Parameters:

solution - model.Solution to improve

Returns:

Improved s

getMove

public M getMove(S solution)

Get next move to execute, different strategies are possible

Get next move to execute.

Specified by:

getMove in class LocalSearch<M extends Move<S,I> & RefreshableMove<M,S,I>, S extends Solution<S,I>, I extends Instance>

Parameters:

solution - Solution

Returns:

Proposed move, null if there are no candidate moves in the neighborhood