Scatter Search for the MDP — Implementation

Introduction

This chapter is devoted to presenting different aspects related to the implementation stage for solving an optimization problem. To illustrate this discussion, we describe the Java implementation of the improved scatter search algorithm for the Maximum Diversity Problem (presented in the previous chapter). The first section is devoted to the design of the application, showing the responsibilities of each class and the relationships between them. The next section describes the implementation details considered most interesting.

The complete, runnable source code is available in this repository under problems/no-framework/MDP. The implementation targets Java 25 and uses modern language features such as records, switch expressions and var. Only a selection of classes is reproduced here; every class name is a link to its source file so the rest can be consulted directly.

Design

The diagram below shows the main classes of the application and the relationships between them. Their responsibilities are described afterwards.

classDiagram
    direction LR

    class Experiment
    class ExperimentManager
    class InstancesManager
    class InstanceFile {
        <<record>>
        +loadInstance() Instance
    }
    class Instance
    class Node
    class Solution {
        +getWeight() double
        +changeNode(old, new)
        +addNode(n)
        +removeNode(n)
    }
    class OptimizationAlgorithm {
        <<interface>>
        +createSolution(timeout) Solution
    }
    class ScatterSearch
    class SSConfig {
        <<enumeration>>
        WITHOUT_INF
        WITH_INF
        WITH_MEMORY
    }
    class Constructive {
        <<abstract>>
    }
    class RandomConstructive
    class GraspD2Constructive
    class TabuD2Constructive
    class Combinator {
        <<abstract>>
    }
    class RandomCombinator
    class D2Combinator
    class TabuD2Combinator
    class Diversificator {
        <<abstract>>
    }
    class NotUsedNodesDiv
    class ImprovementMethod {
        <<abstract>>
    }
    class LocalSearch
    class ImprovedLocalSearch
    class LocalSearchTabuSearch
    class TabuD2Calculator
    class BoundedSortedList~T~
    class Combinations
    class Weighted~E~

    OptimizationAlgorithm <|.. ScatterSearch
    OptimizationAlgorithm <|.. Constructive
    Constructive <|-- RandomConstructive
    Constructive <|-- GraspD2Constructive
    Constructive <|-- TabuD2Constructive
    Combinator <|-- RandomCombinator
    Combinator <|-- D2Combinator
    Combinator <|-- TabuD2Combinator
    Diversificator <|-- NotUsedNodesDiv
    ImprovementMethod <|-- LocalSearch
    ImprovementMethod <|-- ImprovedLocalSearch
    ImprovementMethod <|-- LocalSearchTabuSearch

    ScatterSearch --> SSConfig : configured by
    ScatterSearch ..> Constructive : builds with
    ScatterSearch ..> Combinator : combines with
    ScatterSearch ..> Diversificator : diversifies with
    ScatterSearch ..> ImprovementMethod : improves with
    ScatterSearch *-- BoundedSortedList : RefSet
    ScatterSearch --> Combinations : subset groups
    ScatterSearch ..> Solution : returns
    TabuD2Constructive ..> TabuD2Calculator : shares memory
    TabuD2Combinator ..> TabuD2Calculator : shares memory

    Experiment ..> InstancesManager : reads instances
    Experiment ..> OptimizationAlgorithm : runs configs
    Experiment ..> ExperimentManager : records solutions
    InstancesManager "1" o-- "*" InstanceFile : registers
    InstanceFile ..> Instance : loadInstance()
    Instance "1" o-- "*" Node
    Solution --> Instance
    Solution "1" o-- "*" Node : selected
    Solution ..> Weighted : contributions
    ExperimentManager ..> Solution : saves + reports

Figure 1. Class diagram of the Scatter Search metaheuristic applied to the MDP.

Problem data — package `ssmdp.instance`

Instance: the in-memory representation of a problem instance. It holds the pairwise distance matrix, the list of Nodes and the number m of elements a solution must select. It exposes the distance between two elements (getWeight(i, j)), the node list, m (getNumSolutionNodes()), and lazily builds the per-node distance contributions (getNodesDistance()). It replaces the MDPGraph class from the book.
Node: an element of an Instance. It stores its index and a reference to its owning instance, and asks that instance for the distance to another node (getDistanceTo). The same Node objects are shared by the instance and by the Solutions that select them.
InstanceFile: a lightweight record (file name, display name and type) that lazily loads an Instance from a classpath resource through loadInstance(). It replaces the book's MDPInstance.
InstancesManager: holds the registered list of available InstanceFiles and lets callers query them all, by type, by index, by range, or by file name. It replaces the book's MDPInstancesManager.
FormatException: a checked exception signalling a malformed instance file.

The scatter search — package `ssmdp.algorithm`

OptimizationAlgorithm: the common interface implemented by anything that can produce a Solution within a time budget — createSolution(long millisTimeout). Both ScatterSearch and Constructive implement it, so Experiment can run them uniformly.
Solution: objects of this class represent the candidate solutions handled throughout the metaheuristic's execution. It provides methods to add, remove and change nodes of the solution. To represent the solution, two synchronized data structures are used. On the one hand, there is a boolean array called nodesPresence, where each position encodes whether that node belongs to the solution; an array is very appropriate here because it allows direct access to its components. On the other hand, there is a list called nodes that holds the nodes present in the solution, which lets us traverse the selected nodes in time proportional to their number and add/remove them more efficiently than in an array. Finally, another list called nodesDistance stores, for each node in the solution, the sum of the distances from that node to the rest of the nodes included in the solution (as Weighted<Node> pairs). This structure makes recomputing the weight of the solution more efficient, since the contribution of each node can be factored out — for example, if a node is removed, the new weight is the previous weight minus the removed node's contribution. When nodesDistance is used, the nodes structure becomes unnecessary, since its information is contained in nodesDistance. The class also implements Comparable<Solution> (by weight) and Iterable<Node>, keeps its position inside the RefSet, and offers calculatePreciseWeight() to recompute the objective value exactly. It replaces the book's MDPSolution.
ScatterSearch: represents the SS algorithm applied to the MDP. Its nested SSConfig enum (WITHOUT_INF, WITH_INF, WITH_MEMORY) selects one of the three configurations by wiring together a Constructive, a Combinator and an ImprovementMethod. It replaces the book's MDPScatterSearch.
Diverse-solution generation — package constructive: each constructive method is a subclass of Constructive (which is itself an OptimizationAlgorithm). The random constructive is RandomConstructive, the GRASP_D-2 constructive is GraspD2Constructive, and the Tabu_D-2 constructive is TabuD2Constructive.
Combination — package combinator: each combination method is a subclass of Combinator. The random method is RandomCombinator, the D-2 method is D2Combinator, and the Tabu_D-2 method is TabuD2Combinator.
Diversification — package diversificator: a single diversification algorithm is implemented, NotUsedNodesDiv, a subclass of Diversificator. It selects solutions by diversity, computing the distance between solutions. This design makes it possible to experiment with other selection methods simply by creating a new subclass of Diversificator.
Improvement — package improvement: each improvement method is a subclass of ImprovementMethod. The best-improvement local search (LS) is LocalSearch, the improved (first-improvement) local search (I_LS) is ImprovedLocalSearch, and the local search tabu search (LS_TS) is LocalSearchTabuSearch. (This class was named LocalSeachTabuSearch in the book; the typo has been corrected.) The name ImprovementMethod replaces the book's ImprovingMethod.
TabuD2Calculator (package tabud2): the adaptive memory (per-element frequency and average quality) shared by TabuD2Constructive and TabuD2Combinator in the memory configuration.

Utilities — package `ssmdp.util`

BoundedSortedList<T>: implements the RefSet itself — a size-bounded list kept sorted in descending order that drops the worst element when it overflows and rejects duplicates.
Weighted<E>: an (element, weight) pair with static min/max helpers; used to associate a Node with its distance contribution.
Combinations: generates the subsets of RefSet positions to be combined, and can return only the groups that contain a given set of indexes (so that only combinations involving new solutions are recomputed).
RandomList<T>: an Iterable that traverses a collection in random order (used by RandomConstructive).
RotateListView<T>: an Iterable that traverses a list starting from a rotating offset (used by LocalSearchTabuSearch).
WeightedIterator<E>: adapts an Iterator<Weighted<E>> into an Iterator<E>, letting a Solution iterate over its nodes even when it internally stores Weighted<Node> contributions.

Entry point — package `ssmdp`

Experiment: the main program. It loads instances through InstancesManager, runs a plain RandomConstructive plus the three ScatterSearch configurations on each instance under a fixed time budget (TIMEOUT_MILLIS, currently 2 seconds per run), and hands each resulting Solution to the ExperimentManager.
ExperimentManager: collects the results, computes statistics (the mean percentage deviation from the best solution found and the number of instances where each method reached that best value), prints a comparison table to the console, and saves each run under experiments/<datetime>/ — one file per instance and algorithm plus an HTML report (report.html).

Improved Scatter Search Algorithm

The behavior of ScatterSearch follows the two pseudocodes below, which constitute an advanced implementation of the original SS algorithm. In the code, the parameters of Algorithm 2 are fixed constants: N = 100 initial solutions (NUM_INITIAL_SOLUTIONS), the RefSet size b = 10 (NUM_BEST_SOLUTIONS = 5 plus NUM_DIVERSE_SOLUTIONS = 5), SubsetSize = 2, and the objective f is the weight of a Solution. The correspondence between the pseudocode and the code is:

Pseudocode	Implementation
`SS(...)`	`ScatterSearch.createSolution(millisTimeout)`
`createSolutions`	`Constructive.createSolutions`
`improveAndRefreshRefSet`	`ScatterSearch.improveAndRefreshRefSet` (Algorithm 3)
`getDiversity`	`Diversificator.getDiverseSolutions`
`GenerateGroups` / `Combine`	`Combinations.getGroups` + `Combinator.combineGroups`

Algorithm 2 uses the following local variables: InitialSolutions, NewSolutions (arrays $[1 \ldots N]$ of Solution); RefSet (array $[1 \ldots b]$ of Solution); RefSetCombinations (array $[1 \ldots M]$ of Solution); P (array $[1 \ldots M,\ 1 \ldots SubsetSize]$ of Solution); i (integer); ImprovedSolutions (a hash table); and terminationCondition (boolean).

$$ \begin{aligned} &{RefSet[1] : \text{Solution}} = \text{SS}(N,\ b,\ SubsetSize : \text{integer};\ f : \text{ObjectiveFunctionType}) \[4pt] &InitialSolutions := \text{createSolutions}(N) \\ &RefSet := [,,] \\ &\quad \triangleright\ \text{Improve } InitialSolutions \text{ and initialize } RefSet \text{ with the } b/2 \text{ best solutions} \\ &{InitialSolutions,, RefSet} := \text{improveAndRefreshRefSet}(InitialSolutions,, RefSet,, b/2,, f) \\ &\quad \triangleright\ \text{Complete } RefSet \text{ with the } b/2 \text{ solutions most different from those already in it} \\ &RefSet := \text{getDiversity}(RefSet,, InitialSolutions,, b/2,, f) \\ &P := \text{GenerateGroups}(SubsetSize,, RefSet) \\ &RefSetCombinations := \text{Combine}(P) \\ &\textbf{while } \text{not}(terminationCondition)\ \textbf{do} \\ &\quad \textbf{repeat} \\ &\qquad RefSetOld := RefSet \\ &\qquad RefSet := \text{improveAndRefreshRefSet}(RefSetCombinations,, RefSet,, b,, f) \\ &\qquad \triangleright\ \text{Build groups from } RefSet \text{ except those already built with } RefSetOld \\ &\qquad P := \text{GenerateGroups}(SubsetSize,, RefSet,, RefSetOld) \\ &\qquad RefSetCombinations := \text{Combine}(P) \\ &\quad \textbf{until } RefSetOld = RefSet \\ &\quad RefSet := RefSet[1 : b/2] \\ &\quad NewSolutions := \text{createSolutions}(N) \\ &\quad RefSet := \text{getDiversity}(RefSet,, InitialSolutions,, b/2,, f) \\ &\quad P := \text{GenerateGroups}(SubsetSize,, RefSet) \\ &\quad RefSetCombinations := \text{Combine}(P) \\ &\textbf{end while} \end{aligned} $$

Algorithm 2. Improved Scatter Search.

Algorithm 3 uses the following local variables: i (integer); and original, improvedSolution (Solution). In the code, the bounded, keep-best bookkeeping of the RefSet (the f(improvedSolution) > f(RefSet[b]) test and the update) is delegated to BoundedSortedList.add.

$$ \begin{aligned} &{Solutions,, RefSet} = \text{improveAndRefreshRefSet}(Solutions,, RefSet,, NElem : \text{integer};\ f;\ ImprovedSolutions) \[4pt] &\textbf{for } i := 1 \textbf{ to } \text{length}(Solutions)\ \textbf{do} \\ &\quad \textbf{if } \langle ImprovedSolutions \text{ does not contain } Solutions[i] \rangle\ \textbf{then} \\ &\qquad original := Solutions[i] \\ &\qquad Solutions[i] := \text{improveSolution}(original) \\ &\qquad improvedSolution := Solutions[i] \\ &\qquad \langle \text{associate } original \text{ with } Solutions[i] \text{ in } ImprovedSolutions \rangle \\ &\quad \textbf{else} \\ &\qquad improvedSolution := \langle \text{the improved solution associated with } Solutions[i] \rangle \\ &\quad \textbf{end if} \\ &\quad \textbf{if } f(improvedSolution) > f(RefSet[b])\ \textbf{then} \\ &\qquad RefSet := \text{Update}(RefSet,, improvedSolution) \\ &\quad \textbf{end if} \\ &\textbf{end for} \end{aligned} $$

Algorithm 3. Improving solutions and updating the RefSet.

Implementation Details

This section shows, by way of example, the implementation of some parts of the algorithm. All listings are the actual source; only a representative subset of the classes is reproduced.

The Scatter Search Algorithm

ScatterSearch implements the OptimizationAlgorithm interface, which is the single contract every algorithm exposes:

package ssmdp.algorithm;

public interface OptimizationAlgorithm {

    public Solution createSolution(long millisTimeout);

}

The main class follows Algorithm 2 and Algorithm 3 above. Its constructor wires the Constructive, Combinator and ImprovementMethod that correspond to the chosen SSConfig, and createSolution runs the RefSet life cycle. The most relevant aspects are explained through comments:

package ssmdp.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import ssmdp.algorithm.combinator.Combinator;
import ssmdp.algorithm.combinator.D2Combinator;
import ssmdp.algorithm.combinator.RandomCombinator;
import ssmdp.algorithm.combinator.TabuD2Combinator;
import ssmdp.algorithm.constructive.Constructive;
import ssmdp.algorithm.constructive.GraspD2Constructive;
import ssmdp.algorithm.constructive.RandomConstructive;
import ssmdp.algorithm.constructive.TabuD2Constructive;
import ssmdp.algorithm.diversificator.Diversificator;
import ssmdp.algorithm.diversificator.NotUsedNodesDiv;
import ssmdp.algorithm.improvement.ImprovedLocalSearch;
import ssmdp.algorithm.improvement.ImprovementMethod;
import ssmdp.algorithm.improvement.LocalSearch;
import ssmdp.algorithm.improvement.LocalSearchTabuSearch;
import ssmdp.algorithm.tabud2.TabuD2Calculator;
import ssmdp.instance.Instance;
import ssmdp.util.BoundedSortedList;
import ssmdp.util.Combinations;

public class ScatterSearch implements OptimizationAlgorithm {

    public enum SSConfig {
        WITHOUT_INF, WITH_INF, WITH_MEMORY
    }

    private static final int NUM_INITIAL_SOLUTIONS = 100;
    private static final int NUM_BEST_SOLUTIONS = 5;
    private static final int NUM_DIVERSE_SOLUTIONS = 5;

    private Constructive constructive;
    private ImprovementMethod improvingMethod;
    private Combinator combinator;
    private Diversificator diversificator = new NotUsedNodesDiv();
    private Combinations combinations = new Combinations(2,
            getRefSetSize());

    private BoundedSortedList<Solution> refSet;

    private Map<Solution, Solution> improvedSolutions;

    public ScatterSearch(Instance instance,
                            SSConfig methodConfig) {

        switch (methodConfig) {
            case WITHOUT_INF -> {
                constructive = new RandomConstructive(instance);
                combinator = new RandomCombinator();
                improvingMethod = new LocalSearch();
            }
            case WITH_INF -> {
                constructive = new GraspD2Constructive(instance);
                combinator = new D2Combinator();
                improvingMethod = new ImprovedLocalSearch();
            }
            case WITH_MEMORY -> {
                TabuD2Calculator tD2C = new TabuD2Calculator(instance);
                constructive = new TabuD2Constructive(tD2C);
                combinator = new TabuD2Combinator(tD2C);
                improvingMethod = new LocalSearchTabuSearch();
            }
        }
    }

    public Solution createSolution(long millisTimeout) {

        improvedSolutions = new HashMap<Solution, Solution>();

        refSet = new BoundedSortedList<Solution>(NUM_BEST_SOLUTIONS);

        long finishTime = System.currentTimeMillis() + millisTimeout;

        List<Solution> initialSolutions =
                constructive.createSolutions(NUM_INITIAL_SOLUTIONS);

        // Improve the solutions and add them to the RefSet
        improveAndRefreshRefSet(initialSolutions);

        // Select the diverse solutions
        List<Solution> diverseSolutions =
                diversificator.getDiverseSolutions(NUM_DIVERSE_SOLUTIONS,
                        initialSolutions, refSet.getList());

        // Prepare the RefSet to hold the diverse solutions as well as
        // the quality-based ones
        refSet.setMaxSize(getRefSetSize());

        // Add the diverse solutions to the RefSet
        refSet.addAll(diverseSolutions);

        // Create the solution groups
        List<List<Solution>> groups =
                combinations.getGroups(refSet.getList());

        // Combine the solution groups
        List<Solution> refSetCombinations =
                combinator.combineGroups(groups);

        do {

            List<Integer> newSolPositions;

            do {

                // Improve the solutions and add them to the RefSet
                improveAndRefreshRefSet(refSetCombinations);

                // Compute the new RefSet solutions
                newSolPositions = getNewSolutionsPositions();

                // If there are new solutions...
                if (newSolPositions.size() > 0) {

                    // Get the groups containing those new solutions
                    groups = combinations.getGroupsContainingIndexes(
                            newSolPositions, refSet.getList());

                    // And combine those groups
                    refSetCombinations = combinator.combineGroups(groups);
                }

                // If the time limit has been exceeded, exit the algorithm
                if (System.currentTimeMillis() > finishTime) {
                    return refSet.getBiggest();
                }

            } while (newSolPositions.size() > 0);

            // Keep only the best solutions in the RefSet
            refSet.retain(NUM_BEST_SOLUTIONS);

            // Create new solutions
            List<Solution> newSolutions =
                    constructive.createSolutions(NUM_INITIAL_SOLUTIONS);

            // Select the most diverse ones
            diverseSolutions = diversificator.getDiverseSolutions(
                    NUM_DIVERSE_SOLUTIONS, newSolutions, refSet.getList());

            // And add them to the RefSet
            refSet.addAll(diverseSolutions);

            // Compute the new solutions
            newSolPositions = getNewSolutionsPositions();

            // Get the groups with those new solutions
            groups = combinations.getGroupsContainingIndexes(
                    newSolPositions, refSet.getList());

            // And combine those groups
            refSetCombinations = combinator.combineGroups(groups);

        } while (true);

    }

    private List<Integer> getNewSolutionsPositions() {

        // Obtain the positions of the new solutions in the RefSet.
        // Each solution stores its RefSet position or -1 if it is new.

        List<Integer> indexes = new ArrayList<Integer>();
        int index = 0;
        for (Solution solution : refSet.getList()) {
            if (solution.getRefSetPosition() == -1) {
                indexes.add(index);
            }
            solution.setRefSetPosition(index);
            index++;
        }
        return indexes;
    }

    private void refreshRefSetIndexes() {

        // Update the positions of the RefSet solutions

        int index = 0;
        for (Solution sol : refSet.getList()) {
            sol.setRefSetPosition(index);
            index++;
        }
    }

    private void improveAndRefreshRefSet(
            List<Solution> solutions) {

        refreshRefSetIndexes();

        for (Solution solution : solutions) {

            Solution improvedSolution;

            if (!improvedSolutions.containsKey(solution)) {
                Solution original = new Solution(solution);
                improvingMethod.improveSolution(solution);
                improvedSolutions.put(original, solution);
                improvedSolution = solution;

            } else {
                improvedSolution = new Solution(improvedSolutions.get(solution));
            }
            refSet.add(improvedSolution);
        }
    }

    public int getRefSetSize() {
        return NUM_BEST_SOLUTIONS + NUM_DIVERSE_SOLUTIONS;
    }

}

Diversification Algorithm

The diversification algorithm has been implemented as a subclass of the Diversificator class, shown below:

package ssmdp.algorithm.diversificator;

import java.util.List;

import ssmdp.algorithm.Solution;

public abstract class Diversificator {

    public abstract List<Solution> getDiverseSolutions(
            int numDiverseSolutions,
            List<Solution> solutions,
            List<Solution> selectedSolutions);

}

The diversification algorithm presented in the previous chapter computes the distance from a solution to a set of previously selected solutions. To do so, it first computes the number of times each element of a solution appears in the set of selected solutions. A solution will be more similar to the selected solutions the greater the number of elements it shares with them (see Distance Between Solutions).

Each time a solution is incorporated into the set of selected solutions, the distance computation must be updated before the next solution is selected. The only implementation, NotUsedNodesDiv, is shown below:

package ssmdp.algorithm.diversificator;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import ssmdp.algorithm.Solution;
import ssmdp.instance.Node;

public class NotUsedNodesDiv extends Diversificator {

    @Override
    public List<Solution> getDiverseSolutions(
            int numDiverseSolutions, List<Solution> solutions,
            List<Solution> selectedSolutions) {

        // Create the list that will store the diverse solutions
        List<Solution> diverseSolutions =
                new ArrayList<Solution>();

        // Get the number of nodes in the instance
        int numNodes = solutions.get(0).getInstance().getNumNodes();

        // Create the data structure that will store the number of
        // appearances of the i-th node in the selected solutions
        int[] selectedNodesCount = new int[numNodes];

        // Count the nodes that have already been selected
        for (Solution mdpGraph : selectedSolutions) {
            refreshNodeCount(selectedNodesCount, mdpGraph);
        }

        // Store in otherSolutions the solutions that are not in
        // selectedSolutions
        Set<Solution> otherSolutions =
                new HashSet<Solution>(solutions);

        otherSolutions.removeAll(selectedSolutions);

        // If the number of solutions is less than or equal to the
        // number of diverse solutions that must be selected, return
        // the ones we already have.
        if(otherSolutions.size() <= numDiverseSolutions){
            diverseSolutions.addAll(otherSolutions);
            return diverseSolutions;
        }

        // Keep going until all diverse solutions have been selected
        while (diverseSolutions.size() < numDiverseSolutions) {

            int minSimilarity = Integer.MAX_VALUE;
            Solution minSimilaritySol = null;

            if(otherSolutions.size() == 0){
                throw new Error();
            }

            for (Solution solution : otherSolutions) {

                int similarity = calculateSimilarity(selectedNodesCount,
                        solution);

                if (similarity < minSimilarity) {
                    minSimilarity = similarity;
                    minSimilaritySol = solution;
                }
            }

            // Add the most different solution to the diverse solutions list
            diverseSolutions.add(minSimilaritySol);

            // Remove that solution from the candidates to be selected
            otherSolutions.remove(minSimilaritySol);

            // Update the node counts with the new solution
            refreshNodeCount(selectedNodesCount, minSimilaritySol);
        }
        return diverseSolutions;
    }

    private int calculateSimilarity(int[] selectedNodesCount,
                                    Solution solution) {

        int similarity = 0;
        for (Node node : solution) {
            similarity += selectedNodesCount[node.getIndex()];
        }
        return similarity;
    }

    private void refreshNodeCount(int[] selectedNodesCount,
                                  Solution solution) {

        for (Node node : solution) {
            selectedNodesCount[node.getIndex()]++;
        }
    }

}

Generation of Diverse Solutions: Random Selection

The algorithms for generating diverse solutions have been implemented as subclasses of the Constructive class. Note that Constructive also implements OptimizationAlgorithm, so a constructive can be run directly by the Experiment as a baseline. The implementation of this class is shown below:

package ssmdp.algorithm.constructive;

import java.util.ArrayList;
import java.util.List;

import ssmdp.algorithm.OptimizationAlgorithm;
import ssmdp.algorithm.Solution;
import ssmdp.instance.Instance;

public abstract class Constructive implements OptimizationAlgorithm {

    protected Instance instance;

    public Constructive(Instance instance) {
        this.instance = instance;
    }

    public Instance getInstance() {
        return instance;
    }

    public List<Solution> createSolutions(int numSolutions) {
        List<Solution> solutions = new ArrayList<Solution>();
        for(int i=0; i<numSolutions; i++){
            solutions.add(createSolution());
        }
        return solutions;
    }

    public Solution createSolution(long millisTimeout){
        return createSolution();
    }

    public abstract Solution createSolution();

}

Random selection has been chosen as an example implementation of a method for generating diverse solutions. This is the simplest method and consists of randomly selecting the nodes of the solution from the total set of nodes. The implementation, RandomConstructive, is shown below:

package ssmdp.algorithm.constructive;

import java.util.ArrayList;
import java.util.List;

import ssmdp.algorithm.Solution;
import ssmdp.instance.Instance;
import ssmdp.instance.Node;
import ssmdp.util.RandomList;

public class RandomConstructive extends Constructive {

    public RandomConstructive(Instance instance) {
        super(instance);
    }

    @Override
    public Solution createSolution() {

        // Create the list that will store the randomly selected nodes
        List<Node> nodes = new ArrayList<Node>();

        // Use the RandomList class to iterate randomly over the
        // elements of a list. In this case, it is the instance node list
        for (Node n : RandomList.create(instance.getNodes())) {

            // Add the randomly selected node
            nodes.add(n);

            // If the number of selected nodes matches the number of
            // nodes in a solution, exit the loop
            if (nodes.size() == instance.getNumSolutionNodes()) {
                break;
            }
        }

        // Build a solution with the selected nodes and return it
        return new Solution(nodes, instance);
    }

}

Combination Method: D-2 Selection

All combination methods have been implemented as subclasses of the Combinator class. This class is shown below:

package ssmdp.algorithm.combinator;

import java.util.ArrayList;
import java.util.List;

import ssmdp.algorithm.Solution;

public abstract class Combinator {

    public List<Solution> combineGroups(
            List<List<Solution>> groups) {

        List<Solution> combinedSolutions =
                new ArrayList<Solution>();

        for (List<Solution> group : groups) {
            Solution solution = combineGroup(group);
            combinedSolutions.add(solution);
        }

        return combinedSolutions;
    }

    public abstract Solution combineGroup(
            List<Solution> group);

}

The method chosen to show an implementation of the combination method is the D-2 Selection method, D2Combinator. As described in D-2 Selection, this method consists of applying the D-2 destructive heuristic to the union of the elements of the solutions being combined. The method starts from an infeasible solution containing all the elements of the solutions to be combined, and iteratively discards elements until only $m$ elements remain selected. The $i$-th element that is discarded at each iteration is the one with the minimum $D(i)$ value. The implementation is shown below:

package ssmdp.algorithm.combinator;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import ssmdp.algorithm.Solution;
import ssmdp.instance.Instance;
import ssmdp.instance.Node;
import ssmdp.util.Weighted;

public class D2Combinator extends Combinator {

    // Attribute that stores the node with the minimum distance
    private Weighted<Node> worstWNode = null;

    @Override
    public Solution combineGroup(List<Solution> solutions) {

        // Get the instance from the solutions
        Instance instance = solutions.get(0).getInstance();

        // Insert the nodes from the solutions into a set
        Set<Node> nodes = createUnion(solutions);

        // Calculate the distances between those nodes
        List<Weighted<Node>> nodesDistance =
                calculateDist(nodes);

        // While the node list still has more nodes than needed
        // for a solution
        while (nodesDistance.size() > instance.getNumSolutionNodes()) {

            Node oldNode = worstWNode.getElement();
            worstWNode = null;

              // Traverse the node list with an iterator
            for (Iterator<Weighted<Node>> it =
                 nodesDistance.iterator(); it.hasNext();) {

                Weighted<Node> wn = it.next();

                // If the node is the worst one, remove it
                if (wn.getElement() == oldNode) {
                    it.remove();
                } else {

                    // Update the weight of the nodes by subtracting
                    // the distance value to the removed node
                    wn.setWeight(wn.getWeight()
                            - wn.getElement().getDistanceTo(oldNode));

                    worstWNode = Weighted.min(worstWNode,wn);
                }
            }
        }

        return new Solution(instance, nodesDistance);
    }

    private List<Weighted<Node>> calculateDist(Set<Node> nodes) {

        // Create a list that will store each node associated with the
        // sum of its distances to the remaining nodes
        List<Weighted<Node>> nodesDistance =
                new ArrayList<Weighted<Node>>(nodes.size());

        for (Node node : nodes) {

            // Compute the sum of the distances from one node to the
            // rest of the nodes
            double distance = 0;
            for (Node otherNode : nodes) {
                distance += node.getDistanceTo(otherNode);
            }

            // Create a node associated with its distance
            Weighted<Node> wn = new Weighted<Node>(node, distance);

            // Add it to the distance list
            nodesDistance.add(wn);

            // Update the node with the minimum distance
            worstWNode = Weighted.min(worstWNode,wn);
        }
        return nodesDistance;
    }

    private Set<Node> createUnion(List<Solution> solutions) {
        Set<Node> nodes = new HashSet<Node>();
        for (Solution solution : solutions) {
            for (Node node : solution) {
                nodes.add(node);
            }
        }
        return nodes;
    }

}

Improvement Method: Improved Local Search

All improvement methods have been implemented as a subclass of ImprovementMethod. Its implementation is shown below:

package ssmdp.algorithm.improvement;

import ssmdp.algorithm.Solution;

public abstract class ImprovementMethod {

    public abstract void improveSolution(Solution solution);

}

The method chosen as an example of an improvement method has been Improved Local Search (I_LS), ImprovedLocalSearch. As described in Improved Local Search (I_LS), it selects the element $i^$ ($x_{i^} = 1$) that provides the smallest contribution to the objective-function value of the current solution. It then looks for an element $j$ ($x_j = 0$) to be swapped with $i^$. The first element $j$ that results in an improving move is selected, and the swap is performed without examining the remaining unselected elements. If no improving move that swaps $j$ for $i^$ is found, the element with the next smallest contribution is examined. This process continues until no improving move is found.

The implementation is shown below:

package ssmdp.algorithm.improvement;

import java.util.Collections;
import java.util.List;

import ssmdp.algorithm.Solution;
import ssmdp.instance.Instance;
import ssmdp.instance.Node;
import ssmdp.util.Weighted;

public class ImprovedLocalSearch extends ImprovementMethod {

    @Override
    public void improveSolution(Solution solution) {

        Instance instance = solution.getInstance();

        // Stop condition flag. Indicates whether a node has been swapped
        boolean nodeChanged;

        do {

            nodeChanged = false;

            // Get the distance list for each node
            List<Weighted<Node>> nodeDistances =
                    solution.getNodesDistance();

            // Sort the distance list from smallest to largest
            Collections.sort(nodeDistances);

            // Traverse the sorted list from smallest to largest
            for (Weighted<Node> oldWNode: solution.getNodesDistance()){

                // Take a node as a candidate to be removed
                Node oldNode = oldWNode.getElement();

                // Compute the weight the solution would have if that
                // node were removed
                double weightWithoutOld = solution.getWeight()
                        - oldWNode.getWeight();

                // Traverse the list of instance nodes
                for (Node newNode : instance.getNodes()) {

                    // If the node is not in the solution, consider it a
                    // candidate to be swapped with oldNode
                    if (!solution.contains(newNode)) {

                        // Compute the distance from newNode to the rest of
                        // the nodes, assuming oldNode is not in the solution
                        double contribution = solution
                                .calculateDistanceWithoutNode(oldNode, newNode);

                        // Compute the weight the solution would have after
                        // the swap
                        double newWeight = weightWithoutOld + contribution;

                        // If the possible solution weight is greater than
                        // the current weight
                        if (newWeight > solution.getWeight()) {
                            // Swap the node
                            solution.changeNode(oldNode, newNode);
                            nodeChanged = true;
                            break;
                        }
                    }
                }
            }
        } while (nodeChanged);

        solution.calculatePreciseWeight();
    }
}

Next: Java MetaHeuristics framework (JMH) →

Navigation Menu

Uh oh!

Scatter Search for the MDP — Implementation

Introduction

Design

Problem data — package `ssmdp.instance`

The scatter search — package `ssmdp.algorithm`

Utilities — package `ssmdp.util`

Entry point — package `ssmdp`

Improved Scatter Search Algorithm

Implementation Details

The Scatter Search Algorithm

Diversification Algorithm

Generation of Diverse Solutions: Random Selection

Combination Method: D-2 Selection

Improvement Method: Improved Local Search

Uh oh!

FilesExpand file tree

mdp-implementation.md

Latest commit

History

mdp-implementation.md

File metadata and controls

Scatter Search for the MDP — Implementation

Introduction

Design

Problem data — package ssmdp.instance

The scatter search — package ssmdp.algorithm

Utilities — package ssmdp.util

Entry point — package ssmdp

Improved Scatter Search Algorithm

Implementation Details

The Scatter Search Algorithm

Diversification Algorithm

Generation of Diverse Solutions: Random Selection

Combination Method: D-2 Selection

Improvement Method: Improved Local Search

Problem data — package `ssmdp.instance`

The scatter search — package `ssmdp.algorithm`

Utilities — package `ssmdp.util`

Entry point — package `ssmdp`