local-search-0.0.2: A first attempt at generalised local search within Haskell, for applications in combinatorial optimisation.

Portabilityportable
Stabilityprovisional
MaintainerRichard Senington <sc06r2s@leeds.ac.uk>

Control.Search.Local.Transformation

Description

Transformations for capturing characteristics of algorithms.

Synopsis

Documentation

improvement :: Ord nme => LSTree nme -> LSTree nmeSource

A basic recursive filter. This will check every neighbourhood, and remove those neighbours that do not improve upon their parent solution.

nShuffle :: RandomGen g => g -> LSTree nme -> LSTree nmeSource

Recursive neighbourhood shuffling transformation, all neighbourhoods will become randomised.

nSort :: Ord nme => LSTree nme -> LSTree nmeSource

Recursive neighbourhood ordering transformation. Could be reimplemented in the future in a similar way to improvement, with a single level transformation, this would allow odd combinations in lists to be used in other multi-apply configurations.

nReverse :: LSTree nme -> LSTree nmeSource

Reversal, recursive again. To be used in combination with sorting to place in ascending or descending order, depending on what you want.

tabu :: Eq nme => Int -> [nme] -> LSTree nme -> LSTree nmeSource

A simple (very simple) TABU system. Based upon a limited Queue, and direct node comparison (not the way it is usually used in the OR community). Acts as a recursive filter based upon memory.

thresholdWorsening :: NumericallyPriced nme a => a -> LSTree nme -> LSTree nmeSource

Takes advantage of numerically priced solutions, rather than just ordering, to allow through solutions that are worse than the current solution, but only to a limited extent. Would require some understanding of the maximum and minimum differences likely in a solution set.

varyingThresholdWorsening :: NumericallyPriced nme a => [a] -> LSTree nme -> LSTree nmeSource

An adaptation of the above. We now have a list of thresholds, constructed in some way (user defined) and then applied each to a different level of the tree. Used in one of the Simulated Annealing experiments.

multiLevelApply :: [LSTree nme -> LSTree nme] -> LSTree nme -> LSTree nmeSource

Takes a list of single level transformations, and applies them each to a different level of a tree. These are also generated in a user defined way, and this function is used in the other Simulated Annealing experiment.

sImprovement :: Ord nme => LSTree nme -> LSTree nmeSource

A single level improvement transformation, that will remove from the top neighbourhood of the tree those solutions that do not improve upon the parent solution. It is used by both the recursive improvement transformation, and one of the attempts to encode Simulated Annealing.