🚀 go-pugleaf

On Jul 21, 4:31 am, Ted Dunning <ted.dunn...@gmail.com> wrote:
> On Jul 20, 2:47 am, roberto03 <robert...@gmail.com> 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.

this could be a quite good way to solve the problem
may you point me to some good reference about it ?
thanks in advance

>
> 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. ]