Portability  portable 

Stability  provisional 
Maintainer  Richard Senington <sc06r2s@leeds.ac.uk> 
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.
 firstImprov :: Ord nme => LSTree nme > [nme]
 minImprov :: Ord nme => LSTree nme > [nme]
 maxImprov :: Ord nme => LSTree nme > [nme]
 randomImprov :: (RandomGen g, Ord nme) => g > LSTree nme > [nme]
 randomWalk :: RandomGen g => g > LSTree nme > [nme]
 simpleTabu :: Eq nme => Int > LSTree nme > [nme]
 minFirstTabu :: Ord nme => Int > LSTree nme > [nme]
 maxFirstTabu :: Ord nme => Int > LSTree nme > [nme]
 stochasticTabu :: (Eq nme, RandomGen g) => Int > g > LSTree nme > [nme]
 saTemp :: Num a => a > a > [a]
 simulatedAnnealingA :: (NumericallyPriced nme a, RandomGen g) => a > a > g > LSTree nme > [nme]
 simulatedAnnealingB :: (Ord nme, RandomGen g, Num a, Random a, Ord a) => a > a > g > LSTree nme > [nme]
 firstChoice :: LSTree a > [a]
 manualNavigator :: (Show nme, NumericallyPriced nme b) => LSTree nme > IO ()
 improvement :: Ord nme => LSTree nme > LSTree nme
 nShuffle :: RandomGen g => g > LSTree nme > LSTree nme
 nSort :: Ord nme => LSTree nme > LSTree nme
 nReverse :: LSTree nme > LSTree nme
 tabu :: Eq nme => Int > [nme] > LSTree nme > LSTree nme
 thresholdWorsening :: NumericallyPriced nme a => a > LSTree nme > LSTree nme
 varyingThresholdWorsening :: NumericallyPriced nme a => [a] > LSTree nme > LSTree nme
 multiLevelApply :: [LSTree nme > LSTree nme] > LSTree nme > LSTree nme
 sImprovement :: Ord nme => LSTree nme > LSTree nme
 data LSTree nme = LSTree {
 treeNodeName :: nme
 treeNodeChildren :: [LSTree nme]
 mkTree :: (a > [a]) > a > LSTree a
 exchange :: Eq a => Int > Int > [a] > [[a]]
 basicExchange :: Eq a => [a] > [[a]]
 class (Ord b, Num b) => NumericallyPriced a b  a > b where
 priceSolution :: a > b
Documentation
firstImprov :: Ord nme => LSTree nme > [nme]Source
First improvement, relies upon the solutions forming an ordering.
minImprov :: Ord nme => LSTree nme > [nme]Source
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]Source
Maximal improvement, always takes the best neighbour, and stops when there are no more improvements
randomImprov :: (RandomGen g, Ord nme) => g > LSTree nme > [nme]Source
Random improvement, only accepts improvements, but is less predictable as to which it will take.
randomWalk :: RandomGen g => g > LSTree nme > [nme]Source
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]Source
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]Source
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]Source
stochasticTabu :: (Eq nme, RandomGen g) => Int > g > LSTree nme > [nme]Source
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]Source
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]Source
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]Source
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]Source
manualNavigator :: (Show nme, NumericallyPriced nme b) => LSTree nme > IO ()Source
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. Implemented using multiapply.
nReverse :: LSTree nme > LSTree nmeSource
Recursive neighbourhood reversal transformation. Implemented using multiapply.
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.
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.
LSTree  

mkTree :: (a > [a]) > a > LSTree aSource
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]]Source
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]]Source
We provide the most basic exchange system for testing
class (Ord b, Num b) => NumericallyPriced a b  a > b whereSource
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.
priceSolution :: a > bSource