Algorithm that minimizes y=f(b1, ..., bn) where y is real, and bi{0,1}

#1 09-04-2008, 11:17 PM

Hello,

I am looking for some pointers and keywords for an algorithm that
minimizes a function that takes a sequence of bits as an input and
return a real number.

In addition, I would like to have the constraints that the number of
bits equal to one is fixed.

This function has some special properties. If b is a sequence of bits,
then f(b) >= f(b or additional bit). It means that for any sequence of
bits, if I set one additional bit to one, then the function decreases.

Do you have any pointer? I am not looking for a ready-made solution
(but will gladly take it if you have one), but keywords and hints.

Thanks in advance,
Tony

#2 09-05-2008, 12:06 AM

Antoine Bruguier <tony.bruguier@gmail.com> writes:

> Hello,
>
> I am looking for some pointers and keywords for an algorithm that
> minimizes a function that takes a sequence of bits as an input and
> return a real number.
>
> In addition, I would like to have the constraints that the number of
> bits equal to one is fixed.

This is good, since it reduces greatly the number of combinations,
since they're combinations with repetition.

A(n,2)= (n+1)!/2!/(n-1)! = (n+1)(n)/2

So perhaps you may envisage trying all the combinations in O(n^2)
instead of O(2^n).

If n is very big, you may try some kind genetic programming.

> This function has some special properties. If b is a sequence of bits,
> then f(b) >= f(b or additional bit). It means that for any sequence of
> bits, if I set one additional bit to one, then the function decreases.

This doesn't help, if you keep the number of set bits fixed.

> Do you have any pointer? I am not looking for a ready-made solution
> (but will gladly take it if you have one), but keywords and hints.
>
> Thanks in advance,
> Tony

--
__Pascal Bourguignon__ http://www.informatimago.com/

"Our users will know fear and cower before our software! Ship it!
Ship it and let them flee like the dogs they are!"

#3 09-05-2008, 03:48 AM

On Sep 5, 10:17*am, Antoine Bruguier <tony.brugu...@gmail.com> wrote:
> I am looking for some pointers and keywords for an algorithm that
> minimizes a function that takes a sequence of bits as an input and
> return a real number.
>
> In addition, I would like to have the constraints that the number of
> bits equal to one is fixed.

The basic algorithm probably should be
(1) start with a random string, with correct
number of bits set. (Instead of a random
string, you might try a local optimum
obtained iteratively with a simple "greedy"
policy.)
(2) choose two bits randomly, one zero, one one.
swap them, and score the result.
(3) Accept the change if the score is improved.
(4) Sometimes accept the change even when score
doesn't improve.
(5) Loop to (2) until you lose patience.

> Do you have any pointer? I am not looking for a ready-made solution
> (but will gladly take it if you have one), but keywords and hints.

It's probably obvious that step (4) above is where the cleverness
and magic will lie. Google for
Lin-Kernighan
Kernighan-Lin
Simulated annealing

James Dow Allen

#4 09-06-2008, 03:48 AM

"Antoine Bruguier" <tony.bruguier@gmail.com> wrote in message
>
> I am looking for some pointers and keywords for an algorithm that
> minimizes a function that takes a sequence of bits as an input and
> return a real number.
>
> In addition, I would like to have the constraints that the number of
> bits equal to one is fixed.
>
> This function has some special properties. If b is a sequence of bits,
> then f(b) >= f(b or additional bit). It means that for any sequence of
> bits, if I set one additional bit to one, then the function decreases.
>
> Do you have any pointer? I am not looking for a ready-made solution
> (but will gladly take it if you have one), but keywords and hints.
>
Go to my website and pull over the simulated annealing code. All you need to
do is supply a clone(), kill() and copy() function. These are just
housekeeping - clone() is a wrapper to malloc() and memcpy(), kill() is a
wrapper to free(), and copy() is a wrapper to memcp(). Then you need your
score() and mutate() fucntions. You already know the score(). Mutate(), as
James said, can just be a swap.

It will minimise any function, and the nice thing about it is that it works
out the temperature schedule using a heuristic. I've also got more
sophisticated methods of parallel annealing if that proves inadequate.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode