Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

Summary

This paper studies the "multi-objective minimum weight base" problem in the MOEA/D framework and proposed several useful properties.

Strengths

This paper gives the running time analysis for a special kind of MOEAD problem. This is an important contribution for the MOO field since MOEAD is a very basic idea. The strength of this paper is that, the studied algorithm is very meaningful since it take cooperation into consideration. (Line 8-9 in Algorithm 3).

Weaknesses

1. This paper take multi-objective minimum weight base problems as an example. This is not general however.

Questions

1. This paper mainly considers the weighted sum scalarization. It is known that this method can only recover the convex part of a PF. Will the proposed method find the whole Pareto solution? 2. When the objectives are all non-convex. It is impossible to use the supportive set to approximate the whole PS. So is there any assumption for your supportive set? 3. Line 102, a support set is extreme if ..... This statement is not clear. 4. line 250, ontrade off -> on trade off?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NO.

Summary

This paper presents a comprehensive theoretical and empirical analysis of the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) for the Multi-Objective Minimum Weight Base problem. The authors provide a detailed explanation of the algorithm, including its fitness functions and decomposition scheme. They also propose a series of algorithms for finding extreme points and a complete trade-off set. The paper includes a rigorous theoretical analysis, providing expected time bounds for the algorithm to minimize scalarized weights and enumerate the convex hull of the feasible region. The authors also conduct an experimental investigation on various bi-objective minimum spanning tree instances, comparing the performance of MOEA/D against GSEMO. The results demonstrate that MOEA/D significantly outperforms GSEMO in computing extreme points under an appropriate decomposition.

Strengths

1. The paper provides a thorough theoretical analysis of the MOEA/D algorithm, including expected time bounds for key operations, which contributes to the understanding of the algorithm's performance and efficiency. 2. The authors apply their theoretical findings to a real-world problem demonstrating the practical relevance of their research. 3. The paper includes a comparative analysis of MOEA/D and GSEMO, and provides valuable insights into the strengths and weaknesses of these algorithms. 4. The authors provide a detailed explanation that helps understand the MOEA/D algorithm.

Weaknesses

1. The paper makes several assumptions, such as distinct supported solutions having distinct images under the weight function, which might not be applicable in all scenarios. How would the theory guides the application of MOEA/D? 2. The paper does not provide a detailed discussion on how to choose the parameters for the MOEA/D algorithm. 3. This paper may only be interested by the evolutionary computation community.

Questions

1. How would the theory guides the application of MOEA/D? 2. Could the authors elaborate on the rationale behind the assumption that distinct supported solutions have distinct images under the weight function.? Are there any scenarios where this assumption might not hold, and if so, how would this affect the results? 3. Could the authors provide more insights into how these parameters should be selected?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Societal impact of the work is not discussed in this paper.

Summary

The result is for the cross product of a problem class and algorithm. The problem is the multi-objective weight base problem and the algorithm is Multi-objective, evolutionary algorithm with decomposition (MOEA/D). This algorithm effectively optimizes by decomposing the objectives into single-objectives. With an appropriate decomposition, the algorithm can find all extreme points with expected fixed-parameter polynomial time. The problem has the appropriate decomposition. Experiments agree with the theory and show the algorithm is faster than another EA called GSEMO

Strengths

The problem is in the matroid optimization category and generalizes wrt a previously studied bi-objective minimum spanning tree problem. Decomposition into single-objective problems is one of two well-used approaches to Multi-objective optimization (MOO) so the MOEA/D is relevant. Prior state of art is for a different (simplified) algorithm (GSEMO) which shows a pseudo-polynomial run-time for 2 not k objectives. Together with recent analyses of NSGA-II, the paper represents significant progress in developing runtime analysis of practically relevant multi-objective evolutionary algorithms. The paper develops insight into the local structure (Hamming neighborhoods) of matroid optimization problems. This structural insights will be helpful to analyse the runtime of other evolutionary algorithms on such problems. This is the first rigorous runtime analysis of MOEA/D. The authors provide upper bounds on the expected time to enumerate the convex hull of the Pareto front of the bi- and k-objective minimum weight base (MWB) problem. The assumption is that the algorithm is provided with optima for complete trade-off sets (e.g.,via the Greedy algorithm).

Weaknesses

One problem with the paper is readability. Algorithm and problem names are stated early as are comparisons but they are poorly described until the preliminaries. There are a lack of clear intuitive descriptions of the problem, the algorithm (and those it is compared with) within the preliminaries. The reader has to jump across statements to figure out the analytic approach and to understand how/why it works. Granted it's challenging to describe a matroidal problem and one that is multi-objective, but the writing does not offer sufficient help with this. The problem definition is inline on line 83 for example. The objectives arise from the problem's matroidal properties and in a sense, the problem formulation makes it easy for each objective to be solved for extrema. The challenge with MOEA/D in practice is the decomposition and this is neither noted nor related to the matroidal problem analyzed here. Are there real world problems that are as ideally decomposable? The analysis depends on a property of the problem (linear independence), the convex hull of its non-dominated front, and the ability to compute extrema for more than two objectives. It is not explained why the MOEA/D is a good algorithm to use vs a dominance-based one. The stochastic behavior of the MOEA/D algorithm has not been accounted for. It would be helpful to additionally provide an analysis for standard multi-objective benchmark functions to allow for a comparison with analyses of other MOEAs. The description of the experimental setting lacks detail.

Questions

Why are there no figures!? How does this problem -- the multi-objective weight base problem relate to common MOO problems? What are the properties of a harder problem that we would use the algorithm for? How is the first generation population of GSEMO initialized, and does this give the MOEA/D an unfair advantage?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

None

Summary

This paper presents the first run-time analysis of the MOEA/D for the multi-objective minimum weight base problem, e.g., multi-objective minimum spanning tree (MST). The theoretical results show the MOEA/D can find all extreme points within expected fixed-parameter polynomial time given an appropriate decomposition setting. Experiments on minimum spanning tree instances agree with the theoretical results.

Strengths

1/ This paper gives the first analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem.

Weaknesses

1. **Lack of novelty and originality**: Although the paper presents the first analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem, it does not offer significant novelty in the context of multi-objective combinatorial optimization. Recent studies, such as the analysis of NSGA-II for similar problems, have already explored this area. 2. **Insufficient innovation in analysis techniques**: The technical approach used in this paper is similar to previous work, focusing on enumerating the convex hull Conv($𝐹$) of the non-dominated front. The paper does not introduce substantial innovations or improvements to the existing techniques, which limits its contribution to the field. 3. **Limited insights from the results**: The results obtained in the paper do not provide new insights or implications for algorithm design. Although the MOEA/D algorithm is shown to be faster than the GSEMO algorithm for the given problem, this alone is not enough to warrant a significant contribution to the research community.

Questions

Why do you claim “multi-objective minimum weight base problem is a significant generalization of the previously studied bi-objective minimum spanning tree problem”? Please give more disccusions.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

No, this paper does not include the limitations.

Summary

This paper provides a run-time analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem. It focuses on approximating the non-dominated front and shows that MOEA/D obtains a factor 2-approximation for two objectives in expected polynomial time. Empirical studies are conducted to verify the theoretical results.

Strengths

1. A run-time analysis is presented on the MOEA/D algorithm, a classical multi-objective evolutionary algorithm that has rarely been analyzed theoretically. 2. It is shown that MOEA/D obtains a factor 2-approximation for two objectives in expected polynomial time, compared with a pseudo-polynomial run-time of an existing method.

Weaknesses

1. The definition of the multi-objective minimum weight base problem is unclear, e.g., the range of the decision variables and what the objectives are. 2. The empirical study is performed by comparing with GSEMO, an algorithm published in 2007. This might be inefficient in verifying the superiority of the analyzed MOEA/D.

Questions

1. In the experiments, why not consider more state-of-the-art algorithms on bi-objective minimum spanning tree instances? 2. According to the definition of dominance relation in Section 2, solutions with objectives taking the same value will dominate each other, which can cause a contradiction. How is this situation handled in the algorithm? It says that “Such a set is known to guarantee a 2-approximation of the non-dominated set for k= 2”. Nevertheless, this conclusion was obtained on the multi-objective minimum spanning tree problem; does it still hold on to the more general multi-objective minimum weight base problem?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

It is suggested to analyze the front shape of the tested problems, e.g., if problems with irregular Pareto fronts have been examined.

Thanks for the response

Thank all the authors for their detailed responses. I think the anwsers are reasonable.

For Q1

My concern for Q1 is that, when the PF is concave, like f_1 = 1 - f_2^2. You can check that, using any preference w=[0,1] from w = [1,0], the minimal value of w^T f will only lead to the two end point (0,1) or (1,0). Am I correct? So when the PF is concave, using LS will only find some partial solutions. Will this argument hurt your conclusion?