Safe Haskell | None |
---|
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
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
- a stream transformer to create the stream of TABU lists (typically provided by
window
) - 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.
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.
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;
- 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
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.