In regular EAs, a stopping criteria often used in practice is stagnation: if the fitness value of the best individual in the population does not improve for a given number of generations, the algorithm stops. Since I do not know well the field of multi-objective evolutionary algorithms, I was wondering: is there a similar "stagnation" stopping criteria?
I've seen some publications on the topic, like "An approach to stopping criteria for multi-objective optimization evolutionary algorithms: The MGBM criterion", but I was wondering whether there are other stop conditions used in practice, and if someone here experimented with different "stagnation" criteria for MOEAs.
I would suggest referring to the following interesting paper published in EMO 2011.
Conference Paper A Taxonomy of Online Stopping Criteria for Multi-Objective E...
Yes, this is only the (I believe) last one in a row of papers on this matter...
You can apply pretty much any criterion quantitatively measuring the quality of the Pareto front to identify stagnation. We used the hypervolume measure, calculated its value after each iteration and compared with previous iteration results. If the progress was not significant for a consecutive X number of iterations (we typically use 30-50) stagnation conditions were met.
Sometimes the most effective means just the fastest. I would suggest to count the number of solutions in the working pareto set. if it doesn't change for a certain number of iterations it means that "probably" the algorithms stagnates. It worked pretty well for us. If, however, the execution time is not a problem checking the hypervolume is the best choice.
There are several criteria to establish the termination condition, and the paper that Carlos Azevedo has cited talks about this topic.
I notice a possible inconvenience of the criterion commented by Michele Ciavotta, i.e. to consider the number of solutions in the non-dominated set does not change during a given number of iterations. In you use this criterion, you must have in mind that, if the external file size is limited in size (e.g. 50 solutions), the external archive of the multi-objective algorithm could be full from a given moment, but it does not means necessarily that it has converged (because, for instance, a new obtained solution dominates only one solution of the previoulsy stored, and the size does not change).
I would suggest to use, instead, as criterion, that the non-dominated set is not updated during a certain number of iterations (it is very easy to determine if the external archive is updated using a counter of the number of iterations without removing/substituting solutions).
Of course, as Michele Ciavotta says, the hypervolume is the best choice, but perphaps Alberto Paolo Tonda is not using the hyper-volume as criteria to compare the obtained non-dominated sets, but other metrics (e.g. the Set Coverage, the Schott Spacing Metric, etc.) .
The most used stopping criteria is "the number of evaluations"... it is set to 15.000-30.000 for NSGA-II for example is ZDT test suite. But if you are looking for a more advanced stopping criteria, i think it depends on whether the problem is computationally expensive or not, whether the optimization is on-line or off-line, whether the computation budget is limited or no, whether the problem is dynamic or static, deterministic or stochastic/noisy,...
Hi Alberto,
There are several approaches for stopping an algorithm. You can use either the number of iterations, or the number of evaluations of the objective functions, but I do not like them too much since it is like an open-loop way of controlling your algorithm (i.e. you do not really know how the solutions are behaving, so you just let it run for a given time). On the other hand, you can use a limit for the fitness, but you need to know something about the problem, e.g. if it is bounded.
Another approach is to use the evolution of the fitness. In this case, you analyze how much is the solution improving over each iteration, and if it reaches a given limit, you can stop the algorithm. This, however, is not really helpful when your problem has planar regions, since the solution will improve little but the coordinates will vary greatly. In this case, you could use an analysis on the evolution of the coordinates of the solution, instead of the fitness. If you have a swarm-based technique, you can consider the data for the best element, or you can do so for the local bests (in case you have neighborhoods or a similar topology). There is a metaheuristic (CFO) that calculates a diagonal (think of it as a value on the dispersion of elements), and it uses that data to decide if it should converge or not.
As you can see, there are several approaches, and each one can be more/less helpful for each type of problem. Thus, and in case you do not know anything about the behavior of the objective function, I would say that it is better to run some exploratory tests with some of the criteria, and then decide which one to use for the extensive tests.
Hope it helps...
OCD (Online Covergenc Detection) is a method that seems to work based on statistical time series extrapolation of the development of an performance indicator (R2, hypervolume indicator). There are quite some papers on this, such as this one:
Trautmann H, Wagner T, Naujoks B, Preuss M, Mehnen J.: Statistical methods for convergence detection of multi-objective evolutionary algorithms. Evol Comput. 2009 Winter;17(4):493-509. doi: 10.1162/evco.2009.17.4.17403.
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication