- Rating
- 4
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies a specific design choice in noisy multi-objective evolutionary optimization: whether NSGA-II should retain individuals’ initial fitness evaluations or reevaluate them in every generation. On LOTZ, reevaluation can increase the expected runtime from polynomial to superpolynomial. On the newly constructed PairedCOCZ benchmark, reevaluation instead provides a substantial advantage when the noise probability equals or is sufficiently close to one. Experiments further illustrate the mechanisms underlying these contrasting results.
Critical strengths
The problem is clearly formulated, and the theoretical results support the main conclusions under explicitly stated assumptions.
The paper demonstrates that a small change in the fitness evaluation policy can substantially improve noise robustness, producing large runtime advantages while leaving other algorithmic components unchanged.
Critical weaknesses
This is a typical theoretical paper that analyzes a specific mechanism on constructed, abstract problems and provides experimental support for its conclusions. If I were to identify areas for improvement, I would highlight the following three points:
- I would appreciate more discussion of the motivation behind PairedCOCZ, particularly whether its construction captures features of real-world optimization problems.
- The theoretical bounds are relatively loose, leaving a substantial gap between the proven guarantees and the experimental settings. However, this is not unusual in theoretical runtime analysis, and I do not consider it a major concern.
- I would like to see experiments on more realistic problems beyond toy benchmarks such as LOTZ, LeadingOnes, and OneMax (in single objective optimisation), or at least on classical optimization problems with practical relevance. Such experiments would help establish whether the mechanisms identified in the theoretical analysis translate into practical benefits.
Questions for authors
This is a question for discussion rather than a weakness of the paper. Could the authors discuss the connection between reevaluation and non-elitist population replacement? Although NSGA-II remains structurally elitist, reevaluation prevents a previously favorable noisy evaluation from conferring a permanent survival advantage. Fully replacing parents with freshly evaluated offspring could potentially break the same mechanism of persistent overestimation. Existing single-objective analyses show that non-elitist EAs can handle noise efficiently with appropriately chosen mutation rates and population parameters, and that parameter control mechanisms can further improve noise tolerance in certain settings. These results motivate asking whether non-elitist replacement could provide a complementary approach to noisy multi-objective optimization. A key challenge would be maintaining representatives of the entire Pareto front. Could suitable mutation-rate control, together with appropriate population sizing and diversity preservation, address this challenge while preventing incorrect fitness evaluations from persisting indefinitely?
4 comments
Response to Reviewer Gy8x (2/3)
Experiments on more realistic problems. Thank you for this suggestion. We agree, and following it we added such an experiment to the revision (last paragraph of Section 5, Figure 1(d) and Appendix I.6). We ran NSGA-II with both strategies, under the same noise model, on the bi-objective minimum spanning tree problem described above. The setting is as follows. The main experiment uses 1000 random instances on the complete graph with 8 vertices (28 edges) and the population size ; the appendix also reports 6 and 7 vertices. For every noise level and each strategy, NSGA-II is run once on each instance, which gives 1000 runs. Both strategies get the same number of fitness evaluations: every run has a budget of 2,000,100 evaluations, which are 20,000 generations without reevaluation and 10,000 generations with reevaluation, because reevaluation uses twice as many evaluations per generation. We count the runs whose population covers the Pareto front within this budget, that is, contains, for every vector of the Pareto front, a spanning tree with this weight vector.
The results are consistent with our theoretical findings and with the experiments on PairedCOCZ: when the noise is not too high, no reevaluation is better, and when the noise is very high, reevaluation is better.
- Moderate noise. At , all 1000 runs without reevaluation cover the Pareto front, but only 27.6% of the runs with reevaluation. Reevaluation is harmful here, as we proved on LOTZ.
- High noise. The order changes between and , as on PairedCOCZ. Without reevaluation, 96.0% of the runs cover the front at , 4.9% at and none at ; with reevaluation, these are 16.9%, 16.8% and 16.8%. At , every run without reevaluation ends in a population that stores only values of spanning trees and contains no spanning tree. Such a population never accepts a spanning tree, which is the situation of Theorem 4(b). Reevaluation is helpful here, as we proved on PairedCOCZ.
Response to Reviewer Gy8x (3/3)
Reevaluation and non-elitist replacement. Thank you for this insightful comment. We added Appendix A.3 for discussion. Our view is as follows.
- Both mechanisms limit the time during which one lucky noisy evaluation helps an individual. With reevaluation, the individual may stay, but its value is replaced in the next generation. With non-elitist replacement, the value stays with the individual, but the individual is removed.
- However, non-elitist replacement may not have the same effect as reevaluation. On PairedCOCZ at , replacing all parents by the offspring would remove the absorbing populations of Theorem 4(b), because their members would not survive. This alone does not give a runtime bound. With reevaluation, an optimum can stay in the population and only its value is renewed. With full replacement, no optimum survives as an individual, so the classes of the front must be created again in every generation. Our lower bound for reevaluation on LOTZ shows where noise adds a difficulty. Its key lemma uses only that many Pareto-optimal solutions have at most two copies and that all copies of a solution can receive dominated values in the same generation. Neither fact depends on elitism. A non-elitist NSGA-II would therefore need more copies of every Pareto-optimal solution, for example through a larger population.
- For single-objective optimization, non-elitist evolutionary algorithms with a suitable mutation rate and selective pressure are efficient under noise (Dang and Lehre 2015; Lehre and Qin 2024), and self-adaptation of the mutation rate can increase the noise level that the algorithm can handle (Lehre and Qin 2023). In the multi-objective case the algorithm must also keep representatives of the whole front, as you point out. On LOTZ, each Pareto-optimal solution is the only solution with its fitness vector and would have to be created again in every generation. Whether mutation-rate control, together with a suitable population size and a mechanism that keeps the population diverse, can achieve this under noise is, in our view, an interesting open question.
Thanks to your suggestions, we have revised the paper to add non-elitist survival selection as a direction for future work (Section 6).
Thank you again for your encouraging and helpful review. We would be glad to answer any further questions.
References
- Duc-Cuong Dang and Per Kristian Lehre. Efficient Optimisation of Noisy Fitness Functions with Population-based Evolutionary Algorithms. In Proceedings of the 13th Workshop on Foundations of Genetic Algorithms (FOGA'15), pp. 62–68, Aberystwyth, UK, 2015.
- Yaochu Jin and Jürgen Branke. Evolutionary Optimization in Uncertain Environments—A Survey. IEEE Transactions on Evolutionary Computation, 9(3):303–317, 2005.
- Per Kristian Lehre and Xiaoyu Qin. Self-Adaptation Can Improve the Noise-Tolerance of Evolutionary Algorithms. In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA'23), pp. 105–116, Potsdam, Germany, 2023.
- Per Kristian Lehre and Xiaoyu Qin. More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments. Algorithmica, 86(2):396–441, 2024.
- Frank Neumann. Expected Runtimes of a Simple Evolutionary Algorithm for the Multi-Objective Minimum Spanning Tree Problem. European Journal of Operational Research, 181(3):1620–1629, 2007.
Dear Reviewer Gy8x,
Thank you again for your helpful suggestions. Following them, we have carefully revised the paper point by point, and your suggestions have helped us a lot to improve our work.
Finally, we would like to thank you sincerely for your encouraging review. It means a lot to us.
Best regards,
The Authors
Response to Reviewer Gy8x (1/3)
We sincerely thank you for your time, insightful comments and helpful suggestions, as well as the recognition of our work. Your encouraging remarks are much appreciated. Please find below our detailed responses to your comments and the revision made accordingly. All changes are marked in blue in the uploaded PDF.
Motivation of PairedCOCZ. Thank you for this question. Following it, we revised the paper to make the motivation stronger. We added a sentence in Section 4 and a new Appendix A.2, and we added a classical combinatorial problem that has the same property as PairedCOCZ, together with a new experiment. We explain both points here.
PairedCOCZ is not a model of one application. It focuses on one property that practical problems can have: optima that are sensitive to small changes. Every one-bit neighbour of an optimum is worse than every optimum in both objectives. Under prior noise, an optimum is therefore never evaluated better than it is, and it is evaluated worse whenever the evaluation is corrupted. Such optima are the non-robust optima of robust optimization (Jin and Branke 2005). They occur, for example, when the best designs lie at the boundary of the feasible region and violations are penalized, so that a slightly changed copy of the design pays the penalty; in PairedCOCZ the penalty r+1 per defect has this role. In addition, a changed copy of a slightly worse solution can be optimal, so a non-optimal solution can receive a value that is too good, and without reevaluation it keeps this value.
The example that we added is the bi-objective minimum spanning tree problem in the penalized formulation of Neumann (2007), in which edge sets that are not spanning trees are penalized. This problem has the property that motivated PairedCOCZ. A spanning tree has a fixed number of edges, so flipping any single bit of a spanning tree gives an edge set that is not a spanning tree and is penalized. A corrupted evaluation therefore always makes an optimal spanning tree look worse, as it does for the optima of PairedCOCZ. Our new experiments on this problem, which we describe in the answer to your third point below, show the same behaviour as on PairedCOCZ.
In addition, following a comment of Reviewer eZxp, we added a new result on the noise levels of Theorem 4 (Lemma 54 in Appendix H.3). Theorem 4 is stated only for the maximal noise level p=1 and for noise levels that are exponentially close to it, 0<1−p≤2−2n. The new lemma shows that, for constant r and every p<1, the expected runtime without reevaluation on PairedCOCZ is polynomial in n, μ and 1/(1−p). So reevaluation can be faster by more than a polynomial factor only if p is extremely close to 1. A restriction of Theorem 4 to such noise levels is therefore necessary, and it is not a weakness of our proof.
Loose bounds. Thank you for pointing this out; we agree. The constants are larger than needed because they come from union bounds over long runs. Closing the gaps between the proved noise ranges on LOTZ is listed as future work.