Upload
internet
View
109
Download
0
Embed Size (px)
Citation preview
O PROBLEMA DE O PROBLEMA DE SCHEDULING SCHEDULING EM JOB-SHOPEM JOB-SHOP
SOLUÇÃO POR APROXIMAÇÃOSOLUÇÃO POR APROXIMAÇÃO
Algoritmo genético: definições e características básicasAlgoritmo genético: definições e características básicas
Tópicos Especiais em Logística e TransportesTópicos Especiais em Logística e TransportesMe. Rogério Malta BrancoMe. Rogério Malta Branco
Estrutura do trabalhoEstrutura do trabalho1. Introdução 1. Introdução 1.2. O problema de job-shop scheduling1.2. O problema de job-shop scheduling1.2.1. Representação por grafos disjuntivos1.2.1. Representação por grafos disjuntivos1.2.2. Construção de escalas 1.2.2. Construção de escalas 1.2.3. Representação binária1.2.3. Representação binária
2. Técnicas para solucionar os JSSP2. Técnicas para solucionar os JSSP2.1. Soluções ótimas2.1. Soluções ótimas2.2. Soluções aproximadas2.2. Soluções aproximadas2.2.1. Regras de despacho2.2.1. Regras de despacho2.2.2. Metaheurísticas2.2.2. Metaheurísticas2.2.2.1. Algoritmos genéticos2.2.2.1. Algoritmos genéticos2.2.2.2. Simulated annealing2.2.2.2. Simulated annealing2.2.2.3. Outros procedimentos de busca 2.2.2.3. Outros procedimentos de busca
local e modelos híbridoslocal e modelos híbridos2.2.3. Outras soluções não ótimas2.2.3. Outras soluções não ótimas2.4. Conclusões2.4. Conclusões
3. Algortimos genéticos3. Algortimos genéticos3.1 Conceitos básicos3.1 Conceitos básicos3.2 Algoritmo genético simples3.2 Algoritmo genético simples3.3 O procedimento de um algoritmo 3.3 O procedimento de um algoritmo
genetico simplesgenetico simples
4 Um algoritmo genético simples no 4 Um algoritmo genético simples no problema de scheduling de job-shopproblema de scheduling de job-shop
4.1 Codificação genética de uma solução 4.1 Codificação genética de uma solução de schedulede schedule
4.2 Harmonização local4.2 Harmonização local4.3 Harmonização Global4.3 Harmonização Global4.4 Forcing4.4 Forcing4.5 Algoritmo genético simples para o Job-4.5 Algoritmo genético simples para o Job-
shopshop4.6 Limitações para uma aproximação 4.6 Limitações para uma aproximação
simplessimples
............
Meta-heurísticasMeta-heurísticas
Simulated AnnealingSimulated Annealing (tempera simulada)(tempera simulada) Colônia de formigasColônia de formigas Tabu searchTabu search Fast Local Search (Hill climbing)Fast Local Search (Hill climbing) Guided Local SearchGuided Local Search (refinamento) (refinamento) Algoritmos genéticosAlgoritmos genéticos
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Algoritmos genéticosAlgoritmos genéticos
Sua origem advém dos trabalhos Sua origem advém dos trabalhos desenvolvidos por John Holland (1962 e 1970).desenvolvidos por John Holland (1962 e 1970).
São métodos de busca probabilística São métodos de busca probabilística inteligentes baseados em mecanismos de inteligentes baseados em mecanismos de seleção e evolução natural.seleção e evolução natural.
Holland (1972 e 1975) utilizou símbolos Holland (1972 e 1975) utilizou símbolos binários (0,1) em estruturas semelhantes aos binários (0,1) em estruturas semelhantes aos cromossomos.cromossomos.
GOLDBARG & LUNA(2000)
Algoritmos genéticosAlgoritmos genéticos
Os objetivos de Holland eram fundamentar Os objetivos de Holland eram fundamentar uma teoria geral de sistemas de adaptação uma teoria geral de sistemas de adaptação robusta.robusta.
Acabou por encontrar um caminho de Acabou por encontrar um caminho de grande e imediata aplicação prática na grande e imediata aplicação prática na determinação de máximos e mínimos de determinação de máximos e mínimos de funções matemáticas.funções matemáticas.
As operações com funções matemáticas As operações com funções matemáticas facilitaram a utilização dos AGs no meio facilitaram a utilização dos AGs no meio acadêmico.acadêmico.
GOLDBARG & LUNA(2000)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
ObjetivoObjetivo
Tentar Tentar melhorar as qualidades genéticas melhorar as qualidades genéticas de uma populaçãode uma população através de um processo de através de um processo de renovação iterativa das populaçõesrenovação iterativa das populações
SOUZA(2006)
CaracterísticasCaracterísticas
Método de busca populacional, i.e, parte de um Método de busca populacional, i.e, parte de um conjunto de soluçõesconjunto de soluções, aplicando sobre estes , aplicando sobre estes operadores que visam à melhoria desse conjuntooperadores que visam à melhoria desse conjunto
Fundamentam-se em uma analogia com Fundamentam-se em uma analogia com processos naturais de evolução, nos quais, dada processos naturais de evolução, nos quais, dada uma população, os indivíduos com características uma população, os indivíduos com características genéticas melhores têm genéticas melhores têm maiores chances de maiores chances de sobrevivênciasobrevivência e de produzirem filhos cada vez e de produzirem filhos cada vez mais aptos, enquanto indivíduos menos aptos mais aptos, enquanto indivíduos menos aptos tendem a desaparecer tendem a desaparecer
SOUZA(2006)
CaracterísticasCaracterísticas
As características dos indivíduos, registradas em As características dos indivíduos, registradas em seus genes, são transmitidas para seus seus genes, são transmitidas para seus descendentes e descendentes e tendem a propagar-se por novas tendem a propagar-se por novas geraçõesgerações
Características dos descendentes são Características dos descendentes são parcialmente herdadas de seus paisparcialmente herdadas de seus pais ( (CrossoverCrossover) ) e parcialmente de novos e parcialmente de novos genes criados durante o genes criados durante o processo de reproduçãoprocesso de reprodução ( (MutaçãoMutação))
SOUZA(2006)
Genótipo = {0,1}L
Fenótipo Codificação (representação)
Decodificação (representação inversa)
011101001
010001001
10010010
10010001
RepresentaçãoRepresentação
EIBEN & SMITH (2006)
AG x Problema de OtimizaçãoAG x Problema de Otimização
AGAG Problema de OtimizaçãoProblema de Otimização
IndivíduoIndivíduo Solução de um problemaSolução de um problema
PopulaçãoPopulação Conjunto de soluçõesConjunto de soluções
CromossomoCromossomo Representação de uma soluçãoRepresentação de uma solução
GeneGene Parte da representação de uma Parte da representação de uma soluçãosolução
Crossover / MutaçãoCrossover / Mutação Operadores de buscaOperadores de busca
SOUZA(2006)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Estrutura de um AG básicoEstrutura de um AG básico
Selecione os pais
Crossover
Mutação
Defina a população sobrevivente
Avalie a população
Critérios de parada
satisfeitos?
Liste os melhores indivíduos
Gere uma população inicial
Avalie a população
Geração de uma nova população
Não
Sim
SOUZA(2006)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Função de aptidãoFunção de aptidão
• Avalia os cromossomos (Avalia os cromossomos (fitnessfitness))
• Em um problema de maximização pode Em um problema de maximização pode ser a própria função objetivoser a própria função objetivo
• Em um problema de minimização pode Em um problema de minimização pode ser o complemento da função objetivo, ou ser o complemento da função objetivo, ou seja, (-1*fseja, (-1*fobjobj))
SOUZA(2006)
Função de aptidão : Função de aptidão : exemplo para exemplo para problema de minimizaçãoproblema de minimização
SARAMAGO (2003)
>>x=8:0.05:10;
>>y=x;
>>[yy,xx] = meshgrid(y,x);
>>fx=xx.*sin(4*xx)+1.1*yy.*sin(2*yy);
>>meshc(xx,yy,fx);
Função: f(x,y)=x.sen(4x)+1.1 y sen(2.y)Domínio: 8<x<10 e 8<y<10Precisão; 2 casas decimais
Função de aptidãoFunção de aptidão
I=10-8=2, mas com 2 casas decimais;I=10-8=2, mas com 2 casas decimais;I= 2.10I= 2.102casas 2casas = 2.100 = 200 intervalos;= 2.100 = 200 intervalos;
Cada gene irá representar estes intervalos;Cada gene irá representar estes intervalos;2277=128 < 200 < 2=128 < 200 < 288=256=256
Solução:Solução: empregar, para cada variável, 8 bits na empregar, para cada variável, 8 bits na representação de escalas de 200 inervalos.representação de escalas de 200 inervalos.
Cada gene é um vetor binário de m bits, sendo m função Cada gene é um vetor binário de m bits, sendo m função da precisão exigida.da precisão exigida.
Baseado no exemplo de SARAMAGO (2003)
Função de aptidãoFunção de aptidão
Fase 1: Decodificação bináriaFase 1: Decodificação binária
ex: 00110011ex: 0011001122 = 51 = 511010
Fase 2: Ajuste da escala (int p/ real)Fase 2: Ajuste da escala (int p/ real)
ex: x =133ex: x =1331010 onde S onde Sscalescale= 8 e E= 8 e Escalescale= 10= 10
7 6 1 0 7 6 1 0[ , ,..., , , , ,..., , ]c b b b b a a a a1
0
.2m
ii
i
x b
1
0
.2m
ii
i
y a
1var var.
2scale scale
scale m
e ss
8
10 8 28 133. 8 133. 9,04
2 1 255x
Baseado no exemplo de SARAMAGO (2003)
Função de aptidãoFunção de aptidão
010 08
25510 10
13310
2real256inteiro
Regra de 3:
255 – 2 133 – x
X=2.133/255X=1,04
Como a escalainicia em 8, faz-se o ajuste:
X=1,04+8X=9,04
9,04
Baseado no exemplo de SARAMAGO (2003)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Seleção de indivíduos: Seleção de indivíduos: sobrevivência e mortesobrevivência e morte
• Como selecionamos os cromossomos que Como selecionamos os cromossomos que devem sobreviver?devem sobreviver?
• Sobrevivem os que possuem os melhores Sobrevivem os que possuem os melhores níveis de aptidão?níveis de aptidão?
• É importante permitir também a sobrevida É importante permitir também a sobrevida de cromossomos menos aptos, do de cromossomos menos aptos, do contrário o método ficaria contrário o método ficaria preso em ótimos preso em ótimos locaislocais
• ElitismoElitismo
SOUZA (2006)
Seleção de indivíduosSeleção de indivíduos
Princípio básico para o direcionamento da Princípio básico para o direcionamento da evolução de uma dada populaçãoevolução de uma dada população
Utiliza uma Utiliza uma função de avaliação para medir a função de avaliação para medir a aptidãoaptidão de cada indivíduo de cada indivíduo
Essa aptidão pode ser Essa aptidão pode ser absolutaabsoluta ou ou relativarelativa
Existem vários métodos de seleçãoExistem vários métodos de seleção
SOUZA (2006)
Seleção de indivíduos: métodosSeleção de indivíduos: métodos
• RoletaRoleta• TorneioTorneio• Aleatório, etc...Aleatório, etc...
LOPES (2006)
Método da RoletaMétodo da Roleta
Coloca-se os indivíduos em uma roleta, dando a Coloca-se os indivíduos em uma roleta, dando a cada um uma “fatia” proporcional à sua aptidão cada um uma “fatia” proporcional à sua aptidão relativarelativa
Roda-se a roleta. O indivíduo em cuja fatia a Roda-se a roleta. O indivíduo em cuja fatia a agulha parar permanece para a próxima agulha parar permanece para a próxima geraçãogeração
Repete-se o sorteio tantas vezes quanto forem Repete-se o sorteio tantas vezes quanto forem necessárias para selecionar a quantidade necessárias para selecionar a quantidade desejada de indivíduosdesejada de indivíduos
LOPES (2006)
Roleta - ExemploRoleta - ExemploIndivíduoIndivíduo Aptidão AbsolutaAptidão Absoluta Aptidão RelativaAptidão Relativa
11 22 0,0526315790,052631579
22 44 0,1052631580,105263158
33 55 0,1315789470,131578947
44 99 0,2368421050,236842105
55 1818 0,4736842110,473684211
TotalTotal 3838 11
LOPES (2006)
Seleção de indivíduos: métodosSeleção de indivíduos: métodos
• RoletaRoleta• TorneioTorneio• Aleatório, etc...Aleatório, etc...
LOPES (2006)
Método do TorneioMétodo do Torneio
Utiliza sucessivas Utiliza sucessivas disputasdisputas para realizar a para realizar a seleçãoseleção
Para selecionar Para selecionar kk indivíduos indivíduos, realiza , realiza kk disputasdisputas, cada disputa envolvendo , cada disputa envolvendo nn indivíduosindivíduos escolhidos ao acaso escolhidos ao acaso
O indivíduo de maior aptidão na disputa é O indivíduo de maior aptidão na disputa é selecionadoselecionado
É muito comum utilizar É muito comum utilizar nn = 3 = 3
LOPES (2006)
Torneio - ExemploTorneio - Exemplo
Indiv 1, Indiv 2, Indiv 4 Indiv 4
Indiv 1, Indiv 2, Indiv 3 Indiv 3
Indiv 2, Indiv 3, Indiv 4 Indiv 4
Indiv 3, Indiv 4, Indiv 5 Indiv 5
LOPES (2006)
Seleção de indivíduos: exemplo Seleção de indivíduos: exemplo
Gera-se n=6 (tam. população) números aleatórios.
Observa-se que: r1 > q1;r1 > q2;r1 < q3; => C3 selecionado.
De forma análoga, aplica-se os demais valores aleatórios gerados.
São portanto selecionados: C3, C1, C3, C5, C5, C4.
Depois de selecionados, dão origem a uma nova população, a ser submetida agora aos operadores genéticos CROSSOVER e MUTAÇÃO.
Baseado no exemplo de SARAMAGO (2003)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Operadores genéticosOperadores genéticos
CROSSOVER
MUTAÇÃO
SOUZA (2006)
Operadores genéticosOperadores genéticos
Reprodução (Reprodução (crossovercrossover))MutaçãoMutaçãoClonagem, etc...Clonagem, etc...
Operador de CruzamentoOperador de Cruzamento
Também chamado de Também chamado de reproduçãoreprodução ou ou crossovercrossover
Combina as informações genéticas de Combina as informações genéticas de dois indivíduos (dois indivíduos (paispais) para gerar novos ) para gerar novos indivíduos (indivíduos (filhosfilhos))
Versões mais comuns criam sempre dois Versões mais comuns criam sempre dois filhos para cada operaçãofilhos para cada operação
LOPES (2006)
Operador de CruzamentoOperador de Cruzamento
Operador genético principalOperador genético principalResponsável por gerar novos indivíduos Responsável por gerar novos indivíduos
diferentesdiferentes (sejam melhores ou piores) a (sejam melhores ou piores) a partir de indivíduos já promissorespartir de indivíduos já promissores
Aplicado a cada par de indivíduos com Aplicado a cada par de indivíduos com alta probabilidade (normalmente entre 0,6 alta probabilidade (normalmente entre 0,6 e 0,99)e 0,99)
LOPES (2006)
Abordagens para CruzamentoAbordagens para Cruzamento
Cruzamento Um-PontoCruzamento Um-Ponto
Cruzamento Multi-PontosCruzamento Multi-Pontos
Cruzamento UniformeCruzamento Uniforme
LOPES (2006)
0 0 0 1 1 110 Pais
Cruzamento Um-PontoCruzamento Um-Ponto
00 Filhos 1 1 001 1
LOPES (2006)
0 0 0 1 1 110 Pais
Cruzamento Multi-PontoCruzamento Multi-Ponto
00 Filhos 1 1001 1
LOPES (2006)
0 0 0 1 1 11Pais0
Máscara 1 0 10
Cruzamento UniformeCruzamento Uniforme
00 Filhos 1 1 001 1
LOPES (2006)
Cruzamento : exemplo Cruzamento : exemplo
Geram-se números aleatórios para cada novo indivíduo da população.Estima-se também um valor para probabilidade de cruzamento (Pc=0.25).
Se randi > Pc então Indivíduo Ci não selecionado, Senão Indivíduo Ci selecionado.
No exemplo acima selecionou-se C3 e C6.Gera-se, de forma aleatória o ponto K de corte: k=1+rand.[m-1)-1]Ou seja: k= 1 + 0,7. [(16-1)-1] = 1+0,7.14 = 10,8 = 11
Baseado no exemplo de SARAMAGO (2003)
Cruzamento : exemplo Cruzamento : exemplo
Baseado no exemplo de SARAMAGO (2003)
Operadores genéticosOperadores genéticos
Reprodução (Reprodução (crossovercrossover))MutaçãoMutaçãoClonagem, etc...Clonagem, etc...
LOPES (2006)
Operador de MutaçãoOperador de Mutação
Operador Operador randômicorandômico de manipulação de manipulação Introduz e mantém a Introduz e mantém a variedade genéticavariedade genética
da populaçãoda populaçãoGarante a possibilidade de se alcançar Garante a possibilidade de se alcançar
qualquer ponto do espaço de buscaqualquer ponto do espaço de buscaContorna mínimos locaisContorna mínimos locaisOpera sobre os indivíduos resultantes do Opera sobre os indivíduos resultantes do
processo de cruzamentoprocesso de cruzamento
LOPES (2006)
Operador de MutaçãoOperador de Mutação
É um É um operador genético secundáriooperador genético secundárioSe seu uso for exagerado, reduz a Se seu uso for exagerado, reduz a
evolução a uma evolução a uma busca totalmente busca totalmente aleatóriaaleatória
Deve atuar com probabilidade baixa Deve atuar com probabilidade baixa (normalmente entre 0,001 e 0,1)(normalmente entre 0,001 e 0,1)
LOPES (2006)
0 1 1 0 0 0 1
Operador de MutaçãoOperador de Mutação
0 1 0 0 0 0 1
LOPES (2006)
Exemplo de MutaçãoExemplo de Mutação
Baseado no exemplo de SARAMAGO (2003)
Exemplo de MutaçãoExemplo de Mutação
Para a população final pós-operadores, o processo é reiniciado até serencontrado o critério de parada.
Baseado no exemplo de SARAMAGO (2003)
EstruturaEstrutura
IntroduçãoIntroduçãoObjetivo e características dos AGsObjetivo e características dos AGsEstrutura básica de um AG (fluxograma)Estrutura básica de um AG (fluxograma)Função de aptidãoFunção de aptidãoSeleção de indivíduosSeleção de indivíduosOperadores genéticosOperadores genéticosParâmetros genéticosParâmetros genéticos
Parâmetros GenéticosParâmetros Genéticos
Tamanho da populaçãoTamanho da populaçãoTaxa de cruzamentoTaxa de cruzamentoTaxa de mutaçãoTaxa de mutação Intervalo de geraçãoIntervalo de geraçãoCritério de paradaCritério de parada
LOPES (2006)
ReferênciasReferênciasEIBEN, A.E. & SMITH, J.E., Apresentação: EIBEN, A.E. & SMITH, J.E., Apresentação: Introduction to Evolutionary Computing: Genetic Introduction to Evolutionary Computing: Genetic
AlgorithmsAlgorithms, , http://www.cs.vu.nl/~jabekker/ec0607/slides/Lecture03-Chapter3-GeneticAlgorithms.ppthttp://www.cs.vu.nl/~jabekker/ec0607/slides/Lecture03-Chapter3-GeneticAlgorithms.ppt ,acessado em 19/10/2006. ,acessado em 19/10/2006.
GOLDBERG, D. GOLDBERG, D. Genetic algorithms in search, optimization and machine learning. Genetic algorithms in search, optimization and machine learning. Addison- Addison-Wesley, 1989. Wesley, 1989.
GOLDBARG, M. C. e LUNA, H. P. L., GOLDBARG, M. C. e LUNA, H. P. L., Otimização Combinatória e Programação Linear: modelos Otimização Combinatória e Programação Linear: modelos e algoritmose algoritmos, Rio de Janeiro: Editora Campus, 2000., Rio de Janeiro: Editora Campus, 2000.
LOPES, L. R. M., Apresentação: LOPES, L. R. M., Apresentação: Fundamentos de Algoritmos GenéticosFundamentos de Algoritmos Genéticos, , www.cos.ufrj.br/~ines/courses/cos740/leila/cos740/Algoritmos%20Geneticos.pptwww.cos.ufrj.br/~ines/courses/cos740/leila/cos740/Algoritmos%20Geneticos.ppt ,acessado em ,acessado em 19/10/2006.19/10/2006.
PITTMAN, J. , Apresentação: PITTMAN, J. , Apresentação: Genetic Algorithm for Variable Selection,Genetic Algorithm for Variable Selection, Universidade Duke, Universidade Duke, http://www.niss.org/affiliates/proteomics200303/presentations20030306/04%http://www.niss.org/affiliates/proteomics200303/presentations20030306/04%20Jennifer.ppt acessado em 19/10/2006. acessado em 19/10/2006.
SOUZA, M. J. F., Apresentação: SOUZA, M. J. F., Apresentação: Algoritmos genéticos.Algoritmos genéticos. http://www.iceb.ufop.br/prof/marconehttp://www.iceb.ufop.br/prof/marcone acessado em 19/10/2006.acessado em 19/10/2006.