Slides TCC 2015.1 - UNICAP - Aplicações de Algoritmos Genéticos em Otimização de Horários

APLICAÇÕES DE ALGORITMOS GENÉTICOS EM OTIMIZAÇÃO DE

HORÁRIOS

Orientando: Philippe Norbert Cavalcanti AussourdOrientadora: Clarissa Daisy da Costa Albuquerque

Roteiro da Apresentação O problema do Timetabling

O caso do curso de Ciência da Computação da UNICAP

Computação Natural

Algoritmos Genéticos

Sistemas Automatizados para Resolução de Timetabling em Instituições de ensino usando Algoritmos Genéticos

Conclusão e Sugestões de Trabalhos Futuros

O PROBLEMA DO TIMETABLING

O problema do Timetabling O que é Timetabling ?

Problema de alocação de recursos, sujeito a restrições num espaço de tempo, de modo a satisfazer o maior numero de objetivos desejáveis.

Problema NP-Completo Importância na área Científica

PATAT (Practice and Theory of Automated Timetabling)

EURO (Association of European Operational Research Societies)

WATT (Working Group on Automated Timetabling)

ITC (International Timetable Competition) Aplicações Características do Timetabling em Instituições de

Ensino Course Timetabling Examination Timetabling School Timetabling University Timetabling

O CASO DO CURSO DE CIÊNCIA DA COMPUTAÇÃO DA UNICAP


Grade Horária do Curso Noturno

HorárioDia da Semana

Segunda-feira Terça-feira Quarta-feira Quinta-feira Sexta-feira

NO18:30-20:10

- - - - -

PQ20:20-22:00

- - - - -


Número de possibilidades por turma: (

Soluções possíveis: = 3,854 x 1030

Algoritmo forca bruta (1 ms p/ solução) 3,854 x 1030 ms Em anos = 1,22 x 1020 anos

O que mostra o trabalho e inteligência dos funcionários que resolvem o problema manualmente e a importância da automatização do processo de produção de grade horárias

Turma NS3 NS4 NS5 NS6 NS7 NS8 NS9

Número de Professores 5 5 5 5 4 5 5

Total de Possibilidades 30240 30240 30240 30240 5040 30240 30240


Restrições e particularidades Colisão por professor (Turmas NS3 e NS4)


Segunda-feira Terça-feira Quarta-feira Quinta-feira Sexta-feira

NO18:30-20:10

Circuitos Dig. /

Madeiro

Est. Dados I / Ana

- - -

PQ20:20-22:00

- - - - -


Segunda-feira Terça-feira Quarta-feira Quinta-feira Sexta-feiraNO

18:30-20:10-

Est. Dados II / Ana

- - -

PQ20:20-22:00

Mét. Numéricos /

Bertino- - - -


Restrições e particularidades Horários Esparsos

NS5 Segunda-feira

NO18:30-20:10

-

PQ20:20-22:00

Paradig. Ling de Prog. / TJ


Restrições e particularidades Blocos de Disciplinas

2NO-4NO, 2PQ-5PQ, 3NO-6NO, 3PQ-5NO, 4PQ-6PQ

Preferência dos Professores


Segunda-feira Terça-feira Quarta-feira Quinta-feira Sexta-feiraNO

18:30-20:10INF1701Márcio

INF1720Antônio

INF1701Márcio

INF1224Márcio

INF1720Antônio

PQ20:20-22:00

INF1218Mozart

INF1224Márcio

INF1617Rubens

INF1218Mozart

INF1617Rubens

COMPUTAÇÃO NATURAL



Computação com mecanismos

naturais

Estudos sobre a natureza através da computação

Computação inspirada na

natureza

ALGORITMOS GENÉTICOS

Algoritmos Genéticos Origem e Definição

Herança genética Genética Populacional Favorecimento de indivíduos melhores adaptados, com maior possibilidade de perpetuação do

seu código genético Os Algoritmos Genéticos constituem uma técnica de busca e otimização inspirada no princípio

Darwiniano de seleção natural e na reprodução genética os cromossomos são então submetidos a um processo que inclui avaliação, seleção e recombinação sexuada (crossover) e mutação

Charles Darwin Alfred Wallace Gregor Mendel John Holland


Aplicações Otimização Combinatorial Otimização em Negócios


Terminologia BiológicaMeio Função

Objetivo F(x) = x³ Aptidão = 216

Indivíduo Candidato a Solução Fenótipo = 6

Genótipo

Gene

Alelo

População Conjunto de Candidatos a Solução


Algoritmo Genético Genérico

Algoritmo Genético genérico

Inicialize a população de cromossomos (geração i=1)

Avalie indivíduos na população (função objetivo e sobrevivência)

Repita (evolução)

Selecione indivíduos para reprodução

Aplicar operadores de recombinação e/ou mutação

Avaliar indivíduos gerados na população

Selecione indivíduos para sobreviver (geração i=i+1)

Até máximo de gerações ou objetivo final

Fim


Seleção Método da Roleta Método de Seleção por Torneio Mapeamento de Função Objetivo

Escalonamento Linear

1234

1 x 3 1

3 x 2 2

4 x 2 4

fmax

f

gmin g gmax

fmin

bagf


Crossover Crossover em um ponto

Crossover em dois pontos

Taxa de Cruzamento: 60% - 80%

CROMOSSOMO 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1

CROMOSSOMO 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0

CROMOSSOMO 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0

CROMOSSOMO 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1

Algoritmos Genéticos Mutação

Individuo Número Aleatório Novo Individuo

Taxa de Mutação: 0,5% - 1%

Tamanho da População Condições para Término

1 0 1 1 0,564 0,951 0,175 0,457 1 0 1 1

0 1 1 0 0,234 0,783 0,009 0,841 0 1 0 0

0 0 0 1 0,322 0,007 0,290 0,642 1 1 0 1

SISTEMAS AUTOMATIZADOS PARA RESOLUÇÃO DE TIMETABLING EM INSTITUIÇÕES DE ENSINO

USANDO ALGORITMOS GENÉTICOS

Sistemas Automatizados para Resolução de Timetabling em Instituições de ensino usando

Algoritmos Genéticos Foram analisados dez trabalhos nessa monografia, sendo analisado os seguintes itens em comum:

Objetivos Modelagem do problema Representação da solução Restrições Criação da população inicial Avaliação da População Método de Seleção Operadores Critério de parada Resultados

Dentre esses dez, três foram escolhidos para serem mostrados nesta apresentação. Como conclusão, cinco características foram elencadas para estatística:

Representação da Solução Tamanho da População Função de Aptidão Operadores Critério de parada


Algoritmos Genéticos Desenvolvimento de um Algoritmo Genético para a resolução do

Timetabling Timóteo, G. T. S (2002) – UFLA

Objetivos Implementação de AG para Timetabling, analisar seu comportamento

através de testes. Modelagem do problema

Modelo usando AG para o problema da escola Nossa Senhora de Lourdes em Lavras-MG.

Representação da solução


Algoritmos Genéticos Restrições

Colisão por professor Horários esparsos Blocos de disciplinas Vários blocos por dia Média de aulas por dia Preferências dos professores

Criação da população inicial Geração Aleatória

Percorre uma lista de uma turma e sorteia para cada slot. Geração Heurística

Seleciona em blocos de duas.


Algoritmos Genéticos Avaliação da População

Método de Seleção Roleta Giratória Torneio Roleta com Redução

Cada vez que um individuo for selecionado sua aptidão é reduzida.

Operadores Crossover em um ponto, em dois e heurístico com corte em um ponto Mutação aleatória num indivíduo apenas e heurística (Dupla)

Critério de parada Limite máximo de gerações

Resultados Baseado nos testes, observou-se que o método de seleção por torneio, o operador de

crossover com corte em um ponto e operador de mutação comum foram os que apresentaram maiores resultados.


Algoritmos Genéticos Sistema de Alocação de Horários de Cursos Universitários:

Um Estudo de Caso no Departamento de Computação da Universidade Federal de Sergipe F. Vieira; H. Macedo (2011) – UFS

Objetivos Descrever o sistema de geração automática de grade de horários

para atender as necessidades do Departamento de Computação da UFS.

Modelagem do problema O Departamento possui 28 professores, 3 cursos e 650 alunos entre

três turnos. Representação da solução



Hard Todas as disciplinas ofertadas devem preencher o número de horas por semana estabelecidas

pelo currículo. O professor não pode lecionar em duas turmas diferentes num mesmo dia e horário. Aulas de uma mesma turma não devem acontecer em um mesmo dia e horário. Todas as disciplinas obrigatórias do período atual devem ser ofertadas. A oferta das disciplinas deve obedecer ao turno dos cursos.

Soft Todas as aulas de uma turma devem ser ofertadas, preferencialmente num mesmo horário

durante a semana. Aulas de uma mesma turma não devem ser ofertadas em dias seguidos, nem em um único

dia. A preferencia do professor em optar por lecionar apenas disciplinas de seu interesse deve ser

respeitada

Criação da População Inicial Os indivíduos da população inicial foram criados com base na lista de todas as turmas que devem

ser ofertadas no período vigente. Informações sobre professores e horários da disciplina são geradas aleatoriamente. O professor é adicionado através da lista oficial de docentes do departamento e o vetor de horários é preenchido através de valores inteiros pré-definidos.



Método de Seleção Roleta Giratória

Operadores Crossover de um ponto de corte Mutação aleatória

Critério de parada Limite máximo de gerações

Resultados Os resultados obtidos nos testes mostraram o potencial da solução

proposta. O software baseado em AG será usado no DCOMP, apenas durante alguns períodos, como auxilio ao método manual, já em funcionamento. Após a comprovação definitiva de sua eficácia, poderá vir a ser utilizado de forma oficial no DCOMP.


Algoritmos Genéticos Algoritmo Genético com Estratégias de Busca em Banco para o

Problema do Timetabling em Cursos de Universidade Genetic Algorithm with Search Bank Strategies for University Course Timetabling Problem

Mahiba A. A.; Durai A. D. C. (2012) - Karunya University Objetivos

Desenvolver um novo método em AG com estratégias de busca em banco: local, guiada e em busca tabu.

Modelagem do problema Busca local foi usada para aumentar as soluções, Busca Guiada foi

usada para limitar as soluções pelo uso de estrutura de dados de eventos. Busca tabu foi utilizado para remover as soluções usadas.

Representação da solução

Funcionário Matérias Estudantes Timeslot Sala de Aula



Hard Um funcionário não será atribuído a dois ou mais classes de estudantes no mesmo

de intervalo de tempo. Dois ou mais funcionários não devem ser atribuídos a uma classe de estudante no

mesmo timeslot. Dois ou mais salas não devem ser atribuídos a uma classe de alunos no mesmo

timeslot. Soft

Funcionários não devem ter três aulas consecutivas de timeslot, exceto seções de laboratório.

Para timeslot consecutivos, uma turma de alunos não deve mudar suas salas de aula. Todos os timeslots devem ser ocupados.

Criação da População Inicial Aleatoriamente com cada gene sendo limitado a limites inferiores e

superiores



Método de Seleção Busca Guiada Busca Local procurando um cromossomo de baixa aptidão

Operadores Crossover com movimentos de vizinhança Mutação através de Busca Local procurando um cromossomo de aptidão baixo

Critério de parada Limite de tempo

Resultados Todos esses métodos foram implementados para entradas de larga escala e

alcançaram resultados promissores. Três tipos de teste, de pequeno, médio e grande porte foram realizados com parâmetros variados. Testes com a população variando de 120 a 250, apresentaram melhores resultados para problemas de grande porte.



Considerações FinaisCaracterística Analisada Especificação Frequência de

Uso

Forma de representação

Vetor de Matrizes 2D 2Matriz 2D 1Vetor 2D 2Matriz 3D 4

Estrutura de vetores composta por variáveis simples 1

Tamanho da população

Entre 80 a 160 Indivíduos 1100 Indivíduos 2

Entre 120 a 250 Indivíduos 1Entre 100 a 500 Indivíduos 1Entre 200 a 750 Indivíduos 1

750 Indivíduos 11000 Indivíduos 2

Entre 256 a 5120 Indivíduos 1



Função Aptidão

3 2 1

1

1

Primeira fase do AG:

Segunda fase do AG:

1

1



Conclusão dos Resultados

Operadores

Crossover 9

Mutação 10

Critério de parada

Convergência 1Tempo Máximo de Execução 1

200 iterações 1

Entre 300 a 1000 iterações 1

500 iterações 23000 iterações 1

10000 iterações 115000 iterações 1

Entre 10.000 e 30.000 iterações 1

CONCLUSÕES E SUGESTÕES DE TRABALHOS FUTUROS

APLICAÇÕES DE ALGORITMOS GENÉTICOS EM OTIMIZAÇÃO DE

HORÁRIOS

Orientando: Philippe Norbert Cavalcanti AussourdOrientadora: Clarissa Daisy da Costa Albuquerque

Technology

Slides TCC 2015.1 - UNICAP - Aplicações de Algoritmos Genéticos em Otimização de Horários