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: Digital Puer on 18 Feb 2010 14:43 I need some help on identifying a type of "blackbox" combinatorial optimization problem. Also, I would like to figure out when I should look for an approximation algorithm and when I should use some kind of randomised search, like a genetic algorithm or hill-climbing. To place my question in context, suppose I am first dealing with the zero-one knapsack problem. It is a combinatorial problem because I am either selecting or not selecting each item to be placed into the knapsack. Now, the selection process can be guided because it's known that if you order the items by decreasing profit density and choose from them in that order, you can then use an approximation algorithm or a search heuristic like A* or branch-and-bound to get a good solution. Here, one can immediately see how selecting or not selecting an item has an impact on the profit and weight of the knapsack. Now, suppose you have a "blackbox" combinatorial problem where you are either selecting or not selecting items, and you want find the best selection to get the optimal score. However, here you have no idea how to predict the outcome from your choice. You select some items, feed it through a function, and out pops a resulting score. You can assume that for all inputs, some real value other than 0 is returned, but you don't know what is the effect of selecting any particular item, unlike the knapsack problem. As a result, I believe it is not possible to create an approximation algorithm or to use A* (because an admissive heuristic is not known). You would have to use a randomised search, like a genetic algorithm or hill-climbing. So my question is: what is this type of "blackbox" combinatorial problem called? I have called it "blackbox", but is there a more formal name or description? Are such types of "blackbox" problems common? Perhaps this is a machine-learning problem? And getting back to my first question: when faced with this type of combinatorial optimization problem, how would I know when to stop looking for an approximation algorithm and when I should start using a randomised search? A colleague mentioned "convex functions", which I know about, but I don't see how that is helpful here.
From: tchow on 18 Feb 2010 20:32 In article <625dc589-25dc-452c-a02b-f6c31259452c(a)k18g2000prf.googlegroups.com>, Digital Puer <digital_puer(a)hotmail.com> wrote: >Now, suppose you have a "blackbox" combinatorial problem >where you are either selecting or not selecting items, >and you want find the best selection to get the optimal >score. However, here you have no idea how to predict >the outcome from your choice. If the problem is truly a black-box problem then there is nothing you can do other than exhaustive search. The only way you can do better is if there is some kind of structure to the problem. For example, to use hill-climbing, knowing the value of the function at a particular point must convey some information about values at nearby points; if there is no such "neighborhood structure" then moving from one point to a nearby point is not any better than blindly jumping around the search space. In reality, problems that arise in practice do have some structure. There is unfortunately no general method of figuring out the best way to identify that structure and exploit it. The best thing you can do is to identify similar problems to yours that have been studied in the past, and see what techniques have worked well on those related problems. The "Handbook of Approximation Algorithms and Metaheuristics," edited by Teofilo Gonzalez, is a good reference for this purpose. So is "Algorithmics for Hard Problems" by Juraj Hromkovic. -- 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: James Dow Allen on 19 Feb 2010 03:31 On Feb 19, 8:32 am, tc...(a)lsa.umich.edu wrote: > If the problem is truly a black-box problem then there is nothing you can do > other than exhaustive search.... > In reality, problems that arise in practice do have some structure. There > is unfortunately no general method of figuring out the best way to identify > that structure and exploit it.... I assume the structure in OP's problem exists, but is unknown and too complicated to easily deduce experimentally. Since his is simple binary selection, it would seem to be a perfect candidate for the method of Genetic Algorithm. James Dow Allen
From: tchow on 19 Feb 2010 12:20 In article <56520ef0-199e-4dd0-bf8f-35620e0f1587(a)b7g2000pro.googlegroups.com>, James Dow Allen <jdallen2000(a)yahoo.com> wrote: >I assume the structure in OP's problem exists, but is unknown >and too complicated to easily deduce experimentally. Right. >Since his is simple binary selection, it would seem to be >a perfect candidate for the method of Genetic Algorithm. I'm not sure what you're referring to. The OP mentioned a knapsack problem, but as an example of something where he understood the structure well enough to design an approximation algorithm. I didn't see any mention of a specific "blackbox" problem that the OP was having trouble with. -- 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: Digital Puer on 19 Feb 2010 18:06
On Feb 18, 5:32 pm, tc...(a)lsa.umich.edu wrote: > In article <625dc589-25dc-452c-a02b-f6c312594...(a)k18g2000prf.googlegroups..com>, > Digital Puer <digital_p...(a)hotmail.com> wrote: > > >Now, suppose you have a "blackbox" combinatorial problem > >where you are either selecting or not selecting items, > >and you want find the best selection to get the optimal > >score. However, here you have no idea how to predict > >the outcome from your choice. > > If the problem is truly a black-box problem then there is nothing you can do > other than exhaustive search. The only way you can do better is if there is > some kind of structure to the problem. For example, to use hill-climbing, > knowing the value of the function at a particular point must convey some > information about values at nearby points; if there is no such "neighborhood > structure" then moving from one point to a nearby point is not any better > than blindly jumping around the search space. > > In reality, problems that arise in practice do have some structure. There > is unfortunately no general method of figuring out the best way to identify > that structure and exploit it. The best thing you can do is to identify > similar problems to yours that have been studied in the past, and see what > techniques have worked well on those related problems. The "Handbook of > Approximation Algorithms and Metaheuristics," edited by Teofilo Gonzalez, > is a good reference for this purpose. So is "Algorithmics for Hard Problems" > by Juraj Hromkovic. > -- > 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 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 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"? 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. |