XPost: sci.math, comp.theory, bionet.biology.computational   
   From: roberto03@gmail.com   
      
   On Jul 21, 4:31 am, Ted Dunning  wrote:   
   > 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.   
      
   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. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)