cicirello / chips-n-salsa

A Java library of Customizable, Hybridizable, Iterative, Parallel, Stochastic, and Self-Adaptive Local Search Algorithms

Vincent A Cicirello

	Sites where you can find me or my work
Web and social media
Software development
Publications

If you want to generate the equivalent to the above for your own GitHub profile, check out the cicirello/user-statistician GitHub Action.

chips-n-salsa's Issues

Fully migrate build process from ant to maven

Currently using maven for deploying packages to Maven Central and GitHub Packages. But development process still using Ant. Fully migrate to Maven.

Variation of TSP implementation that precomputes pairwise distances

Summary
Existing TSP implementation computes edge distances as needed, which saves memory and enables representing instances that are too large to store full weight matrix. However, solving smaller instances can be sped up if full weight matrix is stored.

Add an exponential bias option to ValueBiasedStochasticSampling

• HeuristicBiasedStochasticSampling already includes constructors to define an exponential bias function. Add similar support to the ValueBiasedStochasticSampling class.
• At the moment, you can do this using one of the constructors that takes a bias function parameter, but this is a sufficiently common form that it is worth having a constructor for this specific purpose (and also for consistency with design of the HeuristicBiasedStochasticSampling class).

Examples should be relevant and applicable

While the examples do a good job of answering the questions of "what" and "how", they do not answer "why".

It would be great if the examples were based on some real-world problems that demonstrate application context and why a dev should use this tool.

Good examples include:

• protobuf
• tensorflow
• pybotics

cc openjournals/joss-reviews#2448

Make Self-Tuning Lam the default annealing schedule

Summary
Change the default annealing schedule in the simulated annealing implementation from the Modified Lam to the Self-Tuning Lam. It is more effective, and also better accomplishes what the Modified Lam attempts to accomplish (i.e., better follows Lam and Delosme's idealized neighbor acceptance rate). The Self-Tuning Lam is introduced in:

• Vincent A. Cicirello. 2021. Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving. Preprint, under review (September 2021).

Notes
Changing the default annealing schedule may be considered a breaking change if someone is expecting the Modified Lam in particular. However, it can also be viewed as an improved version of the Modified Lam, and since strictly speaking existing code relying on the default will still work (and probably exhibit improved performance as a result), it may be considered non-breaking. In any event, consider this carefully before making this change. For now, we'll schedule the change with the Release 3.0.0 milestone, assuming we'll consider it breaking.

References and Citations

• There are 27 citations for a two page paper. Are all these citations needed? Are they all truly relevant?
• 11 of the 27 citations (40%) are self-citations. This can be seen as citation farming. Same questions as above.
• Many of the non-self-citations are >5 years old. Due to the popularity of AI/ML, the fields of optimization and search algorithms are rapidly evolving. Are these the most up-to-date and relevant references?

cc openjournals/joss-reviews#2448

Documentation website: bug in amp cache formatting

Google's amp cache doesn't seem to recognize % as the percent sign. Looks fine served from gh pages, but amp cache leaves character encoding as if verbatim text.

Move the Gaussian random number classes to a separate library

Summary
The Gaussian random number classes are more generally applicable than Chips-n-Salsa. The JPT library is in the process of moving random number utility classes to a separate dependent library. Once that is complete, move the Gaussian classes to that new library.

Move example programs to separate repository

To simplify repository structure, move example programs to separate repo. In particular, this would better enable managing dependencies of example programs.

Feature request: Add support for scaling an optimization problem's cost function

If one is experimenting with a stochastic local search algorithm, it may be desirable to explore the effects of properties of a cost function on problem solving behavior. One such property may be the range of the cost function. If one has a cost function with known range, they could potentially explore the effects of varying the range in a simple way such as scaling the existing cost function. For example, if you have a cost function f(x) that you are minimizing, you can instead minimize g(x) = a * g(x) where a is a scale factor greater than 0.

This feature request involves implementing a pair of classes, one that can be used to scale the cost function of problems with real-valued cost functions (e.g., scale the costs represented by implementations of the interface OptimizationProblem), and the second for integer-cost problems (e.g., problems that implement IntegerCostOptimizationProblem).

Modularize library

Summary
Use Java modules. Depends on #287.

Implementation of Traveling Salesperson Problem

Summary
Add an implementation of the traveling salesperson (TSP) including random instance generation. Desired characteristics include:

• Support for both integer cost and floating-point cost versions.
• Euclidean distance between 2D city locations as default distance function.
• Support for custom function for edge distances.

Instance generator for static scheduling with weights and duedates

• Instance generator for static scheduling with weights and duedates, similar to the existing one, but this time without setup times.
• It should generate problem instances with the same characteristics as the instances from the OR-Library.
• It should be able to parse the OR-Library instance files.
• It should be able to produce files in that format as well.

Feature request: Support for optionally extracting fine-grained detail from SA runs

Motivation

If one is designing a new annealing schedule for simulated annealing, it may be desirable to have the ability to extract fine-grained detail from a run of SA, such as frequency of neighbor acceptance.

Request

A simple class implementing AnnealingSchedule that can be used to wrap an AnnealingSchedule object. Ultimately, this class would delegate the actual annealing schedule to the wrapped object, but would provide a means of accessing data such as cost values passed to the AnnealingSchedule by simulated annealing, whether the wrapped AnnealingSchedule accepted the neighbor, etc.

Feature Req: Non-contiguous scramble mutation

Describe the solution you'd like
A version of Scramble Mutation for permutations that randomizes a non-contiguous set of permutation elements. Preferably configurable with a parameter that specifies the probability of an element being included in the scramble, similar to the parameter of the classic uniform crossover operator for bitstrings.

Describe alternatives you've considered
The library has a ScrambleMutation class that scrambles a randomly selected sub-permutation (between two indexes). This request is for an alternative to that.

Feature Req: Royal Roads problem

Describe the solution you'd like
Implementations of the Royal Road problems (problems on bit strings), including:

• The two original RoyalRoad problems, specified by Mitchell et al, usually referred to as R1 and R2.
• Holland's RoyalRoad problem.

Instance generator and heuristics for Common Duedate Scheduling

• Instance generator for Common Duedate Scheduling, based on the method used to generate the instances from the OR-Lib.
• Parser for the file format specified in OR-Lib.
• Relevant constructive heuristics for the problem.

Feature Req: Three opt mutation for permutations

Is your feature request related to a problem? Please describe.
Relevant when solving problems like the TSP, using Permutations to represent solutions where the permutation represents a sequence of edges.

Describe the solution you'd like
The classic 2-change operator removes two edges at random and replaces them with two other edges to get a valid tour. The classic 3-change is similar, but removes 3 random edges, and reconnects with 3 different edges that lead to a valid tour. For any 3 edges removes, there are 4 combinations of 3 edges that are different than those removed and which results in a valid tour. The classic 3-opt algorithm with the TSP uses a neighborhood consisting of al 2-changes and all 3-changes. This request is for a mutation operator where a random 2-change or 3-change is applied to the permutation.

Describe alternatives you've considered
The library has a BlockMove mutation operator. A Block Move is a type of 3-change, but it doesn't generate all possible reconnections of the 3 removed edges. A ReversalMutation is almost a 2-change (but includes some redundant cases). See Issue #228 for a related request for a mutation operator.

Installation, usage, and artifacts

The README explains how to build the repo and run the examples, but not how (and why) to integrate it into other codebases. There should also be an artifactory or release management system (e.g., JFrog, Nexus, Maven Central Repository, GitHub releases) that contains the latest built JARs for quick integration. Bonus points if the code can be integrated through the most popular Java build tools, such as gradle and maven.

cc openjournals/joss-reviews#2448

Other libraries?

The paper includes a lot of discussions around algorithms (the first section) and the library itself (the second section). What about other (i.e., competitor) libraries? I highly doubt that this is the only library that serves this purpose for Java. What about for other languages? How does this work compare to those implementations?

cc openjournals/joss-reviews#2448

Specifiy Java version

The supported java (and openjdk) versions should be explicitly specified in the README.

cc openjournals/joss-reviews#2448

Reorganize source code to use Maven default hierarchy

Summary
Current directory hierarchy is remnant of our prior use of Ant. We switched to Maven over a year ago or longer but kept dir structure. Reorganize into Maven's standard hierarchy. This is a non-functional change strictly for maintainability.

Implementation of Forrester et al (2008) continuous function optimization problem

Summary
Add implementation of Forrester et al (2008) continuous function optimization problem used in recent journal article submission.

Replace direct calls to methods of ZigguratGaussian with the methods of RandomVariates class

Summary
The Gaussian mutation operator implementation currently directly calls methods of the ZigguratGaussian class, a specific implementation of Gaussian distributed random numbers. The dependency library rho-mu has a class RandomVariates that currently delegates Gaussian random numbers to ZigguratGaussian, but doesn't make any specific algorithm guarantees, other than that it uses the most efficient of the options available within the library. Thus, switching the calls to the methods of that class will guarantee that we gain the benefit of any future changes that improve speed of random number generation.

Parser for benchmark scheduling instance data files

The library already includes an instance generator for single machine scheduling problems with weights, duedates, and sequence-dependent setups. That generator is based upon a generator for a set of benchmark instances: http://dx.doi.org/10.7910/DVN/VHA0VQ . Add functionality for parsing the data files containing problem instances, as well as for generating files in that format.

Update documentation for dependency changes and Java version change

Summary
Update the documentation (including repo's README.md and the project website) to reflect the changes related to dependencies and minimum Java 11+ change.

Fitness proportionate selection

Summary
Add an implementation of fitness proportionate selection, i.e., weighted roulette wheel.

Feature Req: Cycle mutation for permutations

Describe the solution you'd like
A mutation operator for permutations that creates a random permutation cycle within the permutation. The idea is similar to cycle crossover, but instead of operating on a pair of permutations, the proposed mutation operator will operate on a single permutation to replace a set of elements chosen randomly with a cycle of those elements. Ideally, it will be configurable with a parameter specifying the probability of including an element in the cycle, similar to the parameter for a uniform crossover operator for bitstrings.

Describe alternatives you've considered
The library has a SwapMutation. Swap creates a special type of cycle of length 2. The library also has an InsertionMutation, which randomly removes an element, and reinserts it into a different randomly chosen position. Insertion mutation is a more specific type of cycle, where all of the elements of the cycle are in sequence. The requested cycle mutation is more general than both of these, specifically, select a set of elements (not necessarily in sequence) at random, and then form a permutation cycle of those.

Add CONTRIBUTING.md

https://docs.github.com/en/github/building-a-strong-community/setting-guidelines-for-repository-contributors

cc openjournals/joss-reviews#2448

Investigate and address (if necessary) issues identified in initial run of MuseDev

Summary

We recently enabled MuseDev static analysis on the repository. The initial run identified some possible issues. Some of these have already been determined as false positives, and some others (mostly minor code improvements, and not actual bugs) were already fixed in most recent release. This issue is to go through the rest to verify whether they are false positives or something worth fixing.

Change build to target Java 11

Summary
Library currently supports Java 8+. Change build to target Java 11 to gain access to newer language features.

Update configuration of Lift (MuseDev renamed including configuration file)

Update configuration of Lift (MuseDev renamed including configuration file)

Evolutionary algorithms

Summary
Add a population based search, such as an evolutionary algorithm.

Copyright printing should be in its own file/class/utility package to avoid code duplication

Chips-n-Salsa/examples/org/cicirello/examples/chipsnsalsa/CustomIntegerCostProblemExample.java

Line 41 in afc5921

public static void printCopyrightAndLicense() {

cc openjournals/joss-reviews#2448

Define versioning scheme

I noticed that the GH Releases/Packages appear to be using SemVer (https://semver.org/). The README should be updated to include a section that explicitly defines the versioning scheme.

cc openjournals/joss-reviews#2448

Feature Req: Ackley's Plateau problem

Describe the solution you'd like
An implementation of Ackley Plateaus, a problem for bit string representation.

Unable to run examples

I could download and build the library using the makefile. However, when I tried to run "make examples", I got the following error:

java -cp "exbin;dist/chips-n-salsa-1.0-jar-with-dependencies.jar" org.cicirello.examples.chipsnsalsa.BitVectorExample
Error: Could not locate or load main class org.cicirello.examples.chipsnsalsa.BitVectorExample
Caused by: java.lang.ClassNotFoundException: org.cicirello.examples.chipsnsalsa.BitVectorExample
make: *** [Makefile:11: examples] Error 1

The same error appears when I try to run each example manually. I'm running the commands from the root repository.

cc openjournals/joss-reviews#2448

Simplify entrypoint

When getting started with the repo, the two primary entrypoints are "building the code" and "running examples".

While a java developer will have no problem building with ant and understanding why the -cp flag is needed to run the examples, these are an extra impedance for someone new to the repo.

I'd recommend using a Makefile as the entrypoint. See #1 for an example. The READMEs will need to be updated as well.

Moreover, the two READMEs (README.md and examples/README.md) cite the same way to run the examples. This duplication of instructions can lead to future stale or out-of-sync documentation. Using a Makefile separates the implementation from the documentation.

cc openjournals/joss-reviews#2448

Stochastic sampling search: add support for additional types

At the present time, the stochastic sampling search algorithms in Java package org.cicirello.search.ss only support searching the space of permutations. This will involve extracting an interface from the PartialPermutation class, along with modifications to rely on that interface rather than directly interacting with the PartialPermutation class.

Feature Req: Two change mutation for permutations

Describe the solution you'd like
Two change is a classic mutation operator for problems like the TSP, where the permutation represents a sequence of edges. It removes two random "edges" and replaces them with the two edges that leads to a different valid permutation.

Describe alternatives you've considered
The existing ReversalMutation is almost the same, however a complete reversal of the permutation does not replace any edges, and a reversal of length n-1 also doesn't replace any edges. Ideally, a two change operator should always produce a permutation that represents a different set of edges (i.e., a different tour for a tsp).

AcceptanceTracker class assumes no runs ended early by finding known optimal

Describe the bug
The AcceptanceTracker class, which can be used to track and log the neighbor acceptance rate during runs of simulated annealing assumes that all runs went to end of run. But the SA implementation will terminate early if it finds a solution with cost equal to the theoretical min for the problem. This leads to the potential for acceptance rates to be underreported, especially near end of long runs if some runs terminated early. For example, if there are 100 runs, it will divide by 100 when computing the acceptance rate at iteration i, regardless of whether there were 100 runs that reached iteration i.

Expected behavior
Correct acceptance rate calculation (i.e., divide by number of runs that reached iteration i).

Migrate API doc website build process from Ant to Maven

The library's build process has been migrated from Ant to Maven. However, the workflow that generates the documentation website using GitHub Actions is still currently using Ant to run javadoc. The Maven pom.xml will need to be revised to use a custom target location for the output of javadoc in order to use Maven for this.

Implementation of Self-Tuning Lam annealing schedule

Summary
Add an implementation of the new Self-Tuning Lam annealing schedule, from our recent journal submission:

• Vincent A. Cicirello. 2021. Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving. Preprint, under review (September 2021).

Implementation of Gramacy and Lee (2012) continuous function optimization problem

Summary
Add implementation of Gramacy and Lee (2012) continuous function optimization problem used in experiments of recent journal article submission.

Stochastic universal sampling

Summary
Add an implementation of stochastic universal sampling.

Update README to include GitHub Packages maven info

Now that GH Packages is being used to distribute the package, there should be a README section that describes how to import this package.

cc openjournals/joss-reviews#2448

BUG: Trap function missing floor in definition of z

Describe the bug
In the artificial search landscape known as Trap, there is a parameter z defined originally by Ackley as z = floor((3/4)n). Currently implemented without the floor (based on a secondary source of the problem definition). Bug discovered by reading the original description of problem by Ackley.

Update javadocs of SelfTuningLam class with citation to article

Summary
Update the javadocs of SelfTuningLam with the citation to the recently published article about it.

Set up automated testing and CI/CD

Good software practice calls for automated testing, continuous integrations, and continuous deployments. Each pull request, change, merge, and release should be rigorously tested and deployed without human intervention (the source of all errors).

Set up testing/CI/CD with one of the many free services, such as GitHub Actions, CircleCI, TravisCI, etc

cc openjournals/joss-reviews#2448

Feature Req: Ackley's Mix problem

Describe the solution you'd like
An implementation of Ackley's Mix problem, which is a combination of OneMax, TwoMax, Trap, Porcupine, and Plateau. All of these already exist in the library except for Plateau. So this feature request depends upon issue #232 .