Class BoundMax

java.lang.Object
org.cicirello.search.problems.BoundMax
All Implemented Interfaces:
Splittable<Initializer<IntegerVector>>, Initializer<IntegerVector>, IntegerCostOptimizationProblem<IntegerVector>, Problem<IntegerVector>
public final class BoundMax extends Object implements IntegerCostOptimizationProblem<IntegerVector>, Initializer<IntegerVector>
The BoundMax class is an implementation of a generalization of the well-known OneMax problem, often used in benchmarking genetic algorithms and other metaheuristics.

In the OneMax problem, the metaheuristic is searching the space of bit-strings of length n for the bit-string with the most bits equal to a 1. It originated as a test problem for genetic algorithms, where the standard form of a genetic algorithm represents solutions to the problem with a string of bits. The OneMax problem offers a test problem with a known optimal solution, a bit-string of all 1s. For example, if n=8, then the optimal solution is: 11111111.

BoundMax generalizes OneMax to vectors of integers such that each integer is bound in the interval [0,B] for some B ≥ 1. The problem is to find the vector of length n with maximum number of integers equal to B. The optimal solution is thus n copies of B. For example, if n is 8, the optimal solution is [B, B, B, B, B, B, B, B]. The OneMax problem is the special case when B=1.

The value method simply counts the number of components equal to B. The problem is to maximize this count. Thus, as a cost function, the cost method counts the number of components not equal to B, where the minimum cost is thus 0.

The BoundMax class extends IntegerVectorInitializer to ensure that metaheuristics solving an instance have access to a correct means of generating valid vectors within the search space (correct length and components in the interval [0,B].

Although technically you can use the BoundMax class, which evaluates IntegerVector objects, using a bound B=1 to define the OneMax problem, you should instead use the OneMax class for the original OneMax problem. The OneMax class evaluates BitVector objects, which is a proper implementation of an indexable vector of bits.

  • Constructor Details

    • BoundMax

      public BoundMax(int n, int bound)
      Constructs an instance of the BoundMax problem.
      Parameters:
      n - The length of the instance (length of the array under optimization).
      bound - The maximum value allowed for each integer.
      Throws:
      IllegalArgumentException - if bound is negative
      NegativeArraySizeException - if n is negative

  • Method Details

    • cost

      public int cost(IntegerVector candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface IntegerCostOptimizationProblem<IntegerVector>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • value

      public int value(IntegerVector candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface IntegerCostOptimizationProblem<IntegerVector>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.

    • minCost

      public int minCost()
      Description copied from interface: IntegerCostOptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Integer.MIN_VALUE.
      Specified by:
      minCost in interface IntegerCostOptimizationProblem<IntegerVector>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.

    • isMinCost

      public boolean isMinCost(int cost)
      Description copied from interface: IntegerCostOptimizationProblem
      Checks if a given cost value is equal to the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
      Specified by:
      isMinCost in interface IntegerCostOptimizationProblem<IntegerVector>
      Parameters:
      cost - The cost to check.
      Returns:
      true if cost is equal to the minimum theoretical cost,

    • createCandidateSolution

      public final IntegerVector createCandidateSolution()
      Description copied from interface: Initializer
      Creates one candidate solution to a problem.
      Specified by:
      createCandidateSolution in interface Initializer<IntegerVector>
      Returns:
      a candidate solution to a problem instance.

    • split

      public Initializer<IntegerVector> split()
      Description copied from interface: Splittable
      Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of the Copyable interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state.
      Specified by:
      split in interface Splittable<Initializer<IntegerVector>>
      Returns:
      A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.