# Which metaheuristic methods are admissible for discussion ?

This question is prompted by this post on genetic algorithms, but I think the matter applies more generally as well to other metaheuristic methods like annealing, neural networks and the like.

Are these reasonable topics for discussion on this site ? They are weak on pure theoretical content, but they do crop up "when the theory fails", and there's been a fair amount of discussion on theory blogs (see Michael Mitzenmacher, and myself) on whether these should be taught in algorithms classes, which would make them fair game.

• disagree with the [apparent widely shared] bias that heuristic methods in TCS are "weak on pure theoretical content", whatever that means, to me some of them are stronger on theory than much of other "mainstream" TCS subjs. & feel the tiein to "when the theory fails" is defn a nonsequitur. but am indeed attempting to understand this perspective more .. can anyone articulate it better via refs etc? to me it seems like a concept bordering on academic folklore or even stigma/taboo.. also, plz forgive the question if basic, but what is the difference between a heuristic & a metaheuristic?
– vzn
Sep 2 '12 at 22:11
• When I say "weak on pure theoretical content", I mean "weak on formal guarantees of quality/running time". This is not controversial - most heuristic methods are some kind of local search that deal with local optima and have weak convergence bounds. There is a formal treatment of such heuristics in the work on PLS, PPAD and the like. "Meta"-heuristics are techniques that apply generically to many different problems and are 'parametrized' for each problem: this is also not my term, it's used in the Encyclopedia of approximations Sep 3 '12 at 1:34
• thx for clarification yet feels like sleight of hand or moving goalposts to me =( .. two different concepts & seems there is a strong case there are many algorithms weak on formal guarantees yet still chock full of theory (some even more so than some algorithms with guarantees, because of emergent complexity involved). have never seen literature arguing otherwise & but am open to suggestions. moreover sometimes so-called "weak" algorithms deliver superior even extraordinary results in practice based on domain specific quality measurements. but agree your pov is defn not unique on this site.
– vzn
Sep 3 '12 at 2:32
• @vzn: You and Suresh are talking about different kinds of "theory". TCS is about what we can prove about abstract computation. This is not controversial. Sep 3 '12 at 14:37
• @JɛﬀE .. think your defn is unnec limiting & not unanimous, see 1st answer below which seems to directly contradict it, & measures last/current? group consensus on subj unless theres been sig. drift since posted. there is clearly sig. controversy over the scope of this site across many discussions in meta, easy to find it. there is no strict defn given in the FAQ of what TCS actually constitutes. that is not surprising because moreoever the field of TCS does not have such a consensus either. there are however many individuals in the field with strong but nonuniform opinions on the subj...
– vzn
Sep 3 '12 at 15:22
• No, the first answer does not contradict my claim. "Rigorous theoretical analysis" means proof. Sep 3 '12 at 18:44
• ps not all GAs seem to be provably within PLS or PPAD although it works as a rough approximation. some issues are that the fitness functions can have very high complexity, and also many of the algorithms are not really terminating. they are just run for very long and stopped in practice when improvement becomes negligible. proof is only one tool of rigorous theoretical analysis, admittedly one of the best & most unequivocal. proof is preferred where possible but often unattainable and sig. areas of TCS do not focus on it... in GAs "proof" is in fact discovered and computed by fitness fns!
– vzn
Sep 3 '12 at 18:51
• (this is not sarcastic) Can you provide an example of "rigorous theoretical analysis" that doesn't involve a proof ? Sep 4 '12 at 16:41
• ?! dude, how about this? there is mass research on P vs NP and NP complete problems even though there is no proof that $\mathsf{ P \ne NP}$, and the problem has been open for four decades. or maybe you dont think it has any "rigorous theoretical analysis"? reading your original question above you came out as favoring scope that includes metaheuristics.... scratching my head over here....
– vzn
Sep 13 '12 at 2:25