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

Control.Search.Local.Distributions

Description

Selection routines have been made generic through the `select` and `select'` functions, which are parametrised by probability distributions. This module provides functions for constructing and manipulating some example probability distributions.

Synopsis

# Types

type Distribution = [Double]Source

The data type for a discrete probability distribution.

The number of elements being selected between will often vary (such as in improving neighbourhoods), so it will often be necessary to construct distributions with some constant properties, but varying the length.

# Distributions

Parametrised as follows;

1. mean
2. standard deviation
3. size

The function generates the CDF of a Normal distribution, using the mean and standard deviation, over the range of discrete values [0 .. size]. The result is processed by the `fixEnd` function, so the final entry in the distribution is always 1. Over larger enough values of size this should be fine.

Parametrised as follows;

1. mean
2. size

This function generates the CDF of a Poisson distribution with the specified mean, over the range of discrete values [0 .. size]. This function includes a call to `fixEnd` so that the final value of the distribution is always 1.

A function to generate a Uniform distribution CDF over the range [0 .. size]. For safety this includes `fixEnd`, though this should have no effect.

It is more likely that when always choosing the first element of list of choices `head` will be employed, but this has been included for completeness. This is a CDF.

Like `firstChoice` it is more likely that `last` will be used for this effect. This is also a CDF.

# Distribution Manipulation

To enable the construction of more exotic distributions from existing distributions. The basic function combines them with equal weight on each component. For example;

``` addDistributions [[0,0.5,1],[1,1,1]] = [0.5,0.75,1]
```

Compare this with `addDistributions'`.

addDistributions' :: [Double] -> [Distribution] -> DistributionSource

A more flexible variation upon `addDistributions` which allows the programmer to specify the weights to merge the distributions with. For example;

``` addDistributions [0.3,0.7] [[0,0.5,1],[1,1,1]] = [0.7,0.85,1]
```

Combines `DistributionMaker`s. This combines them with equal weighting.

Combines `DistributionMaker`s but weights each one.

# Helper code

This is parametrised as follows;

1. mean
2. k

The function generates the probability of element k being chosen from a Poisson distribution with the specified mean.

This is quite a slow function and should probably be memoized in the future.

The basic CDF functions (e.g. `poissonCDF'`) often do not yield complete CDFs. The distributions that are produced tend to 1 in the last position of the list, but do not actually get there. For these to be used practically, the last value of the list should be replaced with 1. This is a bodge, but under most circumstances should not adversely effect results.

Parametrised as follows;

1. mean
2. standard deviation
3. size

The function generates the CDF of a Normal distribution, using the mean and standard deviation, over the range of discrete values [0 .. size]. This function is raw, and does not use `fixEnd`.

Parametrised as follows;

1. mean
2. size

This function generates the CDF of a Poisson distribution with the specified mean, over the range of discrete values [0 .. size]. This function gives the raw distribution.

The raw Uniform distribution without using `fixEnd`.

# Debug code

A function included for debug purposes. I expect that many users will be more comfortable using CDFs, but happier thinking in terms of PDFs. Use in conjunction with `distribution2SVG` to see what a distribution looks like.

A function included for debug purposes, to allow a user to visualise a distribution. It generates a string, which can be stored in a file as SVG.