O PROBLEMA DE SCHEDULING
EM JOB-SHOP
SOLUÇÃO POR APROXIMAÇÃO
Algoritmo genético: definições e características básicas
Tópicos Especiais em Logística e Transportes
Me. Rogério Malta Branco
Estrutura do trabalho
1. Introdução
1.2. O problema de job-shop scheduling
1.2.1. Representação por grafos disjuntivos
1.2.2. Construção de escalas
1.2.3. Representação binária
3. Algortimos genéticos
3.1 Conceitos básicos
3.2 Algoritmo genético simples
3.3 O procedimento de um algoritmo
genetico simples
2. Técnicas para solucionar os JSSP
2.1. Soluções ótimas
2.2. Soluções aproximadas
2.2.1. Regras de despacho
2.2.2. Metaheurísticas
2.2.2.1. Algoritmos genéticos
2.2.2.2. Simulated annealing
2.2.2.3. Outros procedimentos de busca
local e modelos híbridos
2.2.3. Outras soluções não ótimas
2.4. Conclusões
4 Um algoritmo genético simples no
problema de scheduling de job-shop
4.1 Codificação genética de uma solução
de schedule
4.2 Harmonização local
4.3 Harmonização Global
4.4 Forcing
4.5 Algoritmo genético simples para o Jobshop
4.6 Limitações para uma aproximação
simples
......
Meta-heurísticas






Simulated Annealing (tempera simulada)
Colônia de formigas
Tabu search
Fast Local Search (Hill climbing)
Guided Local Search (refinamento)
Algoritmos genéticos
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Algoritmos genéticos
Sua
origem
advém
dos
trabalhos
desenvolvidos por John Holland (1962 e 1970).
São métodos de busca probabilística
inteligentes baseados em mecanismos de
seleção e evolução natural.
Holland (1972 e 1975) utilizou símbolos
binários (0,1) em estruturas semelhantes aos
cromossomos.
GOLDBARG & LUNA(2000)
Algoritmos genéticos
Os objetivos de Holland eram fundamentar
uma teoria geral de sistemas de adaptação
robusta.
Acabou por encontrar um caminho de
grande e imediata aplicação prática na
determinação de máximos e mínimos de
funções matemáticas.
As operações com funções matemáticas
facilitaram a utilização dos AGs no meio
acadêmico.
GOLDBARG & LUNA(2000)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Objetivo
Tentar melhorar as qualidades genéticas de
uma população através de um processo de
renovação iterativa das populações
SOUZA(2006)
Características

Método de busca populacional, i.e, parte de um
conjunto de soluções, aplicando sobre estes
operadores que visam à melhoria desse conjunto

Fundamentam-se em uma analogia com
processos naturais de evolução, nos quais, dada
uma população, os indivíduos com características
genéticas melhores têm maiores chances de
sobrevivência e de produzirem filhos cada vez
mais aptos, enquanto indivíduos menos aptos
tendem a desaparecer
SOUZA(2006)
Características

As características dos indivíduos, registradas em
seus genes, são transmitidas para seus
descendentes e tendem a propagar-se por novas
gerações

Características dos descendentes são
parcialmente herdadas de seus pais (Crossover)
e parcialmente de novos genes criados durante o
processo de reprodução (Mutação)
SOUZA(2006)
Representação
Genótipo = {0,1}L
Fenótipo
Codificação
(representação)
10010001
10010010
010001001
011101001
Decodificação
(representação inversa)
EIBEN & SMITH (2006)
AG x Problema de Otimização
AG
Problema de Otimização
Indivíduo
Solução de um problema
População
Conjunto de soluções
Cromossomo
Representação de uma solução
Gene
Parte da representação de uma
solução
Crossover / Mutação Operadores de busca
SOUZA(2006)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Estrutura de um AG básico
Gere uma
população inicial
Avalie a
população
Critérios de
parada
satisfeitos?
Sim
Liste os melhores
indivíduos
Não
Selecione os pais
Crossover
Mutação
Avalie a
população
Defina a população
sobrevivente
Geração de uma nova população
SOUZA(2006)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Função de aptidão
•
Avalia os cromossomos (fitness)
•
Em um problema de maximização pode
ser a própria função objetivo
•
Em um problema de minimização pode
ser o complemento da função objetivo, ou
seja, (-1*fobj)
SOUZA(2006)
Função de aptidão : exemplo para
problema de minimização
Função: f(x,y)=x.sen(4x)+1.1 y sen(2.y)
Domínio: 8<x<10 e 8<y<10
Precisão; 2 casas decimais
>>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);
SARAMAGO (2003)
Função de aptidão
I=10-8=2, mas com 2 casas decimais;
I= 2.102casas = 2.100 = 200 intervalos;
Cada gene irá representar estes intervalos;
27=128 < 200 < 28=256
Solução: empregar, para cada variável, 8 bits na
representação de escalas de 200 inervalos.
Cada gene é um vetor binário de m bits, sendo m função
da precisão exigida.
Baseado no exemplo de SARAMAGO (2003)
Função de aptidão
Fase 1: Decodificação binária
c  [b7 , b6 ,..., b1, b0 , a7 , a6 ,..., a1, a0 ]
m 1
m 1
x   bi .2
y   ai .2i
i
i 0
i 0
ex: 001100112 = 5110
Fase 2: Ajuste da escala (int p/ real)
e s 
var  sscale  var.  scale m1 scale 
2


ex: x =13310 onde Sscale= 8 e Escale= 10
 10  8 
 2 
x  8  133.  8

8

133.


  9, 04
2

1
255




Baseado no exemplo de SARAMAGO (2003)
Função de aptidão
25510
10
Regra de 3:
255 – 2
133 – x
13310
X=2.133/255
X=1,04
9,04
256inteiro
2real
Como a escala
inicia em 8,
faz-se o ajuste:
X=1,04+8
X=9,04
010
08
Baseado no exemplo de SARAMAGO (2003)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Seleção de indivíduos:
sobrevivência e morte
•
•
•
•
Como selecionamos os cromossomos que
devem sobreviver?
Sobrevivem os que possuem os melhores
níveis de aptidão?
É importante permitir também a sobrevida
de cromossomos menos aptos, do
contrário o método ficaria preso em ótimos
locais
Elitismo
SOUZA (2006)
Seleção de indivíduos

Princípio básico para o direcionamento da
evolução de uma dada população

Utiliza uma função de avaliação para medir a
aptidão de cada indivíduo

Essa aptidão pode ser absoluta ou relativa

Existem vários métodos de seleção
SOUZA (2006)
Seleção de indivíduos: métodos
•
•
•
Roleta
Torneio
Aleatório, etc...
LOPES (2006)
Método da Roleta



Coloca-se os indivíduos em uma roleta, dando a
cada um uma “fatia” proporcional à sua aptidão
relativa
Roda-se a roleta. O indivíduo em cuja fatia a
agulha parar permanece para a próxima
geração
Repete-se o sorteio tantas vezes quanto forem
necessárias para selecionar a quantidade
desejada de indivíduos
LOPES (2006)
Roleta - Exemplo
Indivíduo
Aptidão Absoluta
Aptidão Relativa
1
2
0,052631579
2
4
0,105263158
3
5
0,131578947
4
9
0,236842105
5
18
0,473684211
38
1
Total
LOPES (2006)
Seleção de indivíduos: métodos
•
•
•
Roleta
Torneio
Aleatório, etc...
LOPES (2006)
Método do Torneio
Utiliza sucessivas disputas para realizar a
seleção
 Para selecionar k indivíduos, realiza k
disputas, cada disputa envolvendo n
indivíduos escolhidos ao acaso
 O indivíduo de maior aptidão na disputa é
selecionado
 É muito comum utilizar n = 3

LOPES (2006)
Torneio - 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
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)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Operadores genéticos
CROSSOVER
MUTAÇÃO
SOUZA (2006)
Operadores genéticos
Reprodução (crossover)
 Mutação
 Clonagem, etc...

Operador de Cruzamento
Também chamado de reprodução ou
crossover
 Combina as informações genéticas de
dois indivíduos (pais) para gerar novos
indivíduos (filhos)
 Versões mais comuns criam sempre dois
filhos para cada operação

LOPES (2006)
Operador de Cruzamento
Operador genético principal
 Responsável por gerar novos indivíduos
diferentes (sejam melhores ou piores) a
partir de indivíduos já promissores
 Aplicado a cada par de indivíduos com
alta probabilidade (normalmente entre 0,6
e 0,99)

LOPES (2006)
Abordagens para Cruzamento

Cruzamento Um-Ponto

Cruzamento Multi-Pontos

Cruzamento Uniforme
LOPES (2006)
Cruzamento Um-Ponto
0
0
0
0
Pais
1
1
1
1
0
0
1
1
Filhos
1
1
0
0
LOPES (2006)
Cruzamento Multi-Ponto
0
0
0
0
Pais
1
1
1
1
0
1
1
0
Filhos
1
0
0
1
LOPES (2006)
Cruzamento Uniforme
Máscara
0
1
0
1
0
0
0
0
Pais
1
1
1
1
0
1
0
1
Filhos
1
0
1
0
LOPES (2006)
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
Baseado no exemplo de SARAMAGO (2003)
Operadores genéticos
Reprodução (crossover)
 Mutação
 Clonagem, etc...

LOPES (2006)
Operador de Mutação
Operador randômico de manipulação
 Introduz e mantém a variedade genética
da população
 Garante a possibilidade de se alcançar
qualquer ponto do espaço de busca
 Contorna mínimos locais
 Opera sobre os indivíduos resultantes do
processo de cruzamento

LOPES (2006)
Operador de Mutação
É um operador genético secundário
 Se seu uso for exagerado, reduz a
evolução a uma busca totalmente
aleatória
 Deve atuar com probabilidade baixa
(normalmente entre 0,001 e 0,1)

LOPES (2006)
Operador de Mutação
0
1
1
0
0
0
1
0
1
0
0
0
0
1
LOPES (2006)
Exemplo de Mutação
Baseado no exemplo de SARAMAGO (2003)
Exemplo de Mutação
Para a população final pós-operadores, o processo é reiniciado até ser
encontrado o critério de parada.
Baseado no exemplo de SARAMAGO (2003)
Estrutura
Introdução
 Objetivo e características dos AGs
 Estrutura básica de um AG (fluxograma)
 Função de aptidão
 Seleção de indivíduos
 Operadores genéticos
 Parâmetros genéticos

Parâmetros Genéticos
Tamanho da população
 Taxa de cruzamento
 Taxa de mutação
 Intervalo de geração
 Critério de parada

LOPES (2006)
Referências
EIBEN, A.E. & SMITH, J.E., Apresentação: Introduction to Evolutionary Computing: Genetic
Algorithms,
http://www.cs.vu.nl/~jabekker/ec0607/slides/Lecture03-Chapter3GeneticAlgorithms.ppt ,acessado em 19/10/2006.
GOLDBERG, D. Genetic algorithms in search, optimization and machine learning. AddisonWesley, 1989.
GOLDBARG, M. C. e LUNA, H. P. L., Otimização Combinatória e Programação Linear: modelos
e algoritmos, Rio de Janeiro: Editora Campus, 2000.
LOPES,
L.
R.
M.,
Apresentação:
Fundamentos
de
Algoritmos
Genéticos,
www.cos.ufrj.br/~ines/courses/cos740/leila/cos740/Algoritmos%20Geneticos.ppt ,acessado em
19/10/2006.
PITTMAN, J. , Apresentação: Genetic Algorithm for Variable Selection, Universidade Duke,
http://www.niss.org/affiliates/proteomics200303/presentations20030306/04%
20Jennifer.ppt acessado em 19/10/2006.
SOUZA, M. J. F., Apresentação: Algoritmos genéticos. http://www.iceb.ufop.br/prof/marcone
acessado em 19/10/2006.