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.
 ====== Trabalhos ======

===== Considerações gerais =====

  * O trabalho é em grupos até dois.
  * Cada grupo 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**

  * O trabalho é estruturado em quatro etapas

^ Etapa            ^ Prazo ^ Entregáveis ^
| 1 | 25 de abril     | Descrição e implementação do modelo matemático com resultados (20%)                                          |
| 2 | 02 de maio      | Proposta concreta com descrição de heurística e de todos componentes heurístcas aplicados ao problema (25%)  |
| 3 | 13 de maio      | Trabalho escrito final (parte do modelo e da heurística) (35%)                                               |
| 4 | 13 e 18 de maio | Apresentação do trabalho (20%)                                                                               |

  * Conteúdo da proposta: 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.

  * Trabalho: {{tp20171.pdf|Como perder pontos?}}

===== Problemas =====

{{t20202.pdf|Definição dos problemas}} :!: Atualizado: 25 de março!

===== 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        ^  E1  ^  E2  ^  E3  ^  E4  ^
|   1 |  RMV+SA     |  Jéssica <del>& Roberta</del>  |  |   -   |   ✓    |   ✓    |
|   2 |  RMV+AG     |  Tiago & Alexandre    |   ✓      |   ✓    |   ✓    |   ✓    |
|   3 |  RMV+GRASP  |  <del>Gabriel</del>   |   -      |        |        |        |
|   4 |  PMD+SA     |  Luiza & Francielle   |   ✓      |   ✓    |   ✓    |   ✓    |
|   5 |  RMV+ILS    |  Argel & Matheus      |   ✓      |   ✓    |   ✓    |   ✓    |
|   6 |  RMV+VNS    |  Lucas & Renan        |   ✓      |   ✓    |   ✓    |   ✓    |
|   7 |  RMV+BT     |  <del>Andrei &</del> Rafael  |  ✓  |  ✓   |   ✓    |   ✓    |
|   8 |  CMB+GRASP  |  Andrei & Augusto     |   ✓      |   ✓    |   ✓    |   ✓    |
|   9 |  PMD+BT     |  Felipe & Isis        |   ✓      |   ✓    |        |        |
|  10 |  PMD+VNS    |  <del>Vagner</del>    |   ✓      |   -    |        |        |
|  11 |  CMB+GA     |  Gabriel RP & Arthur  |   ✓      |   ✓    |   ✓    |   ✓    |
|  12 |  CMB+SA     |  Bruna & Gessica      |   ✓      |   ✓    |   ✓    |   ✓    |
|  13 |  CMB+BT     |  Fernando             |   ✓      |   ✓    |   ✓    |        |
|  14 |  CMB+ILS    |  <del>Renan</del>     |   -      |   -    |        |        |
|  15 |  CMB+VNS    |  Aline & Mayra        |   ✓      |   ✓    |   ✓    |   ✓    |

Status: 17 de maio.\\
#Trabalhos definidos: 26/30.

A=Apresentação, R=Relatorio, C=Codigo.  (+x): entregue (com atraso de x dias).

==== Seleções ====

^       ^  CMB   ^  RMV    ^  PMD  ^
| SA    |  X   |    X   |   X    |
| ILS   |  X   |    X   |        |
| IGA   |      |        |        |
| BT    |  X   |    X   |   X    |
| AG    |  X   |    X   |        |
| GRASP |  X   |    X   |        |
| VNS   |  X   |    X   |   X    |

CMB = Coloração mais balanceada\\
RMV = Rota mais valiosa\\
PMD = Partição mais distante

===== Agenda =====

^ Data ^ Hora ^ Apresentação ^
| 13/05 |  13.30 |  [Transferido]  |
| :::   |  13.44 |  RMV+AG	  |
| :::   |  13.58 |  RMV+ILS	  |
| :::   |  14.12 |  PMD+VNS	  |
| :::   |  14.26 |  RMV+BT	  |
| :::   |  14.40 |  <del>CMB+BT</del>  |
| :::   |  14.54 |  CMB+VNS	  |
| 18/05 |  13.30 |  PMD+BT        |
| :::   |  13.44 |  CMB+GRASP 	  |
| :::   |  13.58 |  CMB+GA    	  |
| :::   |  14.12 |  PMD+SA        |
| :::   |  14.26 |  RMV+VNS       |
| :::   |  14.40 |  CMB+SA        |
| :::   |  14.54 |  RMV+SA        |
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
