Package es.urjc.etsii.grafo.algorithms.scattersearch

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

java.lang.Object
es.urjc.etsii.grafo.algorithms.scattersearch.ScatterSearchBuilder<S,I>
public class ScatterSearchBuilder<S extends Solution<S,I>,I extends Instance> extends Object

  • Field Details

    • name

      protected String name
      Name of the algorithm

    • initialRatio

      protected double initialRatio
      When initializing the refset inside the Scatter Search, build (initialRatio * refSetSize) solutions, and choose from them the set of the best solutions and diverse solutions. The bigger the initialRatio, the better the initial solutions and more diverse, but it will take longer to initialize the refset and reset it if it gets stuck.

    • maxIterations

      protected int maxIterations
      Maximum number of iterations, set by default to a value near Integer.MAX_VALUE

    • refsetSize

      protected int refsetSize
      Refset size

    • diversityRatio

      protected double diversityRatio
      Proportion of items in refset to select using diversity criteria instead of a greedy or by value one. Must be in range [0, 1]

    • objective

      protected Objective<?,S extends Solution<S,I>,I extends Instance> objective
      Objective to optimize Defaults to mainObjective

    • constructiveGoodValues

      protected Constructive<S extends Solution<S,I>,I extends Instance> constructiveGoodValues
      Constructive to use to create "good value" solutions

    • constructiveDiverseValues

      protected Constructive<S extends Solution<S,I>,I extends Instance> constructiveDiverseValues
      Constructive to use when creating "diverse" solutions

    • improver

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

    • combinator

      protected SolutionCombinator<S extends Solution<S,I>,I extends Instance> combinator
      Defines how solutions are combined to create the new candidate refset

    • solutionDistance

      protected SolutionDistance<S extends Solution<S,I>,I extends Instance> solutionDistance
      How solution distance is measured, useful to calculate diversity metrics

    • softRestartEnabled

      protected boolean softRestartEnabled

  • Constructor Details

    • ScatterSearchBuilder

      public ScatterSearchBuilder()
      Create a new Scatter Search Builder. After configuring the parameters, call ref build()

  • Method Details

    • withConstructive

      public ScatterSearchBuilder<S,I> withConstructive(Constructive<S,I> constructive)
      Configure constructive method for initial refset generation. If no diverse constructive method is specified, this constructive method will be used by default to build diverse solutions
      Parameters:
      constructive - constructive method
      Returns:
      builder

    • withConstructiveForDiversity

      public ScatterSearchBuilder<S,I> withConstructiveForDiversity(Constructive<S,I> constructive)
      Configure a constructive method to use only when diverse solutions are required
      Parameters:
      constructive - constructive method
      Returns:
      builder

    • withImprover

      public ScatterSearchBuilder<S,I> withImprover(Improver<S,I> improver)
      Configure an improvement method for the Scatter Search algorithm. The improvement method, if provided, will be executed after constructing each solution.
      Parameters:
      improver - improvement method
      Returns:
      builder

    • withCombinator

      public ScatterSearchBuilder<S,I> withCombinator(SolutionCombinator<S,I> combinator)
      Configure the method used to generate a new candidate set in each Scatter Search algorithm
      Parameters:
      combinator - non null combinator method
      Returns:
      builder

    • withDistance

      public ScatterSearchBuilder<S,I> withDistance(SolutionDistance<S,I> distance)
      Configure how distance is calculated between different solutions, needed to see how diverse are the solutions.
      Parameters:
      distance - distance calculation implementation
      Returns:
      builder

    • withRefsetSize

      public ScatterSearchBuilder<S,I> withRefsetSize(int size)
      Refset size, common values are in range [10,30]
      Parameters:
      size - number of elements in refset
      Returns:
      builder

    • withDiversity

      public ScatterSearchBuilder<S,I> withDiversity(double ratio)
      Configure diversity ratio, ie, number of elements that during refset initialization will be accepted maximizing distance to existing solutions, instead of by objective function value.
      Parameters:
      ratio - double in range [0, 1]
      Returns:
      builder

    • withName

      public ScatterSearchBuilder<S,I> withName(String name)
      Configure algorithm name
      Parameters:
      name - algorithm name, must not be blank
      Returns:
      builder

    • withInitialRatio

      public ScatterSearchBuilder<S,I> withInitialRatio(double ratio)
      Optional parameter, specifies how many extra solutions to build during refset initialization When initializing the refset inside the Scatter Search, build (initialRatio * refSetSize) solutions, and choose from them the set of the best solutions and diverse solutions. The bigger the initialRatio, the better the initial solutions and more diverse, but it will take longer to initialize the refset and reset it if it gets stuck.
      Parameters:
      ratio - create ratio*initialRefset solutions to choose from for both by value and by diversity acceptance during initial refset initialization. If not configured defaults to 1.
      Returns:
      builder

    • withMaxIterations

      public ScatterSearchBuilder<S,I> withMaxIterations(int maxIterations)
      Optional parameter, specifies how many scatter search iterations to execute before stopping. Defaults to a huge number, if a TimeLimit is not configured, the algorithm will run indefinitely.
      Parameters:
      maxIterations - maximum number of iterations. Defaults to Integer.MAX_VALUE / 2 or an equivalent huge number.
      Returns:
      builder

    • withObjective

      public ScatterSearchBuilder<S,I> withObjective(Objective<?,S,I> objective)
      Set objective to optimize in ScatterSearch
      Parameters:
      objective - objective to optimize, defautls to Context::getMainObjective if not set
      Returns:
      current builder with solving mode set

    • withSoftRestart

      public ScatterSearchBuilder<S,I> withSoftRestart(boolean enabled)
      Enable or disable soft restart. If soft restart is disabled, the algorithm ends when the reference set converges, otherwise, part of the refset is discarded and new solutions are inserted. If not configured, defaults to false.
      Parameters:
      enabled - MAXIMIZING if maximizing, MINIMIZING if minimizing
      Returns:
      current builder with soft restart set.

    • build

      public ScatterSearch<S,I> build()
      Build a Scatter Search algorithm with the configured parameters of this builder
      Returns:
      New instance of Scatter Search algorithm. Same builder can generate multiple algorithm instances.