Marcus Ritt

Esta página é apenas de leitura. Pode ver a fonte, mas não alterá-la. Informe-se com o administrador deste Wiki se achar que isto não está correcto.
====== Técnicas de busca heurística (2014/1) ======

//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, sala 112, prédio 43425.\\
**Consultas:** Seg 10.30-12.00, sala 2012, prédio 43425.\\
**Súmula:** [[http://ppgc.inf.ufrgs.br/index.php?option=com_content&view=category&layout=blog&id=171&disc=92|Na página do PPGC]].

===== Resultados =====
  * [[2014-1-Notas|Notas]]
  * [[2014-1-Lista1|Comparação dos resultados da lista 1]]

<html><!--
  * [[2013-1-FF|Frequência]]
  * [[2013-1-Trabalhos|Trabalhos]]
--></html>

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

  * Cronograma nova, prova (a ser confirmando) dia 24/6, 13.00, sala 220 (Conselho). :!:


===== Materiais =====

  * Página da disciplina em [[2013-1|2013/1]]
  * {{notas-6443.pdf|Notas de aula}} (atualizado: 17/4/2016) :!:
  * Mais informação sobre o [[2014-1-trabalhos|trabalho]] disponível.

==== Aulas ====

^ No. ^ Data ^ Tópicos                                                                        ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^
|  1 | 24/02 | Administrativa, Definições, Almoços de graça, representação e transformação.                      |     5-11 |                                         |                   | R3.4.4,4.2 |
|    | 03/03 | //Dia não letivo//                                                                                |          |                                         |                   |            |
|    | 05/03 | //Dia não letivo//                                                                                |          |                                         |                   |            |
|  2 | 10/03 | Busca local: Vizinhanças.                                                                         |    13-16 |                                         |                   |            |
|  3 | 12/03 | Busca local monótona: Vizinhanças e exemplos.                                                     |    17-24 |                                         |                   |            |
|  4 | 17/03 | Busca local monótona: Segue os vencedores. Complexidade.                                          |    25-29 |                                         |                   |            |
|  5 | 19/03 | Busca local não-monótona: Simulated Annealing e aceitação por limite.                             |    30-34 |                                         |                   |            |
|  6 | 24/03 | Busca local não-monótona: Simulated Annealing e aceitação por limite, Busca Tabu.                 |    34-36 |                                         |                   |            |
|  7 | 26/03 | Busca local não-monótona: Busca Tabu, otimização extremal, busca local guidada                    |    34-38 |  {{e01a.pdf|E1}}((Atualizado 1/4/14.))  |  {{s01a.pdf|S1}}  |            |
|  8 | 31/03 | Busca local não-monótona: Métodos iterados,  vizinhanças múltiplas e grandes.                     |    38-43 |                                         |                   |            |
|  9 | 02/04 | Busca por construção: Matroides, algoritmos gulosos e de prioridade.                              |    45-50 |                                         |                   |            |
| 10 | 07/04 | Busca por construção: Construção independente: Múltiplos inicios, Bubble search, GRASP.           |    50-52 |                                         |                   |            |
| 11 | 09/04 | Busca por construção: Construçao dependente: guloso iterado, squeaky wheel, sistemas de formigas. |    52-54 |                                         |                   |            |
| 12 | 14/04 | Busca por recombinação: Operadores de recombinação genéricos, religamento de caminhos, exemplos.  |    55-59 |  Prazo E1: 14/04                        |                   |            |
| 13 | 16/04 | Busca por recombinação: Probe, scatter search, e GRASP com religamento de caminhos.               |    59-62 |                                         |                   |            |
|    | 21/04 | //Tiradentes//                                                                                    |          |                                         |                   |            |
| 14 | 23/04 | Busca por recombinação: Algoritmos genéticos e meméticos.                                         |    62-70 |  {{e02a20141.pdf|E2}}                   |  {{s02a20141.pdf|S2}}  |            |
| 15 | 28/04 | Busca por recombinação: Algoritmos evolucionários, enxames.                                       |    70-74 |                                         |                   |            |
| 16 | 30/04 | Metodologia de projeto.                                                                           |    91-95 |                                         |                   |            |
| 17 | 05/05 | Avaliação experimental: Analise de paisagens de otimização.                                       |    95-98 |  Prazo E2: 07/05                        |                   |            |
| 18 | 07/05 | Avaliação experimental: Complexidade empírica, distribuição de tempo e qualidade.                 |   99-103 |                                         |                   |            |
|    | 12/05 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]//                                                    |          |                                         |                   |            |
|    | 14/05 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]//                                                    |          |                                         |                   |            |
| 19 | 19/05 | Avaliação experimental: Teste de hipóteses.                                                       |  103-107 |                                         |                   |            |
| 20 | 21/05 | Avaliação experimental: Teste de hipóteses.                                                       |  108-111 |                                         |                   |            |
| 21 | 26/05 | Avaliação experimental: Projeto de experimentos e escolha de parâmetros.                          |  111-114 |                                         |                   |            |
| 22 | 28/05 | Tópicos: Hibridização e híper-heurísticas.                                                        |    75-79 |                                         |                   |            |
| 23 | 02/06 | Tópicos: Heurísticas paralelas.                                                                   |    79-83 |  {{e03a20141.pdf|E3}}                   |  {{s03a20141.pdf|S3}}  |            |
| 24 | 04/06 | Tópicos: Heurísticas multi-objetivos.                                                             |    83-89 |                                         |                   |            |
| 25 | 09/06 | Tópicos: Demais heurísticas.                                                                      |          |                                         |                   |            |
| 26 | 11/06 | Revisão para prova.                                                                                          |          |                                         |                   |            |
|    | 16/06 | //Sem aula//                                                                                         |          |                                         |                   |            |
|    | 18/06 | //Dia não-letivo//                                                                                |          |  Prazo E3: 20/06                        |                   |            |
| 27 | 24/06 | **Prova** as 13.00 (a ser confirmado, 43412(65) - sala 220 (Sala do conselho)                     |          |                                           {{p01a.pdf|P}}   |  {{sp01a.pdf|S}}  |  |
|    | 25/06 | //Dia não letivo//                                                                                |          |                                         |                   |            |
|    | 30/06 | //Dia não letivo//                                                                                |          |                                         |                   |            |
|28,29| 01/07 | Apresentação de trabalhos: 10.30 e 13.30 (Sala: 43412(65): 214)                                  |          |                                         |                   |            |
| 30 | 02/07 | Apresentação de trabalhos: 13.30                                                                  |          |                                         |                   |            |
|    | 07/07 | Prova de recuperação.                                                                             |          |                                         |                   |            |
|    |       |                                                                                                   |          |                                         |                   |            |
|    | 20/07 | Término oficial das aulas.                                                                        |          |                                         |                   |            |

R = Rothlauf.

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

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

==== Ferramentas ====

 * {{http://www-e.uni-magdeburg.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/bin/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="http://link.springer.com/book/10.1007/978-3-540-35854-1/page/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="http://link.springer.com/book/10.1007/978-3-642-22084-5/page/1"><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/2007"></a>Teofile&nbsp;F.
  Gonzalez, editor.
<a href="http://www.crcpress.com/product/isbn/9781584885504"><cite>Handbook of
  Approximation Algorithms and Metaheuristics</cite></a>.
Chapman and Hall, 2007.</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="http://www.sls-book.net"><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="http://link.springer.com/book/10.1007/978-3-540-72962-4/page/1"><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="http://link.springer.com/book/10.1007/978-1-4419-1665-5/page/1"><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="http://link.springer.com/book/10.1007/978-3-642-11343-7/page/1"><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/2008"></a>Christian Blum,
  Maria Jos&eacute;&nbsp;Blesa Aguilera, Andrea Roli, and
  Michael Sampels, editors.
<a href="http://link.springer.com/book/10.1007/978-3-540-78295-7/page/1"><cite>Hybrid Metaheuristics : An Emerging Approach to Optimization</cite></a>.
Springer, 2008.
INF: Recurso eletr&ocirc;nico.</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="http://link.springer.com/book/10.1007/978-3-540-79438-7/page/1"><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="http://link.springer.com/book/10.1007/978-1-4419-1306-7/page/1"><cite>Matheuristics</cite></a>.
Springer, 2009.
INF: Recurso eletr&ocirc;nico.</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>
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
