Esta página mostra as diferenças entre as duas revisões da página.
Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
cmp268:homepage [2017/09/13 13:16] marcus [Aulas] |
cmp268:homepage [2025/10/08 15:43] (Actual) |
||
---|---|---|---|
Linha 1: | Linha 1: | ||
- | ====== Técnicas de busca heurística (2017/2) ====== | + | ====== Técnicas de busca heurística (2025/2) ====== |
//There ain't no such thing as a free lunch.// | //There ain't no such thing as a free lunch.// | ||
Linha 11: | Linha 11: | ||
**Súmula:** Introduction to heuristic and meta-heuristic search methods: design, calibration, evaluation, and comparison. Case studies of applications of heuristic search methods.\\ | **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.\\ | **Turma:** U.\\ | ||
- | **Horário/Sala:** Seg/Qua 13.30, sala 116, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\ | + | **Horário/Sala:** Seg/Qua 13.30, 106/43413.\\ |
- | **Consultas:** Seg 10.30-12.00, sala 201, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\ | + | **Consultas:** A ser combinado.\\ |
- | **Súmula:** [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp268/|Na página do PPGC]]. | + | **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 ===== | ===== Resultados ===== | ||
- | * [[2017-2-Notas|Notas]] | ||
- | * [[2017-2-Trabalhos|Trabalhos]] | ||
- | <html><!-- | + | * [[2025-2-Notas|Listas]] |
- | * [[2017-2-FF|Frequência]] | + | * [[2025-2-Trabalhos|Trabalhos]] |
- | --></html> | + | |
===== Notícias ===== | ===== Notícias ===== | ||
- | * Primeiro dia de aula: 28 de agosto. | + | * Primeiro dia de aula: 11 de agosto. |
===== Materiais ===== | ===== Materiais ===== | ||
- | * Página da disciplina em [[2016-1|2016/1]], [[2014-1|2014/1]] e [[2013-1|2013/1]] | + | * 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-8176.pdf|Notas de aula}} (atualizado: 13/09/2017) | + | * {{notas-11799.pdf|Notas de aula}} (atualizado: 14/01/2022) |
==== Aulas ==== | ==== Aulas ==== | ||
- | ^ No. ^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^ | + | ^ No. ^ Data ^ Tópicos ^ Notas cáp. ^ Exercícios ^ Soluções ^ Leitura ^ Prazos ^ |
- | | 1 | 28/08 | Administrativa, Definições, Almoços de graça, representação e transformação. | 5-12 | | | R3.4.4,4.2 | | + | | 1 | 11/08 | Administrativa, Definições, Almoços de graça | 1.1-1.2 | | | R3.4.4,4.2 | |
- | | 2 | 30/08 | Busca local: Vizinhanças. | 13-16 | | | | | + | | 2 | 13/08 | Representação e transformação. | 1.3-1.5 | | | R4.2 | |
- | | 3 | 04/09 | Busca local monótona: Vizinhanças e exemplos. | 16-19 | | | | | + | | || ** Busca local ** ||||| |
- | | 4 | 06/09 | Busca local monótona: Segue os vencedores. Complexidade. | 10-23 | | | M5.2 | | + | | 3 | 18/08 | Busca local: Vizinhanças e exemplos. | 2.1 | | | R4.3.2,ZBB6.1 | |
- | | 5 | 11/09 | Busca local não-monótona: Simulated Annealing e aceitação por limite. | 23-29 | | | M5.3 | | + | | || ** Busca local monótona ** ||||| |
- | | 6 | 13/09 | Busca local não-monótona: Simulated Annealing e aceitação por limite, Busca Tabu. | 30-34 | {{e01c20172.pdf|E1}} | | R5.1 | | + | | 4 | 20/08 | Busca local: Vizinhanças e exemplos. | 2.1 | | | R4.3.2,ZBB6.1 | |
- | | 7 | 18/09 | Busca local não-monótona: Busca Tabu, otimização extremal, busca local guidada | 34-39 | | | R5.1 | | + | | 5 | 25/08 | Busca local monótona: Exemplos e resultados teóricos. | 2.2 | | | M5.2 | |
- | | | 20/09 | [[wppt>Revolução Farroupilha]] | | | | | | + | | 6 | 27/08 | Busca local monótona: Resultados teóricos. | 2.2 | | | M5.2 | |
- | | 8 | 25/09 | Busca local não-monótona: Métodos iterados, vizinhanças múltiplas e grandes. | 39-44 | | | R5.1 | | + | | 7 | 01/09 | Busca local monótona: Resultados teóricos. | 2.2 | | | M5.2 | |
- | | 9 | 27/09 | Busca por construção: Matroides, algoritmos gulosos e de prioridade. | 45-50 | | | | | + | | || ** Busca local não-monótona ** ||||| |
- | | 10 | 02/10 | Busca por construção: Construção independente: Múltiplos inicios, Bubble search, GRASP. | 50-59 | | | | | + | | 8 | 03/09 | Variantes de aceitação por limite, algoritmo Metropolis e Simulated Annealing | 2.3 | | | M5.3 | |
- | | 11 | 04/10 | Busca por construção: Construçao dependente: guloso iterado, squeaky wheel, sistemas de formigas. | 52-59 | | | | | + | | 9 | 08/09 | Busca Tabu, otimização extremal, busca local guidada. | 2.3 | {{e0120252.pdf|L1}} | | R5.1 | |
- | | 12 | 09/10 | Busca por recombinação: Operadores de recombinação genéricos, religamento de caminhos, exemplos. | 59-62 | | | | | + | | 10 | 10/09 | Métodos iterados, vizinhanças múltiplas e grandes. | 2.4 | | | R5.1 | |
- | | 13 | 11/10 | Busca por recombinação: Probe, scatter search, e GRASP com religamento de caminhos. | 59-62 | | | | | + | | || ** Busca por construção ** ||||| |
- | | | 16/10 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]// | | | | | | + | | 11 | 15/09 | Laboratório Busca Local (102, 43425). | | | | | |
- | | | 18/10 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]// | | | | | | + | | | 17/09 | //Sem aula// | | | | | |
- | | 14 | 23/10 | Busca por recombinação: Algoritmos genéticos e meméticos. | 62-70 | | | | | + | | 12 | 22/09 | Matroides, algoritmos gulosos e de prioridade. | 3.1 | | | PS12 | |
- | | 15 | 25/10 | Busca por recombinação: Algoritmos evolucionários, enxames. | 70-74 | | | | | + | | 13 | 24/09 | Construção independente: Múltiplos inicios, Bubble search, GRASP. | 3.2 | | | ZBB5.1 | |
- | | 16 | 30/10 | Metodologia de projeto. | 91-95 | | | | | + | | 14 | 29/09 | Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas. | 3.3 | {{e0220252.pdf|L2}} | | ZBB5.2 | |
- | | 17 | 01/11 | Avaliação experimental: Analise de paisagens de otimização. | 95-98 | | | | | + | | || ** Busca por recombinação ** ||||| |
- | | 18 | 06/11 | Avaliação experimental: Complexidade empírica, distribuição de tempo e qualidade. | 99-103 | | | | | + | | 15 | 01/10 | Operadores de recombinação, Religamento de caminhos (RL), Probe. | 4, 4.4 | | | R4.3.3, ZBB7.2 | |
- | | 19 | 08/11 | Avaliação experimental: Teste de hipóteses. | 103-107 | | | | | + | | 16 | 06/10 | Laboratório Algoritmos Construtivos (104, 43425). | | | | | |
- | | 20 | 13/11 | Avaliação experimental: Teste de hipóteses. | 108-111 | | | | | + | | 17 | 08/10 | Scatter search, GRASP/RL, alg. genéticos, meméticos, evolucionários, enxames. | 4.5-4.7 | | | ZBB7.1,R5.2.1 | |
- | | | 15/11 | [[wppt>Proclamação da república]] | | | | | | + | | 18 | 13/10 | Algoritmos de estimação de distribuição. | 4.8 | | | R5.2.2 | |
- | | 21 | 20/11 | Avaliação experimental: Projeto de experimentos e escolha de parâmetros. | 111-114 | | | | | + | | 19 | 15/10 | CMA-ES. | | | |
- | | 22 | 22/11 | Tópicos: Hibridização e híper-heurísticas. | 75-79 | | | | | + | | | 20/10 | //Semana Acadêmica// | | | |
- | | 23 | 27/11 | Tópicos: Heurísticas paralelas. | 79-83 | | | | | + | | | 22/10 | //Semana Acadêmica// | | | |
- | | 24 | 29/11 | Tópicos: Heurísticas multi-objetivos. | 83-89 | | | | | + | | | 27/10 | //Dia do Servidor Público// | | | |
- | | 25 | 04/12 | Tópicos: Demais heurísticas. | | | | | | + | | || ** Metodologia de projeto e avaliação experimental ** ||||| |
- | | 26 | 06/12 | Revisão. | | | | | | + | | 20 | 29/10 | Metodologia de projeto. | 6.1 | | | | |
- | | 27 | 11/12 | **Prova** | | | | | | + | | 21 | 03/11 | Analise de paisagens de otimização. | 6.2 | | | HS5 | |
- | | 28 | 13/12 | Apresentação de trabalhos. | | | | | | + | | 22 | 05/11 | Complexidade empírica, distribuição de tempo e qualidade. | 6.3 | | | HS4 | |
- | | 29 | 18/12 | Apresentação de trabalhos. | | | | | | + | | 23 | 10/11 | Estratégias de reinício, Teste de hipóteses. | 6.3 | | | | |
- | | 30 | 20/12 | Apresentação de trabalhos. | | | | | | + | | 24 | 12/11 | Teste de hipóteses. Projeto de experimentos e escolha de parâmetros (sala 107/43425). | 6.3 | | | | |
- | | | 03/01 | Prova de recuperação. | | | | | | + | | 25 | 17/11 | Configuração automática de algoritmos (sala TBD). | 6.3 | | | | |
- | | | 27/01 | Término oficial das aulas. | | | | | | + | | || ** 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. | + | R = Rothlauf, M = Michiels, ZBB = Zäpfl. et al., HS= Hoos & Stützle |
==== Avaliação ==== | ==== 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). | + | 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 ==== | ==== Ferramentas ==== | ||
- | * {{http://www-e.uni-magdeburg.de/mertens/TSP/TSP.html|TSP Algorithms in Action}} | + | * {{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 ==== | ==== Bibliografia ==== | ||
Linha 90: | Linha 94: | ||
YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED! | 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 --> | + | <!-- Generated by: /home/ritt/arch/share/bib2xhtml-v3.0-56-gd8f4/bib2xhtml -s unsortlist livros.bib livros.html --> |
<ul class="bib2xhtml"> | <ul class="bib2xhtml"> | ||
<!-- Authors: El Ghazali Talbi --> | <!-- Authors: El Ghazali Talbi --> | ||
<li><a name="Talbi/2009"></a>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>. | + | <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470278587.html"><cite>Metaheuristics. |
+ | From Design to Implementation</cite></a>. | ||
Wiley, 2009.</li> | Wiley, 2009.</li> | ||
Linha 101: | Linha 106: | ||
<li><a name="Michalewicz.Fogel/2004"></a>Zbigniew | <li><a name="Michalewicz.Fogel/2004"></a>Zbigniew | ||
Michalewicz and David B. Fogel. | Michalewicz and David 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>. | + | <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. | Springer, 2nd edition, 2004. | ||
INF 65.012.122 M622h.</li> | INF 65.012.122 M622h.</li> | ||
Linha 121: | Linha 127: | ||
<li><a name="Michiels/2007"></a>Wil Michiels, | <li><a name="Michiels/2007"></a>Wil Michiels, | ||
Emile Aarts, and Jan Korst. | 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>. | + | <a href="https://link.springer.com/book/10.1007/978-3-540-35854-1"><cite>Theoretical |
+ | Aspects of Local Search</cite></a>. | ||
Springer, 2007. | Springer, 2007. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 134: | Linha 141: | ||
<li><a name="Luque.Alba/2011"></a>Gabriel Luque and | <li><a name="Luque.Alba/2011"></a>Gabriel Luque and | ||
Enrique Alba. | 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>. | + | <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. | Springer, 2011. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 151: | Linha 159: | ||
<!-- Authors: Teofile F Gonzalez --> | <!-- Authors: Teofile F Gonzalez --> | ||
- | <li><a name="Gonzalez/2007"></a>Teofile F. | + | <li><a name="Gonzalez/2018"></a>Teofile F. |
Gonzalez, editor. | Gonzalez, editor. | ||
- | <a href="http://www.crcpress.com/product/isbn/9781584885504"><cite>Handbook of | + | <a href="https://www.routledge.com/Handbook-of-Approximation-Algorithms-and-Metaheuristics-Second-Edition/Gonzalez/p/book/9780367570286"><cite>Handbook |
- | Approximation Algorithms and Metaheuristics</cite></a>. | + | of Approximation Algorithms and Metaheuristics</cite></a>. |
- | Chapman and Hall, 2007.</li> | + | Chapman and Hall, 2nd edition, 2018.</li> |
<!-- Authors: Holger H Hoos and Thomas Stutzle --> | <!-- Authors: Holger H Hoos and Thomas Stutzle --> | ||
<li><a name="Hoos.Stuetzle/2004"></a>Holger H. Hoos | <li><a name="Hoos.Stuetzle/2004"></a>Holger H. Hoos | ||
and Thomas Stützle. | and Thomas Stützle. | ||
- | <a href="http://www.sls-book.net"><cite>Stochastic Local Search : Foundations | + | <a href="https://www.cs.ubc.ca/~hoos/SLS-Book"><cite>Stochastic Local Search : |
- | & Applications</cite></a>. | + | Foundations & Applications</cite></a>. |
Morgan Kaufmann, 2004.</li> | Morgan Kaufmann, 2004.</li> | ||
<!-- Authors: Franz Rothlauf --> | <!-- Authors: Franz Rothlauf --> | ||
<li><a name="Rothlauf/2011"></a>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>. | + | <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. | Springer, 2011. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 180: | Linha 189: | ||
<li><a name="Edelkamp.Schroeder/2011"></a>Stefan | <li><a name="Edelkamp.Schroeder/2011"></a>Stefan | ||
Edelkamp and Stefan Schroeder. | Edelkamp and Stefan Schroeder. | ||
- | <a href="http://www.sciencedirect.com/science/book/9780123725127"><cite>Heuristic Search: Theory and Applications</cite></a>. | + | <a href="http://www.sciencedirect.com/science/book/9780123725127"><cite>Heuristic |
+ | Search: Theory and Applications</cite></a>. | ||
Morgan Kaufmann, 2011.</li> | Morgan Kaufmann, 2011.</li> | ||
Linha 186: | Linha 196: | ||
<li><a name="Genreau.Potvin/2010"></a>Michel | <li><a name="Genreau.Potvin/2010"></a>Michel | ||
Gendreau and Jean-Yves Potvin. | 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>. | + | <a href="https://link.springer.com/book/10.1007/978-1-4419-1665-5"><cite>Handbook |
+ | of Metaheuristics</cite></a>. | ||
Springer, 2nd edition, 2011. | Springer, 2nd edition, 2011. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 193: | Linha 204: | ||
<li><a name="Zaepfel.etal/2010"></a>Günter | <li><a name="Zaepfel.etal/2010"></a>Günter | ||
Zäpfel, Roland Braune, and Michael Bögl. | Zäpfel, Roland Braune, and Michael Bögl. | ||
- | <a href="http://link.springer.com/book/10.1007/978-3-642-11343-7/page/1"><cite>Metaheuristic search concepts</cite></a>. | + | <a href="https://link.springer.com/book/10.1007/978-3-642-11343-7"><cite>Metaheuristic |
+ | search concepts</cite></a>. | ||
Springer, 2010. | Springer, 2010. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 210: | Linha 222: | ||
<!-- Authors: Christian Blum and Maria Jose Blesa Aguilera and Andrea Roli and | <!-- Authors: Christian Blum and Maria Jose Blesa Aguilera and Andrea Roli and | ||
Michael Sampels --> | Michael Sampels --> | ||
- | <li><a name="Blum.etal/2008"></a>Christian Blum, | + | <li><a name="Blum.etal/2008a"></a>Christian Blum, |
Maria José Blesa Aguilera, Andrea Roli, and | Maria José Blesa Aguilera, Andrea Roli, and | ||
Michael Sampels, editors. | 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>. | + | <cite>Hybrid Metaheuristics : An Emerging Approach to Optimization</cite>. |
Springer, 2008. | Springer, 2008. | ||
- | INF: Recurso eletrônico.</li> | + | INF: Recurso eletrô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 --> | <!-- Authors: Carlos Cotta and Marc Sevaux and Kenneth Sorensen --> | ||
<li><a name="Cotta.etal/2008"></a>Carlos Cotta, | <li><a name="Cotta.etal/2008"></a>Carlos Cotta, | ||
Marc Sevaux, and Kenneth Sörensen, editors. | Marc Sevaux, and Kenneth Sö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>. | + | <a href="https://link.springer.com/book/10.1007/978-3-540-79438-7"><cite>Adaptive |
+ | and Multilevel Metaheuristics</cite></a>. | ||
Springer, 2008. | Springer, 2008. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
Linha 235: | Linha 249: | ||
Maniezzo, Thomas Stützle, and Stefan | Maniezzo, Thomas Stützle, and Stefan | ||
Voß, editors. | Voß, editors. | ||
- | <a href="http://link.springer.com/book/10.1007/978-1-4419-1306-7/page/1"><cite>Matheuristics</cite></a>. | + | <a href="https://link.springer.com/book/10.1007/978-1-4419-1306-7"><cite>Matheuristics</cite></a>. |
Springer, 2009. | Springer, 2009. | ||
INF: Recurso eletrônico.</li> | INF: Recurso eletrônico.</li> | ||
+ | |||
+ | <!-- Authors: J Dreo and A Petrowski and P Siarry and E Taillard --> | ||
+ | <li><a name="Dreo.etal/2006"></a>J. Dréo, | ||
+ | A. Pétrowski, P. Siarry, and | ||
+ | E. Taillard. | ||
+ | <cite>Metaheuristics for hard optimization</cite>. | ||
+ | Springer, 2006.</li> | ||
</ul> | </ul> | ||
Linha 248: | Linha 269: | ||
</a> | </a> | ||
</html> | </html> | ||
+ |