Metaheurísticas

Ementa: Muitos problemas de engenharia podem ser formulados como um problema de otimização. Para solução de tais problemas, diferentes métodos baseados programação matemática, pesquisa operacional, heurísticas computacionais, entre outros têm sido desenvolvidos. Meta-heurísticas são heurísticas de alto nível que através de um controle do processo de busca pretende atingir de forma sistemática e eficiente a solução ótima global de problemas de otimização, em especial de otimização combinatória. O objetivo desta disciplina é estudar alguns problema importantes de otimização e as meta-heurísticas capazes de resolvê-los. As meta-heurísticas estudadas são divididas em dois grupos: métodos de trajetórias e métodos populacionais. No primeiro grupo se encontram os algoritmos de busca tabu, simulated annealing, busca local (iterativa e guiada) entre outros. No segundo grupo incluem-se os métodos baseados em algoritmos evolucionários, meméticos, swarm e evolução diferencial. No final do curso, o estudante deve ser capaz de compreender as ideias de base por trás de cada meta-heurística estudada, saber como usar meta-heurísticas na solução de um problema prático, e ser capaz de desenvolver novas meta-heurísticas.

Syllabus: Many engineering problems can be formulated as an optimization problem. To solve such problems, different methods based on mathematical programming, operations research, computational heuristics, among others have been developed. Metaheuristics are high-level heuristics that, through search process control, aim to achieve systematically and efficiently the global optimal solution of optimization problems, especially combinatorial optimization. The objective of this course is to study some important optimization problems and the metaheuristics capable of solving them. The metaheuristics studied are divided into two groups: trajectory methods and population-based methods. In the first group are found tabu search, simulated annealing, local search (iterative and guided) algorithms, among others. In the second group are included methods based on evolutionary algorithms, memetic algorithms, swarm-based methods, and differential evolution. At the end of the course, the student should be able to understand the basic ideas behind each metaheuristic studied, know how to use metaheuristics in solving a practical problem, and be capable of developing new metaheuristics.

Bibliografia:

J. Dréo, A. Pétrowski, P. Siarry and E. Taillard. Metaheuristics for hard optimization: methods and case studies, Springer, 2003.

Z. Michalewicz and D. Fogel. How to solve it: Modern Heuristic, Springer, 2004.

E. G Talbi. Metaheuristicsfrom design to implementation, John Wiley & Sons, 2009.

C. Blum and A. Roli: Metaheuristics in Combinatorial Optimization: orverview and conceptual comparison. ACM computing Surveys, vol 35 (3), pp 268-308, 2003.

M. Gendrau and J-Y Potvin. Metaheuristics in Combinatorial Optimization. Annals of Operations Research, vol 140 (1), pp 189 213, 2005.

Outros artigos selecionados.