Fundamentos dos
Algoritmos Genéticos
Alex F. V. Machado
Problema da grade
horária
Escalonar salas, professores e classes em
um número fixo de períodos de tal maneira
que nenhum professor, classe ou sala sejam
usados mais de uma vez num mesmo
período
Suposições para resolver o problema


Uma classe consiste de um certo número de
estudantes
As classes são disjuntas, ou seja, não há
estudantes em comum
Problema da grade
horária (Cont.)




Em cada período uma matéria é lecionada a uma
classe
É possível que uma matéria apareça mais de uma
vez em um período
Uma combinação particular de (professor,
matéria, sala, classe) é chamada de tupla
A tarefa de realizar a combinação (professor,
matéria, sala, classe) para formar uma tupla é
feita à parte
Problema da grade
horária (Cont.)
Problema da grade
horária (Cont.)
Para medir a qualidade da grade horária
(função objetiva - custo), calcular o número
de colisões em qualquer grade.
A grade aceitável tem custo 0
O custo de cada período pode ser dado pela
soma dos três componentes: custo da classe,
custo do professor e custo da sala
Problema da grade
horária (Cont.)
O custo das classes é o número de vezes em
que cada classe aparece num período menos
1.
Se uma classe não aparece em nenhum
período seu custo é 0
A mesma idéia se aplica para os professores
e salas
Assim, o custo da grade é a soma dos custos
de cada período
Problema da grade
horária (Cont.)
Como fazer o mapeamento entre a grade e os
cromossomos?
Representação do problema usando tuplas:
Problema da grade
horária (Cont.)
Mapeamento das tuplas em períodos
(representação de uma grade – indivíduo):
Problema da grade
horária (Cont.)
Representação de tuplas usando
cromossomos:
Problema da grade
horária (Cont.)
Reprodução:
Problema da grade
horária (Cont.)
Mutação:
Problema da grade
horária (Cont.)
Problema causado pela perda de tuplas:
12
Problema da grade
horária (Cont.) Algoritmo
Enquanto número de gerações < limite e não
houver indivíduo perfeito faça

Para cada filho a ser gerado faça



Escolha dois indivíduos aleatórios da população
velha
Crie um filho vazio
Para cada período dos pais faça


Realize os crossover dos períodos correspondentes,
produzindo um novo período
Copie o novo período para a posição
correspondente do filho
Problema da grade
horária (Cont.) Algoritmo

Arrumar a perda e duplicação de tuplas
Aplicar mutação selecionando aleatóriamente um
período e uma tupla
Medir o custo do indivíduo

Se custo < mínimo permitido




Se não


Matar o filho
Colocar o filho na população nova
População velha = População nova
Problema da grade
horária (Cont.)
Resultados:
Problema da grade
horária (Cont.)
Paralelizando a reprodução: