Many benchmarks for optimization are based on a fixed number of function evaluations -- e.g. 5000*dimension. Many search techniques (e.g. PSO, DE, etc) can be tuned to converge quickly or more slowly. On multi-modal functions, it is often more effective to converge quickly and do multiple restarts.
Is anyone aware of an optimal number of restarts? Are there any key studies that have isolated this issue in detail? Is there a general trend among the various restart techniques? Or, does every technique have to be its own ad hoc implementation?
I am not aware of an optimal number of restarts. I also think that this number might (strongly) depend on the population size and, of course, on the fitness function. Two techniques I am aware of are a) increase the population size for each restart (e.g. by a factor of 2) and b) keep the number of restarts * population size constant for several population sizes. One way of terminating the restarts process is to stop after several restarts did not yield any improvement. However, how many restarts you should perform is most often done, I guess, by trial-and-error or personal experience.
Why is the optimization problem difficult? For simplicity, let consider an OP for minimizing a function on n continuous variables. Difficulties may come from 1) the existence of many minima - they are closed together or far apart - their values are very closed to the others or not 2) the region containing the minimum point is very small - the paths or directions leading to it are very rare or difficut to find 3) the high dimensionality.
Restart techniques are mainly used for local search methods which usually give only local optimum points and their performances depend very much on the initial points.
See this rather old publication (1998, seems to have been updated) on restarts by Hoos and Stützle:
http://arxiv.org/abs/1301.7383
However, your question is far too general to be answered concretely, I would simply say that whenever an optimization algorithm is stuck, it shall restart. Determining when it is stuck it not trivial and is usually solved by heuristics. So any concrete number depends on the algorithm, the problem, and last but not least: the performance measure!
I think that the number of restarts needs to be considered in conjunction with the convergence criteria (esp. for metaheuristics). The previously because you can choose to perform multiple restarts with a less restrictive convergence (e.g. that the fitness is inside a given region), or you can let the algorithm run more time (e.g. by reducing the convergence region) and do less restarts.
Algorithms such as PSO, which are stochastic in nature, tend to avoid the local minima problem, since any particle can find a better solution at any given time, and communicate the information to the other ones. Thus, considering several restarts could be useful for deterministic approaches (such as CFO), or for stochastic ones, varying the search domain (since some of this techniques are, or can be set, to remain inside a given space).
Anyway, that is just my point of view, so I certainly hope it can help you...
Ps: A final thought: you could also run the algorithm several times (as independent runs) and using average values for the data. This way, you have results for different starting points, and through different paths (because of the stochastic behavior of the algorithms).
there is no way to say optimal number of restarts because it depends on the characteristic of the optimization problem. you can make restart when the convergence of your evolution algorithm stops for a number of cycles, this way is probably most suitable for many problems. if you give me more details of your problem probably I can help you better
hi Stephen,
this paper below addresses the problem you brought up:
A. S. Fukunaga. Restart scheduling for genetic algorithms. In Parallel Problem
Solving from Nature (PPSN V), LNCS 1498, pages 357-366. Springer, 1998.
The author proposes an approach which generates "static restart strategies with optimal expected utility", based on a database of past performance of the algorithm on a class of similar problem instances.
I think it's reasonable to ask why we need a restart. The population-based methods generally do not need this. A restart is already contained in the population of multiple searching points.
With the population-based methods, the problem becomes how to to tell the difference between premature convergence and real convergence.
There are two interesting papers that come to mind on principled ways of performing restarts in a black-box optimization problem. This is indeed a challenging decision to take, but it turns out there are ideas which were demonstrated to work quite efficiently in a variety of benchmark problems. Not incidentally, both approaches utilize memory-based heuristics for triggering the restarts:
1) The first approach that I remember is that of Coccu et al. (2011) published in IEEE CEC'2011: "Novelty-based restarts for evolution strategies" - http://dx.doi.org/10.1109/CEC.2011.5949613
It uses the history of the search to detect stagnation and to restart the population around the region of the most "novel" individual, in which the "novelty" of a candidate solution can be defined in many ways, but the authors chose to use the average distance of a solution to its k nearest neighbors.
2) The second idea is by e.g. Hornby (2009) published in GECCO'2009: "Steady-state ALPS for real-valued problems" - http://dx.doi.org/10.1145/1569901.1570011
It uses the so-called Age-Layered Population Structure (ALPS) which incrementally replaces old individuals for new ones and restrict mating (i.e., the selection of pairs of solutions to undergo crossover operations) according to different layers that group together individuals with similar ages. This procedure can be interpreted as a controlled, continuous "restart" process.
The idea showed very promising results in a range of problems (was also applied for a few NASA applications).
Anyway, I'd say that the main message those two papers convey is that the interesting question to ask about restarts is not how often should it be applied, but "how" (e.g., the paper on Novelty-based restarts) and "when" (e.g., the paper on ALPS).
I hope that helps.
Carlos.
The best restart criteria I know are used within the CMA-ES
(and are nearly unchanged there since at least 2005), see
Niko Hansen's constantly updated written Tutorial:
https://www.lri.fr/~hansen/cmatutorial110628.pdf
The criteria (at least most of them) have been thoroughly
evaluated experimentally over the years and could be
used in almost unchanged condition in almost any
stochastic/heuristic search algorithm.
To put it more generally, your question seems to be related to the issues of exploration (e.g. restarts, mutation, etc) versus exploitation (e.g. more intense local search), particularly population diversity management. There are adaptive and self-adaptive algorithms that makes use of population dynamics (e.g. population diversity measure such as distance-based or fitness-based) to balance these two processes within a population search framework such as PSO, ACO or DE, etc. (e.g. more exploration when the population appears to be converging or more exploitation otherwise).
Population diversity refers to the extent of variation in the population based on the individuals’ structure or performance. Various measures of diversity have been used in evolutonary computation, swarm intelligence, memetic computation etc,
such as the extent of variations in fitness values, aging of solutions, etc. Based on these diversity measures, various adaptive and self-adaptive techniques have been proposed for population-based meta-heuristics.
With fitness-based diversity, adaptation techniques maintain the population diversity by managing good fitness spread among individual solutions in the population. For example, one can coordinate multiple refinement or local search procedures (which either explore or exploit), and monitor how close the average fitness within the current generation of the search is compared to the population
elite. Alternative, one can chose to effect the search adaptation according to the sparseness of individuals, or the super-fit individual in the population. To
prevent loss in diversity, multiple populations using completely different fitness criteria can also be considered.
With distance-based diversity, one can maintain the population diversity by managing the distance spread among individual solutions in the population while the search progresses. Some relevant works in this discipline have been using adaptation based on population entropy, etc.
I'd like to thank everyone for a highly useful discussion. I've downloaded several of the papers, and I'll have to see if they're what we're looking for.
The overall research is trying to find better ways to balance and/or efficiently separate exploration and exploitation. Delaying convergence adds one set of tools (and complexities), and performing restarts adds another set of tools (and complexities).
Our current focus is on how to improve restart techniques (https://www.researchgate.net/post/Whats_a_good_way_to_implement_an_algorithm_with_restarts). More than tracking information on *when* to do a restart, we're trying to develop new ideas on *where* to go back.
The above examples will be useful as benchmarks to test our new ideas (as opposed to reinventing the wheel or using a weak straw man).
If we come up with anything really interesting, I'll be sure to post an update!
Based on my experience for the number of independent runs for metaheuristic methods, usually 30 to 50 independent runs should be enough. 20 is the minimum number of independent runs which I saw in academic papers. In order to have comparative study, its better to follow others in terms of number of runs. In case of having new problems, you can determine the number of restarts. However, when you increase the number of runs, you give more chance to your method to find the global optimum point, on the other hand, the value for the standard deviation is supposed to be larger.
In contrast, If you run your algorithm for less than 10 times, it is not proper and enough number of runs to evaluate the performance of your method. Therefore, if you run your optimizer for more than 30 runs and you have obtained better statistical results (i. e. best, mean, worst and standard deviation), you can claim for the efficiency of your method compared with other optimizers.
When we do not know the vicinity of the global optimum, we initialize optimizers with randomized trial solutions (and auxiliary features such as velocity or direction). If the solution converges, we have an optimum. But do not know whether it is a global or local optimum. So, we restart the optimizer with newly randomized conditions. A question is, "How many independent optimizer trials are required to be confident that the best of N trials will identify the global optimum. The paper by Iyer, M. S., and R. R. Rhinehart, “A Method to Determine the Required Number of Neural Network Training Repetitions,” IEEE Transactions on Neural Networks, Vol. 10, No. 2, March, 1999, pp. 427-432, derives a formula to determine N based on a user-desired confidence, c [0
Hey there, a rule of thumb is 30 restarts which is a statistical lower bound (assuming that the central limit theorem is fulfilled by true set from which the sample is taken), google for some Dr. Juan Frausto-Solis 's articles, he is an expert in metaheuristics as Simulated annealing or GA, and in most of his papers he uses that rule. Maybe you should try this heuristic and Dr. Russell's suggestion (or anyother). With those results you can perform a hypothesis test (like Wilcoxson test) and see if there is any difference or not. It will be quite interesting if you let us know about your results.
What is the problem that you are trying to solve? Is it finding any global minimum only, or you need all the global minima (in case there are more than one), or you need to find the global minimum and a number of other local minima with function values with a small deviation from the global value, or you need to find all the local minima inside a bounded area?
These are all global optimization problems, however they have differences that are important in deciding which method to use.
One should use termination criteria, however different type of problems need different criteria.
If you send me extra info, i might be able to help
Isaac E. Lagaris, University of Ioannina, GREECE
Thanks to everyone for their comments. For improved clarity and focus of discussion, I've started a new thread. Please join in!
https://www.researchgate.net/post/How_can_we_identify_the_critical_search_scale_for_continuous-domain_multi-modal_fitness_functions
- Badges
- Science topic
- Similar topics
- Psychology