Control.Search.Local

This is the unification, and it is not expected that a user will have to directly import any other files, they are all exposed through this one. It then defines some basic search strategies of its own.

Documentation

firstImprov :: Ord nme => LSTree nme -> [nme]

First improvement, relies upon the solutions forming an ordering.

minImprov :: Ord nme => LSTree nme -> [nme]

Minimal improvement, will take the worst solution, that still improves upon the current solution. It is slightly more cautious, and is likely to create longer paths in most problems.

maxImprov :: Ord nme => LSTree nme -> [nme]

Maximal improvement, always takes the best neighbour, and stops when there are no more improvements

randomImprov :: (RandomGen g, Ord nme) => g -> LSTree nme -> [nme]

Random improvement, only accepts improvements, but is less predictable as to which it will take.

randomWalk :: RandomGen g => g -> LSTree nme -> [nme]

The simplest strategy. The randomisation may not be needed, it depends how structured the tree is originally. Using the basicExchange function it will be very ordered, so this is useful.

simpleTabu :: Eq nme => Int -> LSTree nme -> [nme]

The simplest Tabu search, simply disallows backtracking, should do slightly better than a random walk, but that is about it.

minFirstTabu :: Ord nme => Int -> LSTree nme -> [nme]

This will always choose the lowest ordered element of the neighbourhood, unless it has been seen recently. The choice of the minFirstTabu or maxFirstTabu, depends upon the problem, and how it has been encoded, does the user wish for high ordered, or low ordered solutions. In most cases the other becomes pointless.

maxFirstTabu :: Ord nme => Int -> LSTree nme -> [nme]

stochasticTabu :: (Eq nme, RandomGen g) => Int -> g -> LSTree nme -> [nme]

Injection of a random element into TABU, less useful than it sounds in this case, as this is very similar to simpleTabu. In practice, real TABU systems use a process of choices. If improvement is possible (subject to the TABU list) you accept the first (in whatever order, that is where randomness comes in) improvement you find. Otherwise you take another element and continue. This has not yet been represented.

saTemp :: Num a => a -> a -> [a]

A helper function for creating a falling temperature list. Used by Simulated Annealing. Really just to make it slightly easier to see what it is doing.

simulatedAnnealingA :: (NumericallyPriced nme a, RandomGen g) => a -> a -> g -> LSTree nme -> [nme]

There are two variants on simulated annealing represented here. The first is simpler, it assumes that the temperature represents a threshold for a limited worsening filter. This is applied, and the system is then navigated randomly.

simulatedAnnealingB :: (Ord nme, RandomGen g, Num a, Random a, Ord a) => a -> a -> g -> LSTree nme -> [nme]

The second takes the approach that SA tends to be (based upon a level of randomisation) a random walk at high temperatures, and an iterative improver at low temperatures. It generates a list of single level transformations based upon this idea, and then applies them one at a time.

firstChoice :: LSTree a -> [a]

manualNavigator :: (Show nme, NumericallyPriced nme b) => LSTree nme -> IO ()

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

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 nme

Recursive neighbourhood shuffling transformation, all neighbourhoods will become randomised.

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

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 nme

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 nme

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 nme

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 nme

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 nme

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 nme

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.

data LSTree nme

A rose tree, but not currently using an optimised data structure, just this little home built one. The accessor functions should be easy enough to understand.

Constructors

LSTree

Fields

treeNodeName :: nme

treeNodeChildren :: [LSTree nme]

Instances

Eq nme => Eq (LSTree nme)

Ord nme => Ord (LSTree nme)

Making a tree part of Ord and Eq, for ease of comparison later. Note that how the order is determined depends upon the implementation given for a solution.

mkTree :: (a -> [a]) -> a -> LSTree a

The construction function, as seen in the paper. Takes a neighbourhood function, that is, a function that takes a solution and perterbs it in some way, giving a selection of new solutions. It then requires a seed, and gives back an initial tree.

exchange :: Eq a => Int -> Int -> [a] -> [[a]]

following helper function pinched from http:www.polyomino.f2s.comdavidhaskell/combinatorics.html

my code again from here on

The first type of neighbourhood is based upon combination exchange in a sequence of elements. This is appropriate for something like TSP, where order matters, but would be less useful for SAT.

It takes 2 numbers as parameters, one of which is the number of exchanges to perform, the other the maximum distance within the list. For example exchange 2 2, would change up to 2 elements in each neighbourhood, either adjacent or separated by 1 other element.

basicExchange :: Eq a => [a] -> [[a]]

We provide the most basic exchange system for testing

class (Ord b, Num b) => NumericallyPriced a b | a -> b where

Some transformations (and the manual inspector of the search process) need to be able to extract a numeric price from a solution. To use these, the solution representation data type must be a part of the following class, please see the example code.

Methods

priceSolution :: a -> b

Instances

NumericallyPriced TSPTour Float