|
Post by Hannes Vilhjalmsson on Feb 1, 2011 10:38:24 GMT -5
Dear students, The reading for next week's discussion is now ready, you can find it here: Frank, J., Cheesman, P. and Stutz, J. (1997) When Gravity Fails: Local Search Topology, in Journal of Artificial Intelligence Research, Vol. 7, pages 249-298, Morgan Kaufmann Publishers.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! Cheers, - Hannes Högni
|
|
|
Post by carmine on Feb 5, 2011 10:18:26 GMT -5
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 ?
|
|
|
Post by lorenzo on Feb 5, 2011 11:14:43 GMT -5
- 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 finnur on Feb 6, 2011 9:20:44 GMT -5
this paper was published in 1997, im thinking, he talks about next generation of local search algorithms that could learn which tactics work best, has that been accompliced yet?
|
|
|
Post by thorsteinnth on Feb 6, 2011 11:35:48 GMT -5
Ég skil ekki neitt í útskýringunum í þessari grein...
1. Hvernig virkar þessi GSAT algorithmi?
2. Hvað er "border"?
3. Hvað þýðir afgangurinn af greininni?
|
|
|
Post by Hrafn J. Geirsson on Feb 6, 2011 13:44:28 GMT -5
About the article (I will be confused for weeks):
1) In what cases would one want to use an adaptive search algoritm ?
2) What is topology and how does it relate to search algorithms ?
To our guest speaker:
3) Is there a set of common structures which are the most beneficial for a search algorithm to exploit ?
4) How big a part of your job revolves around doing statistical analysis on algorithms ?
|
|
|
Post by kristjan on Feb 6, 2011 14:22:15 GMT -5
In what sort of problems do you consider most efficient to use local search to solve the problem?
|
|
|
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 grimurtomasson on Feb 6, 2011 15:21:47 GMT -5
1. The authors do an analysis of the nature of the problem they picked (3SAT), was this work done before the time of statistic learning search algorithms like Monte-Carlo search?
2. Did this paper effect any changes in the way the AI community approached local-minima and plateaus in local-search algorithm design?
|
|
|
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?
|
|
|
Post by helgil08 on Feb 6, 2011 16:21:16 GMT -5
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.
|
|
|
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?
|
|
|
Post by GSATS on Feb 6, 2011 18:30:14 GMT -5
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
|
|