====== Técnicas de busca heurística (2025/2) ======

//There ain't no such thing as a free lunch.//

:!: Bem-vindo.

===== Informações gerais =====

**Carga horária:** 60 h (em 30 aulas de 2h)\\
**Créditos:** 4\\
**Súmula:** Introduction to heuristic and meta-heuristic search methods: design, calibration, evaluation, and comparison. Case studies of applications of heuristic search methods.\\
**Turma:** U.\\
**Horário/Sala:** Seg/Qua 13.30, 106/43413.\\
**Consultas:** A ser combinado.\\
**Súmula:** [[https://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp268|Na página do PPGC]] e no [[http://www.inf.ufrgs.br/~mrpritt/msc/pea-2021-2.pdf|plano de ensino adaptado]].

===== Resultados =====

  * [[2025-2-Notas|Listas]]
  * [[2025-2-Trabalhos|Trabalhos]]

===== Notícias =====

  * Primeiro dia de aula: 11 de agosto.

===== Materiais =====

  * Página da disciplina em [[2023-1|2023/1]], [[2021-2|2021/2]], [[2020-1|2020/1]], [[2019-1|2019/1]], [[2017-2|2017/2]], [[2016-1|2016/1]], [[2014-1|2014/1]] e [[2013-1|2013/1]]
  * {{notas-11799.pdf|Notas de aula}} (atualizado: 14/01/2022)

==== Aulas ====

^ No. ^ Data ^ Tópicos                                                                                  ^ Notas cáp. ^ Exercícios ^ Soluções ^ Leitura ^ Prazos ^
|   1 | 11/08 | Administrativa, Definições, Almoços de graça                                            |   1.1-1.2 |   |   | R3.4.4,4.2     |
|   2 | 13/08 | Representação e transformação.                                                          |   1.3-1.5 |   |   | R4.2           |
| || ** Busca local **                                                                                                     |||||
|   3 | 18/08 | Busca local: Vizinhanças e exemplos.                                                    |       2.1 |   |   | R4.3.2,ZBB6.1  |
| || ** Busca local monótona **                                                                                            |||||
|   4 | 20/08 | Busca local: Vizinhanças e exemplos.                                                    |       2.1 |   |   | R4.3.2,ZBB6.1  |
|   5 | 25/08 | Busca local monótona: Exemplos e resultados teóricos.                                   |       2.2 |   |   | M5.2           |
|   6 | 27/08 | Busca local monótona: Resultados teóricos.                                              |       2.2 |   |   | M5.2           |
|   7 | 01/09 | Busca local monótona: Resultados teóricos.                                              |       2.2 |   |   | M5.2           |
| || ** Busca local não-monótona **                                                                                        |||||
|   8 | 03/09 | Variantes de aceitação por limite, algoritmo Metropolis e Simulated Annealing           |       2.3 |   |   | M5.3           |
|   9 | 08/09 | Busca Tabu, otimização extremal, busca local guidada.                                   |       2.3 |  {{e0120252.pdf|L1}}  |   | R5.1           |
|  10 | 10/09 | Métodos iterados, vizinhanças múltiplas e grandes.                                      |       2.4 |   |   | R5.1           |
| || ** Busca por construção **                                                                                            |||||
|  11 | 15/09 | Laboratório Busca Local (102, 43425).                                                   |           |   |   |                |
|     | 17/09 | //Sem aula//                                                                            |           |   |   |                |
|  12 | 22/09 | Matroides, algoritmos gulosos e de prioridade.                                          |       3.1 |   |   | PS12           |
|  13 | 24/09 | Construção independente: Múltiplos inicios, Bubble search, GRASP.                       |       3.2 |   |   | ZBB5.1         |
|  14 | 29/09 | Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas.             |       3.3 |    {{e0220252.pdf|L2}}  |   | ZBB5.2         |
| || ** Busca por recombinação **                                                                                         |||||
|  15 | 01/10 | Operadores de recombinação, Religamento de caminhos (RL), Probe.                        |    4, 4.4 |   |   | R4.3.3, ZBB7.2 |
|  16 | 06/10 | Laboratório Algoritmos Construtivos (104, 43425).                                       |           |   |   |                |
|  17 | 08/10 | Scatter search, GRASP/RL, alg. genéticos, meméticos, evolucionários, enxames.           |   4.5-4.7 |   |   | ZBB7.1,R5.2.1  |
|  18 | 13/10 | Algoritmos de estimação de distribuição.                                                |       4.8 |   |   | R5.2.2         |
|  19 | 15/10 | CMA-ES.                                                                                 |           |                                             |
|     | 20/10 | //Semana Acadêmica//                                                                    |           |                                             |
|     | 22/10 | //Semana Acadêmica//                                                                    |           |                                             |
|     | 27/10 | //Dia do Servidor Público//                                                             |           |                                             |
| || ** Metodologia de projeto e avaliação experimental **                                                                |||||
|  20 | 29/10 | Metodologia de projeto.                                                                 |       6.1 |   |   |                |
|  21 | 03/11 | Analise de paisagens de otimização.                                                     |       6.2 |   |   | HS5            | 
|  22 | 05/11 | Complexidade empírica, distribuição de tempo e qualidade.                               |       6.3 |   |   | HS4        |     
|  23 | 10/11 | Estratégias de reinício, Teste de hipóteses.                                            |       6.3 |   |   |            |     
|  24 | 12/11 | Teste de hipóteses. Projeto de experimentos e escolha de parâmetros (sala 107/43425).   |       6.3 |   |   |            |
|  25 | 17/11 | Configuração automática de algoritmos (sala TBD).                                       |       6.3 |   |   |            | 
| || ** Tópicos **                                                                                      |||||
|  26 | 19/11 | Híper-heurísticas. Hibridização de heurísticas. Heurísticas para problemas contínuos.   |  5.[156]  |     |   |            |   
|  27 | 24/11 | Aula de revisão                                                                         |           |   |   |            |
|  28 | 26/11 | ** Prova **                                                                             |           |   |   |            |
|  29 | 01/12 | Heurísticas multi-objetivos e paralelas, e para problemas estocásticos.                 |       5.2-5.4 |   |   |            |
|  30 | 03/12 | Apresentação de trabalhos.                                                              |           |   |   |            |
|     | 10/12 | Provas de recuperação.                                                                  |           |   |   |            |
|     | 20/12 | Término oficial das aulas.                                                              |           |   |   |            |

R = Rothlauf, M = Michiels, ZBB = Zäpfl. et al., HS= Hoos & Stützle

==== Avaliação ====

A nota final é composta pela nota obtida na solução dos exercícios (1/3), a nota do projeto (1/3) e a nota da prova (1/3).

==== Ferramentas ====

  * {{http://www.math.uwaterloo.ca/tsp/iphone/index.html|Concorde TSP Solver for iOS}}
  * {{https://www-e.ovgu.de/mertens/TSP/TSP.html|TSP Algorithms in Action}}

==== Bibliografia ====
<html>
<!-- BEGIN BIBLIOGRAPHY livros -->
<!--
    DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND!  IT IS MAINTAINED AUTOMATICALLY!
    YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED!
-->
<!-- Generated by: /home/ritt/arch/share/bib2xhtml-v3.0-56-gd8f4/bib2xhtml -s unsortlist livros.bib livros.html -->
<ul class="bib2xhtml">

<!-- Authors: El Ghazali Talbi -->
<li><a name="Talbi/2009"></a>El-Ghazali Talbi.
<a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470278587.html"><cite>Metaheuristics.
  From Design to Implementation</cite></a>.
Wiley, 2009.</li>

<!-- Authors: Zbigniew Michalewicz and David B Fogel -->
<li><a name="Michalewicz.Fogel/2004"></a>Zbigniew
  Michalewicz and David&nbsp;B. Fogel.
<a href="http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-22494-5"><cite>How
  to Solve It: Modern Heuristics</cite></a>.
Springer, 2nd edition, 2004.
INF 65.012.122 M622h.</li>

<!-- Authors: Sean Luke -->
<li><a name="Luke/2011"></a>Sean Luke.
<a href="http://cs.gmu.edu/~sean/book/metaheuristics"><cite>Essentials of
  Metaheuristics</cite></a>.
lulu.com, 2011.</li>

<!-- Authors: Emile Aarts and Jan Karel Lenstra -->
<li><a name="Aarts.Lenstra/2003"></a>Emile Aarts and
  Jan&nbsp;Karel Lenstra, editors.
<a href="http://press.princeton.edu/titles/7564.html"><cite>Local Search in
  Combinatorial Optimization</cite></a>.
Princeton University Press, 2003.</li>

<!-- Authors: Wil Michiels and Emile Aarts and Jan Korst -->
<li><a name="Michiels/2007"></a>Wil Michiels,
  Emile Aarts, and Jan Korst.
<a href="https://link.springer.com/book/10.1007/978-3-540-35854-1"><cite>Theoretical
  Aspects of Local Search</cite></a>.
Springer, 2007.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: David E Goldberg -->
<li><a name="Goldberg/1989"></a>David&nbsp;E. Goldberg.
<cite>Genetic Algorithms in Search, Optimization, and Machine Learning</cite>.
Addison-Wesley, 1989.
INF 681.3.011 G618g.</li>

<!-- Authors: Gabriel Luque and Enrique Alba -->
<li><a name="Luque.Alba/2011"></a>Gabriel Luque and
  Enrique Alba.
<a href="https://link.springer.com/book/10.1007/978-3-642-22084-5"><cite>Parallel
  Genetic Algorithms: Theory and Real World Applications</cite></a>.
Springer, 2011.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: Xin She Yang -->
<li><a name="Yang/2010"></a>Xin-She Yang.
<cite>Nature-Inspired Metaheuristic Algorithms</cite>.
Luniver Press, 2nd edition, 2010.</li>

<!-- Authors: Agoston E Eiben and J E Smith -->
<li><a name="Eiben.Smith/2008"></a>Agoston&nbsp;E. Eiben
  and J.&nbsp;E. Smith.
<cite>Introduction to Evolutionary Computing</cite>.
Springer, 2008.
INF 681.3.011 E34i.</li>

<!-- Authors: Teofile F Gonzalez -->
<li><a name="Gonzalez/2018"></a>Teofile&nbsp;F.
  Gonzalez, editor.
<a href="https://www.routledge.com/Handbook-of-Approximation-Algorithms-and-Metaheuristics-Second-Edition/Gonzalez/p/book/9780367570286"><cite>Handbook
  of Approximation Algorithms and Metaheuristics</cite></a>.
Chapman and Hall, 2nd edition, 2018.</li>

<!-- Authors: Holger H Hoos and Thomas Stutzle -->
<li><a name="Hoos.Stuetzle/2004"></a>Holger&nbsp;H. Hoos
  and Thomas St&uuml;tzle.
<a href="https://www.cs.ubc.ca/~hoos/SLS-Book"><cite>Stochastic Local Search :
  Foundations &amp; Applications</cite></a>.
Morgan Kaufmann, 2004.</li>

<!-- Authors: Franz Rothlauf -->
<li><a name="Rothlauf/2011"></a>Franz Rothlauf.
<a href="https://link.springer.com/book/10.1007/978-3-540-72962-4"><cite>Design
  of Modern Heuristics: Principles and Application</cite></a>.
Springer, 2011.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: Ibrahim H Osman and James P Kelly -->
<li><a name="Osman.Kelly/1996"></a>Ibrahim&nbsp;H. Osman
  and James&nbsp;P. Kelly.
<cite>Meta-heuristics: Theory and Applications</cite>.
Kluwer, 1996.
INF 65.012.122 M587.</li>

<!-- Authors: Stefan Edelkamp and Stefan Schroeder -->
<li><a name="Edelkamp.Schroeder/2011"></a>Stefan
  Edelkamp and Stefan Schroeder.
<a href="http://www.sciencedirect.com/science/book/9780123725127"><cite>Heuristic
  Search: Theory and Applications</cite></a>.
Morgan Kaufmann, 2011.</li>

<!-- Authors: Michel Gendreau and Jean Yves Potvin -->
<li><a name="Genreau.Potvin/2010"></a>Michel
  Gendreau and Jean-Yves Potvin.
<a href="https://link.springer.com/book/10.1007/978-1-4419-1665-5"><cite>Handbook
  of Metaheuristics</cite></a>.
Springer, 2nd edition, 2011.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: Gunter Zapfel and Roland Braune and Michael Bogl -->
<li><a name="Zaepfel.etal/2010"></a>G&uuml;nter
  Z&auml;pfel, Roland Braune, and Michael B&ouml;gl.
<a href="https://link.springer.com/book/10.1007/978-3-642-11343-7"><cite>Metaheuristic
  search concepts</cite></a>.
Springer, 2010.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: Warren B Powell -->
<li><a name="Powell/2011"></a>Warren&nbsp;B. Powell.
<cite>Approximate Dynamic Programming: Solving the Curses of
  Dimensionality</cite>.
Wiley, 2nd edition, 2011.</li>

<!-- Authors: M Birattari -->
<li><a name="Birattari/2005"></a>M.&nbsp;Birattari.
<cite>The Problem of Tuning Metaheuristics</cite>.
IOS Press, 2005.</li>

<!-- Authors: Christian Blum and Maria Jose Blesa Aguilera and Andrea Roli and
  Michael Sampels -->
<li><a name="Blum.etal/2008a"></a>Christian Blum,
  Maria Jos&eacute;&nbsp;Blesa Aguilera, Andrea Roli, and
  Michael Sampels, editors.
<cite>Hybrid Metaheuristics : An Emerging Approach to Optimization</cite>.
Springer, 2008.
INF: Recurso eletr&ocirc;nico.
(<a href="http://dx.doi.org/10.1007/978-3-540-78295-7">doi:10.1007/978-3-540-78295-7</a>)</li>

<!-- Authors: Carlos Cotta and Marc Sevaux and Kenneth Sorensen -->
<li><a name="Cotta.etal/2008"></a>Carlos Cotta,
  Marc Sevaux, and Kenneth S&ouml;rensen, editors.
<a href="https://link.springer.com/book/10.1007/978-3-540-79438-7"><cite>Adaptive
  and Multilevel Metaheuristics</cite></a>.
Springer, 2008.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: Fred Glover and Gary A Kochenberger -->
<li><a name="Glover.Kochenberger/2002"></a>Fred
  Glover and Gary&nbsp;A. Kochenberger, editors.
<cite>Handbook of metaheuristics</cite>.
Kluwer, 2002.
INF 65.012.122 H237.</li>

<!-- Authors: Vittorio Maniezzo and Thomas Stutzle and Stefan Voss -->
<li><a name="Maniezzo.etal/2009"></a>Vittorio
  Maniezzo, Thomas St&uuml;tzle, and Stefan
  Vo&szlig;, editors.
<a href="https://link.springer.com/book/10.1007/978-1-4419-1306-7"><cite>Matheuristics</cite></a>.
Springer, 2009.
INF: Recurso eletr&ocirc;nico.</li>

<!-- Authors: J Dreo and A Petrowski and P Siarry and E Taillard -->
<li><a name="Dreo.etal/2006"></a>J.&nbsp;Dr&eacute;o,
  A.&nbsp;P&eacute;trowski, P.&nbsp;Siarry, and
  E.&nbsp;Taillard.
<cite>Metaheuristics for hard optimization</cite>.
Springer, 2006.</li>

</ul>

<!-- END BIBLIOGRAPHY livros -->
</body></html>

<html>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>