d-lowl / kglsm

kGLSM

Build

• ./gradlew build builds into .class files.
• ./gradlew jar builds jar file for the library.

Run in Jupyter Notebook

This repository has examples written in Jupyter Notebooks. Before running, jar must be built first and requirements need to be installed (primarily `kotlin-jupyter-kernel``)

./gradlew jar
pip install -r requirements.txt
jupyter-notebook

Motivation

This library is to serve as a framework for performing Stochastic Local Search (SLS) based on Generalised Local Search Machines (GLSM). It was shown that best performing SLS (on a variety of classes of problems) are combinations of multiple pure SLS algorithms. The idea of GLSMs is a unified way to build a represent SLS algorithms that may (or may not be) combinations of pure strategies themselves, using Finite State Automata.

GLSM components

A GLSM consists of:

• State machine with Search Strategies as nodes and Transition Predicates as transitions between them
• Memory that may hold current and best solutions, steps performed and other task or search strategy dependent information
• Search Space definition, and possible operations on it
• Problem definition, or in other words cost function

Note: In SLS 2005, the last two components are treated as inputs to GLSM instead, but for the sake of convinience I will be sticking to the definition above. Subject to change later.

Notes

This is WIP, the signatures most likely will be changed in the future, until I settle down on what works best. More algorithms, search space supports, and model problems are yet to be added.

References

[SLS 2005] H. H. Hoos and Stützle Thomas, Stochastic local search: foundations and applications. Amsterdam: Morgan Kaufmann Publishers, 2005. -- Main reference for SLS algorithms and GLSM framework. If not explicitly stated otherwise, you can assume that it's from this book.

[SURVEY 2012] Parejo, J.A., Ruiz-Cortés, A., Lozano, S. et al. Metaheuristic optimization frameworks: a survey and benchmarking. Soft Comput 16, 527–561 (2012). https://doi.org/10.1007/s00500-011-0754-8 -- a good review and a benchmark of existing libraries for metaheuristics/SLS algorithms. More comparisons with this approach against the pre-existing once are to come.

kglsm's Issues

Investigate: solution as kmath vectors

Implement if feasible and appropriate

Implement other model problems

TSP, Scheduling, Knapsack

recombination and mutation operators for permutation search spaces

To allow Evolutionary Algorithms on TSP

Refactor state machines

Add more sophisticated SLS strategies

TBC

• Population based, e.g. Genetic Algorithms
• Better ILS, e.g. Simulated Annealing

Setup kotlin notebooks with examples

Cost function diffs

Allow for diffs in cost function: instead of calculating a cost function itself, calculate difference in cost between two solutions. Might decrease constant computation term, which is important for large instances of TSP specifically

Continuous Search Space sampling

Multiple sampling modes:

• Uniform, whole space
• Uniform, fixed neighbourhood
• Gaussians

Simulated Annealing

Different temperature schedules

• Linear
• Multiplicative
• Slow
  - [ ] Multiple steps -- same temperature

Check GLSM state machine for correctness

• Must terminate (eventually potentially reach termination state)
• Must be fully connected
• Must not have transitions from the final state

Add memory event handlers to memory attributes

DSL

DSL for defining GLSMs outside the code. Potential fallback to JSON/YAML

Add State Machine for strategies

Multistep Delayed Annealing Schedule

Add option for simulated annealing routine to stay at the same temperature for multiple iterations.

Simplify Generic Signatures

Current generic signatures are really cumbersome pretty much everywhere. We want as much of automatic inference as possible.

Dokka

• Add KDoc/Dokka
• Host at jitpack

TSP Model Problem

• Permutation search space
• 2-exchange neighbourhood
• TSP cost function
• Loading from file -- TSPlib

Optionals:

• k-exchange neighbourhood
• recombination and mutation operators for permutation search spaces

Example: SimAnneal for simple function

Cannot create sequential LSM with single state

sequentialStateMachine<Double, BasicSolution<Double>> {
            step {
                name = "RandomWalk"
                strategy = RandomWalkStrategy(true)
            }
            terminationPredicate = FixedStepsPredicate(10)
        }

raises an exception

Exception in thread "main" java.lang.IllegalStateException: Required value was null.
	at space.d_lowl.kglsm.sls.StateMachineTransition$Builder.build(StateMachine.kt:36)
	at space.d_lowl.kglsm.sls.SequentialStateMachineBuilder.build(SequentialStateMachineBuilder.kt:109)

Add documentation and examples

k-exchange neighbourhood

Add CI

Constructive search

So far only perturbative search has been considered

Implement Iterated Local Search

Starting with SAT and binary neighbourhood?

Unify packages structure

Add multi-state SLS

• ILS with Restart
• Memetic Algorithm
• Random Iterative Improvement

Add those both as pre-built exploitable classes and as the code in the notebooks

Visualise GLSM state machine

Memory Efficient Serialisation of Memory

SLS Performance analysis

Emperical analysis, search space structure. Chapters 4, 5

Add state machine composition

This is to add various binary operations on state machines/graphs to combine GLSMs

Logging and progress bars

Add other prototypical search spaces

• Continuous
• 2-swap paths
• Constructive paths

External bindings

Python and binary apps. Potentially R?