When do I have to resort to a randomised search for a combinatorial algorithm?
in [Theory]
|
Prev: Call for Papers: FCS'10 (The 2010 International Conference on Foundations of Computer Science), USA, July 2010
Next: beautiful indian girls see and enjoy
From: tchow on 19 Feb 2010 21:16 In article <d6380fe3-a7e4-470b-98ee-299b83be3599(a)k6g2000prg.googlegroups.com>, Digital Puer <digital_puer(a)hotmail.com> wrote: >Thanks for the reply. You mentioned "neighbourhood structure," >namely that "knowing the value of the function at a particular point >must convey some information about values at nearby points." > >Is there a formal terminology for this type of structure for the >evaluation function? For example, the function can be "structured" >or "structureless"? If you're asking about formal terminology for neighborhood structure, then I think the closest thing may be the concept of PLS-completeness. See for example http://faculty.cs.tamu.edu/chen/courses/637/2004/pres/pre2.pdf >If there is such a terminology, is there any published textbook or >article that states outright that "the lack of neighbourhood structure >limits the effectiveness of search-space algorithms like >hill-climbing or genetic algorithms"? No, but the point I was trying to make was a rather trivial one. If you have a black-box function and know nothing about it, then there is obviously no way to find the global optimum except by exhaustively trying all the values. As long as there is some value you have not yet tried, there is a possibility that one of the unknown values is the optimum. In real life, functions you're interested in are not *actually* black boxes. They may be *seemingly* structureless, but one cannot rule out the possibility that there is structure there that you just aren't smart enough to see. Therefore, as I said before, there is not going to be any simple step-by-step recipe you can follow to decide whether a particular problem is going to yield to a nice approximation algorithm, or to a hill-climbing technique, or to nothing better than exhaustive search. Having said that, I should mention that there are some concepts in computational complexity theory that can help you decide how good an approximation algorithm you can hope to find. For example if a problem is APX-complete then there is no polynomial time approximation scheme for it (unless P = NP). If it is XP-complete with respect to some parameter then you cannot expect it to be fixed-parameter tractable. I won't explain these buzzwords here (you can easily look them up); the point is that sometimes you can show that you cannot hope to find an approximation algorithm unless P = NP. >As I wrote in my original post, a theorist colleague mentioned that >it would be helpful if the function were convex, which I think would >be >an overkill example of neighbourhood structure, since a convex/concave >function would imply a global optimum, making the search very easy. What you say sounds right to me, too. Without further information I'm not sure what that colleague had in mind. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Paul E. Black on 24 Feb 2010 13:09 On Friday 19 February 2010 21:16, tchow(a)lsa.umich.edu wrote: > In real life, functions you're interested in are not *actually* black > boxes. They may be *seemingly* structureless, but one cannot rule out > the possibility that there is structure there that you just aren't smart > enough to see. Therefore, as I said before, there is not going to be any > simple step-by-step recipe you can follow to decide whether a particular > problem is going to yield to a nice approximation algorithm, or to a > hill-climbing technique, or to nothing better than exhaustive search. Although not the original question in the past I tried literally random sampling of the space to get some sense of the structure. (Choosing the order of variables to minimize the size of a BDD.) In my case most samples were pretty close to the optimal with a very long, sparse tail. So I could choose a few random sample, then randomly mutate the best one to get very close to optimal - kind of a randomized hill climbing. -paul- -- Paul E. Black (p.black(a)acm.org)
From: tchow on 24 Feb 2010 13:42
In article <hm3q0402km3(a)news2.newsguy.com>, Paul E. Black <p.black(a)acm.org> wrote: >Although not the original question in the past I tried literally >random sampling of the space to get some sense of the structure. >(Choosing the order of variables to minimize the size of a BDD.) In >my case most samples were pretty close to the optimal with a very >long, sparse tail. So I could choose a few random sample, then >randomly mutate the best one to get very close to optimal - kind of a >randomized hill climbing. Some other ideas along these lines are described in the book "Reactive Search and Intelligent Optimization" by Battiti, Brunato, and Mascia. One of the basic ideas is to use machine-learning techniques to learn what the landscape looks like and to design one's search accordingly. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences |