Computação Evolucionária:Conceitos Básicos de Otimização

Prof. Dr. Rafael Stubs ParpinelliE-mail: rafael.parpinelli@udesc.br

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 ...