XPost: sci.math, comp.theory, bionet.biology.computational
From: ted.dunning@gmail.com
On Jul 20, 2:47 am, roberto03 wrote:
> Hello, i am trying to apply the "simulated annealing" methodology to a
> problem where i have to determine an optimal (according to some cost
> function) sequence of N bits, k of which are 1 and (N-k) are 0; i can
> switch at will the 1's and the 0's between them, but the total number
> of 1's should be kept constant, say k = N_0, chosen by the user;
>
> now i'd like to know if anyone has applied this methodology to this
> kind of problem where one has to optimize a bit string in some sense.
>
> Thanks for any answer.
> Roberto.
>
Let me first warn that I really know little about this specific
problem.
But it does smell quite a bit like many coding problems where you are
trying to find a bit string that matches some criterion given partial
information. There are lots of interesting results to do with
probabilistic optimization of bit strings in the area of coding, but
some of these results depend on careful construction of the code.
There are also related sorts of issues in Ising systems.
Mackay discusses these in his book.
In general, the problem that you have with these systems is that the
set of bit strings that you want is not nicely connected. Yes, all
strings with a constant number of bits can be derived from all the
other ones by simple operations like repeated transpositions, but the
distance between strings can be pretty long. This means that it might
be preferable to optimize over all strings with an added penalty for
having the wrong number of bits. This is essentially the same as
using a Laplace multiplier in that the optimum is not changed while
the search space is expanded nicely. Once you do this, SA becomes a
very attractive option for the optimization itself.
[ comp.ai is moderated ... your article may take a while to appear. ]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
