Details and Options
The cost function f is applied to complete orderings of elems and must return a real number.
The result {fmin,ordering} satisfies fmin==f[ordering].
The following options can be given:
| Method | Automatic | method to use |
| MaxIterations | Automatic | maximum number of cost function evaluations |
| RandomSeeding | Inherited | seeding of the pseudorandom generator |
| "RandomRestarts" | None | additional runs starting from random reorderings of the input |
| "CandidateGeneration" | {"Swaps", "SegmentReverse", "ElementMove"} | random moves used by heuristic methods to generate candidate orderings |
Possible settings for
Method include:
| "Exhaustive" | evaluate every distinct ordering; guaranteed to find a global minimum |
| "LocalSearch" | random-neighbor hill climbing from a random starting ordering |
| "SimulatedAnnealing" | simulated annealing with geometric cooling |
| "MetropolisHastings" | Markov chain Monte Carlo search at a fixed temperature |
With
Method→Automatic,
"Exhaustive" is used when
elems has 8 or fewer elements,
MaxIterations is
Automatic or at least the number of distinct orderings of
elems, and neither
"RandomRestarts" nor
"CandidateGeneration" is given. Otherwise
"SimulatedAnnealing" is used.
With
MaxIterations→Automatic,
"Exhaustive" evaluates
f up to
n! times for a list of length
n, at most
Max[1000,100 n2] times for heuristic methods.
Possible settings for "RandomRestarts" include:
| None | a single run starting from the order given |
| n | one run from elems, then n runs from random reorderings of elems; the best result is returned |
| {n,m} | one run from elems, then batches of n random restarts; another batch is run only if the previous one improved the best result, up to m batches |
MaxIterations applies to each run separately.
Heuristic methods generate candidate orderings by applying random moves to the current ordering. Moves are chosen randomly from the methods given by "CandidateGeneration"; these can be any combination of:
| "Swaps" | exchange two elements |
| "NeighborSwaps" | exchange two adjacent elements |
| "SegmentReverse" | reverse the order of a contiguous segment |
| "ElementMove" | move one element to a new position |
Heuristic methods may return a local minimum.
Method→{"LocalSearch",subopts} supports the following suboptions:
| "SearchBreadth" | Automatic | maximum number of candidates tried at each step |
| "SearchDepth" | 1 | maximum number of steps in an excursion |
| "ImprovementPool" | 1 | number of improving candidates to collect before taking the best |
| "MaxExcursions" | Infinity | consecutive excursions without a lower cost before stopping |
"LocalSearch" proceeds by testing candidate orderings for improvement, constrained by "SearchBreadth" and "ImprovementPool". The best improvement is used and the process restarts. If no improvement is found, an excursion is started into the best candidate found (which may be worse than the current ordering) in an attempt to escape local minima. The excursion can recursively continue up to "SearchDepth" before returning to the best ordering so far. The number of such excursions is constrained by "MaxExcursions"
"ImprovementPool" → 1 takes the first improvement found, and "ImprovementPool" → Infinity takes the best improvement among all candidates (constrained only by "SearchBreadth").
Orderings already visited during the current excursion are not revisited. Such candidates are not evaluated, but count toward
MaxIterations.
Method→{"MetropolisHastings",subopts} supports the following suboption:
| "Temperature" | Automatic | fixed temperature of the search |
"MetropolisHastings" and "SimulatedAnnealing" use the same basic process. They always accepts a candidate that does not increase the cost, and accepts one that increases the cost by
d with probability
Exp[-d/t], where
t is the temperature. The difference is that In
"SimulatedAnnealing", the temperature
t decays geometrically so that the algorithms settles into a minumum and in "MetropolisHastings" it remains fixed so that the search keeps exploring . In both cases the best ordering visited is returned.
With
"Temperature"→Automatic,
t is a tenth of the mean change in cost of random candidates generated from the starting ordering.
Every move used by
"CandidateGeneration" is as likely to be proposed as the move that undoes it, so no Hastings correction is needed, and the search samples orderings with probability proportional to
Exp[-f[ordering]/t].
"RandomRestarts"→n is equivalent to "RandomRestarts"→{n,1}.