Resoluçao de Timetabling utilizando algoritmos genéticos e evoluçao cooperativa

AnexosOrientadora: Aurora T. Ramirez PozoDissertaçao(mestrado)- Universidade Federal do Paraná. Setor de Ciencias Exatas. Departamento de Informática. Curso de Mestrado em InformáticaInclui bibliografiaResumo: A produção de grades horárias em instituições de ensino é uma tarefa complexa e de difícil solução, pois, neste contexto, existem muitas restrições necessárias à validade e aplicabilidade das respostas produzidas. Na literatura, a produção de grades horárias e, na verdade, uma das variações de timetabling, o qual, em essência, é um problema de escalonamento de eventos em um periodo finito de tempo, sujeito a restrições, como por exemplo, tempo, recursos humanos disponíveis (professores), recursos físicos existentes (salas de aula) e atividades a serem desenvolvidas (exames, aulas, entre outros). Para solucionar esse problema e automatizar o processo, abordagens de Inteligência Artificial têm sido aplicadas com sucesso, mais especificamente, os métodos da Computação Evolutiva. A computação evolutiva define uma classe de algoritmos que modelam computacionalmente os conceitos da teoria da Evolução de Charles Darwin. Esses algoritmos aplicam operadores genéticos sobre populações de indivíduos, visando à produção de indivíduos mais aptos que os antigos. Como resultado, obtêm-se indivíduos ou soluções candidatas com um alto grau de aptidão para solucionar um problema específico. O objetivo principal deste trabalho é estudar e implementar uma solução para o problema de Geração de Grades Horárias, com base na Computação Evolutiva. O método evolutivo escolhido é denominado Algoritmo Coevolutivo Cooperativo. Esse método subdivide um problema complexo em problemas menores, sendo que cada um deles é representado por uma população pertencente ao dominio do problema. Cada uma dessas populações possui características individuais e, no processo, todas evoluem paralelamente, de maneira cooperativa, por meio de sucessivas aplicações de operadores genéticos. Ao final do processo, os representantes de cada uma das populações formam, em conjunto, uma solução completa. Para verificar a validade do método para a resolução do problema em estudo, implementou-se um algoritmo cooperativo. Os resultados dos experimentos mostraram que algoritmos cooperativos são ferramentas poderosas, capazes de resolver problemas complexos de otimização numérica sujeitos a restrições.Abstract: The production of schedules in educational institutions is a complex and hard solution, because in this scenario there are many constraints required to the validity and applicability of the produced results. According to the literature, the production of schedules in educational institutions, in fact, one of the Timetabling variations, which is, in essence, a problem of event scheduling in a finite period of time, subjected to constraints, for example, time, human resources (teachers, lecturers, etc), physical resources (rooms) and activity to be advanced (exams, class, etc). In order to solve this problem and automate the process, -Artificial intelligence methods have been used with success, more specifically, Evolutionary Computing methods. The evolutionary computing defines a class of algorithms that computationally model the Charles Darwin's Evolution theory concepts. These algorithms apply genetic operators over a population of individuals, aiming at the production of individuals more capable than the older ones. The result is candidate individuals or solutions with a high degree of capability to solve a specific problem. The main goal of this work is to study and implement a solution for the Schedule Generation problem, based on Evolutionary Computing. The chosen evolutionary method is denominated Cooperative Co-Evolutionary Algorithm. This method divides a complex problem in smaller ones, being each small problem represented by a population that belongs to the problem domain. Each population has individual features and all of them evolve in a parallel and cooperative way through the successive application of genetic operators. At the end of this process, the representatives of each population compose a complete solution. In order to verify the validity of the method for the solution of the problem under study, a cooperative algorithm was implemented. The results of the experiments showed that the co-evolutionary algorithms are powerful tools, capable of solving complex problems of numeric optimization subjected to constraints