Reviews and Comments on Paper 582
Paper information
| Paper #582: Everardo Gutiérrez and Carlos A. Brizuela. ILS-perturbation based on local optima structure |
| Abstract: Many problems in AI can be stated as search problems and most of them
are very complex to solve. On the other hand, local search methods has been
used for tackling difficult optimization problems for which we do not know
efficient algorithms. One of the most popular methods is the so called iterated
local search (ILS), which sample the set of local optima searching for a better
solution. This algorithm's behavior is achieved by some mechanisms
like perturbation which is a key aspect to consider, since it allows the
algorithm to reach a new solution from the set of local optima by escaping
from the previous one basis of attraction. In order to design a good perturbation
method we need to analyze the local optima structure such that ILS
leads to a good biased sampling. In this paper, the local optima
structure of the Quadratic Assignment Problem, an NP-hard optimization
problem, is used to determine the size of the perturbation in the ILS algorithm.
The analysis is focused on verifying if the set of local optima has the so called
``Big Valley (BV)" structure, and on how close local optima are in relation to
problem size. Experimental results show that a small perturbation
seems appropriate for instances having the BV structure, and for instances
having a low distance among local optima, even if they do not have
a clear BV structure. Finally, as the local optima structure moves away
from BV a larger perturbation is needed. (file) |
Summary of received reviews and comments
Reviews superseded by other reviews are shown in the grey color in the table.
| confidence | score | ||||
| Review 1 | 3 | 3 | |||
| Review 2 | 3 | 2 | |||
| Review 3 | 2 | 1 | |||
| Current decision: A NOT best (not best) (change) | |||||
| Add a new comment | Add a new review | ||||
Reviews and Comments
Review 1
| PC member: | |
| Reviewer: | |
| Overall rating: | 3 (strong accept) |
| Confidence: | 3 |
| Relevance: Is this paper relevant for this conference? | 3 (strong accept) |
| Soundness: Is this paper technically sound and complete? | 2 (accept (I will argue for this paper)) |
| Are the claims sufficiently supported by experimental/theoretical results? | 3 (strong accept) |
| Significance: Are the results/ideas interesting for other AI researchers? | 2 (accept (I will argue for this paper)) |
| Originality: Are the results or ideas novel and previously unknown? | 2 (accept (I will argue for this paper)) |
| Readability: Is the paper well-organized and easy to understand? | 3 (strong accept) |
| Language: Is the paper written in correct English and style? | 2 (accept (I will argue for this paper)) |
| Format: Is the paper correctly and consistently formatted? | 3 (strong accept) |
| Review: | CONTRIBUTION OF THE PAPER: The authors present an analysis about the local optima structure of several benchmark instances of the quadratic assignmnet problem, and they basically classify the problems in two types. Based in this analysis, they define the walk length to obtain good results with an iterated local search algorithm. POSITIVE ASPECTS: A good discussion about the drawbacks of different measures (including a visual comparison) to classify the instances. NEGATIVE ASPECTS: A rule to obtain the walk length is missing. CHANGES TO IMPROVE THE PAPER: The authors may add an empirical rule to obtain a walk length based on the measures they comment. FURTHER COMMENTS: Abstract: "for which we do not know efficient algorithms". Actually, we do know efficient algorithms for many NP problems, but they are not exact or complete (we cannot prove optimality). Abstract: "previous one basis of attraction". It seems that something is missing in this statement. Sec1, par1: again, the authors must mention that lack of efficient algorithms is only for complete algorithms. Sec1, par1: "used in practice for difficult optimization problems". Please add the word "combinatorial", since all of your references are about combinatorial problems. Sec1, par3: "this may make it difficult to perturb this solution". Remove "it". Sec1, par4: the same about "efficient algorithms". Sec2, par1: "some well known problems". Again, please add "combinatorial". Table1, caption: Actually, they are not the instances, but some features about them. Sec5.1, par3: Replace "as the one shown" for "as those shown". Figure2 and Figure3 captions: Replace the word "instances" for "examples" or "samples", or any other you consider appropriate. Sec5.2, par2: Define the terms in the expression ((ILS - Best)/Best). Moreover, I suggest to use other letter instead of ILS, because you previously defined it as an algorithm. Sec5.2, par4: "This confirm the existence" must be "confirms". ITEMS BELOW ARE JUSTIFICATION OF THE SCORES IF NEGATIVE: (1) IS THIS PAPER RELEVANT FOR THIS CONFERENCE? Yes. (2) IS THIS PAPER TECHNICALLY SOUND AND COMPLETE? Yes. (3) ARE THE CLAIMS SUFFICIENTLY SUPPORTED BY EXPERIMENTAL OR THEORETICAL RESULTS? Yes. (4) ARE THE RESULTS/IDEAS INTERESTING FOR OTHER AI RESEARCHERS? Yes. (5) ARE THE RESULTS OR IDEAS NOVEL AND PREVIOUSLY UNKNOWN? Yes. (6) IS THE PAPER WELL-ORGANIZED AND EASY TO UNDERSTAND? Yes. (7) IS THE PAPER WRITTEN IN CORRECT ENGLISH AND STYLE? Yes, but some minor corrections. (8) IS THE PAPER CORRECTLY AND CONSISTENTLY FORMATTED? Yes. |
| PC only: | |
| Time: | Jul 7, 00:36 |
Review 2
| PC member: | |
| Reviewer: | |
| Overall rating: | 2 (accept: I will argue for this paper) |
| Confidence: | 3 |
| Relevance: Is this paper relevant for this conference? | 2 (accept (I will argue for this paper)) |
| Soundness: Is this paper technically sound and complete? | 2 (accept (I will argue for this paper)) |
| Are the claims sufficiently supported by experimental/theoretical results? | 2 (accept (I will argue for this paper)) |
| Significance: Are the results/ideas interesting for other AI researchers? | 1 (weak accept (vote accept but don't mind rejecting)) |
| Originality: Are the results or ideas novel and previously unknown? | 1 (weak accept (vote accept but don't mind rejecting)) |
| Readability: Is the paper well-organized and easy to understand? | 2 (accept (I will argue for this paper)) |
| Language: Is the paper written in correct English and style? | 2 (accept (I will argue for this paper)) |
| Format: Is the paper correctly and consistently formatted? | 2 (accept (I will argue for this paper)) |
| Review: | CONTRIBUTION OF THE PAPER: A search method was applied and tested on a NP-hard problem. POSITIVE ASPECTS: This is a good paper overall. NEGATIVE ASPECTS: The idea could be explained in more detail. CHANGES TO IMPROVE THE PAPER: FURTHER COMMENTS: ITEMS BELOW ARE JUSTIFICATION OF THE SCORES IF NEGATIVE: (1) IS THIS PAPER RELEVANT FOR THIS CONFERENCE? (2) IS THIS PAPER TECHNICALLY SOUND AND COMPLETE? (3) ARE THE CLAIMS SUFFICIENTLY SUPPORTED BY EXPERIMENTAL OR THEORETICAL RESULTS? (4) ARE THE RESULTS/IDEAS INTERESTING FOR OTHER AI RESEARCHERS? (5) ARE THE RESULTS OR IDEAS NOVEL AND PREVIOUSLY UNKNOWN? (6) IS THE PAPER WELL-ORGANIZED AND EASY TO UNDERSTAND? (7) IS THE PAPER WRITTEN IN CORRECT ENGLISH AND STYLE? (8) IS THE PAPER CORRECTLY AND CONSISTENTLY FORMATTED? |
| PC only: | Clear accept. |
| Time: | Jul 10, 11:19 |
Review 3
| PC member: | |
| Overall rating: | 1 (weak accept: Vote accept, but wouldn't mind rejecting) |
| Confidence: | 2 |
| Relevance: Is this paper relevant for this conference? | 2 (accept (I will argue for this paper)) |
| Soundness: Is this paper technically sound and complete? | 1 (weak accept (vote accept but don't mind rejecting)) |
| Are the claims sufficiently supported by experimental/theoretical results? | 0 (neutral (please avoid this option)) |
| Significance: Are the results/ideas interesting for other AI researchers? | 1 (weak accept (vote accept but don't mind rejecting)) |
| Originality: Are the results or ideas novel and previously unknown? | 0 (neutral (please avoid this option)) |
| Readability: Is the paper well-organized and easy to understand? | 2 (accept (I will argue for this paper)) |
| Language: Is the paper written in correct English and style? | 1 (weak accept (vote accept but don't mind rejecting)) |
| Format: Is the paper correctly and consistently formatted? | 3 (strong accept) |
| Review: | CONTRIBUTION OF THE PAPER: Paper analyses the size of the perturbation required in the Iterated Local Search method (ILS) in order to efficiently tackle the Quadratic Assignment Problem (QAP), an NP-hard optimisation problem. This is achieved by analysing the set of local optima structure of QAP, concluding that the more they resemble the Big Valley (BV) structure, the less perturbation is required (and conversely.) This is in some sense as expected. POSITIVE ASPECTS: Paper is easy to read. The setup of the experimentation is well described and motivated. NEGATIVE ASPECTS: Paper does not emphasise on the significance of the results (if any at all). It would be nice to know if there existsa relation between the BV structure and other combinatorial optimisation problems. CHANGES TO IMPROVE THE PAPER: Title is misleading. It promises more than it buys. Need to add QAP. Need to thoroughly review paper looking for common grammatical English errors an dfor polishing writing style. Some appear below: Abstract: On the other hand --> Begs for other sentence of the form "On the one hand ..." Abstract: "... methods HAVE been used" Abstract: "... which sampleS" Intro: "Most problems ..." Cost-Distance Correlation: "THESE results" Perturbation vs local ...: "two acceptance CRITERIA" Perturbation vs local ...: "This confirmS" Perturbation vs local ...: "The first one is" (remove ",") Conclusions: "to relate THESE structures" FURTHER COMMENTS: ITEMS BELOW ARE JUSTIFICATION OF THE SCORES IF NEGATIVE: (1) IS THIS PAPER RELEVANT FOR THIS CONFERENCE? (2) IS THIS PAPER TECHNICALLY SOUND AND COMPLETE? (3) ARE THE CLAIMS SUFFICIENTLY SUPPORTED BY EXPERIMENTAL OR THEORETICAL RESULTS? (4) ARE THE RESULTS/IDEAS INTERESTING FOR OTHER AI RESEARCHERS? (5) ARE THE RESULTS OR IDEAS NOVEL AND PREVIOUSLY UNKNOWN? (6) IS THE PAPER WELL-ORGANIZED AND EASY TO UNDERSTAND? (7) IS THE PAPER WRITTEN IN CORRECT ENGLISH AND STYLE? (8) IS THE PAPER CORRECTLY AND CONSISTENTLY FORMATTED? |
| PC only: | |
| Time: | Jul 11, 16:44 |