Category: Research

The Research System – Its problems and what we can do about it

This time I would like to talk about our current research system. With research system I mean the framework in which research is conducted at the beginning of the 21st century. In my opinion there are many different problems with the current system, some of which lead to false incentives and ultimately corrupt science. I will start with a discussion of what I think are the main issues with our research system. After that I will talk about some ways in which we researchers could actively influence and change this system into a better one. At the end I will present some ideas of how I personally want to cope with this flawed system in the future. I can already tell you at this point that I am not leaving academia. At least not now.

The problems of our research system

There exist many blog posts and articles about the problems of the research system. Most researchers are aware of these issues or even frequently experience them. The huge problem is that nobody is doing anything about it. With our passive behavior we are gambling the reputation of science. This needs to change.

We are conducting research within a framework that consists for the most part of non-democratic structures. There are huge differences with respect to the power and influence of different researchers within this framework, which cannot be simply explained by the quality of their work. There are third parties involved, mainly in the publication process, which impede our research work, mostly because of financial reasons. We decide whether a work is worth publishing or not using a system which cannot work for very simple game theoretical considerations. And finally, we measure the quality of research and the success of researchers using certain flawed indicators. This all together leads to many false incentives for all the parties involved in that process. This might not be a problem in other situations, but here we deal with persons which presumably belong to the smartest in our society. And therefore it is of greatest importance that we work within a system which gives the right incentives in order to perform good research.

Indicators

To a large extend we measure quality and success based on indicators. The quality of a publication is measured by the number of citations it gets. The quality of journals is measured by the impact factor, which is the average of the number of citations from publications within this journal. Our own success is measured by the number of publications we publish and the number of citations our publications receive. Researchgate uses indicators called impact points and rg scores and google scholar uses indicators called h-index and i10-index to measure our success.

The problem with all these indicators is that they do not accurately reflect the quality of our work. At the very best there is a slightly positive correlation. Let me give you an example. At google scholar I have 163 citations, an h-index of 8 and an i10-index of 7, at researchgate I have 6.85 impact points and an rg-score of 8.28. Another researcher has 8150 citations, an h-index of 34 and an i10-index of 57 at google scholar and 72.06 impact point and an rg-score of 28.95 at researchgate. Comparing these indicators, it seems that this researcher is performing much better research than me. What if I tell you that this researcher is Zong Woo Geem, whose career is based on his “invention” of the dubious harmony search algorithm and whose academic fraud was recently exposed by myself (see my previous blog post for more details: The Harmony Search Algorithm – My personal experience with this “novel” metaheuristic)?

If these indicators do not accurately reflect the quality of our work, why are we actually using them to measure the quality of our work? Instead of conducting high quality research, the system gives incentives to optimize indicators. And such a system obviously leads to a research output which improves the indicators and not necessarily to a research output of high quality. This is definitely not a feature we want to have in a research system.

Peer reviewing

We use peer reviewing to decide what is getting published in journals and what is getting accepted for conferences. There are several studies which show that peer reviewing does not really work as intended. For example, some studies show that results of peer reviewing are extremely stochastic. Therefore a small number of reviewers, which is commonly used for journal articles and conference submissions, cannot be used to adequately estimate the quality of a given work. Let me give you another argument for why peer reviewing does not work. For this purpose, lets look at it from a game theoretical point of view (I am not aware of any such treatment in literature, please let me know if you know any such sources). So lets assume that you are asked to review some manuscript. What are your incentives to do a good job? Apart from any ethical reasons or issues with your conscience, I cannot think of such incentives. But are there incentives for not making a good job? In my opinion there are a lot of such incentives. It makes sense not to invest too much time for the review, since in this way you could better devote your time to other parts of your research work, maybe something which might help you with your own career. It also makes sense to be biased with your assessment of the manuscript. It is very likely that the authors of the manuscript work in the same field as you do. If they are friends you might want to be very positive in your review, or if the manuscript contains serious flaws, you might want to prevent them from harm. If they are competitors you could do the exact opposite, you might want to be very negative with your review, or if the manuscript contains serious flaws, you might want to suggest publication in order to criticize the authors later. Game theoretically speaking, this leads to a kind of dilemma situation between behaving ethically correct and doing a good job on the one side and behaving egoistic and possibly doing a bad job on purpose on the other side.

Some of those issues are thoroughly covered and well-known. Still we heavily rely on peer reviewing to assess the quality of our work. Most researchers agree with me, that peer reviewing is flawed, but then they justify its usage based on the fact that there is no better method available. It hurts to hear such an argument from researchers, who are supposed to change things and to facilitate progress. At certain times there was no better system known than slavery or monarchy. People slowly understood that these systems were flawed. Instead of keeping them, because no alternatives were available, they were actually looking for alternatives (By the way, this should also trigger us to think critically about the political and economical system in which we are living). This is what we should do as well. Instead of relying on an approach, which we all know is seriously flawed, we should try to find alternatives. I will come back to this issue later in this blog post.

Publishers

The role of publishing companies in today’s research system is kind of awkward. They run a big business with huge margins for profit, but their benefits to research are not clear at all. I would even go one step further and say that they are actively impeding research work. Lets have a closer look at that.

It is, and always was, of great importance to make research results available to others. In the past this has been done in the form of letters, journals or books. Here publishers played a key role. For them the whole thing was a business with financial incentives. They were providing a certain service which was important for the process of communicating research results. They were not necessarily interested in promoting excellent research, but since they provided the research community with a service which had a certain value, this seems completely fair in my opinion.

This situation has changed dramatically due to the Internet and the personal computer. Using modern editing tools on personal computers, we are actually preparing high quality papers (here I mean high quality with respect to typesetting and related issues), which are basically ready for publishing. Additionally, the Internet allows us to easily make our research results instantaneously available to the wide public. But instead of that we are still using those old structures that have developed in the past, and we still publish our results with the help of publishing companies.

The crucial question here is, which kind of service are those companies actually providing to the research community? I personally do not see any kind of service they are actually providing, except their existing structures (which are probably not even a service in that sense). In my field we submit so-called manuscripts to conferences and journals. In the original meaning, “[a] manuscript is any document written by hand or typewritten, as opposed to being mechanically printed or reproduced in some automated way.” What an irony, nowadays our manuscripts are basically pdf documents which are ready for publishing. That means, the only thing these publishing companies are doing, is, apart from some minor things, to take our documents and to print them or just to put them online. For obvious reasons, we do not need printed versions anymore in the 21st century. That means they are taking our documents and putting them in the Internet. Is that really a service? And on top of that they make huge profits with that system.

And it is getting even worse. Using these kind of obsolete structures, they actively impede research. First of all, results could be made available much faster without using the “services” of publishing companies. But the real problem is, that the publishing companies are aware of the fact that they are actually providing little or no service. For this reason they try to make us dependent on these obsolete structures in order to continue with their antiquated business model. This happens on many different levels. For example, in the form of so-called “top” or “high impact” journals, by enforcing us to rely on indicators, or by “sponsoring” research. Another point is that their profits rely heavily on the number of publications they are able to sell back, for example to universities. This gives them a financial incentive to publish vast quantities of papers and they try to impose this incentive on us researchers.

The whole point is, we do not need these sort of publishing companies anymore. Using personal computers and the Internet, we should be able to easily communicate our research results without the help of any third party involved.

Power structures

The current research system relies on several non-democratic structures and on processes which are far from transparent. In this environment, it is extremely difficult, to obtain some idealistic purpose such as good research. At this point I would like to briefly discuss two of these issues, the typical career path in academia and the power of researchers that are journal editors or part of a conference committee.

The typical career in academia consists of something like finishing your studies, doing a PhD, working a few years as a PostDoc and then trying to somehow get a professor position or quit at some point in between. This is a very inflexible career path which comes at the cost of many inherent problems. Apart from that, it is commonly assumed that as a PhD student you are basically thriving on the ideas of your supervisor and that as a PostDoc you slowly start with independent research, still under the supervision of a professor. While in reality, some PhD students are already doing great independent research and their supervisors are simply exploiting them (in order to optimize their own indicators). I am doing independent research since years, I have been exploited, and still I have to prove that I am able to conduct independent research. This whole career path is strongly intertwined with the indicators I have discussed before. In order to advance in your career, you have to optimize your indicators. Nobody really cares about your potential as a researcher. There are definitely many brilliant researchers who manage to make a successful career in academia, but due to our increasing focus on indicators, there is also an increasing amount of researchers which make a successful career because they are better in optimizing their indicators or simply because they know how to play the game. And this creates a vicious circle.

The other point is that certain researchers are equipped with an immense power in the current research system. Journal editors and committee members of conferences have the power to shape the direction of research. They are those people who decide what gets published and what does not get published. The problem is not that there are people who have such a power, the problem is that they are selected in a highly non-democratic way and that they are able to execute their power in a non-transparent way. No wonder that we are supposed to do excessive networking at conferences instead of research.

How can we change this situation?

The current state of the research system is not acceptable. But it will not change if we just hope that those parties who profit from this system will alter their behavior and act in a more idealistic way. If we want to change something, we have to do it ourselves. The reason why I still want to continue in academia is, that I somehow hope it is possible to change things. If it turns out during the next years that it is not possible to change anything, then you will find me among those researchers which simply quit and leave academia (maybe with another of those infamous blog posts). Maybe I will find another way to pursue my passion of research, but I will definitely not become some indicator optimizer.

So, how can we change the situation? This is a complex and difficult task and I would like to invite everyone who managed to read that far, to discuss this with me (by email, by twitter @dennisweyland, or by commenting on this blog post). I have three suggestions that I would like to share here.

The first suggestion is to stop playing the game. Forget about your indicators, stop reviewing manuscripts for the big publishing companies without compensation, and stop submitting your manuscripts to journals run by the big publishing companies. If we just continue as before without leaving our comfort zone, it is very unlikely that anything will change. Question everything about the research system and draw your own conclusions. If we all try that, I am sure change will come.

My second suggestion is to develop in a collaborative effort an alternative publishing model based on the Internet. I have a pretty clear vision of what I would consider an ideal publishing model and I think I might write a separate blog post about this topic in the near future. But it is important that we shape the system in a way which suits all of us.

The last suggestion is simply to create a union for researchers. In this way we can organize ourselves and obtain some political power in order to change things as project funding or publishing policies on the political level. The structures that are imposed on us are not the structures we want and maybe we can change certain things in this way.

My personal research policies

In order to give you some examples of how we could change our own behavior regarding the current research system, I would like to discuss some changes of my own research policies.

As I said, for the moment I will try to continue in academia. Unfortunately, I am not in a position to drastically change policies on a higher level. But there are some small things which I can do (and which basically everyone could do). First of all, I will not participate anymore in the peer reviewing process under the current conditions. Well, peer reviewing gives me a certain power over my peers and in theory I could use it for the overall good. But this is exactly one of the many problems with peer reviewing. It is a non-transparent system which empowers the reviewers over their peers. You might say that my behavior is not fair, because other researchers will still review my manuscripts. I can assure you that this will not be the case, because I also plan to publish my research results in an alternative way. I will put them on the Internet, freely available for everyone and open to discourse. This does not mean that I believe that my work is free from defects and does not need any sort of reviewing. If there is something wrong with my papers or there are reasons to change parts of them, I will be more than happy to do it.

Conclusions

The current research system is fundamentally flawed. The different problems are extremely intertwined and facilitate an environment which is diametrically opposed to conducting good research. It will require our collaborative effort to change things. This is definitely not an easy task, but I still hope it is somehow possible. Please let me know (by email, by twitter @dennisweyland, or by commenting on this blog post) what you think about this whole issue.

The Harmony Search Algorithm – My personal experience with this “novel” metaheuristic

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 10^{-37}. 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 5.2 \cdot 10^{-8}. 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 4.83 \cdot 10^{-100}. 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 10^{80}.

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.