シミュレーションベースの最適化

シミュレーションベース最適化（単にシミュレーション最適化とも呼ばれる）は、最適化手法をシミュレーションモデリングと解析に統合する手法です。シミュレーションの複雑さにより、目的関数の評価が困難になり、コストも高くなる場合があります。通常、基礎となるシミュレーションモデルは確率的であるため、目的関数は統計的推定手法（シミュレーション手法では出力分析と呼ばれる）を用いて推定する必要があります。

システムが数学的にモデル化されると、コンピュータベースのシミュレーションによってその動作に関する情報が得られます。パラメトリックシミュレーション手法は、システムの性能向上に使用できます。この手法では、他のパラメータを一定に保ちながら各変数の入力を変化させ、設計目標への影響を観察します。これは時間のかかる手法であり、性能向上の効果は限定的です。最小限の計算時間と時間で最適解を得るために、問題は反復的に解かれ、反復ごとに解は最適解に近づきます。このような手法は、「数値最適化」、「シミュレーションベース最適化」[ 1 ] 、または複数の目的が関係する場合に使用される 「シミュレーションベース多目的最適化」と呼ばれます。

シミュレーション実験の目的は、入力変数の異なる値がシステムに与える影響を評価することです。しかし、システムの結果の観点から、入力変数の最適な値を見つけることが重要な場合もあります。1つの方法として、考えられるすべての入力変数に対してシミュレーション実験を実行することが挙げられます。しかし、このアプローチは、さまざまな状況が発生する可能性があるため、必ずしも実用的ではなく、各シナリオで実験を実行することが困難になる場合があります。たとえば、入力変数の値が多すぎる場合や、シミュレーションモデルが複雑すぎて、多数の入力変数値に対して実行するにはコストが高すぎる場合があります。このような場合、目標は、考えられるすべての値を試すのではなく、入力変数の最適な値を反復的に見つけることです。このプロセスはシミュレーション最適化と呼ばれます。[ 2 ]

具体的なシミュレーションベースの最適化手法は、図1に示すように、決定変数の種類に応じて選択できます。[ 3 ]

図1 変数の種類によるシミュレーションベース最適化の分類

最適化はオペレーションズ・リサーチの 2 つの主要な分野に存在します。

パラメトリック最適化（静的） – 関数を最大化または最小化することを目指し、すべての状態において「静的」なパラメータの値を求めること。この場合、線形計画法などの数理計画法を用いることができる。このシナリオでは、パラメータにノイズが含まれている場合や、問題が複雑であるため評価に過度の計算時間を要する場合に、シミュレーションが役立つ。[ 4 ]

最適化制御（動的） - これは主にコンピュータサイエンスと電気工学で用いられます。最適制御は状態ごとに行われ、結果は状態ごとに変化します。数理計画法と動的計画法が利用可能です。このシナリオでは、シミュレーションによってランダムサンプルを生成し、複雑で大規模な問題を解くことができます。[ 4 ]

シミュレーションベースの最適化手法

シミュレーション最適化におけるいくつかの重要なアプローチについて以下で説明する。 [ 5 ] [ 6 ]

統計的ランキングと選択方法（R/S）

ランキングと選択の手法は、選択肢が固定かつ既知であり、シミュレーションを用いてシステム性能を推定する問題向けに設計されています。シミュレーション最適化の設定では、無差別領域アプローチ、最適な計算予算配分、知識勾配アルゴリズムなどが適用可能です。

応答曲面法（RSM）

応答曲面法では、入力変数と応答変数の関係を見つけることが目的です。このプロセスは、線形回帰モデルの当てはめを試行することから始まります。P値が低いことが判明した場合、通常は2次式である高次の多項式回帰が実施されます。入力変数と応答変数間の良好な関係を見つけるプロセスは、各シミュレーションテストごとに実行されます。シミュレーション最適化において、応答曲面法は、応答変数の観点から望ましい結果をもたらす最適な入力変数を見つけるために使用できます。[ 7 ]

ヒューリスティックな方法

ヒューリスティック法は、速度によって精度が変わります。従来の方法では解決が遅すぎたり、問題を解決できなかったりする場合に、ヒューリスティック法よりも速く良い解を見つけることが目的です。通常、最適値ではなく局所最適値を見つけますが、その値は最終解に十分近いとみなされます。この種の手法の例としては、タブー探索や遺伝的アルゴリズムなどが挙げられます。[ 4 ]

メタモデルを用いることで、研究者は高価で時間のかかるコンピュータシミュレーションを実行することなく、信頼性の高い近似モデル出力を得ることができる。そのため、モデル最適化のプロセスにかかる計算時間とコストを削減することができる。[ 8 ]

確率的近似

確率近似は、関数を直接計算できず、ノイズの多い観測値から推定するしかない場合に用いられます。このような状況では、この手法（あるいはその一群）は、これらの関数の極値を探します。目的関数は以下のようになります。[ 9 ]

分×∈θf（×）＝分×∈θE[F（x,y）]{\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}})]}
y{\displaystyle y}ノイズを表すランダム変数 です。
×{\displaystyle x}を最小化するパラメータです 。f（×）{\displaystyle f{\bigl (}{\text{x}}{\bigr )}}
θ{\displaystyle \theta} はパラメータの定義域です。×{\displaystyle x}

導関数を使わない最適化手法

導関数を用いない最適化は、数理最適化の一分野です。この手法は、導関数が利用できない、あるいは信頼できない最適化問題に適用されます。導関数を用いない手法は、サンプル関数値に基づいてモデルを構築するか、詳細なモデルを用いることなく、サンプル関数値集合を直接抽出します。導関数を必要としないため、導関数を用いる手法と比較することはできません。[ 10 ]

制約のない最適化問題の場合、形式は次のようになります。

分×∈Rnf（×）{\displaystyle {\underset {{\text{x}}\in \mathbb {R} ^{n}}{\min }}f{\bigl (}{\text{x}}{\bigr )}}

導関数を使用しない最適化の限界:

1. 一部の手法は、少数以上の変数を含む最適化問題には対応できず、結果は通常それほど正確ではありません。しかしながら、目的関数に「ノイズ」として現れるランダム性を含む、非自明なシミュレーション最適化問題において、導関数を用いない手法が成功した実例が数多くあります。例えば、以下の [ 5 ] [ 11 ]を参照してください 。

2. 非凸関数を最小化しようとすると、その限界が現れます。

3. 導関数を使用しない最適化手法は比較的単純で簡単ですが、ほとんどの最適化手法と同様に、実際の実装にはある程度の注意が必要です（たとえば、アルゴリズムパラメータの選択など）。

動的計画法とニューロダイナミック計画法

動的計画法

動的計画法は、段階的に意思決定が行われる状況を扱います。この種の問題における鍵は、現在と将来のコストのトレードオフです。[ 12 ]

1 つの動的基本モデルには、次の 2 つの機能があります。

1) 離散時間動的システムを備えています。

2) コスト関数は時間の経過とともに加算されます。

離散的な特徴の場合、動的計画法は次の形式になります。

×け+1＝fけ（×け、あなたけ、わけ）、け＝0、1、。。。、北−1{\displaystyle x_{k+1}=f_{k}(x_{k},u_{k},w_{k}),k=0,1,...,N-1}
け{\displaystyle k}離散時間のインデックスを表します。
×け{\displaystyle x_{k}}は時刻 k の状態であり、過去の情報を含んでおり、将来の最適化のために準備されます。
あなたけ{\displaystyle u_{k}}制御変数です。
わけ{\displaystyle w_{k}}ランダムパラメータです。

コスト関数は次の形式になります。

グラム北（X北）+∑け＝0北−1グラムけ（×け、あなたけ、Wけ）{\displaystyle g_{N}(X_{N})+\sum _{k=0}^{N-1}g_{k}(x_{k},u_{k},W_{k})}

グラム北（X北）{\displaystyle g_{N}(X_{N})}プロセス終了時のコストです。

コストを意味のある形で最適化することはできないため、期待値を使用できます。

E{グラム北（X北）+∑け＝0北−1グラムけ（×け、あなたけ、Wけ）}{\displaystyle E\{g_{N}(X_{N})+\sum _{k=0}^{N-1}g_{k}(x_{k},u_{k},W_{k})\}}

ニューロダイナミックプログラミング

ニューロダイナミックプログラミングは、近似アーキテクチャの概念を持つ点を除けば動的プログラミングと同じです。人工知能、シミュレーションベースのアルゴリズム、そして関数型アプローチ技術を組み合わせたものです。この用語の「ニューロ」は人工知能コミュニティに由来しています。これは、現在の行動に基づいて、組み込みメカニズムを介して将来に向けてより良い意思決定を行う方法を学習することを意味します。ニューロダイナミックプログラミングの最も重要な部分は、最適な問題のために訓練されたニューロネットワークを構築することです。[ 13 ]

制限事項

シミュレーションに基づく最適化には、システムの動的挙動を模倣し、かつその表現として十分な精度を持つモデルを作成することの難しさなど、いくつかの限界があります。また、実世界のシステムとシミュレーションの両方において、制御不能なパラメータを決定する際の複雑さも問題となります。さらに、実数値の統計的推定値しか得られません。目的関数は測定結果であるため、その決定は容易ではなく、解に悪影響を与える可能性があります。[ 14 ] [ 15 ]

参考文献

  1. ^ Nguyen, Anh-Tuan, Sigrid Reiter, Philippe Rigo. 「建物の性能解析に適用されるシミュレーションベースの最適化手法のレビュー」 Applied Energy 113 (2014): 1043–1058.
  2. ^カーソン、ヨランダ、アヌ・マリア。「シミュレーションの最適化：方法と応用」第29回冬季シミュレーション会議議事録。IEEEコンピュータ協会、1997年。
  3. ^ Jalali, Hamed, Inneke Van Nieuwenhuyse. 「在庫補充におけるシミュレーション最適化：分類」IIE Transactions 47.11 (2015): 1217-1235.
  4. ^ a b cアビジット・ゴサヴィ『シミュレーションベース最適化：パラメトリック最適化手法と強化学習』シュプリンガー、第2版（2015年）
  5. ^ a b Fu, Michael編 (2015).シミュレーション最適化ハンドブック. Springer.
  6. ^ Spall, JC (2003).確率的探索と最適化入門：推定、シミュレーション、制御. ホーボーケン: Wiley.
  7. ^ Rahimi Mazrae Shahi, M., Fallah Mehdipour, E. and Amiri, M. (2016),地下鉄列車運行スケジュールへの応用を伴うシミュレーションと応答曲面法を用いた最適化. Intl. Trans. in Op. Res., 23: 797–811. doi : 10.1111/itor.12150
  8. ^ Yousefi, Milad; Yousefi, Moslem; Ferreira, Ricardo Poley Martins; Kim, Joong Hoon; Fogliatto, Flavio S. (2018). 「救急部門における最適な資源計画のためのカオス遺伝的アルゴリズムとAdaboostアンサンブルメタモデリングアプローチ」. 『人工知能と医療』 . 84 : 23–33 . doi : 10.1016/j.artmed.2017.10.002 . PMID 29054572 . 
  9. ^ Powell, W. (2011).近似動的計画法による次元の呪いの解決（第2版、Wiley確率統計シリーズ）. ホーボーケン: Wiley.
  10. ^ Conn, AR; Scheinberg, K .; Vicente, LN (2009).導関数フリー最適化入門. MPS-SIAM最適化ブックシリーズ. フィラデルフィア: SIAM. 2014年1月18日閲覧。
  11. ^ Fu, MC, Hill, SD. 同時摂動法による離散事象システムの最適化. IIE Transactions 29, 233–243 (1997). https://doi.org/10.1023/A:1018523313043
  12. ^クーパー、レオン、クーパー、メアリー・W. 動的計画法入門. ニューヨーク：ペルガモン・プレス, 1981
  13. ^ Van Roy, ​​B., Bertsekas, D., Lee, Y., & Tsitsiklis, J. (1997).小売業者の在庫管理へのニューロダイナミックプログラミングアプローチ. IEEE Con​​ference on Decision and Control, 4 , 4052-4057.
  14. ^ Prasetio, Y. (2005).複雑確率システムのためのシミュレーションベースの最適化. ワシントン大学.
  15. ^ Deng, G., & Ferris, Michael. (2007).シミュレーションベースの最適化, ProQuest Dissertations and Theses
「 https://en.wikipedia.org/w/index.php?title=シミュレーションベースの最適化&oldid =1314447784」より取得