Algoritmo genético aplicado a geração automática de grade de horários

Abstract

Este trabalho apresenta a solução de um problema muito comum nas instituições de ensino, o problema de distribuição de grade horária. Problemas de grade horária são complexos devido ao grande número de variáveis envolvidas, além de possuir diversas soluções possíveis. Para solucionar este problema foi utilizado o algoritmo genético. Algoritmo Genético é um ramo da inteligência artificial que possibilita uma busca heurística em um grande espaço de soluções possíveis. Ele se baseia na evolução natural, onde a cada geração de uma população, a mesma evolui e se adapta ao ambiente ao qual ela está inserida. Partindo desse princípio podemos utiliza-lo para resolver diversos problemas complexos. Ele possui uma estrutura genérica, onde se modela o cromossomo/indivíduo de acordo com o problema, avalia o mesmo, seleciona os mais aptos (de acordo com a avaliação), utiliza operadores de cruzamento aos indivíduos “pais” para que possam gerar “filhos” melhores e que terão mais chances de sobrevivência na população, realiza-se a mutação e o avalia novamente, repetindo o processo até que se atinja um critério de parada predefinido. Essa estrutura pode e deve ser modelada de acordo com o problema. Para a resolução do problema de grade horária proposto neste trabalho, o cromossomo foi estruturado de forma que já suprisse algumas restrições, fazendo com que fosse apenas necessário alocar o horário de aula na mesma. Utilizando uma avaliação onde caso o indivíduo que infringisse alguma restrição sofresse uma penalidade (valor do fitness), os indivíduos com um menor valor de fitness estão mais próximos de uma solução para o problema. Foi desenvolvido um software para realizar a distribuição utilizando o AG e para a codificação a linguagem Java e o banco de dados em MySql. Foi possível observar na execução do algoritmo que a cada geração a população evoluía, e que o AG foi capaz de trazer uma boa solução para o problema.