Class OneMaxAckley

  • All Implemented Interfaces:
    IntegerCostOptimizationProblem<BitVector>, Problem<BitVector>

    public final class OneMaxAckley
    extends Object
    implements IntegerCostOptimizationProblem<BitVector>

    The OneMaxAckley class is an implementation of the well-known OneMax problem, often used in benchmarking genetic algorithms and other metaheuristics. Specifically, it implements Ackley's (1985) original version of the problem.

    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. The OneMax problem has no local optima, and thus should be trivially easy for hill climbers.

    It was originally posed as a maximization problem because it was originally defined as a fitness function for a genetic algorithm. The problem was originally stated to maximize f(x) = 10 * CountOfOneBits(x), where x is a vector of bits of length n. The value method returns 10 times the number of bits in the BitVector equal to 1, which is to be maximized. Thus, as a cost function, the cost method returns 10 times the number of bits not equal to 1, where the minimum cost is thus 0, corresponding to the case of maximal number of 1-bits.

    The Chips-n-Salsa library also includes a version that is a simple count of the bits without the multiplication by 10 in the OneMax class.

    Although commonly used by others without reference, the OneMax problem was introduced by David Ackley in the following paper:
    David H. Ackley. A connectionist algorithm for genetic search. Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 121-135, July 1985.

    • Constructor Summary

      Constructors 
      Constructor Description
      OneMaxAckley()
      Constructs a OneMaxAckley object for use in evaluating candidate solutions to the OneMax problem.
    • Constructor Detail

      • OneMaxAckley

        public OneMaxAckley()
        Constructs a OneMaxAckley object for use in evaluating candidate solutions to the OneMax problem.
    • Method Detail

      • cost

        public int cost​(BitVector 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<BitVector>
        Parameters:
        candidate - The candidate solution to evaluate.
        Returns:
        The cost of the candidate solution. Lower cost means better 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<BitVector>
        Returns:
        A lower bound on the minimum theoretical cost of the problem instance.
      • value

        public int value​(BitVector 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<BitVector>
        Parameters:
        candidate - The candidate solution to evaluate.
        Returns:
        The actual optimization value of the candidate solution.
      • 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<BitVector>
        Parameters:
        cost - The cost to check.
        Returns:
        true if cost is equal to the minimum theoretical cost,