Dennis Weyland's Blog

In this blog post I would like to talk about the harmony search algorithm. I have written two critical journal articles regarding this heuristic, which have received wide approval in the research community, but also triggered harsh responses by the inventor of this optimization approach, Zong Woo Geem. I will present my personal experience with the harmony search algorithm in chronological order, including the two journal articles, the response by the inventor of harmony search and other related events. At the end of this blog post I will try to detect the underlying causes that lead to such things as the harmony search algorithm. From my personal point of view these causes are rooted in our current research system which seems to be fundamentally flawed and gives false incentives to researchers and all the other parties that are involved in the research process.

My first encounter with harmony search

I have encountered the harmony search algorithm for the first time in a conference talk in 2009 (J. Greblicki and J. Kotowski. Analysis of the properties of the harmony search algorithm carried out on the one dimensional binary knapsack problem. In Computer Aided Systems Theory, Eurocast 2009, pages 697-704). Despite the unusual analogy to jazz music, the approach looked to me like a simple evolutionary algorithm. Nothing sophisticated, no features like self-adaption or others, just very simple mutation, recombination and selection operators. This was one of my first conferences and at that time I was seriously shocked.  Now, after being in academia for a few years, I would be surprised if the proportion of publications which have actually a non-negative value would be more than 5%. But at that time I was really shocked. I thought that such a research work is among the exceptions and I tried to ignore that issue.

In the following months and years I was confronted with the harmony search algorithm over and over again. It seemed to me that there was an extreme quantity of publications regarding so-called novel heuristics based on the most absurd metaphors: the intelligent water drops algorithm, monkey search, cuckoo search, the bat algorithm, the galaxy-based search algorithm, quantum evolutionary algorithms, weed colony optimization, the great salmon run optimization algorithm, the wisdom of crowds algorithm, the shuffled frog leaping algorithm, cat swarm optimization. I could no longer ignore this issue and decided to take a closer look at all these presumably new approaches. My initial plan was to write a very general article about all of these methods. What I did not realize at that time was that just the vast amount of these approaches would make such a project impossible. In any case, I started with the harmony search algorithm and during my investigations I was discovering so many flaws with just this specific algorithm that I finally decided to write an article focusing only on harmony search.

My first article

What I figured out was that harmony search is indeed a special case of evolution strategies, using very simple selection, mutation and recombination operators that were known for a long time. More than 30 years after the introduction of evolution strategies, the mathematically identical algorithm was proposed using a different terminology, namely that of jazz music. Definitely nothing worth of 586 publications (according to a google scholar search in 2010 for “Harmony Search”, including the quotation marks). I have published these results with a slightly informal, but nevertheless correct and accurate, proof in a journal article (D. Weyland. A rigorous analysis of the harmony search algorithm: How the research community can be misled by a “novel” methodology. International Journal of Applied Metaheuristic Computing 1 (2), pages 50-60). In the same article I have also investigated several publications related to harmony search, mainly the top hits from the google scholar search that were freely accessible for me. Apart from that I gave arguments for the fact that I do not expect any real novelties from the analogy to jazz music in the context of optimization and that “research in harmony search is fundamentally misguided and that future research effort could better be devoted to more promising areas”.

The response to my first article

I thought that for me the whole harmony search case would be closed after that. But I was completely wrong. Shortly after my article got published, the “inventor” of harmony search, Zong Woo Geem, responded by publishing a research commentary (Z.W. Geem. Research commentary: Survival of the fittest algorithm or the novelest algorithm? International Journal of Applied Metaheuristic Computing 1 (4), pages 75-79). I can just recommend to everyone to read this research commentary, written by someone we consider to be among our peers in the research community. In any case, I would like to discuss a few of his statements in the following. If this discussion will get too boring at some point, I would suggest to directly skip to the next section.

Let me start with the abstract. The first misunderstanding is already revealed in the first sentence of the abstract, where the Geem writes that I have claimed in my article that “harmony search is equivalent to evolution strategies, and because the latter is not popular currently, the former has no future”. What I have done is different: I have proven that harmony search is a special case of evolution strategies. It is not just a claim, it is a statement which has been carefully proven. And more important, the relationship between harmony search and evolution strategies is no longer negotiable. The results have to be accepted based on fundamental scientific principles, even if it is contrary to one’s own opinion and beliefs. Apart from that I have never argued that harmony search has “no future” because evolution strategies are currently not popular. In fact, I never made any statements about the popularity of evolutionary algorithms or evolution strategies. My argumentation follows a different scheme: (1) Harmony search is a special case of evoluation strategies. (2) In particular, these evolution strategies use common selection, mutation and recombination operators and are therefore representatives of this algorithm family. (3) Harmony search can never be more efficient than the best evolution strategy. (4) Research in harmony search explores already well traveled paths which is a huge waste of resources. (5) In a whole decade the harmony search community did not discover any new principles or mechanisms in the field of heuristics. (6) The only novel concept of harmony search is its metaphor of jazz music. For obvious reasons the underlying metaphor is not a relevant criterion for the success of heuristics. (7) I personally do not see any potential to discover new principles or mechanisms in the field of heuristics based on the metaphor of jazz music. (8) Based on all these observations I have claimed that “research in harmony search is fundamentally misguided and that future research effort could better be devoted to more promising areas”. It seems that Geem completely misunderstood crucial parts of my article and this becomes evident already in the first sentence of the abstract.

Geem then continues to explain the purpose of his research commentary which is “to rebut the original paper’s claims by saying (1) harmony search is different from evolution strategies because each has its own uniqueness, (2) performance, rather than novelty, is an algorithm’s survival factor, and (3) the original paper was biased to mislead into a predefined conclusion”. It is easy to see that Geem can not succeed with his first goal, since I have already proven that harmony search is a special case of evolution strategies. Apart from the underlying metaphor of jazz music, the resulting algorithm of harmony search does not differ from a common subclass of evolution strategies. With his second goal I could almost agree, although I think performance is not the only important criterion for the success of an algorithm and a novel approach may be interesting just for its novelty. In any case, harmony search is neither a novel method nor does it outperform other heuristics and therefore the second goal seems to be irrelevant in this context. As I have said before, as a special case of evolution strategies, the only novelty of the harmony search algorithm is its metaphor of jazz music, which is not relevant from an algorithmic point of view. For the same reason, because harmony search is a special case of evolution strategies, it can not outperform the best evolution strategy. In other words, the best evolution strategy is always at least as good as the harmony search algorithm.

Almost every single sentence of the research commentary is worth to be discussed like I have done it for the abstract, but I think this would go way too far. Instead, I will discuss the most crucial statements from a higher level in the remaining part of this section.

Let me begin with a point that I have already raised in the discussion of the abstract. Throughout the research commentary Geem accuses me to claim that harmony search is equivalent to evolution strategies (“I cannot imagine how the author concluded that HS equals ES with these different problem set and algorithm structure.” / “The author claims that because both HS and ES use solution population and produce one solution per iteration, HS is equivalent to ES if the latter is tweaked.” / “If ES really equals HS, it should be more popular in major literature because of its performance regardless of its novelty.” / “Also, if ES equals HS, GA also equals HS after tweaking GA (uniform crossover, neighboring mutation, multiple parents (polygamy?), etc). But, why did the author insist ES = HS rather than GA = HS?'” / “His logic is HS equals ES…”). Once again, I did not claim that harmony search and evolution strategies are equivalent. I claimed and proved that harmony search is a special case of evolution strategies. In my article I did not explicitly state my result as a theorem followed by a proof, but the logic of the article followed exactly this scheme and it is sad that Geem is not able to understand that. In fact, he writes “His logic is … without any rigorous analysis such as theoretical proof or numerical example.” and “… he should use academic way (mathematical proof or numerical results)…”.

One important point that Geem raises throughout his research commentary is that the success of an algorithm depends highly on its performance (“Again, any algorithm, which performs better, is naturally selected by the research community…” / “Rather, its performance such as solution quality and computational effort is the key factor to accept.” / “I believe HS was selected because it has performed better than other algorithms instead of novelty.”). I completely agree that performance is a very important property of an algorithm or a heuristic. But since I have shown that harmony search behaves in the same way as a common evolution strategy, it is theoretically not possible that it beats evolution strategies. Applying the best possible evolution strategy to a problem should always lead to the same or even better results than applying the best harmony search algorithm. Geem also asks “Why is ES not popular in one of my research areas?’‘. Assuming that harmony search performs well, the same or even better performance can be expected from evolution strategies. So it is indeed puzzling why evolution strategies or other methods are not that popular in this research area.

Another issue raised by Geem is that not he, but I am misleading the research community. The first part of my article contains a formal proof of the relationship between harmony search and evolution strategies and I do not see how this can be misleading in any way. I have then discussed certain publications about harmony search more in detail and the author complains several times about my selection of these publications. I have carefully explained in my work how the publications were selected for the discussion. I selected those publications that were found by a google scholar search and that were freely available. It might be that this selection of publications is not representative for the whole field of harmony search, but I seriously doubt that. In any case, this was not any form of biased selection one could complain about. I can also not understand how the author tries to defend the experimental setup used in many of the harmony search publications. Several issues that are fundamental to conduct meaningful experiments are just not respected and therefore the conclusions drawn from these experiments are of very limited significance.

It is also quite funny that Geem honestly exhibits his lack of knowledge (“Although I do not know much about ES…” / “Most importantly, when I searched Wikipedia, I could not find the structure (mu + 1)-ES …” / “Maybe (mu + 1)-ES is possible, but appears not popular.”). At some point he states that “ES was developed to solve continuous-valued problem … while HS was originally developed to solve discrete-valued problem…” and uses this an argument against my mathematically proven results. It is quite interesting to note that some of the very first applications of evolution strategies indeed dealt with discrete-valued problems (I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. 1973). This was around 30 years before harmony search has been proposed, at a time where optimization was performed without the help of computers and where Galton boxes were used to create discrete random values. In the same publication the above mentioned (mu + 1)-ES has been discussed. It also seems that the author was consulting literature to find a match between harmony search and evolution strategies (“In other words, I never found any exact match between ES and HS with respect to the algorithm structure, …”). This is quite confusing, considering the fact, that I have discussed the relationship of harmony search and evolution strategies in detail in my article and that independently such a discussion has also been performed in another article (M. Padberg. Harmony search algorithms for binary optimization problems. In Operations Research Proceedings 2011, pages 343–348). All in all, I am very grateful to the author of the research commentary for being honest about his lack of knowledge in the field of optimization and about demonstrating that he does not possess the prerequisites to conduct research in this field.

At one point Geem himself suggests that harmony search might also be a special case of genetic algorithms (although he formulates it slightly different: “Also, if ES equals HS, GA also equals HS after tweaking GA (uniform crossover, neighboring mutation, multiple parents (polygamy?), etc).” I think it might be the case that harmony search is also a special case of genetic algorithms (which would reveal the not very surprising and probably known fact that the intersection of evolution strategies and genetic algorithms is not empty). The author then continues with the following two questions: “But, why did the author insist ES = HS rather than GA = HS? Is this because GA is still popular while ES is not?” Apart from the fact that I did not prove equality of the two methods, I do not know why I selected evolution strategies and not genetic algorithms. It was definitely not because of the popularity of any of these two methods. I am quite sure that it is possible to prove that harmony search also falls into the genetic algorithms framework, which would even strengthen the argumentation of my previous article. I would be glad to publish such a proof, if this would be received by Geem in a more scientific way than it was the case with my first article.

It is also interesting to note that Geem attacks me personally and insults me in his research commentary (“… instead of being rejected by an unverified author who pretends to be an Ultimate Being.” / “I guess that the author was pressed to publish a paper using predefined conclusion and biased bases.” / “In this paper, I tried to briefly demonstrate how fictitiously the author wrote a ‘novel’.”. He also calls my article a “hoax paper” and tries several times to instruct me (“However, if the author wants to write a real paper, his logic should be…” / “If the author really wants to criticize a theory, he should use academic way (mathematical proof or numerical results) rather than malediction with predefined conclusion and biased supports. Only in that way, the real chance for the author to write a good paper is given.”). The whole research commentary is also full of absurd and non-scientific statements (“I’d like to rebut this musically. People may easily tell Schöberg’s from Haydn’s. However, sometimes people may not be able to tell Haydn’s from Mozart’s because they share similarity (e.g. Sonata structure). Or, religiously speaking, people may hardly tell the difference between two denominations under Christianity. If we tweak the liturgy of Denomination A, it may become that of Denomination B. In this case, can we say A equals B? (If someone is ecumenical, (s)he may say so though).” / “With an analogy in music, every day so many musicians produce numerous ‘novel’ music pieces all over the world. But only a few go to a music chart based on audience’ preference rather than novelty.” / “Even if any limitation of HS is found in the future, I do not think it is a deadlock because I believe the maxim ‘where there is a will (of overcoming the limitation), there is a way (to solve).’ I imagine this overcoming process is similar to a breakthrough moment of local optimum.” / “My last wish is that the author becomes Paul rather than Saul of HS, or that he becomes the president of a new algorithm rather than the sniper of the existing algorithm (I do not want to mention another academic vandalism by the IP which locates the author’s region).” / “Also, I think the author’s research patron (Swiss National Science Foundation) would be much happier if the author wrote a more constructive paper rather than publication-oriented paper under the financial benefit and time duration.”).

If you want to take a short break from your research work, try to read his research commentary. It will make you sad, but it will also make you laugh at the same time.

My second article

I wonder if anybody managed to read the whole last section. To me it seems quite bizarre that the author of the research commentary is among our peers in the research community and it is hard for me to imagine to come up with different feelings after reading the research commentary.  In any case, the response in the form of the research commentary and the ever growing number of publications regarding harmony search (more than 9000 according to a google scholar search at the end of 2014 for “Harmony Search”, including the quotation marks) forced me to react. For this purpose I wanted to study some harmony search publications more in detail and to provide a formal proof of the result from my first article. This led to a second journal article (D. Weyland. A critical view on the harmony search algorithm – How to not solve sudoku. Operations Research Perspectives 2, pages 97-105).

Putting the proof in a more formal framework was not a big deal. But my study of a certain harmony search article (Z.W. Geem. Harmony search algorithm for solving sudoku. In Knowledge-Based Intelligent Information and Engineering Systems, pages 371–378) written by the inventor of harmony search, Zong Woo Geem, exposed some shocking flaws. The article by Geem is basically about using the harmony search algorithm for solving the sudoku puzzle. Sudoku is a kind of puzzle game you can find, for example, in newspapers. You have given a 9×9 square, partially filled with numbers in the range from 1 to 9. The goal is to fill in the missing numbers, such that in each row, in each column and in each of the nine 3×3 subsquares (into which the big square can be uniquely partitioned) the numbers from 1 to 9 occur each exactly once. There exist many problem specific algorithms which can solve even the hardest of these puzzles in quite a short amount of time. So the first question that arises is, why would we even try to solve this problem with a heuristic? This is simply a conceptual flaw. But for the moment we can easily ignore this fact, since things are getting worse pretty soon.

Let us have a look at the objective function Geem uses in his work. For a potential solution to the sudoku puzzle, he sums the absolute differences of 45 and the sums of values in each row, in each column and in each subsquare. Since the sum of the values from 1 to 9 is 45, it is clear that the unique solution to the sudoku puzzle has an objective value of 0 and is therefore an optimal solution with respect to the given objective function. Unfortunately, it is not obvious whether there are other optimal solutions with respect to the given objective function or not. In his article Geem states the following:

It should be noted that, although the sum of each row, each column, or each block equals 45, it does not guarantee that the numbers 1 through 9 are used exactly once. However, any violation of the uniqueness affects other row, column, or block which contains the wrong value jointly.

This statement itself is true, but does it really explain that there is only one optimal solution with respect to the given objective function? It turns out that this is not true in general. In fact, we can easily derive, starting from the unique solution of the sudoku puzzle, additional solutions with the optimal objective value of 0. Just take any 2×2 subsquare which does not contain numbers given in the description of the puzzle and which is completely embedded in one of the 3×3 subsquares. Increase the numbers in the top left and bottom right position of the 2×2 subsquare by 1 and decrease the numbers in the top right and bottom left position of the 2×2 subsquare by 1 (If this is not possible exchange the increase and decrease operators). In this way the sums of the values in the affected rows, columns and the affected 3×3 subsquare do not change. The resulting solution is still optimal with respect to the objective function proposed by Geem and very likely there is a huge number of such optimal solutions which are not the unique solution to the sudoku puzzle. This is a serious flaw. It seems that Geem was not aware of this issue. He often uses terms as “the optimal solution” or “the global optimum”, which both imply uniqueness of the solution with respect to the given objective function. It is therefore also not clear if the results reported in his article are with respect to finding the unique solution of the sudoku puzzle or with respect to finding any of the optimal solutions.

I have then tried to reproduce the results of the computational experiments that were performed by Geem. I quickly reimplemented the harmony search algorithm and run it on the sudoku instance used by Geem. I did not expect to match his results exactly, since there is some stochasticity involved in the harmony search algorithm, but at least I expected to match the order of magnitude of his results. It turned out that this was not possible at all. Geem reported that for most of the parameter settings of the harmony search algorithm between 100 and 1,000 iterations were necessary to find the optimal solution. I performed 20 independent runs for each parameter settings and never found any optimal solution within 10,000 iterations or the unique solution to the puzzle within 1,000,000 iterations. How can we explain this discrepancy of the results? Maybe some theoretical considerations can help us here.

The harmony search algorithm for the sudoku puzzle is quite simple and therefore it is possible to derive bounds for the probability that the unique solution of the sudoku puzzle is found within a certain number of iterations. For this purpose we calculate the probability that the unique solution is found during the initialization process and a bound for the probability that the unique solution is found within one iteration of the algorithm. The first probability turns out to be smaller than . The second probability depends heavily on the parameters of the harmony search algorithm. With a harmony memory consideration rate of 0.5 and a pitch adjustment rate of 0.1, for example, the probability to find the unique solution within 10,000 iterations is bounded from above by . Putting things together, we can even compute the probability that all the 12 runs from Geem’s article with a harmony memory consideration rate of 0.5 would find the unique solution to the harmony search problem within the maximum of 10,000 iterations. In the results of Geem the unique solution was always found within the 10,000 iterations and the exact number of iterations until the unique solution was found was rather low in all of these runs. This probability is bounded from above by . This is an astronomically small number. To get a feeling for how small this probability really is, I would like to refer to the number of atoms in the visible universe, which is commonly estimated to be around .

This theoretical result is really shocking. And at this point it is difficult to not suspect some sort of deliberate cheating by Geem.

Conclusions

What conclusions can we draw from this whole affair? There is definitely some problem in the field of heuristics. We are overrun by a vast amount of presumably novel heuristics based on increasingly absurd metaphors which in some cases have nothing in common with optimization anymore. This issue is thoroughly discussed in a 2013 article by Kenneth Sorensen (K. Sorensen. Metaheuristics – the metaphor exposed. International Transactions in Operational Research, 2013). In my two journal articles and in this blog post I have shown that the harmony search algorithm is nothing more than a fraud. And I suspect that the situation is similar for many of the other presumably novel metaphor-based heuristics.

But in my opinion the rather sad developments in the field of heuristics are completely understandable. We are operating in a fundamentally flawed research system with a lot of financial interests and many false incentives. From this point of view the work by Geem seems misguided, but somehow reasonable. It is therefore not sufficient to criticize him and others for fraudulent and unethical behavior and to leave aside the much bigger problems of our research system. Peer-reviewing in its current form is just not working. The pressure to publish in order to advance your career or in order to obtain grants is immense and leads to wrong incentives. Financial interests of third parties which are not directly involved in the research process (e.g. publishers) are further corrupting the research system. I guess I will write a blog post about this topic in the near future, but what I want to say at this point is the following: The behavior of Geem is not justifiable at all and definitely affects research in heuristics in a negative way. This is a serious issue, but at the same time we should also think about the bigger picture.

On the more constructive side, I would propose to treat heuristics from a purely mathematical and technical way. Metaphors and analogies might (or might not) help in the construction of heuristics, but the resulting methods should be treated from a mathematical and technical point of view. I have recently submitted an article in which I suggest to see heuristics as methods that iteratively sample and evaluate solutions according to some probability distribution which is regularly updated based on the results of the sampling process. A similar statement has been made in the context of the 11th Metaheuristics International Conference, MIC 2015, in a document with the title “A Research Agenda for Metaheuristic Standardization”. Based on a solid mathematical and theoretical fundament, it is then possible to develop and compare different heuristics in a meaningful way. And this is where I personally see the future of research in the field of heuristics. I am currently working on a metaphor-free heuristic which can make use of the latest technological achievements in the form of cloud computing and GPU computing. More about that soon in another blog post.