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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
2
|
|
|
1
|
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$,
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. |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
0
|
At lerast, simulated annealing is simple to program for your problem, so you could just try it ... |
||
|
|
|
0
|
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. |
|||||||||||||||
|
$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. – David Speyer May 11 2010 at 12:15