Thiago Pradi

Computer Science, Health Informatics and Ruby.

Introduction to Metaheuristics

Hello Readers,

Today I’ll start my series of posts about genetic algorithms in Ruby.

Starting from the beginning, I’ll give an introduction about Artificial Intelligence and Metaheuristics.

But, to start, we need to know what is Artificial Intelligence. To help us, here is a little quote from John McCarthy about the subject:

Q. What is artificial intelligence?

A. It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

To summarize, the focus of Artificial Intelligence is to make computer smarter and sometimes, take solutions inspired by biological behavior that exists in nature. For me, it’s one of the most interesting branches in computer science.

Related to the Intelligence is the capacity of solving problems. Some computacional problems are easily solved in polynomial time (like sorting a list), but some of them couldn’t be solved in polynomial time (like the Travelling Salesman Problem, for example).

In a attempt to build a better strategy to solve those problems in polynomial time, there is the field of Metaheuristics. This field consist basically in building strategies and algorithms to gradually improve an initial solution in order to achieve the best possible solution in a polinomial time.

Again, to help us understand more about Metaheuristics, here is a quote from Sean Luke:

What is a Metaheuristic?

A common but unfortunate name for any stochastic optimization algorithm intended to be the last resort before giving up and using random or brute-force search. Such algorithms are used for problems where you don’t know how to find a good solution, but if shown a candidate solution, you can give it a grade.

There are many different Metaheuristics that have been developed to solve different types of problems. To illustrate and give a better understanding of them, I have detailed a few in the next section.

Genetic algorithms:

Genetic Algorithms are a search heuristics that tries to copy and apply the same process that the nature uses for evolution into solving computer problems. This heuristic was developed by John Holland and his collegues in 1975, and is being used in a huge class of different problems.

Hill-climbing:

Hill-climbing is a type of local search, that aims to improve the current solution by looking at the neighbors to the current state, and takes the neighbor state with the best objective function value as the new current state. They are also called Greedy Algorithms, because they pick the best neighbor for the current state, without considering future steps.

Simulated annealing:

The simulated annealing algorithm is an metaheuristic for global optimization, inspired by the process of annealing in metal work. In the same way that metal cools its structure and become fixed in the nature, we set an initial temperature that decrease by every interaction, allowing the algorithm to accept worse solutions in the beginning (to explore a bigger space), and make it only accept better solution as the temperature goes down. The design of this algorithm make it perfect to solve the travelling salesman problem.

Ant colony optimization:

Initially proposed by Marco Dorigo in 1992 in his PhD thesis, Ant colony optimization is a metaheuristic based on the based on the behavior of ants seeking a path between their colony and a source of food. To resume this techinique, it solves problems that can be reduced to finding good paths through graphs.

Wrapping up

In this post, I tried to introduce the concepts of Artificial intelligence, metaheuristics, and described a few metaheuristics. All of those explanations about specific heuristics are shorter, because every they will be described more detailed in the next posts of this series. In my next post, I’ll start going deep into every Metaheuristic, giving a implementation in Ruby. The first one will be the Hill-Climbing.

Comments