Baixe o app para aproveitar ainda mais
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
Compartilhar