Tabela de Conteúdos
Trabalhos
Considerações gerais
- O trabalho pode ser feito em grupos de dois ou três.
- Cada grupo escolhe um problema e uma meta-heurística.
- Cada grupo implementa o problema, conduz testes com instâncias definidas (listadas abaixo), documenta os resultados e apresenta-los.
Apresentar uma proposta ate 28/11/2008.
Problemas
-
- Instâncias: add20,data,3elt,uk,add32,bcsstk33,whitaker3,crack,wing_nodal,fe_4elt2,vibrobox,bcsstk29,4elt,fe_sphere,cti,memplus
-
- Instâncias 1): uf75-325(31,41),uf125-538(52,96),uf175-753(53,58),uf250-1065(97,93),logistics.a,logistics.b,qg4-08,qg4-09,qg6-09,qg7-09
Meta-heurísticas
- Simulated annealing (SA)
- Variable neighborhood search (VNS)
- Busca Tabu (BT)
- Algorítmo genético/memético (GA)
- GRASP
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, por exemplo representação do problema e a seleção das operações.
- Avaliação experimental
Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Discussão e conclusões.
- Implementação
Critérios básicas da eng. de SW: documentação, legibilidade, etc.
O trabalho consiste em:
- Um relatório com a documentação da solução com resultados e discussão (veja um exemplo).
- 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.
Grupos e trabalhos selecionados
| No. | Trabalho | Grupo | A |
|---|---|---|---|
| 1 | MAXSAT+VNS | Rodrigo Santos, Henrique Valer | |
| 2 | GBP+GA | Guilherme Lima, Giovanni Rinaldi, Roger Gouveia | |
| 3 | MAXSAT+SA | Leandro Vasconcelos, Francisco Rodrigues | |
| 4 | GBP+SA | Leonardo, Júlio, Wagner | A |
| 5 | MAXSAT+GRASP | Daniel, Soares, Gabriel Pereira, Vanius Zapalowski | |
| 6 | MAXSAT+BT | Marcius Vieira, Rosele Schmidt, Soraya Hossain | |
| 7 | GBP+BT | Cezar Rosa, Bruno | A |
| 8 | MAXSAT+GA | Felipe, Adrian, Thiago | |
| 9 | GBP+GRASP | Carlos | A |
#Escolhas: 20/27.
Seleções
| BPG | MAXSAT | |
|---|---|---|
| SA | X | X |
| VNS | X | |
| BT | X | X |
| GA | X | X |
| GRASP | X | X |
Agenda
| Data | Hora | Apresentação |
|---|---|---|
| 01/12 | 10.30 | 4 |
| 01/12 | 10.50 | 2 |
| 01/12 | 11.10 | 9 |
| 01/12 | 11.30 | 7 |
| 01/12 | 11.50 | |
| 03/12 | 10.30 | 3 |
| 03/12 | 10.50 | 6 |
| 03/12 | 11.10 | 8 |
| 03/12 | 11.30 | 5 |
| 03/12 | 11.50 | 1 |
1)
Obs: Todas instâncias são satisfatíveis, tal que o valor da solução ótima é o número de claúsulas.