Algoritmo IV

Prévia do material em texto

1
GA em Otimização de GA em Otimização de 
PlanejamentoPlanejamento
� Planejamento envolve:
� Otimizar: 
–– “Alocar , no tempo, os recursos para a execução das “Alocar , no tempo, os recursos para a execução das 
tarefas, respeitando as restrições e condições, de modo tarefas, respeitando as restrições e condições, de modo 
a alcançar os objetivos do problema.”a alcançar os objetivos do problema.”
ProcedimentosProcedimentos
RecursosRecursos
TarefasTarefas
TempoTempo
Objetivos Objetivos 
Restrições e condiçõesRestrições e condições
ExemplosExemplos
– Problema do Caixeiro Viajante
– Otimização da Distribuição (Rota de veículos)
– Alocação de Salas; Timetabling
– Planejamento de Vôos de Cias Aéreas
– Otimização de Estoque/Produção
– Otimização da Produção Industrial
2
Variáveis Típicas do Variáveis Típicas do 
Planejamento Planejamento 
�� Restrições de RecursosRestrições de Recursos
– número de instâncias de cada recurso/máquina;
– diferenças entre as instâncias (velocidade, tempo máximo de 
operação, capacidade etc).
– paradas de manutenção
– máquinas com programação especial: laminadores de aço (largura, 
espessura e dureza) 
�� Restrições TemporaisRestrições Temporais
– horário de funcionamento preferenciais;
– tempo de transporte de material entre máquinas
�� Reajuste das MáquinasReajuste das Máquinas
– tarefas exigem setup de máquinas (automático ou manual).
Variáveis Típicas do Variáveis Típicas do 
Planejamento Planejamento (cont.)(cont.)
�� PrioridadePrioridade
– tarefas possuem prioridades diferentes (prazo de entrega, 
emergência, manutenção, tipo de cliente etc).
�� EstoqueEstoque
– matéria prima: disponibilidade, ordem de desempilhamento
�� ReprogramaçãoReprogramação
– reprogramação das máquinas em casos de contingências
�� PrecedênciaPrecedência
– certas tarefas não podem ser programadas antes que outras 
tenham terminado.
3
Características do Características do 
PlanejamentoPlanejamento
� Há muitas condições e restrições que não podem ser ser 
expressas matematicamente;
� Métodos de busca podem falhar devido aos requisitos de tempo;
� Podar o espaço de busca reduz o tempo de execução mas limita 
desempenho;
� Heurísticas são úteis para acelerar a busca;
� GA é um técnica adequada a problemas mal estruturados como 
os de planejamento.
Problema Simples de Problema Simples de 
Planejamento de ProduçãoPlanejamento de Produção
� 90 tarefas: (a, b, c, d, e, f................)
� cada tarefa possui um peso associado a sua 
importância (lucro, prioridade, benefício etc)
� 30 recursos: apenas uma instância de cada recurso
� tarefas requerem de 1 a 3 horas para execução
� programação para um total de 40 horas de produção
� algumas tarefas têm restrições nas primeiras 12 horas 
do planejamento
� Objetivo: maximizar a soma dos pesos das tarefas 
planejadas nas primeiras 40 horas
4
Tarefas Tempo Execução Recursos Utilizados pelas Tarefas
Exemplo de Tarefas: Exemplo de Tarefas: a..ua..u
Tempo de Execução de cada tarefa: Tempo de Execução de cada tarefa: 1, 21, 2 ou ou 3 3 horashoras
Recursos requeridos por cada tarefa: Recursos requeridos por cada tarefa: ““ . . ”” = recurso não requerido= recurso não requerido
“ “ aa”” = recurso requerido= recurso requerido
a 3 . a . . . . a a . . . a a . . . . . . . a . . . . .
b 1 . . b . . . . b . b . . b . b b . . b . b . . . . .
c 3 . . c . c c . . c . . . . c . . c c . c . c c . . .
d 3 . . d . . . d . . d . . d . . . . . . . . d . . . .
e 3 . . . . e e e . . e . . . . . . . e . . . . . . . .
f 1 . f . f f f . . f . . . . . . . . . . . f . f f f .
g 3 g . g . . . . g . . . . g . g g g . . . . g g . g g
h 2 h . . . h . h . h . h h . . . . . . . . . . . . . .
i 1 . . . i . . . . . . i i i . . . . . i . . i . . . .
j 1 . . . . . . . . . . . . . . . . . . . . . . . . j .
k 1 . . k k . k . k . . . . . k k . . . . . . k . . . .
l 1 l . . . l l . . l . . . l . . l . l l . . . l . . l
m 3 . . . . m . m . . . m m . . . . . . . . . . . . m .
n 2 . . . . . . . . . . . . . . n n . . n n . . . . . .
o 3 . o o . . . . . o . . . . . o . . o o . . o . . . .
p 1 . . . . p . . . . . p . p p . . . . p . . p . p . .
q 3 . . . q . . . q . . . . q . . q . . q . q . . q . q
r 1 r . . . . . . . . . r r . r . . . . . r . . . . . .
s 3 . . . s s . . . s s . . . . . s . . . . . s . . . .
t 1 t . . . . . . . . . . . . . t . . t t . . . . . . .
u
Exemplo de PlanejamentoExemplo de Planejamento
� Planejamento parcial das tarefas em ordem alfabética
Tempo
Hora
1
2
3
4
5
6
7
8
9
10
11
. a c . c c a a c . . a a c . . c c . c a c c . . . . . . .
a c . c c a a c . . a a c . . c c . c a c c . . . . . . .
. a c . c c a a c . . a a c . . c c . c a c c . . . . . . .
. . b . . . . b . b . . b . b b . . b . b . . . . . . . .
. f d f f f d . f d . . d . . . . . . . f d f f f . f . f d
. . d . . . d . . d . . d . . . . . . . . d . . . . . . . d
. . d . . . d . . d . . d . . . . . . . . d . . . . . . . d
g . g . e e e g . e . . g . g g g e . . . g g . g g e . . e
g . g . e e e g . e . . g . g g g e . . . g g . g g e . . e
g . g . e e e g . e . . g . g g g e . . . g g . g g e . . e
. f . f f f . . f . . . . . . . . . . . f . f f f . f . f .
g . g . . . . g . . . . g . g g g . . . . g g . g g . . . .
5
Modelagem do Algoritmo GenéticoModelagem do Algoritmo Genético
1. Problema1. Problema
2. 2. RepresentaçãoRepresentação
3. Decodificação3. Decodificação
4. Avaliação4. Avaliação
5. Operadores5. Operadores
6. Técnicas6. Técnicas
7. Parâmetros7. Parâmetros
RepresentaçãoRepresentação
� Cromossoma ≡ permutação (lista) de tarefas
P1 = (a, b, c, d, e, . . . . t)
P2 = (d, s, e, h, g, . . . . i)
� cromossoma codifica a ordem e a vez (posição) nas 
quais as tarefas serão planejadas
� requer decodificador ≡ construtor de planejamentos 
legais
6
Decodificador doDecodificador do CromossomaCromossoma
� Constrói soluções LEGAIS
� Concentra todo o conhecimento no domínio do 
problema: restrições, recursos, horários, etc.
� Regra Principal:
“Se uma tarefa está planejada na hora t, uma outra 
tarefa não pode ser planejada em t, exceto se a 
interseção dos recursos requisitados é vazia”
Decodificador doDecodificador do CromossomaCromossoma
1 Pega a primeira tarefa da lista;
2 Coloca a tarefa no planejamento a partir de t=0;
3 Pega próxima tarefa e procura colocá-la no 
planejamento, considerando as restrições presentes, 
a partir de t=0 até t=40 horas;
4 Vai para 3 se não terminou a lista.
7
P = (P = (tt, c, s, a) , c, s, a) 
Hora
1
2
3
4
5
6
7
8
9
10
11
t . . . . . . . . . . . . . t . . t t . . . . . . . . . . .
t . . . . . . . . . . . . . t . . t t . . . . . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, , cc, s, a) , s, a) 
8
t . . . . . . . . . . . . . t . . t t . . . . . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . . s s . . . s s . . . . . s . . . . . s . . . . s . . .
. s s . . . s s . . . . . s . . . . . s . . . . s . . .
. s s . . . s s . . . . . s . . . . . s . . . . s . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, , cc, , ss, a) , a) 
Hora
1
2
3
4
5
6
7
8
9
10
11
t a . . . . a a . . . a a . t . . t t . a . . . . . . . . .
. a c . c c a a c . . a a c . . c c . c a c c . . . . . . .
. a c . c c a a c . . a a c . . c c . c a c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . . s s . . . s s . . . . . s . . . . . s . . . . s . . .
. s s . . . s s. . . . . s . . . . . s . . . . s . . .
. s s . . . s s . . . . . s . . . . . s . . . . s . . .
P = (P = (tt, , cc, , ss, , aa) ) ➨➨ 7 horas 7 horas 
9
t . . . . . . . . . . . . . t . . t t . . . . . . . . . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, a, s, c) , a, s, c) 
t a . . . . a a . . . a a . t . . t t . a . . . . . . . . .
. a . . . . a a . . . a a . . . . . . . a . . . . . . . . .
. a . . . . a a . . . a a . . . . . . . a . . . . . . . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, , aa, s, c) , s, c) 
10
t a . s s . a a s s . a a . t s . t t . a s . . . . s . . .
. a . s s . a a s s . a a . . s . . . . a s . . . . s . . .
. a . s s . a a s s . a a . . s . . . . a s . . . . s . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, , aa, , ss, c) , c) 
t a . s s . a a s s . a a . t s . t t . a s . . . . s . . .
. a . s s . a a s s . a a . . s . . . . a s . . . . s . . .
. a . s s . a a s s . a a . . s . . . . a s . . . . s . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
. . c . c c . . c . . . . c . . c c . c . c c . . . . . . .
Hora
1
2
3
4
5
6
7
8
9
10
11
P = (P = (tt, , aa, , ss, , cc) ) ➨➨ 6 horas 6 horas 
11
AvaliaçãoAvaliação
� Uma possível função considera:
– pesos das tarefas ➨ maximizar a soma das planejadas
– restrições das tarefas ➨ penalizar se violação
– período ➨ não planejar se além de t=40 horas
Ai = ∑ pt - ∑ pn + ∑ pp + ∑ pv/2 
– pt = pesos de todas as ttarefas
– pn = pesos das tarefas nnão planejadas
– pp = pesos das tarefas pplanejadas
– pv = pesos das tarefas que vviolaram restrição
�� AAi i ≥≥≥≥≥≥≥≥ 0; 0; AAi i = 0 = 0 ➨➨➨➨➨➨➨➨ nenhuma planejada;nenhuma planejada; AAi i = 2 = 2 ∑∑∑∑∑∑∑∑ ppt t ➨➨➨➨➨➨➨➨ todastodas
t n p v
Avaliando OperadoresAvaliando Operadores
�� Mutação Baseada em OrdemMutação Baseada em Ordem
�� Mutação Baseada em PosiçãoMutação Baseada em Posição
�� Mutação porMutação por EmbaralhamentoEmbaralhamento
�� Crossover Crossover Baseado em OrdemBaseado em Ordem
�� CrossoverCrossover Baseado em PosiçãoBaseado em Posição
�� Recombinação de AdjacênciasRecombinação de Adjacências
Aspectos importantes
– Ordem Relativa
• tarefas anteriores podem impedir o planejamento das tarefas 
posteriores
– Posição da Tarefa
• tarefas no início da lista têm maior chance de serem planejadas
12
Avaliação de DesempenhoAvaliação de Desempenho
� Avaliação dos Operadores isoladamente:
– só mutação
– só crossover
� Combinando os Melhores Operadores
� Busca Aleatória para comparar resultados
– gera uma lista de tarefas e avalia
� Espaço de Representação = 90! = 10138
� Média de 50 Experimentos de 3000 Indivíduos: 
média dos melhores a cada instante
Busca AleatóriaBusca Aleatória
13
Mutação Baseada em OrdemMutação Baseada em Ordem
� duas tarefas são selecionadas aleatoriamente e a 
segunda é colocada na frente da primeira
� Exemplo:
(aa b c d ee f) (a bb c dd e f)
⇓ ⇓
(ee aa b c d f) (a dd bb c e f)
� operador preserva ordem relativa de parte do
cromossoma
Mutação Baseada em PosiçãoMutação Baseada em Posição
� troca as posições de duas tarefas escolhidas 
aleatoriamente
(aa b c d ee f) (a bb c dd e f)
⇓ ⇓
(ee b c d aa f) (a dd c bb e f)
� operador não preserva a ordem relativa das posições 
selecionadas em relação as tarefas do meio
14
Mutação porMutação por EmbaralhamentoEmbaralhamento
� embaralha sub-lista escolhida aleatoriamente
(a | b c d | e f) (a b c | d e f |)
⇓ ⇓
(a | c d b | e f) (a b c | f d e |)
� operador tem maior poder de dispersão da 
população
Resultados da MutaçãoResultados da Mutação
� Testes sem crossover e com elitismo
� Mutação é mais efetiva que busca aleatória
� Mutação baseada em ordem é mais efetiva
� Embaralhamento é melhor que busca aleatória
� Operadores de mutação são heurísticos, por isso são 
melhores que busca aleatória
15
Resultados da MutaçãoResultados da Mutação
Crossover Crossover de Ordemde Ordem
� Posições são selecionadas aleatoriamente
� Ordem das tarefas nas posições selecionadas em um genitor é 
imposta nas tarefas correspondentes no outro genitor
P1 = a bb cc d ee f g hh i j
P2 = e ii bb d ff a j gg c h
posições ✶✶✶✶ ✶✶✶✶ ✶✶✶✶ ✶✶✶✶
F1 = a _ c d e _ _ h _ j
F2 = _ i _ d f a j g _ _
F1 = a ii c d e bb ff h gg j
F2 = bb i cc d f a j g ee hh
16
Crossover Crossover de Posiçãode Posição
� Posições são selecionadas aleatoriamente
� Posições das tarefas em um genitor são impostas nas tarefas 
correspondentes no outro genitor
P1 = a bb cc d ee f g hh i j
P2 = e ii bb d ff a j gg c h
posições ✶✶✶✶ ✶✶✶✶ ✶✶✶✶ ✶✶✶✶
F1 = _ ii bb _ ff _ _ gg _ _
F2 = _ b cb c _ ee _ _ hh _ _
F1 = a ii bb c f f d e gg h j
F2 = i bb cc d ee f a hh j g
Recombinação de AdjacênciasRecombinação de Adjacências
� Crossover combina a informação de adjacências entre as 
tarefas presentes nos genitores
P1 = a b c d e f
P2 = b d c a e f
P1 ➩ ab bc cd de ef fa informação de adjacência
P2 ➩ bd dc ca ae ef fb informação de adjacência
F = b c d e a f
F ➩ bc cd de ea af fb informação de adjacência
17
Recombinação de AdjacênciasRecombinação de Adjacências
� Operador foi originalmente criado para o problema 
do Caixeiro Viajante (TSP)
A
C
B ED
7Km
3Km4Km
1Km
3Km
cidades
A D B C E
� No TSP temos:
– informação de adjacência é importante
– direção (ordem) entre 2 cidades não importa (A B = B A)
Resultados do Resultados do CrossoverCrossover
� Testes sem mutação e com elitismo (rápida evolução 
no início, nada acontece após 1000 indivíduos)
� Crossover de ordem apresenta resultado equivalente 
ao de posição: são de fato o mesmo operador !!são de fato o mesmo operador !!
� Recombinação de Adjacências é equivalente a busca 
aleatória no problema de planejamento
18
Resultados do Resultados do CrossoverCrossover
Combinando Combinando CrossoverCrossover e e 
MutaçãoMutação
1 Mutação de Ordem (50%) + Crossover de Ordem (50%)
2 Mutação de Ordem (50%) + Crossover de Posição (50%)
3 Mutação de Ordem (50%) + Recomb. de Adjacências (50%)
� Curvas menos inclinadas no início e menos planas no final
� Variando os pesos do crossover e mutação, pode-se melhorar o 
desempenho: aumentando-se a mutação e diminuindo-se o 
crossover, lentamente, durante a evolução.
19
Crossover Crossover (50%) + Mutação (50%)(50%) + Mutação (50%)
VariandoVariando--se os Pesos de se os Pesos de 
CrossoverCrossover + Mutação+ Mutação