No Free Lunch Theory

Meta-heuristics are problem independent and require significant tuning to fit for a problem. Using Meta-heuristic is a need specifically when you have to apply to a problem with lot of possible solutions. Hence, use them whem when you are sure that a Meta-heuristic Optimization is required.

Rohail Gulbaz Thank you for your answer. So, why do most articles that propose new metaheuristics (or improved metaheuristics) compare them on global optimization problems? whereas we are going to use them in very specific problems?

Performance of a meta-heuristic can only be examined in a problem where these are applicable. Meta-heuristics do not guarantee a global optimum but it is almost near or close to a global best solution.

Two different problems have their unique characteristics that make them more or less difficult. One solution method may work better than another one for one problem, and it might be the other way around for another solution method. This is just natural, unless the problems are similar, i.e. they are in the same class of problems according to some classification. Also, metaheuristics do not give you an optimal solution. Solution quality may also depend on the starting point. There are a lot of things that may cause the difference in performance.

The reasons for difference in performance are the following ones:

• Complexity of problem: As the search space increases, so does the difficulty to locate the area of the global optimum. The point is that some metaheuristics (such as Genetic Algorithms) exhibit worse behaviour than others (e.g. PSO or Harmony Search)
• Number of paremeters: the greater the number of parameters, the more difficult is the tuning of them. In the case of Genetic Algorithms, the parameters are crossover rate, mutation rate, selection method and crossover method and mutation method. Since the crossover rate and the mutation rate are vary from 0 to 1 and the existence of many methods for selection, crossover and mutation, it means that one needs to do a lot of parameters tuning in order to solve the problem. Cuckko search algorithm has only 1 parameter, therefore the tuning is easier
• Inability to sacrifice current "best" solution for future better ones: Sometimes solutions must be kept in the population (such as in Elitist Genetic algorithms) in order to retain the area of the global optimum (if it has been located). Other times, it is better to constantly create solutions new, which can be handy especially if the environment is dynamic or chaotic. One must keep in mind the nature of the problem and, therefore, modify the metaheuristic according to the nature of the problem.

A good solution is to use matheuristics (metaheuristics combined with mathematical programming techniques)

According to the No Free Lunch Theorem, no algorithm can solve every kind of optimization problem efficiently. Since metaheuristics don't need gradient info and they work based on some random solution, they have less probability of getting stuck in local solutions. But, problem-related modification/parameter tuning plays a significant role in the performance of optimization algorithms. I observed many times that most algorithms can perform better for numerical benchmark functions. But, the same algorithm couldn't perform well for real-life engineering problems. Metaheuristics are also sensitive for mixed-integer and constrained, specifically equality constrained problems.

Thanks, everyone for the answers. But I have some questions that I can't find answers to. The first one is, How we can prove that a given metaheuristic X is the best one for a given problem P without experimentation? knowing that we compared a set of metaheuristics with the metaheuristic X and it is always the best one b experimentation. The second question, Given a real-life NP-complete problem, How we can choose the well-suited metaheuristic?

Answer fo Question 1:

Unfortunately, there is no way to prove that a metaheuristic optimization method is the best for any given problem P without experimentation.

Answer fo Question 2: Given a real-life NP-complete problem, you need to know the advatages and disadvantages of an algorithm in order to assess its suitability to the given problem. E.g. in [1] there is a comparative analysis between Ant Colony (AC) and Particle Swarm Optimization (PSO). The main advantages of AC are its parallelization, its ability to give good solutions rapidly and its suitability for the Travelling Salesman Probem (TSP), which is an NP-Hard problem. If your given problem is (or can be transformed into) TSP, then AC is better than PSO. On the other hand, the calculation in PSO is very simple. Compared with the other developing calculations, it occupies the bigger optimization ability and it can be completed easily. And when you have multiple solutions for a problem, then the best solutions is the simplest one.

[1] Selvi, V., and R. Umarani. "Comparative analysis of ant colony and particle swarm optimization techniques." International Journal of Computer Applications 5.4 (2010): 1-6.

Constantinos Spanakis thank you for your answer. So, if I well understand, the best way to find which metaheuristic is good for a given problem P is to test some metaheuristics on it? If yes, how do we choose metaheuristics to test?

If you (X) and the world champion (Y) play table tennis, you are very likely to win Y a ball because of good luck or some unknown factors, but if you play more games, the result will be clear. Therefore, the statistical comparison may be more meaningful.

I would like to invite you to have a look on the following links.

SSO: https://www.mathworks.com/matlabcentral/fileexchange/92150-sperm-swarm-optimization-sso

HSSOGSA: https://www.mathworks.com/matlabcentral/fileexchange/92130-hssogsa?s_tid=srchtitle

MOSFP: https://github.com/sh7adeh1990/MOSFP

Thank you very much for your time and efforts.

Metaheuristics are stochastical algorithms and the responses can not be the same for each run.

A researcher must run the same algorithm for the same problem many times and note mean and std to find the answer for a problem. This is also the way for a researcher determines if a algorithm is better than another. Doing this, you will see that the metaheuristics are not so "caotics".

Every difficult problem class where we need metaheuristics, consists of many subclasses. Each subclass has its own structure. This structure is unknown in most of the cases. Actually, not only in most; however in absolutely most of the cases is the structure hidden. We are very for from to be able to analyse the structures of the subclasses of problems. Even we do not know how to define the subclasses. To give you an example, once I tried to solve a difficult integer programming problem. I used an old version of one of the best solvers. A leading figure in the developing team adviced me to use the newest version. I tried. Much longer CPU times were obtained with the new version. I had to return, to the old version. The moral of the story is, that they made the solver faster to subclasses which occur more frequently. However, they slowed down the solver on the subclass I had at the same time. Returning back to your question, the different metaheuristics behave differently on different subclasses. As we cannot define and analyse the subclasses, we use several metaheuristics.

Benghelima Slimane Charafeddine

This is a normal occurrence in all mathematical problems. There is no perfect solution that solves all problems, especially nonlinear problems. Always strive to improve and work harder. Thank you very much.

A lazy answer to the question would just be to cite the "No Free Lunch" theorem. However, if a more intuitive explanation is to be found, you need to take into consideration that metaheuristics fundamentally operate with two search schemes -- exploration and exploitation. Different algorithms have different strategies that transition one to the other. As such, given how various optimization problems differ in the nature of their search landscapes, a combination of local and global search, in varying extents, will yield different results.

The field, in my opinion, seems to have fallen into a loop hole of constant improvements to algorithms for different problems. What we desperately need now is an all-encompassing algorithm that is "intelligent" in the sense that it adapts to the type of computational domain in encounters, i.e., it tweaks the balance of exploration and exploitation automatically, to produce excellent results.

Usually, the success of metaheuristics mainly depends on the encoding of candidate solutions and thus the search space. I have been really happy using metaheuristics with only one individual most of the time. Check out our book on computational intelligence (details available in my list of publications) that will appear soon in Texts in Computer Science: www.springer.com/series/3191

Meta-heuristic algorithms perform differently in different types of problems. One may perform slightly better than the other in a particular problem and worse in another set of problems. People generally prefer to compare meta-heuristic algorithms applied to a particular problem. You should perform a statistical analysis to compare meta-heuristic algorithms. Because it is an inherent property of meta-heuristics that the solution at each run may not be identical. So it is incorrect (or maybe unfair) to compare met-heuristics when you have evaluated the solution only once (one single run of the algorithm).

Hi, Benghelima Slimane Charafeddine

it is very normal to experience this kind of tendency.

Generally, you may require a different heuristic optimization-based model for different problems.

You may have to consider the problem size when comparing X and Y problems as you abovementioned.

Second of all, you may have to consider the problem type. if they are both are not even the same problem type then the same treatment won't work. from the problem type, it can lead to a lot more factors e.g. problem encoding and decoding.

Finally, one that I can think of if you want to know why they perform differently, you can conduct a statistical-based parameter experiment. it might show something interesting.