Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

@@ Linha 1: / Linha 1: @@
+====== Trabalhos ======
+===== Considerações gerais =====
+  * O trabalho é em grupos de dois.
+  * Cada grupo pode escolher **um problema** e **uma meta-heurística**.
+  * Tarefa de todos:
+      - Formular o problema como programa linear ou inteiro
+      - Resolver as instâncias definidas (abaixo) com um solver genérico (p.ex. CPLEX,GLPK,SCIP)
+      - Definir e implementar e meta-heurística escolhida para o problema
+      - Resolver as instâncias definidas com a meta-heurística
+      - Documentar e analisar os experimentos: **relatório**
+      - Apresentar os resultados: **apresentação em aula**
+  * :!: **Submeter uma proposta ate 5 de setembro**
+    * Conteúdo: Definição dos principais elementos da abordagem (representação de uma solução, solução inicial, vizinhanças, critério de parada, etc.) e a formulação matemática do problema.
+    * Encaminhar a proposta para mrpritt@inf.ufrgs.br
+    * Cada proposta vai ter um feedback, mas não é avaliada.
+  * :!: **Entrega do trabalho escrito: 3 de outubro**
+  * Trabalho: {{tp20171.pdf|Como perder pontos?}}
+===== Passo a passo =====
+  - Ler a {{t20221.pdf|definição dos problemas}}, selecionar um problema.\\
+  - Selecionar uma heurística (Aulas 18, 19, 20).\\
+  - Definir um grupo (até 2 integrantes) e informar por email: grupo formado, [[2022-1-trabalhos#selecoes|problema e heurística selecionada]]. (Cada combinação problema+heurística é disponível somente uma vez.)\\
+  - Submeter uma proposta até 5 de setembro.\\
+  - Entregar o trabalho completo até 3 de outubro.\\
+  - Apresentar o trabalho numa das aulas 29 ou 30 (a [[2022-1-trabalhos#agenda|agenda]] vai ser definida mais próximo das datas de apresentação).
+===== Problemas =====
+{{t20221.pdf|Definição dos problemas}}
+===== Meta-heurísticas =====
+  * Simulated annealing (SA)
+  * Busca local iterada / Busca gulosa iterada (ILS)
+  * Busca Tabu (BT)
+  * Algorítmo genético/memético (GA)
+  * GRASP
+  * Variable neighborhood search
+===== Convenções da implementação =====
+  * Todas implementações devem aceitar uma instância no formato do problema na entrada padrão (stdin) e imprimir a melhor solução encontrada na saída padrão (stdout).
+  * Os principais parâmetros do método devem ser definíveis pela linha de comando.
+  * O primeiro parâmetro da linha de comando é o nome de um arquivo para gravar a melhor solução encontrada.
+===== Documentação e critérios de avaliação =====
+O objetivo do trabalho é conhecer uma meta-heurística profundamente e ganhar experiência prática para aplicar-la em novos problemas. A avaliação reflete esse objetivo.
+  * Entendimento do método\\
+    Definição e justificativa da abordagem ao problema. Todas escolhas feitas para aplicar a meta-heuristica para o problema em questão devem ser claramente relatadas. Isso inclui a representação do problema, a função objetivo, a geração da solução inicial, a vizinhança e a estratégia de escolha em caso de buscas locais, os operadores (crossover,mutação) em caso de algoritmos genéticos, outros parâmetros do métodos (temperatura,lista tabu e tenure,...), critério de terminação. (Essa lista não é exaustiva.)
+  * Avaliação experimental\\
+    Reprodutibilidade: Documentação das instâncias, tempo de execução, parâmetros, número de experimentos, semente do gerador randômico, etc. Método de escolha de parâmetros. Discussão e conclusões. Em particular: para métodos estocásticos os valores apresentados devem ser médias de pelo menos 5 replicações de cada experimento com sementes diferentes.
+  * Implementação\\
+    Critérios básicas da eng. de SW: documentação, legibilidade, etc.
+O trabalho consiste em:
+  * Um [[:relatorio|relatório]] com a documentação da solução com resultados e discussão (veja um {{ga-r.pdf|exemplo}}).
+    * Elementos obrigatórios: Introdução, Formulação, Descrição da solução, Resultados obtidos com análise, Conclusão e Bibliografia.
+    * Nos resultados computacionais, uma tabela informando, para cada instância: valor da solução inicial (SI), valor da solução final (SF), desvio percentual da solução final em relação à inicial calculado como 100*(SI-SF)/SI, desvio percentual da SF em relação à solução ótima, tempo computacional da metaheurística, tempo computacional da resolução via solver.
+  * Uma implementação (linguagem arbitrário desde seja padrão sem uso de bibliotecas proprietárias e pode ser compilado e executado usando somente software livre).
+  * Uma apresentação em aula. Como apresentar? [[http://lmgtfy.com/?q=como+apresentar+bem+um+artigo+cientifico|Mais informações.]]
+**[[trabalho-faq|Perguntas frequentes (FAQ)]]**
+===== Trabalhos selecionados =====
+^ No. ^ Trabalho   ^ Nome        ^  P  ^  A  ^  R  ^  C  ^
+|  1  | PCMCDC+ILS  | Suryalall           |   	✓.      |          |    ✓     |    ✓     |
+|  2  | PCMCDC+AG   | Marco               |     ✓.      |     ✓    |    ✓     |    ✓     |
+|  3  | PCMCDC+SA   | Gustavo, Henrique   |     ✗       |     ✓    |    ✓     |    ✓     |
+|  4  | TTB1+GRASP  | Bruno               |             |          |          |          |
+|  5  | RML+GRASP   | Gabriel, Vitória    |     ✓.      |     ✓    |    ✓     |    ✓     |
+|  6  | RML+SA      | <del>Hiram, Bibiana</del>  |     ✓.      |          |          |          |
+|  7  | MSRRR+ILS   | <del>Gabriel Schumacker</del>  |     ✗       |          |          |          |
+|  8  | MSRRR+BT    | Harold, Vitor       |     ✓.      |     ✓    |    ✓     |    ✓     |
+|  9  | MSRRR+GRASP | Gustavo Noll        |     ✗       |          |    ✓     |    ✓     |
+Status: 10 de outubro.\\
+#Trabalhos definidos: 13/21.
+P=Proposta, A=Apresentação, R=Relatório, C=Código.   (+x): entregue (com atraso de x dias).
+==== Seleções ====
+^       ^  RML   ^  PCMCDC  ^ MSRRR   ^
+| SA    |   X    |  X    |     |
+| ILS   |        |  X    |  X  |
+| IGA   |        |       |     |
+| BT    |        |       |  X  |
+| AG    |        |  X    |     |
+| GRASP |   X    |       |  X  |
+| VNS   |        |       |     |
+RML = Rota de menor "lookahead"\\
+PCMCDC = Problema de múltiplos contêineres\\
+MSRRR = Alocação de servidores
+===== Agenda =====
+^ Data ^ Hora ^ Apresentação ^
+| 03/10 |  10.30 | RML+GRASP    |
+| :::   |  10.50 | <del>RML+SA</del>       |
+| :::   |  11.10 | PCMCDC+ILS   |
+| :::   |  11.30 | PCMCDC+AG    |
+| :::   |  11.50 | PCMCDC+SA    |
+| 05/10 |  10.30 | <del>MSRRR+ILS</del>    |
+| :::   |  10.50 | MSRRR+GA     |
+| :::   |  11.10 | MSRRR+GRASP  |
+| :::   |  11.50 | <del>TTB1+GRASP</del>   |

Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Diferenças

Ferramentas de Página