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 |
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 mimina. The exclusion 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 by only by "SearchBreadth").
Orderings already visited during the current excursion are not revisited. Such candidates are not evaluated, but count toward MaxIterations.