Algoritmos Genéticos
Seminário de MAC5758
Introdução ao Escalonamento e Aplicações
Cleber Miranda Barboza
[email protected]
http://www.linux.ime.usp.br/~cleberc
1
Introdução
2

Um Algoritmo Genético (AG), conceitualmente,
segue passos inspirados no processo biológico
de evolução natural segundo a teoria de Darwin

Algoritmos Genéticos seguem a idéia de
SOBREVIVÊNCIA DO MAIS FORTE (melhores
soluções a cada geração)
Background

3
Cromossomos

Todo organismo vivo consiste de células.

Em cada célula, existe o mesmo conjunto de
cromossomos

Cromossomos consistem de genes –seqüências de
DNA- que servem para determinar as características
de um indivíduo
Background (Cont.)

4
Reprodução

Durante o processo de reprodução ocorre-se a
recombinação (ou crossover –cruzamento-).
Genes dos pais se combinam para formar novos
cromossomos.

Os descendentes criados podem sofrer mutações,
ou seja, os elementos do DNA podem ser trocados

A adaptação de um organismo pode ser medida
pelo sucesso do mesmo em sua vida
Idéia básica
5

Começar com um conjunto de soluções
(representado por cromossomos) chamado
população

Soluções de uma população são escolhidas e
usadas para formar uma nova população
(reprodução)

Espera-se que a nova população seja “melhor”
que a anterior
Idéia básica (Cont.)
6

Soluções que são escolhidas para formar novas
soluções (descendentes) são escolhidas de
acordo com uma função de adaptação (função
objetiva - custo)

O processo é repetido até que uma condição
seja satisfeita
Questões importantes



7
Como criar cromossomos e qual tipo de
codificação usar?
Como escolher os pais para a realização do
crossover?
A geração de uma população a partir de duas
soluções pode causar a perda da melhor
solução. O que fazer?
Esboço do algoritmo



8
[Início] Geração aleatória de uma população de n cromossomos
[Adaptação] Verificar a função objetiva f(x) de cada
cromossomo x
[População] Cria-se uma nova população pela repetição a seguir:
1.
[Seleção] Selecione um par de cromossomos da população
de acordo com a adaptação de cada um (os mais bem
adaptados tem maior chance de serem escolhidos)
2.
[Crossover] Produza dois descendentes (filhos) realizando
crossover com os cromossomos dos pais. O ponto para a
realização do crossover deve ser aleatório.
3.
[Mutação] Com uma certa probabilidade, o descendente sofre
mutação em cada locus (posição no cromossomo).
4.
[Aceitação] Coloque os descendentes em uma nova
população, juntamente com a melhor solução da geração
velha
Esboço do algoritmo (Cont.)

[Troca] Substitua a população velha pela nova

[Teste] Se a condição de finalização é satisfeita, pare, e retorne
a melhor solução da população atual
[Adaptação]
[Laço] Volte ao passo 1


9
Codificação

Como realizar a codificação de cromossomos?

É a primeira pergunta que deve ser feita ao
resolver um problema com AG

A codificação dependerá fortemente do
problema
10
Codificação binária


É a mais comum devido a sua simplicidade
Cada cromossomo é uma string de bits – 0 ou 1




11
Crom: A = 1 0 1 1 0 0 1 0 1 1
Crom: B = 1 1 1 1 1 1 0 0 0 0
Exemplo de uso: problema da mochila
Codificação: Cada bit diz se um elemento está
ou não na mochila
Codificação por permutação




12
Mais usado em problemas de ordenação
Cada cromossomo é uma string de números
que representa uma posição numa seqüência
 Crom A: 1 5 3 2 6 4 7 9 8
 Crom B: 8 5 6 7 2 3 1 4 9
Exemplo de uso: problema do caxeiro viajante
Codificação: os cromossomos descrevem a
ordem em que o caxeiro irá visitar as cidades
Codificação por valor


Usado em problemas onde valores mais
complicados são necessários
Cada cromossomo é uma seqüência de
valores



13
Crom A: 1.2324 5.3243 0.4556 2.3293 2.4545
Crom B: ABDJEIFJDHDIERJFDLDFLFEGT
Crom C: (back), (back), (right), (forward), (left)
Codificação por valor (Cont.)

Exemplo de uso: dada uma estrutura, encontrar
pesos para uma rede neural

Codificação: Valores reais num cromossomo
representam pesos em uma rede neural
14
Crossover


Após decidir qual codificação usar, procede-se
com a operação crossover
A operação deve ser realizada sobre os
cromossos dos pais para a criação de
descendentes




15
Crom1: 11010 | 00100110110
Crom2: 11011 | 11000011110
Filho 1: 11010 | 11000011110
Filho 2: 11011 | 00100110110
Mutação





16
O objetivo da mutação é evitar que as soluções
na população fiquem apenas num mínimo local
Filho1 antes : 1101111000011110
Filho2 antes : 1101100100110110
Filho1 depois : 1100111000011110
Filho2 depois : 1101101100110110
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


17
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.)




18
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.)
19
Problema da grade horária
(Cont.)



20
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.)




21
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.)


22
Como fazer o mapeamento entre a grade e os
cromossomos?
Representação do problema usando tuplas:
Problema da grade horária
(Cont.)

23
Mapeamento das tuplas em períodos
(representação de uma grade – indivíduo):
Problema da grade horária
(Cont.)

24
Representação de tuplas usando cromossomos:
Problema da grade horária
(Cont.)

25
Reprodução:
Problema da grade horária
(Cont.)

26
Mutação:
Problema da grade horária
(Cont.)

27
Problema causado pela perda de tuplas:
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


28
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


29
Matar o filho
Colocar o filho na população nova
População velha = População nova
Problema da grade horária
(Cont.)

30
Resultados:
Problema da grade horária
(Cont.)

31
Paralelizando a reprodução:
Referências





32
H.Firas. Handwritten Numeral Recognition Using Neural Networks,
em: http://ise.stanford.edu/class/ee368a_proj00/project2/node4.html
GENETIC ALGORITHMS, em:
http://cs.felk.cvut.cz/~xobitko/ga/main.html
D.Abramson, J.Abela. A Parallel Genetic Algorithm for Solving the
School Timetabling Problem, em:
http://citeseer.nj.nec.com/abramson92parallel.html
D. Abramson. Constructing School Timetables using Simulated
Annealing: Sequential and Parallel Algorithms, em:
http://citeseer.nj.nec.com/abramson91constructing.html
J.E.Boggess. USING GENETIC ALGORITHMS FOR SCHEDULING
ENGINEERING MISSIONS, em:
http://citeseer.nj.nec.com/55397.html