simulated_annealing(n) 1.0 "flibs"

NAME

simulated_annealing - Implement a "simulated annealing" algorithm

TABLE OF CONTENTS

    TABLE OF CONTENTS
    SYNOPSIS
    DESCRIPTION
    DATA TYPES AND ROUTINES
    INTERFACE ISSUES
    COPYRIGHT

SYNOPSIS

use simulated_annealing
type(ANNEALING_PARAMETERS)
call set_parameters( params, update, initial_temp, temp_reduction, number_iterations, scale_factor, automatic_scaling, verbose)
call get_next_step( params, range, x, value, task
call find_minimum( params, range, x, func, value )

DESCRIPTION

The simulated_annealing module allows you to find the minimum of an arbitrary function of N variables using a straightforward simulated annealing algorithm.

The idea is that the variables can vary independently each within a given interval. For each set of values generated in this way, the function that is to be minimized is evaluated. The new set of values is accepted as the new estimate of the minimum in two situations:

The "temperature" is reduced by a constant factor after a given number of iterations, thus making the second case more and more improbable. If there are no new estimates, the iteration stops.

Theoretically, simulated annealing is able to find the global minimum of a function, but it would require infinite time to actually achieve it.

The module implements the basic technique and if the interface to the function is more complex than the subroutine find_minimum assumes, then you can use the code for that routine as a template for a customised version (see below for some ideas regarding such more general functionality).

DATA TYPES AND ROUTINES

The module defines a single data type, ANNEALING_PARAMETERS and several subroutines:

use simulated_annealing
The name of the module. The module itself uses the module select_precision to select single or double precision reals.

type(ANNEALING_PARAMETERS)
The type holds the parameters and state variables needed for the iteration. You can set the fields via the subroutine set_parameters.

call set_parameters( params, update, initial_temp, temp_reduction, number_iterations, scale_factor, automatic_scaling, verbose)
Subroutine to set the individual parameters for the algorithm. (All arguments are optional, except params and update)

type(ANNEALING_PARAMETERS) params
Derived type holding all parameters (and internal state variables) for the iteration.

logical update
If true, only the arguments that are present in the call are used to update the fields in params. Otherwise the structure is first initialised.

Note: this is probably not a very useful feature.

real(wp) initial_temp
Initial "temperature" (defaults to 1). A larger value means it will be easier for the vector representing the estimated minimum to wander about.

real(wp) temp_reduction
Factor by which to reduce the temperature (defaults to 0.95). A smaller value means the iteration will settle quicker, but possibly misses the global minimum. A value closer to 1 means the process will take longer, but the result will be more accurate.

integer number_iterations
Number of estimates to be examined before reducing the "temperature" (defaults to 100).

real(wp) scale_factor
Factor by which to scale the value before. The idea is that with a well chose scale factor the simulation is more or less independent from the actual values (defaults to 1).

logical automatic_scaling
Whether to first automatically determine a reasonable scale factor or not.

logical verbose
Whether to print the intermediate results before reducing the temperature or not.


call get_next_step( params, range, x, value, task
Low-level routine that exmaines the function value and decides what the next step will be.

type(ANNEALING_PARAMETERS) params
Derived type holding all parameters (and internal state variables) for the iteration.

real(wp), dimension(2,:) range
The minimum and maximum value for each independent variable.

real(wp), dimension(:) x
Current estimate of each independent variable where the minimum is attained.

real(wp) value
Value of the function at x.

integer task
Task to be performed: anneal_init, anneal_print, anneal_value or anneal_done.
call find_minimum( params, range, x, func, value )
Routine implementing the procedure to find the minimum.

type(ANNEALING_PARAMETERS) params
Derived type holding all parameters (and internal state variables) for the iteration.

real(wp), dimension(2,:) range
The minimum and maximum value for each independent variable.

real(wp), dimension(:) x
Upon return, estimate of each independent variable where the minimum is attained.

real(wp) value
Estimate of the minimum value of the function (the value at x).

real(wp) function func(x)
The function must have the interface:

 
    interface
        function f(x)
            use select_precision
            real(wp), dimension(:), intent(in) :: x
            real(wp)                           :: func
        end function
    end interface

INTERFACE ISSUES

The interface to the function to be minimized is fixed. This is an unfortunate limitation of Fortran 95. But there are at least two ways around it:

COPYRIGHT

Copyright © 2008 Arjen Markus <arjenmarkus@sourceforge.net>