Utilização de Algoritmos Genéticos para otimização de soluções
Transcrição
Utilização de Algoritmos Genéticos para otimização de soluções
THIAGO DIAS SIMÃO UTILIZAÇÃO DE ALGORITMOS GENÉTICOS PARA OTIMIZAÇÃO DE SOLUÇÕES PARA O TIMETABLING ESCOLAR LAVRAS - MG 2013 THIAGO DIAS SIMÃO UTILIZAÇÃO DE ALGORITMOS GENÉTICOS PARA OTIMIZAÇÃO DE SOLUÇÕES PARA O TIMETABLING ESCOLAR Monografia de Graduação apresentada ao Departamento de Ciência da Computação para obtenção do título de Bacharel em “Ciência da Computação” Orientador Prof. Dr. Joaquim Quinteiro Uchôa LAVRAS - MG 2013 Dedicada à minha namorada... AGRADECIMENTOS Agradeço aos professores Joaquim e Ulisses, por todo apoio e aprendizado que me proporcionaram. À Escola Estadual Dona Rita Amélia de Carvalho por disponibilizar os dados para esta pesquisa. Ao DCE Ascender por todas as experiências proporcionadas. Ao BREJÃO, minha família durante a graduação. À Mariane, que mesmo quando longe sempre esteve tão próxima. À toda minha família, em especial minha mãe, Eliza, que tanto me ajudou neste trabalho! Forever trusting who we are No, nothing else matters (James e Lars Ulrich) RESUMO Este trabalho aborda o problema de criação de horários para escolas do ensino médio e fundamental. É motivado principalmente pela complexidade do mesmo, tratando-se de um problema NP-Completo, consequentemente um grande custo para as escolas, uma vez que um especialista pode gastar dias para encontrar um bom horário. Optou-se por abordar o problema utilizando os algoritmos genéticos, por sua flexibilidade e eficiência para tratar problemas de otimização. O algoritmo foi desenvolvido de forma a ser aplicado em uma instância real do problema. No final é realizada uma comparação entre as soluções encontradas pelo algoritmo e pelo especialista. Um aspecto importante deste trabalho foi o desenvolvimento de uma aplicação gratuita para utilização por parte das escolas, além disso trata-se de uma ferramenta open-source o que permitirá a outros pesquisadores sua utilização para novos projetos nessa área. Palavras-Chave: Timetabling Escolar; Algoritmos Genéticos; Otimização SUMÁRIO 1 Introdução 12 1.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Timetabling Escolar 14 2.1 Restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Algoritmos Genéticos 20 3.1 Funcionamento Geral do AG . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Definições e nomenclatura . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 População . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6 Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.7 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.8 Sobrevivência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.9 Condições de Término . . . . . . . . . . . . . . . . . . . . . . . . . 31 4 Adaptação do Timetabling Escolar aos Algoritmos Genéticos 32 4.1 Representação da Solução . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 População Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.5.1 1Px . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.2 2Px . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.5.3 Sx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.7 Sobrevivência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 Metodologia 41 5.1 Levantamento de dados . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2 Ambiente de desenvolvimento . . . . . . . . . . . . . . . . . . . . . 41 5.3 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.4 Banco de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.5 Análise de Eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.6 Testes do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Resultados e Discussões 50 7 Considerações Finais 59 7.1 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 A Dados coletados 64 B Autorização para divulgação dos dados da escola 65 C Interface Desenvolvida 66 LISTA DE FIGURAS 3.1 Exemplo de espaço de busca unidimensional definido por uma função de avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Fluxograma geral de um AG . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Fases iniciais do AG . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Ciclo do algoritmo genético . . . . . . . . . . . . . . . . . . . . . . . 27 3.5 Exemplo de crossover com um ponto de corte . . . . . . . . . . . . . 28 3.6 Exemplo de crossover com dois pontos de corte . . . . . . . . . . . . 29 3.7 Exemplo de crossover MPx com 4 pontos de corte utilizando uma máscara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.8 Exemplo de mutação . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1 Representação de uma solução . . . . . . . . . . . . . . . . . . . . . 32 4.2 Cruzamento causando inconsistência no horário . . . . . . . . . . . . 35 4.3 Cruzamento de indivíduos com um ponto de corte . . . . . . . . . . . 36 4.4 Cruzamento de indivíduos com dois pontos de corte . . . . . . . . . . 37 4.5 Cruzamento de indivíduos com número de pontos de corte aleatório . 38 4.6 Mutação com troca de valor de uma aula causando inconsistência no horário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.7 Mutação trocando encontro . . . . . . . . . . . . . . . . . . . . . . . 39 4.8 Mutação trocando slot . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.1 Interface da grade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Modelo do Banco de Dados da Aplicação . . . . . . . . . . . . . . . 44 5.3 Teste de eficiência da primeira implementação da função de cruzamento 46 5.4 Teste de eficiência da segunda implementação da função de cruzamento 47 5.5 Teste de eficiência da terceira implementação da função de cruzamento 48 6.1 Resultado geral dos 15 testes realizados . . . . . . . . . . . . . . . . 51 6.2 Teste 1 (3a repetição), taxa de mutação = 0.1% 6.3 Teste 2 (2a repetição), taxa de mutação = 1% . . . . . . . . . . . . 52 . . . . . . . . . . . . . 52 6.4 Teste 3 (2a repetição), taxa de mutação = 10% . . . . . . . . . . . . . 52 6.5 Teste 4 (1a Repetição), Parte da população selecionada para cruzamento = 25% . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 53 Teste 5 (1a Repetição), Parte da população selecionada para cruzamento = 50% . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.7 Teste 6 (1a Repetição), Método de seleção = uniforme . . . . . . . . 54 6.8 Teste 7 (3a Repetição), Método de seleção = roleta . . . . . . . . . . 54 6.9 Teste 8 (2a Repetição), Método de crossover = 1Px . . . . . . . . . . 54 6.10 Teste 9 (1a Repetição), Método de crossover = Sx . . . . . . . . . . . 55 6.11 Teste 10 (3a Repetição), Método de mutação = Trocar Slot . . . . . . 55 6.12 Teste 11 (2a Repetição), Método de mutação = Trocar Encontro Heurístico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.13 Teste 12 (3a Repetição), Método de sobrevivência = somente filhos 6.14 Teste 13 (1a Repetição), Método de sobrevivência = melhores 55 . 56 . . . . 56 6.15 Teste 14 (2a Repetição), Método de sobrevivência = elitismo de tamanho 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.16 Teste 15 (1a Repetição), Método de sobrevivência = elitismo de tamanho 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 C.1 Interface do cadastro de usuário . . . . . . . . . . . . . . . . . . . . 66 C.2 Interface do cadastro de professor . . . . . . . . . . . . . . . . . . . 67 C.3 Interface da lista de professores cadastrados . . . . . . . . . . . . . . 68 C.4 Interface de cadastro de aulas . . . . . . . . . . . . . . . . . . . . . . 69 C.5 Interface para definição das restrições dos professores . . . . . . . . . 70 C.6 Interface onde define-se os parâmetros do algoritmo genético para criação do horário . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 C.7 Interface que mostra o horário criado . . . . . . . . . . . . . . . . . . 72 LISTA DE TABELAS 4.1 Pesos aplicados a cada critério infligido . . . . . . . . . . . . . . . . 34 5.1 Configuração padrão = teste número 3 . . . . . . . . . . . . . . . . . 49 5.2 Configuração das máquinas . . . . . . . . . . . . . . . . . . . . . . . 49 6.1 Configurações dos testes realizados e resumo dos resultados encontrados 50 6.2 Configurações Propostas . . . . . . . . . . . . . . . . . . . . . . . . 57 7.1 Comparação dos resultados do software e do especialista . . . . . . . 59 A.1 Distribuição de aulas do turno da manhã . . . . . . . . . . . . . . . . 64 12 1 INTRODUÇÃO 1.1 Contextualização Este trabalho esta ligado principalmente a Inteligência Artificial, área de pesquisa da Ciência da Computação definida de diversas formas. Dentre as definições existentes a mais próxima deste estudo é, segundo Russell e Norvig (2009 apud BELLMAN, 1978), “[A automação de] atividades que associamos com o pensamento humano, tais como tomada de decisões, resolução de problemas, a aprendizagem...”, uma vez que parte de um processo realizado por pessoas será automatizado. Neste caso o problema abordado trata-se do Timetabling escolar. O timetabling pode ser descrito como o problema de se alocar o encontro de determinados recursos dentro de um determinado espaço de tempo. Assim o timetabling escolar determina horários para que classes e professores se encontrem durante a semana, sem que um professor ou uma classe tenham duas aulas ao mesmo tempo. Diversas restrições podem ser impostas no momento de gerar os horários, por exemplo, casos onde um professor não pode dar aula em determinado dia ou quando certa aula deve ser ministrada em um determinado dia. Estas restrições dificultam o problema em questão. 1.2 Motivação Conforme Schaerf (1999), “a solução manual do problema geralmente requer muitos dias de trabalho”, assim mesmo em escolas pequenas, a tarefa de definir a grade de horários dos alunos é um trabalho muito árduo, podendo consumir dias de trabalho de um profissional experiente. Logo existe uma demanda por métodos e ferramentas capazes de auxiliar na busca por soluções desse problema. 13 1.3 Objetivos Este projeto visa solucionar o timetabling escolar, desenvolvendo uma aplicação capaz de auxiliar na resolução destes problemas. Entre os objetivos específicos pretende-se: 1. Dar continuidade aos trabalhos de Neto (2011) e Timóteo (2002); 2. Utilizar algoritmos genéticos para abordar o problema em questão; 3. Obter um software capaz de gerar boas soluções em tempo eficiente; 4. Disponibilizar o software, via web, para uso das escolas. Deve-se notar que Neto (2011) abordou o problema de geração horários universitário, que possui restrições diferentes do timetabling escolar. Timóteo (2002) abordou o timetabling escolar e ao final obteve uma aplicação desktop para abordar o mesmo. 14 2 TIMETABLING ESCOLAR Segundo Burke e Petrovic (2002 apud WREN, 1996) “timetabling é a alocação, sujeita a restrições, de determinados recursos em determinado espaço de tempo, de forma a satisfazer da melhor forma possível um conjunto de objetivos desejáveis”. Um exemplo deste tipo de problema é a criação do cronograma para um campeonato de futebol. É necessário definir datas para diversos times se enfrentarem, considerando-se os estádios disponíveis e outras limitações, como a impossibilidade de um time para determinada data. Este problema também é encontrado em escolas, definido por Kingston (2012) como timetabling escolar: associação de um grupo de recursos para determinados slots, pequenos períodos de tempo prontos para um determinado evento em uma timatable, depois que os possíveis espaços de tempo são determinados. De um ponto de vista mais genérico Birbas, Daskalaki e Housos (2009) definem timetabling escolar como “ a associação de um grupo de três elementos que consiste de professores, classes e aulas para determinados períodos de tempo de cada dia da semana, sujeito a restrições de tal forma que uma função custo é minimizada”. Este tipo de problema também faz-se presente nas escolas e universidades, quando a tarefa consiste em definir os horários em que as aulas serão oferecidas, neste caso, conforme Schaerf (1999), é chamado course timetabling. Ainda segundo Schaerf (1999), o problema do timetabling no contexto escolar pode ser dividido em três classes principais: School timetabling ou timetabling escolar : A programação semanal para todas as classes de uma escola, evitando o encontro de professores com duas classes ao mesmo tempo e vice-versa 15 Course Timetabling : A programação semanal para todas as aulas de um conjunto de cursos, evitando a sobreposição de cursos que possuem estudantes em comum Examination Timetabling : O agendamento de exames de um conjunto de cursos de uma universidade, evitando a sobreposição de exames de cursos que possuem estudantes em comum e espalhando os exames o máximo possível. Para definir o problema timetabling escolar, seguiremos, assim como Schaerf (1999), a terminologia e formulações apresentadas por Werra (1985). Werra (1985) formula o problema chamando-o de class-teacher model e para isso utilizou as seguintes definições: Classe: um conjunto de estudantes que seguem exatamente o mesmo programa. C = {c1 , ..., cm } Conjunto de m classes. T = {t1 , ...,tn } Conjunto de n professores. R = (ri j ) Matriz de tamanho m × n onde cada elemento ri j define o número de aulas entre a classe ci e o professor r j . Assume-se que todas as aulas têm a mesma duração, um período ou slot. Assim, dado um conjunto de p períodos deve-se associar cada aula a um destes períodos, de forma que nenhum professor (ou classe) seja estipulado para mais de uma aula no mesmo período. Define-se ainda X = (xi jk ), uma matriz m × n × p, que define os períodos onde professor e classe irão se encontrar. Nela xi jk = 1 se a classe ci e o professor t j se encontram no período k, caso contrário, xi jk = 0. A partir das definições anteriores, pode-se formular o problema timetabling escolar básico conforme a seguir: p ∑ xi jk = ri j k=1 (i = 1...m; j = 1...n) (2.1) 16 n ∑ xi jk <= 1 (i = 1...m; k = 1...p) (2.2) ∑ xi jk <= 1 ( j = 1...n; k = 1...p) (2.3) xi jk = 1 ou 0 ( j = 1...n; k = 1...p) (2.4) j=1 m i=1 A equação 2.1 afirma que em X o número total de aulas entre t j e ci deve ser igual a ri j , ou seja, verifica se o número de aulas entre cada classe e cada professor esta correto. As sentenças 2.2 e 2.3 verificam se as classes e os professores não têm mais de uma aula ao mesmo tempo. Enquanto 2.4 afirma que pode-se haver apenas uma aula entre uma classe e um professor em determinado período. Werra (1985) mostra que existe uma solução para o problema se e somente se m ∑ ri j <= p ( j = 1...n), i=1 n ∑ ri j <= p (i = 1...m) j=1 ou seja, só há uma solução para o problema se houver pelo menos um número de períodos igual ao número de aulas de cada classe e de cada professor. 2.1 Restrições Para cada escola há diversas restrições (constraints), ou indisponibilidades, que se impõem sobre as possíveis soluções. Segundo Burke e Petrovic (2002), as soluções se dividem em duas categorias: 17 Hard ou Fortes caso essas restrições não sejam satisfeitas a solução proposta é inválida Soft ou Leves é desejável que estas sejam cumpridas, porém caso não sejam satisfeitas a solução não deixa de ser válida. Schaerf (1999) mostra que caso o problema possua apenas restrições fortes, o mesmo torna-se um problema de busca, pois, todas as restrições devem sem satisfeitas, caso contrário a solução não seria válida. Ou seja, não havendo restrições leves as soluções válidas são igualmente satisfatórias, portanto, para solucionar o problema basta encontrar uma solução válida para o problema. Seguindo a ideia de Junginger (1986) pode-se redefinir Cn×p e Tm×p como matrizes binárias para representar os períodos onde professores e alunos estão disponíveis, assim se cik = 1 o aluno i está disponível no período k e se cik = 0 o aluno i está indisponível no período k. Substituindo as equações 2.2 e 2.3 do problema timetabling escolar básico, por equações capazes de definir as restrições de cada professor ou classe, formula-se o problema timetabling escolar com restrições conforme a seguir: p ∑ xi jk = ri j (i = 1...m; j = 1...n) (2.5) (i = 1...m; k = 1...p) (2.6) ( j = 1...n; k = 1...p) (2.7) k=1 n ∑ xi jk <= tik j=1 m ∑ xi jk <= c jk i=1 xi jk = 1 ou 0 ( j = 1...n; k = 1...p) (2.8) Conforme Werra (1985), além das restrições, há também as pré-associações, quando encontros entre determinados professores e classes são pré-estabelecidos. 18 Assim, Werra (1985) trata restrições utilizando pré-associações, por exemplo, se t j está indisponível no período k associa-se o mesmo a uma classe falsa, e de forma similar pode-se tratar a indisposição de um classe. Schaerf (1999) afirma que com a inserção de restrições leves, o problema adquire um caráter de otimização, dessa forma é necessária a criação cuidadosa de uma função de avaliação, capaz de avaliar a satisfabilidade de uma determinada solução. 2.2 Complexidade É importante estudar a complexidade dos problemas, pois isso permite classificálos quanto ao recursos, tanto de tempo quanto de memória, que eles podem consumir para serem solucionados. Assim têm-se uma ideia inicial de quais técnicas podem ou não ser utilizadas para abordá-lo. Sipser (2012) mostra que os problemas se dividem em diversas classes, entre elas as principais são: P: classe dos problemas que podem ser resolvidos em tempo polinomial; NP: a classe dos problemas que podem ser verificados em tempo polinomial, isto é, dado uma entrada, existe um verificador que, em tempo polinomial, é capaz de dizer se a entrada resolve ou não o problema dado; NP-Hard ou NP-Difícil: classe dos problemas, onde todos os problema podem ser reduzidos em tempo polinomial para eles, mesmo se estes não estiverem na classe NP; NP-Completo: intersecção entre NP e NP-Hard. Em relação ao timetabling problem, TTP, Even, Itai e Shamir (1976) afirmam que é fácil notar que TTP ∈ NP, isso é simples pois para verificar uma solução de TTP basta analisar se todas as restrições fortes foram cumpridas, o que indica 19 que a solução é válida. Assim Even, Itai e Shamir (1976) ainda reduziu um problema da classe NP-Difícil para TTP, mostrando que TTP ∈ NP-Difícil. Portanto como TTP ∈ NP e TTP ∈ NP-Hard conclui-se que TTP ∈ NP-Completo uma vez que NP-Completo=NP∩NP-Hard. 20 3 ALGORITMOS GENÉTICOS Para compreender as técnicas que podem ser utilizadas para abordar o problema é importante a absorção de alguns conceitos. A Figura 3.1 mostra que um espaço de busca, onde cada indivíduo possui um grau de aptidão dado pela função de avaliação. Deve-se notar que o objetivo de um algoritmo de busca é chegar ao máximo global do espaço de busca. avaliação (fitness) Máximo Local Liso Máximo Global Platô Máximo Local Estado Atual espaço de busca Figura 3.1: Exemplo de espaço de busca unidimensional definido por uma função de avaliação Schaerf (1999) lista algumas técnicas que podem ser utilizadas para abordar o timetabling escolar. Entre elas encontram-se: Redução para Coloração de grafos: pode-se reduzir o problema para coloração de grafos, problema de atribuir “cores” aos elementos de um grafo sujeita a certas restrições, por exemplo, duas arestas adjacentes não podem ter a mesma cor. Esta redução é interessante pois, entre os problemas relacionados à grafos, este é um dos mais antigos e bem estudados e consequentemente possui técnicas consolidadas para abordá-lo; Algoritmos genéticos: abordagem utilizada nesse trabalho, que trabalha sobre um conjunto de soluções, inspirada no processo de evolução; 21 Têmpera Simulada: semelhante à técnica subida de encosta, um loop simples que continuamente se move em direção de soluções melhores para o problema até atingir um pico. A têmpera simulada permite evitar a conversão prematura para um máximo local, permitindo que o algoritmo se mova para soluções piores que a atual quando a “temperatura” do algoritmo estiver alta. Programação Lógica: é possível utilizar programação lógica, a principal vantagem dessa abordagem é possibilidade de expressar as restrições do problema de forma declarativa; Constraint-based: nessa técnica uma penalidade é associada com cada restrição e o objetivo é encontrar uma associação das varáveis do problema que minimizem a penalidade total; Busca Tabu: semelhante à subida de encosta, porém mantêm uma lista tabu de k vértices já visitados, os quais não podem ser revisitados, evitando que a busca fique restrita em apenas uma parte do espaço de soluções. Há outras alternativas, como a utilização de algoritmos inspirados no sistema imune, abordagem principal do trabalho de Neto (2011), porém, esse trabalho está focado na meta-heurística Algoritmos Genéticos. Conforme Davis (1999), Algoritmos Genéticos, ou AGs, simulam o processo de evolução das espécies no computador. Esse método foi inventado por John Holland nos anos 70, inspirado no processo de evolução biológica, onde um indivíduo mais apto ao ambiente possui maior probabilidade de sobrevivência. Essa classe de algoritmos é muito utilizada em problemas que podem ser resolvidos com técnicas de aprendizado de máquina ou otimização. AGs são muito utilizados para abordar problemas difíceis, apesar de serem estocásticos, isto é, geralmente apresentam resultados diferentes a cada execução. Esse método apresenta bons resultados devido a característica de trabalhar sobre 22 diversas soluções, pois dessa forma possui menor probabilidade de converter para um pico local. Segundo Mitchell (1996) a maioria dos métodos chamados de AGs têm pelo menos os seguintes elementos em comum: População: consiste de um conjunto de cromossomos (indivíduos); Seleção: escolhe indivíduos para a etapa de cruzamento de acordo com a aptidão dos mesmos; Cruzamento: produz novos descendentes; Mutação: insere modificações aleatórias nos descendentes. 3.1 Funcionamento Geral do AG O fluxograma da Figura 3.2 mostra o funcionamento geral dos AGs. Nota-se, conforme essa figura, que os processos se repetem a cada nova iteração. Inicialmente a avaliação determina a aptidão de cada indivíduo da população, a seguir, a seleção determina quais participarão da reprodução, que cria uma nova população, que pode sofrer mutação após este processo. Por fim a etapa de sobrevivência define quais indivíduos deverão compor a nova população. Uma das principais características dos AGs é a sobrevivência das características dos mais aptos, dada no processo de seleção. Os passos da Figura 3.2 serão detalhados nas demais subseções deste capítulo, na Figura 3.3 pode-se ver mais detalhes como é realizada a parte sequencial do algoritmo, enquanto a Figura 3.4 mostra melhor o ciclo do algoritmo. 3.2 Definições e nomenclatura Conforme Lobo (2005) a nomenclatura adotada para o estudo de AGs é composta pelos termos: 23 Início População Inicial Avaliação Inicial Sobrevivência Parada? sim Fim não Avaliação Seleção Mutação Reprodução Figura 3.2: Fluxograma geral de um AG Cromossomo, genótipo ou indivíduo: cadeia de caracteres, representando alguma informação relativa às variáveis do problema. Cada cromossomo representa, deste modo, uma solução do problema; Gen ou gene: é a unidade básica do cromossomo. Cada cromossomo tem certo número de genes, cada um descrevendo certa variável do problema. Podem ser do tipo binário, inteiro ou real; População: conjunto de cromossomos ou soluções; Fenótipo: cromossomo decodificado; Geração: o número da iteração que o algoritmo genético executa para gerar uma nova população; Operações genéticas: operações que o algoritmo genético realiza sobre cada um dos cromossomos; 24 Espaço de busca ou região viável: o conjunto, espaço ou região que compreende as soluções possíveis ou viáveis do problema a ser otimizado. Deve ser caracterizado pelas funções de restrição, que definem as soluções viáveis do problema a ser resolvido; Função de avaliação, objetivo ou de aptidão: construída a partir dos parâmetros envolvidos no problema. Fornece uma medida da proximidade da solução em relação a um conjunto de parâmetros. A função de aptidão permite o cálculo da aptidão de cada indivíduo e fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser selecionado para reprodução; Aptidão ou Fitness: saída gerada pela função de avaliação para um indivíduo da população; 3.3 População Dado o espaço de busca do problema, Figura 3.3(a), a população é composta por um conjunto destes indivíduos, Figura 3.3(b), cada um destes codifica uma solução para o problema, ou seja, cada indivíduo pode ser visto como um ponto no espaço de busca das possíveis soluções e possui um grau de aptidão, Figura 3.3(c). Todo indivíduo possui um grau de aptidão (fitness ou evaluation), dado por uma função de avaliação, que permite comparar os indivíduos. — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — 0.5 — — — — — — — — — — — — — — — — — — — — — 0.5 — — — — — — — — — — — — — — — — — — — — — — 0.5 — 0.9 — — — — — — — — — — — — — — — — — — — — 0.1 — — — 0.1 0.7 0.4 0.1 — — — — — — — — — — — — — — — — — 0.6 0.4 — — — — — — — — — — — — — — — — — — — — — 0.2 — — — — — 0.1 — — — — — — — — — — — — — — — — — — — — — — — — — (a) Espaço de Busca (b) População Inicial Figura 3.3: Fases iniciais do AG (c) Avaliação Inicial 25 Deve-se notar, conforme Davis (1999) que a população tem um tamanho constante a cada iteração, logo após a fase de reprodução deve-se decidir quais indivíduos se mantêm para a próxima iteração. Pode-se trocar toda a população por uma nova população (AG geracional), ou pode-se escolher alguns membros para serem substituídos (AG steady-state). Blickle e Thiele (1995) descrevem a população como um conjunto de n potenciais soluções, ou indivíduos, P = { j1 , j2 , · · · , jn }, sendo que cada ji ∈ J onde J é o espaço de todas as soluções possíveis. 3.4 Avaliação A função de avaliação, também chamada de função objetivo ou função de adaptação, tem o intuito de ligar o AG ao problema abordado. Deve ser definida junto a um especialista no problema. A função de avaliação busca assimilar ao indivíduo um número com intuito de mensurar a aptidão do mesmo em relação ao problema, conforme Figura 3.3(c) logo, conforme Mitchell (1996), “O cálculo de aptidão traduz uma string x em um número real y e então avalia a função para aquele valor” Timóteo (2002) mostra que a avaliação dos indivíduos pode ser vista como a aptidão de determinado indivíduo em caso de problemas de otimização. Já em problemas com muitas restrições, funções baseadas em penalidades são mais comuns, ou seja, quanto menos penalidades, maior grau de aptidão do indivíduo. Blickle e Thiele (1995) mostram que o domínio da função de avaliação é composto pelo conjunto de soluções possíveis e que o contradomínio é composto pelo conjunto dos números reais, ou seja, f : J → R. Com finalidade de otimizar o processo de avaliação, Smith, Dike e Stegmann (1995) propuseram que o indivíduos herdassem o fitness dos pais. Dessa forma para os casos onde o processo de avaliação é muito caro, é interessante avaliar-se apenas parte da nova população enquanto o restante é avaliado con- 26 forme o fitness de seus pais. Assim Smith, Dike e Stegmann (1995) propõem dois métodos de herança. Herança média: O indivíduo recebe o fitness médio de seus pais Herança proporcional: A média é ponderada em relação a quantSemelhanteidade de material genético que o indivíduo recebeu de cada pai. 3.5 Seleção Segundo Mitchell (1996), nesta etapa “seleciona-se os cromossomos da população para reprodução” o que gera um conjunto de pais, conforme Figura 3.4(b) onde os indivíduos selecionados estão destacados em vermelho. Sendo que o cromossomo com maior aptidão terá mais chances de ser selecionado. Brindle (1980) afirma que “o sucesso do algoritmo genético como uma técnica de busca adaptativa depende do balanço entre retenção histórica e da exploração”. Nota-se, portanto, que a população é utilizada como memória para manter as boas soluções e como espaço para testar novos indivíduos. Logo durante essa etapa deve-se evitar a seleção dos mesmos indivíduos, o que levaria a uma perda de variância da população, podendo levar o algoritmo a convergir para um mínimo local. Por outro lado, uma seleção completamente aleatória poderia descartar os indivíduos mais aptos da população. Há diversos métodos para realização da seleção, os principais, citados por Goldberg e Deb (1991), são: Seleção Uniforme: todos os indivíduos têm a mesma chance de serem escolhidos para cruzamento, portanto simplesmente escolhe uma amostra entre os pais; Seleção por Roleta Giratória: realiza um sorteio onde cada elemento da população tem probabilidade proporcional ao seu fitness de ser selecionado; 27 — — — — — — — — — — — — — — — — — — — — — — — — 0.5 — — — — — 0.5 — — — — — — 0.5 — 0.9 — — — — — — — — — — — — — — 0.5 — — — — — 0.5 — — — — — — — — — 0.5 — — — — 0.5 — — — — 0.5 — 0.9 — — — — — — 0.5 — 0.9 — — — — 0.1 — — — 0.1 0.7 0.4 0.1 0.1 — — — 0.1 0.7 0.4 0.1 0.1 — — — 0.1 0.7 0.4 0.1 — 0.6 0.4 — — — — — — 0.6 0.4 — — — — — — 0.6 0.4 — — — — — 0.2 — — — — — 0.1 — 0.2 — — — — — 0.1 — 0.2 — — — — — 0.1 — — — — — — — — — — — — — — — — — — — — — — — — — (a) Parada? (b) Seleção — — — — — — — — — — — — — — 0.5 — — — — — — 0.5 — — — — — — (c) Cruzamento — — — — — — — — — 0.5 — — 0.9 — — — — — — — 0.1 — — 0.8 0.5 — 0.5 — — 0.5 — — — — — — — — — 0.8 — — — — — 0.5 — — — — — — 0.5 — 0.9 — — — — — 0.5 — 0.9 — — — — — 0.1 — — — 0.1 0.7 0.4 0.1 0.1 — — — 0.1 0.7 0.4 0.1 0.1 — — — 0.1 0.7 0.4 0.1 0.4 — — — — — — 0.6 0.4 — — — — — — — 0.4 — — — — — — — — — 0.1 — 0.2 — — — — — 0.1 — — — 0.7 — — — — — — — 0.7 — — — — 0.6 0.2 — — — — — 0.1 — 0.2 — — — — — — — — — — — (e) Avaliação (d) Mutação (f) Sobrevivência Figura 3.4: Ciclo do algoritmo genético Seleção por Torneio: trabalha de forma um pouco diferente, ele sorteia pares que irão competir, assim o indivíduo com maior aptidão é escolhido para participar da etapa de cruzamento posteriormente, repete-se estas ações até ter o número de pais esperados; Seleção por Ranking: ordena os indivíduos, depois seleciona os indivíduos de forma que os primeiros possuem maior probabilidade de serem escolhidos. Este método é interessante quando há grandes diferenças entre o fitness dos indivíduos, dessa forma evita que os melhores dominem o momento da seleção e evita a perda de diversidade entre as soluções. Blickle e Thiele (1995) descrevem ainda outros métodos e mostra que a etapa de seleção é uma uma função,ω : Jn → Jn , cujo domínio e contradomínio é o conjunto das possíveis soluções J, recebendo n indivíduos e retornando o mesmo número de indivíduos. 28 3.6 Cruzamento Timóteo (2002) afirma que “o crossover é a operação que realiza a troca genética entre os cromossomos, ou seja, aquela que irá combinar os genes dos indivíduos selecionados na etapa anterior (seleção) para gerar novos indivíduos”, conforme ilustrado na Figura 3.4(c) onde os filhos gerados estão destacados em verde. Esta etapa implementa a recombinação entre indivíduos, isto é, opera sobre um grupo de indivíduos (pais) combinando suas características para geração de novos indivíduos (filhos), para tanto troca segmentos dos pais. Dessa forma os filhos herdam parte das características de um pai e parte de outro. Espera-se que os novos indivíduos combinem as melhores características de seus pais. Este método é aplicado dividindo os genes de cada indivíduo e trocando-os de posição entre si, conforme exemplo mostrado na Figura 3.5. Pai 1 1 1 0 0 1 1 1 Pai 2 1 1 1 0 0 1 0 Filho 1 1 1 1 0 1 1 1 Figura 3.5: Exemplo de crossover com um ponto de corte Alguns operadores de crossover comuns na literatura são: Crossover com corte em 1 ponto (1Px): Neste caso escolhe-se um ponto de corte px e gera-se o primeiro filho com a parte a esquerda de px do primeiro pai e a parte a esquerda de px do segundo pai, conforme exemplificado na Figura 3.5. O segundo filho é gerado de forma semelhante; Crossover com corte em 2 pontos (2Px): Semelhante ao 1Px, porém este método usa dois pontos de corte conforme exemplificado na Figura 3.6; 29 Crossover com múltiplos pontos (MPx): Trata-se de uma generalização dos métodos 1Px e 2Px, este método funciona para qualquer número de pontos de corte. Uma forma para implementar este método é a criação de uma máscara que indica de qual pai o filho receberá cada gene, sendo que para gerar o segundo filho basta inverter a máscara. A Figura 3.7 ilustra o funcionamento desse método para 4 pontos. Crossover segmentado (Sx): Este método é semelhante ao MPx, porém possui número de pontos de corte variável, logo para cada cruzamento pode haver um número diferente de pontos de cruzamento. Pai 1 1 1 0 0 1 1 1 Pai 2 1 1 1 0 0 1 0 Filho 1 1 1 1 0 1 1 0 Figura 3.6: Exemplo de crossover com dois pontos de corte Máscara 1 2 2 1 1 2 1 Pai 1 1 1 0 0 1 1 1 Pai 2 1 1 1 0 0 1 0 Filho 1 1 1 1 0 1 1 1 Figura 3.7: Exemplo de crossover MPx com 4 pontos de corte utilizando uma máscara Blickle e Thiele (1995) definem o processo de cruzamento com a função Ξ : Jn → Jn , que assim como a etapa de seleção possui domínio e contradomínio no conjunto das possíveis soluções J, recebendo n elementos e retornando n elementos. 30 3.7 Mutação Conforme Mitchell (1996), o operador de mutação altera aleatoriamente algum dos genes de um indivíduo, dessa forma o filho que foi gerado na etapa de reprodução torna-se outro indivíduo conforme ilustrado na Figura 3.4(d) onde o indivíduo que sofreu mutação está destaco em azul. Trata-se da etapa seguinte ao cruzamento, onde cada indivíduo possui uma pequena probabilidade de sofrer alterações aleatórias. Um exemplo da aplicação deste método pode ser visto na Figura 3.8. Indivíduo 1 1 0 0 1 1 1 Indivíduo’ 0 1 0 0 1 1 1 Figura 3.8: Exemplo de mutação Esta etapa possui o objetivo de aumentar a diversidade genética das soluções, expandindo o espaço de busca. Trata-se de um método útil para evitar que os genes de um indivíduo dominem a população, o que evita a conversão para máximos locais. 3.8 Sobrevivência Após realizadas as etapas de seleção (onde escolhe-se um conjunto de pais), cruzamento e mutação (onde gera-se um conjunto de filhos), deve-se decidir, entre pais e filhos, quais indivíduos deverão compor a nova população procurando manter o tamanho da população constante. A Figura 3.4(f) ilustra o resultado dessa etapa As técnicas de substituição da população mais utilizadas são: Substituir toda a população: Nesse caso os filhos sobrepõem os pais e assim tornam-se os novos membros da população, porém esta estratégia pode levar a perda de indivíduos com bons genes. 31 Elitismo: esta estratégia visa impedir a perda dos melhores indivíduos, assim copia os melhores indivíduos para a próxima geração. 3.9 Condições de Término A primeira condição de término é o caso de se encontrar um indivíduo que satisfaça o problema, ou seja, a solução ótima. É possível ainda considerar um limite mínimo para considerar uma solução ótima, isto é, se o indivíduo esta próximo o bastante da solução ótima. Lobo (2005) cita outros critérios de parada, tais como: limite de gerações, estabilização da aptidão média ou da máxima e perda de diversidade da população. 32 4 ADAPTAÇÃO DO TIMETABLING ESCOLAR AOS ALGORITMOS GENÉTICOS O indivíduo do Timetabling Escolar não possui uma representação intuitiva por uma cadeia de bits, assim diversas adaptações foram realizadas para implementarse cada aspecto dos algoritmos genéticos, dada a representação escolhida para os indivíduos. A seguir descreve-se como foi esse processo de adaptação para os diversos operadores genéticos. 4.1 Representação da Solução Para representar a solução optou-se por uma matriz de dimensões igual ao número de turmas pelo número de slots. A Figura 4.1 ilustra uma solução para 3 turmas com 4 aulas divididas em dois dias. Slots 11 12 21 22 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 Figura 4.1: Representação de uma solução Para implementação utilizou-se a estrutura de mapeamento presente na linguagem Python, chamada dicionário. Nota-se que cada slot é um par (dia,horário). Assim dadas as chaves slot e turma sabe-se qual aula é ministrada, sendo que a aula carrega informações como disciplina e professor conforme a o modelo do banco de dados da Figura 5.2 da seção 5.4. 33 4.2 População Inicial Para criação da população deve-se gerar o horário aleatoriamente. Porém devido a forma como se realiza o cruzamento, optou-se por uma heurística que na escolha do slot para uma aula evita aqueles em que o professor encontra-se indisponível, procurando auxiliar no posterior desenvolvimento do algoritmo. 4.3 Avaliação Houve um cuidado durante a implementação da função de avaliação, uma vez que segundo a literatura, esta seria a função mais custosa do programa. Tratando-se de um problema de otimização, nesta função percorre-se toda a solução avaliando contabilizando as infrações aos critérios descritos a seguir. Colisão de professores Um professor ministra mais de uma aula no mesmo slot; Professor Indisponível Quando a aula está marcada para um horário em que o professor não pode ministrar aulas; Excesso de aulas no mesmo dia Quando extrapola-se o limite de aulas entre uma turma e um professor no mesmo dia. Critério importante para questões didáticas, pois evita que esta aula se torne massante para a classe e para o professor; Professor Indesejável Quando a aula está marcada para um horário em que o professor gostaria de não ministrar aulas; Excesso de dias do professor Quando um professor vai a escola mais dias que o necessário, por exemplo se um professor puder dar todas as suas aulas em 2 dias e ele tem de ir a escola 3 dias, isso representa 1 dia de excesso. Este critério procura condensar as aulas dos professores; 34 Janela Quando o professor tem um slot vago em seu horário, entre duas aulas do mesmo dia; A tabela 4.1 mostra os pesos definidos para cada critério. Estes pesos foram definidos segundo o conhecimento empírico dos funcionários da escola e após o início dos testes foi aprimorado. Tabela 4.1: Pesos aplicados a cada critério infligido Critério Professor Indisponível Colisão de professores Excesso de aulas no mesmo dia Professor Indesejável Excesso de dias do professor Janela Peso 20 15 10 8 5 1 Tipo Forte Forte Fraco Fraco Fraco Fraco Para calcular o fitness a função de avaliação foi definida, conforme Timóteo (2002), da seguinte forma f (i) = 100 , 100 + ∑nj=1 t j ∗ p j onde t j é o total de violações do critério j e p j o peso do mesmo. Dessa forma o valor do fitness retornado estará no intervalo ]0, 1]. 4.4 Seleção Neste trabalho, foram implementados três métodos de seleção: uniforme, roleta e torneio, para posteriormente verificar qual o mais adequado para a instância do problema tratada. Como este operador depende apenas do fitness dos indivíduos não foram necessárias adaptações. A quantidade e pais selecionados para cruzamento taxa de crossover. O método de seleção por Ranking não foi implementado devido a pequena diferença entre as aptidões dos indivíduos, causada pelo tipo de avaliação imple- 35 mentada. Com isso, as vantagens propostas por este método não seriam necessárias. 4.5 Cruzamento Foram implementados três métodos de cruzamento, para posteriormente verificar qual tem melhor comportamento dada a instância do problema em questão. As seções 4.5.1, 4.5.2 e 4.5.3, a seguir descrevem como cada um deles foi adaptado para os algoritmos genéticos. Para evitar a criação de soluções inconsistentes, evitou-se a inserção de um ponto de cruzamento no meio do horário de uma turma. A Figura 4.2 ilustra um caso deste tipo, nota-se que a turma 2A do filho possui um conjunto de aulas diferentes de seus pais. Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 (a) 1o Pai Slots 11 12 21 22 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (b) 2o Pai 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (c) 1o Filho Figura 4.2: Cruzamento causando inconsistência no horário Portanto optou-se por considerar a turma como um gene e dessa forma o cruzamento é realizado trocando as turmas (genes) dos pais. 36 4.5.1 1Px Conforme visto na seção 3.6 no cruzamento com um ponto de corte deve-se sortear um ponto e assim o primeiro filho é gerado com as turmas do primeiro pai a esquerda deste ponto e as turmas do segundo pai a direita do ponto. A Figura 4.3 ilustra a aplicação deste método, onde o primeiro filho é gerado com a turma 1A do primeiro pai e as demais do segundo pai. Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 (a) 1o Pai Slots 11 12 21 22 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (b) 2o Pai 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (c) 1o Filho Figura 4.3: Cruzamento de indivíduos com um ponto de corte 4.5.2 2Px O cruzamento com dois pontos de corte sorteia dois pontos, assim o primeiro filho é gerado com as turmas do primeiro pai a esquerda do primeiro corte e a direita do segundo, além das turmas do segundo pai entre os pontos de corte. A Figura 4.4 ilustra a aplicação deste método, onde o primeiro filho é gerado com a turma 1A e 3A do primeiro pai e a turma 2A do segundo pai. 37 Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 (a) 1o Pai Slots 11 12 21 22 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (b) 2o Pai 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A ING Prof 1 GEO Prof 4 MAT Prof 2 MAT Prof 3 (c) 1o Filho Figura 4.4: Cruzamento de indivíduos com dois pontos de corte 4.5.3 Sx Este método possui um número aleatório de pontos de corte, portanto optou-se por definir-se a forma de cruzamento através de uma máscara. Assim para cada turma sorteia-se um dos pais para receber o respectivo gene, formando-se assim a máscara que define a próxima geração. A Figura 4.5 ilustra a aplicação deste método, onde o primeiro filho é gerado de acordo com a máscara sorteada. Para criar o segundo filho basta inverter a máscara. 4.6 Mutação A mutação de cada indivíduo depende da taxa de mutação, assim para cada indivíduo sorteia-se um número entre 0 e 1, se o mesmo for menor que a taxa de mutação aplica-se o operador no indivíduo em questão. Foram implementados três métodos de mutação Trocar Encontro, Trocar Slot e Trocar Encontro Heurístico para 38 Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 (a) 1o Pai Slots 11 12 21 22 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 1A ING Prof 1 GEO Prof 4 HIST Prof 5 RED Prof 2 Turmas 2A PORT Prof 2 PORT Prof 2 MAT Prof 3 MAT Prof 3 3A MAT Prof 3 MAT Prof 3 ING Prof 1 GEO Prof 4 (b) 2o Pai 3A MAT Prof 2 MAT Prof 3 ING Prof 1 GEO Prof 4 Turma Pai Selecionado 1A 2 2A 1 3A 2 (d) Máscara (c) 1o Filho Figura 4.5: Cruzamento de indivíduos com número de pontos de corte aleatório posteriormente verificar qual deles é mais eficiente para a instância do problema tratada neste trabalho. Nota-se que não se pode simplesmente mudar o valor de uma aula, isso causaria uma inconsistência no horário, conforme Figura 4.6, logo optou-se pela troca de posição dos genes. Mesmo a troca de posição possui limitações, sempre deve-se trocar as aulas de uma mesma turma. Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 (a) Indivíduo 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 GEO Prof 4 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 (b) Indivíduo’ Figura 4.6: Mutação com troca de valor de uma aula causando inconsistência no horário 39 Troca de Encontro: Sorteia uma turma que deverá sofrer mutação, em seguida troca a posição de duas aulas dessa turma,como ilustrado na Figura 4.7; Troca de Slot: Sorteia dois slots, em seguida troca-se as aulas de todas as turmas entre estes slots. A Figura 4.8 mostra como este método foi implementado; Troca de Encontro Heurístico: procurando atacar alguns dos problemas envolvidos no timetabling escolar, implementou-se este método semelhante ao troca de encontro simples. Após definir a primeira aula a ser realocada procura-se uma posição em que o professor esteja disponível, procurando assim evitar o surgimento de uma infração ao critério professor indisponível. Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 (a) Indivíduo 1A HIST Prof 5 GEO Prof 4 ING Prof 1 RED Prof 2 Turmas 2A MAT Prof 3 MAT Prof 3 GEO Prof 4 PORT Prof 2 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 (b) Indivíduo’ Figura 4.7: Mutação trocando encontro Slots 11 12 21 22 1A HIST Prof 5 RED Prof 2 ING Prof 1 GEO Prof 4 Turmas 2A MAT Prof 3 MAT Prof 3 PORT Prof 2 PORT Prof 2 (a) Indivíduo 3A ING Prof 1 GEO Prof 4 MAT Prof 3 MAT Prof 3 Slots 11 12 21 22 1A HIST Prof 5 GEO Prof 4 ING Prof 1 RED Prof 2 Turmas 2A MAT Prof 3 PORT Prof 2 PORT Prof 2 MAT Prof 3 (b) Indivíduo’ Figura 4.8: Mutação trocando slot 3A ING Prof 1 MAT Prof 3 MAT Prof 3 GEO Prof 4 40 4.7 Sobrevivência Foram implementados três métodos de sobrevivência, para posteriormente análise de qual deles obteria melhores resultados. Somente filhos: nesse caso apenas os filhos gerados sobrevivem, substituindo os pais independente se forem melhores ou piores que os mesmos; Elitismo: nesse caso apenas os filhos gerados sobrevivem, porém mantém-se os n melhores entre pais e filhos para evitar que um pai com bom fitness seja descartado. Nesse caso n define o tamanho da elite; Somente melhores: nesse caso apenas os melhores indivíduos sobrevivem, assim agrupa-se a população de pais e filhos em um conjunto de candidatos e escolhe os melhores entre estes. Trata-se do método de elite com tamanho igual ao conjunto de pais. 41 5 METODOLOGIA A implementação deste trabalho foi dividida em diversas etapas. A seguir descrevese como foi realizado o levantamento do requisitos e dos dados relacionados, além das ferramentas e métodos utilizados durante a etapa de codificação. Ao final descreve-se como foram realizados os testes e como os mesmos foram definidos. 5.1 Levantamento de dados Foi utilizado um exemplo real, no caso, a escola em questão é a Escola Estadual Dona Rita Amélia de Carvalho, localizada no município de Santa Rita de Caldas - MG. A mesma possui dois turnos com diferentes turmas. Foram realizadas entrevistas com os responsáveis pela escola para levantamento dos exemplos necessários e dos requisitos específicos presentes na geração de um bom horário para a escola em questão. Após este levantamento decidiu-se utilizar o problema do horário da manhã por possuir mais turmas e consequentemente representar um desafio maior para a escola, tornando-se assim um problema mais relevante. Esta distribuição de aulas encontra-se no apêndice A, autorização para divulgação dos dados esta disponível no apêndice B. 5.2 Ambiente de desenvolvimento A maioria das ferramentas foram escolhidas considerando-se o domínio da equipe de desenvolvimento sobre as mesmas. Assim o software foi desenvolvido no sistema operacional Ubuntu 12.041 , utilizando ferramentas de software livre para sua 1 http://www.ubuntu.com/ 42 implementação, tais como o editor de texto Kate2 entre outras. Por fim foi utilizada a linguagem de alto nível e orientada a objetos Python 2.73 . Após realização das entrevistas notou-se a necessidade de uma interface intuitiva para realização do cadastro do problema por parte dos próprios membros da escola. Para tanto optou-se pela criação de um site. Assim foi utilizado o Django 1.3.14 , um framework para desenvolvimento web de alto nível desenvolvido em Python. Optou-se por esta ferramenta por utilizar a linguagem que já estava sendo utilizada no projeto e por ser uma ferramenta de código livre sob a licença BSD5 . 5.3 Interface Para desenvolvimento da interface foram utilizados os templates do Django em conjunto com o framework de front-end Bootstrap v2.3.26 , que encontra-se sob a licença Apache v2.0 7 . Este processo consumiu mais tempo do que o esperado, principalmente devido a inexperiência da equipe. Foram realizados pequenos testes de interface, onde foi solicitado aos usuários que realizassem algumas tarefas no software, solicitando ao mesmo que apresentasse oralmente os comentários relacionados a interface. Tomando nota das dificuldades dos usuários, fez-se um levantamento das principais falhas da interface, que foram corrigidas a seguir. Como este não é o foco deste trabalho não foi dedicado mais tempo a esta tarefa. A Figura 5.1 mostra a principal parte do software, onde define-se detalhes da instância do problema, como a distribuição de aulas de cada turma e as res2 http://kate-editor.org/ 3 http://www.python.org/ 4 https://www.djangoproject.com/ 5 https://github.com/django/django/blob/master/LICENSE 6 http://getbootstrap.com/2.3.2/ 7 http://www.apache.org/licenses/LICENSE-2.0 43 trições de horário de cada professor, além de permitir efetivamente a criação do horário. Figura 5.1: Interface da grade Mais figuras da interface desenvolvida podem ser vistas no apêndice C. 5.4 Banco de dados O banco de dados utilizado no projeto foi o SQLite8 , por ser o mais simples de ser utilizado. Porém como o Django é muito bem modularizado, o processo de migração para um novo banco de dados pode ser realizado de forma simples, caso haja necessidade. A Figura 5.2 mostra como o banco de dados foi modelado para a aplicação criada. 8 http://www.sqlite.org/ 44 professor idProfessor INT 1 nome VARCHAR(45) label VARCHAR(45) grade usuario 1..* idusuario INT idGrade INT 1 escola VARCHAR(45) nome VARCHAR(45) 1 1..* Indexes usuario_idusuario INT Indexes dias INT auladia INT 1 1 1..* 1 usuario_idusuario INT 1..* habilitacao idHabilitacao INT professor_idProfessor INT Indexes disciplina 1..* 1 turno VARCHAR(45) 1 idDisciplina INT 1 1 nome VARCHAR(45) disciplina_idDisciplina INT 1 Indexes label VARCHAR(45) usuario_idusuario INT Indexes 1..* turma 1..* aula idAula INT quantidade INT professor_idProfessor INT classe_idClasse INT 1 1..* grade_idGrade INT 1..* 1 saida encontro Indexes idEncontro INT 1..* 1..* 1 idSaida INT grade_idGrade INT aula_idAula INT slot_idSlot INT 1..* Indexes saida_idSaida INT restricao Indexes idRestricao INT tipo INT nome VARCHAR(45) Indexes 1..* disciplina_idDisciplina INT 1..* idClasse INT 1..* 1..* slot_idSlot INT slot professor_idProfessor INT 1 Indexes idSlot INT horario INT 1 dia INT grade_idGrade INT Indexes Figura 5.2: Modelo do Banco de Dados da Aplicação Grade representa a instancia do problema Um professor está ligado a uma disciplina apenas pelas aulas, portanto ele pode ministrar diversas disciplinas No modelo da Figura 5.2 deve-se notar que, ao acessar o software, o Saída pode armazenar diversas soluções para uma grade Encontro define horarios para as aulas Uma saida possui diversos encontros usuário só tem acesso aos seu objetos, por isso as tabelas grade, professor e disciplina possuem o id do usuário, assim os demais objetos são filtrados em função destas tabelas. A entrada do problema é dada através da tabela grade, assim dado o id de uma grade é possível carregar a respectiva distribuição de aulas. Uma grade possui um conjunto de turmas e cada turma possui um conjunto de aulas que 45 definem quais professores deverão ministrar quais disciplinas para aquela turma, além da quantidade de aulas. Deve-se notar que um professor pode ministrar mais de uma disciplina. Além disso, uma disciplina pode ser ministrada por mais de um professor, estas relações são implementadas pela tabela habilitacao. Como a quantidade de dias letivos e o número de aulas por dia pode variar entre as escolas, cada grade possui um conjunto de slots, além disso se um professor ministra aulas em uma determinada grade deve-se criar uma restrição entre o professor e cada um dos slots da grade em questão que indica a disponibilidade do professor naquele slot, a qual pode variar entre 0,1 e 2 que representam “Disponível”, “Indesejável” e “Inviável” respectivamente. Com intuito de facilitar a execução de testes, cada grade pode ter mais de uma saída, sendo que a saída é definida por um conjunto de encontros e cada encontro é uma relação entre uma aula e um slot. Nota-se que uma aula deve ter tantos encontros quanto a quantidade de aulas que ela define. 5.5 Análise de Eficiência Foram realizados testes para verificar a eficiência das funções do software desenvolvido. O primeiro problema encontrado, naturalmente, foi a lentidão do acesso ao banco de dados, assim optou-se por carregar todos os dados relacionados ao problema a ser abordado antes do processamento, evitando acessos ao banco de dados durante a execução do algoritmo. Ainda procurando evitar excesso de acessos ao banco de dados, optouse por não sincronizar as soluções de cada população, isto é, somente a solução final do algoritmo é sincronizada com o banco de dados. Esta abordagem possui a vantagem de aumentar a velocidade do software, porém, caso haja um problema com o mesmo a melhor solução encontrada provavelmente seria perdida. 46 Analisando o tempo gasto por cada função, conforme exemplificado pelas figuras 5.3, 5.4 e 5.5, que mostram quanto tempo cada função gastou a cada iteração do algoritmo, percebe-se que a função de cruzamento é a que toma mais tempo. Isso foi diferente do esperado, uma vez que a literatura afirma que a função de avaliação é a mais custosa nos algoritmos genéticos. Assim reimplementou-se a função de cruzamento. A segunda implementação, Figura 5.4, obteve um resultado mais satisfatório que a implementação original, Figura 5.3. Page One 12 mutacao fitnessTotal sobrevivencia crossover selecao avaliacao 10 8 6 4 2 00 10 20 30 40 Figura 5.3: Teste de eficiência da primeira implementação da função de cruzamento 50 47 Page One 4.0 mutacao fitnessTotal sobrevivencia crossover selecao avaliacao 3.5 3.0 2.5 2.0 1.5 1.0 0.5 0.00 10 20 30 40 50 Figura 5.4: Teste de eficiência da segunda implementação da função de cruzamento A terceira implementação da função de cruzamento, Figura 5.5, obteve um resultado semelhante ao inicial optando-se assim pela segunda implementação. Não foram realizadas novas implementações para as demais funções uma vez que a função de crossover mostrou-se o gargalo deste projeto e o objetivo deste é encontrar uma heurística para tratar o timetabling escolar e não um estudo relacionado a otimização de algoritmos. 48 Page One 12 mutacao fitnessTotal sobrevivencia crossover selecao avaliacao 10 8 6 4 2 00 10 20 30 40 50 Figura 5.5: Teste de eficiência da terceira implementação da função de cruzamento 5.6 Testes do Algoritmo Quanto ao algoritmo genético, conforme visto anteriormente, há um grande número de parâmetros que deve-se configurar para definir o comportamento do algoritmo. Assim fora realizados diversos testes repetido-se 3 vezes para cada configuração proposta. Inicialmente procurou-se de forma intuitiva, com a realização de pequenos testes, por uma configuração que poderia ser a ideal do algoritmo. Assim definiuse esta como a configuração padrão, conforme a Tabela 5.1. 49 Tabela 5.1: Configuração padrão = teste número 3 Parâmetro Alterado Taxa de mutação População selecionada para crossover Método de seleção Método de crossover Método de mutação Método de Sobrevivência Valor 10% 75% Torneio 2Px Trocar Encontro Elitismo, tamanho da elite = 1 A seguir criou-se uma série de novas configurações baseadas nesta configuração padrão. Realizando-se pequenas alterações na mesma obteve-se 14 novas configurações que podem ser vistas na Tabela 6.1, na seção 6. Os testes foram realizados no laboratório do Departamento de Ciência da Computação da Universidade Federal de Lavras, utilizando-se 15 máquinas com as configurações da tabela 5.2. Cada máquina executou uma das configurações três vezes. Tabela 5.2: Configuração das máquinas Característica Processador Memória Sistema Operacional Valor Intel Core i3-2100 3.10GHz 8 Gigabytes Ubuntu 10.04 LTS Com intuito de posteriormente comparar os resultados obtidos, optou-se por utilizar um limite de tempo de vinte horas como critério de parada. Consequentemente as execuções obtiveram um total de gerações final diferente, porém isso não influencia na análise dos resultados, pois espera-se que o algoritmo atinja um resultado em tempo viável, logo este é um critério importante para determinar a eficiência do algoritmo. 50 6 RESULTADOS E DISCUSSÕES Aplicando a meta-heurística do algoritmos genéticos, pretendia-se encontrar uma heurística eficaz para a geração de horários escolares, portanto foram realizados diversos testes conforme a Tabela 6.1 com intuito de definir quais métodos e parâmetros presentes nos AGs são mais adequados a instância do problema tratada. Na Tabela 6.1 pode-se ver ainda o melhor resultado de cada configuração e a média das três repetições. Tabela 6.1: Configurações dos testes realizados e resumo dos resultados encontrados # Parâmetro Alterado Valor 1 2 3 4 5 6 7 8 9 10 11 Taxa de Mutação Taxa de Mutação Taxa de Mutação População crossover População crossover Método de seleção Método de seleção Método de crossover Método de crossover Método de mutação Método de mutação 12 13 Método de sobrevivência Método de sobrevivência 14 Método de sobrevivência 15 Método de sobrevivência 0,1% 1% 10% 25% 50% Aleatório Roleta 1Px Sx Trocar Slot Trocar Encontro Heurístico Tomente Filhos Somente Melhores Elitismo, tamanho 3 Elitismo, tamanho 5 Melhor Fitness 0,198412698 0,401606426 0,41322314 0,440528634 0,540540541 0,465116279 0,507614213 0,537634409 0,534759358 0,094250707 0,178571429 Fitness Médio 0,184017395 0,383612751 0,385830893 0,424794376 0,512257896 0,446831529 0,498521223 0,501171469 0,522841216 0,093177038 0,168545414 0,078864353 0,591715976 0,077125116 0,562420651 0,495049505 0,457010623 0,487804878 0,47178037 A Figura 6.1 mostra o resultado final de todos testes, onde para cada teste de 1 a 15, vê-se o fitness da solução encontrada em cada uma das três execuções. Destaca-se os resultados do teste número 13, melhor resultado encontrado até então. 51 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 0 2 4 6 8 10 12 14 16 Figura 6.1: Resultado geral dos 15 testes realizados A seguir é realizada uma análise do comportamento das diversas configurações testadas. Os gráficos mostram a relação entre a geração e o fitness da população. Optou-se por analisar o comportamento da melhor repetição de cada configuração. O Teste 1, Figura 6.2, mostra que uma taxa de mutação pequena 0,1% gera uma taxa de crescimento muito pequena, sendo inviável a utilização da mesma. Enquanto o Teste 2, Figura 6.3, mostra que a taxa de 1% gera uma boa taxa de crescimento e mantém a média alta, próxima ao melhor indivíduo. Entretanto, este fator pode gerar uma domínio de determinados genes sobre a população o que implica em uma perda de variedade de genes, de forma a perder o potencial do espaço de busca. O Teste 3, Figura 6.4, com taxa de mutação de 10%, mostra que uma taxa de mutação maior consegue atingir uma taxa de crescimento semelhante a do Teste 2, porém a média não apresenta o mesmo crescimento aumentando o desvio padrão. Supõe-se que a diversidade de soluções mantém-se alta pelo desvio padrão 52 0,25 0,2 0,15 Melhor Fitness Fitness Médio 0,1 Desvio Padrão 0,05 0 0 2000 4000 6000 8000 10000 12000 Figura 6.2: Teste 1 (3a repetição), taxa de mutação = 0.1% 0,45 0,4 0,35 0,3 0,25 Melhor Fitness 0,2 Fitness Médio 0,15 Desvio Padrão 0,1 0,05 0 0 2000 4000 6000 8000 10000 12000 Figura 6.3: Teste 2 (2a repetição), taxa de mutação = 1% apresentado mantendo-se assim um espaço de busca mais amplo que o Teste 2 que possui um desvio padrão pequeno. 0,45 0,4 0,35 0,3 0,25 Melhor Fitness 0,2 Fitness Médio 0,15 Desvio Padrão 0,1 0,05 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.4: Teste 3 (2a repetição), taxa de mutação = 10% Variou-se a taxa de crossover, testes 4 (Figura 6.5), 5 (Figura 6.6), e 3 (Figura 6.4), com os valores 25%, 50%, e 75% respectivamente. A comparação entre os resultados obtidos deve ser realizada de maneira cautelosa, uma vez que o 53 critério de sobrevivência utilizado foi o elitismo de tamanho um, afinal isso implica em uma variação da parcela que a elite representa em relação a quantidade de pais. Analisando os resultados verifica-se que o melhor crescimento se deu com a taxa de crossover de 50%, mantendo ainda um desvio padrão maior, melhores tanto quanto os testes de 25% quanto os de 75%. 0,5 0,45 0,4 0,35 0,3 Melhor Fitness 0,25 Fitness Médio 0,2 Desvio Padrão 0,15 0,1 0,05 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.5: Teste 4 (1a Repetição), Parte da população selecionada para cruzamento = 25% 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 5000 10000 15000 20000 Figura 6.6: Teste 5 (1a Repetição), Parte da população selecionada para cruzamento = 50% Quanto aos métodos de seleção, observa-se que o método de seleção por roleta giratória, Figura 6.8, obteve resultados um pouco superiores em relação ao demais. Comparando-se as três execuções do Teste 6, com método de seleção uniforme, Figura 6.7, percebeu-se que o mesmo não possui um comportamento padrão e portanto não é possível tirar conclusões sobre o mesmo. O Teste 3 que utilizou o método de seleção por torneio, Figura 6.4, não obteve bons resultados. Quanto ao crossover nota-se um destaque da média dos resultados do método Sx (Figura 6.10), o qual possui ainda um crescimento um pouco mais rápido 54 0,5 0,45 0,4 0,35 0,3 Melhor Fitness 0,25 Fitness Médio 0,2 Desvio Padrão 0,15 0,1 0,05 0 0 2000 4000 6000 8000 10000 12000 Figura 6.7: Teste 6 (1a Repetição), Método de seleção = uniforme 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 2000 4000 6000 8000 10000 12000 Figura 6.8: Teste 7 (3a Repetição), Método de seleção = roleta que o método 1Px (Figura 6.9), além disso, apenas o mau desempenho do método 2Px (Figura 6.4) pode ser destacado. 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 2000 4000 6000 8000 10000 Figura 6.9: Teste 8 (2a Repetição), Método de crossover = 1Px Os métodos de mutação trocar slot (Figura 6.11) e trocar encontro heurístico (Figura 6.12) não conseguiram evoluir obtendo assim péssimos resultados. 55 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 2000 4000 6000 8000 10000 Figura 6.10: Teste 9 (1a Repetição), Método de crossover = Sx Portanto, isso sugere que o melhor método de mutação seja o trocar encontro simples cujo desempenho pode ser visto na Figura 6.4. 0,12 0,1 0,08 Melhor Fitness 0,06 Fitness Médio Desvio Padrão 0,04 0,02 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.11: Teste 10 (3a Repetição), Método de mutação = Trocar Slot 0,2 0,18 0,16 0,14 0,12 Melhor Fitness 0,1 Fitness Médio 0,08 Desvio Padrão 0,06 0,04 0,02 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.12: Teste 11 (2a Repetição), Método de mutação = Trocar Encontro Heurístico Após realização dos testes percebeu-se que os métodos de sobrevivência possuem grande influência sobre o desempenho do algoritmo. O método de so- 56 brevivência somente filhos (Figura 6.13) não conseguiu evoluir, o que indica a necessidade de se manter a elite para as próximas gerações. 0,08 0,07 0,06 0,05 Melhor Fitness 0,04 Fitness Médio 0,03 Desvio Padrão 0,02 0,01 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.13: Teste 12 (3a Repetição), Método de sobrevivência = somente filhos O método somente melhores (figura 6.14) obteve o melhor resultado, porém sua média entre as três execuções não se manteve muito acima em relação aos demais. Atribui-se esse comportamento ao fato de um método tão elitista não ter possibilidade de sair de máximos locais. Naturalmente seus resultados não podem ser desconsiderados, mas deve-se ter cuidado com a utilização deste método. 0,7 0,6 0,5 0,4 Melhor Fitness Fitness Médio 0,3 Desvio Padrão 0,2 0,1 0 0 2000 4000 6000 8000 10000 12000 Figura 6.14: Teste 13 (1a Repetição), Método de sobrevivência = melhores O método elitismo de tamanhos um, três e cinco (figuras 6.4,6.15 e 6.16 respectivamente) obtiveram resultados regulares, sendo que a elite de tamanho 3 obteve um resultado pouco superior aos demais. Notou-se uma falha quanto à forma de definição do tamanho da elite, pois ela não deve ter um valor fixo, como foi implementado, mas sim uma porcentagem da taxa de crossover. 57 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 2000 4000 6000 8000 10000 12000 14000 Figura 6.15: Teste 14 (2a Repetição), Método de sobrevivência = elitismo de tamanho 3 0,6 0,5 0,4 Melhor Fitness 0,3 Fitness Médio Desvio Padrão 0,2 0,1 0 0 5000 10000 15000 20000 Figura 6.16: Teste 15 (1a Repetição), Método de sobrevivência = elitismo de tamanho 5 Após análise destes primeiros 15 testes, propôs-se duas novas configurações, Tabela 6.2, para a realização de novos testes, obtendo resultados consideravelmente superiores aos encontrados anteriormente. Tabela 6.2: Configurações Propostas Parâmetros \ Configurações Taxa de mutação Taxa de crossover Método de seleção Método de crossover Método de mutação Método de Sobrevivência Repetição 1 Repetição 2 Repetição 3 Fitness Médio 1 10% 75% Roleta sx Trocar Encontro Elitismo, tamanho da elite = 5 0,657894736842 0,5555555556 0,6060606061 0,6065036328 2 10% 50% Roleta sx Trocar Encontro Elitismo, tamanho da elite = 1 0,62893081761 0,595238095238 0,540540540541 0,5882364845 58 Comparando-se os resultados obtidos pelas configurações propostas, Tabela 6.2, nota-se que ambas obtiveram um média próxima ao melhor resultado obtido anteriormente e que o melhor resultado encontrado até então foi obtido com a primeira destas configurações. 59 7 CONSIDERAÇÕES FINAIS 7.1 Conclusão Entre os resultados encontrados com a implementação deste trabalho de pesquisa, encontram-se: Software implementado: é possível utilizá-lo gratuitamente no endereço http: //tt.ginux.ufla.br/; Código-fonte disponível no endereço https://github.com/tdsimao/tt.git sob a licença GPL v2; Bases de dados esta disponível junto ao código fonte, além disso é possível ver a distribuição de uma das turmas na tabela A.1 no apêndice A Conclui-se que, para a instância em questão as melhores configurações encontrada são dadas na tabela 6.2, porém estes resultados ainda devem ser verificados com a execuções repetidas de testes com essas configurações, além da realização de alterações nos mesmos para comprovação da eficiência destes. O melhor resultado, possui onze janelas e cinco professores com excesso de dias, conforme a Tabela 7.1, assim consultou-se o responsável da escola que avaliou o horário como viável, porém este ainda não é o ideal, dada a importância do critério de excesso de dias, o mesmo atingiu uma solução com apenas quatro janelas e quatro excessos de dias. Tabela 7.1: Comparação dos resultados do software e do especialista Janelas Excesso de Dias Fitness Tempo Software 11 5 0,657894736842 20 horas Especialista 4 4 0,806451613 3 dias 60 Nota-se que o resultado do software pode ser utilizado como um horário inicial para o especialista, que poderia apenas aperfeiçoá-lo caso necessário, o que deverá economizar algum tempo para o mesmo. Deve-se notar que o algoritmo consegue resolver todas as colisões de professores e não marca aulas em horários inviáveis. Propõe-se então um préprocessamento da entrada com intuito de definir os dias de folga de cada professor, outra possibilidade é a alteração dos pesos da função de avaliação o que pode melhorar o desempenho do algoritmo. Ao analisar os resultados encontrados, o especialista mostrou que o critério relacionado ao excesso de professores é relativo, por exemplo, o caso onde um professor precisa ir quatro dias à escola ter que ir cinco é pior do que o caso em um professor que precisa ir um dia e vai dois. Portanto, propõem-se uma reavaliação das penalidades, de forma a ponderar qual peso uma infração ao excesso de dias tem segundo o total de dias que espera-se que esse professor de aulas, além de um novo critério forte onde o professor, quando possível, deve ter pelo menos uma dia de folga. Espera-se que esse novos critérios ajudem o algoritmo a encontrar soluções onde os professores possuem aulas mais condensadas em poucos dias. 7.2 Trabalhos Futuros Entre os próximos trabalhos que serão desenvolvidos para o software estão: • Elaboração de um tutorial para facilitar a utilização do software; • Criação de novos relatórios, como exibição de horários de classes e professores; • Realização de novos testes com intuito de comprovar que a configuração encontrada para o software é a melhor; 61 • Análise detalhada da eficiência das funções implementadas, uma vez que as estruturas utilizadas são muito dependentes das implementações built-in da linguagem; • Testar outras instâncias do problema; • Paralelização do algoritmo. Existe ainda a possibilidade de implementação de novos algoritmos reutilizando o código fonte deste projeto para comparação dos resultados. 62 REFERÊNCIAS BIBLIOGRÁFICAS BELLMAN, R. E. An Introduction to Artificial Intelligence: Can Computers Think. Boyd & Fraser Pub. Co., 1978. Disponível em: http://books.google. com.au/books?id=g9AO65QphqIC. BIRBAS, T.; DASKALAKI, S.; HOUSOS, E. School timetabling for quality student and teacher schedules. Journal of Scheduling, Springer Netherlands, v. 12, p. 177–197, 2009. ISSN 1094-6136. 10.1007/s10951-008-0088-2. Disponível em: http://dx.doi.org/10.1007/s10951-008-0088-2. BLICKLE, T.; THIELE, L. A comparison of selection schemes used in genetic algorithms. [S.l.], 1995. BRINDLE, A. A genetic algorithm based university timetabling system. Doctoral Dissertation. 1980. Disponível em: http://hdl.handle.net/10402/era. 24132. BURKE, E. K.; PETROVIC, S. Recent research directions in automated timetabling. European Journal of Operational Research, v. 140, n. 2, p. 266 – 280, 2002. ISSN 0377-2217. Disponível em: http://www.sciencedirect. com/science/article/pii/S0377221702000693. DAVIS, L. D. Genetic algorithms and their applications. 1999. Disponível em: http://www.informatics.indiana.edu/fil/CAS/PPT/Davis/. EVEN, S.; ITAI, A.; SHAMIR, A. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., v. 5, n. 4, p. 691–703, 1976. GOLDBERG, D. E.; DEB, K. K.: A comparative analysis of selection schemes used in genetic algorithms. Foundations of Genetic Algorithms. 1991. JUNGINGER, W. Timetabling in germany – a survey. Interfaces, v. 16, n. 4, p. 66 – 74, 1986. ISSN 00922102. Disponível em: http://goo.gl/1NvQ1. KINGSTON, J. Resource assignment in high school timetabling. Annals of Operations Research, Springer Netherlands, v. 194, p. 241–254, 2012. ISSN 0254-5330. 10.1007/s10479-010-0695-0. Disponível em: http://dx.doi.org/10.1007/s10479-010-0695-0. LOBO, E. L. M. Uma Solução Do Problema De Horário Escolar Via Algoritmo Genético Paralelo. Dissertação (Mestrado) — Centro Federal de Educação Tecnológica de Minas Gerais, 2005. Disponível em: http://goo.gl/TIHDL. MITCHELL, M. An introduction to genetic algorithms. Cambridge, MA, USA: MIT Press, 1996. ISBN 0-262-13316-4. 63 NETO, J. D. Resolução do timetabling universitário utilizando métodos inteligentes. Monografia (Monografia de Graduação) — UFLA - Universidade Federal de Lavras, Lavras - MG, nov 2011. RUSSELL, S.; NORVIG, P. Artificial Intelligence: A Modern Approach (3rd Edition). 3. ed. Prentice Hall, 2009. Hardcover. ISBN 0136042597. Disponível em: http://www.amazon.com/gp/product/0136042597. SCHAERF, A. A survey of automated timetabling. Artificial Intelligence Review, Springer Netherlands, v. 13, p. 87–127, 1999. ISSN 0269-2821. 10.1023/A:1006576209967. Disponível em: http://dx.doi.org/10.1023/A: 1006576209967. SIPSER, M. Introduction to the Theory of Computation. 3. ed. [S.l.]: Course Technology, 2012. ISBN 113318779X. SMITH, R. E.; DIKE, B. A.; STEGMANN, S. A. Fitness inheritance in genetic algorithms. In: Proceedings of the 1995 ACM symposium on Applied computing. New York, NY, USA: ACM, 1995. (SAC ’95), p. 345–350. ISBN 0-89791-658-1. Disponível em: http://doi.acm.org/10.1145/315891.316014. TIMóTEO, G. T. S. Desenvolvimento de um algoritmo genético para a resolução do timetabling. Monografia (Monografia de Graduação) — UFLA - Universidade Federal de Lavras, Lavras - MG, nov 2002. WERRA, D. de. An introduction to timetabling. European Journal of Operational Research, v. 19, n. 2, p. 151–162, February 1985. Disponível em: http://ideas.repec.org/a/eee/ejores/v19y1985i2p151-162.html. WREN, A. Scheduling, timetabling and rostering ´´a special relationship”. In: BURKE, E.; ROSS, P. (Ed.). Practice and Theory of Automated Timetabling. Springer Berlin Heidelberg, 1996, (Lecture Notes in Computer Science, v. 1153). p. 46–75. ISBN 978-3-540-61794-5. Disponível em: http://dx.doi.org/10.1007/3-540-61794-9_51. 64 A DADOS COLETADOS Professor João Noemi Rodrigo Selma Viviane Eliane Adriana Bruna Mônica Edison Meire Maristela Hugo Lucir Sandra Paulo Danila Rogério Joaquim Luzia Isabel Disciplina Port Port Port L. Inglesa Inglês Mat Mat Mat Mat Geografia Sociologia Sociologia Geografia História História História Filosofia Ed. Física Biologia Ciências Ciências Biologia Física Ciências En. Relig Artes Quimica 6A 5 6B 5 7A 5 8A 5 9A 1A 5 1 1 6 1 1 6 6 1B 2 2 3 3 1 1 1 1 3 3 3B 4 4 4 4 4 4 4 4 1 2 1 2 1 2 4 3 3 2 2 4 3 1 3A 2 6 3 3 2B 4 4 2 4 3 3 2A 1 6 3 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 3 1 2 3 2 2 2 3 3 3 3 3 3 1 2 1 2 3 3 3 3 3 2 2 1 2 2 4 1 Tabela A.1: Distribuição de aulas do turno da manhã 65 B AUTORIZAÇÃO PARA DIVULGAÇÃO DOS DADOS DA ESCOLA 66 C INTERFACE DESENVOLVIDA Figura C.1: Interface do cadastro de usuário 67 Figura C.2: Interface do cadastro de professor 68 Figura C.3: Interface da lista de professores cadastrados 69 Figura C.4: Interface de cadastro de aulas 70 Figura C.5: Interface para definição das restrições dos professores 71 Figura C.6: Interface onde define-se os parâmetros do algoritmo genético para criação do horário 72 Figura C.7: Interface que mostra o horário criado