Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > 0$. I would like to optimize $f$ over $\Pi$, i.e., $\Pi^*=\arg\min_{\Pi\in Perm(n)}f(X,\Pi)$. Is there any good approximate algorithm for this?
3 Answers
It may be the case that simulated annealing and genetic algorithms are relatively complicated to understand, bound and implement in this instance.
Instead, a very easy starting point would be a simple hill-climbing algorithm.
Start with an arbitrary (or better, random) initial permutation $\pi$.
The set of moves is the set $M$ of permutations that you can reach by transposing two elements of the permutation.
While there is a move that decreases $f$,
Make the move to reach a new current permutation.
Compute the new set of moves (or rather, their profits $f(\pi) - f(\pi')$ for a move reaching $\pi'$).
This will get you to a local minimum at a cost of $O(n^2)\cdot C(n)$, per move, where $C(n)$ is the cost of calculating $f(\pi)$ for a permutation of $[n]$.
Extremely simple and probably not too costly as a first step. You may be able to prove some sort of worst case bound between a local optimum and a global optimum.
Simulated annealing is a good answer, as given by Kjetil B Halvorsen. You can also try genetic algorithms to mix and cross-over multiple tries at different permutations.
Say that $\Pi_a$ and $\Pi_b$ are two permutations in your permutation space. If the function $f$ is not a black box, or if it is a black box which you are allowed to use as an oracle, find the value $f_a$ for $\Pi_a$ and $f_a$ for $\Pi_b$, or for a larger population of permutations. Take two or three of the highest scoring permutations based on the values of $f(X,\Pi_j)$ and use a genetic algorithm to cross-over between these two permutations.
Or take the single highest scoring permutation and then internally permute a short region of the permutation and recalculate $f$. Iterate as necessary. This presumes that $f$ if smoothly continuous and that you can use a hill-climbing style of approach to find local maxima or local minima, whichever you need in your case.
-
$\begingroup$ George Bernard Shaw once quipped that a second marriage was the triumph of optimimization over permutation. $\endgroup$ Sep 4, 2010 at 4:13
-
$\begingroup$ @will jagy: So that means Elizabeth Taylor, and others of her ilk, were striving to continually optimize over 7+ iterations as they were certain that they had been stuck in a local maximum (or minimum, depending on whose point of view you consider)? $\endgroup$ Sep 4, 2010 at 4:22
-
$\begingroup$ Yes, I think that is the inevitable conclusion. You can't argue with Shaw. $$ $$ I found the best version in an Australian website for woodworkers. Go figure. $$ $$ woodworkforums.com/f17/divorce-54547 $\endgroup$ Sep 4, 2010 at 4:28
-
$\begingroup$ Oh, one of your expressions between dollar signs is \f(X,\Pi_j) which does not work on my screen as \f does not mean anything to Latex $\endgroup$ Sep 4, 2010 at 4:33
-
$\begingroup$ @will, Thanks! I got carried away typing the backslashes in front of the capital Pi's and inserted a few extra accidentally. Edited and fixed. $\endgroup$ Sep 4, 2010 at 4:53
At lerast, simulated annealing is simple to program for your problem, so you could just try it ...
$f(\Pi) = \lambda(\Pi_1, \Pi_2, \ldots, \Pi_n)$
, this is the assignment problem en.wikipedia.org/wiki/Assignment_problem and there is an excellent algorithm. If there is a linear function $\mu$ such that $f(\Pi) = \sum \mu(\Pi_{i}, \Pi_{i+1})$, this is the Traveling Salesman problem and there is no good algorithm. Other situations, of course, may have intermediate difficulties. $\endgroup$