Otimização baseada em simulação - Simulation-based optimization

A otimização baseada em simulação (também conhecida como otimização de simulação simplesmente ) integra técnicas de otimização em modelagem e análise de simulação . Devido à complexidade da simulação, a função objetivo pode se tornar difícil e cara de avaliar. Normalmente, o modelo de simulação subjacente é estocástico, de modo que a função objetivo deve ser estimada usando técnicas de estimativa estatística (chamadas de análise de saída na metodologia de simulação).

Uma vez que um sistema é modelado matematicamente, simulações baseadas em computador fornecem informações sobre seu comportamento. Métodos de simulação paramétrica podem ser usados ​​para melhorar o desempenho de um sistema. Neste método, a entrada de cada variável é variada com outros parâmetros permanecendo constantes e o efeito no objetivo do projeto é observado. Este é um método demorado e melhora parcialmente o desempenho. Para obter a solução ótima com computação e tempo mínimo, o problema é resolvido iterativamente onde a cada iteração a solução se aproxima da solução ótima. Tais métodos são conhecidos como 'otimização numérica' ou 'otimização baseada em simulação'.

No experimento de simulação, o objetivo é avaliar o efeito de diferentes valores de variáveis ​​de entrada em um sistema. No entanto, às vezes o interesse é encontrar o valor ideal para variáveis ​​de entrada em termos dos resultados do sistema. Uma maneira poderia ser executar experimentos de simulação para todas as variáveis ​​de entrada possíveis. No entanto, essa abordagem nem sempre é prática devido a várias situações possíveis e apenas torna intratável a execução de experimentos para cada cenário. Por exemplo, pode haver muitos valores possíveis para variáveis ​​de entrada, ou o modelo de simulação pode ser muito complicado e caro para rodar para valores de variáveis ​​de entrada abaixo do ideal. Nestes casos, o objetivo é encontrar os valores ideais para as variáveis ​​de entrada, em vez de tentar todos os valores possíveis. Este processo é denominado otimização de simulação.

Métodos específicos de otimização baseados em simulação podem ser escolhidos de acordo com a Figura 1 com base nos tipos de variáveis ​​de decisão.

Fig.1 Classificação de otimização baseada em simulação de acordo com tipos de variáveis

A otimização existe em dois ramos principais da pesquisa operacional:

Paramétrica de otimização (estática) - O objetivo é encontrar os valores dos parâmetros, que são “estáticos” para todos os estados, com o objetivo de maximizar ou minimizar uma função. Nesse caso, pode-se usar a programação matemática , como a programação linear . Nesse cenário, a simulação auxilia quando os parâmetros contêm ruído ou a avaliação do problema demandaria tempo excessivo do computador, devido à sua complexidade.

Controle de otimização (dinâmico) - amplamente utilizado em ciência da computação e engenharia elétrica . O controle ideal é por estado e os resultados mudam em cada um deles. Pode-se usar programação matemática, bem como programação dinâmica. Nesse cenário, a simulação pode gerar amostras aleatórias e resolver problemas complexos e de grande escala.

Métodos de otimização baseados em simulação

Algumas abordagens importantes na otimização de simulação são discutidas abaixo.

Métodos estatísticos de classificação e seleção (R ​​/ S)

Os métodos de classificação e seleção são projetados para problemas onde as alternativas são fixas e conhecidas, e a simulação é usada para estimar o desempenho do sistema. Na configuração de otimização de simulação, os métodos aplicáveis ​​incluem abordagens de zona de indiferença, alocação de orçamento de computação ideal e algoritmos de gradiente de conhecimento.

Metodologia de superfície de resposta (RSM)

Na metodologia de superfície de resposta , o objetivo é encontrar a relação entre as variáveis ​​de entrada e as variáveis ​​de resposta. O processo começa tentando ajustar um modelo de regressão linear. Se o valor P acabar sendo baixo, então uma regressão polinomial de grau mais alto, que geralmente é quadrática, será implementada. O processo de encontrar uma boa relação entre as variáveis ​​de entrada e resposta será feito para cada teste de simulação. Na otimização de simulação, o método de superfície de resposta pode ser usado para encontrar as melhores variáveis ​​de entrada que produzem os resultados desejados em termos de variáveis ​​de resposta.

Métodos heurísticos

Os métodos heurísticos alteram a precisão pela velocidade. Seu objetivo é encontrar uma boa solução mais rápido do que os métodos tradicionais, quando são muito lentos ou falham na resolução do problema. Normalmente, eles encontram o ótimo local em vez do valor ótimo; entretanto, os valores são considerados próximos o suficiente da solução final. Exemplos desses tipos de métodos incluem pesquisa tabu e algoritmos genéticos .

Os metamodelos permitem que os pesquisadores obtenham saídas de modelo aproximadas confiáveis ​​sem executar simulações de computador caras e demoradas. Portanto, o processo de otimização do modelo pode levar menos tempo e custo de computação.

Aproximação estocástica

A aproximação estocástica é usada quando a função não pode ser calculada diretamente, apenas estimada por meio de observações ruidosas. Nesses cenários, este método (ou família de métodos) procura os extremos dessas funções. A função objetivo seria:

${\ displaystyle {\ underset {{\ text {x}} \ in \ theta} {\ min}} f {\ bigl (} {\ text {x}} {\ bigr)} = {\ underset {{\ text {x}} \ in \ theta} {\ min}} \ mathrm {E} [F {\ bigl (} {\ text {x, y}})]}$

${\ displaystyle y}$ é uma variável aleatória que representa o ruído.

${\ displaystyle x}$ é o parâmetro que minimiza . ${\ displaystyle f {\ bigl (} {\ text {x}} {\ bigr)}}$

${\ displaystyle \ theta}$ é o domínio do parâmetro . ${\ displaystyle x}$

Métodos de otimização livres de derivados

A otimização livre de derivados é um assunto de otimização matemática. Este método é aplicado a um determinado problema de otimização quando seus derivados não estão disponíveis ou não são confiáveis. Os métodos livres de derivados estabelecem um modelo com base em valores de função de amostra ou desenham diretamente um conjunto de valores de função de amostra sem explorar um modelo detalhado. Como não precisa de derivativos, não pode ser comparado a métodos baseados em derivativos.

Para problemas de otimização irrestrita, tem o formato:

${\ displaystyle {\ underset {{\ text {x}} \ in \ mathbb {R} ^ {n}} {\ min}} f {\ bigl (} {\ text {x}} {\ bigr)}}$

As limitações da otimização livre de derivados:

1. Alguns métodos não podem lidar com problemas de otimização com mais do que algumas variáveis; os resultados geralmente não são tão precisos. No entanto, existem vários casos práticos em que os métodos livres de derivadas têm sido bem-sucedidos em problemas de otimização de simulação não triviais que incluem aleatoriedade manifestando-se como "ruído" na função objetivo. Veja, por exemplo, o seguinte.

2. Quando confrontado com a minimização de funções não convexas, ele mostrará sua limitação.

3. Os métodos de otimização sem derivativos são relativamente simples e fáceis, mas, como a maioria dos métodos de otimização, alguns cuidados são necessários na implementação prática (por exemplo, na escolha dos parâmetros do algoritmo).

Programação dinâmica e programação neuro-dinâmica

Programaçao dinamica

A programação dinâmica lida com situações em que as decisões são tomadas em etapas. A chave para esse tipo de problema é compensar os custos presentes e futuros.

Um modelo básico dinâmico possui dois recursos:

1) Possui um sistema dinâmico de tempo discreto.

2) A função de custo é aditiva ao longo do tempo.

Para recursos discretos, a programação dinâmica tem a forma:

${\ displaystyle x_ {k + 1} = f_ {k} (x_ {k}, u_ {k}, w_ {k}), k = 0,1, ..., N-1}$

${\ displaystyle k}$ representa o índice de tempo discreto.

${\ displaystyle x_ {k}}$ é o estado do tempo k, ele contém as informações anteriores e as prepara para uma otimização futura.

${\ displaystyle u_ {k}}$ é a variável de controle.

${\ displaystyle w_ {k}}$ é o parâmetro aleatório.

Para a função de custo, tem o formato:

${\ displaystyle g_ {N} (X_ {N}) + \ sum _ {k = 0} ^ {N-1} g_ {k} (x_ {k}, u_ {k}, W_ {k})}$

${\ displaystyle g_ {N} (X_ {N})}$ é o custo no final do processo.

Como o custo não pode ser otimizado de forma significativa, pode ser usado o valor esperado:

${\ displaystyle E \ {g_ {N} (X_ {N}) + \ sum _ {k = 0} ^ {N-1} g_ {k} (x_ {k}, u_ {k}, W_ {k} ) \}}$

Programação neuro-dinâmica

A programação neuro-dinâmica é igual à programação dinâmica, exceto que a primeira tem o conceito de arquiteturas de aproximação. Ele combina inteligência artificial , algoritmos baseados em simulação e técnicas de abordagem funcional. “Neuro” neste termo origina-se da comunidade de inteligência artificial. Significa aprender como tomar decisões melhores para o futuro por meio de um mecanismo integrado com base no comportamento atual. A parte mais importante da programação neuro-dinâmica é construir uma rede neuro treinada para o problema ideal.

Limitações

A otimização baseada em simulação possui algumas limitações, como a dificuldade de criar um modelo que imite o comportamento dinâmico de um sistema de uma forma considerada boa o suficiente para sua representação. Outro problema é a complexidade na determinação de parâmetros incontroláveis ​​do sistema do mundo real e da simulação. Além disso, apenas uma estimativa estatística de valores reais pode ser obtida. Determinar a função objetivo não é fácil, pois é o resultado de medições, o que pode ser prejudicial às soluções.

Referências