====== Trabalhos ====== ===== Considerações gerais ===== * O trabalho é individual. * Cada um escolhe **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** * :!: **Apresentar uma proposta ate 15 de novembro**. * 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. * :!: **Entrega do trabalho escrito: 4 de dezembro**. * Trabalho: {{tp20171.pdf|Como perder pontos?}} ===== Problemas ===== {{t20182.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 (VNS) ===== 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)]]** ===== Grupos e trabalhos selecionados ===== ^ No. ^ Trabalho ^ Nome ^ P ^ R ^ A ^ C ^ | 1 | ADMV+SA | Leonardo Ferrazza | Ok | Ok (+1) | Ok (+1) | Ok (+1) | | 2 | CMB+SA | Eduarda Trinidade | Ok (+1) | Ok (+2) | Ok (+2) | Ok (+1) | | 3 | ADMV+GA | Felipe de Mello Flores | Ok | Ok | Ok | Ok | | 4 | CMB+BT | Pedro Caetano de Abreu Teixeira | Ok | Ok (+1) | Ok | Ok | | 5 | ADMV+ILS | Giovane Alves Fonseca | Ok | Ok | Ok | Ok | | 6 | MOC+SA | Bruno Santana | Ok (+2) | Ok | Ok | Ok | | 7 | ADMV+VNS | Gabriel Pakulski | Ok (+1) | Ok (+3) | | Ok (+6) | | 8 | CMB+AG | Gabriel Haggstrom | Ok (+2) | Ok (+4) | | Ok (+4) | | 9 | MOC+ILS | Henrique Goetz | Ok (+1) | Ok | Ok | Ok | | 10 | MOC+GA | Cassiano Bruckhoff | Ok (+2) | | Ok (+3) | Ok (+3) | | 11 | MOC+BT | Pedro Salgado Perrone | Ok (+1) | Ok | Ok | Ok | | 12 | CMB+GRASP | Gabriel Mutti | Ok (+1) | Ok | Ok | Ok | | 13 | CMB+ILS | Eduardo Henrique Ferreira do Nascimento | | Ok | Ok | Ok | | 14 | MOC+GRASP | João Pedro Goncalves Moreira | Ok (+4) | Ok (+1) | Ok | Ok | | 15 | CMB+VNS | Henrique Chaves Pacheco | Ok (+1) | | | Ok (+6) | | 16 | ADMV+BTY | Matheus Alan Bergmann | Ok (+1) | Ok | Ok | Ok | Status: 10 de dezembro.\\ #Trabalhos definidos: 16/23. P=proposta, R=Relatorio, A=Apresentação, C=Codigo. (+x): entregue (com atraso de x dias). ==== Seleções ==== ^ ^ ADMV ^ CMB ^ MOC ^ | SA | X | X | X | | ILS | X | X | X | | IGA | | | | | BT | X | X | X | | AG | X | X | X | | GRASP | | X | X | | VNS | X | X | | ADMV = Árvore direcionada de menor valor CMB = Coloração mais balanceada MOC = Mochila conexa ===== Agenda ===== ^ Data ^ Hora ^ Apresentação ^ | 04/12 | 13.30 | MOC+GRASP | | 04/12 | 13.42 | MOC+ILS | | 04/12 | 13.54 | MOC+AG | | 04/12 | 14.06 | MOC+BT | | 04/12 | 14.18 | MOC+SA | | 04/12 | 14.30 | CMB+SA | | 04/12 | 14.42 | CMB+AG | | 04/12 | 14.54 | CMB+GRASP | | 06/12 | 13.30 | CMB+ILS | | 06/12 | 13.42 | CMB+BT | | 06/12 | 13.54 | CMB+VNS | | 06/12 | 14.06 | ADMV+BT | | 06/12 | 14.18 | ADMV+AG | | 06/12 | 14.30 | ADMV+ILS | | 06/12 | 14.42 | ADMV+VNS | | 06/12 | 14.54 | ADMV+SA |