Computação Evolucionária:Conceitos Básicos de Otimização
Prof. Dr. Rafael Stubs ParpinelliE-mail: [email protected]
OtimizaçãoMin ou Max
Sujeito a
Função objetivo A qual se quer maximizar ou minimizar
Ex: max(lucro), min(custo)
Pode não existir ou ser múltipla
Conjunto de variáveis Que afetam o valor da função objetivo Em problemas complexos este conjunto pode ser muito
grande
Conjunto de restrições Não permite que o conjunto de variáveis assuma
determinados valores
Otimização
Otimização
Definição de Otimização Processo de melhoramento iterativo/interativo de
uma solução para um problema, com respeito a uma função objetiva específica
Problemas típicos da área de otimização Maximização (minimização) de funções algébricas Problemas combinatoriais (caixeiro viajante,
problema da mochila, escalonamento de tarefas...) Projetos de engenharia (maximização de
desempenho, minimização de custo...)
Tipos de ProblemasFunção Objetivo
SIM NÃO
Restrições
SIM COP CSP
NÃO FOP
COP: Problema de Otimização com Restrições (Constrained Optimization Problem)
CSP: Problema de Satisfação de Restrições (Constraint Satisfaction Problem)
FOP: Problema Livre de Restrições (Free Optimziation Problem)
Problemas de Otimização: Dentre as soluções viáveis, qual é a melhor?
Otimização
Otimização Contínua: variáveis assumem valores reais (ou contínuos)
Otimização Combinatória ou Discreta: variáveis com valores discretos (ou inteiros)
Otimização Mista: variáveis inteiras e contínuas
Otimização multiobjetivos O conceito de ótimo não é óbvio e deve respeitar a individualidade de cada critério Otimalidade de Pareto:
Conjunto de soluções P-ótimas e não um único ponto
Minimizar Custo e Número de Acidentes
Dominância: Neste caso: P-ótimo: {A, B, C}
Características do Espaço do Problema
Métodos de soluções de problemas
Métodos fortes Para problemas genéricos em um mundo específico
(linearidade e estacionariedade). Podem garantir uma solução ótima.
Métodos específicos Para problemas específicos em mundos específicos.
Métodos fracos Para problemas genéricos em mundos genéricos (pode
haver não-linearidade e não estacionariedade). Não garantem uma solução ótima, eventualmente uma solução satisfatória.
Métodos de otimização
Enumerativos Busca exaustiva
Numéricos Analíticos: derivadas parciais Diretos: técnicas de gradiente (steepest descent ou
hill-climbing)
Probabilísticos (Heurísticas e Meta-heurísticas) Busca aleatória Simulated Annealing Computação Evolucionária Inteligência de Enxame
Métodos enumerativos
Excelentes para um grande número de problemas, entretanto:
Aplicável somente a problemas de “dimensões pequenas”
Aceitável quando envolve tempos computacionais “razoáveis”
Tendem a ser cada vez mais utilizados a medida que a capacidade computacional disponível aumenta.
Quando utilizar IC para otimização?
Quando a aplicação de métodos fortes ou específicos são inviáveis Quando a complexidade do problema torna inviável sua formulação matemática Quando o número de possíveis soluções a serem examinadas leva a uma explosão combinatória intratável Quando o problema é fortemente não estacionário Quando não existe outra alternativa viável
Necessidade de métodos heurísticos e meta-heurísticos
Problemas complexos: problemas do mundo real Problemas que demandam tempos de processamento muito grandes Métodos heurísticos são executados em tempos aceitáveis, porém não garantem a obtenção da solução ótima, nem mesmo garantem encontrar-se uma solução factível Entretanto, o objetivo de um método heurístico é tentar encontrar uma solução “aceitável” de maneira simples e rápida
Natureza como Inspiração O conceito de otimização pode ser abstraído de
diferentes processos naturais Evolução das espécies Comportamento de grupos sociais Sinapses de neurônios Dinâmica do sistema imunológico Estratégias de busca por alimento Relações ecológicas Sonar de morcego Teias de aranha
Aplicações Funções benchmark
Mineração de Dados
Robótica: planejamento de trajetórias
Processamento de imagens
Projeto de circuitos
Pesquisa operacional:
empacotamento 1D, 2D, 3D, ...,
alocação de recursos
alocação de facilidades, ...
Econometria
Planejamento, previsão e despacho de carga
Bioinformática (filogenia, predição de estruturas)
Problemas de engenharia estrutural
Controle preditivo inteligente
Redes de computadores
Alocação de navios em portos
Treinamento de redes neurais
Arte e música, etc ...