most recent 30 from http://mathoverflow.net 2013-05-19T03:07:53Z http://mathoverflow.net/feeds/question/24215 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24215/optimization-over-permutation pacificmoth 2010-05-11T08:20:06Z 2010-11-27T23:22:13Z

<p>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?</p>

http://mathoverflow.net/questions/24215/optimization-over-permutation/29556#29556 Kjetil B Halvorsen 2010-06-25T22:48:12Z 2010-06-25T22:48:12Z

<p>At lerast, simulated annealing is simple to program for your problem, so you could just try it ...</p>

http://mathoverflow.net/questions/24215/optimization-over-permutation/37689#37689 sleepless in beantown 2010-09-04T04:03:41Z 2010-09-04T04:52:10Z

<p>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.</p> <p>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.</p> <p>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.</p>

http://mathoverflow.net/questions/24215/optimization-over-permutation/40872#40872 Andrew D. King 2010-10-02T20:25:27Z 2010-10-02T20:25:27Z

<p>It may be the case that simulated annealing and genetic algorithms are relatively complicated to understand, bound and implement in this instance.</p> <p>Instead, a very easy starting point would be a simple hill-climbing algorithm.</p> <p>Start with an arbitrary (or better, random) initial permutation $\pi$.</p> <p>The set of <em>moves</em> is the set $M$ of permutations that you can reach by transposing two elements of the permutation.</p> <p>While there is a move that decreases $f$, </p> <ul> <li><p>Make the move to reach a new current permutation.</p></li> <li><p>Compute the new set of moves (or rather, their profits $f(\pi) - f(\pi')$ for a move reaching $\pi'$).</p></li> </ul> <p>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]$.</p> <p>Extremely simple and probably not <em>too</em> 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.</p>