Embed Size (px)
Citation preview
UNIVERSIDADE DO VALE DO ITAJAÍCENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
AUTOMATIZAÇÃO DA ELABORAÇÃO DO QUADRO DEHORÁRIOS ACADÊMICO
Acadêmico: Vinicius Carneiro do Nascimento
Orientador: Edson T. Bez, Doutor
São José, Junho / 2013
UNIVERSIDADE DO VALE DO ITAJAÍCENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE CIÊNCIA DA COMPUTAÇÃO
AUTOMATIZAÇÃO DA ELABORAÇÃO DO QUADRO DEHORÁRIOS ACADÊMICO
Vinicius Carneiro do Nascimento
São José, Junho / 2013
Orientador: Edson T. Bez, Doutor
Área de Concentração: Pesquisa Operacional
Linha de Pesquisa: Pesquisa Operacional
Palavras-chave: Algoritmos Genéticos, Heurísticas, Programação de Horários.
Número de páginas: 69
RESUMO
O problema de programação de horários ou timetabling, consiste na alocação de recursos,sujeita a um conjunto de restrições. Este tipo de problema tem motivado uma série de pesquisas por setratar de um problema de Otimização Combinatória, ou seja, tem o intuito de encontrar o melhorresultado para um problema, da forma mais eficiente e com menor custo operacional possível. Opresente estudo tem como foco a elaboração de uma grade de horário para o curso de Ciência daComputação da UNIVALI. Tendo em vista que, atualmente, esta grade de horários é uma tarefa árduae executada manualmente, desenvolveu-se um sistema automatizado capaz de executar esta tarefa demodo a atender as restrições impostas, tal como, não alocar um mesmo professor para duas disciplinasdistintas em um mesmo horário. A ferramenta desenvolvida foi baseada no Algoritmo Genético, sendoque a população inicial foi gerada apenas com indivíduos factíveis, ou seja, soluções viáveis. Nodecorrer das iterações do Algoritmo Genético buscou-se atender não somente a condição defactibilidade mas também de otimalidade, buscando entre as soluções factíveis, a melhor possível. Aferramenta proposta foi testada com os dados reais do curso contemplado e chegou a resultadossignificativos.
ABSTRACT
The problem of scheduling and timetabling consists in allocating resources, subject to a set ofrestrictions. This type of problem has motivated a lot of research because it is a problem ofCombinatorial Optimization. The present study focuses on the development of a timming schedule forthe Computer Science course UNIVALI. Given that, currently, this timming schedule is a hardmanually performed task, we developed an automatic system capable of performing this task. To solvethis problem and to meet the imposed restrictions, such as allocating the same teacher for two differentdisciplines in the same time, it is proposed using a genetic algorithm. This is intended to serve not onlythe condition of factibility but also the condition of optimality, searching among the achievablesolutions, the best one possible.
LISTA DE TABELAS
Tabela 1. Resultados apresentados pelo AG......................................................................................49
Tabela 2. Resultados apresentados pelo AG com dados fictícios......................................................59
Tabela 3. Tabela de comparação dos resultados apresentados pelas baterias de testes.....................60
LISTA DE FIGURAS
Figura 1. Fluxo do Algoritmo Genético Básico.................................................................................19
Figura 2. Representação da proporção de cada indivíduo na roleta...................................................22
Figura 3. Cromossomo binário com 10 genes....................................................................................23
Figura 4. Cruzamento com um único ponto de corte.........................................................................24
Figura 5. Cruzamento com dois pontos de corte................................................................................24
Figura 6. Mutação do cromossomo....................................................................................................25
Figura 7. Algoritmo de Busca Dispersa Implementado por Spindler................................................29
Figura 8. Caso de Uso do sistema modelado......................................................................................39
Figura 9. Diagrama de sequência da geração da grade de horário.....................................................41
Figura 10. Modelo de Relacionamento do sistema modelado............................................................42
Figura 11. Representação do cromossomo e dos genes.....................................................................43
Figura 12. Estrutura do alelo do cromossomo....................................................................................44
Figura 13. Estrutura do dia do cromossomo.......................................................................................44
Figura 14. Estrutura do período do cromossomo...............................................................................44
Figura 15. Estrutura do cromossomo.................................................................................................45
Figura 16. Pontos de corte do cromossomo.......................................................................................47
Figura 17. Gráfico da população de cromossomos apresentada na tabela 1......................................50
Figura 18. Gráfico das médias de penalidade e função de avaliação da tabela 1...............................50
Figura 19. Tela de consulta professor do sistema desenvolvido........................................................51
Figura 20. Tela de cadastro professor do sistema desenvolvido........................................................52
Figura 21. Tela de apresentação da melhor solução encontrada pelo sistema...................................53
Figura 22. Grade de horário utilizada no semestre.............................................................................56
Figura 23. Grade de horário gerada pelo sistema desenvolvido.........................................................57
Figura 24. Grade horária completa.....................................................................................................58
LISTA DE ABREVIATURAS E SIGLAS
AloGra Alocador de Grade de HoráriaAG Algoritmo GenéticoAGs Algoritmos GenéticosCTIC Congresso de Tecnologia da Informação e TelecomunicaçõesGRASP Greedy Randomized Adaptive Search ProcedureIA Inteligência ArtificialPATAT Pactice and Theory on Automated TimetablingSEPAI Semana Paraense de Informática e Telecomunicações
7
SUMÁRIO
INTRODUÇÃO ........................................................................................91.1 PROBLEMA DE PESQUISA............................................................................101.1.1 Solução Proposta.............................................................................................111.1.2 Delimitação de Escopo....................................................................................111.1.3 Justificativa......................................................................................................111.2 OBJETIVOS........................................................................................................121.2.1 Objetivo Geral.................................................................................................121.2.2 Objetivos Específicos.......................................................................................121.3 METODOLOGIA...............................................................................................121.3.1 Metodologia da Pesquisa.................................................................................121.3.2 Procedimentos Metodológicos........................................................................131.4 ESTRUTURA DO TRABALHO.......................................................................13
2 FUNDAMENTAÇÃO TEÓRICA......................................................142.1 ELABORAÇÃO DA GRADE DE HORÁRIO OU TIMETABLING............142.1.1 Viabilidade x Otimalidade..............................................................................152.2 ALGORITMOS GENÉTICOS..........................................................................162.2.1 Histórico...........................................................................................................162.2.2 Definições.........................................................................................................172.2.3 Analogia Biológica...........................................................................................182.2.4 Aspectos Principais..........................................................................................192.2.4.1 População Inicial.............................................................................................192.2.4.2 Avaliação de Aptidão......................................................................................202.2.4.3 Seleção.............................................................................................................212.2.4.4 Operadores Genéticos......................................................................................222.2.4.5 Critérios de Parada..........................................................................................252.3 MÉTODOS PARA RESOLUÇÃO DO PROBLEMA.....................................26
3 TRABALHOS CORRELATOS..........................................................323.1 ACADÊMICOS...................................................................................................323.2 COMERCIAIS.....................................................................................................333.3 ANÁLISE COMPARATIVA.............................................................................34
4 DESENVOLVIMENTO......................................................................364.1 REQUISITOS......................................................................................................364.1.1 Requisitos Funcionais......................................................................................364.1.2 Requisitos Não Funcionais..............................................................................374.1.3 Regra de Negócio.............................................................................................374.2 MODELAGEM...................................................................................................384.2.1 Caso de Uso......................................................................................................384.2.2 Diagrama de Sequência...................................................................................404.2.3 Banco de Dados................................................................................................41
8
4.2.4 Algoritmo Genético.........................................................................................434.2.5 Interface do Sistema........................................................................................514.3 DESIGN DO EXPERIMENTO.........................................................................534.4 RESULTADOS....................................................................................................54
5 CONCLUSÕES....................................................................................615.1 TRABALHOS FUTUROS..................................................................................62
9
INTRODUÇÃO
Nos dias atuais, com todas as organizações mundiais procurando incessantemente reduzir
custos, um dos grandes desafios encontrado é o schedule, ou seja, a alocação de recursos em um
determinado período de tempo, da melhor maneira possível.
Cada empresa enfrenta um problema de alocação de recurso específico, de acordo com suas
atividades. Uma indústria de automóvel deve alocar as peças que serão utilizadas na linha de
montagem da melhor maneira possível, para que não haja desperdício de tempo no deslocamento
entre seu local de armazenagem e montagem do veículo. Empresas de transporte buscam a melhor
alocação dos itens transportados em suas frotas, para desta forma fazer menos viagens ou utilizar
um veículo menor, economizando combustível. Instituições de ensino tendem a ter problemas com
o ensalamento de concorrentes em concursos e vestibulares, agendamento de exames e elaboração
da grade de horário ou timetabling.
Segundo Wren (1996 apud SANTOS & SOUZA, 2007, p. 3) timetabling é “a alocação,
sujeita a restrições, de recursos a objetos colocados no espaço e no tempo, de modo a satisfazer,
tanto quanto possível, um conjunto de objetivos desejáveis”.
A quantidade de variáveis/restrições existentes nesse tipo de problema pode ser
demasiadamente grande e a cada adição de um novo elemento o grau de complexidade cresce
exponencialmente. Em virtude desse grau de complexidade crescer tanto a cada inclusão de
variável/restrição não existe uma modelagem que provê uma solução genérica para todos os
problemas de alocação de recursos. Desta forma, não é porque já existe um sistema que solucione o
problema apresentado para uma organização, que esta solução funcionará noutra.
Dentre tantas restrições que podem ser encontradas no timetabling pode-se citar: a carga
horária de uma disciplina, a carga horária diária e semanal de uma turma, a sobreposição de
professores, a disponibilidade de professores, a disponibilidade da matéria e restrições geográficas.
Schaerf (1999 apud PAIM & GREIS, 2008, p. 6) classifica as restrições da seguinte
maneira: “restrições essenciais (hard) são aquelas que devem ser obrigatoriamente satisfeitas e
restrições não-essenciais (soft) são aquelas que podem ser violadas mas que devem ser satisfeitas da
melhor forma possível”. Um exemplo de restrição essencial é um professor que não pode dar aula
as terças e quintas-feiras por ter outros compromissos nestes dias. De nada adiantará o responsável
pela grade de horários alocar o professor nos referidos dias, se o mesmo não estará disponível. Já
um exemplo de restrição não-essencial, seria um professor que gostaria de não ministrar aulas as
10
terças e quintas-feiras, ou seja, o professor até pode dar aula nestes dias, mas o ideal é que ele
lecione nos demais dias da semana.
Existem muitas maneiras de solucionar o problema apresentado. Pode-se resolvê-lo usando a
heurística, o Algoritmo Genético (AG) muito difundido na Inteligência Artificial (IA), entre tantas.
Cada uma sendo selecionada de acordo com a modelagem do problema existente.
Tem-se conhecimento da existência de algumas ferramentas para solução do problema de
programação de horários acadêmicos. Entre estas, pode-se citar o Aghora, que é uma ferramenta
desenvolvida por acadêmicos da Universidade da Amazônia, testada na própria instituição e
apresentada na XIX Semana Paraense de Informática e Telecomunicações (SEPAI) e no II
Congresso de Tecnologia da Informação e Comunicação (CTIC). O sistema teve seu
desenvolvimento baseado nos Algoritmos Genéticos (AGs).
Dentro deste contexto, este trabalho procura fazer uma contribuição na área de pesquisa
operacional criando um sistema para automatizar a elaboração do quadro de horários da instituição
de ensino estudada. Compreendendo-se pesquisa operacional como um método científico que
auxilia nas tomadas de decisões.
Com a utilização do sistema desenvolvido na pesquisa, acredita-se que a coordenação do
curso contemplado tenha um ganho de tempo precioso para realizar tarefas mais importantes, visto
que, existe uma complexidade elevada para a construção de uma grade de horário que atenda a
expectativa de todos os envolvidos com ela, seja a coordenação ou os professores. Considerando-se
um cruzamento dos dados necessários a elaboração da grade horária como: a quantidade de
professores envolvidos, suas disponibilidades para lecionar e as disciplinas ministradas no semestre,
percebe-se que a tarefa realizada de forma manual requer muitas horas, sendo que nem sempre é
encontrada a melhor solução possível, enquanto que em alguns minutos, o sistema pode gerar uma
solução muito melhor que a manual, sendo talvez inclusive uma solução ótima.
Dando continuidade ao trabalho, na próxima seção será apresentado o problema da pesquisa.
1.1 PROBLEMA DE PESQUISA
Sabe-se que hoje, todo processo de gerar o quadro de horário do curso de Ciência da
Computação é feito manualmente pela coordenação, o que demanda muitas horas de trabalho para a
confecção de uma grade de horário que atenda a todas as restrições existentes.
Barbadym (1996 apud SOUZA, COSTA & GUIMARÃES, 2002, p. 1) afirma que “a
solução manual deste problema é uma tarefa penosa e complexa e normalmente requer vários dias
de trabalho”.
11
1.1.1 Solução Proposta
Diante de todas as informações expostas até o momento, evidencia-se que a presente
pesquisa, resultou em um sistema capaz de gerar automaticamente a programação horária do curso
de Ciência da Computação do campus São José da Universidade do Vale do Itajaí. Tal sistema foi
desenvolvido com o uso do Algoritmo Genético.
1.1.2 Delimitação de Escopo
O sistema implementado no decorrer da pesquisa, conta com os módulos: configuração do
Algoritmo Genético, disponibilidade do professor, professor, disciplina, semestre e curso. Todos
estes possuem apresentação das informações cadastradas, como a possibilidade de se adicionar
novos dados, edita-los ou removê-los.
Com todos os dados necessários a geração de uma grade de horário cadastrados, o usuário
poderá gerar a tabela de horário do curso de Ciência da Computação do campus São José da
Universidade do Vale do Itajaí.
1.1.3 Justificativa
O trabalho proposto teve o intuito de automatizar a elaboração da grade de horários do curso
de Ciência da Computação do campus São José da UNIVALI. Segundo Souza (2000), existe um
consenso na comunidade científica que é de difícil generalização o problema de alocação de
horários. Isto acontece devido a existência de diversos regimes educacionais, que variam de acordo
com a região, e também com a instituição de ensino. Devido a isto, os sistemas desenvolvidos são
frequentemente focados em uma instituição específica.
Por este motivo, as soluções existentes no mercado podem ser tomadas como base, mas
pelas especificidades encontradas na presente instituição, é necessário um sistema que atenda as
suas características.
Vislumbrou-se que com a presente pesquisa finalizada, a coordenação do curso
contemplado, tenha mais disponibilidade de horário para fazer tarefas menos mecânicas na
instituição.
12
1.2 OBJETIVOS
Esta seção formaliza os objetivos do trabalho, conforme descrito a seguir.
1.2.1 Objetivo Geral
O objetivo geral deste trabalho foi desenvolver um sistema capaz de gerar automaticamente
a grade de horários do curso de Ciência da Computação do campus São José da UNIVALI.
1.2.2 Objetivos Específicos
Os objetivos específicos deste trabalho foram:
1. Pesquisar e analisar soluções similares no mercado e comunidade científica;
2. Pesquisar as técnicas existentes para solução do problema;
3. Desenvolver um sistema capaz de automatizar a elaboração da grade de horários;
4. Testar e avaliar o sistema desenvolvido; e
5. Documentar os resultados apresentados pelo sistema desenvolvido.
1.3 METODOLOGIA
Nesta seção será apresentada a metodologia utilizada na pesquisa.
1.3.1 Metodologia da Pesquisa
O método de pesquisa utilizada no trabalho foi o hipotético-dedutivo, pois se trata de um
problema onde existem conflitos diante das expectativas e soluções existentes para o problema
trabalhado.
A pesquisa sob o ponto de vista de sua natureza foi uma pesquisa aplicada, pois a mesma
resultou em uma ferramenta que pode ser utilizada pela coordenação do curso contemplado.
Sob a forma que o problema foi abordado a pesquisa é do tipo qualitativa, pois se tratou de
um trabalho que vislumbrou a melhora da qualidade do serviço de geração de horário oferecido pela
coordenação do curso contemplado aos professores da instituição.
A presente pesquisa sob o ponto de vista dos objetivos foi uma pesquisa exploratória, devido
ao fato de não existir uma solução padrão para o timetabling, sendo desta forma um problema
aberto a diversos tipos de soluções.
13
1.3.2 Procedimentos Metodológicos
Os procedimentos utilizados no decorrer da presente pesquisa foram a pesquisa bibliográfica
e a pesquisa na internet.
Na biblioteca buscou-se livros que ajudassem no esclarecimento dos assuntos tratados no
decorrer do trabalho.
Já na internet, realizou-se uma busca por artigos científicos, trabalhos de conclusão de curso,
dissertações de mestrado e teses de doutorado capazes de elucidar uma solução para o problema
pesquisado.
Após os passos anteriormente citados, buscou-se criar uma heurística para a geração da
população inicial, já que, vislumbrou-se sempre a geração de indivíduos viáveis desde o inicio do
processo de desenvolvimento do sistema.
1.4 ESTRUTURA DO TRABALHO
O trabalho encontra-se organizado da seguinte forma. Neste capítulo foram apresentados os
problemas de pesquisa, objetivos e metodologia.
No capítulo seguinte será apresentada a fundamentação teórica, com um embasamento a
respeito de timetabling, uma apresentação de métodos existentes para resolução do problema e AG,
que foi a técnica escolhida para se desenvolver a pesquisa.
O Capítulo 3 apresenta uma comparação de trabalhos correlatos com o proposto na presente
pesquisa.
O Capítulo 4 apresentará com os dados do projeto que foi implementado para automatizar a
geração da grade de horários do curso de Ciência da Computação do campus São José da
UNIVALI.
Já o Capítulo 5 apresentará as conclusões referentes à pesquisa.
14
2 FUNDAMENTAÇÃO TEÓRICA
Neste capítulo será apresentado todo o conteúdo necessário à compreensão da pesquisa. Este
capítulo contará com 3 subseções: elaboração da grade de horário ou timetabling, AGs e métodos
para resolução do problema.
Na sequência do trabalho será apresentada a elaboração da grade de horário ou timetabling,
o qual dará embasamento sobre o problema da pesquisa.
2.1 ELABORAÇÃO DA GRADE DE HORÁRIO OU TIMETABLING
Na década de 1960 as pesquisas de Appleby e Gotlieb se tornaram as primeiras pesquisas
sérias que se tem conhecimento sobre a elaboração automatizada de horários acadêmicos (REIS &
OLIVEIRA, 2000; COOPER & KINGSTON, 1996 apud PAIM & GREIS, 2008).
Ainda segundo Paim e Greis (2008) no ano de 1995 foi realizada a primeira conferência
internacional especifica a respeito de elaboração automatizada de horários acadêmicos, Practice
and Theory on Automated Timetabling (PATAT).
No ano de 2002 foi organizada uma competição, a Internacional Timetabling Competition,
pela Metaheuristcs Network. Na competição os participantes deveriam desenvolver programas para
solucionar uma versão simplificada do problema de programação de cursos em universidades. O
vencedor seria o programa que apresentasse a melhor resultado no tempo estipulado. Até a
realização deste evento, era comum publicações compararem os resultados computacionais com os
obtidos manualmente, o que acabava gerando critérios imprecisos (SANTOS & SOUZA, 2007).
O problema da elaboração automatizada de uma grade de horário é constituído do
agendamento de encontros, entre alunos e professores em um período de tempo pré-fixado,
satisfazendo a um grupo de restrições de vários tipos (PAIM & GREIS, 2008).
Schaerf (1995 apud VIEIRA & MACEDO, 2011) classifica o timetabling em três diferentes
grupos: school timetabling, course timetabling, examination timetabling.
A programação de horários em escolas ou school timetabling corresponde, segundo Santos e
Souza (2007), ao problema de programação de horário que encontra-se em escolas do ensino
fundamental e médio. Neste caso, cada professor precisa lecionar um determinado número de aulas
para cada turma em um grupo de períodos. Souza (2000) complementa dizendo que o objetivo
básico é fazer um quadro de horários, em geral semanal, de tal forma que:
1 – As cargas horárias de todas as matérias de todas as turmas sejam cumpridas;
2 – Cada turma não tenha aula com mais de um professor ao mesmo tempo; e
15
3 – Um professor não de aula para mais de uma turma em um mesmo horário.
Na programação de horários de cursos em universidades ou course timetabling, para Santos
e Souza (2007), o conceito de turmas não é tão importante como na programação de horários em
escolas, já que existe a possibilidade dos alunos personalizarem seus currículos. Ocorrendo casos
inclusive de alunos inscreverem-se em disciplinas em mais de um departamento. Para Souza (2000)
o problema é fazer a alocação das aulas dos cursos nos horários disponibilizados, sem ferir as
disponibilidades e capacidades das salas existentes, não permitindo que algum estudante tenha duas
ou mais aulas simultaneamente.
O problema de programação de exames ou examination timetabling é composto por um
grupo de alunos que devem realizar um ou mais exames, os quais precisam ser agendados em um
grupo de períodos que pode se estender por mais de uma semana (SANTOS & SOUZA 2007).
Souza (2000) completa afirmando que o objetivo primário é alocar cada exame a um horário, de
forma que nenhum estudante tenha que fazer dois ou mais exames simultaneamente.
Na seção seguinte será apresentado um cruzamento entre a viabilidade e a otimalidade do
problema.
2.1.1 Viabilidade x Otimalidade
Schaerf (1999 apud PAIM & GREIS, 2008) afirma que o problema típico de horários
acadêmicos é constituído no agendamento de eventos que satisfação um grupo de restrições de
vários tipos, podendo-se classificá-las em dois grupos: hard e soft.
Para Vieira e Macedo (2011) as restrições hard são as restrições que não podem ser violadas
em qualquer hipótese, pois causariam a inviabilidade da grade de horário. Moura et al (2004)
sintetizam afirmando que as restrições hard são aquelas que não podem ser negligenciadas.
Já as restrições soft, são restrições desejáveis, que devem ser preferencialmente seguidas;
sua violação, no entanto, não inviabiliza a solução (VIEIRA & MACEDO, 2011). Moura et al
(2004) complementam garantindo que as restrições soft são aquelas que podem ser violadas, desde
que com parcimônia e quando houver necessidade.
Conforme Souza (2000), os problemas de programação de horário podem ser classificados
em dois tipos, dependendo da necessidade de otimizar ou não uma função objetivo:
1 – Problema de viabilidade: é quando se pretende encontrar apenas um quadro de horários,
viável, ou seja, que satisfaça a todas as restrições hard. (PAIM & GREIS, 2008;
SOUZA, 2000)
16
2 – Problema de otimização: é quando se pretende encontrar dentre todos os quadros de
horários, um que atenda ao grupo de restrições hard e minimizem uma certa função
objetivo, na qual estão incorporadas as funções soft. (PAIM & GREIS, 2008; SOUZA,
2000)
O próximo tópico a ser apresentado no trabalho será o AG, técnica escolhida para solucionar
o problema da pesquisa. Optou-se por esta técnica por ela ser capaz de solucionar problemas
complexos com rapidez e confiança.
2.2 ALGORITMOS GENÉTICOS
Os AGs são algoritmos baseados no princípio da evolução de Charles Darwin. Estes foram
inseridos por John Holland e disseminados por seu aluno David Goldbert (DARWIN 2000,
GOLDBERG 1989, HOLLAND 1975 apud MIRANDA, 2009).
Segundo Lobo (2005), as teorias evolucionárias e a compreensão dos fenômenos da
hereditariedade concretizados a partir dos estudos de Mendel são os elementos-chave para o
desenvolvimento dos AGs. Estes transformam uma população de indivíduos, sendo cada um destes
com seu valor de adaptabilidade, chamado de aptidão, em uma nova geração de indivíduos,
utilizando-se dos princípios de reprodução e sobrevivência dos mais aptos, por meio de operações
genéticas como cruzamento e mutação.
Miranda (2009), completa afirmando que o algoritmo baseado no princípio da seleção
natural simula a criação de soluções, onde novas soluções são geradas a partir de soluções
existentes. Para tanto aplicam-se técnicas de cruzamento e mutação, e seleciona-se os indivíduos
mais fortes para a próxima solução. Desta maneira produz-se sempre uma população melhor que a
anterior, ou seja, mais evoluída.
Na seção seguinte da pesquisa será apresentado um breve histórico sobre o AG.
2.2.1 Histórico
No início da década de 50, diversos cientistas começaram os estudos sobre sistemas
computacionais que visavam imitar a ideia da evolução das populações. Foi o princípio das
pesquisas dos sistemas computacionais evolucionários, acreditando-se que a evolução auxiliaria
como uma ferramenta de otimização para diversos tipos de problemas (LOBO, 2005).
No ano de 1975, John Holland publica o primeiro livro sobre AG, Adaptation in Natural
and Artificial System. O livro reuniu vários trabalhos e ideias que o autor vinha desenvolvendo nos
últimos anos. Já na Alemanha, um outro grupo de pesquisadores, elaboraram uma outra versão de
17
sistema computacional evolucionário, chamada de Estratégias Evolucionárias (BARCELLOS,
2000).
Mitchell, Müller (1996, 2005 apud SKRABE, 2007) afirmam que os estudos apresentavam
similaridade no que diz respeito a ambas usarem um conjunto de soluções candidatas para um
problema e a existência de uma função de aptidão para avaliar se havia uma solução satisfatória.
Outra similaridade encontrada nestas pesquisas era a representação da estrutura de dados, onde são
criadas abstrações de cromossomos biológicos.
A seguir serão apresentadas algumas definições a respeito de AG.
2.2.2 Definições
Os AGs são métodos adaptativos usados para solucionar problemas de busca e otimização.
Eles estão baseados no processo genético e evolutivo dos organismos vivos (COSTA JUNIOR,
1999 apud FERNANDES, 2004).
Russel e Norvig (2004, p. 115) definem AG como:
Uma variação de busca em feixe estocástico, na qual os estados sucessores são gerados pelacombinação de dois estados pais, em vez de serem gerados pela modificação de um únicoestado. A analogia em relação à seleção natural é a mesma que se dá na busca em feixeestocástico, exceto pelo fato de agora estarmos lidando com a reprodução sexuada, e nãocom a reprodução assexuada.
Para Chambers (1996 apud SKRABE, 2007, p. 51) AG é:
Uma técnica de busca matemática baseada nos princípios da seleção natural e recombinaçãogenética [Holland, 1975]. Uma possível solução para o problema é referida como umindividuo. Um individuo é representado por uma estrutura de dados computacionalchamada cromossomo, que é codificada usando um alfabeto de tamanho fixo. Espécies sãoindivíduos com características comuns e nichos são subdomínios do espaço de busca. Porencorajar os nichos e a especiação, os AGs facilitam simultaneamente a convergência paraum ou mais espaços otimizados de busca multimodal.
Segundo Luger (2004, p. 437):
Os Algoritmos Genéticos são baseados numa metáfora biológica: eles veem o aprendizadocomo uma competição numa população de soluções evolutivas, candidatas para o problema.Uma função de “aptidão” avalia cada solução para decidir se ela contribuirá com a próximageração de soluções. Então, através de operações análogas à transferência de genes nareprodução sexual, o algoritmo cria uma nova população de soluções candidatas.
Para Lobo (2005) as principais definições relacionadas aos AGs são:
1 – Cromossomo ou genótipo: cadeia de caracteres, que representam alguma informação
relativa as variáveis do problema, onde cada cromossomo representa uma solução do
problema;
18
2 – Gen ou gene: unidade básica do cromossomo. Os cromossomos são compostos por
um número de genes, cada um deles descrevendo uma variável do problema. Podendo ser do
tipo binário, inteiro ou real;
3 – População: grupo de cromossomos ou soluções;
4 – Fenótipo: cromossomo descodificado;
5 – Geração: número da iteração que o AG executa para gerar uma nova solução;
6 – Operações genéticas: operações realizadas pelo AG nos cromossomos;
7 – Espaço de busca ou região viável: conjunto, espaço ou região que apresenta as
possíveis soluções ou variáveis do problema a ser otimizado. Deve ser caracterizado pelas
funções de restrição que definem a solução viável do problema a ser resolvido;
8 – Função objetivo ou de aptidão: criada a partir dos parâmetros envolvidos no
problema. Estabelece uma aproximação da solução ao conjunto dos parâmetros. A função de
aptidão é calculada para cada indivíduo e fornece o valor a ser usado para o cálculo da
probabilidade de sua seleção na reprodução;
9 – Aptidão bruta: saída da função de aptidão para cada indivíduo da população; e
10 – Aptidão máxima: melhor indivíduo da população.
Na sequência do trabalho será apresentada uma analogia entre o AG e a biologia.
2.2.3 Analogia Biológica
Com os conceitos e definições apresentados até o momento, percebe-se que o AG é uma
analogia a teoria da evolução e a genética, sendo esta, apenas uma simplificação do que ocorre na
natureza (SKRABE, 2007).
Segundo Lobo (2005), os tópicos relevantes à analogia entre a genética e os AGs são:
1 – O vocabulário da genética natural e do AG são o mesmo;
2 – Os cromossomos (população) são atualizados a cada iteração (geração);
3 – Os indivíduos (genótipos) de uma população são representados por cromossomos;
4 – Todo cromossomo (fenótipo) é uma possível solução do problema; e
5 – No processo evolutivo a população de cromossomos é equivalente a uma pesquisa por
meio do espaço de possíveis soluções de um problema.
Na seção seguinte serão apresentados os aspectos principais existentes no AG.
19
2.2.4 Aspectos Principais
Neste tópico serão apresentados os processos que formam um AG. A Figura 1 apresenta o
fluxograma de um AG básico que será detalhado na sequência.
Figura 1. Fluxo do Algoritmo Genético Básico
A seguir será apresentado a primeira etapa do AG básico.
2.2.4.1 População Inicial
A geração da população inicial é a primeira etapa do AG. A população gerada representa um
conjunto de soluções possíveis para o problema, sendo que este conjunto é parte do conjunto de
todas as soluções possíveis existentes (LACERDA & CARVALHO, 1999 apud MIRANDA, 2009).
Conforme Falcone (2004), a população inicial frequentemente é gerada por meio de
procedimentos aleatórios com distribuição uniforme, contudo, também pode-se gerar a população
inicial baseada em heurísticas. Miranda (2009) completa afirmando que devido a todas as
populações geradas posteriormente serem baseadas na população inicial, é importante pensar em
qual(is) característica(s) é(são) interessante(s) que a população inicial tenha, para que não se
reproduzam falhas nas gerações posteriores.
20
Outro fator que deve ser considerado na geração da população inicial é o tamanho de
indivíduos que ela possuirá. Uma população com poucos indivíduos reduzirá o espaço de busca da
solução, e pode diminuir a possibilidade de se chegar a solução ótima. Por outro lado, se a
população de indivíduos for muito grande, o tempo computacional para o processamento da solução
será muito elevado (FALCONE, 2004).
Segundo Silva (2001), existe uma técnica chamada seeding, que constitui-se da introdução
na população inicial de soluções geradas por outros processos de otimização, garantindo desta
forma que a solução gerada pelo AG, seja tão boa quanto a solução gerada pelo outro processo.
Na sequência será apresentado o passo seguinte do fluxo de um AG básico, a avaliação de
aptidão.
2.2.4.2 Avaliação de Aptidão
A avaliação de aptidão ou função de avaliação é a etapa do algoritmo responsável em avaliar
uma população, pontuando cada indivíduo de acordo com sua aptidão. Aos indivíduos considerados
mais próximos da solução ideal é atribuído uma melhor aptidão, de forma que as etapas seguintes
do algoritmo, usem esta informação para gerar sempre indivíduos mais aptos que a população
anterior (MIRANDA, 2009). Leite (2006), completa afirmando que a função de avaliação
demonstra a força de cada indivíduo dentro da população, ou seja, nos diz qual a qualidade da nossa
solução até momento.
Ainda, conforme Leite (2006), a função de avaliação deve ser consideravelmente rápida,
algo típico para métodos de otimização do AG. Devido ao fato do AG trabalhar com soluções
potenciais, incide-se neste o custo de avaliar cada indivíduo da população.
Segundo Falcone (2004) é difícil incorporar ao AG as restrições do problema, ficando
normalmente como responsável pelo gerenciamento das possíveis soluções a função de avaliação.
Conforme Mardle e Pascoe (1999 apud FALCONE, 2004) as restrições causam um impacto muito
maior nos problemas com um pequeno conjunto de soluções, do que aos problemas com um
conjunto grande de soluções. Geralmente a função de avaliação deve determinar o nível de não
factibilidade e otimalidade como uma aptidão estatística.
A seguir será apresentada a etapa de seleção, que é o passo seguinte de um AG básico.
21
2.2.4.3 Seleção
A etapa de seleção normalmente seleciona os melhores indivíduos da população atual para
serem usados na geração da próxima população por meio dos operadores crossover e mutação. Esse
processo de seleção é similar ao processo de seleção natural dos indivíduos, onde os mais adaptados
ao meio tem uma probabilidade maior de reprodução, repassando suas características para a nova
geração (MIRANDA, 2009). Falcone (2004) complementa afirmando que a etapa de avaliação é a
responsável em verificar a aptidão de cada indivíduo da população, relacionando ao indivíduo um
valor de acordo com o critério de otimização escolhido.
De acordo com Leite (2006) os valores retornados pela função de avaliação nem sempre são
apropriados para serem usados como valores de aptidão. É possível por exemplo que uma função de
avaliação retorne um valor negativo, o que inviabiliza a utilização do Método da Roleta, outra
possibilidade é a função de avaliação retornar valores muito próximos tornando o método de
seleção aleatório, outro problema que pode ocorrer entre os problemas advindos do valor da função
de avaliação é que alguns indivíduos podem ter valores muito altos comparados com o resto da
população, tornando desta forma a convergência muito prematura, e etc. Segundo Silva (2001 apud
LEITE, 2006) este problema pode ser evitado mapeando-se a função de avaliação e transformando
seus valores em valores de aptidão.
Os processos de seleção mais comuns são: Seleção da Roleta, Seleção por Classificação,
Seleção por Torneio entre outros.
Seleção da Roleta: O Método da Roleta pode ser descrito fazendo-se uma analogia a roleta
de um cassino, onde cada indivíduo da população tem seu valor de aptidão representado
proporcionalmente ao valor total da aptidão da população, ou seja, quanto maior o valor de aptidão,
maior será a faixa de extensão do indivíduo na roleta e consequentemente maiores as chances deste
ser sorteado (FALCONE, 2004; LEITE, 2006).
A Figura 2 ilustra como é representada a proporção de cada indivíduo no Método da Roleta,
sendo calculada com base na função de avaliação a possibilidade de cada cromossomo ser sorteado
e demonstrando essa possibilidade em percentuais.
22
Figura 2. Representação da proporção de cada indivíduo na roleta
Seleção por Classificação: Na Seleção por Classificação primeiramente classifica-se o
cromossomo de acordo com a função de avaliação e depois se atribui a cada indivíduo da população
um valor de aptidão de acordo com a sua classificação. Nesta classificação o pior indivíduo terá
como valor de aptidão 1, o segundo pior 2 e assim sucessivamente, de tal forma que o melhor
cromossomo terá o valor de aptidão igual ao número de indivíduos da população (LEITE, 2006).
Seleção por Torneio: Neste método os cromossomos são escolhidos de forma aleatória, não
sendo necessária a avaliação da aptidão e nem a ordenação da população (LEITE, 2006).
Segundo Soares (1997 apud FALCONE, 2004) outros métodos de seleção podem ser
encontrados na literatura, entre eles: deterministic sampling, stochastic remainder sampling e
stochastic universal sampling.
De acordo com Nascimento Jr. e Yoneyama (2000 apud MOORI, KIMURA, ASAKURA,
2010) cada método de seleção tem suas vantagens e desvantagens. Devido a isso, deve-se tomar
cuidado com os parâmetros escolhidos para a seleção, não permitindo ao AG convergir rapidamente
a um ponto de alta qualidade, sendo que este não seja o ótimo global, este fenômeno é denominado
na literatura como convergência prematura.
A próxima etapa do AG básico são seus operadores de crossover e mutação.
2.2.4.4 Operadores Genéticos
Esta etapa do algoritmo é a responsável por produzir novos indivíduos de acordo com os
selecionados pelo método anterior. As operações apresentadas a seguir são as mais comumente
usadas na literatura.
23
A Figura 3 mostrada na sequência, apresenta a estrutura de um cromossomo para melhor
compreensão dos operadores genéticos. Onde o conjunto dos genes é o cromossomo, o alelo é o
conteúdo do gene e locus é a posição do gene no cromossomo (MOORI, KIMURA & ASAKURA,
2010).
Figura 3. Cromossomo binário com 10 genes
Fonte: Moori, Kimura e Asakura (2010)
Crossover: O crossover é a parte do algoritmo responsável pela reprodução dos indivíduos,
processo este comparado a reprodução dos seres vivos, onde características dos pais são repassadas
aos filhos. O objetivo do crossover é repassar aos filhos as características mais fortes dos pais,
aproximando cada vez mais a solução do resultado ótimo. A probabilidade do operador de
crossover ser aplicado a qualquer par de cromossomos é denominada taxa de crossover
(MIRANDA, 2009).
A seguir são apresentados alguns tipos de crossover existentes na literatura como os
cruzamentos com um ponto de corte e cruzamento com dois pontos de corte.
Cruzamento com um ponto de corte: seleciona-se um ponto de cruzamento, podendo este ser
fixo ou aleatório, este ponto de cruzamento representa o local de corte do cromossomo, desta forma
o filho1 recebe do pai1 as informações até o ponto de corte selecionado e as demais do pai2 já o
filho2 herda as informações complementares não herdadas pelo filho1. A Figura 4 ilustra o
cruzamento com um ponto de corte.
24
Figura 4. Cruzamento com um único ponto de corte
Cruzamento com dois pontos de corte: similar ao cruzamento com um ponto de corte, só que
com dois pontos de corte. A Figura 5 apresenta o cruzamento com dois pontos de corte.
Figura 5. Cruzamento com dois pontos de corte
Além dos crossover's apresentados detalhadamente, a literatura ainda nos mostra uma vasta
gama de outras formas de realizar o cruzamento entre os cromossomos. Entre estes cita-se o
cruzamento uniforme, cruzamento por variável, cruzamento entre vários indivíduos, cruzamento
aritmético, e etc (FALCONE, 2004; LEITE, 2006; MIRANDA, 2009).
Mutação: Normalmente quando é gerada a população inicial, os cromossomos pertencentes
a ela estão distantes da solução do problema. Devido a isto, é possível que os operadores de seleção
e cruzamento não sejam capazes de fazer as diversificações necessárias na população para encontrar
a solução ótima, tornando a probabilidade de uma convergência prematura muito grande e distante
da solução desejada (LEITE, 2006).
O operador de mutação faz alterações pontuais ao valor do cromossomo, destruindo a
informação anterior e criando uma nova, ou seja, ao contrário do crossover que cria novos
indivíduos, a mutação faz alterações no próprio indivíduo selecionado. Esse processo de
diversificação da população de cromossomos é comparada à mutação no processo evolutivo dos
seres vivos. Devido ao fato do operador de mutação ser um operador destrutivo, deve-se aplicá-lo
25
com uma taxa baixa (taxa de mutação), que geralmente varia entre 0,1% e 5% da população, sendo
isso o suficiente para garantir a diversidade da população (MICHALEWICZ, 1994 apud
MIRANDA, 2009). A Figura 6 ilustra a mutação de um cromossomo.
Figura 6. Mutação do cromossomo
Desta forma, evidencia-se que o operador de mutação influencia de forma importante na
variabilidade das soluções e naturalmente no resultado final do problema. O valor da taxa de
mutação adotado em um problema, depende muito da sensibilidade e experiência do seu operador,
sendo frequentemente necessário que se execute o AG algumas vezes para se calibrar o valor desta
taxa de forma satisfatória (LEITE, 2006).
Na próxima seção será apresentada a última etapa do AG que são os critérios de parada de
execução.
2.2.4.5 Critérios de Parada
Os critérios de parada são os pontos em que o AG deve parar sua execução, sendo estas
condições definidas previamente. Segundo Lobo (2005) são alguns critérios de parada:
1 – Quando se conhecer a resposta máxima da função objetivo;
2 – Quando a aptidão média ou do melhor indivíduo não melhorar mais;
3 – Quando as aptidões dos indivíduos de uma população se tornarem parecidas;
4 – Quando um número pré-estabelecido de gerações for atingido; e
5 – Quando a população não gerar mais diversidade.
Miranda (2009) completa afirmando que um outro critério de parada seria quando 90% à
95% dos cromossomos convergirem para a mesma região, o que indicaria que possivelmente a
população de cromossomos convergiu para uma solução de maior aptidão, ou seja, mais próxima da
solução ótima.
No próximo tópico, serão apresentados alguns métodos existentes para a resolução do
problema proposto.
26
2.3 MÉTODOS PARA RESOLUÇÃO DO PROBLEMA
O problema de automatização da elaboração da grade de horários pode ser resolvido por
muitos métodos. A seguir explica-se algumas possibilidades para resolução do problema.
Souza (2000), em sua tese de doutorado, utilizou-se entre outras metodologias, da Busca
Tabu para chegar a solução perfeita do problema.
A geração inicial da população é realizada de forma construtiva, por um procedimento
parcialmente guloso. Inicialmente determina-se os horários mais críticos, ou seja, aqueles que tem o
menor número de professores disponíveis. Na sequência enumera-se e ordena-se as aulas, dando
prioridade as aulas de maior complexidade para alocação, isto é, as que tem os professores com
maior caga horária e maior quantidade de horários indisponíveis. Forma-se então, uma lista restrita
dos candidatos dessas aulas, selecionando-se uma delas de forma aleatória. Na sequência, procura-
se alocá-la (utilizando-se da ordem de horários críticos) de maneira que não exista nenhum tipo de
inviabilidade (uma turma não pode ter aula com mais de um professor no mesmo horário; e uma
turma não pode ter mais do que X horários de aula da mesma matéria). Caso não seja possível
atender as restrições citadas, admite-se então a violação da segunda. Se mesmo desta forma não for
possível alocar uma determinada aula, admite-se também a violação da primeira restrição. A cada
alocação atualiza-se os horários críticos e as aulas mais difíceis remanescentes.
Com a solução inicial gerada, utiliza-se a Busca Tabu explorando a vizinhança da solução
corrente, por meio de movimentos de troca de dois valores distintos e não negativos de uma dada
linha da solução corrente. Este tipo de movimento pode produzir inviabilidades, contudo essa
solução será rejeitada pela representação escolhida.
Visando prevenir a ocorrência de ciclos, os movimentos realizados pela Busca Tabu são
armazenados em uma lista tabu. Esta lista contém os X movimentos mais recentes, reduzindo a
possibilidade do algoritmo visitar as últimas soluções visitadas anteriormente.
Cada vez que uma solução gerada não apresenta sobreposição, aciona-se o procedimento
Intraturmas-Interturmas, contanto que uma solução de valor igual ainda não tenha sido submetida a
BT-II. Embora soluções com o mesmo valor não sejam necessariamente iguais, esta condição foi
imposta por dois motivos: pela eficiência que o procedimento BT-II apresentou nos testes; e para
que o tempo de processamento do algoritmo não fosse elevado desnecessariamente. Neste ponto o
autor considera duas variantes: BT-II e BT-IIm.
27
Na variante BT-IIm o procedimento continua a busca a partir da solução encontrada em BT-
II. Devido ao fato de BT-II mudar a região pesquisada, inclui-se na lista tabu os movimentos
reversos aos realizados por BT-II caso os movimentos tenham sido de melhora da solução corrente
e nenhuma inviabilidade tenha sido gerada.
Já na variante BT-II, o procedimento de Busca Tabu tem continuidade normal, prosseguindo
a busca a partir do último vizinho gerado. O procedimento BT-II faz uma busca local nas soluções
que estão em seu caminho e atendem a condição de acionamento do procedimento Intraturmas-
Interturmas. Para ser possível a BT-II chegar a este objetivo sem interferir na trajetória do algoritmo
básico, o autor trabalha com uma solução ótima virtual, o que não leva em conta a influencia de BT-
II e é usada para alcançar o valor corrente da função de aspiração.
O autor afirma que os procedimentos BT-II e BT-IIm são acionados apenas uma vez para
cada possível valor que a solução corrente possa assumir.
Souza, Costa e Guimarães (2002) em seu artigo, apresentado no XXII Encontro Nacional de
Engenharia de Produção, elaboraram uma solução híbrida que trabalha com o AG e a Busca Tabu.
Os autores modelaram o cromossomo como uma matriz mxn, onde m é o número de
professores e n o número de horários. Uma célula da matriz representa a situação do professor i no
horário j. As situações supracitadas são representadas da seguinte maneira: se o professor está
disponível recebe um valor infinito, se está indisponível recebe um valor negativo e se está
lecionando recebe um número referente a turma que está lecionando.
A geração da população inicial teve como base a utilizada por Souza (2000), citado
anteriormente. O cruzamento acontece com uma certa probabilidade por meio do crossover. Os
crossover's usados no sistema são o crossover simples e o crossover ordenado, sendo cada um
executado também de acordo com uma probabilidade. No crossover simples, seleciona-se
deterministicamente um ponto de corte, onde o primeiro filho recebe as aulas do primeiro pai antes
do ponto de corte; contudo, as aulas referentes ao segundo pai, antes de serem alocadas passam por
uma verificação de sobreposição. Nos casos em que ocorrem a sobreposição, procuram-se por
horários em que isso não ocorra; se ainda assim acontecer de ter aulas sem alocação, estas são
alocadas aleatoriamente. Já o crossover ordenado, difere do simples pois o ponto de corte acontece
de forma aleatória e antes da operação de corte os quadros são ordenados de acordo com a função
de custo dos professores.
A mutação acontece apenas se for possível reduzir da função de custo do cromossomo. Esta
sucede-se para a programação de um determinado professor escolhido aleatoriamente. A mutação
pode ser de ordem 1, ordem k e dia: a mutação de ordem 1 consiste na troca de genes na
programação do mesmo professor, a mutação de ordem k constitui-se da troca de k genes contíguos
28
da programação de um professor com outro conjunto de k genes contíguos; e a mutação dia, troca a
programação de um dia de um determinado professor.
A função de custo do cromossomo acontece por meio de pesos aplicados as restrições
encontradas, caso a soma dos pesos seja igual a zero a solução é perfeita. A seleção dos indivíduos
que farão parte da próxima geração é feita pelo método da roleta russa.
O algoritmo híbrido proposto pelos autores é um método que a cada geração, o melhor
indivíduo é submetido a um refinamento pelo método de busca tabu.
Lobo (2005), em sua dissertação de mestrado, utilizou-se do AG Paralelo para solução do
problema.
Lobo modelou seu cromossomo como uma matriz de 3 dimensões, de forma que M([Turma]
x [Professor] x [Período]) seja um valor binário. A população inicial é gerada por meio de uma
heurística construtiva buscando atender as restrições fortes. A avaliação de cada cromossomo é
realizada conforme o grau de atendimento das restrições fracas, tendendo a sobreviver os indivíduos
mais adaptados ao meio, ou seja, com maior pontuação.
A mutação acontece com trocas na ordem das disciplinas das turmas entre os períodos
selecionados para participar da operação. O problema na mutação é achar um número X de períodos
que tenham que sofrer mutação. Este valor não pode ser grande, pois causaria uma grande perda de
similaridade com a solução inicial e também não pode ser baixo, pois existe a possibilidade de ser
gerada uma solução idêntica a original.
Na operação de Crossover o autor utiliza-se da teoria de ciclos, fazendo com que as
informações dos pais se completem formando o horário dos filhos de forma completa.
Para realizar o paralelismo no AG, foi utilizado o modelo de ilhas, onde a população é
dividida em subpopulações que são processadas concorrentemente, cada uma responsável por suas
operações. Por meio de processos de migração, os melhores indivíduos de cada ilha podem migrar
para as outras.
Spindler (2010), em sua dissertação de mestrado, utilizou a Busca Dispersa e da Conexão
por Caminhos para resolver o problema.
A Figura 7 apresenta o fluxograma da solução proposta por Spindler em sua dissertação de
mestrado.
29
Figura 7. Algoritmo de Busca Dispersa Implementado por Spindler
Fonte: Spindler (2010)
No Método de Geração Inicial de Soluções Diversas são geradas as soluções iniciais. Tendo
como partida o problema definido, o método agenda as aulas (disciplinas) previstas (número de
disciplinas x carga horária de cada disciplina), agrupando também uma sala e horário. A ordem de
programação das disciplinas acontece de forma aleatória a cada nova geração. Na geração inicial o
algoritmo busca não violar as restrições fortes do sistema. Quando isso não ocorre o sistema leva
em consideração apenas um horário que obedeça a restrição de conflito de alocação de turma. Caso
o conjunto de horários possíveis seja maior que o número de períodos a serem alocados, tem-se a
possibilidade de utilizar duas estratégias: menor alocação e aleatória.
No Método de Melhoria é realizado um sorteio para saber qual o número de vizinhanças que
serão explorados. Os tipos de movimentos existentes são: inserção de sala, realocação de horário,
realocação de horário com inserção de sala, troca de horários, troca de salas e troca de disciplinas.
O Método de Construção de um Conjunto de Referência é uma rotina que seleciona um
conjunto de soluções de referência denominado RefSet, a partir da população inicial. O conjunto
30
RefSet é criado com base nas melhores e mais variadas soluções da população inicial, sendo seu
tamanho consideravelmente menor.
No Método de Geração de Subconjuntos são organizados subconjuntos derivados da
combinação de todos os possíveis pares de soluções de RefSet.
No Método de Combinação são realizadas combinações das soluções encontradas nos
subconjuntos criados pelo Método de Geração de Subconjuntos, adicionando-as a um conjunto
Pool que será avaliado para atualização do conjunto RefSet. O Método de Combinação faz uso de
uma rotina fundamentada na técnica de Reconexão por Caminhos, para encontrar a solução de
melhor qualidade.
O Método de Atualização do Conjunto de Referência tem a função de atualizar o conjunto
RefSet tendo como base as novas soluções geradas. Existem duas possibilidades de atualização do
conjunto RefSet, a primeira é fundamentada na qualidade, usada quando o conjunto Pool contém ao
menos uma solução de custo inferior a melhor solução RefSet, a segunda é baseada na qualidade e
diversidade, utilizada quando o conjunto Pool não oferecer nenhuma solução de custo inferior a
melhor solução de RefSet após duas iterações seguidas.
Subramanian et al (2011) em seu artigo publicado na Revista Produção Online, fizeram uso
da Busca Tabu na solução do problema.
Os autores utilizaram para a geração inicial da população um procedimento construtivo
determinístico. Após a geração inicial, a cada iteração do método é selecionada de forma aleatória
uma determinada aula e executado o melhor movimento de alocação e troca em relação as
vizinhanças. O movimento não tabu dessa vizinhança restrita que obtiver o melhor valor para a
função objetivo será realizado, independentemente dessa solução ser melhor ou pior que a solução
corrente. Um movimento tabu poderá ser realizado caso este produza uma solução melhor que a
gerada até o momento. Realizando-se o movimento, esta aula fica impedida de voltar a sua sala de
origem por X iterações.
Vieira e Macedo (2011) no artigo publicado pela revista Scientia Plena utilizaram o AG
para a solução do problema.
Os autores modelaram o cromossomo de forma que o mesmo contenha todas as turmas a
serem oferecidas no período vigente. Sendo cada gene do cromossomo representado por uma coluna
contendo as informações referentes a turma: disciplina, professor que a leciona, horário da aula e
quantidade de vagas destinadas a cada curso.
A população inicial é gerada com base na lista de todas as turmas que devem ser ofertadas
no período. Para cada indivíduo as informações sobre professor e horário são gerados de forma
aleatória vislumbrando uma variedade maior da população.
31
A avaliação de cada indivíduo é feita por meio do somatório de valores de bonificação e
penalização. Se o indivíduo atender a uma determinada restrição, o mesmo ganha um bônus
associado a um peso pré estabelecido para a mesma. Caso contrário, o indivíduo ganha uma
penalidade com peso pré estabelecido pelo não atendimento da restrição.
A seleção dos indivíduos para o cruzamento é feito por meio do método da roleta russa. Já o
cruzamento é realizado por meio do método single point crossover (cruzamento com um único
ponto de corte), fazendo a seleção do ponto de corte de forma aleatória. Nos exemplos presentes no
artigo, foram utilizadas as taxas de crossover e mutação em 95% e 5% respectivamente.
Existem outras formas possíveis de solucionar o problema da pesquisa. Santos e Souza
(2007) apresentaram no XXXIX Simpósio Brasileiro de Pesquisa Operacional um trabalho
descrevendo algumas formas de solucionar o problema, como Heurísticas baseadas nas Heurísticas
Construtivas e Busca Local, Metaheurísticas utilizando Busca Tabu, Simulated Annealing e
Algoritmos Evolutivos. Souza (2000) em sua tese de doutorado, além da solução apresentada
anteriormente, também apresentou soluções utilizando Greedy Randomized Adaptive Search
Procedure (GRASP), Simulated Annealing, Annealing Microcanônico e Otimização
Microcanônica.
No próximo capítulo serão expostos alguns trabalhos similares ao pesquisado.
32
3 TRABALHOS CORRELATOS
Nesta seção serão apresentados alguns trabalhos semelhantes ao tema pesquisado,
considerando os trabalhos acadêmicos e comerciais.
3.1 ACADÊMICOS
Neste tópico apresentar-se-á algumas ferramentas desenvolvidas no meio acadêmico com o
intuito de resolver o problema de timetabling.
Lucas (2000): O protótipo elaborado por Lucas em seu trabalho de conclusão de curso,
chamado Timetabler, foi desenvolvido com o uso do AG e teve como base a ferramenta GALib por
ter seu código aberto. Segundo o autor, o sistema não tem uma interface muito amigável ao usuário
final e também não leva em consideração todas as restrições necessárias para o problema de
alocação de horário, pois inicialmente tratava-se apenas de um protótipo. Lucas também destaca
algumas características que seriam desejáveis em seu protótipo, são elas: uso de uma base de dados;
uso de restrições complementares e auxílio no processo de matricula.
Jacob e Rocha (2005): O sistema produzido por Jacob e Rocha denominado Aghora, tem o
intuito de reduzir o esforço para gerar a grade de horários. Sendo o sistema baseado no AG, é
permitido ao usuário entrar com o tipo de seleção desejada, taxa de crossover e mutação, assim
como tamanho da população e número de gerações.
O sistema possui dois módulos:
1 – Gerência de informações acadêmicas, onde são inseridas as informações referentes a
instituição, entre elas, professores, cursos e disciplinas; e
2 – Geração de horários, que é o módulo responsável por gerar a grade de horários.
Os autores relatam ao final do trabalho que quanto maior forem as populações e o número
de iterações, maior será o tempo de processamento e melhor será o indivíduo produzido pelo
sistema.
Hamawaki (2005): A ferramenta criada por Hamawaki, denominada Sistema Alocador de
Grade de Horária (AloGra), foi desenvolvida utilizando o pacote Borland C++ Builder 6.0, tem o
gerenciamento do banco de dados realizado por meio do pacote Borland Database Desktop 7.0 e
tem seus relatórios gerados por meio do Quick Report. O sistema usa o AG para gerar a grade de
33
horário e tem o seguinte contexto, um especialista em IA insere os parâmetros do AG, a secretaria
insere as disponibilidades, disciplinas e professores e o sistema retorna a grade horária. O sistema
foi testado com os dados reais do curso de Engenharia Elétrica e segundo o autor apresentou
resultados satisfatórios ao final de sua execução.
Ciscon (2006): O sistema proposto por Ciscon, chamado de AGGH 1.0, foi desenvolvido
em java, tem como sistema gerenciador do banco de dados o MySQL e tem os horários obtidos
exibido em HTML. O sistema que resolve o problema de horários de escolas é baseado no AG.
Como trabalhos futuros o autor citou que seria interessante obter melhorias no AG proposto e
também na aplicação. Ciscon cita como exemplo de melhoria a elaboração de uma heurística para a
geração da população inicial, reduzindo assim o número de indivíduos inviáveis. Outra proposta
para trabalhos futuros identificada pelo autor é o desenvolvimento de uma interface inteligente,
onde o usuário é capaz de fazer alterações no horário fornecido pelo AG e o próprio sistema já
identifica a viabilidade do mesmo.
Preis (2007): O Protótipo Gerador desenvolvido por Preis em seu trabalho de conclusão de
curso foi desenvolvido em java e o gerenciador de banco de dados usado foi o MySQL.
O sistema foi elaborado baseando-se no AG. Neste protótipo é permitido ao usuário
configurar os dados do AG, entre estas configurações é permitido selecionar o número máximo de
gerações, taxa de cruzamento, tipo de cruzamento entre outros.
O autor relata que o sistema funcionou de forma eficaz, sendo que o tempo de execução e
qualidade da solução apresentadas variam de acordo com o tamanho da população, coeficiente de
mutação e número de gerações.
Na próxima seção do trabalho serão apresentadas algumas ferramentas desenvolvidas
comercialmente.
3.2 COMERCIAIS
Neste tópico serão conhecidas algumas ferramentas desenvolvidas de forma comercial.
Phidelis: O Phidelis (http://www.phidelis.com.br) é um sistema web desenvolvido em C#
que trabalha com banco de dados Microsoft Sql Server 2000 ou superior. O sistema possui 5
ambientes entre eles o Portal Administrativo. O Portal Administrativo é utilizado por funcionários
34
da escola, podendo ser acessado por membros da secretaria, tesouraria, coordenações de curso e
diretoria.
Entre algumas das vantagens do sistema apresentadas pela empresa responsável destacam-
se: Segurança de Autenticação e Controle via Níveis de Acesso; Unificação de informações e
gerenciamento de instituições com várias unidades; Processos Acadêmicos (Matrícula,
Cancelamento, Trancamento, Dispensa, Mudança de Turma, Mudança de Unidade, Transferência);
e Configuração Institucional (Cursos, Turnos, Grades Curriculares, Professores, Funcionários).
Lyceum: O Lyceum (http://www.techne.com.br) é um sistema multiplataforma disponível
para internet, smartphone, tablet e TV digital. O sistema realiza tarefas como: a organização dos
cursos, o acompanhamento da execução do projeto pedagógico e a avaliação contínua do
desempenho acadêmico e financeiro.
O sistema efetua o cadastro e a manutenção dos cursos oferecidos pela instituição, sendo
possível incluir critérios para a aprovação nas disciplinas. Também oferece um assistente que
auxilia na montagem da grade curricular dos cursos oferecidos e realiza o agendamento de turmas,
docentes e dependências físicas.
Urânia: Urânia (http://www.horario.com.br) é um sistema desenvolvido pela empresa
GEHA que teve sua primeira versão em 1988. Hoje é utilizado em mais de 7200 instituições de
ensino em todo Brasil.
Entre as funcionalidades do Urânia, destacam-se: determinar os horários em que cada
professor pode dar suas aulas; indicar a forma como as aulas das disciplinas devem ser dispostas na
semana (geminadas, separadas, só uma aula por dia, etc.); elaborar o horário de várias sedes ao
mesmo tempo, controlando o deslocamento dos professores; e trabalhar com duas ou mais turmas,
em conjunto (união de classes).
3.3 ANÁLISE COMPARATIVA
Nesta seção do trabalho tem-se o intuito de fazer uma breve comparação entre as
ferramentas expostas no atual capítulo.
O protótipo desenvolvido por Lucas (2000), deixa clara a necessidade de um sistema
gerador de grade de horários trabalhar com um banco de dados, ou seja, que possibilite armazenar
os dados necessários a elaboração da grade de horários, produzindo a informação desejada.
35
Todos os sistemas acadêmicos apresentados neste capítulo permitem a configuração do AG,
ou seja, o tamanho da população inicial, o número de gerações, a taxa de crossover e mutação,
permitindo desta forma que o usuário calibre o AG de forma a produzir o melhor resultado.
O sistema Urânia é o único sistema que apresenta possíveis soluções para as inviabilidades
encontradas, sugerindo professores que com pequenas alterações em suas disponibilidades podem
viabilizar uma solução. Após ter soluções viáveis o sistema Urânia busca eliminar as janelas
existentes nos horários dos professores.
O problema de janelas não ocorrerá nesta pesquisa pelo fato das aulas serem germinadas, ou
seja, em sequência.
O Quadro 1, mostrado a seguir, apresenta um breve comparativo entre as ferramentas
estudadas e a solução proposta no trabalho.
Quadro 1. Quadro comparativo das soluções correlatas
No próximo capítulo serão apresentados os dados da modelagem do sistema que foi
implementado para solucionar o problema do curso de Ciência da Computação do campus São José
da Universidade do Vale do Itajaí.
Lu
cas
(200
0)
Urâ
nia
Nas
cim
ento
(20
13)
Sistema Comercial X X X
Gera Grade Escolar X ? ? X
Gera Grade Universitária X X X X ? ? X X
Sistema Gerenciador de BD X X X X ? ? ? X
Importação de Dados X
Interface Web X X X X
Jaco
b e
Roc
ha
(200
5)
Ham
awak
i (20
05)
Cis
con
(200
6)
Pre
is (
2007
)
Phi
delis
Lyc
eum
36
4 DESENVOLVIMENTO
Neste capítulo serão apresentadas as informações do sistema que foi implementado. Este
capítulo é composto pelos requisitos funcionais, não funcionais e regras do negócio do sistema,
como também pelo caso de uso, diagrama de sequência, o modelo de relacionamento do banco de
dados e a estrutura do AG que foi implementado.
4.1 REQUISITOS
Neste tópico serão apresentados os requisitos funcionais, não funcionais e regras do negócio
do sistema. Primeiramente serão expostos os requisitos funcionais.
4.1.1 Requisitos Funcionais
Segundo Pfleeger (2004) um requisito funcional descreve uma interação entre o sistema e
seu ambiente. Os requisitos funcionais do sistema são:
RF 01 – O sistema deve permitir ao usuário gerar a grade de horários, sem violar as
restrições de disponibilidade dos professores;
RF 02 – O sistema deve permitir o cadastro de curso;
RF 03 – O sistema deve permitir consultar o curso cadastrado;
RF 04 – O sistema deve permitir editar o curso cadastrado;
RF 05 – O sistema deve permitir excluir o curso cadastrado;
RF 06 – O sistema deve permitir o cadastro de semestres;
RF 07 – O sistema deve permitir consultar os semestres cadastrados;
RF 08 – O sistema deve permitir editar os semestres cadastrados;
RF 09 – O sistema deve permitir excluir os semestres cadastrados;
RF 10 – O sistema deve permitir o cadastro de disciplinas;
RF 11 – O sistema deve permitir consultar as disciplinas cadastradas;
RF 12 – O sistema deve permitir editar as disciplinas cadastradas;
RF 13 – O sistema deve permitir excluir as disciplinas cadastradas;
RF 14 – O sistema deve permitir o cadastro de professores;
RF 15 – O sistema deve permitir consultar os professores cadastrados;
RF 16 – O sistema deve permitir editar os professores cadastrados;
RF 17 – O sistema deve permitir excluir os professores cadastrados;
37
RF 18 – O sistema deve permitir o cadastro da disponibilidade dos professores;
RF 19 – O sistema deve permitir consultar as disponibilidades dos professores cadastrados;
RF 20 – O sistema deve permitir editar as disponibilidades dos professores cadastrados;
RF 21 – O sistema deve permitir excluir as disponibilidades dos professores cadastrados;
RF 22 – O sistema deve permitir o cadastro das configurações do AG;
RF 23 – O sistema deve permitir consultar as configurações do AG cadastradas;
RF 24 – O sistema deve permitir editar as configurações do AG cadastradas;
RF 25 – O sistema deve permitir excluir as configurações do AG cadastradas;
RF 26 – O sistema deve permitir a associação de professores e disciplinas;
RF 27 – O sistema deve permitir a visualização da melhor solução gerada.
A seguir serão apresentados os requisitos não funcionais.
4.1.2 Requisitos Não Funcionais
De acordo com Pfleeger (2004) os requisitos não funcionais descrevem uma restrição no
sistema que limita as opções para criar uma solução para o problema. Os requisitos não funcionais
do sistema são:
RNF 01 – A linguagem de programação utilizada deve ser o Java;
RNF 02 – O Banco de dados utilizado deve ser o MySQL;
RNF 03 – O sistema deve ter interface Web.
A seguir serão apresentadas as regras de negócio.
4.1.3 Regra de Negócio
Na sequência são apresentadas as regras de negócio, sendo que todas dizem respeito ao RF
01.
RN 01 – Procurar não colocar todas as disciplinas de programação no mesmo dia;
RN 02 – Um professor não deve dar mais de uma disciplina para a mesma turma, mas caso
isto ocorra, não devem ser em dias consecutivos;
RN 03 – Um professor não pode dar aula para mais de uma turma no mesmo horário;
RN 04 – Deve-se verificar a disponibilidade do professor para alocá-lo no referido dia;
38
RN 05 – Não permitir quebra de aulas (sempre quatro créditos por dia, exceto para
disciplinas de 6 créditos);
RN 06 – Respeitar o limite diário de aulas de uma mesma disciplina e turma;
RN 07 – Disciplinas com mais de 6 créditos não devem ser em dias consecutivos; e
RN 08 – Um professor só pode ser associado a disciplinas que esteja habilitado a lecionar.
Na próxima seção da pesquisa será apresentada a modelagem do sistema.
4.2 MODELAGEM
Nesta seção será ilustrado como foi realizada a modelagem do sistema, ou seja, o Caso de
Uso, a estrutura do Banco de Dados e o AG. Dar-se-á inicio a apresentação da estrutura do sistema
pelo Caso de Uso.
4.2.1 Caso de Uso
Conforme Fowler (2005), os casos de uso são uma técnica que tem o intuito de captar os
requisitos funcionais de um sistema onde procura-se descrever as interações existentes entre os
usuários e o próprio sistema, demonstrando como o sistema é utilizado.
Na Figura 8 é apresentado o Caso de Uso do sistema que foi implementado na instituição
estudada sendo este, explicado na sequência.
39
Figura 8. Caso de Uso do sistema modelado
CSU 01 – Consulta Curso: neste caso de uso é possível consultar o curso cadastrado. Este
caso de uso atende ao RF 02 e são fluxos alternativos deste caso de uso os RF 03, RF 04 e RF 05.
CSU 02 – Consulta Semestre: neste caso de uso é possível consultar os semestres
cadastrados. Este caso de uso atende ao RF 06 e são fluxos alternativos deste caso de uso os RF 07,
RF 08 e RF 09.
CSU 03 – Consulta Disciplina: neste caso de uso é possível consultar as disciplinas
cadastradas. Este caso de uso atende ao RF 10 e são fluxos alternativos deste caso de uso os RF 11,
RF 12 e RF 13.
CSU 04 – Consulta Professor: neste caso de uso é possível consultar os professores
cadastrados. Este caso de uso atende ao RF 14 e são fluxos alternativos deste caso de uso os RF 15,
RF 16 e RF 17.
40
CSU 05 – Consulta Disponibilidade do Professor: neste caso de uso é possível consultar as
disponibilidades dos professores cadastrados. Este caso de uso atende ao RF 18 e são fluxos
alternativos deste caso de uso os RF 19, RF 20 e RF 21.
CSU 06 – Consulta Configurações do AG: neste caso de uso é possível consultar as
configurações do AG cadastradas. Este caso de uso atende ao RF 22 e são fluxos alternativos deste
caso de uso os RF 23, RF 24 e RF 25.
CSU 07 – Apresentar Melhor Solução: neste caso de uso é apresentada ao usuário a melhor
solução gerada pelo sistema. Este caso de uso atende ao RF 27.
CSU 08 – Gerar Grade de Horário: neste caso de uso é gerada uma grade de horário de
acordo com as informações cadastradas no sistema e as regras de negócio passadas pela
coordenação do curso. Este caso de uso atende ao RF 01.
Na próxima seção do trabalho será apresentado o diagrama de sequência.
4.2.2 Diagrama de Sequência
Com o intuito de elucidar as interações existente no sistema da presente pesquisa, a Figura 9
apresenta o diagrama de sequência da geração da grade de horários.
Nesta ilustração é possível visualizar as atividades que o usuário do sistema executará para
gerar a grade de horário, bem como as atividades que isso acarretará ao sistema.
41
Figura 9. Diagrama de sequência da geração da grade de horário
Continuando a apresentação das informações do sistema, na sequência será ilustrado como
foi estruturado o Banco de Dados.
4.2.3 Banco de Dados
Segundo Date (2004), um sistema de banco de dados pode ser compreendido como um
sistema computadorizado de manutenção de registros, ou seja, um sistema computadorizado para
armazenar informações permitindo aos usuários buscá-las e atualizá-las quando necessário.
Na Figura 10 apresenta-se o Modelo de Relacionamento que foi utilizado no sistema
elaborado para a instituição de ensino estudada, com o intuito de armazenar as informações
necessárias à sua execução, com o intuito de solucionar o problema do curso de Ciência da
Computação do campus São José da Universidade do Vale do Itajaí
42
Figura 10. Modelo de Relacionamento do sistema modelado
A tabela ConfiguracoesAG armazena as informações referentes ao AG, evitando desta
forma que seja necessário que o usuário sempre digite estes dados. Já a tabela FaseSemestre é a
responsável por armazenar os semestres do curso. A tabela Disciplina armazena todas as disciplinas
do curso contemplado pelo sistema, além disso, também constam nesta tabela dois flag`s. Um para
sinalizar se a disciplina deve ser considerada como de programação e o outro identifica se o sistema
deve considerar tal disciplina na hora de montar a grade de horário. O primeiro flag se faz
necessário para atender a RN 01, enquanto o segundo flag atende a especificidade da instituição que
não oferece todas as disciplinas todos os semestres. A tabela Professor guarda os dados referentes
ao professor e a tabela Disponibilidade armazena as preferências do professor no que diz respeito a
sua viabilidade de ministrar aulas, a disponibilidade do professor é identificada da seguinte forma:
se o professor estiver disponível, o dia de disponibilidade receberá o valor 1; se estiver indisponível
este dia receberá o valor 2.
43
Na próxima seção do trabalho será descrita a modelagem do AG.
4.2.4 Algoritmo Genético
Esta seção tem por objetivo descrever o funcionamento do AG do sistema implementado
para solucionar o problema de geração da grade de horário do curso de Ciência da Computação do
campus São José da Universidade do Vale do Itajaí.
O cromossomo do sistema conta com oito semestres, pois é a duração do curso de Ciência
da Computação, e dois horários disponíveis, devido a distribuição das aulas do curso. Cada gene do
cromossomo é composto por disciplina e professor.
Na Figura 11 é apresentada a estrutura do cromossomo modelado.
Figura 11. Representação do cromossomo e dos genes
Com o intuito de facilitar a compreensão da codificação da estrutura do AG, na sequencia do
trabalho será descrito como foi feita a sua codificação.
Sendo o gene a menor parte do cromossomo, o cruzamento entre dia e horário forma o gene
do cromossomo. Já o Alelo é o conteúdo do gene, que está representado na Figura 12, onde são
apresentados os atributos da classe Alelo. Desta forma, percebe-se que cada gene contém a
disciplina e o professor alocados nele.
44
Figura 12. Estrutura do alelo do cromossomo
A Figura 13, apresentada na sequência, ilustra a classe Dia. Onde o alelo_01 representa o
primeiro horário do dia e o alelo_02 representa o segundo horário.
Figura 13. Estrutura do dia do cromossomo
Já a Figura 14, representa o período/semestre do cromossomo, podendo-se verificar na
codificação que a classe Periodo é composta por um ArrayList da classe Dia.
Figura 14. Estrutura do período do cromossomo
A Figura 15, ilustra a classe Cromossomo, onde pode-se verificar que ela é composta por um
ArrayList de Periodo, obtendo assim todos os semestres do curso. Também consta nesta classe o
atributo penalidade, onde é armazenada a quantidade de penalidades do cromossomo e o atributo
resultadoFuncaoAvaliacao, que contém a força do cromossomo calculada por meio da função de
avaliação do AG.
45
Figura 15. Estrutura do cromossomo
População Inicial:
Para a geração da população inicial foi elaborada uma heurística capaz de atender a todas as
restrições hard do problema. Somando-se também nesta heurística a RN 07, devido ao fato que
seria mais complicado manipular o cromossomo posteriormente para atendê-la. São consideradas
restrições hard as Regras de Negócio: RN 03, RN 04, RN 05, RN 06, RN 08, já que estas poderiam
inviabilizar a grade de horário.
A heurística adotada para a geração da população inicial é a seguinte:
1 – Primeiro se busca por professores com baixa disponibilidade para alocá-los. Entende-se
por baixa disponibilidade professores que tenham apenas um dia disponível;
2 – Na sequência são alocadas as disciplinas de seis créditos em dias não consecutivos;
3 – Após a alocação das disciplinas de seis créditos, executa-se novamente o método de
busca e alocação dos professores de baixa disponibilidade;
4 – Na sequência, inicia-se o processo de alocação das disciplinas de quatro crédito de forma
aleatória. Entendendo-se como aleatória, neste caso, que o sistema não varrerá a lista de disciplinas
de forma sequencial. A quantidade de tentativas que o sistema executará o método de alocação
aleatória é escolhido pelo usuário. Este número de tentativas não está associado ao fato que a
alocação das disciplinas sorteadas obterá sucesso. A cada três tentativas de alocação de disciplina,
executa-se o método de busca e alocação dos professores de baixa disponibilidade;
5 – Encerrando o procedimento anterior, o sistema executa novamente o método de busca e
alocação dos professores de baixa disponibilidade;
6 – Após executar o passo anterior, o sistema varre a lista de disciplinas buscando as
disciplinas de quatro créditos que ainda não foram alocadas. A cada três disciplinas de quatro
créditos alocadas, executa-se o método de busca e alocação dos professores de baixa
disponibilidade; e
7 – Terminada a alocação das disciplinas de quatro créditos, o sistema faz uma busca pelos
horários vagos nos semestres, para então encaixar as disciplinas de dois créditos.
46
Avaliação de Aptidão:
A função de aptidão faz a avaliação dos cromossomos baseando-se nas penalidades
encontradas. Já que todos os indivíduos gerados na população inicial são viáveis, a função de
avaliação verifica se os cromossomos atendem as restrições soft do problema, ou seja, as regras de
negócio RN 01, RN 02 e RN 07, buscando-se, desta forma, a solução ótima. Justifica-se a
verificação da RN 07 na função de avaliação, porque embora ela seja atendida na geração da
população inicial, um operador genético pode gerá-la.
A função de avaliação do AG que foi utilizada no sistema proposto é apresentada em (1) e
baseia-se em Preis (2007).
G=1
( Np+1)(1)
Onde G é o grau de aptidão do cromossomo e Np é o número de penalidades, ou seja,
restrições soft encontradas.
Seleção:
O método de seleção escolhido para o AG foi o Método Elitista, pois foi o que melhor se
adaptou ao problema. O Método da Roleta chegou a ser implementado, mas quanto maior sua
população, menor se tornava sua eficácia, já que a margem que o indivíduo ocupava na roleta se
tornava menor e o método, por consequência, aleatório.
O Método Elitista foi implementado da seguinte forma:
1 – Os cromossomos são ordenados de acordo com o valor resultante da função de
avaliação;
2 – Após os cromossomos estarem ordenados, os melhores são automaticamente
selecionados como um dos cromossomos do par que será utilizado no crossover. Entendendo-se
como melhores, os 50% melhor posicionados.
3 – Terminado o passo anterior, são selecionados os outros cromossomos para formar o par.
O segundo cromossomo é selecionado de forma aleatória entre todos os indivíduos da população
excetuando-se o indivíduo já selecionado.
47
Operadores Genéticos:
O operador de crossover aplicado ao AG tem dois pontos de corte, sendo ambos
selecionados randomicamente. O primeiro ponto de corte é entre o segundo e quarto semestre, ou
seja, entre as barras verdes da Figura 16, já o segundo ponto de corte é entre o sexto e o sétimo
semestre, ou seja, entre as barras vermelhas da referida figura.
Figura 16. Pontos de corte do cromossomo
Optou-se por dois pontos de corte para que haja uma maior diversidade entre os
cromossomos gerados nos cruzamentos.
A taxa de crossover a princípio seria selecionada pelo usuário, mas após alguns testes com
os dados reais do curso, verificou-se que a taxa de aproveitamento dos filhos gerados ficou em
aproximadamente 13%. Tal número ficou muito baixo pelo fato de muitos professores lecionarem
diversas matérias no curso de Ciência da Computação, sendo a grande maioria em fases diferentes.
Devido a este fato, a taxa de crossover que inicialmente seria selecionada pelo usuário, passou a ser
sempre 100%.
No processo de mutação, os semestres que serão mutados são selecionados randomicamente.
Ao contrário do crossover, a mutação ocorrerá sempre dentro do semestre, permutando os genes nos
dias da semana, ou seja, trocando, por exemplo, as aulas de terça-feira com quinta-feira no terceiro
semestre. Os dias da semana que são permutados também são selecionados de forma randômica,
buscando desta forma a maior diversidade possível.
Sabendo-se da possibilidade dos operadores genéticos gerarem indivíduos infactíveis, após
cada operação é realizada uma avaliação nos cromossomos gerados para verificar se houve
sobreposição de professor ou se a disponibilidade dos professores continua de acordo com o
cadastrado. Caso isto não ocorra os cromossomos são automaticamente desprezados pelo AG.
Deve-se ressaltar que a mutação além de passar pela supracitada avaliação, só é aceita caso
não haja movimentos de piora, outro dado relevante é que a taxa de mutação será selecionada pelo
usuário e que em testes preliminares a faixa de aproveitamento dos cromossomos mutados ficou em
35%.
48
Outra informação importante sobre a mutação é que embora o comum seja fazer a mutação
apenas nos filhos gerados no crossover, em virtude do aproveitamento deste operador genético ser
tão baixo, a mutação pode acontecer em qualquer indivíduos da população.
Critérios de Parada:
Os critérios de parada utilizados no AG são:
1 – O AG atingir a solução ótima, ou seja, G = 1, maximizando assim a solução;
2 – O número de iterações chegar ao limite pré estabelecido, sendo essa informação
fornecida pelo usuário;
Remoção de Cromossomos da População:
Devido ao baixo aproveitamento do crossover, pensou-se inicialmente em não aplicar a
remoção dos cromossomos. Entretanto, existindo a possibilidade da especificidade encontrada na
instituição de muitos professores que lecionam várias disciplinas ser alterada, causando assim a
inviabilidade do sistema, voltou-se atrás nesta proposta.
Buscando-se justificar a remoção desses cromossomos, a Tabela 1 apresenta os números
gerados pelo AG em 21 iterações sem a exclusão dos indivíduos. Para este processo o tamanho da
população inicial foi de 1000 indivíduos. Neste teste foram usados professores fictícios, permitindo
que cada professor estivesse habilitado para no máximo três disciplinas, viabilizando assim a
geração de uma grade de horário completa.
Diante do exposto evidencia-se que após cada crossover são excluídos os piores
cromossomos da população, mantendo sempre o número de indivíduos de acordo com o parâmetro
de entrada para este critério.
O tamanho da população inicial é selecionado pelo usuário do sistema, quando também
escolherá a taxa de mutação e o número de iterações pretendidas.
49
Tabela 1. Resultados apresentados pelo AG
A Figura 17, apresentada na sequência, ilustra o gráfico de crescimento da população
apresentada na Tabela 1. Pelo gráfico é possível perceber o crescimento exponencial da população,
tornando, desta forma, o processamento computacional muito oneroso. Comprova-se, com isso, ser
inviável para um computador de baixo custo processar esse AG sem que haja a remoção dos
indivíduos.
Já a Figura 18, demonstra a redução da média de penalidades e o aumento da média da
função de avaliação do cromossomo. Comprova-se assim, que mesmo com o aumento exponencial
da população, os indivíduos estão evoluindo, ou seja, demonstra-se que o AG está melhorando a
população de cromossomos.
50
Figura 17. Gráfico da população de cromossomos apresentada na Tabela 1
Figura 18. Gráfico das médias de penalidade e função de avaliação da Tabela 1
Na sequência do trabalho é apresentada a interface do sistema.
51
4.2.5 Interface do Sistema
Este tópico do trabalho tem o intuito de apresentar a interface que foi desenvolvida para a
presente pesquisa.
Vislumbrando-se facilitar a utilização do sistema por parte do usuário final, foi criado um
padrão para as telas de consulta e cadastro.
A Figura 19, apresentada na sequência, ilustra a tela de consulta professor, sendo que, como
mencionado anteriormente, todas as telas de consulta seguem o mesmo padrão. A tela de consulta
apresenta um campo para que o usuário digite o nome do professor que está procurando, também
conta com um ícone para adição de novos professores no canto superior direito. A tabela da tela
apresenta os dados compatíveis com a pesquisa, sendo que por default, quando a tela é aberta, são
apresentados todos os itens referentes a ela. Na tabela figuram alguns dados referentes aos
professores e dois ícones, sendo o primeiro para edição dos dados do item contido naquela linha e
outro para exclusão do item. Na tela de consulta professor são apresentados o nome do professor,
sua matricula, e o código de disponibilidade, sendo este código necessário para a consulta da
disponibilidade do professor.
Figura 19. Tela de consulta professor do sistema desenvolvido
52
A Figura 20 ilustra a tela de cadastro do professor, onde o usuário digita as informações
requisitadas e nos dados referentes a outras tabelas do banco de dados, o usuário deve clicar na lupa
para que seja aberta a tela de consulta do referido item. O item desejado pelo usuário é selecionado
por um duplo clique.
Figura 20. Tela de cadastro professor do sistema desenvolvido
A Figura 21, apresentada na sequência, ilustra a tela onde é visualizado o resultado gerado
pelo sistema desenvolvido. Nesta tela o usuário deve selecionar a configuração do AG pretendido e
o número de tentativas aleatória que será utilizado pelo método de alocação de disciplinas de quatro
créditos de forma aleatória.
53
Figura 21. Tela de apresentação da melhor solução encontrada pelo sistema
Na próxima seção do trabalho é apresentado o design do experimento, ou seja, como foram
os testes e avaliações do sistema implementado.
4.3 DESIGN DO EXPERIMENTO
Almejando que o sistema desenvolvido no decorrer da presente pesquisa seja utilizado pela
coordenação do curso de Ciência da Computação, o mesmo foi testado com os dados reais do curso,
analisando-se, desta forma, sua eficácia na solução do problema.
Com o decorrer dos testes, baseando-se nos dados reais, foi constatado que existe uma
rigidez muito grande na elaboração da grade de horário do curso contemplado. Tal rigidez deve-se
ao fato de que alguns professores da instituição lecionam cinco e até seis disciplinas do curso.
Embora todas estas disciplinas não sejam ofertadas no mesmo semestre, pela quantidade de
disciplinas que esses professores estão habilitados a lecionar, eles ministram de três a quatro
disciplinas no semestre, chegando algumas vezes a até cinco disciplinas.
Devido às especificidades encontradas no curso de Ciência da Computação, também foram
realizados testes com dados fictícios, a fim de melhor testar o sistema. Entendendo-se como dados
54
fictícios, neste caso, o cadastro de novos professores, reduzindo, assim, o número de disciplinas de
cada professor para no máximo três, viabilizando desta forma a geração de uma grade completa.
Para ambos os casos apresentados anteriormente foi realizada uma vasta quantidade de
testes, variando o tamanho da população, o número de iterações, o tipo de seleção, a taxa de
mutação, a remoção ou não dos indivíduos e as tentativas aleatórias para as disciplinas de quatro
créditos.
Outro teste realizado no decorrer da pesquisa foi a comparação dos resultados apresentados
pelo sistema, com a grade atual do curso.
A validação do sistema ocorreu por meio dos resultados apresentados no decorrer dos testes,
com os dados reais e fictícios, sendo ambos considerados satisfatórios.
Na sequência da pesquisa são relatados os resultados encontrados nos testes executados.
4.4 RESULTADOS
Buscando avaliar o sistema da melhor forma possível, foram realizados diversos testes.
Dentre estes, o que teve maior impacto na comprovação da viabilidade do sistema foi a geração de
uma grade de horário simulando os mesmos dados do semestre atual.
A Figura 22 apresenta a grade de horário utilizada neste semestre, onde existem diversas
irregularidades. Dentre elas algumas restrições hard. São restrições hard encontradas na grade de
horário deste semestre: os professores Fabiane e Perfeito estão lecionando na quinta-feira, sendo
que a disponibilidade da primeira é terça e quarta-feira; já a disponibilidade do segundo é segunda e
sexta-feira. Também foram encontradas duas restrições soft, ambas acontecendo na primeira fase.
Uma é que a professora Fernanda ministra duas disciplinas na mesma fase, outra é, que essa
professora leciona na mesma fase em dias consecutivos. Desta forma a grade de horário gerada foi
penalizada duas vezes pela mesma regra de negócio, a RN 02. O Apêndice A apresenta as
disponibilidades de cada professor, podendo-se, desta forma, verificar que seria impossível a grade
de horário não receber estas penalidades, já que o professor de Álgebra tem disponibilidade para
lecionar apenas nas quartas-feiras. No que diz respeito a professora Fernanda ministrar duas
disciplinas para a mesma turma, deve-se a especificidade encontrada na instituição, onde os
professores lecionam muitas disciplinas.
A Figura 23 representa a grade de horário gerada pelo sistema, de acordo com as regras de
negócio apresentadas pela coordenação do curso. Esta grade viola as duas restrições soft
apresentadas na grade de horário atual, já que é impossível pelas especificidades encontradas no
curso de Ciência da Computação, que estas violações não ocorram.
55
Com o intuito de verificar o comportamento do AG, sem que o mesmo esteja tão engessado
pelas especificidades da instituição, comprovando, desta forma, a sua capacidade de gerar uma
grade completa, a Figura 24 ilustra uma grade de horário completa gerada com os dados fictícios. O
AG gerou essa grade com apenas uma restrição soft. A restrição quebrada foi a RN 01, já que na
sexta-feira existem duas disciplinas de programação alocadas. Sabendo-se que existem duas
disciplinas de programação de seis créditos, o que obriga que sejam necessários dois dias para cada
uma, mais duas disciplinas de programação de quatro créditos, precisando desta forma de mais um
dia para cada disciplina, para que não haja tal sobreposição, seriam necessários seis dias distintos, o
que não é possível pelos dias letivos serem de segunda a sexta-feira. Desta forma, esta sobreposição
se torna necessária, tendo o sistema encontrado a melhor solução possível. Os dados fictícios
utilizados para a geração desta grade de horário encontram-se no Apêndice C.
56
Figura 22. Grade de horário utilizada no semestre
57
Figura 23. Grade de horário gerada pelo sistema desenvolvido
58
Figura 24. Grade horária completa
59
A Tabela 2, apresentada na sequência do trabalho, ilustra a evolução da população dos
cromossomos utilizado-se os dados fictícios. Os dados iniciais para processamento do AG que
resultaram nesta tabela foram o seguinte: o tamanho da população foi de 1000 indivíduos, o número
de iterações foi de 50 (mas devido ao fato que a partir da sétima iteração os dados se repetiram,
figuram na tabela apenas as 10 primeiras iterações) a taxa de mutação foi de 5% e por fim o número
de tentativas aleatórias para alocar disciplinas de quatro créditos foi de 15.
O processamento do AG com a entrada destes dados foi de aproximadamente 35 minutos.
Sendo deste tempo, mais de 90% para geração da população inicial. Para tal teste foi utilizado um
computador com um processador Intel Core2 Duo 2.00 GHz e 4GB de memória ram.
Tabela 2. Resultados apresentados pelo AG com dados fictícios
Com o intuito de melhor testar o sistema desenvolvido, foram realizadas baterias de testes,
sendo cada uma destas composta por 100 rodadas. Para tais testes buscou-se simular o aumento do
número de penalidades, alterando-se algumas disponibilidades de professores e classificando mais
disciplinas como disciplina de programação.
Para todos os testes, o tamanho da população foi de 100 indivíduos, o número máximo de
iterações foi de 20 e a taxa de mutação foi de 5%. Alterando-se entre os testes, o número de
tentativas aleatórias para as disciplinas de quatro créditos.
Tendo-se como referencia, o número de tentativas aleatórias para as disciplinas de quatro
créditos, 20 tentativas, os processos chegaram a sua solução final entre 4 e 5 minutos. Com este
parâmetro, chegou-se a melhor solução com o número de iterações ficando entre 8 e 16. A maior
penalidade registrada na primeira iteração foi de 13 e o menor valor apresentado para a maior
penalidade foi de 9.
60
Já, tendo-se como referencia, o número de tentativas aleatórias para as disciplinas de quatro
créditos, 25 tentativas, os processos chegaram a sua solução final entre 4 e 7 minutos. Com este
parâmetro, chegou-se a melhor solução com o número de iterações ficando entre 7 e 15. A maior
penalidade registrada na primeira iteração foi de 13 e o menor valor apresentado para a maior
penalidade foi de 9.
E tendo-se como referencia, o número de tentativas aleatórias para as disciplinas de quatro
créditos, 30 tentativas, os processos chegaram a sua solução final entre 5 e 8 minutos. Com este
parâmetro, chegou-se a melhor solução com o número de iterações ficando entre 7 e 16. A maior
penalidade registrada na primeira iteração foi de 13 e o menor valor apresentado para a maior
penalidade foi de 8.
Nas três últimas baterias de testes apresentadas, o número final de penalidades encontrada
foi 3.
A Tabela 3, apresentada na sequência, ilustra os resultados encontrados nas baterias de testes
detalhados anteriormente.
Tabela 3. Tabela de comparação dos resultados apresentados pelas baterias de testes
Dando continuidade ao trabalho, na próxima seção são apresentadas as conclusões e os
trabalhos futuros.
61
5 CONCLUSÕES
Na presente pesquisa foi solucionado o problema de geração de grade de horário para o
curso de Ciência da Computação do campus São José da UNIVALI. Para chegar ao sistema que
resolvesse de forma efetiva o problema enfrentado pela coordenação do curso, foram necessários
alguns passos.
Primeiro foi necessário pesquisar as técnicas existentes para solução do problema. Diante
desta pesquisa foram encontradas muitas possibilidades. A solução poderia ter vindo por Heurística
Construtiva, Simulated Annealing, Busca Tabu e etc. Entretanto, o trabalho baseou-se no Algoritmo
Genético, acreditando-se em sua capacidade de solucionar problemas NP-Completos.
Após a escolha da técnica que seria utilizada, passou-se a fase de desenvolvimento.
Julgando-se que a melhor forma de se chegar a soluções ótimas seria partindo de uma população
inicial composta apenas por indivíduos factíveis, criou-se uma heurística capaz de gerar tal
população. Por este motivo, a geração da população inicial foi a parte mais árdua do
desenvolvimento do AG. Um fator destacável desta heurística foi seu custo computacional, onde
consegui-se gerar populações com no máximo 3.000 indivíduos.
Quanto ao método de seleção, inicialmente pretendia-se trabalhar com o Método da Roleta,
contudo o Método Elitista apresentou melhor resultado quando se trabalhava com populações
maiores.
Já quanto à mutação, no início da pesquisa, tinha-se a intenção de permitir movimentos de
piora, mas foi detectado no decorrer dos testes que permitir tais movimentos prejudicava o
desenvolvimento da população.
Terminado o desenvolvimento do sistema, iniciou-se a fase de testes com o intuito de avaliar
como o AG se comportaria em produção. Foram realizados testes de diversas formas, com dados
reais e fictícios. De acordo com o esperado, o AG se portou bem diante das avaliações a que foi
submetido. Chegou-se a soluções ótimas na medida do possível, já que nem sempre existe a
possibilidade de se gerar soluções sem qualquer penalidade, como nos casos apresentados na Seção
4.4.
Por fim, com o sistema desenvolvido e testado, procurou-se realizar uma documentação da
forma mais clara possível, viabilizando desta forma a continuidade da pesquisa.
Na seção seguinte do trabalho são apresentadas as propostas para trabalhos futuros.
62
5.1 TRABALHOS FUTUROS
Acredita-se que a presente pesquisa seja apenas o primeiro passo no meio acadêmico, tendo
ainda muito a evoluir.
Um melhoramento que pode ser aplicado à pesquisa é a criação de usuário e senha para que
desta forma os próprios professores possam cadastrar suas disponibilidades, ficando a cargo da
coordenação, apenas a associação dos professores com as disciplinas e a geração da grade de
horário.
Já um fator que justificaria uma pesquisa futura seria que o sistema solucionasse a geração
da grade de horário para mais de um curso, visto que a coordenação do curso de Ciência da
Computação do campus São José é a mesma do curso de Ciência da Computação do campus Ilha e
também do curso de Jogos do campus Ilha. Um fato interessante para esta pesquisa é que os
professores dos campus são os mesmos e os cursos do campus Ilha tem disciplinas equivalentes,
desta forma as aulas destas disciplinas são lecionadas em uma única turma.
Outro fator que poderia gerar uma pesquisa seria criar uma interação entre o resultado
apresentado e o usuário. Desta forma seria possível a coordenação do curso manipular a solução
gerada, tendo o sistema que readaptar a solução encontrada.
63
REFERÊNCIAS BIBLIOGRÁFICAS
ABENSUR, E. O.; OLIVEIRA, R. C. Um Método Heurístico Construtivo para o Problema daGrade Horária Escolar. Revista Eletrônica Pesquisa Operacional para Desenvolvimento, Rio deJaneiro, v. 4, n. 2, p. 230-248, Maio a Agosto de 2012
BARCELLOS, J. C. H. Algoritmos Genéticos Adaptativos: Um Estudo Comparativo. -Dissertação (Mestrado em Engenharia) - Escola Politécnica da Universidade de São Paulo, SãoPaulo, 2000.
CISCON, L. A. O Problema de Geração de Horários: Um Foco na Eliminação de Janelas eAulas Isoladas. TCC (Bacharelado em Ciência da Computação) – UFLA, Lavras, Abril de 2006.
DATE, C. J. Introdução a sistemas de bancos de dados. 8.ed. Rio de Janeiro: ElsevierButterworth Heinemann, 2004.
FALCONE, M. A. Estudo Comparativo entre Algoritmos Genéticos e Evolução Diferencialpara Otimização de um Modelo de Cadeia de Suprimentos Simplificada. Dissertação (Mestradoem Engenharia de Produção e Sistemas) – PUC Paraná, Curitiba, Setembro de 2004.
FERNANDES, A. M. R. Inteligência artificial: Noções Gerais. Florianópolis: Visual Books, 2004.
FOWLER, M. UML essencial: um breve guia para a linguagem-padrão de modelagem de objetos.3. ed. Porto Alegre: Bookman, 2005.
HAMAWAKI, C. D. L. Geração Automática de Grade de Horária Usando AlgoritmosGenéticos: O Caso da Faculdade de Engenharia Elétrica da UFU. Dissertação (Mestrado emCiências) – UFU, Uberlândia, Novembro de 2005.
JACOB, A. F. L. Jr.; ROCHA, C. A. J. AGHORA: Algoritmos Genéticos para Geração de Horáriosde Aula. XIX Semana Paraense de Informática e Telecomunicações – SEPAI e II Congresso deTecnologia da Informação e Comunicação – CTIC. Anais do Congresso... Belém, PA , Setembrode 2005.
LEITE, F. A. P. Análise Inversa de Estruturas com Utilização de Algoritmos Genéticos.Dissertação (Mestrado em Engenharia) – Escola Politécnica da Universidade de São Paulo, SãoPaulo, 2006.
LOBO, E. L. M. Uma Solução do Problema de Horário Escolar Via Algoritmo GenéticoParalelo. Dissertação (Mestrado em Modelagem Matemática e Computacional) – CEFET-MG,Belo Horizonte, Outubro de 2005.
LUCAS, D. C. Algoritmos Genéticos: Um Estudo de Seus Conceitos Fundamentais e Aplicaçãono Problema de Grade Horária. TCC (Bacharelado em Informática) – UFPel, Pelotas, Dezembrode 2000.
LUGER, George F. Inteligência artificial: estruturas e estratégias para a resolução de problemascomplexos. 4. ed. Porto Alegre: Bookman, 2004.
64
MARCONI, M. de A.; LAKATOS, E. M. Metodologia científica. 6. ed. São Paulo: Atlas, 2011.
MARINHO, E. H. Heurística Busca Tabu para o Problema de Programação de Tripulações deÔnibus Urbano. Dissertação (Mestrado em Otimização e Inteligência Artificial) – UFF, Rio deJaneiro, Maio de 2005.
MIRANDA, L. A. Estratégia Paralela Para Alinhamento Múltiplo de Sequências comAlgoritmo Genético Multi-Ilha. Dissertação (Mestrado em Informática) – UNB, Brasília,Setembro de 2009.
MOORI, R. G.; KIMURA, H.; ASAKURA, O. K. Aplicação do Algoritmo Genético na Gestão deSuprimentos. Revista de Administração e Inovação, São Paulo, v. 7, n. 2, p. 171-192, Abril aJunho de 2010.
MOURA, A.; SCARAFICCI, R.; SILVEIRA, R.; SANTOS, V. Técnicas Metaheurísticas Aplicadasà Contrução de Grades Horárias Escolares. XXXVI Simpósio Brasileiro de Pesquisa Operacional –SBPO. Anais do Simpósio... São João Del Rei, MG, Novembro de 2004.
PAIM, A. S.; GREIS, I. C. Abordagens para Elaboração Automatizada de Tabela de HoráriosAcadêmicos. XI Seminário Intermunicipal de Pesquisa. Anais do Seminário... Guaíba, RS,Outubro de 2008. Disponível em <http://www.ulbra.br/guaiba/pesquisa/seminario-de-pesquisa>.Acesso em: 01 ago. 2012.
PFLEEGER, S. L. Engenharia de software: teoria e prática. 2. ed. São Paulo: Prentice Hall, 2004.
PREIS, T. A; Protótipo Gerador de Grades Horárias para Instituições de Ensino. TCC(Graduação em Ciência da Computação) – FURB, Blumenau, Novembro de 2007.
RUSSELL, Stuart J.; NORVIG, Peter. Inteligencia artificial. Rio de Janeiro, RJ: Campus, 2004.
SANTOS, H. G.; SOUZA, M. J. F. Programação de Horários em Instituições Educacionais:Formulações e Algoritmos. XXXIX Simpósio Brasileiro de Pesquisa Operacional – SBPO. Anaisdo Simpósio... Fortaleza, CE, Agosto de 2007.
SILVA, E. E. da Otimização de Estruturas de Concreto Armado Utilizando AlgoritmosGenéticos. Dissertação (Mestrado de Engenharia de Estruturas) – USP, São Paulo, Novembro de2001.
SKRABE, M. S. Proposta de Algoritmo Genético para Aplicação no Problema da GradeHorária. TCC (Bacharel em Sistemas de Informação) – Centro Universitário Feevale, Novembro,2007.
SOUZA, M. J. F. Programação de Horários em Escolas: Uma Aproximação porMetaheurísticas. Tese (Doutorado em Engenharia de Sistemas e Computação) – UFRJ, Rio deJaneiro, Dezembro de 2000.
SOUZA, M. J. F.; COSTA, F. P.; GUIMARÃES, I. F. G. Um Algoritmo Evolutivo Híbrido para oProblema de Programação de Horários em Escolas. XXII Encontro Nacional de Engenharia deProdução – ENEGEP. Anais do Encontro... Curitiba, PR, Outubro de 2002.
65
SPINDLER, M. Uma Proposta de Solução para Problemas de Horário Educacional UtilizandoBusca Dispersa e Reconexão por Caminhos. Dissertação (Mestrado em Computação Aplicada) –Universidade do Vale do Rio dos Sinos, São Leopoldo, Março de 2010.
SUBRAMANIAN, A.; MEDEIROS, J. M. F.; FORMIGA, L. A.; SOUZA, M. J. F. Aplicação daMetaheurística Busca Tabu ao Problema de Alocação de Aulas a Salas em uma InstituiçãoUniversitária. Revista Produção Online, v. 11, n. 1, Março de 2011.
SUCUPIRA, I. R. Métodos Heurísticos Genéricos: Metaheurísticas e Hiper-Heurísticas. USP,São Paulo, 2004.
VIEIRA, F.; MACEDO, H. Sistema de Alocação de Horários de Cursos Universitários: Um Estudode Caso no Departamento de Computação da Universidade Federal de Sergipe. Revista ScientiaPlena, v. 7, n. 3, 2011.
66
APÊNDICE A – DISPONIBILIDADE DOS PROFESSORES
A tabela a seguir apresenta a disponibilidade de cada professor do curso de Ciência da Computaçãodo campus São José da Universidade do Vale do Itajaí. Os dias disponíveis do professor sãopreenchidos com X.
67
APÊNDICE B – RELAÇÃO DAS DISCIPLINAS
A tabela a seguir apresenta a relação das disciplinas, a fase que esta disciplina pertence e o número de créditos presenciais de cada uma.
68
69
APÊNDICE C – DISPONIBILIDADE FICTÍCIA DOS PROFESSORES
A tabela a seguir apresenta a disponibilidade fictícia de cada professor utilizada nos testes. Os dias disponíveis do professor são preenchidos com X.
