Class CMSA<S extends Solution<S,I>, I extends Instance, C>

java.lang.Object
es.urjc.etsii.grafo.algorithms.Algorithm<S,I>
es.urjc.etsii.grafo.algorithms.cmsa.CMSA<S,I,C>
Type Parameters:
S - Solution class
I - Instance class
C - Solution component class
public class CMSA<S extends Solution<S,I>, I extends Instance, C> extends Algorithm<S,I>
CMSA (Construct, Merge, Solve and Adapt) is a hybrid metaheuristic that combines a probabilistic constructive heuristic with an exact method. Instead of applying the exact method to the whole problem instance, which is usually intractable, CMSA repeatedly restricts the search to a small, promising subset of solution components (edges, assignments, items, etc.), and solves that much smaller sub-instance to optimality (or as close to optimality as possible) at every iteration.

Algorithmic outline: 

Csub = {} // sub-instance: solution components with a chance of being part of a good solution
Sbest = null
repeat until stopping criterion is met:
    // Construct & Merge
    for na times:
        S' = ProbabilisticConstruct(instance) // CMSAConstructive
        Csub = Csub U usedComponents(S')       // merge new components into the sub-instance, age = 0
    // Solve
    S* = Solve(instance restricted to Csub)    // CMSASolver
    if S* is better than Sbest: Sbest = S*
    // Adapt
    for each component c in Csub:
        if c in S*: age(c) = 0
        else: age(c) = age(c) + 1
              if age(c) > ageMax: Csub = Csub \ {c}
return Sbest
Components that keep being selected by the exact method stay in Csub indefinitely (their age is reset to 0), while components that are no longer useful eventually age out and are dropped, keeping the sub-instance small across iterations. This is what makes CMSA different from just repeatedly solving a new random restricted sub-instance from scratch: the sub-instance progressively adapts towards the components that matter.

For further information about CMSA see: Blum, C., Pinacho, P., López-Ibáñez, M., & Lozano, J. A. (2016). Construct, Merge, Solve and Adapt: A new algorithm for combinatorial optimization. Computers & Operations Research, 68, 75-88. ...

For an in-depth treatment of CMSA, including guidance on modelling the sub-instance solved at every iteration for different combinatorial optimization problems, see: Blum, C. (2024). Construct, Merge, Solve & Adapt: A Hybrid Metaheuristic for Combinatorial Optimization. Computational Intelligence Methods and Applications. Springer. ...

  • Constructor Details

    • CMSA

      @AutoconfigConstructor public CMSA(@ProvidedParam String name, @ProvidedParam Objective<?,S,I> objective, CMSAConstructive<S,I,C> constructive, CMSASolver<S,I,C> solver, @IntegerParam(min=1,max=1000) int solutionsPerIteration, @IntegerParam(min=0,max=100) int ageMax, @IntegerParam(min=1,max=60000) long solverTimeLimitInMillis, @IntegerParam(min=0,max=1000000) int maxIterations)
      Full CMSA 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()
      objective - objective function to optimize
      constructive - probabilistic constructive procedure used to sample solution components
      solver - exact (or near-exact) method used to solve the restricted sub-instance
      solutionsPerIteration - number of solutions constructed at each iteration before calling the solver, usually denoted na
      ageMax - maximum age a solution component can reach before being removed from the sub-instance
      solverTimeLimitInMillis - maximum time budget, in milliseconds, given to the solver at each iteration
      maxIterations - maximum number of iterations, use a value smaller or equal to zero to only rely on the global time limit

  • Method Details