Otimização estocástica - Stochastic optimization

Métodos de otimização estocástica ( SO ) são métodos de otimização que geram e usam variáveis ​​aleatórias . Para problemas estocásticos, as variáveis ​​aleatórias aparecem na formulação do próprio problema de otimização, que envolve funções objetivo aleatórias ou restrições aleatórias. Os métodos de otimização estocástica também incluem métodos com iterações aleatórias. Alguns métodos de otimização estocástica usam iterações aleatórias para resolver problemas estocásticos, combinando os dois significados de otimização estocástica. Métodos de otimização estocástica generalizar determinísticos métodos para problemas determinísticos.

Métodos para funções estocásticas

Dados de entrada parcialmente aleatórios surgem em áreas como estimativa e controle em tempo real, otimização baseada em simulação onde as simulações de Monte Carlo são executadas como estimativas de um sistema real e problemas onde há erro experimental (aleatório) nas medições do critério. Nesses casos, o conhecimento de que os valores da função estão contaminados por "ruído" aleatório leva naturalmente a algoritmos que usam ferramentas de inferência estatística para estimar os valores "verdadeiros" da função e / ou tomar decisões estatisticamente ótimas sobre as próximas etapas. Os métodos desta classe incluem:

• aproximação estocástica (SA), de Robbins e Monro (1951)
• descida gradiente estocástico
• SA de diferença finita por Kiefer e Wolfowitz (1952)
• perturbação simultânea SA por Spall (1992)
• otimização de cenário

Métodos de pesquisa randomizados

Por outro lado, mesmo quando o conjunto de dados consiste em medições precisas, alguns métodos introduzem aleatoriedade no processo de busca para acelerar o progresso. Essa aleatoriedade também pode tornar o método menos sensível a erros de modelagem. Além disso, a aleatoriedade injetada pode permitir que o método escape de um ótimo local e, eventualmente, se aproxime de um ótimo global. Na verdade, esse princípio de randomização é conhecido por ser uma maneira simples e eficaz de obter algoritmos com desempenho quase certo de maneira uniforme em muitos conjuntos de dados, para muitos tipos de problemas. Os métodos de otimização estocástica desse tipo incluem:

• recozimento simulado por S. Kirkpatrick, CD Gelatt e MP Vecchi (1983)
• recozimento quântico
• Coletivos de probabilidade por DH Wolpert, SR Bieniawski e DG Rajnarayan (2011)
• otimização de busca reativa (RSO) de Roberto Battiti , G. Tecchiolli (1994), recentemente revisado no livro de referência
• método de entropia cruzada de Rubinstein e Kroese (2004)
• pesquisa aleatória por Anatoly Zhigljavsky (1991)
• Busca informativa
• tunelamento estocástico
• têmpera paralela aka troca de réplicas
• escalada estocástica de colina
• algoritmos de enxame
• algoritmos evolutivos
  • algoritmos genéticos de Holland (1975)
  • estratégias de evolução
• algoritmo de modificação e otimização de objetos em cascata (2016)

Em contraste, alguns autores argumentaram que a randomização só pode melhorar um algoritmo determinístico se o algoritmo determinístico foi mal projetado em primeiro lugar. Fred W. Glover argumenta que a dependência de elementos aleatórios pode impedir o desenvolvimento de componentes mais inteligentes e determinísticos melhores. A forma como os resultados dos algoritmos de otimização estocástica são normalmente apresentados (por exemplo, apresentando apenas a média, ou mesmo a melhor, de N execuções sem qualquer menção ao spread), também pode resultar em um viés positivo em direção à aleatoriedade.

Veja também

• Otimização Global
• Aprendizado de máquina
• Otimização de cenário
• Processo gaussiano
• Modelo de Espaço Estadual
• Controle preditivo de modelo
• Programação não linear
• Valor entrópico em risco

Referências

Leitura adicional

• Michalewicz, Z. e Fogel, DB (2000), How to Solve It: Modern Heuristics , Springer-Verlag, New York.
• " PSA: Um novo algoritmo de otimização baseado em regras de sobrevivência de scaber porcellio ", Y. Zhang e S. Li

links externos

• COSP