Control.Search.Local.Strategies

A collection of common strategies, built out of the combinators in the other libraries. For examples of their use, see Control.Search.Local.Example.

Iterative Improvers

iterativeImprover :: Ord s => ExpandT s -> ContraT s -> StreamT s

The generic skeleton of iterative improvers. The first parameters is a neighbourhood stream expander, the second is a stream contractor which makes choices from neighbourhoods. All neighbourhoods will be filtered so that the elements can only improve upon the previous solution.

Since the parameters are stream transformers, simple functions must be lifted before they can be used as parameters. For example a deterministic neighbourhood function df should be lifted with map and to choose the first element from each improving neighbourhood you would use map head, giving

 iterativeImprover (map df) (map head). 

This skeleton provides a standard infinite stream of solutions, rather than terminating when a local minima is reached. This provides better safety for composition than the versions suggested in the paper. When the filter results in an empty list, the seed value is wrapped up as a list and returned in its place.

firstFoundii :: Ord s => ExpandT s -> StreamT s

First found iterative improvement strategy. Fixes the choice function to map head.

maximalii :: Ord s => ExpandT s -> StreamT s

Maximal iterative improvement strategy. Since we seek the lowest possible value of solutions this translates to fixing the choice function to map minimum.

minimalii :: Ord s => ExpandT s -> StreamT s

Minimal iterative improvement strategy. Fixes the choice function to map maximum.

stochasticii :: Ord s => ([s] -> r -> s) -> [r] -> ExpandT s -> StreamT s

Stochastic iterative improvement strategy. The choice function is required to make a random choice from the neighbourhood at each step. In order to keep this as general as possible we require a choice function, and a stream of values, expected to be random numbers. The choice function takes one of these random values, and a neighbourhood and returns a single value.

This choice function and stream of random values are then used to create a stochastic decision stream contractor, and the strategy created.

TABU Search

tabu :: Ord s => ExpandT s -> ExpandT s -> ContraT s -> StreamT s

A general skeleton for TABU search. The three parameters are

1. a stream transformer to create the stream of TABU lists (typically provided by window)
2. a stream transformer to create the stream of neighbourhoods, in the same manner as seen in iterative improver
3. a choice transformer to choose a single element from a pruned neighbourhood.

standardTabu :: Ord s => Int -> ExpandT s -> ContraT s -> StreamT s

Commonly TABU search does not take a function which makes a TABU list, but rather a size of TABU list. We provide this less flexible form here, where the first parameter changes from to being the window size. Implemented in terms of tabu.

Simulated Annealing

sa :: (Floating v, Ord v) => (s -> v) -> StreamT s -> [v] -> [v] -> StreamT s

Simulated Annealing skeleton. This requires a significant number of parameters due to the various stochastic components, temperatures and the need for a numerical valuation of solutions qualities. The parameters are;

1. a function to get the numerical value of a candidate solution
2. a function to provide a perturbation of a solution, with respect to some external factor, such as a random number, which is what the data type r is expected (though not required) to be.
3. a stream of values representing the temperature or cooling strategy
4. a stream of stochastic values
5. a stream of (stochastic) values for the creation of perturbations

Genetic Algorithms

ga :: ExpandT s -> ContraT s -> StreamT s -> StreamT s

Genetic Algorithm skeleton. In it's most general form this has three processes, which make up the parameters;

1. conversion of the stream of solutions into a stream of populations
2. recombination of elements of each population to give new solutions
3. mutation of elements of the stream to create variation

It is expected that each of these processes will be created via the composition of a number of other functions.

gaConfig :: Ord s => [Float] -> Int -> [Float] -> [Bool] -> ContraT s -> StreamT s -> StreamT s

The standard genetic algorithm configuration. The parameters are;

1. the selection distribution
2. the population size
3. a stream of random values to parametrise the selection routine
4. a stream of boolean values to indicate where to apply mutation
5. the recombination stream transformer
6. the mutation stream transformer