Re: [boost] Proposal for a Differential Evolution C++ library

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