🚀 go-pugleaf

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.

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

On Jul 20, 10: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.
>

Dear Roberto

Have a look on the "Royal Road" problem, commonly used to test
Evolutionary Algorithms (e.g. Genetic Algorithms - GAs).
You have also an "oscillatory" harder version of the problem
(dynamic). For instance here solved sucessfully with Swarm
Intelligence approaches: http://www.laseeb.org/vramos/ref69.html
GA's normally solve the problem very well.

Best, Vitorino

~ v.ramos, LaSEEB, IST, http://www.laseeb.org/vramos/
[...] Interactions among many sporuliferous and ubiquitous
abstractions
may lead to increasing reality [...] Vitorino Ramos, 2001.

[ comp.ai is moderated ... your article may take a while to appear. ]

On Jul 20, 10: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.
>


Dear Roberto
Have a look on the "Royal Road" function problem usually used to test
and benchmark Evolutionary Algorithms (e.g. Genetic Algorithms - GAs).
There are harder versions as the Oscillatory Royal Road (dynamic
version) here

http://www.laseeb.org/vramos/ref69.html

solved efficiently by Swarm Intelligence. Anyway, GAs are a pretty
good aproach for the problem. I believe SA will also be.

Best, v.


~ v.ramos, LaSEEB, IST, http://www.laseeb.org/vramos/
[...] Interactions among many sporuliferous and ubiquitous
abstractions
may lead to increasing reality [...] Vitorino Ramos, 2001.

[ comp.ai is moderated ... your article may take a while to appear. ]