Definição e implementação de uma função de avaliação para um sistema de geração de grade horária que utiliza como método de busca algoritmo genético

Abstract

A presente monografia descreve o estudo elaborado acerca de um sistema para geração de grade horária para Instituições de ensino por meio de algoritmos genéticos. Os estudos desenvolvidos tiveram como ponto de partida o “Sistema para Geração de Grade Horária Para Instituições de Ensino” desenvolvido na Universidade do Planalto Catarinense (UNIPLAC) em 2001. O problema de geração de grade horária, ou timetabling consiste na alocação de recursos, combinados ou não, necessários a execução de uma série de tarefas tendo normalmente como base o fator tempo. As grades geradas pelo sistema da UNIPLAC apresentavam coincidência de horário e não atendiam completamente ao critério de disponibilidade dos professores em lecionar. O mesmo ocorria devido a uma definição incompleta da função de avaliação, que corresponde em um algoritmo genético à função que atribui o grau de adaptação de cada cromossomo dentro de uma população. Cada cromossomo da população representa uma possível solução do problema e, no problema em questão, quanto menos restrições apresentar um cromossomo melhor será o seu grau de adaptação e conseqüentemente, maior as suas chances de ser a solução do problema. Para eliminação das coincidências de horários do sistema da UNIPLAC foi implementada uma função de avaliação mais refinada e uma função de teste que seleciona com precisão a melhor solução gerada pelo algoritmo. Os resultados obtidos corresponderam aos objetivos propostos, eliminando em 100% dos casos as coincidências de horários e atendendo a todas as restrições impostas pelo problema. O nome do sistema desenvolvido foi chamado de URANO.