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 é 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 26/5/2014**.
    * Contéudo: 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.
  * **Prazos** Entrega do trabalho escrito: 18/6/2014.
===== Problemas =====
{{t-2014-1b.pdf|Definição dos problemas}}

  - [[http://tracer.lcc.uma.es/problems/minla/minla.htm|Linear arrangement]]
  - [[http://www.mpi-inf.mpg.de/departments/d1/projects/benchmarks/UflLib|Localização de facilidades não-capacitadas]] {{http://www.inf.ufrgs.br/~mrpritt/oc/ufl-2014-1.tgj|Instâncias}} e o [[formato-ufl|formato]]
  - Mapeamento de redes virtuais

===== Meta-heurísticas =====

  * Simulated annealing (SA)
  * Busca local iterada / Algoritmo guloso iterado (ILS/IGA)
  * Busca Tabu (BT)
  * Algorítmo genético/memético (GA)
  * GRASP

===== 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 saida 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 parameteros do métodos (temperature,lista tabu e tenure,...), critério de terminação. (Essa lista não é exhaustiva.)
  * Avaliação experimental\\
    Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Método de escolha de parâmetros. Discussão e conclusões.
  * 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 {{sa-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 bibliotécas 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 ^ A ^ R ^ C ^
|   1 |  LA + GRASP  |  Vinícius  | <html>&#x2713;</html> | | <html>&#x2713;</html> | <html>&#x2713;</html> |
|   2 |  LF + BT     |  Rodrigo   | <html>&#x2713;</html> | <html>&#x2713;</html> | <html>&#x2713;</html> | <html>&#x2713;</html> |
|   3 |  LA + AG     |  Matheus   | <html>&#x2713;</html> | | | |
|   4 |  LA + BT     |  Danhuri   | <html>&#x2713;</html> | | | |
|   5 |  LF + AG     |  Felipe    | <html>&#x2713;</html> | | | |
|   6 |  LA + SA     |  William   | <html>&#x2713;</html> | | <html>&#x2713;</html> | |
|   7 |  MR + SA     |  Fernando  | <html>&#x2713;</html> | | <html>&#x2713;</html> | |
|   8 |  LF + SA     |  Alana     | <html>&#x2713;</html> | | <html>&#x2713;</html> | <html>&#x2713;</html> |
|   9 |  LA + ILS    |  Leonardo  | <html>&#x2713;</html> | | | |
Status: 3 de julho.\\
#Escolhas: 9/13.

P=Proposta, A=Apresentação, R=Relatório, C=Código. <html>&#x2713;</html> (+x): entregue (com atraso de x dias).
==== Seleções ====

^       ^ LA  ^ LF  ^ MR ^
| SA    |  X  |  X  |  X  |
| ILS   |  X  |     |     |
| BT    |  X  |  X  |     |
| AG    |  X  |  X  |     |
| GRASP |  X  |     |     |

LA = Linear arrangement, LF = locação de facilidades, MR = mapeamento de redes;

===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 23/06 |  8.30 |  LA + GRASP (Vinícius)  |
| 23/06 |  8.50 |  LA + AG (Matheus)      |
| 23/06 |  9.10 |  LA + BT (Danhuri)      |
| 23/06 |  9.30 |  LA + ILS (Leonardo)    |
| 23/06 |  9.50 |  LF + SA (Alana)        |
| 02/07 |  8.30 |  MR + SA (Fernando)     |
| 02/07 |  8.50 |  LF + BT (Rodrigo)      |
| 02/07 |  9.10 |  LA + SA (William)      |
| 02/07 |  9.30 |  LF + AG (Felipe)       |
| 02/07 |  9.50 |                         |
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
