First, the size of the search space grows exponentially. For each dimension d, there are two extremes, so there are 2^d "corners" of the search space. For d = 1000, there are 2^1000 ~= 10^9 corners/quadrants to the search space. For a typical function evaluation limit of 10,000*d = 10^8, there aren't even enough function evaluations to sample each quadrant.
Second, there are scaling issues. Assuming that population size is also a function of dimensionality, what is the convergence rate as a function of population size -- general experimental evidence suggests it's super-linear, but are there any more precise measurements on this? So, let's estimate quadratic to cubic growth here.
Third, there are function evaluation issues. Non-separable benchmark functions which use rotation matrices are quadratic in cost. This seems like a minimum for any interesting real-world problems.
The last two issues for population-based metaheuristics lead to a d^4+ growth, so of course population size and generation counts are limited. However, these limitations occur in the context of a search space growing in size exponentially. To get any convergence, we accept premature convergence in these large complex search spaces.
Is there a conceptual limit for how much we can actually explore? For function evaluations (FE) 2^d? How much greater does FE have to be than 2^d to achieve a meaningful search/sampling of a search space?
Steven, first of all, let me correct a typo in your statement: 2^1000 >>>> 10^9. Early optimization researchers did not invent the name "curse of dimensionality" for nothing!. In general, this curse of dimensionality and the bounds you mentioned, clearly imply that you cannot hope to "guarantee" that your meta-heuristic method has found the global minimum to your problem, unless you have a good lower bound to compare it with. Without a "provable" lower bound (that must be tight-enough), you cannot possibly say that "I let my algorithm search 10 billion points in the search space, and this should be enough". If your problem doesn't admit any good lower bounds, then the best you can do is to at least make sure that your solution is "locally optimal", i.e. either you go to a stationary point (satisfying Karush-Kuhn-Tucker conditions or even better second-order conditions), or if your problem is non-smooth objective you work with sub-gradients (bundle methods?), or if your problem is discrete, you define some notion of neighborhood for your solutions, and make sure your final solution is "the best in the 'hood..." using some hill-climbing or other local-search procedure.
If you have lower bounds, you can use Branch&Bound methods for whatever type of problem you have, and either let it run to completion (but may take exponential time), or else stop it after you have become sick-and-tired of waiting, or else, when the solution is within some gap of a lower bound your method has computed.
Oh, and don't forget, for the toughest problems around, all you have to do is come up with a solution that is better than the ones published in the literature: if you can do it fast enough, that's enough to get you published :-)
Oops. 2^10 ~= 10^3, so 2^30 ~= 10^9. Somehow wanting to believe they were even close to the same scale caused me to do that wrong.
So, what does this say about using approximately 10^8 function evaluations on the LSGO (d = 1000) benchmark functions? Sounds like any search technique would be about as effective as picking two random local optima on a d = 30 problem.
Well, I am not an expert in this area but I want to point you that, you may try to look in the area of information based complexity where it develops lower bounds on the number of needed pointe (in continuous functions only) that you need to guarantee approximation to the function. Given such lower bound, you can't hope "In general" to get any guarantees.
Many optimization methods suffer from the ``curse of dimensionality'', which implies that their performance deteriorates quickly as the dimension of the search space increases. There are several reasons that cause this phenomenon.
First, the solution space of a problem often increases exponentially with the problem dimension and more efficient search strategies are required to explore all promising regions within a given time budget. The evolutionary computation or swarm intelligence is based on the interaction of a group of solutions. The promising regions or the landscape of problems are very difficult to reveal by small solution samples (compared with the number of all feasible solutions).
The ``empty space phenomenon'' gives an example of problems getting hard when the dimension increases. The number of possible solutions is increased exponentially when the dimension increasing. There are $m^{n}$ possible solutions in total for a problem with $m$ possible solutions in each dimension (assume that each dimension has the same number of possible solutions). For example, when the $m$ equals to $1 000$, $100$ samples cover $10\%$ solutions for one dimensional problem. However, $100$ samples only cover $0.01\%$ solutions for two dimensional problem. For continuous problems, even we considered the computational accuracy, the number of possible solutions in one dimension is larger than $1 000$. The percent of data points will decrease rapidly. The search performance of most algorithms are based on the previous search experience. Considered the limitation of computational resources, the percent of data points have been retrieved will close to zero when the dimension increased to a large number. The performance of algorithms is affected by the increasing of problems' dimension.
Second, the characteristics of a problem may change with the scale. Problems will become more difficult and complex when the dimension increases. Rosenbrock's function, for instance, is unimodal for two dimensional problems but becomes multimodal for higher dimensional problems. Because of such a worsening of the features of an optimization problem resulting from an increase in scale, a previously successful search strategy may no longer be capable of finding an optimal solution.
Third, the direction of ``good'' solutions is difficult to determine. The swarm intelligence takes an ``update on each dimension, evaluation on whole dimensions'' strategy. An algorithm is very difficult to determine which one is better when two solutions both have some good parts and their fitness values are equally bad. The similar scenario also happens in multiobjective optimization. In Pareto domination measurement, nearly all solutions are Pareto non-dominated when the number of objects is larger than 10.
The last, the bias is accumulated. In the swarm intelligence, each solution is updated dimension by dimension, and the fitness value is calculated for the whole solution. The solution update depends on the combination of several vectors, i.e., the current value, the difference between current value and previous best value, the differential between current value and neighbor best value, or the difference between two random solutions, etc. In the low dimensional space, the direction of the vector combination has the high probability to point to the global optimum. However, the distance metric, which is utilized in low dimension space, is not effective in high dimensional space. The search direction is far away from the global optimum due to the bias accumulation.
Many effective strategies are proposed for high dimensional optimization problems, such as problem decomposition and subcomponents cooperation, parameter adaptation, surrogate-based fitness evaluations. Based on the swarm intelligence, an effective method could find good solutions for large scale problems, both on the time complexity and result accuracy.
Please give any description of your problem as mathematical model. I have read your three papers ( "Minimum Population Search – Lessons from building a heuristic technique with two population members" and others) on your OVERVIEW but I didn't find any description. I'm interested to know about it to try to use a Branch & Bound + Local Search Algorithm in order to find the best approximate solution within a given time limit. Can be solved your problem by using other algorithms excepting PSO ?
Our goal with Minimum Population Search (MPS) is to scale it up to 1000 dimensions for the LSGO contest -- http://goanna.cs.rmit.edu.au/~xiaodong/cec13-lsgo/
I don't think branch and bound would be well-suited to any multi-modal functions without global structure (using the terminology from BBOB -- http://coco.gforge.inria.fr/doku.php?id=bbob-2013), but given my new grasp of the scale of the search space, these problems seem completely hopeless for any technique.
Part of our goal in the MPS paper was to show how main stream techniques (e.g. PSO and DE) are implicitly designed for low-dimensional search spaces. The insights on low-dimensions suggest that they will scale poorly to extremely high dimensions.
New insights and results show that MPS also has difficulty to scale, so we have lots of work to do.
Steven, I would like to point out two things further:
1) I don't think that most meta-heuristic methods have been designed (even implicitly) for low dimensional spaces. In fact, I have personally applied GA techniques to discrete optimization problems that involved many thousands (or even millions) of binary or integer variables with great success in practice (for crew-assignment problems for instance). Further, a search space in the order of 2^1000 might not be as many orders of magnitude larger than other problems you very likely have already ran against: let's take the CEC-2005 benchmark functions. They included problems with dimensions up to 100. Now, remember that for most of these problems, your variables had to be "right" with a precision of at least 3 decimal places if your answer was to be anywhere near the optimal value. This means that your algorithm had to decide for each variable among 10^3 ~= 2^10 different choices, and there were 100 variables, so your total "grid-size" of the entire domain goes to around (2^10)^100 = 2^1000. So, your algorithms most likely have already searched such vast spaces, and have managed to come up with "OK answers" most of the time already!!! Somehow, the magic of the most successful meta-heuristics (combined with some yet unknown characteristics of the test-functions we have been experimenting with, because otherwise, the NFL theorem wouldn't hold), has allowed computers to find "pretty good" answers to problems that might have looked "impossible" at first glance.
2) Regarding B&B methods applied to NLP: there has been significant work on applying such methods to (constrained or unconstrained) NLPs, e.g. the a-bb method of Floudas (published somewhere in the late nineties in the Journal of Global Optimization, look it up if you will) and others, and they met with very good success, at least in certain domains.
Thank you to everyone for a productive discussion. The ideas became an important part of the attached paper.
A key discovery is that convergence time (as measured by generations) grows super-linearly with dimensionality. If the allowed number of function evaluations also grows linearly (a common allocation), then at some point, a constant population size will be unable to achieve the desired level of convergence. This is measured for only a single local optimum, and it does not take into account deceptive search spaces where the number of local optima can grow exponentially.
Simply put, meaningful search in very high dimensional search spaces will be extremely difficult.
Article Measuring the curse of dimensionality and its effects on par...
https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization
Code Codes in MATLAB for Particle Swarm Optimization
https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB
Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling