Otimização global - Global optimization
A otimização global é um ramo da matemática aplicada e da análise numérica que tenta encontrar os mínimos ou máximos globais de uma função ou conjunto de funções em um determinado conjunto. Geralmente é descrito como um problema de minimização porque a maximização da função de valor real é equivalente à minimização da função .
Dada uma função contínua possivelmente não linear e não convexa com os mínimos globais e o conjunto de todos os minimizadores globais em , o problema de minimização padrão pode ser dado como
isto é, encontrar e um minimizador global em ; onde é um conjunto compacto (não necessariamente convexo) definido por desigualdades .
A otimização global se distingue da otimização local por seu foco em encontrar o mínimo ou máximo em um determinado conjunto, em oposição a encontrar mínimos ou máximos locais . Encontrar um mínimo local arbitrário é relativamente simples usando métodos clássicos de otimização local . Encontrar o mínimo global de uma função é muito mais difícil: os métodos analíticos frequentemente não são aplicáveis, e o uso de estratégias de solução numérica geralmente leva a desafios muito difíceis.
Teoria geral
Uma abordagem recente ao problema de otimização global é por meio da distribuição de mínimos . Neste trabalho, uma relação entre qualquer função contínua em um conjunto compacto e seus mínimos globais foi estritamente estabelecida. Como um caso típico, segue-se que
Enquanto isso,
onde está a medida de Lebesgue -dimensional do conjunto de minimizadores . E se não for uma constante no , a relação monotônica
vale para todos e , o que implica uma série de relações de contenção monótonas, e uma delas é, por exemplo,
E definimos uma distribuição mínima como um limite fraco, de modo que a identidade
é válido para todas as funções suaves com suporte compacto em . Aqui estão duas propriedades imediatas de :
- (1) satisfaz a identidade .
- (2) Se for contínuo ativado , então .
Como comparação, a conhecida relação entre qualquer função convexa diferenciável e seus mínimos é estritamente estabelecida pelo gradiente. Se é diferenciável em um conjunto convexo , então é convexo se e somente se
assim, implica que vale para todos , ou seja, é um minimizador global de on .
Formulários
Exemplos típicos de aplicativos de otimização global incluem:
- Previsão da estrutura da proteína (minimizar a função energia / energia livre)
- Filogenética computacional (por exemplo, minimizar o número de transformações de caracteres na árvore)
- Problema do caixeiro viajante e projeto do circuito elétrico (minimizar o comprimento do caminho)
- Engenharia química (por exemplo, analisando a energia de Gibbs )
- Verificação de segurança , engenharia de segurança (por exemplo, de estruturas mecânicas, edifícios)
- Análise de pior caso
- Problemas matemáticos (por exemplo, a conjectura de Kepler )
- Problemas de empacotamento de objetos (projeto de configuração)
- O ponto de partida de várias simulações de dinâmica molecular consiste em uma otimização inicial da energia do sistema a ser simulado.
- Óculos giratórios
- Calibração de modelos de propagação de rádio e de muitos outros modelos nas ciências e engenharia
- Ajuste de curva como análise de mínimos quadrados não lineares e outras generalizações, usado para ajustar parâmetros de modelo a dados experimentais em química, física, biologia, economia, finanças, medicina, astronomia, engenharia.
- Planejamento da radioterapia IMRT
Métodos determinísticos
As estratégias gerais exatas de maior sucesso são:
Aproximação interna e externa
Em ambas as estratégias, o conjunto sobre o qual uma função deve ser otimizada é aproximado por poliedros. Na aproximação interna, os poliedros estão contidos no conjunto, enquanto na aproximação externa, os poliedros contêm o conjunto.
Métodos de plano de corte
O método do plano de corte é um termo abrangente para métodos de otimização que refinam iterativamente um conjunto viável ou função objetivo por meio de desigualdades lineares, chamadas de cortes . Tais procedimentos são usados popularmente para encontrar soluções inteiras para problemas de programação linear inteira mista (MILP), bem como para resolver problemas gerais de otimização convexa não necessariamente diferenciáveis . O uso de planos de corte para resolver o MILP foi introduzido por Ralph E. Gomory e Václav Chvátal .
Métodos de ramificação e limite
Branch and bound ( BB ou B&B ) é um paradigma de projeto de algoritmo para problemas de otimização discreta e combinatória . Um algoritmo branch-and-bound consiste em uma enumeração sistemática de soluções candidatas por meio de pesquisa no espaço de estados : o conjunto de soluções candidatas é pensado como formando uma árvore enraizada com o conjunto completo na raiz. O algoritmo explora ramos desta árvore, que representam subconjuntos do conjunto de soluções. Antes de enumerar as soluções candidatas de uma ramificação, a ramificação é verificada em relação aos limites estimados superior e inferior da solução ótima e é descartada se não puder produzir uma solução melhor do que a melhor encontrada até agora pelo algoritmo.
Métodos de intervalo
Aritmética de intervalo , matemática de intervalo , análise de intervalo ou computação de intervalo , é um método desenvolvido por matemáticos desde 1950 e 1960 como uma abordagem para colocar limites em erros de arredondamento e erros de medição em computação matemática e, assim, desenvolver métodos numéricos que produzem resultados confiáveis. A aritmética de intervalo ajuda a encontrar soluções confiáveis e garantidas para equações e problemas de otimização.
Métodos baseados em geometria algébrica real
Álgebra real é a parte da álgebra que é relevante para a geometria algébrica real (e semialgébrica). Está principalmente preocupado com o estudo de campos ordenados e anéis ordenados (em particular campos fechados reais ) e suas aplicações ao estudo de polinômios positivos e somas de quadrados de polinômios . Pode ser usado na otimização convexa
Métodos estocásticos
Existem vários algoritmos baseados em Monte-Carlo exatos ou inexatos:
Amostragem Monte-Carlo direta
Neste método, simulações aleatórias são usadas para encontrar uma solução aproximada.
Exemplo: O problema do caixeiro viajante é o que se chama de problema de otimização convencional. Ou seja, todos os fatos (distâncias entre cada ponto de destino) necessários para determinar o caminho ideal a seguir são conhecidos com certeza e o objetivo é percorrer as opções de viagem possíveis para chegar àquele com a menor distância total. No entanto, vamos supor que, em vez de querer minimizar a distância total percorrida para visitar cada destino desejado, quiséssemos minimizar o tempo total necessário para chegar a cada destino. Isso vai além da otimização convencional, pois o tempo de viagem é inerentemente incerto (congestionamentos, hora do dia, etc.). Como resultado, para determinar nosso caminho ideal, gostaríamos de usar simulação - otimização para primeiro entender a gama de tempos potenciais que poderia levar para ir de um ponto a outro (representado por uma distribuição de probabilidade, neste caso, em vez de uma distância específica) e então otimizar nossas decisões de viagem para identificar o melhor caminho a seguir levando essa incerteza em consideração.
Tunelamento estocástico
O tunelamento estocástico (STUN) é uma abordagem para otimização global baseada no método Monte Carlo - amostragem da função a ser objetivamente minimizada na qual a função é transformada de forma não linear para permitir um tunelamento mais fácil entre regiões contendo mínimos de função. O tunelamento mais fácil permite uma exploração mais rápida do espaço da amostra e uma convergência mais rápida para uma boa solução.
Têmpera paralela
A têmpera paralela , também conhecida como amostragem MCMC de troca de réplicas , é um método de simulação que visa melhorar as propriedades dinâmicas das simulações do método Monte Carlo de sistemas físicos e dos métodos de amostragem Monte Carlo por cadeia de Markov (MCMC) de forma mais geral. O método de troca de réplicas foi originalmente concebido por Swendsen, depois estendido por Geyer e posteriormente desenvolvido, entre outros, por Giorgio Parisi ., Sugita e Okamoto formularam uma versão de dinâmica molecular de têmpera paralela: isso geralmente é conhecido como dinâmica molecular de troca de réplicas ou REMD .
Essencialmente, executa-se N cópias do sistema, inicializadas aleatoriamente, em diferentes temperaturas. Então, com base no critério de Metrópolis, troca-se as configurações em diferentes temperaturas. A ideia desse método é disponibilizar configurações em altas temperaturas para as simulações em baixas temperaturas e vice-versa. Isso resulta em um conjunto muito robusto que é capaz de amostrar configurações de baixa e alta energia. Desta forma, propriedades termodinâmicas como o calor específico, que em geral não é bem calculado no conjunto canônico, podem ser calculadas com grande precisão.
Heurísticas e metaheurísticas
- Página principal: Metaheurística
Outras abordagens incluem estratégias heurísticas para pesquisar o espaço de busca de uma forma mais ou menos inteligente, incluindo:
- Otimização de colônia de formigas (ACO)
- Simulated annealing , uma metaheurística probabilística genérica
- Pesquisa Tabu , uma extensão da pesquisa local capaz de escapar dos mínimos locais
- Algoritmos evolutivos (por exemplo, algoritmos genéticos e estratégias de evolução )
- Evolução diferencial , um método que otimiza um problema tentando iterativamente melhorar uma solução candidata com relação a uma determinada medida de qualidade
- Algoritmos de optimização baseada Swarm (por exemplo, optimização de partícula enxame , optimização social cognitiva , optimização multi-enxame e optimização formigueiro )
- Algoritmos meméticos , combinando estratégias de pesquisa globais e locais
- Otimização de pesquisa reativa (ou seja, integração de técnicas de aprendizado de máquina sub-simbólicas em heurísticas de pesquisa)
- Otimização graduada , uma técnica que tenta resolver um problema de otimização difícil resolvendo inicialmente um problema muito simplificado e transformando progressivamente esse problema (enquanto otimiza) até que seja equivalente ao problema de otimização difícil.
Abordagens baseadas em metodologia de superfície de resposta
- Otimização indireta IOSO baseada em auto-organização
- Otimização Bayesiana , uma estratégia de projeto sequencial para otimização global de funções de caixa preta usando estatísticas Bayesianas
Veja também
- Otimização global determinística
- Otimização de design multidisciplinar
- Otimização multiobjetivo
- Otimização (matemática)
Notas de rodapé
Referências
Otimização global determinística:
- R. Horst, H. Tuy, Global Optimization: Deterministic Approaches , Springer, 1996.
- R. Horst, PM Pardalos e NV Thoai, Introdução à Otimização Global , Segunda Edição. Kluwer Academic Publishers, 2000.
- A. Neumaier, Pesquisa Completa em Otimização Global Contínua e Satisfação de Restrições, pp. 271-369 em: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
- M. Mongeau, H. Karsenty, V. Rouzé e J.-B. Hiriart-Urruty, Comparison of public-domain software for black box global optimization . Optimization Methods & Software 13 (3), pp. 203–226, 2000.
- JD Pintér, Otimização Global em Ação - Otimização Contínua e Lipschitz: Algoritmos, Implementações e Aplicações . Kluwer Academic Publishers, Dordrecht, 1996. Agora distribuído pela Springer Science and Business Media, Nova York. Este livro também discute métodos de otimização global estocástica.
- L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Análise de intervalo aplicada. Berlim: Springer.
- ER Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.
Para recozimento simulado:
- Kirkpatrick, S .; Gelatt, CD; Vecchi, MP (1983-05-13). "Otimização por recozimento simulado". Ciência . Associação Americana para o Avanço da Ciência (AAAS). 220 (4598): 671–680. doi : 10.1126 / science.220.4598.671 . ISSN 0036-8075 . PMID 17813860 .
Para otimização de pesquisa reativa:
- Roberto Battiti , M. Brunato e F. Mascia, Pesquisa Reativa e Otimização Inteligente, Pesquisa de Operações / Série de Interfaces de Ciência da Computação, Vol. 45, Springer, novembro de 2008. ISBN 978-0-387-09623-0
Para métodos estocásticos:
- A. Zhigljavsky . Teoria da Pesquisa Aleatória Global. Matemática e suas aplicações. Kluwer Academic Publishers. 1991.
- Hamacher, K (2006). "Adaptação na otimização global de tunelamento estocástico de paisagens de energia potencial complexas". Cartas Europhysics (EPL) . Publicação do IOP. 74 (6): 944–950. doi : 10.1209 / epl / i2006-10058-0 . ISSN 0295-5075 .
- Hamacher, K .; Wenzel, W. (01/01/1999). "Escalando o comportamento de algoritmos de minimização estocástica em uma paisagem de funil perfeita". Physical Review E . 59 (1): 938–941. arXiv : física / 9810035 . doi : 10.1103 / physreve.59.938 . ISSN 1063-651X .
- Wenzel, W .; Hamacher, K. (12/04/1999). "Abordagem de Tunelamento Estocástico para Minimização Global de Paisagens de Energia Potencial Complexa". Cartas de revisão física . American Physical Society (APS). 82 (15): 3003–3007. arXiv : física / 9903008 . doi : 10.1103 / physrevlett.82.3003 . ISSN 0031-9007 .
Para têmpera paralela:
- Hansmann, Ulrich HE (1997). "Algoritmo de têmpera paralela para estudos conformacionais de moléculas biológicas". Cartas de Física Química . Elsevier BV. 281 (1–3): 140–150. arXiv : física / 9710041 . doi : 10.1016 / s0009-2614 (97) 01198-6 . ISSN 0009-2614 .
Para métodos de continuação:
- Zhijun Wu. O esquema de transformação de energia efetiva como uma abordagem de continuação especial para a otimização global com aplicação à conformação molecular . Relatório Técnico, Argonne National Lab., IL (Estados Unidos), novembro de 1996.
Para considerações gerais sobre a dimensionalidade do domínio de definição da função objetivo:
- Hamacher, Kay (2005). "Na otimização global estocástica de funções unidimensionais". Physica A: Mecânica Estatística e suas Aplicações . Elsevier BV. 354 : 547–557. doi : 10.1016 / j.physa.2005.02.028 . ISSN 0378-4371 .
Para estratégias que permitem comparar métodos de otimização global determinísticos e estocásticos