It is quite heavy, so do your best to at least extract what the fundamental problems are that here are being discussed. They relate to the topic of 4.1 and 4.2 in the textbook (I will briefly skim 4.1 in lecture on Friday). This paper provides an introduction to the kinds of work done by our first guest speaker Dr. Deon Garrett, who recently joined the The Icelandic Institute for Intelligent Machines. Your questions below will be handed to him on Monday morning, so fire away!
1) considering just the SAT problem (and its several versions) and using statistical data analyzing size/difficulties/number of local minima and benches, is not a limitation? what about other problems? should the result be equal?
2) in some problems in which the search tree is too large and it is impossible to analyze it completely (for example chess), can we use the local search to find a good (maybe not the best solution)? How much is the difference between "good" and "best"?
Post by Ásgeir Jónasson on Feb 5, 2011 10:29:59 GMT -5
When a local minimum is detected and the local search is forced to move to a state of higher level, is it likely that the local search will run into local minima again soon and can that risk be minimized by unsatisfying more than one clause before decreasing the level again, although it may not be necessary ?
- In the section "Next Generation Local Search Algorithms" is mantioned the possibility that this new class of local search algorithms could LEARN which tacticts work better for the current problem to solve. I'm wandering how much performance improvements we can have by using that.
- In local search is important for the result of it the starting point where the search start so i was wondering if there are any statics that show the influence of this choice on the result ?
Post by Helgi Siemsen Sigurðarson on Feb 5, 2011 19:05:33 GMT -5
In the section "Next Generation Local Search Algorithms" what does he mean by learn? does it remember the value of the move and then store it and then later tries to get to it if it is the better score than the ones available ?
Post by Jökull Jóhannsson on Feb 6, 2011 14:24:52 GMT -5
I got little confused after reading this :/ 1)For what problems of today is the local search algorithm used? 2What is the defintion of Unsatisable Problems? Is it a problem with no solution or a solution wich is bad for this algorithm?
Post by Eiríkur Fannar Torfason on Feb 6, 2011 15:30:01 GMT -5
Ambitious reading this week...
1. Is 3-SAT really a good candidate for researching local search behavior? Is it representative of the problems usually tackled using local search?
2. If I were to find myself on a plateu (somewhere in South America perhaps) with limited visibility (fog) and I suspected that I were trapped in a valley (local minima) I guess I'd drop a marker somewhere and then travel along the edge of the plateu and then see if a reached the marker again. Then my suspicion would be confirmed. Would it be possible to switch into some sort of "border travel" mode that behaves similarily when the local search algorithm believes it's on a plateu in the hope that it will lead to an exit?
If most level 1 minima with 100 variables and 430 clauses are less than 1000 states, is it possible to somehow mark the states in those larger than 1000 (or some other upper limit) states plateaus at the time the search space is being generated as states that shouldn't be searched to avoid having to waste computation on finding exits if one of those plateaus is entered.
Last Edit: Feb 6, 2011 17:33:50 GMT -5 by helgil08
Post by Elín Carstens on Feb 6, 2011 17:04:26 GMT -5
1) The authors say that they used GSAT to find the plateaus they analyzed for this paper.
Has similar research been done using other sampling methodologies? I.e. Using other local search methods than GSAT to find plateaus to analyze? If so, did the results differ from the ones presented in this paper?
2) "Our study provides a first step towards identifying features that should be tracked by these self-modifying local search algorithms."
Have any other features been identified other than the ones mentioned in the paper, since it was written?
I do know that this question has probably been asked above but it is the only thing i can think of as even after reading it i cant for the life of me understand how GSATS algorithim works could you please explain it more clearly than the text does