|
Post by Jón Þór Kristinsson on Feb 6, 2011 18:38:09 GMT -5
Have there been improvements in search in the time (1997-2011) since this research paper was written. And if so in what way?
It is mentioned in the paper that there has been some research in search algorithms that are able to learn, has this been successful?
|
|
|
Post by jonfs09 on Feb 6, 2011 18:40:35 GMT -5
Uhm I didnt really understand much and the questions that I came up with have already been asked.
|
|
|
Post by niccolo on Feb 6, 2011 18:42:03 GMT -5
Notwithstanding I enjoyed the reading and I understand that the purpose of the research was totally empiric-based, I felt like a big lack of theoretical explanation. Have further studies tried to make a theory upon these results? I mean, why do we have these results? How can we explain these topologies, frequencies, differences.. Indeed it happens more then once in the article to read that the authors did not have explanations or made conjectures about something. Two clear examples are at pag. 256: "Finally, we note that between plateaus of level 1 and 2 there is a reordering of the proportion of local minima. For example, problems with 450 clauses have the lowest proportion of local minima of level 1, but the highest proportion of local minima of level 2. We do not have an explanation for this result." " We conjecture that, for larger problems, the proportion of local minima decreases significantly for plateaus of levels higher than 5, but we cannot predict the exact behavior from the data at hand." Not that I do not value empirical researches. Just I feel like a complete theory could provide us better answers and predictability. So, finally, my question is about further researches, because I see that maybe this was a starting point for these kind of studies and it is a classic to first collect empirical data and then to make a theory. Keeping in the empirical exploration of the problem, I wonder if we could benefit from a larger exploration of the graph topology. If I well understand, the article examines 'only' the plateaus regions, basically frequency and dimension. It actually consider also the nearest part of the graph to plateaus (always if I understand correctly). My point are: - is it possible a topological study also on the regions out of the plateaus? That is, is it not possible to conjecture that the way on how the graph gets close to plateaus has some recurrent characteristics and then to use them to avoid to be trapped in plateaus? (of course we should remember that solutions, at the end of the day, are plateaus and that we want to get there)
- do study on the effective topology of plateaus exists? In particular, if we knew the possible shape of benches we could use it to escape. I don't fully get if the authors covered that. This question is related to the one made by Eiríkur Fannar Torfason. I wonder about the probability that we find an exit inside the plateau. If we find an exit surrounded by a plateau, what's its probablity to get us to a global minima? And in general, has the probability of benches' exits to get to a global minima being studied?
I am also interested to know if some algorithms that use sections 6 and 7 suggestions have been developed. Furthermore I'd like, if possible, to see in class a concrete example of these problems and graphs to better understand how all this work.
|
|
|
Post by baldurb09 on Feb 6, 2011 18:56:07 GMT -5
1. The article mentions that “some researchers suggest algorithms like GSAT [...]”—I assume, always?—“[...] become trapped in local minima, [...].” Is it actually possible to verify this? The article also refers to the detection and avoidance as the most important problems in local search algorithms (given that the former assumption is correct), what other prominent problems are there in local search algorithms?
2. Why does the proportion of minima outgrow the proportion of benches as the problem size grows?
|
|
|
Post by hordurh10 on Feb 6, 2011 18:59:25 GMT -5
Could it be of help to turn gravity upside down in some cases?
Can md5 help in remembering state in an efficient way?
|
|
|
Post by gudrunht on Feb 6, 2011 19:01:18 GMT -5
I´m not clear on why local minima is considered more of a problem than benches? One would think that since you cannot get trapped when all of your neighbours look worse it would be less of a problem than that where all of your neighbours look better and hence a possibility of getting trapped.
|
|