2
$\begingroup$

What are the advantages and disadvantages of using meta-heuristic algorithms on optimization problems? Simply, why do we use meta-heuristic algorithms, like PSO, over traditional mathematical techniques, such as linear, non-linear and dynamic programming?

I actually have a good understanding of meta-heuristic algorithms and I know how they work. For example, one advantage of this kind of algorithms is that they can find an optimal solution in a reasonable time.

However, my lack of knowledge about other methods and techniques brought this question to my mind.

$\endgroup$
0
1
$\begingroup$

Meta-heuristics are particularly suited for combinatorial optimization problems, given that, although they are not usually guaranteed to find the optimal global solution, they can often find a sufficiently good solution in a decent amount of time. So, they are an alternative to exhaustive search, which would take exponential time. For example, ant colony optimization algorithms have been used to approximately (or exactly, in the case of small or medium-size instances) solve the travelling salesman problem, whose decision version is an NP-complete problem (which means that, unless P=NP, there is no polynomial-time solution to solve it).

Meta-heuristics can also be easily applied to many problems, given that they are not problem-specific. For example, in the case of genetic algorithms, you just need to encode the possible solutions, but, in principle, you can apply genetic algorithms to a wide range of problems, although they may not always be the best solution to each of these problems. Moreover, as opposed to gradient-based optimisation algorithms, there's no need for the gradient of the objective function. For instance, in the case of genetic algorithms, you just need a way of evaluating the solutions (e.g. the fitness or the novelty).

Meta-heuristics often incorporate some form of randomness in order to escape from local minima. Ant-colony optimization algorithms or simulated annealing are two good examples of this approach.

If you are still interested in meta-heuristics, the book Clever Algorithms: Nature-Inspired Programming Recipes (by Jason Brownlee) is a very good resource for learning about them. There's also a Github repository with the implementation of the algorithms described in this book.

$\endgroup$
1
  • $\begingroup$ I was already preparing this answer before the last edit to the question, which indicates that the OP is already aware of an advantage of meta-heuristics that I mention in this answer. $\endgroup$
    – nbro
    Jan 27 '20 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.