DREAM
Markov Chain Monte Carlo acceleration by Differential Evolution
DREAM
is a C++ program which
implements the DREAM algorithm for accelerating
Markov Chain Monte Carlo (MCMC) convergence using differential evolution,
by Guannan Zhang.
DREAM requires user input in the form of five C++
functions:
-
problem_size(), defines the sizes of problem parameters;
-
problem_value(), defines the value of problem parameters;
-
prior_density(), evaluates the prior distribution;
-
prior_sample(), samples the prior distribution;
-
sample_likelihood(), evaluates the log likelihood function.
Examples of such user input are listed below.
DREAM requires access to a compiled version of the
pdflib library, which can evaluate a variety of Probability
Density Functions (PDF's) and produce samples from them.
The user may wish to invoke this library when constructing
some of the user functions.
DREAM requires access to a compiled version of the
rnglib library, in order to generate random numbers.
An older implementation of the DREAM algorithm is available
as DREAM1; it requires a user main program and two input files.
The DREAM program was originally developed by Guannan Zhang, of
Oak Ridge National Laboratory (ORNL); it has been incorporated into
the DAKOTA package of Sandia National Laboratory, and forms
part of the ORNL package known as TASMANIAN.
Web Link:
A version of the DREAM library is available in
http://tasmanian.ornl.gov,
the TASMANIAN library, available from Oak Ridge National Laboratory.
Licensing:
The computer code and data files described and made available on this
web page are distributed under
the GNU LGPL license.
Languages:
DREAM is available in
a C version and
a C++ version and
a FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
DREAM1,
a C++ library which
is an older implementation of the DREAM algorithm for accelerating
Markov Chain Monte Carlo (MCMC)
convergence using differential evolution,
using a user function main program and two input files
to define the problem, by Guannan Zhang.
PDFLIB,
a C++ library which
evaluates Probability Density Functions (PDF's)
and produces random samples from them,
including beta, binomial, chi, exponential, gamma, inverse chi,
inverse gamma, multinomial, normal, scaled inverse chi, and uniform.
RANLIB,
a C++ library which
produces random samples from Probability Density Functions (PDF's),
including Beta, Chi-square Exponential, F, Gamma, Multivariate normal,
Noncentral chi-square, Noncentral F, Univariate normal,
random permutations, Real uniform, Binomial, Negative Binomial,
Multinomial, Poisson and Integer uniform,
by Barry Brown and James Lovato.
RNGLIB,
a C++ library which
implements a random number generator (RNG) with splitting facilities,
allowing multiple independent streams to be computed,
by L'Ecuyer and Cote.
Author:
Original FORTRAN90 version by Guannan Zhang;
C++ version by John Burkardt.
Reference:
-
Pierre LEcuyer, Serge Cote,
Implementing a Random Number Package with Splitting Facilities,
ACM Transactions on Mathematical Software,
Volume 17, Number 1, March 1991, pages 98-111.
-
Jasper Vrugt, CJF ter Braak, CGH Diks, Bruce Robinson, James Hyman,
Dave Higdon,
Accelerating Markov Chain Monte Carlo Simulation by Differential
Evolution with Self-Adaptive Randomized Subspace Sampling,
International Journal of Nonlinear Sciences and Numerical
Simulation,
Volume 10, Number 3, March 2009, pages 271-288.
Source Code:
Examples and Tests:
PROBLEM0 is a small sample problem, in 10 dimensions, with a
density that is the maximum of two gaussians centered at (-5,-5,...,-5)
and (5,5,...,5).
-
problem0.cpp,
is a user written file, containing 5 functions, which
define the problem data.
-
problem0_output.txt,
the output file.
-
problem0_chain00.txt,
a chain data file.
-
problem0_chain01.txt,
a chain data file.
-
problem0_chain02.txt,
a chain data file.
-
problem0_chain03.txt,
a chain data file.
-
problem0_chain04.txt,
a chain data file.
-
problem0_chain05.txt,
a chain data file.
-
problem0_chain06.txt,
a chain data file.
-
problem0_chain07.txt,
a chain data file.
-
problem0_chain08.txt,
a chain data file.
-
problem0_chain09.txt,
a chain data file.
-
problem0_gr.txt,
the Gelman-Rubin statistic file.
-
problem0_restart.txt,
the restart file.
PROBLEM1 is based on the first example in the Vrugt reference.
The Vrugt version involves 100 variables, with a multidimensional
normal distribution with specified mean vector and covariance matrix.
So far, I have simply set up the user routines, with just 5 variables,
and created a small stand-alone main program to test it. An important
issue was to find a simple and efficient way of handling the covariance.
We need to evaluate the matrix, compute its Cholesky factor,
find its determinant, just one time, and then provide this information
to any function that needs it, quickly and simply. In this version
of the code, I opted to define a "Covariance" structure, making it
an "extern" variable so the main program could access it.
-
problem1.cpp,
is a user written file, containing the 5 functions required
to define the problem data, as well as other functions to
set the covariance.
-
problem1_covariance.hpp,
an include file that defines the "Covariance" structure.
-
problem1_main.cpp,
a stand-alone main program that calls the user functions
to make some simple tests.
-
problem1_main_output.txt,
the output file from the standalone main program.
PROBLEM1C is a version of PROBLEM1 that uses a class to store
the covariance information, instead of a structure. I didn't like
this approach, since it seemed like, every time I needed some information,
I had to call a function and provide an array to store a copy of the
information, rather than simply accessing the information directly.
PROBLEM2 is based on the second example in the Vrugt reference.
The Vrugt version involves 10 variables, with a "twisted" Gaussian
density function.
-
problem2.cpp,
is a user written file, containing the 5 functions required
to define problem 2.
List of Routines:
-
MAIN is the main program for DREAM.
-
CHAIN_INIT starts Markov chains from a prior distribution.
-
CHAIN_INIT_PRINT prints the initial values for Markov chains.
-
CHAIN_OUTLIERS identifies and modifies outlier chains during burn-in.
-
CHAIN_WRITE writes samples of each chain to separate files.
-
CR_DIS_UPDATE updates the CR distance.
-
CR_INDEX_CHOOSE chooses a CR index.
-
CR_INIT initializes the crossover probability values.
-
CR_PROB_UPDATE updates the CR probabilities.
-
DIFF_COMPUTE computes the differential evolution.
-
DREAM_ALGM gets a candidate parameter sample.
-
FILENAME_INC increments a partially numeric file name.
-
GR_COMPUTE computes the Gelman Rubin statistics R used to check
-
GR_INIT initializes Gelman-Rubin variables.
-
GR_WRITE writes Gelman-Rubin R statistics into a file.
-
I4_MAX returns the maximum of two I4's.
-
I4_MIN returns the minimum of two I4's.
-
I4MAT_PRINT prints an I4MAT.
-
I4MAT_PRINT_SOME prints some of an I4MAT.
-
I4VEC_TRANSPOSE_PRINT prints an I4VEC "transposed".
-
I4VEC_ZERO_NEW creates and zeroes an I4VEC.
-
INPUT_PRINT prints the data from the input file.
-
JUMPRATE_CHOOSE chooses a jump rate from the jump rate table.
-
JUMPRATE_TABLE_INIT initializes the jump rate table.
-
JUMPRATE_TABLE_PRINT prints the jump rate table.
-
R8_ROUND_I4 rounds an R8, returning an I4.
-
R8BLOCK_ZERO_NEW returns a new zeroed R8BLOCK.
-
R8MAT_ZERO_NEW returns a new zeroed R8MAT.
-
R8VEC_COPY_NEW copies an R8VEC to a new R8VEC.
-
R8VEC_HEAP_D reorders an R8VEC into a descending heap.
-
R8VEC_SORT_HEAP_A ascending sorts an R8VEC using heap sort.
-
R8VEC_SUM returns the sum of an R8VEC.
-
R8VEC_TRANSPOSE_PRINT prints an R8VEC "transposed".
-
R8VEC_ZERO_NEW creates and zeroes an R8VEC.
-
RESTART_READ reads parameter sample data from a restart file.
-
RESTART_WRITE writes a restart file.
-
SAMPLE_CANDIDATE generates candidate parameter samples.
-
SAMPLE_LIMITS enforces limits on a sample variable.
-
STD_COMPUTE computes the current standard deviations, for each parameter.
You can go up one level to
the C++ source codes.
Last revised on 27 June 2013.