TCC
Uso do algoritmo genético e recozimento simulado para o problema de alocação de salas
Carregando...
Notas
Data
Autores
Orientadores
Editores
Coorientadores
Membros de banca
Título da Revista
ISSN da Revista
Título de Volume
Editor
Faculdade, Instituto ou Escola
Departamento
Programa de Pós-Graduação
Agência de fomento
Tipo de impacto
Áreas Temáticas da Extenção
Objetivos de Desenvolvimento Sustentável
Dados abertos
Resumo
Este trabalho apresenta uma comparação entre duas técnicas heurísticas para o Problema
de Alocação de Salas: o Algoritmo Genético e o Recozimento Simulado (Simulated
Annealing). Sabe-se este problema é NP-Difícil e que vários métodos heurísticos têm sido
propostos para resolvê-lo. Os métodos heurísticos procuram por soluções em tempo viável
para problemas onde os algoritmos exatos não terminam em tempo hábil, embora não
garantam encontrar a solução ótima. Além das restrições de otimização de espaço e
alocação das aulas em salas que evitem superlotações, o Problema de Alocação de Salas
considerado envolve restrições adicionais referentes às distâncias percorridas pelos alunos
para se deslocarem de uma sala para a próxima, como para aulas práticas. Os resultados de
cada método são comparados, considerando o mesmo problema e ainda a utilização dos
mesmos tipos de operadores de busca local. Por fim, são feitas conclusões sobre os
operadores adotados e sugestões de possíveis melhorias nas soluções propostas.
Abstract
This work address the implementation and comparison of two heuristic techniques for
Class Assign Problem: Genetic Algorithm and Simulated Annealing. Since it is a NP-hard
problem, some heuristic methods have been proposed to solve it. The heuristic methods
search for good solutions in reasonable time, when exact methods are appropriated. The
Class Assign Problem considered involves additional restrictions when compared to others
previous similar works. These restrictions are the covered distance by students to walk
from a room to another and the allocation of practical lessons. The best results for each
method are compared observing same set of local search operators. To do end, some
conclusions are possible and suggestions are presented for possible improvements on both
algorithms.
Descrição
Área de concentração
Otimização combinatória
Agência de desenvolvimento
Palavra chave
Marca
Objetivo
Procedência
Impacto da pesquisa
Resumen
ISBN
DOI
Citação
OLIVEIRA, A. C. de. Uso do algoritmo genético e recozimento simulado para o problema de alocação de salas. 2006. 72 p. Monografia (Graduação em Ciência da Computação) – Universidade Federal de Lavras, Lavras, 2006.