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