63ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 6. Inteligência Artificial e Redes Neurais

APLICAÇÃO DE RNAs NA SOLUÇÃO DO PROBLEMA DE GERAÇÃO DE HORÁRIOS EDUCACIONAIS

Aldrin Willy Mesquita Taborda 1 Francis de Oliveira Bins 2 Antonio Carlos Duarte Ricciotti 3 Carlos Alberto Tenório de Carvalho Júnior 4

1. Departamento de Informática – Universidade Federal de Rondônia – UNIR 2. Departamento de Engenharia Elétrica – Universidade Federal de Rondônia – UNIR 3. Prof. M.Sc. / Co-orientador – Departamento de Engenharia Elétrica – UNIR 4. Prof. Dr. / Orientador – Departamento de Engenharia Elétrica – UNIR

INTRODUÇÃO:

A confecção da grade de horários de instituições de ensino representa uma verdadeira prova à obstinação dos encarregados de tal tarefa. É bastante usual que o senso comum considere esse trabalho de natureza pouco complexa. Essa impressão, contudo, desaba diante do mais modesto estudo sobre a questão. Em muitos casos, esse trabalho é realizado manualmente. Tal situação, graças à sabida complexidade do problema, aliada aos riscos de erro inerentes ao trabalho manual, tornam-no ainda mais difícil. O Problema da Alocação de Horários (PAH) estende-se a uma ampla gama de atividades: da Geração de Horários Educacionais (PGHE), passando pela confecção de escala de plantonistas, agendamento de entrevistas, entre muitos outros problemas de satisfação de requisitos. Estudar as abordagens computacionais dadas a esse problema, bem como traçar um paralelo entre essas e as abordagens dadas pela Inteligência Artificial, em especial pelas Redes Neurais Artificiais (RNAs), culminando por demonstrar a Rede de Hopfield modificada como a mais eficiente, foram os objetivos centrais do estudo. A relevância do trabalho está em estudar o PAH sob uma abordagem ainda pouco explorada, cujo alto poder de processamento e aprendizagem são bastante atraentes face à natureza do problema que constitui seu objeto.

METODOLOGIA:

Para a consecução dos objetivos do estudo, a pesquisa foi estruturada em três etapas. Na primeira, tratou-se de obter subsídios teóricos e historiográficos acerca do Problema de Geração de Horários Educacionais, bem como a respeito das técnicas computacionais desenvolvidas para tratá-lo. Em uma segunda etapa, consubstanciaram-se os dados obtidos com profunda pesquisa bibliográfica acerca do campo da Inteligência Artificial envolvida, especialmente, a partir dos anos 80, no tratamento computacional dado ao tema. Na terceira etapa, o foco do estudo se deteve na comparação qualitativa entre as abordagens de Inteligência Artificial aplicadas ao problema e, dentre essas, qual dos modelos de Redes Neurais Artificiais apresentava melhor desempenho e maior grau de exeqüibilidade para lidar com o PGHE.

RESULTADOS:

O estudo bibliográfico inicial demonstra o PGHE como um problema de satisfação, admitindo três variedades: Problema Turma-Professor (PTP); Problema de Cursos Universitários (PCU), Problema de Horários para Exames (PHE). Em síntese, pode-se dizer que o primeiro consiste em atribuir aulas aos períodos de modo a evitar sobreposições de turmas ou professores em mais de uma aula ao mesmo tempo, enquanto os dois últimos, com algumas diferenças, se ocupam de alocar um grupo de disciplinas de cada curso a um dado número de salas e períodos de tempo. Em todos os casos, o PAH pode ser tido como pertencente a uma classe especial de problemas, chamada de NP-completos. Tendo em vista o grau de complexidade inerente ao problema, a Inteligência Artificial surge como natural abordagem computacional e, dentro dela, as RNAs têm se mostrado uma solução possível, razão pela qual vêm sendo motivo de estudo ao longo dos últimos anos. Estudou-se neste trabalho três dos principais modelos que tratam o PGHE por meio de RNAs: Ativação Interativa e Competição; Rede Neural de Potts; e Rede Neural de Hopfield modificada. A análise comparativa dos resultados obtidos por cada modelo demonstrou que o modelo de Hopfield supera os outros dois, exibindo, inclusive, qualidade escalar superior a outras técnicas.

CONCLUSÃO:

As RNAs ainda são um método pouco estudado como forma de resolução para o PGHE. Sua aplicação para este problema apareceu pela primeira vez na transição entre as décadas de 1980 e 1990. Contudo, a utilização dessa ferramenta da corrente conexionista da Inteligência Artificial tem se mostrado uma solução interessante ao problema. Aliado aos conhecidos atributos de processamento paralelo e poder aprendizagem por elas exibidos, as RNAs se transformam, assim, num convidativo campo de pesquisa para a Ciência da Computação. Nesse passo, os resultados conquistados utilizando a abordagem da Rede Neural de Hopfield modificada provaram-na comparável com as melhores técnicas metaheurísticas para a solução do problema. De tal forma que a referida rede neural se mostrou capaz de produzir soluções de boa qualidade para problemas de alocação de horário extremamente difíceis. Quando consideradas vantagens em termos de velocidade, estas podem ser obtidas por meio da implementação em hardware. O modelo de Hopfield mostrou-se superior aos outros dois modelos mencionados também porque consegue lidar com problemas de igual tamanho e complexidade, bem como com problemas maiores.

Palavras-chave: Redes Neurais Artificiais, Problema de Alocação de Horários, Problemas NP-completos.