Chips-n-Salsa, v4.0.0

[4.0.0] - 2022-01-05

CONTAINS BREAKING CHANGES

This release contains breaking changes. See the Removed list below for details. The most significant
breaking changes relate to functionality initially introduced in v3.1.0, released on 12/21/2021, and
thus likely affects very few users. Other breaking changes relate to removal of previously deprecated
methods.

Added

• Added GenerationalMutationOnlyEvolutionaryAlgorithm, moving the mutation-only EA
  functionality into this new class from the existing GenerationalEvolutionaryAlgorithm
  class.
• Added GenerationalNANDOperatorsEvolutionaryAlgorithm, moving the EA
  functionality related to mutually-exclusive genetic operators (i.e., generation variation where
  each child is result of either mutation, or crossover, or identical copy of a parent, but never
  result of both mutation and crossover) into this new class from the existing
  GenerationalEvolutionaryAlgorithm class.
• Enhanced all of the following Evolutionary Algorithm and Genetic Algorithm classes with the option to use elitism:
  • GenerationalEvolutionaryAlgorithm
  • GenerationalMutationOnlyEvolutionaryAlgorithm
  • GenerationalNANDOperatorsEvolutionaryAlgorithm
  • GeneticAlgorithm
  • MutationOnlyGeneticAlgorithm
• Crossover operators for IntegerVector and BoundedIntegerVector classes, including:
  • Single-point crossover
  • Two-point crossover
  • K-point crossover
  • Uniform crossover
• Crossover operators for RealVector and BoundedRealVector classes, including:
  • Single-point crossover
  • Two-point crossover
  • K-point crossover
  • Uniform crossover
• Enhancements to IntegerVector and BoundedIntegerVector, including:
  • IntegerVector.exchange method which exchanges a subsequence between two IntegerVectors.
  • BoundedIntegerVector.sameBounds method which checks if two bounded integer vectors are
    subject to the same min and max values.
• Enhancements to RealVector and BoundedRealVector, including:
  • RealVector.exchange method which exchanges a subsequence between two RealVectors.
  • BoundedRealVector.sameBounds method which checks if two bounded real vectors are
    subject to the same min and max values.
• Added constructors to TSP (traveling salesperson problem) classes to enable specifying
  problem instance from arrays of x and y coordinates.

Changed

• Refactored evolutionary algorithm classes to improve maintainability, and ease
  integration of planned future functionality.
• Refactored ProgressTracker.update(SolutionCostPair) to simplify logic.

Removed

• Removed all mutation-only EA functionality from the GenerationalEvolutionaryAlgorithm,
  moving that functionality into the new GenerationalMutationOnlyEvolutionaryAlgorithm. This
  was done for maintainability. It is a breaking-change, although it should affect minimal
  users as the GenerationalEvolutionaryAlgorithm was just introduced in v3.1.0. For those using it
  simply use the new GenerationalMutationOnlyEvolutionaryAlgorithm class where you will
  find all the same constructors and methods necessary for mutation-only EAs.
• Removed all mutually-exclusive genetic operator functionality from the GenerationalEvolutionaryAlgorithm,
  moving that functionality into the new GenerationalNANDOperatorsEvolutionaryAlgorithm. This
  was done for maintainability. It is a breaking-change, although it should affect minimal
  users as the GenerationalEvolutionaryAlgorithm was just introduced in v3.1.0. For those using it
  simply use the new GenerationalNANDOperatorsEvolutionaryAlgorithm class where you will
  find that functionality.
• All methods/constructors that were previously deprecated in earlier releases have
  now been removed, including:
  • The following deprecated methods of the ProgressTracker class have been removed:
    • update(int, T) in favor of using update(int, T, boolean).
    • update(double, T) in favor of using update(double, T, boolean).
    • setFoundBest() in favor of using either update(int, T, boolean)
      or update(double, T, boolean).
  • The following deprecated constructors of the SolutionCostPair class have been removed:
    • SolutionCostPair(T, int) in favor of using SolutionCostPair(T, int, boolean)
    • SolutionCostPair(T, double) in favor of using SolutionCostPair(T, double, boolean)

Chips-n-Salsa, v3.1.0

[3.1.0] - 2021-12-21

Added

• Enhancements to BitVector class, including:
  • A new method to exchange a sequence of bits between two BitVectors.
  • A new method to exchange a selection of bits, specified with a bit mask, between two BitVectors.
  • A new constructor, BitVector(length, p), that generates random bit masks given probability p of a 1-bit.
• Generational evolutionary algorithms, including the following features and functionality:
  • A generic base class, GenerationalEvolutionaryAlgorithms, with type parameter to specify type of structure we
    are evolving, and which supports the following EA variations:
    • Standard generational model, parents replaced by children, crossover and mutation.
    • Generational with mutation-only (no crossover).
    • Generational, parents replaced by children, with mutually exclusive crossover and mutation (i.e.,
      no child is result of both crossover and mutation).
  • Subclasses of GenerationalEvolutionaryAlgorithms for Genetic Algorithm specific cases for convenience
    when optimizing BitVectors, including:
    • GeneticAlgorithm: a standard generational GA with bit flip mutation, and choice of crossover operator
      and selection operator.
    • MutationOnlyGeneticAlgorithm: a generational GA with only bit flip mutation, and choice of selection operator.
    • SimpleGeneticAlgorithm: a generational GA with bit flip mutation, single-point crossover, and fitness proportional
      selection.
  • Crossover features (mirrors the existing features of mutation operators):
    • CrossoverOperator interface for defining custom crossover operators.
    • Support for hybrid crossover operators (e.g., picking randomly from set of crossover operators).
  • Crossover operators for BitVectors, including:
    • Single-point crossover
    • Two-point crossover
    • K-point crossover
    • Uniform crossover
  • The following selection operators:
    • FitnessProportionalSelection
    • StochasticUniversalSampling
    • TournamentSelection
    • TruncationSelection
    • RandomSelection
    • BiasedFitnessProportionalSelection, which is fitness proportional selection but which
      enables transforming the fitness values by a bias function.
    • BiasedStochasticUniversalSampling, which is stochastic universal sampling but which
      enables transforming the fitness values by a bias function.
    • ShiftedFitnessProportionalSelection, which is a variation of FitnessProportionalSelection
      that uses transformed fitness values that are shifted so that the minimum is equal to 1,
      enabling safe use with negative fitness values.
    • ShiftedStochasticUniversalSampling, which is a variation of StochasticUniversalSampling
      that uses transformed fitness values that are shifted so that the minimum is equal to 1,
      enabling safe use with negative fitness values.
    • BiasedShiftedFitnessProportionalSelection, which is a variation of BiasedFitnessProportionalSelection
      that uses transformed fitness values that are shifted so that the minimum is equal to 1,
      enabling safe use with negative fitness values.
    • BiasedShiftedStochasticUniversalSampling, which is a variation of BiasedStochasticUniversalSampling
      that uses transformed fitness values that are shifted so that the minimum is equal to 1,
      enabling safe use with negative fitness values.
  • Classes to transform cost values to fitness values:
    • InverseCostFitnessFunction: Transforms optimization cost functions to fitnesses with a
      division.
    • NegativeCostFitnessFunction: Transforms cost to fitness with fitness(s)=-cost(s).
    • NegativeIntegerCostFitnessFunction: Transforms cost to fitness with fitness(s)=-cost(s),
      same as above but for integer cost problems.
• Constructive heuristics for the TSP for use by stochastic sampling algorithms, including:
  • Nearest city heuristic
  • Nearest city pair heuristic, which prefers the first city of the nearest 2-city combination
• New methods added to ProgressTracker class:
  • update(int, T, boolean)
  • update(double, T, boolean)
  • update(SolutionCostPair<T>)
• New constructors in SolutionCostPair class:
  • SolutionCostPair(T, int, boolean)
  • SolutionCostPair(T, double, boolean)

Deprecated

• The following methods of the ProgressTracker class have been deprecated:
  • update(int, T) in favor of using update(int, T, boolean).
  • update(double, T) in favor of using update(double, T, boolean).
  • setFoundBest() in favor of using either update(int, T, boolean)
    or update(double, T, boolean).
• The following constructors of the SolutionCostPair class have been deprecated:
  • SolutionCostPair(T, int) in favor of using SolutionCostPair(T, int, boolean)
  • SolutionCostPair(T, double) in favor of using SolutionCostPair(T, double, boolean)

CI/CD

• Updated CI/CD workflow to comment on PRs with the coverage and branches coverage percentages.

Chips-n-Salsa, v3.0.0

[3.0.0] - 2021-10-25

Added

• Implementation of the Traveling Salesperson Problem (class TSP), with the following features:
  • Generates random instances with cities distributed uniformly at random within a square.
  • Defaults to Euclidean distance, but also supports specifying a function for edge distance.
  • Two variations with a precomputed matrix of edge costs: floating-point costs, and integer costs,
    where the integer cost version by default rounds each edge cost to nearest int, but which can be
    customized. These use quadratic memory.
  • Two variations where edge costs are computed as needed: floating-point costs, and integer costs,
    where the integer cost version by default rounds each edge cost to nearest int, but which can be
    customized. These use linear memory.

Changed

• Beginning with release 3.0.0, the minimum supported Java version is now Java 11+.
• The randomization utilities for generating Gaussian-distributed random numbers, previously
  contained in the package org.cicirello.math.rand has been moved to a new
  library ρμ, which is a transitive dependency (via
  our dependency on JPT).
• Refactored GaussianMutation to improve maintainability by eliminating dependence upon a
  specific algorithm for generating Gaussian distributed random numbers.
• The library now uses Java modules, providing the module org.cicirello.chips_n_salsa, which
  includes the package org.cicirello.search and all of its very many subpackages.
  • The required dependent module org.cicirello.jpt is declared with requires transitive
    because the Permutation class from one of the packages of that module is a parameter
    and/or returned by a variety of methods such as operators that manipulate permutations.
    As a consequence, projects that include Chips-n-Salsa as a dependency will also include JPT
    and its dependencies. User's dependency manager should handle this.
• Changed the default annealing schedule in the SimulatedAnnealing class to the Self-Tuning Lam
  adaptive schedule of Cicirello (2021), which is implemented in class SelfTuningLam.

Other

• Reorganized directory hierarchy to the Maven default (we had been using a custom directory
  hierarchy for quite some time from before we switched to Maven).

Chips-n-Salsa, v2.13.0

[2.13.0] - 2021-09-16

Added

• The Self-Tuning Lam annealing schedule (class SelfTuningLam), as described by the
  paper: Vincent A. Cicirello. 2021. Self-Tuning Lam Annealing: Learning Hyperparameters
  While Problem Solving. Preprint, under review (September 2021).
• Implementation of Forrester et al (2008) continuous function optimization problem.
• Implementation of Gramacy and Lee (2012) continuous function optimization problem.

Other

• Added CITATION.cff file to configure GitHub's citation link.
• Edited Zenodo metadata.

Chips-n-Salsa, v2.12.1

[2.12.1] - 2021-7-30

Fixed

• Corrected acceptance rate calculations in AcceptanceTracker class for
  cases where some runs terminated early upon finding solution with cost
  equal to theoretical minimum cost for problem.

Chips-n-Salsa, v2.12.0

[2.12.0] - 2021-7-28

Added

• Implementations of various Royal Road problems (optimization problems on bit vectors).
  • RoyalRoad class which implements Mitchell et al's original two variations (with
    and without stepping stones) of the Royal Road problem, but generalized to BitVectors
    of any length as well as other block sizes (Mitchell et al's original problem was on
    bit vectors of length 64 with 8-bit blocks).
  • HollandRoyalRoad class implements Holland's Royal Road function.

Changed

• Completely redesigned the website for the library, including
  redesigning with AMP to accelerate mobile browsing.
• Upgraded JPT dependency to JPT 2.6.1.

Chips-n-Salsa, v2.11.1

[2.11.1] - 2021-5-13

Changed

• Code improvements based on report from initial run of MuseDev's
  static code analysis tool (non-functional changes to improve code).

Fixed

• Fixed null pointer bug in stochastic sampling implementations for the case when
  the given heuristic doesn't use an incremental evaluation.

Chips-n-Salsa, v2.11.0

[2.11.0] - 2021-5-11

Added

• New mutation operators for permutations:
  • UniformScrambleMutation: Like ScrambleMutation, but scrambled elements
    are not necessarily contiguous.
  • UndoableUniformScrambleMutation: Exactly like UniformScrambleMutation (see above),
    but with support for the undo method of the UndoableMutationOperator interface.
  • TwoChangeMutation: Mutation operator on permutations that is the equivalent of
    the classic two change operator, assuming that the permutation represents a cyclic
    sequence of edges.
  • ThreeOptMutation: Mutation operator on permutations that is the equivalent of
    the classic 3-Opt operator, which is a combination of two-changes and three-changes,
    assuming that the permutation represents a cyclic sequence of edges.
  • CycleMutation: Generates a random permutation cycle.

Changed

• Updated dependency to JPT, v2.6.0.
• Minor optimization to UndoableScrambleMutation, utilizing the JPT updates.

CI/CD

• Started using CodeQL code scanning on all push/pull-request events.
• Started using Muse.dev for static analysis.
• Upgraded coverage reporting to JaCoCo 0.8.7.

Chips-n-Salsa, v2.10.0

[2.10.0] - 2021-3-27

Added

• Enhanced support for parallel metaheuristics, including:
  • ParallelMetaheuristic class, which enables running multiple copies of a
    metaheuristic, or multiple metaheuristics, in parallel using multiple threads.
  • ParallelReoptimizableMetaheuristic, which enables running multiple copies of a
    metaheuristic that supports the reoptimize method, or multiple such metaheuristics,
    in parallel using multiple threads.
• Additional artificial search landscapes, including:
  • OneMaxAckley class implements the original version of the One Max
    problem as described by Ackley (1985), whereas the existing OneMax
    class in the library implements a variation. Ackley defined the problem
    as maximize 10 * number of one bits.
  • Plateaus class implements the Plateaus problem, originally described by Ackley (1987),
    and is an optimization problem over the space of bit strings, characterized by large
    flat areas.
  • Mix class implements the Mix problem, originally described by Ackley (1987),
    and is an optimization problem over the space of bit strings, that mixes the
    characteristics of OneMax, TwoMax, Trap, Porcupine, and Plateau problems.
• Added the following predicate methods to BitVector: allOnes, allZeros, anyOnes, anyZeros.
• Enhancements to BitVector.BitIterator, including:
  • BitVector.BitIterator.skip() method enabling skipping over bits.
  • BitVector.BitIterator.numRemaining() method to get number of remaining bits.
  • BitVector.BitIterator.nextLargeBitBlock() for getting more than 32 bits at a time.
• RotationMutation, a mutation operator for Permutations.

Changed

• Enhanced support for parallel metaheuristics, including:
  • Refactored ParallelMultistarter class to reduce redundancy among its constructors.
  • Refactored ParallelMultistarter class to utilize the new ParallelMetaheuristic as
    a base class.
  • Refactored ParallelReoptimizableMultistarter class to utilize the
    new ParallelReoptimizableMetaheuristic as its super class.

Fixed

• Bug in definition of Ackley's Trap function (had been missing a
  floor due to an error in a secondary source of description of problem).

Chips-n-Salsa, v2.9.0

[2.9.0] - 2021-3-20

Added

• Added an implementation of the TwoMax problem.
• Added an implementation of a variation of the TwoMax problem, but
  with two global optima, unlike the original version which has one
  global and one sub-optimal local optima.
• Added an implementation of Ackley's Trap function, an artificial
  search landscape with one global optima, and one sub-optimal local
  optima, where most of the search space is within the attraction basin
  of the local optima.
• Added an implementation of Ackley's Porcupine function, an artificial
  search landscape with one global optima, and an exponential number of
  local optima, a very rugged landscape.