2
$\begingroup$

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$?)

$\endgroup$
2
$\begingroup$

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.

$\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.