SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA APLICAÇÃO DOS ALGORITMOS GENÉTICOS

UNIVERSIDADE FEDERAL DO RECÔNCAVO DA BAHIA

CENTRO DE CIÊNCIAS EXATAS E TECNOLÓGICAS

BACHARELADO EM CIÊNCIAS EXATAS E TECNOLÓGICAS

SOFTWARE DE ESCALONAMENTO DE HORÁRIO

ACADEMICO: UMA APLICAÇÃO DOS

ALGORITMOS GENÉTICOS

MARCOS VINICIUS BIÃO CERQUEIRA

CRUZ DAS ALMAS, 2012

ii







Trabalho de conclusão de curso apresentado à

Universidade Federal do Recôncavo da Bahia como

parte dos requisitos para obtenção do título de

bacharel em ciências exatas e tecnológicas

Orientador : Prof.: Tiago Oliveira Motta

Co-orientador: Prof.: Carlos Frederico Macedo Cortês

MARCOS VINICIUS BIÃO CERQUEIRA


iii







Aprovada em: 12/12/2012

BANCA EXAMINADORA

ASS_____________________________________________________________________

Presidente: Prof° M. SC Tiago Oliveira Motta

ASS_____________________________________________________________________

Membro I: Prof° M. SC Tiago Palma Pagano

ASS_____________________________________________________________________

Membro II: Prof° Dr Carlos Frederico Macêdo Cortes

ASS_____________________________________________________________________

Membro III: Prof° M. Sc. Anderson Leonardo Sanches

Orientador: Prof° M. SC Tiago Oliveira Motta

Graduando: Sr. Marcos Vinicius Bião Cerqueira


iv

AGRADECIMENTOS

Agradeço primeiramente aos meus pais, pois devo a eles a minha educação e

meu sustento.

A Carlos Cortês por me propor esse trabalho e se disponibilizar a me orientar

e a posterior passando minha orientação para Tiago Motta, que me ajudou diversas

vezes e sem ele, não teria conseguido concluir esse projeto.

Não posso esquecer de agradecer aos meus colegas Gabriel, Deise e

Eduardo, amigos desde 2009, mas que com o passar dos semestre, pegamos cada

vez menos disciplinas juntos. A Alex, Ernando e Maiara, companheiros de estudo,

dores de cabeça e de preocupações. Batalhamos para passar em tantas disciplinas.

A Rafael Levi, amigo de longas datas, mais de 10 anos com certeza. Rapaz

bem atrapalhado, mas determinado. Desejo que muitos anos de sucesso estejam

pra vim.

Um agradecimento especial a Luana, o amor da minha vida. Mulher meiga,

carinhosa e amorosa, que com seu jeito cativante me conquistou e eu posso dizer

que sem ela, nada disso seria possível.

Agradeço também aos membros da banca que se predisporá a ler o meu

trabalho e a estarem presentes no dia da defesa para avaliar o mesmo.

Obrigado a todos aqueles que não mencionei, mas que sempre estiveram me

apoiando em todos os momentos

v




SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA

APLICAÇÃO DOS ALGORITMOS GENÉTICOS

RESUMO

A grade de horários é de notável importância para todo corpo docente e discente. Uma vez

que elaborada, terá validade por todo período letivo. Porém o escalonamento desses horários é

de solução não-trivial devido a sua quantidade de variáveis e de quantidade de informações a

serem tratadas. Os Algoritmos Genéticos é um método probabilístico de otimização baseado

nas leis da evolução, onde as soluções mais aptas sobrevivem. O software condensa a solução

do problema em uma cadeia binária, onde essa passara pelos processos evolutivos (seleção,

cruzamento e mutação) até encontrar uma boa solução ou uma que satisfaça o critério de

parada. Para saber se a solução é aceitável, existe a função objetivo que avalia a cadeia

binária, penalizando os erros existentes, fazendo com que os mais evoluídos permaneçam e

gerem filhos melhores a cada nova geração. Com a sobrevivência dos mais aptos, os melhores

indivíduos prevalecerão. É possível que uma geração seja pior que a sua anterior, mas isso é

pouco provável. Para tal projeto, foi feito uma pesquisa bibliográfica, a fim de compreender o

funcionamento dos algoritmos genéticos e a construção de versões beta do software.

Palavras-chave: Escalonamento de horário, Algoritmo genético, Grade acadêmica

vi




SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA

APLICAÇÃO DOS ALGORITMOS GENÉTICOS

ABSTRACT

The grid scheduling is of considerable importance to all faculty and students. Once

drafted, will be valid throughout the school year. But the escalation of these

schedules is non-trivial solution due to its number of variables and amount of

information to be handled. The Genetic Algorithm is a probabilistic optimization

method based on the laws of evolution, where the most suitable solutions survive.

The software condenses the solution of the problem in a binary string, where it

passed by evolutionary processes (selection, crossover and mutation) to find a good

solution or one that meets the stopping criterion. To determine whether the solution is

acceptable, there is the objective function that evaluates the binary string, penalizing

existing errors, making the stay more evolved and better manage children with each

new generation. With the survival of the fittest, the best individuals prevail. It is

possible that a generation is worse than his previous one, but this is unlikely. For this

project, a literature search was done in order to understand the functioning of genetic

algorithms and the construction of beta versions of software.

Keywords: Scheduling time, Genetic Algorithm, academic Grade

vii

Índice

1. Introdução ..................................................................................................... 1

1.1 Justificativa ..................................................................................................................... 2

1.2. Objetivo .......................................................................................................................... 3 1.3. Estrutura do trabalho ................................................................................................... 3

2. Algoritmos Genéticos .................................................................................. 4

2.1. Introdução ..................................................................................................................... 4

2.2 Terminologia .................................................................................................................. 6

2.3. Operadores Genéticos ................................................................................................ 7 2.3.1. Operador de seleção ............................................................................................ 7

2.3.2. Operadores de cruzamento ................................................................................ 8 2.3.3. Operadores de Mutação ...................................................................................... 9

2.4. Elitismo ........................................................................................................................ 10 2.5. Critérios de parada .................................................................................................... 10

2.6. Outras considerações sobre AGs ........................................................................... 10

2.6.1. Reutilização de código ....................................................................................... 10 2.6.2. Os menos aptos também deve ter chance de se perpetuar ........................ 10

3. Estudo de caso ........................................................................................... 12

3.1 – Abordagens iniciais ................................................................................................. 12

3.2 – Complexidades algorítmicas .................................................................................. 13

3.3 – Tipos de restrições .................................................................................................. 16 3.3.1 – Leves .................................................................................................................. 16

3.3.2 – Médias ................................................................................................................ 16 3.3.3 – Severas .............................................................................................................. 17

4. Implementação do sistema ........................................................................ 18

4.1 Banco de dados ........................................................................................................... 18

4.1.1 Tabela de disciplinas ........................................................................................... 18 4.1.1 Tabela de professores ........................................................................................ 20

4.1.1 Tabela de salas .................................................................................................... 21 4.2 Modelagem computacional ........................................................................................ 23

4.3 Inicialização da população ......................................................................................... 25

4.4. Função de avaliação ................................................................................................. 26 4.4.1 Número de aulas .................................................................................................. 26

4.5. Operadores genéticos ............................................................................................... 26 4.5.1 Operador de seleção – Roleta ........................................................................... 26

4.5.2 Operador de cruzamento – crossoverUmPonto ............................................. 27 4.5.3 Operador de mutação ......................................................................................... 27

4.6 Elitismo ......................................................................................................................... 27

4.7 Função de ajuste ......................................................................................................... 28

5. Resultados e Conclusões .......................................................................... 29

5.1 Plataformas de hardware e software ....................................................................... 29

5.2 Análise dos resultados ............................................................................................... 30

6. Conclusão ................................................................................................... 31

6. Trabalhos futuros ....................................................................................... 32

viii

Bibliografia ...................................................................................................... 33

APENDICE A – Diagrama de caso de uso .................................................... 34

APENDICE B – Diagrama de sequencia ....................................................... 35

APENDICE C – Diagrama de classes ............................................................ 43

ix

Índice de figuras

Figura 1- Algoritmo genético básico .......................................................................................... 4

Figura 2- Descrição gráfica dos elementos genéticos com codificação binária ......................... 7 Figura 3-- Exemplo de operador de crossover de um ponto....................................................... 9 Figura 4- Exemplo de operador de mutação ............................................................................... 9 Figura 5- Horário semanal de um estudante ............................................................................. 12 Figura 6- Exemplo de matriz curricular ................................................................................... 13

Figura 7- Tela de cadastro de disciplinas ................................................................................. 19 Figura 8- Tela de atualização de disciplinas ............................................................................. 19

Figura 9– Telas de exclusão de disciplinas .............................................................................. 20 Figura 10- Tela de cadastro de professor.................................................................................. 20 Figura 11- Tela de atualização de professor ............................................................................. 21 Figura 12– Tela de exclusão de professores ............................................................................. 21 Figura 13- Tela de cadastro de sala .......................................................................................... 22

Figura 14- Tela de atualização de sala...................................................................................... 22 Figura 15– Tela de exclusão de salas ....................................................................................... 23 Figura 16- Tela de cadastro de turma ....................................................................................... 24 Figura 17- Representação de cromossomo com disciplina sendo representada por 2 bits ....... 25

Figura 18- Apresentação dos resultados ................................................................................... 30

Figura 19- Apresentação dos resultados ................................................................................... 30 Figura 20– Diagrama de caso de uso ........................................................................................ 34 Figura 21– Diagrama atualiza disciplina .................................................................................. 35

Figura 22– Diagrama atualiza professor ................................................................................... 36 Figura 23– Diagrama Atualiza sala .......................................................................................... 37

Figura 24– Diagrama cadastra disciplina ................................................................................. 37 Figura 25– Diagrama cadastra professor .................................................................................. 38 Figura 26– Diagrama cadastra sala ........................................................................................... 38

Figura 27– Diagrama exclui disciplina ..................................................................................... 39 Figura 28– Diagrama exclui professor ..................................................................................... 40

Figura 29– Diagrama exclui sala .............................................................................................. 41 Figura 30– Diagrama forma horário ......................................................................................... 42 Figura 31– Diagrama de classe ................................................................................................. 43

x

Índice de tabelas

Tabela 1- Possível solução para maximizar f(x)=x² ................................................................. 11

Tabela 2- Representação de 3 turmas ....................................................................................... 24 Tabela 3- Representação de 5 turmas ....................................................................................... 24 Tabela 4- Representação dos slots ............................................................................................ 25

1

1. Introdução

É bastante desejável que a resolução de um problema seja obtida de forma

rápida e robusta. No inicio dos tempos a busca pela solução era feita de forma

intuitiva, mas à medida que os problemas foram tornado-se complexos, a intuição

deixou de ser uma ferramenta utilizável, tendo assim a necessidade de criação de

métodos que indicassem o melhor caminho a seguir.

Atualmente, métodos computacionais são bastante utilizados na resolução

de problemas nas diversas áreas da ciência. Dentre esses métodos computacionais

existe a otimização combinatória. Segundo Ribeiro Filho(2000), a otimização

combinatória se caracteriza pelo tratamento de problemas cujo conjunto de

possibilidades solução é finito e enumerável. Outro método que pode ser utilizado é

a Rede Neural que é inspirado na estrutura neural dos organismos inteligentes que

tem a habilidade de aprender com o ambiente, melhorando assim o seu

desempenho através de processos interativos de ajustes. Uma grande rede neural

pode apresentar centenas de unidades de processamento, uma vez que um cérebro

de um mamífero pode ter bilhões de neurônios. Outra forma é a utilização da Lógica

Fuzzy, apesar desse método não precisar de uma boa aproximação inicial, ela é

uma proposta de dois extremos, ou esta tudo verdadeiro ou tudo falso.

De acordo com Linden (2012), os algoritmos evolutivos dependem de fatores

estocásticos (probabilísticos), tanto em sua fase de inicialização, quanto em sua

evolução. Com isso, é quase impossível que seus resultados sejam perfeitamente

reproduzidos, ou seja, é muito provável fazer a execução do código diversas vezes e

encontrar resultados diferentes. Caso o tempo de execução do algoritmo seja

pequeno, não existe a necessidade de se utilizar algoritmos evolutivos, os métodos

matemáticos são mais eficientes para esse tipo de problema. Entretanto quando

trabalhamos com algoritmos extremamente lentos, onde o espaço de busca é muito

grande, as classes evolutivas são uma excelente ferramenta para a busca de

soluções.

2

1.1 Justificativa

Nesse trabalho será analisado o problema do escalonamento de horários de

disciplinas de graduação do CETEC, Centro de Ciências Exatas e Tecnológicas, da

UFRB, Universidade Federal do Recôncavo da Bahia. Esse tipo de problema é de

difícil solução manual, pois existe um grande número de professores e disciplinas

sendo ministradas no centro, tornando assim muito complicado a tabulação das

informações. A grade de horários é de notável importância para todo corpo docente,

discente e funcionários da instituição, já que uma vez elaborada, ela terá validade

por todo período letivo. O CETEC se encontra atualmente com cerca de 81

professores, sendo que parte do corpo docente atua como suporte a outro centro, o

CCAAB, Centro de Ciências Agrárias Ambientais e Biológicas. Tomando-se uma

média de três disciplinas por professor, totalizando 243 turmas para serem

distribuídas.

Nesse sentido o escalonamento de horários em questão se torna uma tarefa

não-trivial do ponto de vista computacional. Assim, a teoria da complexidade

computacional faz parte da teoria da computação que estuda os recursos

necessários de um algoritmo para resolver um problema. Existem vários tipos de

problemas, dentre os quais se podem citar: N, P e NP - completo. Um problema

pode ser considerado do tipo P se existir um algoritmo polinomial que resolva esse

problema, nesse caso eles são tratáveis. Geralmente são problemas onde envolvem

equações polinomiais simples, como por exemplo, equações lineares. Segundo

Toscani (2001), os assim chamados problemas „NP – Completos‟ são aqueles que

têm a questão da complexidade ou tratabilidade não resolvida, pois não se sabe se

existe ou não algoritmo polinomial que o resolva. Nesse tipo de problema se

encontram equações exponenciais e fatoriais, que com um pequeno número de

entradas se alcançam números muito grandes de cálculos.

A pessoa responsável por esse processo é o Gestor de Ensino. A cada novo

semestre ele deve redefinir os horários, levando em consideração a preferência de

horário dos professores, o tamanho da turma, o tamanho da sala, entre outros. Com

isso, segundo Linden 2012, fica claro que o espaço de busca é demasiadamente

grande, dando que o número de combinações turma/sala/horário é proporcional ao

fatorial do número de turmas e salas, adquirindo assim o caráter de NP - Completo.

3

1.2. Objetivo

O objetivo deste trabalho é criar um software de fácil operação, do qual seja

possível a extração de informações relevantes ao processo de formação da grade

horária, levando em consideração a limitação dos recursos humanos e de infra-

estrutura, utilizando Algoritmo Genético para alcançar uma solução viável.

1.3. Estrutura do trabalho

No capítulo 2 são apresentados e discutidos os fundamentos dos algoritmos

genéticos. No tópico seguinte, mostra-se a dificuldade de se criar uma grade de

horários, mostrando a sua complexidade e as restrições encontradas nesse tipo de

problema. O capítulo 4 apresenta a implementação do sistema, desde sua

modelagem até os métodos utilizados. O capítulo 5 expõe os resultados e a

conclusão obtida por sua análise. Por último e não menos importante, no capítulo 6

é feito sugestões para trabalhos futuros.

4

2. Algoritmos Genéticos

2.1. Introdução

Segundo Cortês(2010), a busca pela otimização de um problema é uma

grande escolha para o melhoramento de suas soluções. A otimização visa

determinar a melhor correlação entre as variáveis para atender os parâmetros e

condições do projeto sem a necessidade de testar todas as possibilidades e,

portanto sem onerar o processo. A otimização vem sendo aplicada em diversos

campos da engenharia, como por exemplo, planejamento, logísticas, análise de

estruturas e formação de horários.

Os Algoritmos Genéticos(AG) são uma classe de algoritmo que visa a

otimização dos problemas com base nos preceitos da genética. Para a evolução da

cadeia de soluções, são usados os operadores genéticos, esses por sua vez, são

divididos em 3 grupos: mutação, seleção e cruzamento. Abaixo se encontra um

pseudocódigo de AG básico:

Figura 1- Algoritmo genético básico

Fonte: Adaptado de Linden,2006

De acordo com Linden (2012), é importante ressaltar que a evolução natural

não é um processo para a obtenção de uma solução ótima. O processo

simplesmente consiste em fazer vários indivíduos competirem entre si pelo processo

de sobrevivência do mais apto, onde os melhores indivíduos tendem a sobreviver.

É possível que uma geração seja pior que a sua anterior, mas isso é pouco

provável.

5

Com a aplicação dos operadores genéticos, novos cromossomos são criados.

Faz-se necessário a utilização de um método de avaliação que faça a seleção. Tem-

se então a função objetivo que “penaliza” o individuo que se encontra em

contradição com a resolução do problema.

Devido à necessidade de implementações mais precisas, problemas mais

complexos são criados para poder suprir a grande demanda imposta pelo mercado e

apesar dos avanços das ferramentas computacionais, não era mais possível contar

com os processos de tentativa e erro.

Percebe-se, então, que a otimização é uma ferramenta importante para a

resolução dos problemas da engenharia. Abaixo se encontra algumas de suas

vantagens e desvantagem:

Vantagens:

- Redução do tempo e custo devido à elaboração do projeto, em um curto

prazo o problema é otimizado;

-Possibilidade de manejo simultâneo de uma grande quantidade de variáveis

e restrições de difícil visualização gráfica ou tabular

Desvantagens:

-Aumento do custo computacional, computadores que rodam esse tipo de

programa necessitam de uma grande quantidade de memória;

-Presença de muitos mínimos locais (o mínimo global é dificilmente obtido);

Na maioria das vezes as soluções encontradas são próximas ao mínimo global

onde satisfazem o método de parada. Além disso, são aplicados a vários tipos de

problemas, já que não impõem limitações encontradas geralmente em outros

métodos de buscas. Algumas vantagens do AG:

São relativamente fáceis de serem implementados;

São flexíveis, é possível utilizar parte do código em outros problemas;

É possível utilizar varias funções-objetivo, mesmo que conflitantes;

Trabalham sobre um conjunto de soluções do espaço de busca em vez de

uma única solução;

Trabalham com múltiplos candidatos à solução ao mesmo tempo, na mesma

geração;

Usam regras probabilísticas de transição;

Pode ser hibridizada com outras técnicas heurísticas.

6

Devido a essas características, os AG mostram ser mais eficientes do que os

métodos tradicionais. Contudo, quando se existe uma boa aproximação inicial, os

métodos matemáticos se mostram mais eficientes devido ao baixo custo

computacional. Daí surgiu novas formas de manejo, onde primeiramente utilizam-se

os métodos probabilísticos e com o refinamento dos resultados, utilizam-se técnicas

matemáticas para redefinir o resultado garantindo um ótimo resultado. (BARBOSA &

LEMONGE 2003).

Segundo Concilio (2000), três condições devem ser consideradas em torno do

processo interativo:

Garantia de convergência;

Tempo de convergência compatível com as necessidades de cada

aplicação;

Convergência para uma solução de boa qualidade.

Quanto mais complexo o problema de otimização e quanto maior o número de

variáveis, menores são as chances das três condições serem atendidas,

principalmente quando o método de otimização aplicado não for poderoso o

suficiente na execução do processo de busca.

A tratabilidade de problemas com alto grau de complexidade, por muitas

vezes, é conseguida abrindo mão de uma solução ótima em prol de uma boa

solução. Como em muitos casos se desconhece a solução ótima, a qualidade

dessas soluções é medida de acordo com as soluções obtidas em outros testes.

2.2 Terminologia

Os seres vivos são constituídos de células que por sua vez são compostos por

cromossomos. Cada indivíduo está presente em sua geração, podendo fazer com

que seus genes sejam passados para a próxima geração. Abaixo temos uma lista

com os termos usado nos AGs.

Cromossomo: Ele é a representação das soluções do problema, como esse

trabalho utiliza a representação binária, o cromossomo nada mais é do que

uma cadeia de 0 e 1;

Gene: Um elemento que indica o cromossomo;

7

Individuo: Junção do cromossomo com sua aptidão;

Aptidão: O quão próximo o cromossomo esta para chegar à melhor solução

do problema;

Genótipo: Informação contida no cromossomo;

Fenótipo: É o cromossomo codificado, em nosso caso, seria a informação de

qual professor estaria em qual sala lecionanda determinada disciplina;

Alelo: Devido à representação binária, seria propriamente o 0 ou o 1;

Epistasia: Interação entre os genes de um cromossomo, ou seja, quando um

gene interferiu em outro;

Geração: Número de ciclos que o algoritmo faz.

Figura 2- Descrição gráfica dos elementos genéticos com codificação binária

Fonte: Adaptado de Cortês, 2010

2.3. Operadores Genéticos

Os operadores genéticos já existentes têm como objetivo gerar novos

indivíduos, mantendo a diversidade cromossomial, permitindo assim que o algoritmo

explore varias regiões do espaço de busca.

2.3.1. Operador de seleção

8

O operador de seleção tem como objetivo escolher aleatoriamente os

indivíduos que passarão para a próxima geração e quais sofrerão as ações dos

operadores. O fator levado em conta para esse tipo de operador é o índice de

aptidão. Seu objetivo é fazer com que os mais aptos permaneçam na população,

gerando descendentes com índice de aptidão ainda melhores, enquanto os outros

indivíduos tendem a desaparecer.

O operador de seleção a ser usado, vai depender muito do problema

analisado. Quanto mais rigoroso for o operador, mais rápido os indivíduos tendem

aos mínimos das funções, em contrapartida sua diversidade é reduzida, dificultando

à exploração de outras regiões do espaço que poderiam ser favoráveis a solução do

problema.

O índice de aptidão está associado à probabilidade de reprodução de um

indivíduo. Logo, este indicador depende do valor da função-objetivo para cada

indivíduo que compõe a população. (LACERDA e CARVALHO, 1999)

2.3.2. Operadores de cruzamento

O cruzamento é um processo onde a partir de dois cromossomos é gerado

um novo, garantindo a diversidade da população.

Para controle de sua ocorrência existe uma taxa de cruzamento pc(ponto de

cruzamento), que limita a possibilidade do cromossomo sofrer o processo. Uma taxa

alta permite uma maior exploração do espaço, porém o tempo computacional é

elevado devido à exploração de áreas não favoráveis.

O cruzamento funciona da seguinte forma: gera-se um número real e

aleatório(entre 0 e 1) para cada indivíduo. Aqueles que tiverem o número menor que

a taxa de cruzamento, serão aplicados os processos de cruzamento adotados no

código, eles são chamados de progenitores. Os resultados dos cruzamentos são

chamados de descendentes.

Segundo Cristina Hamawaki(2005), vale lembrar que o cruzamento de

indivíduos iguais, resultará em um indivíduo igual aos seus progenitores, atrasando

o processo de convergência do algoritmo. Por isso, o método de cruzamento não

deve ser realizado com cromossomos iguais.

9

Figura 3-- Exemplo de operador de crossover de um ponto

Fonte: Adaptado de Cortês,2010

2.3.3. Operadores de Mutação

A mutação é obtida pela mudança aleatória de um gene em um cromossomo

especifico, que também é escolhido aleatoriamente dentre os descendentes da

geração.

Para existir um controle desse operador, existe um limitador chamado de

pm(ponto de mutação). Uma baixa taxa de mutação tende a obter resultados mais

rápidos devido à diminuição da diversidade. Contudo, uma taxa maior acarretaria

uma exploração maior de outras regiões.

Para o funcionamento desse operador, é gerado aleatoriamente um número

entre 0 e 1 para cada alelo. Aqueles que tiverem um número menor que pm sofreram

as ações dos operadores de mutação.

Geralmente se utiliza valores pequenos entre 0,1% a 10%.

Figura 4- Exemplo de operador de mutação

Fonte: Adaptado de Cortês, 2010

10

2.4. Elitismo

Na genética, o filho é gerado a partir da combinação dos cromossomos de

seus pais, fazendo com que apareça um novo indivíduo, porém com isso perdem-se

os indivíduos originais. No AG, o desaparecimento de bons indivíduos é ruim para

atingimos a melhor solução do problema. Portanto De Jong (1975) propôs um

método chamado de elitismo, onde os melhores indivíduos são mantidos nas

gerações seguintes. Alguns pesquisadores da área também chamam esse método

de clonagem.

2.5. Critérios de parada

Em vários casos, demora-se muito a atingir um mínimo global. Em outros

casos ele nem é atingido, faz-se necessário a utilização de um método de parada.

Normalmente os métodos mais utilizados são o número máximo de gerações e o

tempo limite de processamento.

2.6. Outras considerações sobre AGs

2.6.1. Reutilização de código

Os algoritmos genéticos têm a característica de poderem ser reutilizados de

um problema para o outro, simplesmente alterando sua função de avaliação e

buscando novamente a solução. Alguns resultados podem ate ser interessantes,

mas a lógica sugere que não é a melhor abordagem. De acordo com Linden (2012)

quanto mais informações do problema o algoritmo tiver, mais eficiente ele será. A

utilização do algoritmo genético não pode ser uma desculpa para ignorar as

caracteristicas do problema e para a não modelá-lo computacionalmente.

2.6.2. Os menos aptos também deve ter chance de se perpetuar

Charles Darwin não estava errado em dizer que apenas os indivíduos mais

aptos sobreviverão, no entanto isso não exclui a possibilidade tentativa de

11

reprodução de indivíduos menos aptos. Nos algoritmos genéticos não pode ser

diferente, pois existem casos em que um indivíduo com uma baixa aptidão possui

um alelo de vital importância para a otimização do problema. O exemplo é melhor

visualizado na tabela abaixo, onde se utiliza os AGs para maximizar a função f(x) =

x² dentro do intervalo [0,15]. Este é um exemplo puramente explicativo, pois se sabe

de antemão que onde a função é maximizada é 15(1111),

Cromossomo Valor representado Avaliação f(x) = x²

0010 2 4

1100 12 144

0110 6 36

0001 1 1

Tabela 1- Possível solução para maximizar f(x)=x²

O indivíduo 4(0001) tem uma péssima avaliação, porém ele tem um ótimo alelo, que

é o 1 na ultima posição do cromossomo, característica essa que não se encontra

nos dois melhores cromossomos. Logo se utilizar somente os melhores

cromossomos para a reprodução, esse alelo não terá a chance de se perpetuar e

para que ele apareça novamente, ficar-se-ia dependente apenas do processo de

mutação, processo esse com baixa possibilidade de acontecimento, como visto

anteriormente.

12

3. Estudo de caso

3.1 – Abordagens iniciais

Neste trabalho, considera-se como base o curso de Bacharelado em Ciências

Exatas e Tecnológicas e uma de suas terminalidades da UFRB. Ela é formada por

um conjunto de disciplinas, distribuídas ao longo de 10 semestres. Para concluir o

curso, o aluno deve concluir todas as disciplinas de sua matriz curricular.

A cada semestre, as disciplinas são oferecidas em um determinado dia da

semana, onde o aluno poderá se matricular nas disciplinas oferecidas. Porém ele

terá que respeitar o choque de horários e os pré-requisitos dos componentes

curriculares que deseja cursar. Abaixo tem uma figura que exemplifica o horário

semanal de um estudante:

Figura 5- Horário semanal de um estudante

Fonte: Dados da pesquisa

Para uma melhor administração por conta do corpo discente, o curso oferece um

diagrama do fluxo curricular, como ilustra a figura abaixo. Nessa grade já é previsto

o cumprimento de pré-requisitos afim de não comprometer o tempo de conclusão do

curso pelo aluno.

13

Figura 6- Exemplo de matriz curricular

Fonte:http://www.ufrb.edu.br/cetec/index.php/documentos/diversos/84-ppc-

bcet/download

O número de disciplinas por semestre pode varia de acordo com o curso

analisado. Como existe a possibilidade de adiantamento ou atraso de disciplinas por

parte do aluno, existe uma quantidade mínima e máxima de semestre a serem

cursadas.

Segundo Cristina Hamawaki (2005), a criação de uma grade horária em uma

instituição de ensino é uma atividade muito importante, já que depois de elaborada,

ela será utilizada por todo o período letivo. Isto faz com que todos, inclusive o corpo

docente, tenham que se adaptar a esses horários.

3.2 – Complexidades algorítmicas

Algo que não fica explicito aos olhos dos usuários é a complexidade que existe

para se montar uma grade de horários em uma universidade. Para poder definir o

14

tamanho total do nosso espaço, poderia-se aplicar o arranjo simples. O arranjo

simples de n elementos tomado p a p, onde p < n, são diferentes agrupamentos

ordenados que se possam formar com p dos n elementos dados. Eles são

calculados assim:

Equação 1- Formula de arranjo simples

Onde:

Arranjo simples de "a" elementos separados em grupo de p elementos

a Numero total de elementos

p Numero de elementos escolhidos

Porém, esse tipo de raciocínio é aplicado em situações onde a ordem de

alocação é importante, como por exemplo, senhas. Então, nesse caso utiliza-se a

permutação. O conceito de permutação expressa à idéia de que objetos distintos

podem ser arranjados em inúmeras ordens diferentes. Por exemplo, com os

números de um a seis, cada ordem possível produz uma lista dos números, sem

repetições. Ele é dado da seguinte forma:

Equação 2- Formula para permutação simples

Onde:

P Permutação simples de n elementos

n Numero total de elementos

Nesse caso tem-se 243 turmas para serem alocadas em salas de aula.

Supondo que todas as turmas tenham 2 aulas semanais, tem-se um total de 486

aulas distribuídas na semana.

Para primeira alocação tem-se 486 possibilidades, aloca-se uma aula. Na

segunda tem-se 485, aloca-se outra aula, e assim sucessivamente obtendo uma

característica fatorial, como mostra o esquema abaixo.

Equação 3– Exemplo do numero total de possibilidades

Onde: TT Número total de possibilidades

15

A não existência de um método polinomial torna esse problema de difícil

resolução computacional. O fato de ter uma equação fatorial faz com que uma

pequena quantidade de entrada se torne uma quantidade absurda de cálculos a

serem analisados, fazendo com que se gaste um tempo muito grande para

atingirmos uma solução. Por isso esse problema pode ser caracterizado por NP -

Completo.

Olhando agora a parte estrutural, tem-se 23 salas, dentre elas encontram-se 3

tipos diferentes:

Salas convencionais;

Salas de desenho;

Laboratorio de informática.

Inicialmente não diferenciaremos essas salas. Como as aulas podem ser

ministradas no turno da manha e da tarde, tendo 2 aulas em cada turno, tem-se

então um espaço total de 460 alocações para poder serem distribuídas as aulas,

como se pode ver a seguir:

Equação 4- Equação para o numero total de alocações na semana

NA número de alocações

NS número de salas = 23

NADS número de aulas por dia por sala = 4

ND número de dias = 5

Equação 5- Exemplo do caso analisado

De acordo com Lemes Hamawaki, 2005, Frangouli 2002, propôs uma fórmula

para determinar o tamanho máximo do espaço de pesquisa. Essa fórmula pode ser

expressa por:

Equação 6- Equação proposta por Frangouli, 2002

Onde:

16

TEP tamanho do espaço de pesquisa

NDS números de dias letivos na semana

NAD número de aulas por dia

NSA número de salas de aula

ND número de turmas

NAP número de aulas por turma

No caso analisado, têm-se os seguintes valores:

Equação 7- Exemplo do caso, segundo a equação de Fragouli, 2002

Como se pode ver, o número total de possibilidades foi reduzido, mas ainda

é um número elevado.

3.3 – Tipos de restrições

O problema de alocação de aulas é multiobjetivo e sujeito a vários tipos de

restrições, restrições essas que podem ser classificadas em:

3.3.1 – Leves

Geralmente ligadas à preferência do professor. Ele poderá preencher uma

ficha informando quais os horários ele prefere ministrar suas aulas, deixando

horários reservados para suas pesquisas e extensão. As penalidades associadas a

esse tipo de advertência são baixas, já que o professor pode facilmente adequar o

seu horário.

3.3.2 – Médias

São situações de maior complexidade, geralmente ligadas a distribuição

uniforme das aulas. As penalizações envolvidas são de peso médio ou alto, a

depender do caso. Exemplos de restrições médias:

Evitar o professor ministrar aulas todos os dias;

Professores e alunos têm o dia inteiro de aulas;

17

Disciplinas de semestre impar em um turno e de semestres pares em outro

turno;

Uma disciplina dever ter no mínimo um dia e no máximo dois dias entre suas

aulas;

Uma turma deve sempre estar na mesma sala e no mesmo horário e todas as

suas aulas.

3.3.3 – Severas

Esse tipo de restrição verifica a factibilidade do cromossomo, se ele pode ser

aplicado ou não. As penalizações são elevadas, a fim de fazer o cromossomo ser

descartado ao decorrer da evolução, em alguns casos, ele inviabiliza imediatamente

o cromossomo. As restrições abaixo descritas devem ser atendidas em qualquer

sistema de elaboração de grade horária:

Cada turma deve estar presente na grade horária em um número pré-definido

de horas;

Não podem existir dois professores na mesma sala em um mesmo horário;

Nenhum professor pode estar em duas ou mais salas ao no mesmo dia e no

mesmo horário;

Disciplinas de mesmo semestre não devem estar no mesmo dia e horário;

Só pode haver uma disciplina na mesma sala e mesmo horário;

18

4. Implementação do sistema

Para poder implementar a proposta, o algoritmo foi escrito na linguagem Java,

utilizando o ambiente de desenvolvimento Eclipse. Como o Eclipse inicialmente não

possui um gerador de telas foi-se utilizada uma versão não-comecial do plug-in

Jigloo.

4.1 Banco de dados

A aplicação trabalha com uma base de dados previamente elaborada com

base em dados reais. Esses dados se encontram ordenados em tabelas criadas pelo

PostgreSQL. Nestas tabelas temos todos os dados necessários sobre as disciplinas,

professores e salas para o processamento do algoritmo.

4.1.1 Tabela de disciplinas

A tabela de disciplinas se encontra com quatro colunas: nome, código,

semestre e carga horária. As figuras abaixo mostram as telas de cadastro, de

atualização e de exclusão de disciplinas:

19

Figura 7- Tela de cadastro de disciplinas

Fonte: Dados da Pesquisa

Figura 8- Tela de atualização de disciplinas

Fonte: Dados da Pesquisa

20

Figura 9– Telas de exclusão de disciplinas


4.1.1 Tabela de professores

A tabela de Professores é dividida em duas colunas: nome e SIAPE. As

figuras 10, 11 e 12 mostram, respectivamente, as telas de cadastro, de atualização e

de exclusão de professores:

Figura 10- Tela de cadastro de professor


21

Figura 11- Tela de atualização de professor


Figura 12– Tela de exclusão de professores


4.1.1 Tabela de salas

A divisão da tabela de salas é feita em duas colunas: número e tipo. As

figuras abaixo mostram as telas de cadastro, de atualização e de exclusão de sala:

22

Figura 13- Tela de cadastro de sala


Figura 14- Tela de atualização de sala


23

Figura 15– Tela de exclusão de salas


4.2 Modelagem computacional

A modelagem computacional é à base dos algoritmos genéticos. Ele deve ser

o primeiro aspecto a ser definido. Uma modelagem ruim detectada tardiamente pode

apresentar dificuldades em possíveis alterações futuras ou ate obrigar o

programador a refazer o trabalho.

O cromossomo é a representação da possível solução do problema, logo este

deve conter todas as informações necessárias para compor o horário acadêmico.

Em alguns casos, uma disciplina pode ter mais de uma turma, pode existir

mais de um professor responsável para a mesma disciplina.

Assim, a modelagem inicialmente pensada contém as seguintes informações:

Turma, conjunto de professor, disciplina e “turma” ex: professor A, disciplina

Cálculo diferencial e integral I, T02;

Slots, conjunto da sala, dia e horário.

Depois de fazer o cadastro das disciplinas, professores e das salas, é feito o

cadastro das turmas. Na tela de cadastro das turmas, são exibidas duas tabelas,

a dos professores e das disciplinas que foram cadastrados anteriormente. Então

basta selecionar quem será o professor e qual disciplina ele lecionará que ao

criar a turma ele verificará se já existe alguma turma que possua a disciplina que

24

está sendo cadastrada, caso não exista, será atribuído T01, caso já tenha será

atribuído T02, T03, assim por diante.

Figura 16- Tela de cadastro de turma


Ao iniciar a formação dos horários, o algoritmo busca todas as turmas

cadastradas e calcula quantos bits serão necessários para representar todas

elas. Abaixo encontra-se uma tabela onde ilustra a situação.

Tabela 2- Representação de 3 turmas

Número Professor Disciplina Turma Representação

0 --------------- -------------- ------------ 00

1 A Cálculo I T01 01

2 B Cálculo I T02 10

3 A Cálculo II T01 11

Analisando outro caso. Se houver 5 turmas para serem representadas, serão

necessários 3 bits, porém com 3 bits pode-se representar até 7 turmas. A tabela

abaixo mostra como é feita a representação.

Tabela 3- Representação de 5 turmas

Número Professor Disciplina Turma Representação

0 --------------- -------------- ------------ 000



3 A Cálculo II T01 011

4 C Cálculo II T02 100

5 D Cálculo III T01 101



25

Uma vez que todos as turmas já obtiveram uma codificação binária, mas

ainda restam códigos binários sem turma associada, inicia-se o processo de

repetição das primeiras turmas tendo em vista não permitir que códigos fiquem sem

turma relacionada.

O cromossomo é subdividido em slots, onde cada um deles é a representação

do conjunto de dia/sala/horário. A sua divisão é feita de acordo com o numero de

bits necessários para representar o total de turmas cadastradas. Como no primeiro

exemplo acima foi utilizado apenas 2 bits, no cromossomo a cada 2 bits é um slot. A

figura 20 mostra um exemplo de cromossomo, com disciplina sendo representada

com 2 bits, e a tabela 4 mostra a sua codificação.

Figura 17- Representação de cromossomo com disciplina sendo representada por 2 bits

Tabela 4- Representação dos slots

Sala 1 SEG TER QUA QUI SEX

08 as 10 01 01

10 as 12 11 11

14 as 16 10 10

16 as 18

Em um caso real, o número de salas serão maiores, então novas matrizes

serão criadas respeitando essa lógica.

Contudo, nesse trabalho não foi utilizada a representação das turmas, devido

à necessidade de estudo do comportamento dos Algoritmos Genéticos em situações

pouco complexas, para então englobar todas as variáveis do problema em questão,

já que a utilização da variável “Professor” encarretaria no aumento do número de

restrições a serem respeitadas. Em vez disso, o algoritmo busca todas as disciplinas

cadastradas e cria as suas representações binárias. O comportamento dos slots

permanece inalterado.

4.3 Inicialização da população

Para dar início ao processo evolutivo, é necessário inicializar a população

criando vários cromossomos. A quantidade ideal desses cromossomos é parâmetro

bem específico de cada problema, sendo definido melhor através de alguns testes.

26

Ao iniciar o algoritmo, o método inicializaPopulacao() é chamado. A partir dele

dois outros métodos são iniciados tamanhoRepresentacaoDisciplinas(), esse método

calcula a quantidade de disciplinas cadastradas no banco de dados e verifica

quantos bits serão necessários para representar todos eles, e tamanhoVetor(), esse

método ira calcular o tamanho total do vetor binário e o seu retorno será passado

para o construtor do cromossomo.

Os cromossomos são criados de forma aleatória, os bits são gerados de

forma aleatória pelo método Math.random(), já existente na biblioteca do Java. Isso

é uma forma de obter uma boa diversidade, podendo assim, analisar vários pontos

do espaço de busca. Apesar de a inicialização ser aleatória, ela não vai gerar

soluções invalidas (disciplinas que não existem), o que comprometeria toda a

evolução. Isso só foi possível porque para cada representação existente, tem uma

disciplina associada a ele (tabela 3).

4.4. Função de avaliação

Para avaliar o cromossomo, é necessário um conjunto de restrições que

verificam factibilidade do mesmo. Quando uma dessas restrições é violada, o

cromossomo é penalizado com o valor associado a ela. Limitações leves têm baixo

valor de penalização, já restrições severas possuem o peso mais elevado.

4.4.1 Número de aulas

Nessa restrição é analisado se o número de aulas de cada disciplina condiz

com a sua carga horária cadastrada. Como foi suposto, nesse trabalho, que cada

disciplina teria apenas duas aulas semanais, se no vetor binário ela aparecer duas

vezes, a avaliação do cromossomo é acrescida com o valor 100, caso contrario, não

há acréscimo.

4.5. Operadores genéticos

4.5.1 Operador de seleção – Roleta

27

O operador de seleção escolhido foi o método roleta(). Nesse método a

chance de um cromossomo ser escolhido é diretamente proporcional ao valor da sua

aptidão. Pode-se imaginar o seguinte, cada individuo representa uma fração de uma

roleta, roleta essa que se encontra dentro do intervalo [0,1]. É gerado um número

aleatório. O cromossomo que estiver na faixa onde pertence o número sorteado,

será selecionado. Os indivíduos mais aptos conseguirão maiores frações da roleta,

consequentemente, uma maior probabilidade de serem escolhidos e os indivíduos

menos aptos, ainda que seja pequena, terá sua chance de reprodução.

4.5.2 Operador de cruzamento – crossoverUmPonto

O operador de seleção escolhido foi o crossoverUmPonto(). Inicialmente são

selecionados dois pais pelo operador de seleção (pai1, pai2). Logo após é escolhido

aleatoriamente onde será o ponto de corte. Então os dois pais têm sua cadeia de

bits cortada gerando duas cabeças e duas caldas. Este método não irá gerar dois

filhos, apenas um, pois segundo Linden (2012), isso poderia ocasionar um efeito

colateral na hora de preencher um Vector, fazendo com que o retorno do método

seja incompreensível. Nesse caso, o filho gerado pode vir com a cauda do primeiro

pai e a cabeça do segundo ou com a esquerda parte do primeiro pai e a direita do

segundo. Essa escolha é feita de forma aleatória, com 50% de chances para cada

um dos filhos.

4.5.3 Operador de mutação

A diversidade da população é necessária para que novas regiões do espaço

de busca possam ser analisadas, podendo assim encontrar áreas promissoras. Esse

operador origina aleatoriamente um número para cada bit do cromossomo, caso

esse valor seja menor do que a taxa de mutação definida previamente, o bit será

trocado. A taxa de mutação pode ser escolhida pelo usuário, mas foi utilizada uma

taxa de 0.05% nos teste feitos.

4.6 Elitismo

28

O método do elitismo, nesse software, vai selecionar os 10 cromossomos que

tiverem a maior avaliação para serem “clonados” para a próxima geração. Para a

população não crescer sem controle, os operadores genéticos vão funcionar para

gerarem 10 filhos a menos que o número total da população, quando o elitismo

atuar, a nova população apresentará o mesmo número de cromossomos do que a

sua geração anterior, mantendo assim, o número de indivíduos constantes por toda

a evolução.

4.7 Função de ajuste

Como os algoritmos genéticos não buscam uma solução ótima, então foi

preciso certificar que o horário fornecido no final da execução fosse factível. Para

isso, foi criada uma função de ajuste, onde são verificadas quais disciplinas tem

mais de 2 aulas na semana, as aulas excedentes são tiradas do horário. Logo após,

é verificado as disciplinas que tem o numero de aulas menor que o exigido, e então

são acrescentado às aulas que estão em falta.

29

5. Resultados e Conclusões

Este trabalho apresenta os aspectos da utilização dos algoritmos genéticos na

construção de uma grade horária de uma instituição de ensino superior. Procura-se

mostrar a complexidade dos problemas encontrados para a definição de uma boa

elaboração da grade horária, já que, existem múltiplos objetivos, restrições e número

de variáveis elevadas para ser considerado.

A fim de reduzir a complexidade do problema, apenas uma restrição foi

utilizada, o número de aulas durante a semana, assim como o número de variáveis

também foi reduzido, apenas a variável disciplina é levada em conta. O horário é

gerado para 1 sala. Abaixo encontra-se uma descrição do algoritmo

Buscam-se todas as disciplinas cadastradas no banco de dados;

Calculam-se quantos bits serão necessários para representar todas as

disciplinas;

Calcula-se o tamanho total do vetor binário(cromossomo);

Cada representação, da faixa de contagem, é associada a uma disciplina;

Gera-se a população inicial

São aplicados os operadores genéticos;

Exibe a melhor solução

5.1 Plataformas de hardware e software

Com o intuito de manter uma homogeneidade na apresentação dos

resultados, foram mantidos os recursos de hardware e software empregados para

essa fase do programa.

A plataforma de hardware empregada para a experimentação da aplicação

constituiu de um notebook com as seguintes características:

Processador Intel core i5-460M (2.53GHz, 3M L3 cache);

Memória principal de 4GB(utilizável 3,68GB) DDR3

Disco rígido, tecnologia SATAII de 500GB

30

E a plataforma de software foi a seguinte:

Sistema operacional: Microsoft Windows Seven;

Ambiente de desenvolvimento: Eclipse versão Indigo

Banco de dados: PostgreSQL

5.2 Análise dos resultados

A fim de compreender a funcionalidade do aplicativo, foram feitos uma série

de testes desde a implantação das primeiras classes e métodos.

Para a geração da grade horária, foram utilizados dados fictícios, porém

baseados na situação do curso Bacharelado em Ciências Exatas e Tecnológicas da

Universidade federal do Recôncavo da Bahia. Com posso desses dados, o aplicativo

foi executado varias vezes, e a cada execução o resultado era analisado para

verificar a sua convergência.

Para uma melhor exemplificação, as figuras 21 e 22, mostram os resultados

obtidos para uma entrada de 7 disciplinas:

Figura 18- Apresentação dos resultados


Figura 19- Apresentação dos resultados


31

6. Conclusão O software foi desenvolvido para uma instituição de ensino superior que

possui problemas e restrições a serem resolvidas com relação à criação de grade de

horários, que ate então era executado pelo gestor, sem auxilio de uma ferramenta

adequada para a minimização do tempo. Porém, foi implementada apenas a

restrição quanto ao número de aulas semanais.

Assim que a ferramenta for concluída, além de diminuir o tempo requerido

para a confecção da grade horária, amenizaria o esforço por parte do gestor, já que

o mais necessário é a alimentação do banco de dados.

A partir da análise dos resultados obtidos, pode-se concluir que as técnicas

que foram implementadas possuem resultados satisfatórios, simplificando os

procedimentos, utilizando métodos heurísticos de evolução.

Para a principal contribuição desse trabalho, pode-se mencionar o estudo de

técnicas evolutivas, em conjunto com problema de restrições, vindo com uma

solução para o problema de alocação de salas.

32

6. Trabalhos futuros

Este trabalho contribuiu para o estudo da aplicação dos algoritmos genéticos

na construção de grades de horário acadêmica. Porém as possibilidades de

pesquisa e desenvolvimento desse aplicativo não foram esgotadas. Sugerem-se

então novos trabalhos para que possam ser realizados para ampliar o conhecimento

e na obtenção de uma versão final do aplicativo. Dentre as possibilidades de

pesquisa, pode-se citar:

O acréscimo de novas restrições, a fim de que a solução seja de

agrado a um maior número de pessoas;

A utilização de todas as variáveis (disciplina, professor, sala);

O melhoramento do tempo de execução.

33

Bibliografia

BARBOSA, H. J., & LEMONGE, A. C. (2003). A New Adaptive Penalty Scheme for Genetic

Algorithm. Information Sciences , 215-251.

CONCILIO, RICARDO (2002). Contribuições à Solução de Problemas de Escalonamento

pela Aplicação Conjunta de Computação Evolutiva e Otimização com Restrições . Campinas,

São Paulo, Brasil.

Cortês, CARLOS FREDERICO, (Março de 2010). OTIMIZAÇÃO DO PROJETO DA

SUPERESTRUTURA DE PONTES PRÉ-FABRICADAS PELO MÉTODO DOS

ALGORITMOS GENÉTICOS . Rio de Janeiro, Rio de Janeiro, Brasil.

De JONG, KENNETH ALAN. (1975). An Analysis of the Behavior of a Genetic Adaptive

System . Arbor, USA.

Filho, GERALDO RIBEIRO (6 de dezembro de 2000). MELHORAMENTOS NO

ALGORITMO GENÉTICO CONSTRUTIVO E NOVAS APLICAÇÕES EM PROBLEMAS DE

AGRUPAMENTO . São José dos Campos, São Paulo, Brasil.

Hamawaki, CRISTINA DIVINA. (Novembro de 2005). Geração automatica de grade

horaria usando algoritmo genetico: O caso da faculdade de engenharia eletrica da UFU .

Uberlandia, Minas Gerais, Brasil.

LACERDA, E. G., & CARVALHO, A. C. (1999). Introdução aos Algoritmos Genéticos . Rio

de Janeiro, Brasil.

Linden, RICARDO. (2006). Algoritmos Geneticos. Rio de Janeiro: Ciencia Moderna.

Toscani, LAIRA VIEIRA (2002). Complexidade de Algoritmo. Porto Alegre: Sagra Luzzato.

34

APENDICE A – Diagrama de caso de uso

Figura 20– Diagrama de caso de uso


35

APENDICE B – Diagrama de sequencia

Figura 21– Diagrama atualiza disciplina


36

Figura 22– Diagrama atualiza professor


37

Figura 23– Diagrama Atualiza sala


Figura 24– Diagrama cadastra disciplina


38

Figura 25– Diagrama cadastra professor


Figura 26– Diagrama cadastra sala


39

Figura 27– Diagrama exclui disciplina


40

Figura 28– Diagrama exclui professor


41

Figura 29– Diagrama exclui sala


42

Figura 30– Diagrama forma horário


43

APENDICE C – Diagrama de classes

Figura 31– Diagrama de classe


Documents

SOFTWARE DE ESCALONAMENTO DE HORÁRIO ACADEMICO: UMA APLICAÇÃO DOS ALGORITMOS GENÉTICOS