Package es.urjc.etsii.grafo.algorithms

Class IteratedGreedy<S extends Solution<S,I>,I extends Instance>

java.lang.Object

es.urjc.etsii.grafo.algorithms.Algorithm<S,I>

es.urjc.etsii.grafo.algorithms.IteratedGreedy<S,I>

Type Parameters:

S - the type of the problem solution

I - the type of problem instances

public class IteratedGreedy<S extends Solution<S,I>,I extends Instance>
extends Algorithm<S,I>

Iterated greedy is a search method that iterates through applications of construction heuristics using the repeated execution of two main phases, the partial destruction of a complete candidate solution and a subsequent reconstruction of a complete candidate solution.

Algorithmic outline of the simplest version of Iterated Greedy (IG)

s = GenerateInitialSolution do { s' = Destruction(s) s'' = Reconstruction (s'') s = AcceptanceCriterion(s,s'') } while (Termination criteria is not met) return s

Iterated greedy algorithms natural extension is to improve the generated solutions by the application of an improvement algorithm, such as local search procedures.

Algorithmic outline of an IG with an additional local search step

For further information about Iterated Greedy Algorithms see: Stützle T., Ruiz R. (2018) Iterated Greedy. In: Martí R., Pardalos P., Resende M. (eds) Handbook of Heuristics. Springer, Cham. ...

Constructor Summary

Constructors

Constructor	Description
IteratedGreedy(String name, int maxIterations, int stopIfNotImprovedIn, Constructive<S,I> constructive, Destructive<S,I> destructive, Reconstructive<S,I> reconstructive, Improver<S,I> improver)	Iterated Greedy Algorithm constructor: uses one constructive method when building the initial solution and another one when reconstructing
IteratedGreedy(String name, int maxIterations, int stopIfNotImprovedIn, Constructive<S,I> constructive, Shake<S,I> destructionReconstruction, Improver<S,I> improver)
IteratedGreedy(String name, int maxIterations, int stopIfNotImprovedIn, Reconstructive<S,I> constructive, Destructive<S,I> destructive, Improver<S,I> improver)	Iterated Greedy Algorithm constructor: uses same constructive method when building the initial solution and after the destructive.
IteratedGreedy(String name, Objective<?,S,I> objective, int maxIterations, int stopIfNotImprovedIn, Constructive<S,I> constructive, Shake<S,I> destructionReconstruction, Improver<S,I> improver)	Iterated Greedy Algorithm constructor

Method Summary

Modifier and Type	Method	Description
S	algorithm(I instance)	Runs the algorithm
String	toString()

Methods inherited from class es.urjc.etsii.grafo.algorithms.Algorithm

getBuilder, getName, newSolution, setBuilder, setName

Methods inherited from class java.lang.Object

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

Constructor Details

IteratedGreedy

public IteratedGreedy(String name,
 Objective<?,S,I> objective,
 int maxIterations,
 int stopIfNotImprovedIn,
 Constructive<S,I> constructive,
 Shake<S,I> destructionReconstruction,
 Improver<S,I> improver)

Iterated Greedy Algorithm constructor

Parameters:

name - Algorithm name, uniquely identifies the current algorithm. Tip: If you dont care about the name, generate a random one using StringUtil.randomAlgorithmName()

maxIterations - maximum number of iterations the algorithm could be executed.

stopIfNotImprovedIn - maximum number of iterations without improving the algorithm could be executed.

constructive - constructive procedure to generate the initial solution of the algorithm

destructionReconstruction - destruction and reconstruction procedures

improver - improving procedures. Could be 0 or more.

IteratedGreedy

@AutoconfigConstructor
public IteratedGreedy(@ProvidedParam
 String name,
 @IntegerParam(min=0,max=1000000)
 int maxIterations,
 @IntegerParam(min=1,max=1000000)
 int stopIfNotImprovedIn,
 Constructive<S,I> constructive,
 Shake<S,I> destructionReconstruction,
 Improver<S,I> improver)

IteratedGreedy

public IteratedGreedy(String name,
 int maxIterations,
 int stopIfNotImprovedIn,
 Reconstructive<S,I> constructive,
 Destructive<S,I> destructive,
 Improver<S,I> improver)

Iterated Greedy Algorithm constructor: uses same constructive method when building the initial solution and after the destructive.

Parameters:

name - Algorithm name, uniquely identifies the current algorithm. Tip: If you dont care about the name, generate a random one using StringUtil.randomAlgorithmName()

maxIterations - maximum number of iterations the algorithm could be executed.

stopIfNotImprovedIn - maximum number of iterations without improving the algorithm could be executed.

constructive - constructive procedure to generate the initial solution of the algorithm, and rebuild the solution after the destructive method

destructive - destructive method called before the reconstructive

improver - improving procedures. Could be 0 or more.

IteratedGreedy

public IteratedGreedy(String name,
 int maxIterations,
 int stopIfNotImprovedIn,
 Constructive<S,I> constructive,
 Destructive<S,I> destructive,
 Reconstructive<S,I> reconstructive,
 Improver<S,I> improver)

Iterated Greedy Algorithm constructor: uses one constructive method when building the initial solution and another one when reconstructing

Parameters:

name - Algorithm name, uniquely identifies the current algorithm. Tip: If you dont care about the name, generate a random one using StringUtil.randomAlgorithmName()

maxIterations - maximum number of iterations the algorithm could be executed.

stopIfNotImprovedIn - maximum number of iterations without improving the algorithm could be executed.

constructive - constructive procedure to generate the initial solution of the algorithm, solution is NOT rebuilt using this component

destructive - destructive method called before the reconstructive

reconstructive - reconstructive procedure to rebuild the solution. Initial solution is NOT built using this method.

improver - improving procedures. Could be 0 or more.

Method Details

algorithm

public S algorithm(I instance)

Runs the algorithm Iterated greedy algorithm procedure

Specified by:

algorithm in class Algorithm<S extends Solution<S,I>,I extends Instance>

Parameters:

instance - Instance to solve

Returns:

Built solution

toString

public String toString()

Overrides:

toString in class Algorithm<S extends Solution<S,I>,I extends Instance>