0
$\begingroup$

I have 20 words. One permutation of these 20 words is the "correct" one. Assume I have a metric to find the correctness of the permutation.

I'm trying to figure out how to use simulated annealing to find the correct permutation of these 20 words. To begin with, I'm not even sure if I understand simulated annealing entirely, so I'll describe an algorithm that I think resembles simulated annealing.

For an arbitrary number (preferably a big number) of times, generate a random permutation and measure how correct it is. If the answer is more correct than any previous attempt, save the score and the sentence. Once we are done iterating, we have found something that it is probably close to the global maximum (the "correct" permutation).

I'm not sure where to go from there. Essentially, I have two questions.

  1. Does that sound like a good approach?
  2. Is my algorithm simulated annealing?
$\endgroup$
  • 1
    $\begingroup$ Your algorithm is "local search" or "hill climbing". In simulated annealing, you sometimes modify your answer even if this worsens the score. $\endgroup$ – Yuval Filmus Jun 29 '18 at 13:03
  • $\begingroup$ So, to change it to simulated annealing, would I go through the permutations iteratively (though not computationally possible)? $\endgroup$ – Zachary Delano Jun 29 '18 at 16:59
  • $\begingroup$ No. I suggest looking up some sources on simulated annealing. It's a standard technique so there are many descriptions available online. $\endgroup$ – Yuval Filmus Jun 29 '18 at 17:08
1
$\begingroup$

No, that's not simulated annealing. It's not really even close.

Whether it will be a good enough approach will depend on your metric. Since you haven't told us what the metric is, it's not really possible to say. In the worst case, if your metric is sufficiently horrible, you might need to explore all $20!$ permutations. In any case, usually the only reliable way to find out whether your approach is a good one is to implement and see what happens. There are few theorems that gives useful provable results about how effective the approach will be; instead, you need to use empirical evaluation.

$\endgroup$
  • $\begingroup$ So, this is a problem for school. I think that the metric is a query to his server, passing our permutation in the header. The server then (I think) will return a score indicating how correct the string is. The lower the score, the better the answer. $\endgroup$ – Zachary Delano Jun 29 '18 at 6:34
1
$\begingroup$

Simulated annealing, like gradient descent, needs a metric that identifies partial correctness. Unlike gradient descent, simulated annealing tries to escape local minima by randomly allowing state transitions that are not improvements.

Instead of randomly generating a new permutation each iteration, you should only generate a full random permutation at the beginning.

Just like gradient descent, in each iteration you must choose a random "neighbor" state that is close to the current state in the solution space. This is a crucial step that allows you to find a local minima before moving to a new "neighborhood". A simple and highly effective strategy for searching permutations is to swap the position of two randomly sampled words. This insures that the neighbors are very similar to each other and that any permutation can be reached in a reasonable number of transitions.

The "cooling schedule" is a function dependent on the time that controls the odds of keeping bad transitions. At the beginning lots of bad transitions are allowed. At the end the odds of allowing a bad transition are so low that it is effectively performing gradient descent. There is a proof that simulated annealing will arrive at an optimal solution if its cooling schedule is exponential and it is allowed to run indefinitely. This is a very good strategy even if you don't have an infinite number of CPU cycles to spare.

At each iteration you save a copy of the permutation if it is the best so far, because simulated annealing is not guaranteed to terminate on the best state it will visit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.