simulated annealing

simulated annealing

[Achim Gädke]

[-- Attachment #1: Type: text/plain, Size: 1256 bytes --]

  Hi folks!

I'm trying to solve a not well understood optimization problem with 
simulated annealing. I have some basic understanding by some talks and 
read the manual and gsl-1.3/siman/siman.c  and header.

But at least some questions are open:

- The variable gsl_siman_params_t.iters_fixed_T is unused, but explained,
- and the intended difference between n_tries and iters_fixed_T is not 
clear,
- also the difference between gsl_siman_solve_many and gsl_siman_solve 
is unclear (gsl_siman_solve_many is only found in the header)
- gsl_siman_solve algorithm: (the patch is attached)
* the run control output format is not as the manual states (x-(*x0_p) 
is missing), hence metric difference is not necessary.
* for loop condition should be for (i=0; i<params.iters_fixed_T; ++i), 
so this parameter makes sense
* E=Ef(x) should be evaluated before the while loop, because during the 
search new_E is already determined and copied to E, if new_x is accepted.
- gsl_siman_solve_many algorithm:
* are there extensions to the variable data length interface of 
gsl_siman_solve() ?

I like the aproach of all these object oriented helper functions - it 
can be wraped to c++ easily. But perhaps a struct is better than so many 
parameters.

Yours, Achim

[-- Attachment #2: siman.patch --]
[-- Type: text/plain, Size: 1384 bytes --]

Index: siman.c
===================================================================
RCS file: /cvs/gsl/gsl/siman/siman.c,v
retrieving revision 1.23
diff -C2 -r1.23 siman.c
*** siman.c	3 Aug 2002 19:36:14 -0000	1.23
--- siman.c	24 Mar 2003 13:54:13 -0000
***************
*** 45,49 ****
    int i, done;
    double T;
!   int n_evals = 0, n_iter = 0, n_accepts, n_rejects, n_eless;
  
    /* this function requires that either the dynamic functions (copy,
--- 45,49 ----
    int i, done;
    double T;
!   int n_evals = 1, n_iter = 0, n_accepts, n_rejects, n_eless;
  
    /* this function requires that either the dynamic functions (copy,
***************
*** 54,57 ****
--- 54,58 ----
  
    distance = 0 ; /* This parameter is not currently used */
+   E = Ef(x0_p);
  
    if (copyfunc) {
***************
*** 67,71 ****
    }
  
!   best_E = Ef(best_x);
  
    T = params.t_initial;
--- 68,72 ----
    }
  
!   best_E = E;
  
    T = params.t_initial;
***************
*** 77,86 ****
  
    while (!done) {
-     E = Ef (x);
  
      n_accepts = 0;
      n_rejects = 0;
      n_eless = 0;
!     for (i = 0; i < params.n_tries - 1; ++i) {
        if (copyfunc) {
  	copyfunc(x, new_x);
--- 78,86 ----
  
    while (!done) {
  
      n_accepts = 0;
      n_rejects = 0;
      n_eless = 0;
!     for (i = 0; i < params.iters_fixed_T; ++i) {
        if (copyfunc) {
  	copyfunc(x, new_x);

Re: simulated annealing

[Brian Gough]

=?ISO-8859-15?Q?Achim_G=E4dke?= writes:
 > I'm trying to solve a not well understood optimization problem with 
 > simulated annealing. I have some basic understanding by some talks and 
 > read the manual and gsl-1.3/siman/siman.c  and header.

I'll look at you patch more closely at the weekend but I will just say
that this section of the library is one of the very first parts of GSL
and so uses different approach -- ideally we should add a new-style
iterative interface to match the other modules.

Brian

Re: simulated annealing

[Brian Gough]

Achim_Gaedke writes
 > But at least some questions are open:
 > 
 > - The variable gsl_siman_params_t.iters_fixed_T is unused, but explained,
 > - and the intended difference between n_tries and iters_fixed_T is not 
 > clear,

As in your patch it looks like iters_fixed_T should be used in
gsl_siman_solve and n_tries is for gsl_siman_solve_many.

 > - also the difference between gsl_siman_solve_many and gsl_siman_solve 
 > is unclear (gsl_siman_solve_many is only found in the header)

At the time I didn't document it in the manual because I wasn't sure
whether it was finished/tested, since it isn't used in the test
programs.  I believe the idea is simply to run n_tries in parallel.

 > - gsl_siman_solve algorithm: (the patch is attached)

I've applied the patch, thanks.

 > - gsl_siman_solve_many algorithm:
 > * are there extensions to the variable data length interface of 
 > gsl_siman_solve() ?

I don't have any.  If gsl_siman_solve_many is useful we should update
it so it can be used and go in the manual as an "official" function.

-- 
Brian

Re: Simulated annealing

[Achim Gädke]

Rampas, Tomas wrote:

>Hello,
>I need a little help with a gsl_siman_solve function.
>I have defined the energy function, step function, metric function and print
>function and other stuffs. Compilation is OK. But when I go through the code
>in debug mode program never jump into the metric function.
>  
>
This is no error. gsl_siman_solve_many uses the metric function - but 
only for output.
gsl_siman_solve_many is not documented, it just makes many tries for one 
random walk step.

It is save to run gsl_siman_solve without metric function. You should 
implement the correct stepsize in do_step.

Yours, achim

Simulated annealing

[Rampas, Tomas]

Hello,
I need a little help with a gsl_siman_solve function.
I have defined the energy function, step function, metric function and print
function and other stuffs. Compilation is OK. But when I go through the code
in debug mode program never jump into the metric function.

I'm using Visual Studio 7.0 (.NET) on WinXP


Tomáš Rampas
---------------------------------------------------------------
gedas ČR s.r.o.
System analyst
TGM  840, 293 01 Mladá Boleslav, Czech Republic
Telefon/phone   +420-326-711-411
Telefax/fax       +420-326-711-420
rampas@gedas.cz
<http://www.gedas.com/>

simulated annealing

[Francisco J Molina]

I am trying to use the Simulated Annealing function under C++ and I am
trying to avoid the use of the functions of C that allocate/deallocate
dynamic memory ( malloc,...).

My configuration could be described with a pair of vectors ( one int
and the other one float ) and an integer number.
The problem is that the size of these vectors is not known at compiling
time but at
running time, so that, I can not declare my configuration as an
structure.

I thought of passing 

lengthRealVector * sizeof( float ) + lengthIntVector * sizeof( int ) +
sizeof( int )

as 

element_size 

to 

gsl_siman_solv

and then using the following declarations within the functions energy
and
take-step:

   static int* pInteger;
   static double* realVector;
   static int* intVector;

   pInteger = ( int* ) pOinter;
   realVector = ( double* )( pInteger + 1 );
   intVector = ( int* )( realVector + lengthRealVector );

where pOinter is the void pointer to the configuration ( argument ).
With this fixed-size approach, the problem was to create the initial
configuration.
Do you know if there is any way to solve this problem( trying to make
gsl_siman_solv work in the fixed-size mode, when the size of the
configuration is part of the input and the configuration is described
by several elements of different data types ) 

Second question:

In the non-fixed-approach, can I use new and delete in the functions
to clone, create and delete configurations?

Thank you for reading this long email

Re: Simulated Annealing

[Brian Gough]

Andrey V. Panov writes:
 > gsl_siman_solve() uses gsl_siman_copy_t copyfunc(), 
 > gsl_siman_copy_construct_t copy_constructor(), 
 > gsl_siman_destroy_t destructor() or memcpy() functiions.
 > Is it better to implement gsl_siman_solve() through gsl_vector_X functions 
 > and use gsl_vector * in energy, step functions parameters? I am working on 
 > this.

It's designed to handle arbitrary data structures, including mixed
integer/real, lists, trees etc, so it takes void *.  

If you are working with vectors it should be possible to make small
wrappers of the gsl_vector_alloc, gsl_vector_memcpy and
gsl_vector_free for the copyfunc, copy_constructor and destroy
functions.

Brian

Re: simulated annealing

[Brian Gough]

Francisco J Molina writes:
 > Do you know if there is any way to solve this problem( trying to make
 > gsl_siman_solv work in the fixed-size mode, when the size of the
 > configuration is part of the input and the configuration is described
 > by several elements of different data types ) 

Hi,
I don't think there is any clean way to do this in C.

 > Second question:
 > 
 > In the non-fixed-approach, can I use new and delete in the functions
 > to clone, create and delete configurations?

Possibly, but perhaps it would involve fiddling with casts.

The simulated annealing algorithm is fairly short so I'd recommend
converting it into C++ for simplicity.

Brian

Simulated Annealing

[Andrey V. Panov]

gsl_siman_solve() uses gsl_siman_copy_t copyfunc(), 
gsl_siman_copy_construct_t copy_constructor(), 
gsl_siman_destroy_t destructor() or memcpy() functiions.
Is it better to implement gsl_siman_solve() through gsl_vector_X functions 
and use gsl_vector * in energy, step functions parameters? I am working on 
this.

-- 
Andrey V. Panov
http://canopus.iacp.dvo.ru/~panov/

Re: simulated annealing

[Brian Gough]

Francisco J Molina writes:
 > Do you know if there is any way to solve this problem( trying to make
 > gsl_siman_solv work in the fixed-size mode, when the size of the
 > configuration is part of the input and the configuration is described
 > by several elements of different data types ) 

Hi,
I don't think there is any clean way to do this in C.

 > Second question:
 > 
 > In the non-fixed-approach, can I use new and delete in the functions
 > to clone, create and delete configurations?

Possibly, but perhaps it would involve fiddling with casts.

The simulated annealing algorithm is fairly short so I'd recommend
converting it into C++ for simplicity.

Brian

simulated annealing

[Francisco J Molina]

I am trying to use the Simulated Annealing function under C++ and I am
trying to avoid the use of the functions of C that allocate/deallocate
dynamic memory ( malloc,...).

My configuration could be described with a pair of vectors ( one int
and the other one float ) and an integer number.
The problem is that the size of these vectors is not known at compiling
time but at
running time, so that, I can not declare my configuration as an
structure.

I thought of passing 

lengthRealVector * sizeof( float ) + lengthIntVector * sizeof( int ) +
sizeof( int )

as 

element_size 

to 

gsl_siman_solv

and then using the following declarations within the functions energy
and
take-step:

   static int* pInteger;
   static double* realVector;
   static int* intVector;

   pInteger = ( int* ) pOinter;
   realVector = ( double* )( pInteger + 1 );
   intVector = ( int* )( realVector + lengthRealVector );

where pOinter is the void pointer to the configuration ( argument ).
With this fixed-size approach, the problem was to create the initial
configuration.
Do you know if there is any way to solve this problem( trying to make
gsl_siman_solv work in the fixed-size mode, when the size of the
configuration is part of the input and the configuration is described
by several elements of different data types ) 

Second question:

In the non-fixed-approach, can I use new and delete in the functions
to clone, create and delete configurations?

Thank you for reading this long email

Re: Simulated Annealing

[Brian Gough]

Andrey V. Panov writes:
 > gsl_siman_solve() uses gsl_siman_copy_t copyfunc(), 
 > gsl_siman_copy_construct_t copy_constructor(), 
 > gsl_siman_destroy_t destructor() or memcpy() functiions.
 > Is it better to implement gsl_siman_solve() through gsl_vector_X functions 
 > and use gsl_vector * in energy, step functions parameters? I am working on 
 > this.

It's designed to handle arbitrary data structures, including mixed
integer/real, lists, trees etc, so it takes void *.  

If you are working with vectors it should be possible to make small
wrappers of the gsl_vector_alloc, gsl_vector_memcpy and
gsl_vector_free for the copyfunc, copy_constructor and destroy
functions.

Brian

Simulated Annealing

[Andrey V. Panov]

gsl_siman_solve() uses gsl_siman_copy_t copyfunc(), 
gsl_siman_copy_construct_t copy_constructor(), 
gsl_siman_destroy_t destructor() or memcpy() functiions.
Is it better to implement gsl_siman_solve() through gsl_vector_X functions 
and use gsl_vector * in energy, step functions parameters? I am working on 
this.

-- 
Andrey V. Panov
http://canopus.iacp.dvo.ru/~panov/

Re: Simulated annealing

[Brian Gough]

Adam Kleczkowski writes:
 > What is the current status of 'simulated annealing' part of GSL?
 > The example program (sim_test.c) does not agree with the help
 > file(s) in the call to gsl_siman_solve. It also contains just a
 > simple 1D case, and all the more complicated 1D, 2D, 3D cases are
 > commented out. gsl_siman_Usolve (used in more complicated part of
 > sim_test.c) does not exist in the library.
 >  I need to use simulated annealing for parameter fitting. I could
 > probably implement it from scratch (it is not too difficult), but
 > it would be nice to simply call a GSL function.

The simulated annealing needs to be cleaned up, also the documentation
is out of date. 

In the meantime siman_tsp.c is a working program that you can use as
an example.

Brian

Simulated annealing

[Adam Kleczkowski]

What is the current status of 'simulated annealing' part of GSL? The example
program (sim_test.c) does not agree with the help file(s) in the call to
gsl_siman_solve. It also contains just a simple 1D case, and all the more
complicated 1D, 2D, 3D cases are commented out. gsl_siman_Usolve (used in
more complicated part of sim_test.c) does not exist in the library.

I need to use simulated annealing for parameter fitting. I could probably
implement it from scratch (it is not too difficult), but it would be nice to
simply call a GSL function.

Thanks in advance,
Adam

--
Adam Kleczkowski
Dept. Plant Sciences, University of Cambridge
e-mail: adam@kleczkowski.net
http://mathbio.com/ (work) http://kleczkowski.net/ (private)

Re: Simulated annealing

[Brian Gough]

Adam Kleczkowski writes:
 > What is the current status of 'simulated annealing' part of GSL?
 > The example program (sim_test.c) does not agree with the help
 > file(s) in the call to gsl_siman_solve. It also contains just a
 > simple 1D case, and all the more complicated 1D, 2D, 3D cases are
 > commented out. gsl_siman_Usolve (used in more complicated part of
 > sim_test.c) does not exist in the library.
 >  I need to use simulated annealing for parameter fitting. I could
 > probably implement it from scratch (it is not too difficult), but
 > it would be nice to simply call a GSL function.

The simulated annealing needs to be cleaned up, also the documentation
is out of date. 

In the meantime siman_tsp.c is a working program that you can use as
an example.

Brian

Simulated annealing

[Adam Kleczkowski]

What is the current status of 'simulated annealing' part of GSL? The example
program (sim_test.c) does not agree with the help file(s) in the call to
gsl_siman_solve. It also contains just a simple 1D case, and all the more
complicated 1D, 2D, 3D cases are commented out. gsl_siman_Usolve (used in
more complicated part of sim_test.c) does not exist in the library.

I need to use simulated annealing for parameter fitting. I could probably
implement it from scratch (it is not too difficult), but it would be nice to
simply call a GSL function.

Thanks in advance,
Adam

--
Adam Kleczkowski
Dept. Plant Sciences, University of Cambridge
e-mail: adam@kleczkowski.net
http://mathbio.com/ (work) http://kleczkowski.net/ (private)