Package es.urjc.etsii.grafo.algorithms.vns

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

java.lang.Object

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

es.urjc.etsii.grafo.algorithms.vns.VNS<S,I>

Type Parameters:

S - type of the problem solution

I - type of the problem instance

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

Variable neighborhood search (VNS) is a metaheuristic for solving combinatorial and global optimization problems. Its basic idea is the systematic change of neighborhood both in a descent phase to find a local optimum and in a perturbation phase to exit the corresponding local optimum

Algorithmic outline one of the simplest versions of VNS

 s = GenerateInitialSolution
 while (Termination criteria is not met){
      k = 1
      while (k != kmax){
          s' = Shake(s,k)
          s'' = Improve (s')
          NeighborhoodChange(s,s'',k)
      }
 }
 

More information can be found in: Hansen P., Mladenović N. (2018) Variable Neighborhood Search. In: Martí R., Pardalos P., Resende M. (eds) Handbook of Heuristics. Springer, Cham. ...

Field Summary

Fields

Modifier and Type	Field	Description
protected Constructive<S,I>	constructive	Constructive procedure
protected Improver<S,I>	improver
protected VNSNeighChange<S,I>	neighChange	Calculates K value for each VNS step.
protected Objective<?,S,I>	objective	Objective function to optimize
protected Shake<S,I>	shake	Shake procedure

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	VNS(String algorithmName, int maxK, Constructive<S,I> constructive, Shake<S,I> shake, Improver<S,I> improver)	VNS with default KMapper, which starts at 0 and increments by 1 each time the solution does not improve.
	VNS(String algorithmName, Objective<?,S,I> objective, VNSNeighChange<S,I> neighChange, Constructive<S,I> constructive, Shake<S,I> shake, Improver<S,I> improver)	Execute VNS until finished

Method Summary

Modifier and Type	Method	Description
S	algorithm(I instance)	VNS 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

Field Details

improver

protected Improver<S extends Solution<S,I>,I extends Instance> improver

constructive

protected Constructive<S extends Solution<S,I>,I extends Instance> constructive

Constructive procedure

shake

protected Shake<S extends Solution<S,I>,I extends Instance> shake

Shake procedure

neighChange

protected VNSNeighChange<S extends Solution<S,I>,I extends Instance> neighChange

Calculates K value for each VNS step.

objective

protected Objective<?,S extends Solution<S,I>,I extends Instance> objective

Objective function to optimize

Constructor Details

VNS

@AutoconfigConstructor
protected VNS(@ProvidedParam
 String algorithmName,
 @IntegerParam(min=1,max=100)
 int maxK,
 Constructive<S,I> constructive,
 Shake<S,I> shake,
 Improver<S,I> improver)

VNS with default KMapper, which starts at 0 and increments by 1 each time the solution does not improve. Stops when k >= 5. Behaviour can be customized passing a custom kMapper, such as:

 
 (solution, originalK) -> originalK >= 10 ? KMapper.STOPNOW : originalK
 
 

Parameters:

algorithmName - Algorithm name, example "VNS1-GRASP". Uniquely identifies the current algorithm. Tip: If you dont care about the name, generate a random one using StringUtil.randomAlgorithmName()

constructive - Constructive method

shake - Perturbation method

improver - List of improvers/local searches

VNS

public VNS(String algorithmName,
 Objective<?,S,I> objective,
 VNSNeighChange<S,I> neighChange,
 Constructive<S,I> constructive,
 Shake<S,I> shake,
 Improver<S,I> improver)

Execute VNS until finished

Parameters:

algorithmName - Algorithm name, example: "VNSWithRandomConstructive"

objective - function to optimize

neighChange - k value provider, @see VNS.KMapper

constructive - Constructive method

shake - Perturbation method

improver - List of improvers/local searches

Method Details

algorithm

public S algorithm(I instance)

VNS algorithm. This procedure follows this schema:

     s = GenerateInitial solution
     k = 1
     while (k != kmax){
     s' = Shake(s,k)
     s'' = Improve (s')
     NeighborhoodChange(s,s'',k)
     }
 

To run the VNS procedure multiples time consider use MultiStart algorithm class

Specified by:

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

Parameters:

instance - Instance to solve

Returns:

best solution found when the VNS procedure ends

toString

public String toString()

Overrides:

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