If we have that information, then we can do some interesting things to exploit that knowledge to improve the performance of some search techniques. Our clustering based methods to measure the minimum (and average) distance between local optima is highly inconsistent, and this has a large effect on the overall performance of our methods.
Does anyone have any ideas or can someone point me towards work in the area of techniques to measure the size and shape of attraction basins in continuous search spaces?
Dear Stephen I used same idea of using knowledge about distribution for parameter setting in my article (A gravitational search algorithm for multimodal optimization). in multimodal problem in some case we have a knowledge known as Nich Radius that is the half of maximum Radius of a ball in search space that contain only one local optimum.
I think you can find 2 main axes of the feature space, then plot the scatter plot of your data in this 2 main axes.
Or you can do the former method after applying PCA.
What information about your objective / constraint functions is available? Do you have explicit expressions? Hessians? Higher derivatives? Which local search method do you use - usually the basins of attraction depend on that...
In my opinion the only answer (you'll don't like it) is following: find those all optima and do required statistics on this set.
From my recent own experience: suppose I am able to find all critical points of my objective function (interval computations are quite good at such task), that is those where gradient vanishes (for simplicity I don't consider constrained problems). Having such points the first task is to classify them as minima, maxima and saddle points. The objective function values will certainly tell us where are the global maximum and global minimum located. But I am also interested in remaining local minima! How to detect them with certainty without calculating second derivatives (because they do not exist or are too costly to compute)? The simple idea is to compare function values at given suspected point and its nearest neighbors, but it DOES NOT work reliably. First you have to decide who is and who is not the nearest neighbor (i.e. the radius of basin of attraction/repulsion is needed). But you also have to decide first which metric to use - the results will depend on it.
In summary that is not the reliable/promising way to solve the problem, I think.
As part of a larger technique, there is a highly limited budget of function evaluations. We'll probably pick several random lines through the search space and sample an even spread of points on each line. We'll start in a search space with known local optima points so that we can validate the estimates we derive.
Any additional thoughts?
Stephen, your proposal is next to trivial when the problem is in single dimension. But in higher dimension - I don't see its advantage over Monte Carlo approach. Well, not the most widely known version of MC based on any random number generator uniform on (0,1). There are the so called LP\tau random sequences uniformly distributed in [0,1]^n cube with additional property that their average distance has rather small variance. This property is called discrepancy (see Wikipedia for more details). Maybe this is what you are thinking of? Just in case I enclose appropriate Fortran90 routine. You'll find at least important references there, among other comments.
We're currently focusing on the CEC2013 benchmark in 30 dimensions.
@Marek, I'll take a look at your suggestion. Thanks.
Summarizing your problem as I have understood it: You have a bound constrained (or unconstrained) optimization problem with a black-box objective function f providing function values only. You want to get an assessment of the size (and probably rough shape) of the basin of attraction of a local optimum.
Since you want to keep the number of function evaluations small, probably an approach using local models for the objective function is a good start. You could use samples (set of points P) around the currently best point x (reusing already computed points close enough to x, adding new ones with some stochastic or quasi-stochastic scheme, e.g. Halton points or Niederreiter points as suggested above) to fit a quadratic model q(y) = (y-x)^T A (y-x) + a^T (y-x) + \alpha (weighting points according to their distance to x) - if there are too many parameters in the quadratic model, a possibility would be to fix some sparsity pattern for A (i.e. banded) to reduce the number of parameters.
This local model around x (if it is a local optimum) should have a=0, and the eigenvalues of A together with the deviation of the function values of points in P to get an estimate of the local (elliptic) shape around x of the basin of attraction and of the size of the basin - where for points p in P f(p) starts to be significantly smaller than q(p).
This could give something working for sufficiently smooth objective functions (C^2).
However, not all functions in the CEC2013 are smooth (if I remember correctly) so you might want to complement your local quadratic model by a local bundle, i.e., a model of the form c(y) = max_i b_i^T (y-x) + \beta_i to also capture functions which are locally badly represented by a quadratic function. c should satisfy that 0 \in convexhull({b_i | i}). The level sets of c(y) then give size and shape information for the basin of attraction. Here the level can be also chosen such that f(p) significantly smaller than c(p).
Repeating that modeling approach around the local optima you know can then provide statistical information and can give information on the regions where the information is still not sufficient to decide whether they might contain a local optimum or not.
Of course, none of these models and estimates will be foolproof (or even stable) as you only know finitely many points of f, and even if f is C^\infty it can have arbitrarily many local (and global) minima between these finitely many points. For a really stable estimate you would need curvature information of f, at least.
I will definitely look into that, but I still have the concern of how to handle attraction basins of different sizes and how to handle sub-basins -- e.g. a fitness landscape with two sinusoids where the period of one is a medium to large multiple of the other.
We'll report back after we have some results.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling