Boost logo

Boost :

Subject: Re: [boost] Proposal for a Differential Evolution C++ library
From: Topher Cooper (topher_at_[hidden])
Date: 2012-01-11 13:25:51


On 1/10/2012 2:00 PM, Topher Cooper wrote:
>
> I think delaying inclusion until all this has been nailed down would
> be a mistake. But thinking about traits, concepts, standards (e.g.,
> does optimization mean minimization or maximization?), decisions about
> how both algorithm specific and somewhat shared algorithm
> parametrization (e.g., cooling schedule, population size) are to be
> specified, mutator interfaces (parametrized, presumably, with
> candidate solution representation), and certainly things that I have
> not yet considered, before locking it down, would probably be useful
> -- avoiding having to put too thick an adaptor interface around it later.

I was thinking about this as I was going to sleep last night. I had
some thoughts about the direction this should go. This is no where near
anything that could be called a design, but this what I thought of as a
start.

The key, I think, is separation of concerns -- even when those concerns
can't entirely be separated.

The idea of having a function prototype for the objective function that
looks anything like:

> The way I see it, the only common point between different optimization
> algorithms (if they are generic enough) is the objective function,
> which should have a very simple prototype:
>
> double f( std::vector< double > );

while natural for this narrow context, is, in the context of a more
general interface, wrong.

The central entity, I think, is an object representing /a point in the
solution space/, i.e., a candidate solution or partial solution with
additional information such as history. Then, similarly to the
algorithms library, metaheuristics like genetic algorithms, neural nets,
etc. could be written abstractly to operate on these. I'm really not
ready for any solid design, obviously, but, if we call the point in the
solution space SSPoint (presumably, we are dealing with template duck
typing rather than class heirarchy), the objective function interface
could look something like:

double SSPoint::objective(SSPoint::ObjectiveSelector dim =
SSPoint::ObjectiveSelector::Primary); // ObjectiveSelector probably an enum

template < size_t N>
std::array< double, N > SSPoint::objective(std::array<
SSPoint::ObjectiveSelector, N >); // Other sequence in/out alternatives
in addition or instead of.

(Here is where the real handwaving starts):

SSPoint would (in my thinking) also provide lists of operators (mutators
and/or combiners) filtered by an appropriate filter on the request. An
operator might be deterministic (e.g., it might, internally, execute
code equivalent to "private_v[13] *= 1.3;") or non-deterministic (e.g.,
"private_v[13] *= 1.0 + this->stdNrmGen()*0.1;"). The filters would
restrict the kinds of operators (e.g., you wouldn't want a combiner for
simulated annealing). There would also be additional information with
the operator that would allow the metaheuristic to choose non-uniformly
among them. Or perhaps instead of a filter there would be a
specification for how to choose an operator. Combiners add some
complexity here, since the characteristic of the other SSPoint (or
SSPoints) might effect the selection criteria (even if we are not using
biased operator choice, we might want to count a combiner with three
candidate partners as if it were three operators in order to act as a
uniform selector). Hand wave, hand wave ...

The separation of concerns is that SSPoint understands its own
representation, how it can be manipulated and how it can be measured
(not only the objective function(s), but also information necessary for
heuristic weighting, solution similarity, mate selection, local optima
detection, schedule adjustment, and termination criteria) while the
metaheuristic understands its requirements and how to sequence and
select a series of operations on a point in a solution space to look for
an optima. In practice, I imagine, there generally would be concurrent
development of the two interacting pieces, but separation of concerns
does not mean that choices in the different domains are not influenced
or determined by global knowledge of the requirements in their interaction.

There is a lot to pin down in terms of concepts, traits etc. and such
fundamentals as whether an operator is applied destructively. In the
long term, I could imagine (if this catches on sufficiently) a rich set
of adaptors and building blocks for various metaheuristics and various
kinds of problem representations, plus perhaps useful tools and data
structures of more general use (e.g., a Fibonacci heap for efficient
prioritization with frequent insertions and deletions between pops,
packages for keeping solution histories and doing backtracking or taboo
search (keeping a list of recent solutions and blocking,
deterministically or nondeterministically repeats or near repeats), or
coordinating distributed solvers).

But maybe this is too ambitious.

Topher Cooper


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk