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