Talk:Metaheuristic

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Systems (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
Taskforce icon
This article is within the field of Operations research.
 

Genetic algorithms vs. metaheuristics[edit]

The timeline includes lots of developments that relate more to genetic algorithms than metaheuristics. I don't think advances in genetic algorithms are necessarily relevant. And the timeline doesn't even include Eurisko! -24.17.243.81 (talk) 00:24, 1 October 2009 (UTC)

  • AFAIK, in spite of the "algorithm" in the name, general genetic algorithms are usually metaheuristics, and their applications to specific problems are usually heuristics. If any entries of the list are not general ("metaheuristics") but problem-specific ("heuristics") they should be removed. Otherwise the various flavors of genetic algorithms do belong to the list.
    On the other hand, if the timeline becomes too long, perhaps it should be moved to a separate article, and replaced by a single paragraph mentioning only two or three of the most important developments. --Jorge Stolfi (talk) 13:40, 23 October 2009 (UTC)

Heuristic search in AI[edit]

There are lots of works on heuristic search in Artificial Intelligence which are not mentioned in the article and definitely belong in it, including A* and its extensions. —Preceding unsigned comment added by 203.143.165.77 (talk) 06:39, 20 May 2008 (UTC)

Merge[edit]

Hi All, I've an undergrad degree in Computer Science. It is incorrect to redirect heuristic algoritm to this page. A heuristic algorithm is any algorithm that one believes typically comes up with a good solution. I'm not sure about this particular term but in context, this discusses a broad class of heuristic algorithms. Heuristic algorithm don't have to be iterative. For example, my undegraduate thesis was on standard bin packing algorithms and the class I was looking at produced a packing in the order that packets arrived. First Fit would be such an algorithm. Its not really the type of algorithm discussed here. —Preceding unsigned comment added by 70.54.93.18 (talk) 02:29, 3 October 2010 (UTC)


Diomidis Spinellis believes this page would be better off at metaheuristic. I agree. However, the approach Diomidis Spinellis took, by cut and paste, is not the right one, since that destroys the page history.

I would like to ask an admin to delete the redirect now at metaheuristic, then move this page there. The links to this page were already taken care for. Thank you. Oleg Alexandrov 17:37, 27 Apr 2005 (UTC)

  • Agree. Corrects a glaring usage error. ---Isaac R 17:55, 27 Apr 2005 (UTC)
Done. Lachatdelarue (talk) 22:11, 28 Apr 2005 (UTC)
Dear Lachatdelarue, thanks! Oleg Alexandrov 23:03, 28 Apr 2005 (UTC)

Citing sources[edit]

Hi All. It is unclear whether some of the text in the article is the writers’ thoughts, or generally accepted fact. As an encyclopedia, citation is necessary to back up arguments. --Daleh 12:29, 27 September 2006 (UTC)

The opinions in the text are clearly not generally accepted. In fact, they seem to come from someone who hates metaheuristics. Evolutionary computation researchers such as myself take serious issue with statement such as that no particular class of metaheuristics does better than any other for particular problem classes. Also, many of us are not very convinced of the wide-ranging implications of the no free lunch theorem. Daleh

Hi Daleh, I'm confused why somebody would "hate" metaheuristics. Assuming that this is a correct term for said class of heuristic algorithms, its a valid approach to a great deal of problems. I'm really annoyed that somebody seems to have "merged" heuristic algorithms into this; that was dumb. Its like having a topic "dogs" and merging it into the German Shephard entry. Most obviously a lot of people who don't have computer science degrees have played with this? —Preceding unsigned comment added by 70.54.93.18 (talk) 02:32, 3 October 2010 (UTC)

Clear bias and misleading discussion[edit]

This article contains a clear bias against metaheuristic based approaches. I find the language used is especially emotive and far from an objective description or assessment of the concept.

I also find the final paragraph of the "General criticisms" section to be highly misleading. Whilst the paragraph is factually correct in its statements regarding continuous non-linear optimisation, it implies these methods should be easily applicable in metaheuristics. Given that metaheuristics are primarily used for combinatorial optimsation and constraint satisfaction problems where the solution space is discrete I find this to be a highly dubious and un-supported inference.



Axiomaticus 03:05, 8 May 2007 (UTC) A heuristic has been developed for achieving a minimum makespan schedule for the shop. The heuristic considers both jobs in a given queue and those yet to arrive at any machine, to sequence the operations to be processed on all machines. It is a singlepass procedure and creates a feasible, near-minimum makespan schedule

Free lunch not specific to metaheuristics[edit]

With regard to the comments about spaces deceptive to metaheuristic algorithms, and to the no-free-lunch theorem. The no free lunch theorem applies to all algorithms and all problems, the it is as easy to find a function to fool a second order method, or to cause slow convergence as it is to for any algorithm.

--87.192.57.3 12:14, 22 May 2007 (UTC)Conor

  • Yes, but people who use continuous optimization methods are conscious of their limitations; whereas many users of metaheuristics seem quite unaware of that.
    I have seen people waste huge amounts of time trying to find a metaheuristic that would be good "in general". Readers must be warned that such a thing does not exist, and that no meta-heuristic can be shown to be better "in general" than any other. One cannot "prove", theoretically or empirically, that A-teams are better than Tabu Search, or the Genetic Algorithm is better than Simulated Annealing. One cannot even specify for which sorts of problems and/or heuristics one is better than the other. Why shouldn't the article say so?
    All the best, --Jorge Stolfi (talk) 00:59, 7 December 2009 (UTC)
All that need be said about this topic was said by Phil Wolfe in his famous parody (by "anonymous") of "A universal algorithm for optimization", in Math Prog. c. 1973!  Kiefer.Wolfowitz  (Discussion) 22:51, 22 February 2011 (UTC)
From the article: "However, when these restrictions are stated at all, they either exclude most applications of interest, or make the problem amenable to specific solution methods that are much more efficient than the meta-heuristic." This seems like a bit of a stretch, how do we know they exclude "most applications of interest"? Criticism is good, but this seems to be totally slating metaheuristics in a possibly unfair way. Maybe I just don't feel right about the "no free lunch" theorem in the first place. All algorithms are not equal - I can easily make an algorithm that's twice as slow as brute force search by purposefully retreading my footsteps in the state space search. Why can't one algorithm be twice as fast as another, for many interesting and realistic problem domains? Destynova (talk) 16:17, 24 February 2010 (UTC)

Reference to Hessian irrelevant?[edit]

I agree with Axiomaticus, this article is presented in a very biased manner that would seem to me to be founded in the authors limited perspective on metaheuristic methods. In addition it is not, in my opinion, even factually correct. For instance evaluating the hessian at a particular point in space to obtain a good search direction works very well on some problems, but for others where the search space is non-smooth or discontinuous or for some other reason cannot be approximated using for instance, a taylor series expansion about a point or using some other perturbation methods, the hessian will be difficult to evaluate and may be a very misleading.

--87.192.57.3 12:14, 22 May 2007 (UTC)Conor

I agree with Axiomaticus and the user at 87.192.57.3 , that this article, and especially the "Criticism" section is presented in a very biased manner, that lowers the standard of wikipedia in general. The statement about better thinking and programming is an insult, there are no citations in that section, there are misleading and false assertions (e.g. "no meta-heuristic can be shown to be better for any specific problem than brute force search" - better in what sense?). The whole paragraph about Hessian methods and their comparison to metaheuristics indicate the author does not understand that the class of problems where "Hessian-based methods reach [the optimum] in one step" is not so broad; what happens if derivatives cannot be calculated for example? it is apparent that if the problem under consideration is amenable to a method that is guaranteed to yield a GLOBAL (not local) optimum, that method should be used. If not, either a specialized heuristic that is proved to be more efficient than a meta-heuristic, or if no such algorithm exists, a general meta-heuristic, must be used to find a near-optimal solution; perhaps in conjunction with a relaxed version of the model, to have both upper and lower bounds of the optimal solution. My opinion is that this section is a more of an attack to meta-heuristics than an encyclopedia entry and should be deleted. —Preceding unsigned comment added by 93.40.50.97 (talk) 15:32, 30 September 2009 (UTC)

  • I have seen people waste months of work trying to tune a metaheuristic that was taking hours to solve nonlinear optimization problems that a classical nonlinear optimization method would have solved in seconds. In one particular case, the goal function had only six variables but a very narrow "valley" in six-dimensional space. If that "victim" had been taught about nonlinear optimization, he would have realized that the metaheuristic was essentially doing a crude version of gradient descent (actually worse, see below), and he would know that such narrow valleys trap gradient descent into bouncing back and forth across the valley. He would also know that narrow valleys are the rule, not the exception, in problems with more than 2--3 variables. And he would have known that the Hessian (which one can build from O(n^2) function probes, or O(n) gradient probes) is necessary to have an intelligent guess at the position of the minimum, and escape from the narrow valley curse; and that no amount of smartness in the algorithm can compensate the lack of the Hessian.
    If the goal function is completely irregular, of course, continous methods won't work --- but metaheuristics won't either. In that case no metaheuristic will beat the trivial one (generate N random candidates and pick the best). Metaheuristics only work if the goal function has some structure; by understanding that structure, even a little bit, one can usually save months of computation and metaparameter-tuning. If the structure is "a smooth function with a lot of noise added", then one can use continuous optimization after smoothing the function, and it should be an effective way to get close to the minimum.
    In one of those narrow valley cases, the "victim" happeend to choose Genetic Algorithm. The crossover method was such that mixing two good solutions would, with probability near 1, generate a solution much, much worse than both. Only when the two solutions were really close to each other the crossover had a chance to be slighlty better. So in this case GA was basically an extremely inefficient way to perform local descent.
    I could cite other examples, but the gist is that a lot of time and energy has been wasted beause people were not properly warned about the limitations of metaheuristics in general. Unfortunately much metaheuristics literature is overly optmistic and fail to properly warn the readers on that point. If the caveats in that section of the article can save one person from that trap, it will have earned its right to be there. All the best, --Jorge Stolfi (talk) 00:25, 7 December 2009 (UTC)

Inventor of the term "metaheuristic"[edit]

Something else I cannot understand is the fact, that the inventor of the term "meta-heuristic" with a french quote is linked to an professional NHL player and coach. Sorry, but I cannot believe this. Not because of a lack of intelligence but as a lack of time and interests. So please, fulfill the site of the linked "Fred Glover" with his scientific career or correct the link with the right person. Thanks. --User: Guest 22:12, 09 May 2009 (MEST) —Preceding unsigned comment added by 134.109.84.112 (talk)

  • The fake Fred Glover currently referenced is DEAD; the real Fred Glover Fred Glover, a professor at the University of Colorodo, is very much ALIVE and is still pumping out lots of papers. 69.109.41.33 (talk) 18:05, 25 July 2009 (UTC)
    • I have create the Fred W. Glover page and I am linking to it.
      By the way, if the article is in English, why is the quotation in French?
      All the best, --Jorge Stolfi (talk) 00:57, 7 December 2009 (UTC)
Fixed. Found the original article and replaced the translated-to-French and retranslated-from-English-to-French-to-English version with the original English text. No idea how that happened... :P Destynova (talk) 16:24, 24 February 2010 (UTC)

Timeline section[edit]

This tag was pasted onto the "Timeline" section:

In what sense it is "off-topic"? GA is a metheuristic too, right? --Jorge Stolfi (talk) 00:25, 7 December 2009 (UTC)

Major update.[edit]

Dear All,

This page has had a major update to make it more informative and scientific.

Several items have been removed from the timeline, not because I want to pass judgment on what is a significant contribution and what is not, but because the newer and as of yet unestablished contributions to the research field should at least have proper Wikipedia pages before being added to this list. Please don't use this page as a promotional billboard.

I hope you all like the new page, which took me a long time to make.

Optimering (talk) 13:22, 16 May 2010 (UTC)

The page was way better before...... and less biased. BTW who the fuck is pedersen??? Your brother?

original research[edit]

The article contains original research, which is contrary to wikipedia guidelines:http://en.wikipedia.org/wiki/Wikipedia:No_original_research

The relevance of the time-line history can be very easily debated (for me, it is "original research"). The criticism section also does not seem to cite too many references. While almost any wikipedia page could contain such a section, criticism sections do not seem to be very encouraged by the policy of wikipedia. —Preceding unsigned comment added by 84.98.0.99 (talk) 18:04, 2 July 2010 (UTC)

I think the TL is interesting, but some of its more recent stuff (e.g Monkey Search) may need citations to show they aren't vanity links. It also doesn't include the first stochastic work -such as the Monte Carlo method- which are almost a precursor algorithm wise, as they are first optimisation techniques to use randomness as part of the solution. SteveLoughran (talk) 14:26, 2 August 2011 (UTC)
I removed the Time-Line, which was OR. Kiefer.Wolfowitz 20:48, 8 April 2013 (UTC)

Updated related links section[edit]

I am currently doing a dissertation on metaheuristics and have generally found the 'related pages' section on relevant wiki pages to be largely confusing and poorly organised. Now I have a greater understanding, I have been going around the various pages, this one in particular, and edited the sections to be more uniform, helping the reader to place the topic within its greater context. I hope my edits will be found to be beneficial. Talk or edit otherwise :) Jr271 (talk) 17:31, 27 March 2011 (UTC)

About Criticism section[edit]

You write "the work by Trelea,[57] amongst others, for analysis of particle swarm optimization". However Trelea is explicitely starting from

[59] Clerc, M. & Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space IEEE Transactions on Evolutionary Computation, 2002, 6, 58 - 73

Another important work is the thesis

[60] Van den Bergh, F. An Analysis of Particle Swarm Optimizers Department of Computer Science, University of Pretoria, 2002 which also quotes [59], which indeed seems to be the very first one (and which has been awarded by IEEE TEC). — Preceding unsigned comment added by 78.229.106.132 (talk) 07:29, 25 September 2011 (UTC)

Heuristic (computer science) redirects here[edit]

Heuristic (computer science) redirects here but I'm not convinced this is the only thing that can be meant by a heuristic. Opinions on removing the redirect and placing an article at Heuristic (computer science)? RJFJR (talk) 22:30, 14 February 2012 (UTC)

Contradictions with the Local Search Entry[edit]

According to the "Local Search" entry in wikipedia, Tabu Search and Simulated Annealing are subfields of Local Search, according to this page they are not (I'm specially referring to the image containing a classification of the techniques).

Honestly, I think the whole of metaheuristics is a subfield of Local Search, and not the other way around, but since it's just a matter of labeling, I think it's fine either way. But at least the inconsistency I point out should be sorted out. — Preceding unsigned comment added by 69.249.184.238 (talk) 15:49, 15 April 2012 (UTC)

Indeed metaheuristics as a whole is a subfield of local search. Having genetic algorithms as a disjoint set form local search (as in the diagram) seems to be very misleading (for not using a stronger word). — Preceding unsigned comment added by 76.98.108.46 (talk) 01:34, 2 June 2014 (UTC)

Bias in the Main contributions[edit]

Some (many) of the methods in the section "Main contributions" are not the main contributions. Many of them are not even cited by ten other papers in the area of Metaheuristics. It seems that every paper which is published in this area is listed in this wiki page. For example "galaxy-based search algorithm", in two years, have been cited by three other papers, two of which are by the author of the original paper. How can this be a main contribution?

This list should contain those algorithms and methods that are accepted by the other researchers and have something like more than 100 citations. Every paper published about Metaheuristic algorithms is not a main contribution.

One alternative solution is to change the title of the section and call it "All of the contributions" instead of "Main contributions". — Preceding unsigned comment added by 165.91.242.169 (talk) 18:14, 14 February 2013 (UTC)

Yes check.svg Done Diego (talk) 18:51, 14 February 2013 (UTC)
This article attracts quite some citation spam. This article needs some pruning here and there and only mention publications and researchers that have been discussed in many secondary sources (and thus have a high citation count) or, ideally, tertiary sources. —Ruud 09:55, 7 April 2013 (UTC)
The article has also been written as Original Research, in which papers are touted as being important but no references discussing the papers have been given.
There are plenty of survey articles and texts in this field, and they should be the sources for this article. I removed stuff that (1) lacked secondary sources and (2) were not known to me to be important.
I do not claim infallibility. Kiefer.Wolfowitz 20:47, 8 April 2013 (UTC)

Biased view is observed[edit]

including a quotation of an unknown researcher in the main page of metaheuristic and act according to his guidelines is totally ridiculous. Who is this Sorensen, someone with papers that almost nobody cites and this paper of him you have included in the page has been published in a journal with impact factor less than 0.7. Somebody seems to desire very much to play the role of dictator in this big field of science.

Unsigned comment by User:Hoodaan (KW)

If you continue to make attacks against Sorensen or any living person, such as imputing a wish to be a dictator, you will be blocked from editing. Is that clear?
You are welcome to improve the article by using high quality reliable sources. Please use survey and review articles in leading journals, or other writings by leading researchers. Please limit this talk page to discussions of improving the article. Wikipedia is not a forum or chatting site.
Please sign your comments. Thanks! Kiefer.Wolfowitz 18:43, 9 April 2013 (UTC)

You did not get my point. The point is acting based on a single paper which is just published does not seem scientific. As you mentioned earlier at least 100 citations are needed. How many citations does this paper have? If you read the paper, you see that it is void of mathematical proofs or any experiments and the idea in the paper is totally based on his personal view. I just mention that double standard is not an academic procedure. Moreover, my comments were in no purpose to insult anybody. Thanks Hoodaan (talk) 11:17, 10 April 2013 (UTC)

Restoring the list of meta-heuristics on a different page[edit]

In the past there used to be a large list of metaheuristics, most of which were reputable (like the ant/bee based one).

Rather than add those back into this article, I am adding a link in the also see section for: List of metaheuristics. I merely copied and pasted an older draft from 2013 to preserve much of what was already there. Please help the article in progress (http://en.wikipedia.org/wiki/Wikipedia_talk:Articles_for_creation/List_of_Metaheuristics).

You need to provide reliable sources stating that the contributions were important. The original sources are useful, but they don't establish reliability or notability. Also, lists are notorious for self-promotion problems. Kiefer.Wolfowitz 23:05, 9 April 2013 (UTC)
While some of the metaheuristics are self-promoted, I know for a fact that the ant-colony based meta-heuristic is in several books and you can find it discussed extensively on the Internet. I also know that MOGA is used in Sandia's Dakota Toolkit (http://dakota.sandia.gov/software.html). The article may not be ready to be published as of yet, but I believe that the list could be edited to keep only those that have full-fledged wikipedia pages. Simply removing the information altogether is too drastic and I believe worse than leaving published peer-reviewed research (even if it is "original," it has been peer-reviewed). I do not believe the list should be rejected, but should be refined as there are several good resources and links still available on it. — Preceding unsigned comment added by Mouse7mouse9 (talkcontribs) 23:07, 9 April 2013 (UTC)
Also, self-promoted research, as long as it is peer-reviewed does not count as original research according to Wikipedia's own definition (http://en.wikipedia.org/wiki/Wikipedia:No_original_research). "Wikipedia articles must not contain original research. The term 'original research' (OR) is used on Wikipedia to refer to material—such as facts, allegations, and ideas—for which no reliable, published sources exist."Mouse7mouse9 (talk) 23:20, 9 April 2013 (UTC)