otimização aleatório - Random optimization

Optimização aleatório (RO) é uma família de numéricos de optimização de métodos que não exigem o gradiente do problema a ser optimizado e RO pode, portanto, ser utilizada em funções que não são contínua ou diferenciáveis . Tais métodos de otimização são também conhecidos como métodos de busca direta, derivados-livres, ou caixa-preta.

A otimização aleatório nome é atribuído ao Matyas que fez uma rápida apresentação do RO junto com a análise matemática básica. RO funciona de forma iterativa de se mudar para melhores posições na busca por espaços que são amostrados usando por exemplo, uma distribuição normal em torno da posição atual.

Algoritmo

Vamos f : ℝ n  → ℝ ser a função de fitness ou custo que deve ser minimizado. Vamos x  ∈ ℝ n designar uma posição ou solução candidato na busca por espaço. O algoritmo básico RO pode ser descrito como:

  • Inicializar x com uma posição aleatória na busca por espaço.
  • Até que um critério de terminação for atendida (por exemplo, número de iterações executadas, ou adequação adequada atingido), repita o seguinte:
    • A experiência de uma nova posição y por adição de um normalmente distribuído vector aleatório para a posição actual X
    • Se ( f ( y ) <  f ( x )), em seguida mover-se para a nova posição, definindo x  =  y
  • Agora x ocupa o cargo mais encontrados.

Este algoritmo corresponde a um (1 + 1) estratégia de evolução com a etapa de tamanho constante.

Convergência e variantes

Matyas mostrou a forma básica de RO converge para o óptimo de uma simples função unimodal usando uma prova de limite que mostra convergência para o óptimo é determinado para ocorrer se um número potencialmente infinito de iterações são realizadas. No entanto, esta prova não é útil na prática, porque um número finito de iterações só pode ser executado. Na verdade, um limite à prova de tais teórica também irá mostrar que a amostragem puramente aleatório da pesquisa do espaço, inevitavelmente, deu uma amostra arbitrariamente perto do ideal.

Análises matemáticos também são conduzidas por Baba e Solis e molha para estabelecer que a convergência para uma região em torno do óptimo é inevitável sob algumas condições suaves para RO variantes utilizando outras distribuições de probabilidade para a amostragem. Uma estimativa do número de iterações necessárias para aproximar o óptimo é derivado por Dorea. Estas análises são criticados por meio de experimentos empíricos por Sarma que usaram as variantes otimizador de Baba e Dorea em dois problemas do mundo real, mostrando o melhor de ser abordado de forma muito lenta e, além disso, que os métodos eram, na verdade incapaz de localizar uma solução de aptidão adequada, a menos o processo foi iniciado suficientemente próximo do ideal para começar.

Veja também

  • Busca aleatória é uma família estreitamente relacionado de métodos de otimização que amostra de um hiperesfera em vez de uma distribuição normal.
  • Luus-Jaakola é um método de optimização intimamente relacionados usando uma distribuição uniforme na sua amostragem e uma fórmula simples para diminuir exponencialmente o intervalo de amostragem.
  • Pesquisa padrão toma medidas ao longo dos eixos da pesquisa do espaço, utilizando exponencialmente decrescentes tamanhos de passo.
  • otimização estocástica

Referências