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.
- iterativeImprover :: Optimisable s => StreamT s (List s) -> StreamT (List s) s -> StreamT s s
- firstFoundii :: Optimisable s => StreamT s (List s) -> StreamT s s
- maximalii :: Optimisable s => StreamT s (List s) -> StreamT s s
- minimalii :: Optimisable s => StreamT s (List s) -> StreamT s s
- stochasticii :: Optimisable s => StreamT s (List s) -> StreamT s s
- tabu :: Ord s => StreamT s (List s) -> StreamT s (List s) -> StreamT (List s) s -> StreamT s s
- standardTabu :: Ord s => Int -> StreamT s (List s) -> StreamT s s
- tabuFilter :: Eq s => StreamT s (List s) -> StreamT s (List s) -> StreamT s (List s)
- sa :: (Floating v, Ord v) => (s -> v) -> StreamT s s -> Stream v -> Stream v -> StreamT s s
- logCooling :: Floating b => b -> b -> [b]
- linCooling :: Floating b => b -> b -> [b]
- geoCooling :: Floating b => b -> b -> [b]
- saChoose :: (Floating v, Ord v) => (s -> v) -> v -> v -> s -> s -> s
- ga :: Int -> Float -> StreamT (List s) s -> StreamT (List s) (List s) -> StreamT s s -> StreamT s s
- aco :: Int -> StreamT (List s) a -> StreamT a s -> StreamT s s
- pheromoneDegrade :: Num a => a -> StreamT a a -> StreamT a a
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
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.
First found iterative improvement strategy. Fixes the choice function to
Maximal iterative improvement strategy. Since we seek the lowest possible value of solutions this
translates to fixing the choice function to
Minimal iterative improvement strategy. Fixes the choice function to
A general skeleton for TABU search. The three parameters are
- a stream transformer to create the stream of TABU lists (typically provided by
- a stream transformer to create the stream of neighbourhoods, in the same manner as seen in iterative improver
- a choice transformer to choose a single element from a pruned neighbourhood.
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
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.
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;
- a function to get the numerical value of a candidate solution
- 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.
- a stream of values representing the temperature or cooling strategy
- a stream of stochastic values
- a stream of (stochastic) values for the creation of perturbations
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.
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.
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.
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
because it requires the actual floating point quality values of solutions.
Ant Colony Optimisation
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.
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;
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.