UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA
CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS
SOFTWARE DE ESCALONAMENTO DE HORÁRIO
ACADEMICO: UMA APLICAÇÃO DOS
ALGORITMOS GENÉTICOS
MARCOS VINICIUS BIÃO CERQUEIRA
CRUZ DAS ALMAS, 2012
ii
UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA
CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS
SOFTWARE DE ESCALONAMENTO DE HORÁRIO
ACADEMICO: UMA APLICAÇÃO DOS
ALGORITMOS GENÉTICOS
Trabalho de conclusão de curso apresentado à
Universidade Federal do Recôncavo da Bahia como
parte dos requisitos para obtenção do título de
bacharel em ciências exatas e tecnológicas
Orientador : Prof.: Tiago Oliveira Motta
Co-orientador: Prof.: Carlos Frederico Macedo Cortês
MARCOS VINICIUS BIÃO CERQUEIRA
CRUZ DAS ALMAS, 2012
iii
UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA
CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS
SOFTWARE DE ESCALONAMENTO DE HORÁRIO
ACADEMICO: UMA APLICAÇÃO DOS
ALGORITMOS GENÉTICOS
Aprovada em: 12/12/2012
BANCA EXAMINADORA
ASS_____________________________________________________________________
Presidente: Prof° M. SC Tiago Oliveira Motta
ASS_____________________________________________________________________
Membro I: Prof° M. SC Tiago Palma Pagano
ASS_____________________________________________________________________
Membro II: Prof° Dr Carlos Frederico Macêdo Cortes
ASS_____________________________________________________________________
Membro III: Prof° M. Sc. Anderson Leonardo Sanches
Orientador: Prof° M. SC Tiago Oliveira Motta
Graduando: Sr. Marcos Vinicius Bião Cerqueira
CRUZ DAS ALMAS, 2012
iv
AGRADECIMENTOS
Agradeço primeiramente aos meus pais, pois devo a eles a minha educação e
meu sustento.
A Carlos Cortês por me propor esse trabalho e se disponibilizar a me orientar
e a posterior passando minha orientação para Tiago Motta, que me ajudou diversas
vezes e sem ele, não teria conseguido concluir esse projeto.
Não posso esquecer de agradecer aos meus colegas Gabriel, Deise e
Eduardo, amigos desde 2009, mas que com o passar dos semestre, pegamos cada
vez menos disciplinas juntos. A Alex, Ernando e Maiara, companheiros de estudo,
dores de cabeça e de preocupações. Batalhamos para passar em tantas disciplinas.
A Rafael Levi, amigo de longas datas, mais de 10 anos com certeza. Rapaz
bem atrapalhado, mas determinado. Desejo que muitos anos de sucesso estejam
pra vim.
Um agradecimento especial a Luana, o amor da minha vida. Mulher meiga,
carinhosa e amorosa, que com seu jeito cativante me conquistou e eu posso dizer
que sem ela, nada disso seria possível.
Agradeço também aos membros da banca que se predisporá a ler o meu
trabalho e a estarem presentes no dia da defesa para avaliar o mesmo.
Obrigado a todos aqueles que não mencionei, mas que sempre estiveram me
apoiando em todos os momentos
v
UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA
CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS
SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA
APLICAÇÃO DOS ALGORITMOS GENÉTICOS
RESUMO
A grade de horários é de notável importância para todo corpo docente e discente. Uma vez
que elaborada, terá validade por todo período letivo. Porém o escalonamento desses horários é
de solução não-trivial devido a sua quantidade de variáveis e de quantidade de informações a
serem tratadas. Os Algoritmos Genéticos é um método probabilístico de otimização baseado
nas leis da evolução, onde as soluções mais aptas sobrevivem. O software condensa a solução
do problema em uma cadeia binária, onde essa passara pelos processos evolutivos (seleção,
cruzamento e mutação) até encontrar uma boa solução ou uma que satisfaça o critério de
parada. Para saber se a solução é aceitável, existe a função objetivo que avalia a cadeia
binária, penalizando os erros existentes, fazendo com que os mais evoluídos permaneçam e
gerem filhos melhores a cada nova geração. Com a sobrevivência dos mais aptos, os melhores
indivíduos prevalecerão. É possível que uma geração seja pior que a sua anterior, mas isso é
pouco provável. Para tal projeto, foi feito uma pesquisa bibliográfica, a fim de compreender o
funcionamento dos algoritmos genéticos e a construção de versões beta do software.
Palavras-chave: Escalonamento de horário, Algoritmo genético, Grade acadêmica
vi
UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA
CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS
SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA
APLICAÇÃO DOS ALGORITMOS GENÉTICOS
ABSTRACT
The grid scheduling is of considerable importance to all faculty and students. Once
drafted, will be valid throughout the school year. But the escalation of these
schedules is non-trivial solution due to its number of variables and amount of
information to be handled. The Genetic Algorithm is a probabilistic optimization
method based on the laws of evolution, where the most suitable solutions survive.
The software condenses the solution of the problem in a binary string, where it
passed by evolutionary processes (selection, crossover and mutation) to find a good
solution or one that meets the stopping criterion. To determine whether the solution is
acceptable, there is the objective function that evaluates the binary string, penalizing
existing errors, making the stay more evolved and better manage children with each
new generation. With the survival of the fittest, the best individuals prevail. It is
possible that a generation is worse than his previous one, but this is unlikely. For this
project, a literature search was done in order to understand the functioning of genetic
algorithms and the construction of beta versions of software.
Keywords: Scheduling time, Genetic Algorithm, academic Grade
vii
Índice
1. Introdução ..................................................................................................... 1
1.1 Justificativa ..................................................................................................................... 2
1.2. Objetivo .......................................................................................................................... 3 1.3. Estrutura do trabalho ................................................................................................... 3
2. Algoritmos Genéticos .................................................................................. 4
2.1. Introdução ..................................................................................................................... 4
2.2 Terminologia .................................................................................................................. 6
2.3. Operadores Genéticos ................................................................................................ 7 2.3.1. Operador de seleção ............................................................................................ 7
2.3.2. Operadores de cruzamento ................................................................................ 8 2.3.3. Operadores de Mutação ...................................................................................... 9
2.4. Elitismo ........................................................................................................................ 10 2.5. Critérios de parada .................................................................................................... 10
2.6. Outras considerações sobre AGs ........................................................................... 10
2.6.1. Reutilização de código ....................................................................................... 10 2.6.2. Os menos aptos também deve ter chance de se perpetuar ........................ 10
3. Estudo de caso ........................................................................................... 12
3.1 – Abordagens iniciais ................................................................................................. 12
3.2 – Complexidades algorítmicas .................................................................................. 13
3.3 – Tipos de restrições .................................................................................................. 16 3.3.1 – Leves .................................................................................................................. 16
3.3.2 – Médias ................................................................................................................ 16 3.3.3 – Severas .............................................................................................................. 17
4. Implementação do sistema ........................................................................ 18
4.1 Banco de dados ........................................................................................................... 18
4.1.1 Tabela de disciplinas ........................................................................................... 18 4.1.1 Tabela de professores ........................................................................................ 20
4.1.1 Tabela de salas .................................................................................................... 21 4.2 Modelagem computacional ........................................................................................ 23
4.3 Inicialização da população ......................................................................................... 25
4.4. Função de avaliação ................................................................................................. 26 4.4.1 Número de aulas .................................................................................................. 26
4.5. Operadores genéticos ............................................................................................... 26 4.5.1 Operador de seleção – Roleta ........................................................................... 26
4.5.2 Operador de cruzamento – crossoverUmPonto ............................................. 27 4.5.3 Operador de mutação ......................................................................................... 27
4.6 Elitismo ......................................................................................................................... 27
4.7 Função de ajuste ......................................................................................................... 28
5. Resultados e Conclusões .......................................................................... 29
5.1 Plataformas de hardware e software ....................................................................... 29
5.2 Análise dos resultados ............................................................................................... 30
6. Conclusão ................................................................................................... 31
6. Trabalhos futuros ....................................................................................... 32
viii
Bibliografia ...................................................................................................... 33
APENDICE A – Diagrama de caso de uso .................................................... 34
APENDICE B – Diagrama de sequencia ....................................................... 35
APENDICE C – Diagrama de classes ............................................................ 43
ix
Índice de figuras
Figura 1- Algoritmo genético básico .......................................................................................... 4
Figura 2- Descrição gráfica dos elementos genéticos com codificação binária ......................... 7 Figura 3-- Exemplo de operador de crossover de um ponto....................................................... 9 Figura 4- Exemplo de operador de mutação ............................................................................... 9 Figura 5- Horário semanal de um estudante ............................................................................. 12 Figura 6- Exemplo de matriz curricular ................................................................................... 13
Figura 7- Tela de cadastro de disciplinas ................................................................................. 19 Figura 8- Tela de atualização de disciplinas ............................................................................. 19
Figura 9– Telas de exclusão de disciplinas .............................................................................. 20 Figura 10- Tela de cadastro de professor.................................................................................. 20 Figura 11- Tela de atualização de professor ............................................................................. 21 Figura 12– Tela de exclusão de professores ............................................................................. 21 Figura 13- Tela de cadastro de sala .......................................................................................... 22
Figura 14- Tela de atualização de sala...................................................................................... 22 Figura 15– Tela de exclusão de salas ....................................................................................... 23 Figura 16- Tela de cadastro de turma ....................................................................................... 24 Figura 17- Representação de cromossomo com disciplina sendo representada por 2 bits ....... 25
Figura 18- Apresentação dos resultados ................................................................................... 30
Figura 19- Apresentação dos resultados ................................................................................... 30 Figura 20– Diagrama de caso de uso ........................................................................................ 34 Figura 21– Diagrama atualiza disciplina .................................................................................. 35
Figura 22– Diagrama atualiza professor ................................................................................... 36 Figura 23– Diagrama Atualiza sala .......................................................................................... 37
Figura 24– Diagrama cadastra disciplina ................................................................................. 37 Figura 25– Diagrama cadastra professor .................................................................................. 38 Figura 26– Diagrama cadastra sala ........................................................................................... 38
Figura 27– Diagrama exclui disciplina ..................................................................................... 39 Figura 28– Diagrama exclui professor ..................................................................................... 40
Figura 29– Diagrama exclui sala .............................................................................................. 41 Figura 30– Diagrama forma horário ......................................................................................... 42 Figura 31– Diagrama de classe ................................................................................................. 43
x
Índice de tabelas
Tabela 1- Possível solução para maximizar f(x)=x² ................................................................. 11
Tabela 2- Representação de 3 turmas ....................................................................................... 24 Tabela 3- Representação de 5 turmas ....................................................................................... 24 Tabela 4- Representação dos slots ............................................................................................ 25
1
1. Introdução
É bastante desejável que a resolução de um problema seja obtida de forma
rápida e robusta. No inicio dos tempos a busca pela solução era feita de forma
intuitiva, mas à medida que os problemas foram tornado-se complexos, a intuição
deixou de ser uma ferramenta utilizável, tendo assim a necessidade de criação de
métodos que indicassem o melhor caminho a seguir.
Atualmente, métodos computacionais são bastante utilizados na resolução
de problemas nas diversas áreas da ciência. Dentre esses métodos computacionais
existe a otimização combinatória. Segundo Ribeiro Filho(2000), a otimização
combinatória se caracteriza pelo tratamento de problemas cujo conjunto de
possibilidades solução é finito e enumerável. Outro método que pode ser utilizado é
a Rede Neural que é inspirado na estrutura neural dos organismos inteligentes que
tem a habilidade de aprender com o ambiente, melhorando assim o seu
desempenho através de processos interativos de ajustes. Uma grande rede neural
pode apresentar centenas de unidades de processamento, uma vez que um cérebro
de um mamífero pode ter bilhões de neurônios. Outra forma é a utilização da Lógica
Fuzzy, apesar desse método não precisar de uma boa aproximação inicial, ela é
uma proposta de dois extremos, ou esta tudo verdadeiro ou tudo falso.
De acordo com Linden (2012), os algoritmos evolutivos dependem de fatores
estocásticos (probabilísticos), tanto em sua fase de inicialização, quanto em sua
evolução. Com isso, é quase impossível que seus resultados sejam perfeitamente
reproduzidos, ou seja, é muito provável fazer a execução do código diversas vezes e
encontrar resultados diferentes. Caso o tempo de execução do algoritmo seja
pequeno, não existe a necessidade de se utilizar algoritmos evolutivos, os métodos
matemáticos são mais eficientes para esse tipo de problema. Entretanto quando
trabalhamos com algoritmos extremamente lentos, onde o espaço de busca é muito
grande, as classes evolutivas são uma excelente ferramenta para a busca de
soluções.
2
1.1 Justificativa
Nesse trabalho será analisado o problema do escalonamento de horários de
disciplinas de graduação do CETEC, Centro de Ciências Exatas e Tecnológicas, da
UFRB, Universidade Federal do Recôncavo da Bahia. Esse tipo de problema é de
difícil solução manual, pois existe um grande número de professores e disciplinas
sendo ministradas no centro, tornando assim muito complicado a tabulação das
informações. A grade de horários é de notável importância para todo corpo docente,
discente e funcionários da instituição, já que uma vez elaborada, ela terá validade
por todo período letivo. O CETEC se encontra atualmente com cerca de 81
professores, sendo que parte do corpo docente atua como suporte a outro centro, o
CCAAB, Centro de Ciências Agrárias Ambientais e Biológicas. Tomando-se uma
média de três disciplinas por professor, totalizando 243 turmas para serem
distribuídas.
Nesse sentido o escalonamento de horários em questão se torna uma tarefa
não-trivial do ponto de vista computacional. Assim, a teoria da complexidade
computacional faz parte da teoria da computação que estuda os recursos
necessários de um algoritmo para resolver um problema. Existem vários tipos de
problemas, dentre os quais se podem citar: N, P e NP - completo. Um problema
pode ser considerado do tipo P se existir um algoritmo polinomial que resolva esse
problema, nesse caso eles são tratáveis. Geralmente são problemas onde envolvem
equações polinomiais simples, como por exemplo, equações lineares. Segundo
Toscani (2001), os assim chamados problemas „NP – Completos‟ são aqueles que
têm a questão da complexidade ou tratabilidade não resolvida, pois não se sabe se
existe ou não algoritmo polinomial que o resolva. Nesse tipo de problema se
encontram equações exponenciais e fatoriais, que com um pequeno número de
entradas se alcançam números muito grandes de cálculos.
A pessoa responsável por esse processo é o Gestor de Ensino. A cada novo
semestre ele deve redefinir os horários, levando em consideração a preferência de
horário dos professores, o tamanho da turma, o tamanho da sala, entre outros. Com
isso, segundo Linden 2012, fica claro que o espaço de busca é demasiadamente
grande, dando que o número de combinações turma/sala/horário é proporcional ao
fatorial do número de turmas e salas, adquirindo assim o caráter de NP - Completo.
3
1.2. Objetivo
O objetivo deste trabalho é criar um software de fácil operação, do qual seja
possível a extração de informações relevantes ao processo de formação da grade
horária, levando em consideração a limitação dos recursos humanos e de infra-
estrutura, utilizando Algoritmo Genético para alcançar uma solução viável.
1.3. Estrutura do trabalho
No capítulo 2 são apresentados e discutidos os fundamentos dos algoritmos
genéticos. No tópico seguinte, mostra-se a dificuldade de se criar uma grade de
horários, mostrando a sua complexidade e as restrições encontradas nesse tipo de
problema. O capítulo 4 apresenta a implementação do sistema, desde sua
modelagem até os métodos utilizados. O capítulo 5 expõe os resultados e a
conclusão obtida por sua análise. Por último e não menos importante, no capítulo 6
é feito sugestões para trabalhos futuros.
4
2. Algoritmos Genéticos
2.1. Introdução
Segundo Cortês(2010), a busca pela otimização de um problema é uma
grande escolha para o melhoramento de suas soluções. A otimização visa
determinar a melhor correlação entre as variáveis para atender os parâmetros e
condições do projeto sem a necessidade de testar todas as possibilidades e,
portanto sem onerar o processo. A otimização vem sendo aplicada em diversos
campos da engenharia, como por exemplo, planejamento, logísticas, análise de
estruturas e formação de horários.
Os Algoritmos Genéticos(AG) são uma classe de algoritmo que visa a
otimização dos problemas com base nos preceitos da genética. Para a evolução da
cadeia de soluções, são usados os operadores genéticos, esses por sua vez, são
divididos em 3 grupos: mutação, seleção e cruzamento. Abaixo se encontra um
pseudocódigo de AG básico:
Figura 1- Algoritmo genético básico
Fonte: Adaptado de Linden,2006
De acordo com Linden (2012), é importante ressaltar que a evolução natural
não é um processo para a obtenção de uma solução ótima. O processo
simplesmente consiste em fazer vários indivíduos competirem entre si pelo processo
de sobrevivência do mais apto, onde os melhores indivíduos tendem a sobreviver.
É possível que uma geração seja pior que a sua anterior, mas isso é pouco
provável.
5
Com a aplicação dos operadores genéticos, novos cromossomos são criados.
Faz-se necessário a utilização de um método de avaliação que faça a seleção. Tem-
se então a função objetivo que “penaliza” o individuo que se encontra em
contradição com a resolução do problema.
Devido à necessidade de implementações mais precisas, problemas mais
complexos são criados para poder suprir a grande demanda imposta pelo mercado e
apesar dos avanços das ferramentas computacionais, não era mais possível contar
com os processos de tentativa e erro.
Percebe-se, então, que a otimização é uma ferramenta importante para a
resolução dos problemas da engenharia. Abaixo se encontra algumas de suas
vantagens e desvantagem:
Vantagens:
- Redução do tempo e custo devido à elaboração do projeto, em um curto
prazo o problema é otimizado;
-Possibilidade de manejo simultâneo de uma grande quantidade de variáveis
e restrições de difícil visualização gráfica ou tabular
Desvantagens:
-Aumento do custo computacional, computadores que rodam esse tipo de
programa necessitam de uma grande quantidade de memória;
-Presença de muitos mínimos locais (o mínimo global é dificilmente obtido);
Na maioria das vezes as soluções encontradas são próximas ao mínimo global
onde satisfazem o método de parada. Além disso, são aplicados a vários tipos de
problemas, já que não impõem limitações encontradas geralmente em outros
métodos de buscas. Algumas vantagens do AG:
São relativamente fáceis de serem implementados;
São flexíveis, é possível utilizar parte do código em outros problemas;
É possível utilizar varias funções-objetivo, mesmo que conflitantes;
Trabalham sobre um conjunto de soluções do espaço de busca em vez de
uma única solução;
Trabalham com múltiplos candidatos à solução ao mesmo tempo, na mesma
geração;
Usam regras probabilísticas de transição;
Pode ser hibridizada com outras técnicas heurísticas.
6
Devido a essas características, os AG mostram ser mais eficientes do que os
métodos tradicionais. Contudo, quando se existe uma boa aproximação inicial, os
métodos matemáticos se mostram mais eficientes devido ao baixo custo
computacional. Daí surgiu novas formas de manejo, onde primeiramente utilizam-se
os métodos probabilísticos e com o refinamento dos resultados, utilizam-se técnicas
matemáticas para redefinir o resultado garantindo um ótimo resultado. (BARBOSA &
LEMONGE 2003).
Segundo Concilio (2000), três condições devem ser consideradas em torno do
processo interativo:
Garantia de convergência;
Tempo de convergência compatível com as necessidades de cada
aplicação;
Convergência para uma solução de boa qualidade.
Quanto mais complexo o problema de otimização e quanto maior o número de
variáveis, menores são as chances das três condições serem atendidas,
principalmente quando o método de otimização aplicado não for poderoso o
suficiente na execução do processo de busca.
A tratabilidade de problemas com alto grau de complexidade, por muitas
vezes, é conseguida abrindo mão de uma solução ótima em prol de uma boa
solução. Como em muitos casos se desconhece a solução ótima, a qualidade
dessas soluções é medida de acordo com as soluções obtidas em outros testes.
2.2 Terminologia
Os seres vivos são constituídos de células que por sua vez são compostos por
cromossomos. Cada indivíduo está presente em sua geração, podendo fazer com
que seus genes sejam passados para a próxima geração. Abaixo temos uma lista
com os termos usado nos AGs.
Cromossomo: Ele é a representação das soluções do problema, como esse
trabalho utiliza a representação binária, o cromossomo nada mais é do que
uma cadeia de 0 e 1;
Gene: Um elemento que indica o cromossomo;
7
Individuo: Junção do cromossomo com sua aptidão;
Aptidão: O quão próximo o cromossomo esta para chegar à melhor solução
do problema;
Genótipo: Informação contida no cromossomo;
Fenótipo: É o cromossomo codificado, em nosso caso, seria a informação de
qual professor estaria em qual sala lecionanda determinada disciplina;
Alelo: Devido à representação binária, seria propriamente o 0 ou o 1;
Epistasia: Interação entre os genes de um cromossomo, ou seja, quando um
gene interferiu em outro;
Geração: Número de ciclos que o algoritmo faz.
Figura 2- Descrição gráfica dos elementos genéticos com codificação binária
Fonte: Adaptado de Cortês, 2010
2.3. Operadores Genéticos
Os operadores genéticos já existentes têm como objetivo gerar novos
indivíduos, mantendo a diversidade cromossomial, permitindo assim que o algoritmo
explore varias regiões do espaço de busca.
2.3.1. Operador de seleção
8
O operador de seleção tem como objetivo escolher aleatoriamente os
indivíduos que passarão para a próxima geração e quais sofrerão as ações dos
operadores. O fator levado em conta para esse tipo de operador é o índice de
aptidão. Seu objetivo é fazer com que os mais aptos permaneçam na população,
gerando descendentes com índice de aptidão ainda melhores, enquanto os outros
indivíduos tendem a desaparecer.
O operador de seleção a ser usado, vai depender muito do problema
analisado. Quanto mais rigoroso for o operador, mais rápido os indivíduos tendem
aos mínimos das funções, em contrapartida sua diversidade é reduzida, dificultando
à exploração de outras regiões do espaço que poderiam ser favoráveis a solução do
problema.
O índice de aptidão está associado à probabilidade de reprodução de um
indivíduo. Logo, este indicador depende do valor da função-objetivo para cada
indivíduo que compõe a população. (LACERDA e CARVALHO, 1999)
2.3.2. Operadores de cruzamento
O cruzamento é um processo onde a partir de dois cromossomos é gerado
um novo, garantindo a diversidade da população.
Para controle de sua ocorrência existe uma taxa de cruzamento pc(ponto de
cruzamento), que limita a possibilidade do cromossomo sofrer o processo. Uma taxa
alta permite uma maior exploração do espaço, porém o tempo computacional é
elevado devido à exploração de áreas não favoráveis.
O cruzamento funciona da seguinte forma: gera-se um número real e
aleatório(entre 0 e 1) para cada indivíduo. Aqueles que tiverem o número menor que
a taxa de cruzamento, serão aplicados os processos de cruzamento adotados no
código, eles são chamados de progenitores. Os resultados dos cruzamentos são
chamados de descendentes.
Segundo Cristina Hamawaki(2005), vale lembrar que o cruzamento de
indivíduos iguais, resultará em um indivíduo igual aos seus progenitores, atrasando
o processo de convergência do algoritmo. Por isso, o método de cruzamento não
deve ser realizado com cromossomos iguais.
9
Figura 3-- Exemplo de operador de crossover de um ponto
Fonte: Adaptado de Cortês,2010
2.3.3. Operadores de Mutação
A mutação é obtida pela mudança aleatória de um gene em um cromossomo
especifico, que também é escolhido aleatoriamente dentre os descendentes da
geração.
Para existir um controle desse operador, existe um limitador chamado de
pm(ponto de mutação). Uma baixa taxa de mutação tende a obter resultados mais
rápidos devido à diminuição da diversidade. Contudo, uma taxa maior acarretaria
uma exploração maior de outras regiões.
Para o funcionamento desse operador, é gerado aleatoriamente um número
entre 0 e 1 para cada alelo. Aqueles que tiverem um número menor que pm sofreram
as ações dos operadores de mutação.
Geralmente se utiliza valores pequenos entre 0,1% a 10%.
Figura 4- Exemplo de operador de mutação
Fonte: Adaptado de Cortês, 2010
10
2.4. Elitismo
Na genética, o filho é gerado a partir da combinação dos cromossomos de
seus pais, fazendo com que apareça um novo indivíduo, porém com isso perdem-se
os indivíduos originais. No AG, o desaparecimento de bons indivíduos é ruim para
atingimos a melhor solução do problema. Portanto De Jong (1975) propôs um
método chamado de elitismo, onde os melhores indivíduos são mantidos nas
gerações seguintes. Alguns pesquisadores da área também chamam esse método
de clonagem.
2.5. Critérios de parada
Em vários casos, demora-se muito a atingir um mínimo global. Em outros
casos ele nem é atingido, faz-se necessário a utilização de um método de parada.
Normalmente os métodos mais utilizados são o número máximo de gerações e o
tempo limite de processamento.
2.6. Outras considerações sobre AGs
2.6.1. Reutilização de código
Os algoritmos genéticos têm a característica de poderem ser reutilizados de
um problema para o outro, simplesmente alterando sua função de avaliação e
buscando novamente a solução. Alguns resultados podem ate ser interessantes,
mas a lógica sugere que não é a melhor abordagem. De acordo com Linden (2012)
quanto mais informações do problema o algoritmo tiver, mais eficiente ele será. A
utilização do algoritmo genético não pode ser uma desculpa para ignorar as
caracteristicas do problema e para a não modelá-lo computacionalmente.
2.6.2. Os menos aptos também deve ter chance de se perpetuar
Charles Darwin não estava errado em dizer que apenas os indivíduos mais
aptos sobreviverão, no entanto isso não exclui a possibilidade tentativa de
11
reprodução de indivíduos menos aptos. Nos algoritmos genéticos não pode ser
diferente, pois existem casos em que um indivíduo com uma baixa aptidão possui
um alelo de vital importância para a otimização do problema. O exemplo é melhor
visualizado na tabela abaixo, onde se utiliza os AGs para maximizar a função f(x) =
x² dentro do intervalo [0,15]. Este é um exemplo puramente explicativo, pois se sabe
de antemão que onde a função é maximizada é 15(1111),
Cromossomo Valor representado Avaliação f(x) = x²
0010 2 4
1100 12 144
0110 6 36
0001 1 1
Tabela 1- Possível solução para maximizar f(x)=x²
O indivíduo 4(0001) tem uma péssima avaliação, porém ele tem um ótimo alelo, que
é o 1 na ultima posição do cromossomo, característica essa que não se encontra
nos dois melhores cromossomos. Logo se utilizar somente os melhores
cromossomos para a reprodução, esse alelo não terá a chance de se perpetuar e
para que ele apareça novamente, ficar-se-ia dependente apenas do processo de
mutação, processo esse com baixa possibilidade de acontecimento, como visto
anteriormente.
12
3. Estudo de caso
3.1 – Abordagens iniciais
Neste trabalho, considera-se como base o curso de Bacharelado em Ciências
Exatas e Tecnológicas e uma de suas terminalidades da UFRB. Ela é formada por
um conjunto de disciplinas, distribuídas ao longo de 10 semestres. Para concluir o
curso, o aluno deve concluir todas as disciplinas de sua matriz curricular.
A cada semestre, as disciplinas são oferecidas em um determinado dia da
semana, onde o aluno poderá se matricular nas disciplinas oferecidas. Porém ele
terá que respeitar o choque de horários e os pré-requisitos dos componentes
curriculares que deseja cursar. Abaixo tem uma figura que exemplifica o horário
semanal de um estudante:
Figura 5- Horário semanal de um estudante
Fonte: Dados da pesquisa
Para uma melhor administração por conta do corpo discente, o curso oferece um
diagrama do fluxo curricular, como ilustra a figura abaixo. Nessa grade já é previsto
o cumprimento de pré-requisitos afim de não comprometer o tempo de conclusão do
curso pelo aluno.
13
Figura 6- Exemplo de matriz curricular
Fonte:http://www.ufrb.edu.br/cetec/index.php/documentos/diversos/84-ppc-
bcet/download
O número de disciplinas por semestre pode varia de acordo com o curso
analisado. Como existe a possibilidade de adiantamento ou atraso de disciplinas por
parte do aluno, existe uma quantidade mínima e máxima de semestre a serem
cursadas.
Segundo Cristina Hamawaki (2005), a criação de uma grade horária em uma
instituição de ensino é uma atividade muito importante, já que depois de elaborada,
ela será utilizada por todo o período letivo. Isto faz com que todos, inclusive o corpo
docente, tenham que se adaptar a esses horários.
3.2 – Complexidades algorítmicas
Algo que não fica explicito aos olhos dos usuários é a complexidade que existe
para se montar uma grade de horários em uma universidade. Para poder definir o
14
tamanho total do nosso espaço, poderia-se aplicar o arranjo simples. O arranjo
simples de n elementos tomado p a p, onde p < n, são diferentes agrupamentos
ordenados que se possam formar com p dos n elementos dados. Eles são
calculados assim:
Equação 1- Formula de arranjo simples
Onde:
Arranjo simples de "a" elementos separados em grupo de p elementos
a Numero total de elementos
p Numero de elementos escolhidos
Porém, esse tipo de raciocínio é aplicado em situações onde a ordem de
alocação é importante, como por exemplo, senhas. Então, nesse caso utiliza-se a
permutação. O conceito de permutação expressa à idéia de que objetos distintos
podem ser arranjados em inúmeras ordens diferentes. Por exemplo, com os
números de um a seis, cada ordem possível produz uma lista dos números, sem
repetições. Ele é dado da seguinte forma:
Equação 2- Formula para permutação simples
Onde:
P Permutação simples de n elementos
n Numero total de elementos
Nesse caso tem-se 243 turmas para serem alocadas em salas de aula.
Supondo que todas as turmas tenham 2 aulas semanais, tem-se um total de 486
aulas distribuídas na semana.
Para primeira alocação tem-se 486 possibilidades, aloca-se uma aula. Na
segunda tem-se 485, aloca-se outra aula, e assim sucessivamente obtendo uma
característica fatorial, como mostra o esquema abaixo.
Equação 3– Exemplo do numero total de possibilidades
Onde: TT Número total de possibilidades
15
A não existência de um método polinomial torna esse problema de difícil
resolução computacional. O fato de ter uma equação fatorial faz com que uma
pequena quantidade de entrada se torne uma quantidade absurda de cálculos a
serem analisados, fazendo com que se gaste um tempo muito grande para
atingirmos uma solução. Por isso esse problema pode ser caracterizado por NP -
Completo.
Olhando agora a parte estrutural, tem-se 23 salas, dentre elas encontram-se 3
tipos diferentes:
Salas convencionais;
Salas de desenho;
Laboratorio de informática.
Inicialmente não diferenciaremos essas salas. Como as aulas podem ser
ministradas no turno da manha e da tarde, tendo 2 aulas em cada turno, tem-se
então um espaço total de 460 alocações para poder serem distribuídas as aulas,
como se pode ver a seguir:
Equação 4- Equação para o numero total de alocações na semana
NA número de alocações
NS número de salas = 23
NADS número de aulas por dia por sala = 4
ND número de dias = 5
Equação 5- Exemplo do caso analisado
De acordo com Lemes Hamawaki, 2005, Frangouli 2002, propôs uma fórmula
para determinar o tamanho máximo do espaço de pesquisa. Essa fórmula pode ser
expressa por:
Equação 6- Equação proposta por Frangouli, 2002
Onde:
16
TEP tamanho do espaço de pesquisa
NDS números de dias letivos na semana
NAD número de aulas por dia
NSA número de salas de aula
ND número de turmas
NAP número de aulas por turma
No caso analisado, têm-se os seguintes valores:
Equação 7- Exemplo do caso, segundo a equação de Fragouli, 2002
Como se pode ver, o número total de possibilidades foi reduzido, mas ainda
é um número elevado.
3.3 – Tipos de restrições
O problema de alocação de aulas é multiobjetivo e sujeito a vários tipos de
restrições, restrições essas que podem ser classificadas em:
3.3.1 – Leves
Geralmente ligadas à preferência do professor. Ele poderá preencher uma
ficha informando quais os horários ele prefere ministrar suas aulas, deixando
horários reservados para suas pesquisas e extensão. As penalidades associadas a
esse tipo de advertência são baixas, já que o professor pode facilmente adequar o
seu horário.
3.3.2 – Médias
São situações de maior complexidade, geralmente ligadas a distribuição
uniforme das aulas. As penalizações envolvidas são de peso médio ou alto, a
depender do caso. Exemplos de restrições médias:
Evitar o professor ministrar aulas todos os dias;
Professores e alunos têm o dia inteiro de aulas;
17
Disciplinas de semestre impar em um turno e de semestres pares em outro
turno;
Uma disciplina dever ter no mínimo um dia e no máximo dois dias entre suas
aulas;
Uma turma deve sempre estar na mesma sala e no mesmo horário e todas as
suas aulas.
3.3.3 – Severas
Esse tipo de restrição verifica a factibilidade do cromossomo, se ele pode ser
aplicado ou não. As penalizações são elevadas, a fim de fazer o cromossomo ser
descartado ao decorrer da evolução, em alguns casos, ele inviabiliza imediatamente
o cromossomo. As restrições abaixo descritas devem ser atendidas em qualquer
sistema de elaboração de grade horária:
Cada turma deve estar presente na grade horária em um número pré-definido
de horas;
Não podem existir dois professores na mesma sala em um mesmo horário;
Nenhum professor pode estar em duas ou mais salas ao no mesmo dia e no
mesmo horário;
Disciplinas de mesmo semestre não devem estar no mesmo dia e horário;
Só pode haver uma disciplina na mesma sala e mesmo horário;
18
4. Implementação do sistema
Para poder implementar a proposta, o algoritmo foi escrito na linguagem Java,
utilizando o ambiente de desenvolvimento Eclipse. Como o Eclipse inicialmente não
possui um gerador de telas foi-se utilizada uma versão não-comecial do plug-in
Jigloo.
4.1 Banco de dados
A aplicação trabalha com uma base de dados previamente elaborada com
base em dados reais. Esses dados se encontram ordenados em tabelas criadas pelo
PostgreSQL. Nestas tabelas temos todos os dados necessários sobre as disciplinas,
professores e salas para o processamento do algoritmo.
4.1.1 Tabela de disciplinas
A tabela de disciplinas se encontra com quatro colunas: nome, código,
semestre e carga horária. As figuras abaixo mostram as telas de cadastro, de
atualização e de exclusão de disciplinas:
19
Figura 7- Tela de cadastro de disciplinas
Fonte: Dados da Pesquisa
Figura 8- Tela de atualização de disciplinas
Fonte: Dados da Pesquisa
20
Figura 9– Telas de exclusão de disciplinas
Fonte: Dados da pesquisa
4.1.1 Tabela de professores
A tabela de Professores é dividida em duas colunas: nome e SIAPE. As
figuras 10, 11 e 12 mostram, respectivamente, as telas de cadastro, de atualização e
de exclusão de professores:
Figura 10- Tela de cadastro de professor
Fonte: Dados da pesquisa
21
Figura 11- Tela de atualização de professor
Fonte: Dados da pesquisa
Figura 12– Tela de exclusão de professores
Fonte: Dados da pesquisa
4.1.1 Tabela de salas
A divisão da tabela de salas é feita em duas colunas: número e tipo. As
figuras abaixo mostram as telas de cadastro, de atualização e de exclusão de sala:
22
Figura 13- Tela de cadastro de sala
Fonte: Dados da pesquisa
Figura 14- Tela de atualização de sala
Fonte: Dados da pesquisa
23
Figura 15– Tela de exclusão de salas
Fonte: Dados da pesquisa
4.2 Modelagem computacional
A modelagem computacional é à base dos algoritmos genéticos. Ele deve ser
o primeiro aspecto a ser definido. Uma modelagem ruim detectada tardiamente pode
apresentar dificuldades em possíveis alterações futuras ou ate obrigar o
programador a refazer o trabalho.
O cromossomo é a representação da possível solução do problema, logo este
deve conter todas as informações necessárias para compor o horário acadêmico.
Em alguns casos, uma disciplina pode ter mais de uma turma, pode existir
mais de um professor responsável para a mesma disciplina.
Assim, a modelagem inicialmente pensada contém as seguintes informações:
Turma, conjunto de professor, disciplina e “turma” ex: professor A, disciplina
Cálculo diferencial e integral I, T02;
Slots, conjunto da sala, dia e horário.
Depois de fazer o cadastro das disciplinas, professores e das salas, é feito o
cadastro das turmas. Na tela de cadastro das turmas, são exibidas duas tabelas,
a dos professores e das disciplinas que foram cadastrados anteriormente. Então
basta selecionar quem será o professor e qual disciplina ele lecionará que ao
criar a turma ele verificará se já existe alguma turma que possua a disciplina que
24
está sendo cadastrada, caso não exista, será atribuído T01, caso já tenha será
atribuído T02, T03, assim por diante.
Figura 16- Tela de cadastro de turma
Fonte: Dados da pesquisa
Ao iniciar a formação dos horários, o algoritmo busca todas as turmas
cadastradas e calcula quantos bits serão necessários para representar todas
elas. Abaixo encontra-se uma tabela onde ilustra a situação.
Tabela 2- Representação de 3 turmas
Número Professor Disciplina Turma Representação
0 --------------- -------------- ------------ 00
1 A Cálculo I T01 01
2 B Cálculo I T02 10
3 A Cálculo II T01 11
Analisando outro caso. Se houver 5 turmas para serem representadas, serão
necessários 3 bits, porém com 3 bits pode-se representar até 7 turmas. A tabela
abaixo mostra como é feita a representação.
Tabela 3- Representação de 5 turmas
Número Professor Disciplina Turma Representação
0 --------------- -------------- ------------ 000
1 A Cálculo I T01 001
2 B Cálculo I T02 010
3 A Cálculo II T01 011
4 C Cálculo II T02 100
5 D Cálculo III T01 101
1 A Cálculo I T01 110
2 B Cálculo I T02 111
25
Uma vez que todos as turmas já obtiveram uma codificação binária, mas
ainda restam códigos binários sem turma associada, inicia-se o processo de
repetição das primeiras turmas tendo em vista não permitir que códigos fiquem sem
turma relacionada.
O cromossomo é subdividido em slots, onde cada um deles é a representação
do conjunto de dia/sala/horário. A sua divisão é feita de acordo com o numero de
bits necessários para representar o total de turmas cadastradas. Como no primeiro
exemplo acima foi utilizado apenas 2 bits, no cromossomo a cada 2 bits é um slot. A
figura 20 mostra um exemplo de cromossomo, com disciplina sendo representada
com 2 bits, e a tabela 4 mostra a sua codificação.
Figura 17- Representação de cromossomo com disciplina sendo representada por 2 bits
Tabela 4- Representação dos slots
Sala 1 SEG TER QUA QUI SEX
08 as 10 01 01
10 as 12 11 11
14 as 16 10 10
16 as 18
Em um caso real, o número de salas serão maiores, então novas matrizes
serão criadas respeitando essa lógica.
Contudo, nesse trabalho não foi utilizada a representação das turmas, devido
à necessidade de estudo do comportamento dos Algoritmos Genéticos em situações
pouco complexas, para então englobar todas as variáveis do problema em questão,
já que a utilização da variável “Professor” encarretaria no aumento do número de
restrições a serem respeitadas. Em vez disso, o algoritmo busca todas as disciplinas
cadastradas e cria as suas representações binárias. O comportamento dos slots
permanece inalterado.
4.3 Inicialização da população
Para dar início ao processo evolutivo, é necessário inicializar a população
criando vários cromossomos. A quantidade ideal desses cromossomos é parâmetro
bem específico de cada problema, sendo definido melhor através de alguns testes.
26
Ao iniciar o algoritmo, o método inicializaPopulacao() é chamado. A partir dele
dois outros métodos são iniciados tamanhoRepresentacaoDisciplinas(), esse método
calcula a quantidade de disciplinas cadastradas no banco de dados e verifica
quantos bits serão necessários para representar todos eles, e tamanhoVetor(), esse
método ira calcular o tamanho total do vetor binário e o seu retorno será passado
para o construtor do cromossomo.
Os cromossomos são criados de forma aleatória, os bits são gerados de
forma aleatória pelo método Math.random(), já existente na biblioteca do Java. Isso
é uma forma de obter uma boa diversidade, podendo assim, analisar vários pontos
do espaço de busca. Apesar de a inicialização ser aleatória, ela não vai gerar
soluções invalidas (disciplinas que não existem), o que comprometeria toda a
evolução. Isso só foi possível porque para cada representação existente, tem uma
disciplina associada a ele (tabela 3).
4.4. Função de avaliação
Para avaliar o cromossomo, é necessário um conjunto de restrições que
verificam factibilidade do mesmo. Quando uma dessas restrições é violada, o
cromossomo é penalizado com o valor associado a ela. Limitações leves têm baixo
valor de penalização, já restrições severas possuem o peso mais elevado.
4.4.1 Número de aulas
Nessa restrição é analisado se o número de aulas de cada disciplina condiz
com a sua carga horária cadastrada. Como foi suposto, nesse trabalho, que cada
disciplina teria apenas duas aulas semanais, se no vetor binário ela aparecer duas
vezes, a avaliação do cromossomo é acrescida com o valor 100, caso contrario, não
há acréscimo.
4.5. Operadores genéticos
4.5.1 Operador de seleção – Roleta
27
O operador de seleção escolhido foi o método roleta(). Nesse método a
chance de um cromossomo ser escolhido é diretamente proporcional ao valor da sua
aptidão. Pode-se imaginar o seguinte, cada individuo representa uma fração de uma
roleta, roleta essa que se encontra dentro do intervalo [0,1]. É gerado um número
aleatório. O cromossomo que estiver na faixa onde pertence o número sorteado,
será selecionado. Os indivíduos mais aptos conseguirão maiores frações da roleta,
consequentemente, uma maior probabilidade de serem escolhidos e os indivíduos
menos aptos, ainda que seja pequena, terá sua chance de reprodução.
4.5.2 Operador de cruzamento – crossoverUmPonto
O operador de seleção escolhido foi o crossoverUmPonto(). Inicialmente são
selecionados dois pais pelo operador de seleção (pai1, pai2). Logo após é escolhido
aleatoriamente onde será o ponto de corte. Então os dois pais têm sua cadeia de
bits cortada gerando duas cabeças e duas caldas. Este método não irá gerar dois
filhos, apenas um, pois segundo Linden (2012), isso poderia ocasionar um efeito
colateral na hora de preencher um Vector, fazendo com que o retorno do método
seja incompreensível. Nesse caso, o filho gerado pode vir com a cauda do primeiro
pai e a cabeça do segundo ou com a esquerda parte do primeiro pai e a direita do
segundo. Essa escolha é feita de forma aleatória, com 50% de chances para cada
um dos filhos.
4.5.3 Operador de mutação
A diversidade da população é necessária para que novas regiões do espaço
de busca possam ser analisadas, podendo assim encontrar áreas promissoras. Esse
operador origina aleatoriamente um número para cada bit do cromossomo, caso
esse valor seja menor do que a taxa de mutação definida previamente, o bit será
trocado. A taxa de mutação pode ser escolhida pelo usuário, mas foi utilizada uma
taxa de 0.05% nos teste feitos.
4.6 Elitismo
28
O método do elitismo, nesse software, vai selecionar os 10 cromossomos que
tiverem a maior avaliação para serem “clonados” para a próxima geração. Para a
população não crescer sem controle, os operadores genéticos vão funcionar para
gerarem 10 filhos a menos que o número total da população, quando o elitismo
atuar, a nova população apresentará o mesmo número de cromossomos do que a
sua geração anterior, mantendo assim, o número de indivíduos constantes por toda
a evolução.
4.7 Função de ajuste
Como os algoritmos genéticos não buscam uma solução ótima, então foi
preciso certificar que o horário fornecido no final da execução fosse factível. Para
isso, foi criada uma função de ajuste, onde são verificadas quais disciplinas tem
mais de 2 aulas na semana, as aulas excedentes são tiradas do horário. Logo após,
é verificado as disciplinas que tem o numero de aulas menor que o exigido, e então
são acrescentado às aulas que estão em falta.
29
5. Resultados e Conclusões
Este trabalho apresenta os aspectos da utilização dos algoritmos genéticos na
construção de uma grade horária de uma instituição de ensino superior. Procura-se
mostrar a complexidade dos problemas encontrados para a definição de uma boa
elaboração da grade horária, já que, existem múltiplos objetivos, restrições e número
de variáveis elevadas para ser considerado.
A fim de reduzir a complexidade do problema, apenas uma restrição foi
utilizada, o número de aulas durante a semana, assim como o número de variáveis
também foi reduzido, apenas a variável disciplina é levada em conta. O horário é
gerado para 1 sala. Abaixo encontra-se uma descrição do algoritmo
Buscam-se todas as disciplinas cadastradas no banco de dados;
Calculam-se quantos bits serão necessários para representar todas as
disciplinas;
Calcula-se o tamanho total do vetor binário(cromossomo);
Cada representação, da faixa de contagem, é associada a uma disciplina;
Gera-se a população inicial
São aplicados os operadores genéticos;
Exibe a melhor solução
5.1 Plataformas de hardware e software
Com o intuito de manter uma homogeneidade na apresentação dos
resultados, foram mantidos os recursos de hardware e software empregados para
essa fase do programa.
A plataforma de hardware empregada para a experimentação da aplicação
constituiu de um notebook com as seguintes características:
Processador Intel core i5-460M (2.53GHz, 3M L3 cache);
Memória principal de 4GB(utilizável 3,68GB) DDR3
Disco rígido, tecnologia SATAII de 500GB
30
E a plataforma de software foi a seguinte:
Sistema operacional: Microsoft Windows Seven;
Ambiente de desenvolvimento: Eclipse versão Indigo
Banco de dados: PostgreSQL
5.2 Análise dos resultados
A fim de compreender a funcionalidade do aplicativo, foram feitos uma série
de testes desde a implantação das primeiras classes e métodos.
Para a geração da grade horária, foram utilizados dados fictícios, porém
baseados na situação do curso Bacharelado em Ciências Exatas e Tecnológicas da
Universidade federal do Recôncavo da Bahia. Com posso desses dados, o aplicativo
foi executado varias vezes, e a cada execução o resultado era analisado para
verificar a sua convergência.
Para uma melhor exemplificação, as figuras 21 e 22, mostram os resultados
obtidos para uma entrada de 7 disciplinas:
Figura 18- Apresentação dos resultados
Fonte: Dados da pesquisa
Figura 19- Apresentação dos resultados
Fonte: Dados da pesquisa
31
6. Conclusão O software foi desenvolvido para uma instituição de ensino superior que
possui problemas e restrições a serem resolvidas com relação à criação de grade de
horários, que ate então era executado pelo gestor, sem auxilio de uma ferramenta
adequada para a minimização do tempo. Porém, foi implementada apenas a
restrição quanto ao número de aulas semanais.
Assim que a ferramenta for concluída, além de diminuir o tempo requerido
para a confecção da grade horária, amenizaria o esforço por parte do gestor, já que
o mais necessário é a alimentação do banco de dados.
A partir da análise dos resultados obtidos, pode-se concluir que as técnicas
que foram implementadas possuem resultados satisfatórios, simplificando os
procedimentos, utilizando métodos heurísticos de evolução.
Para a principal contribuição desse trabalho, pode-se mencionar o estudo de
técnicas evolutivas, em conjunto com problema de restrições, vindo com uma
solução para o problema de alocação de salas.
32
6. Trabalhos futuros
Este trabalho contribuiu para o estudo da aplicação dos algoritmos genéticos
na construção de grades de horário acadêmica. Porém as possibilidades de
pesquisa e desenvolvimento desse aplicativo não foram esgotadas. Sugerem-se
então novos trabalhos para que possam ser realizados para ampliar o conhecimento
e na obtenção de uma versão final do aplicativo. Dentre as possibilidades de
pesquisa, pode-se citar:
O acréscimo de novas restrições, a fim de que a solução seja de
agrado a um maior número de pessoas;
A utilização de todas as variáveis (disciplina, professor, sala);
O melhoramento do tempo de execução.
33
Bibliografia
BARBOSA, H. J., & LEMONGE, A. C. (2003). A New Adaptive Penalty Scheme for Genetic
Algorithm. Information Sciences , 215-251.
CONCILIO, RICARDO (2002). Contribuições à Solução de Problemas de Escalonamento
pela Aplicação Conjunta de Computação Evolutiva e Otimização com Restrições . Campinas,
São Paulo, Brasil.
Cortês, CARLOS FREDERICO, (Março de 2010). OTIMIZAÇÃO DO PROJETO DA
SUPERESTRUTURA DE PONTES PRÉ-FABRICADAS PELO MÉTODO DOS
ALGORITMOS GENÉTICOS . Rio de Janeiro, Rio de Janeiro, Brasil.
De JONG, KENNETH ALAN. (1975). An Analysis of the Behavior of a Genetic Adaptive
System . Arbor, USA.
Filho, GERALDO RIBEIRO (6 de dezembro de 2000). MELHORAMENTOS NO
ALGORITMO GENÉTICO CONSTRUTIVO E NOVAS APLICAÇÕES EM PROBLEMAS DE
AGRUPAMENTO . São José dos Campos, São Paulo, Brasil.
Hamawaki, CRISTINA DIVINA. (Novembro de 2005). Geração automatica de grade
horaria usando algoritmo genetico: O caso da faculdade de engenharia eletrica da UFU .
Uberlandia, Minas Gerais, Brasil.
LACERDA, E. G., & CARVALHO, A. C. (1999). Introdução aos Algoritmos Genéticos . Rio
de Janeiro, Brasil.
Linden, RICARDO. (2006). Algoritmos Geneticos. Rio de Janeiro: Ciencia Moderna.
Toscani, LAIRA VIEIRA (2002). Complexidade de Algoritmo. Porto Alegre: Sagra Luzzato.
34
APENDICE A – Diagrama de caso de uso
Figura 20– Diagrama de caso de uso
Fonte: Dados da pesquisa
35
APENDICE B – Diagrama de sequencia
Figura 21– Diagrama atualiza disciplina
Fonte: Dados da pesquisa
36
Figura 22– Diagrama atualiza professor
Fonte: Dados da pesquisa
37
Figura 23– Diagrama Atualiza sala
Fonte: Dados da pesquisa
Figura 24– Diagrama cadastra disciplina
Fonte: Dados da pesquisa
38
Figura 25– Diagrama cadastra professor
Fonte: Dados da pesquisa
Figura 26– Diagrama cadastra sala
Fonte: Dados da pesquisa
39
Figura 27– Diagrama exclui disciplina
Fonte: Dados da pesquisa
40
Figura 28– Diagrama exclui professor
Fonte: Dados da pesquisa
41
Figura 29– Diagrama exclui sala
Fonte: Dados da pesquisa
42
Figura 30– Diagrama forma horário
Fonte: Dados da pesquisa
43
APENDICE C – Diagrama de classes
Figura 31– Diagrama de classe
Fonte: Dados da pesquisa