Capítulo 12:
Tratamento de Restrições
Lyno Henrique Gonçalves Ferraz
Programa de Engenharia Elétrica - PEE/COPPE/UFRJ
Universidade Federal do Rio de Janeiro
18/05/2012
Motivação (1)
• Algoritmos evolucionários (EA)
– Problemas difíceis
• NP-difícil, NP-completo
– Geralmente restritos
• Nem todas as combinações são possíveis
– Restrições
• Aplicação em EA não trivial
− Operadores “cegos”
• Recombinação e mutação
Problema com Restrições
• O que é um problema com restrições?
– Espaço de busca livre
v1 , v2 , v3 ,...,vn
S  D1  D2  D3  ... Dn
– Depende do algoritmo!
– Caixeiro Viajante
C  {c1 , c2 , c3 ,...,cn }
d (,)
S1  perm{c1 , c2 , c3 ,...,cn }
n


s  S1 | arg min f ( s )   d si , si 1 
i 1


S2  C n
n


s  S 2 | arg min f ( s )   d si , si 1 
i 1


Problema com Restrições
Função Objetivo
Restrições
Não
Sim
Não
Não há problema
Problema de Otimização
Livre
(Free Optimization
Problem – FOP)
Sim
Problema de Atendimento
de Restrições
(Constrain Satisfaction
Problem – CSP)
Problema de Otimização
com Restrições
(Constrained Optimization
Problem – COP)
Problema com Restrições
Função Objetivo
Problema de Otimização Livre
Restrições
Não
Sim
Não há problema
Problema de Otimização
Livre
(Free Optimization
Problem – FOP)
Par (S,f)
S, f 
S : espaço de busca livre
Não
f : função objetivo
Solução:
Problema
ssESS com valor
ótimodedeAtendimento
f
Sim
de Restrições
(Constrain Satisfaction
Problem – CSP)
Problema de Otimização
com Restrições
(Constrained Optimization
Problem – COP)
Problema com Restrições
Problema de Atendimento de Restrições
Par S ,  
Restrições
Função Objetivo
Não de busca livre
S : espaço
Sim
 : fórmula (booleana em
S)
Problema
de Otimização
Não
Sim
Não há problema
Livre
(Free Optimization
Solução:
ssESS com  (s )  true Problem – FOP)
Problema de Atendimento
de Restrições
(Constrain Satisfaction
Problem – CSP)
Problema de Otimização
com Restrições
(Constrained Optimization
Problem – COP)
Problema com Restrições
Problema de Otimização com Restrições
Trio S , f ,  
Função Objetivo
S : espaço de busca livre
Restrições
Não
f : função objetivo
Sim
Problema
de Otimização
 : fórmula (booleana em
S)
Não
Sim
Não há problema
Livre
(Free Optimization
Solução:
Problem – FOP)
ssESS com valor ótimo de f e  (s )  true
Problema de Atendimento
de Restrições
(Constrain Satisfaction
Problem – CSP)
Problema de Otimização
com Restrições
(Constrained Optimization
Problem – COP)
Problema de Otimização com
Restrições
• Caixeiro Viajante
C  {c1 , c2 , c3 ,...,cn }
d (,)
S2  C n
n


s  S 2 | arg min f ( s )   d si , si 1 
i 1


  c  u
c ( s )  true  c  C : !i  1,2,...,n
u ( s )  true  k , l  1,2,...,n: sk  sl
Abordagens para
Tratamento de Restrições
• Tratamento indireto de restrições
– Transformação de restrições
– CSP, COP  FOP
– Realizado antes do EA
• Tratamento direto de restrições
– Resolução de COP
S ,, , S , f ,   S , g,
S ,,    S , f , 
S , f ,  
S , f ,    S , g , 
• Tratamento através de mapeamento
– CSP, COP  FOP
S ,, , S , f ,   S ' , g,
Formas de Tratar Restrições
• Geralmente variáveis discretas
• Opções
–
–
–
–
Funções de penalidade Indireta
Funções de reparo de soluções inviáveis Direta
Representação do problema Direta
Funções decodificadoras Mapeamento
Funções de Penalidade
• Mapeamento da função objetivo
f ' ( x )  f ( x )  P(d ( x , F ))
m
P(d ( x , F ))   wi  di ( x )
i 1
• Tipos
– Estática
– Dinâmica
– Adaptativa
Funções de Penalidade Estática
• Extintivo
– Coeficientes altos
• Binário
– Valor da distância unitário
• Penalidade baseada na distância
• Problema
– Valores dos pesos
Funções de Penalidade
Dinâmicas
• Valores dos pesos
– Dependentes do tempo
si (t )  (wit )
• Divisão em estágios
– Pena de morte para que viola
– Cumprimento parcial de restrições
– Cumprimento obrigatório de restrições
• Aumenta
Funções de Penalidade
Adaptativas
• Abordagens
– Diminuição do impacto de resultados ruins
• Escolha dos pesos
– Dimensionamento adaptativo
• Estatísticas dos melhores resultados
• Distância da restrição
• “proximidade de limiar viável”
– Adaptação do espaço de busca em nível populacional
• Restrições violadas pelo melhor indivíduo
• Atualização de pesos dessas restrições
Funções de Reparo
• Caso especial de busca local
– Remoção da violação
• Substituição
– Aprendizado Baldwiniano
– Aprendizado Lamakiano
• Adição de aleatoriedade
• Complexidade da função de reparo
– GENOCOP III
Representação do Problema
• Limitação do espaço de busca
– Toda região possível  permutação
• Operadores
– Alcançabilidade de toda região
– Geração de indivíduos possíveis
• Desafios
– Operadores
Funções Decodificadores
• Mapeamento genótipos para região possível
• Requisitos
– Genótipo z é mapeado para solução única s
– Toda solução única s deve ter ao menos
uma representação s’
– Toda solução única s deve ter o mesmo
número de representações em S’
• Introdução de redundâncias
S' F
z  S'
s' S '
sF
Exemplo: Pintar 3-cores no Grafo
• Indireto
–
–
–
–
Funções de penalidade
CSP FOP
Strings ternárias
Penalidades
• “Arestas incorretas”
• “Nós incorretos”
– Aplicação de componentes
padrões
cj
Ci
f1 ( s )   w j   s , c j 
m
j 1
n

f 2 ( s )   wi   s , C i

i 1
1 se s viola k
 s ,     senão
0
Exemplo: Pintar 3-cores no Grafo
• Direto  Decodificador
– Cromossomos
• Permutações de nós
• Procedimento
S  { ,  ,  }n  S '  {s  S | si  s j
– Função objetivo
• Somatório de nós sem cor
– Aplicação de componentes
padrões
(i, j  1,2,...,n)}