Cheap and Secure Web Hosting Provider : See Now

What is the number of degrees of freedom of my problem in this Simulated Annealing context?

, , No Comments
Problem Detail: 

I'm trying to apply a Simulated Annealing technique to solve my (NP-complete) optimization problem. I'm using this book to help myself out.

In the section on Simulated Annealing and more specifically in the section on practical suggestions for beginners, the authors state:

Change in temperature stage: can take place as soon as one of the 2 following conditions is satisfied during the temperature stages:
- $ 12 \cdot N$ pertubations accepted;
- $ 100 \cdot N$ pertubations attempted,
$N$ indicating the number of degrees of freedom (or parameters) of the problem

Because I'm still relatively new to Simulated Annealing, I'm willing to trust this guideline blindly for a first implementation.

A (non-optimal) solution to the problem is represented by a vector of integers $\mathbf{[a_1, a_2, a_3, ..., a_n]}$ with $ 0 < a_i \leq f(i), \forall i \in \mathbb{N} : 0 < i \leq n$.

What is the degree of freedom ($N$) here? Is it $n$?

Additionally, for this not to be a yes/no question:
Intuitively, why is this a bad/mediocre/good (pick one) guideline ? (i.e. why $\underline{12} \cdot N$ and $\underline{100} \cdot N$?)

Asked By : Auberon
Answered By : Yuval Filmus

The parameter $N$ is the length of the vector you're running simulated annealing on. In your case, $N = n$. The values $12,100$ are completely heuristic, and were probably chosen experimentally.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55480

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback