Greetings, and apologies for cross-posting.
A PhD student, Dimitris Fouskakis, and I are working on a large global
optimization problem arising in Bayesian decision theory applied to an
application in health policy.
Given binary input variables ( x1, ..., xp ), the problem is to find as
many as possible of the k best choices of the xi in a fixed (and rather
small) amount of CPU time, where "best" is with respect to maximizing a
particular real-valued function f( x1, ..., xp ).
For example, with p = 83 and k = 20 there are 2**p (about 10**25) possible
choices of ( x1, ..., xp ), from ( 0, ..., 0 ) to ( 1, ... 1 ); call each
of these choices a "model". Imagine rank-ordering from largest to smallest
all 2**p values of f( x1, ..., xp ). We want to find as many as possible of
the 20 biggest such values of f in a small amount of CPU time, and the
particular ( x1, ..., xp ) choices associated with these f values.
It takes about 1 second at 400 MHz to evaluate f once in our problem, so
brute-force enumeration of all possibilities is far from feasible for us.
We have instead been looking at a variety of stochastic optimization
methods, including simulated annealing (SA), tabu search (TS), and genetic
algorithms (GA).
Our initial work with GA has been based on what might be termed a plain or
"vanilla" implementation of the algorithm, not far from the initial plan
laid out by, e.g., Holland JH (1975: Adaptation in natural and artificial
systems. Ann Arbor: University of Michigan Press). We wish to publish
results in the statistics and/or optimization literature comparing GA with
SA and TS on our problem, and we are aware that we may be criticized for
using such an "old" version of GA.
Questions: (1) Are you aware of any specific references in the open
literature to more recent versions of GA that might be expected to work
particularly well on problems like ours? (2) More generally, if we wish to
conduct a literature search of our own to answer question (1), can you
recommend to us one or two recent and good survey papers which have tried
to summarize the current state of play in GA?
In either or both cases, if the answer is yes, could you please send any
such references to me?
Many thanks in advance for any help you can provide.
Best wishes, David Draper
============================================================================
Professor David Draper
Head of Statistics Group web http://www.bath.ac.uk/~masdd
Department of email d.draper@maths.bath.ac.uk
Mathematical Sciences phone UK (01225) 826 222, nonUK +44 1225 826 222
University of Bath fax UK (01225) 826 492, nonUK +44 1225 826 492
Claverton Down
Bath BA2 7AY England
============================================================================
-----------------------------------------------------------------------
This message was distributed by s-news@wubios.wustl.edu. To unsubscribe
send e-mail to s-news-request@wubios.wustl.edu with the BODY of the
message: unsubscribe s-news
|