local-search-0.0.7: Generalised local search within Haskell, for applications in combinatorial optimisation.

Safe HaskellNone

Control.Search.Local.Strategies

Contents

Description

A collection of common strategies, built out of the combinators in the other libraries. For examples of their use, see Control.Search.Local.Example. ACO is the least well thought through.

Synopsis

Iterative Improvers

iterativeImprover :: Optimisable s => StreamT s (List s) -> StreamT (List s) s -> StreamT s sSource

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 :: Optimisable s => StreamT s (List s) -> StreamT s sSource

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

maximalii :: Optimisable s => StreamT s (List s) -> StreamT s sSource

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

minimalii :: Optimisable s => StreamT s (List s) -> StreamT s sSource

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

stochasticii :: Optimisable s => StreamT s (List s) -> StreamT s sSource

Stochastic iterative improvement strategy. The choice function is required to make a random choice from the neighbourhood at each step. This is implemented in terms of the select function, and uses a uniformCDF.

TABU Search

tabu :: Ord s => StreamT s (List s) -> StreamT s (List s) -> StreamT (List s) s -> StreamT s sSource

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 -> StreamT s (List s) -> StreamT s sSource

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. The choice function is set to map head. Implemented in terms of tabu.

I am not happy with this. What is really needed is a more flexible version of safe, so that rather than just returning the singleton it can return an alternative transformation of the neighbourhood. This is also some scope for using compiler rules here to balance usability with performance.

tabuFilter :: Eq s => StreamT s (List s) -> StreamT s (List s) -> StreamT s (List s)Source

Simulated Annealing

sa :: (Floating v, Ord v) => (s -> v) -> StreamT s s -> Stream v -> Stream v -> StreamT s sSource

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

logCooling :: Floating b => b -> b -> [b]Source

A logarithmic cooling strategy intended for use within simulated annealing. Broadly the first value is the starting temperature and the second a value between 0 and 1.

linCooling :: Floating b => b -> b -> [b]Source

Included for completeness, this is a cooling strategy for simulated annealing that is usually not very effective, a linear changing strategy. The first value is the starting temperature the second is the value to increase it by at each step. In order to have it reduce at each step, pass a negative value.

geoCooling :: Floating b => b -> b -> [b]Source

The most common cooling strategy for simulated annealing, geometric. The first value is the starting temperature, the second a value between 0 and 1, the cooling rate.

saChoose :: (Floating v, Ord v) => (s -> v) -> v -> v -> s -> s -> sSource

The traditional choice function used within simulated annealing. The parameters are; a function to yield quality of a solution, a value between 0 and 1 (stochastic expected) a temperature, the old solution and the possible future solution. Frustratingly this does not make use of Optimisable because it requires the actual floating point quality values of solutions.

Genetic Algorithms

ga :: Int -> Float -> StreamT (List s) s -> StreamT (List s) (List s) -> StreamT s s -> StreamT s sSource

Ant Colony Optimisation

aco :: Int -> StreamT (List s) a -> StreamT a s -> StreamT s sSource

A simple ACO implementation. It assumes that Ants will be released in groups, which is represented as the population size. It requires a transformation for generating pheromones, and creating new solutions from pheromone data. This will be problem specific.

pheromoneDegrade :: Num a => a -> StreamT a a -> StreamT a aSource

ACO's often use a degrading system, so that the next trail contains some part of the previous trails. This function provides this functionality, assuming that pheromone data can be summed like a number, and an initial state is provided. The stream transformation parameter represents a streamed degrade, for example;

 map (*0.1)

would give one tenth of the previous previous pheromone data added to the result. This is a stream transformation to allow for flexibility, for example adding a stochastic element.