Upload
others
View
3
Download
1
Embed Size (px)
Citation preview
Otimização MultiobjetivoIntrodução
Professores:
Eduardo G. CarranoFrederico G. Guimarães
Lucas S. Batista
{egcarrano,fredericoguimaraes,lusoba}@ufmg.brwww.ppgee.ufmg.br/∼lusoba
Universidade Federal de Minas GeraisPrograma de Pós-Graduação em Engenharia Elétrica, Brasil
Introdução Literatura Especializada
Apresentação
Sumário
1 IntroduçãoApresentaçãoMetaheurísticasOtimização multiobjetivo
2 / 36
Introdução Literatura Especializada
Apresentação
O que é Otimização?
Em qualquer processo de engenharia, decisões gerenciais outecnológicas devem ser tomadas em diversos estágios.
Frequentemente, o custo ou o benefício dessas escolhas podeser expresso por meio de uma função de determinadas variáveisde decisão.
Obter o melhor arranjo dessas variáveis que minimiza ou maxi-miza essa função mérito consiste em um processo de otimização.
3 / 36
Introdução Literatura Especializada
Apresentação
O que é Otimização?
Otimização: processo que utiliza métodos computacionais paraencontrar a “melhor” forma de projetar e/ou operar um dado sis-tema, representada pela melhor combinação de valores para asvariáveis do problema (solução ótima), considerando seus objeti-vos e suas restrições de projeto e de operação.
O processo de otimização sempre resulta, ou busca justificação,em um impacto econômico: qualidade do produto, custo da pro-dução, competitividade.
4 / 36
Introdução Literatura Especializada
Apresentação
O que é Otimização?
OtimizarSignifica minimizar ou maximizar uma dada função:
Encontrar x ∈ F : f (x) ≤ f (y), ∀ y ∈ F
minx
f (x), x ∈ F
5 / 36
Introdução Literatura Especializada
Apresentação
O que é Otimização?
OtimizarSignifica minimizar ou maximizar uma dada função:
minx
f(x) ∈ Rm, x ∈ F
f : X ⊂ Rn 7→ Y ⊂ Rm
X = {x = (x1 . . . xn), xi ∈ Di}
F =
gi(x) ≤ 0; i = 1, . . . ,phj(x) = 0; j = 1, . . . ,qx ∈ X
6 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Quanto ao número de objetivos:
Otimização mono-objetivo vs. Otimização multiobjetivo (multicri-tério, multidesempenho ou vetorial)
f : X ⊂ Rn 7→ Y ⊂ Rm
Quanto ao domínio das variáveis:Otimização discreta ou combinatória vs. Otimização contínua
X = {x = (x1 . . . xn), xi ∈ Di}
7 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Quanto às restrições:
Otimização restrita vs. Otimização irrestrita
F =
gi(x) ≤ 0; i = 1, . . . ,phj(x) = 0; j = 1, . . . ,qx ∈ X
Restrição: limitações físicas, tempo de processamento, etc.
Podem ser explícitas ou implícitas.
Problema overconstrained (q ≥ n).
8 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Formulação geral do problema de otimização:
minx
f(x) ∈ Rm, x ∈ F
F =
gi(x) ≤ 0; i = 1, . . . ,phj(x) = 0; j = 1, . . . ,qx ∈ X
Espaços Euclidianos: parâmetros (Rn) e objetivos (Rm).
Cada ponto no primeiro espaço representa uma solução, a qualcaracteriza um certo ponto no segundo.
Os objetivos podem ser linear, não linear, contínuo, ou discreto.
9 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Caso particular (programação linear):
minx
Cx ∈ Rm, x ∈ F
F =
∑
k aik xk ≤ 0; i = 1, . . . ,p∑k bjk xk = 0; j = 1, . . . ,q
x ≥ 0
10 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Vetor Ideal ou Solução Utópica:
Suponha o vetor x∗(k) tal que fk (x∗(k)) = optx fk (x);
A solução utópica f∗ = [f ∗1 , f∗2 , . . . , f
∗k , . . . , f
∗m] minimiza todos os
objetivos simultaneamente.
11 / 36
Introdução Literatura Especializada
Apresentação
Problema de Otimização
Condições de otimalidade:
Se uma solução x é eficiente (não inferior ou Pareto-ótima), ascondições necessárias para otimalidade são:
∑m
k=1 wk∇fk (x) +∑p
i=1 µi∇gi(x) +∑q
j=1 λj∇hj(x) = 0µigi(x) = 0, i = 1, . . . ,phj(x) = 0, j = 1, . . . ,q
12 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
Dois tipos de problemas de otimização são claramente postos:problemas “discretos” e problemas com variáveis contínuas.
Problemas discretos: caixeiro viajante, roteamento de veículos.
Problemas contínuos: máquinas elétricas, controladores PI.
Problemas mistos: envolvem simultaneamente variáveis discre-tas e contínuas.
Essa diferenciação é útil para definir o domínio de “dificuldade”do problema de otimização.
13 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
Otimização combinatória: problemas para os quais não se co-nhece nenhum algoritmo exato rápido, ou seja, problemas daclasse NP-hard.
Otimização contínua: problemas para os quais não se conheceum algoritmo exato rápido capaz de localizar o ótimo global emum número finito de iterações.
14 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
Muito esforço foi dedicado, separadamente, à solução dessesproblemas:
No campo dos problemas contínuos “difíceis”. . .
Existe um arcabouço significativo de métodos tradicionais para otimi-zação global. Entretanto, sua efetividade depende de propriedadesespecíficas do problema, e.g., diferenciabilidade, convexidade, moda-lidade.
No campo dos problemas discretos “difíceis”. . .
Existe um arsenal de heurísticas, as quais encontram soluções pró-ximas do ótimo. Entretanto, a maioria delas é concebida para umproblema específico.
15 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
“There are no easy methods to solve hard problems”(René Descartes)
16 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
Métodos exatos fornecem garantias sobre a otimalidade da soluçãoencontrada. No caso de problemas NP-difíceis, nãoexiste (ou muito provavelmente não existe) algoritmoque garanta que a solução exata seja encontrada emtempo polinomial.
Métodos de aproximação garantem uma solução aproximada do pro-blema em tempo polinomial. Fornece limitantes para asolução ótima.
17 / 36
Introdução Literatura Especializada
Apresentação
Hard optimization
Heurísticas são técnicas que visam fornecer soluções razoáveis ra-pidamente, sem fornecer garantias formais sobre a qua-lidade dessas soluções. Ganha-se em eficiência ou emsimplicidade conceitual, ao custo de precisão e forma-lismo.
Metaheurísticas são métodos heurísticos que combinam procedimen-tos - geralmente outras heurísticas - para resolver pro-blemas computacionais usando estratégias de alto nível(portanto, “meta”). Aplicados para se encontrar solu-ções satisfatórias para problemas complexos de otimi-zação.
18 / 36
Introdução Literatura Especializada
Metaheurísticas
Sumário
1 IntroduçãoApresentaçãoMetaheurísticasOtimização multiobjetivo
19 / 36
Introdução Literatura Especializada
Metaheurísticas
Metaheurísticas
Metaheurísticas (MHs) possuem raízes na Inteligência Artificialnas décadas de 1960 e 1970, porém atingiram popularidade ematuridade a partir da década de 1990;
Características:Fácil implementação;Guiam o processo de busca;Capacidade de escapar de mínimos locais;Produzem boas soluções rapidamente (near-optimal solutions);Não garantem a otimalidade da solução obtida;São métodos aproximados e usualmente não-determinísticos.
20 / 36
Introdução Literatura Especializada
Metaheurísticas
Metaheurísticas
Algumas definições:
A metaheuristic is formally defined as an iterativegeneration process which guides a subordinate heuristic bycombining intelligently different concepts for exploring andexploiting the search space, learning strategies are used tostructure information in order to find efficiently near-optimalsolutions (Osman & Laporte 1996).
21 / 36
Introdução Literatura Especializada
Metaheurísticas
Metaheurísticas
Algumas definições:Metaheuristics are typically high-level strategies which
guide an underlying, more problem specific heuristic, toincrease their performance. The main goal is to avoid thedisadvantages of iterative improvement and, in particular,multiple descent by allowing the local search to escape fromlocal optima. This is achieved by either allowing worseningmoves or generating new starting solutions for the localsearch in a more “intelligent” way than just providing randominitial solutions. (...) Many of the metaheuristic approachesrely on probabilistic decisions made during the search. But,the main difference to pure random search is that inmetaheuristic algorithms randomness is not used blindly butin an intelligent, biased form (Stützle 1999).
22 / 36
Introdução Literatura Especializada
Metaheurísticas
Metaheurísticas
A chegada das MHs marca uma reconciliação de ambos os do-mínios de otimização.
De fato, elas são aplicadas a todos os tipos de problemas discre-tos, e podem ser adaptadas a problemas contínuos.
Possuem em comum as seguintes características:
são estocásticas;
possuem origem discreta, e mesmo em problemas contínuos nãoexigem diferenciabilidade, convexidade, modalidade;
são inspiradas em analogias físicas (SA), biológicas (TS, EAs) ouetológicas (ACO, PSO);
compartilham as mesmas desvantagens, i.e., ajuste de parâmetrose alto custo computacional.
23 / 36
Introdução Literatura Especializada
Metaheurísticas
Metaheurísticas
Em geral, é impossível assegurar com certeza a efetividade deuma dada MH quando aplicada a um dado problema.
As MHs não são mutualmente excludentes. A tendência atualé a utilização de métodos híbridos, buscando beneficiar-se devantagens específicas combinadas.
As MHs podem ser facilmente estendidas para:
otimização multiobjetivo;
otimização multimodal;
otimização dinâmica;
implementações paralelas.
24 / 36
Introdução Literatura Especializada
Metaheurísticas
Filosofias
Extensões “inteligentes” de algoritmos de busca local: é ocaso de Simulated Annealing, Busca Tabu, Iterated Local Search,GRASP, entre outros. Também chamados métodos de trajetóriaou busca em vizinhança.
População distribuída de soluções: É o caso dos AlgoritmosEvolucionários, Programação Genética, Estratégias Evolutivas,Colônia de Formigas, Swarm Intelligence, Sistemas Imunes Artifi-ciais. Estes métodos incorporam uma componente de aprendiza-gem e funcionam como uma amostragem polarizada do espaçode busca. Em geral inspirados na natureza para produzir formasnão convencionais de se resolver problemas.
25 / 36
Introdução Literatura Especializada
Metaheurísticas
Limitação Geral de Métodos Clássicos
Métodos clássicos, ou métodos de decida, aceitam somente “mo-vimentos” de melhora (possuem convergência monotônica).
Esses algoritmos de aperfeiçoamento iterativo não conduzem,em geral, ao ótimo global, mas a um mínimo local específico (cn).
26 / 36
Introdução Literatura Especializada
Metaheurísticas
Limitação Geral de Métodos Clássicos
Para melhorar a efetividade dos métodos clássicos, eles podemser aplicados repetidas vezes, partindo de configurações iniciaisdistintas.
Esse processo, entretanto, aumenta o custo computacional doalgoritmo, não garante a determinação do ótimo c∗, e torna-seinefetivo com o aumento do número de mínimos locais.
27 / 36
Introdução Literatura Especializada
Metaheurísticas
Fonte de Efetividade das MHs
MHs são capazes de escapar de ótimos locais!!!MHs baseadas em “vizinhança” (SA, VNS, ILS) aceitam a degra-dação temporária da solução, permitindo encontrar cn, c′n e c∗.MHs “distribuídas” evoluem paralelamente uma população de so-luções candidatas, e empregam estratégias específicas para ex-ploração do espaço de busca.
28 / 36
Introdução Literatura Especializada
Metaheurísticas
Classificação geral dos métodos de otimização
29 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Sumário
1 IntroduçãoApresentaçãoMetaheurísticasOtimização multiobjetivo
30 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Introdução
Principal dificuldade em otimização mono-objetivo: modelar umproblema em uma única equação (função-objetivo);
Otimização multiobjetivo introduz uma certa flexibilidade à mode-lagem;
Essa flexibilidade tem um preço: não há uma única solução de-finida, mas um conjunto de soluções de compromisso (soluçõesde Pareto).
Para refletir:O problema mono-objetivo é mais bem formulado do que o problemamultiobjetivo?
31 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Otimização e Decisão
Encontrado um conjunto de soluções, qual solução será de fatoimplementada?
O resultado de um problema de otimização multiobjetivo leva aum problema de decisão: um ou mais tomadores de decisão de-verão escolher entre o conjunto de alternativas aquela que semostra mais interessante.
funções de utilidade;
decisão multicritério.
32 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Métodos de Decisão Multiobjetivo
A priori O tradeoff entre as funções-objetivo é determinado (emodelado) antes da execução do método de otimiza-ção. O problema multiobjetivo é transformado num pro-blema mono-objetivo e uma única solução é gerada. Al-terando a relação de tradeoff entre os objetivos, umanova solução pode ser gerada, até que o decisor estejasatisfeito. (decide⇒ otimiza)
Progressivo Nos métodos de otimização progressivos, consultas aodecisor durante a otimização orientam a busca na dire-ção da solução de tradeoff que satisfaz o decisor. Re-quer a atenção do decisor durante o processo de otimi-zação. (decide⇔ otimiza)
33 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Métodos de Decisão Multiobjetivo
A posteriori Os métodos são projetados para buscar por um con-junto de soluções representativo no espaço de objeti-vos. O resultado é um conjunto de alternativas que sãooferecidas ao decisor após a otimização. Não é neces-sária a modelagem de preferências do decisor, mas oprocesso de otimização é mais complexo e computaci-onalmente caro, porque várias soluções devem ser ge-radas. (otimiza⇒ decide)
A escolha do método depende do tomador de decisão e do problema.Frequentemente, adotam-se métodos a posteriori em conjunto commetaheurísticas multiobjetivo.
34 / 36
Introdução Literatura Especializada
Otimização multiobjetivo
Classificação dos Algoritmos
35 / 36
Introdução Literatura Especializada
Referências Bibliográficas
Y. Collette and P. Siarry. Multiobjective Optimization: Principles and Case Studies.Springer, 2004.
J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard. Metaheuristics for Hard Optimiza-tion: Methods and Case Studies. Springer, 2005.
C.A. Coello Coello, G.B. Lamont, and D.A. Van Veldhuizen. Evolutionary Algo-rithms for Solving Multi-Objective Problems. Springer, 2007.
Início
36 / 36