A review of surrogate-assisted evolutionary algorithms for expensive optimization problems

# Surrogateのreview論文
Surrogate のレビュー論文についていろいろなsurrogateを紹介していければと思います。

https://www.sciencedirect.com/science/article/pii/S0957417422025143#:~:text=Surrogate-assisted%20evolutionary%20algorithms%20(SAEAs)%20has%20become

surrogate modelがそもそも何？という方は以下の記事がとても分かりやすいと思います。surrogate→代理　model→モデルなので代理のモデルを作成しようというような分野です。

https://qiita.com/shinjikato/items/cb65994a00b2330fa65f#:~:text=%E3%81%97%E3%81%8B%E3%81%97%EF%BC%8C%E6%9C%AC%E8%A8%98

# この論文で何を話しているの？
Expensive Optimization Problems (EOPs)を最適化するためにSurrogate modelの技術分野がありそれに対するreview論文なのでいろいろな手法がたくさん列挙されます。そして詳しくは論文を見てねという形です。

大まかにまとめると
- 今までの古来の手法
- single-objectiveなsurrrogate
- multi-objectiveなsurrogate
- future works


## Introduction 

Introduction
　EOPs問題は伝統的なアルゴリズムだと19次元の変数でも一分以上計算にあかかってしまい、33次元だたお18分間もかかってくる。変数の次元数が多くなるにつれこの時間は多くなっていく。
　多くの候補解から探索しなれければならないために、EOPsはとても計算コストが高いことが問題となっている。これを解決するために、surrogate modelが２０世紀の終わりから研究が始まった。Jin,et 2000.
 目的はhistorical なデータから値を予測するようなｋとおをします。候補解から予測します。実際のデータから取る代わりに。。そしてEAの計算コスト削減に挑みます。
　図１はsurrogate の基本的なフローチャートです。始めに、initial sampleからデータを生成します。そして、実際の値から本当の適応度を計算します。Latin hypercube samplingというものが多くの場合使われます。その後初期のsurrogate modelをデータから構築します。結果的にアルゴリズムのサイクルを通して、それぞれの個体での評価を行うことと、進化あるごりz無は。そしてサンプルした値の評価が確からしければ、surrogate modelを更新します。

いろいろなsurrogatemodelがありますが、low costで試そうとしているものが、 ((Guo et al., 2019; Li, Gao, Garg, Shen, & Huang, 2021; Tian
et al., 2019)

(1)高次元で組み合わせ最適化・問題はEMMOPsと呼ばれています。SAEAｓはEMMOPsに用いられる際は、私たちは代理モデルのサイズなどをや評価コストを互いに評価します。
(2)高次元で項かな最適化問題は一般にエンジニアで実践されています。変数の次元が多くなあああるにつれ、surrogate modelのaccuracyは下がっていきます。（(Cai et al., 2020; Li, Cai, Gao, & Shen,
2021).）次元削減は効率的な方法です。コストと正解の両方にとって効率的。
(3)組み合わせの問題はMOPsと呼ばれ、１つの最適化な値を求めるのに比べてとても難しくなる。

これらの研究を通して急速に近年SAEAsは注目を集めたが、review論文は少ししかない。
1.singe の最適化　Haftka et al. (2016)
2.組み合わせ　　　Díaz-Manríquez et al. (2016)
3.

section2 有名なsurrogate model
section3 それぞれの問題に関してclassifiesと表現
section4 実践的なSAEAsの使い方
section5 SAEAsの未来の研究や今後の挑戦について


# section2 

## 2.1 Polynomial response surface 
low dimensional で非線形問題のときに有用なアルゴリズム。しかし高次元で難しい問題に扱う時は精度が低い

Gemini
例えば、ある製品の品質が、製造時の温度と湿度という2つの要因によってどのように変化するかを考えます。このとき、品質をZ、温度をX、湿度をYとすると、Z = a + bX + cY + dX^2 + eY^2 + fXYのような式で近似的に表すことができます。この式で表される3次元空間上の曲面が、多項式応答曲面となります。
## 2.2Krigin
Kriging Modelの基礎知識
Kriging Modelの概要
提案者: Krige (1951)
応用: コンピュータシミュレーション実験 (Sacks et al., 1989)
特徴: 不偏推定、応答値と不確実性の予測、サロゲートモデル最適化や工学最適化への応用
数学的表現:
予測値: ŷ(x) = β + Z(x)
共分散: COV[Z(xi), Z(xj)] = σ²R(θ, xi, xj)
重要な概念の説明
ŷ(x): 未知サンプルの予測値
β: 既知のグローバル近似関数
Z(x): 平均0、分散σ²のランダムプロセス
σ²: 誤差分散
R(θ, xi, xj): サンプル点xiとxj間の相関係数
θ: 相関係数のパラメータ
xi, xj: サンプル点
Kriging Modelの仕組み
データ収集: 既知の入力値とそれに対応する出力値のペアを収集します。
半変動関数: 空間的な相関をモデル化するために、半変動関数R(θ, xi, xj)を定義します。
パラメータ推定: データに基づいて、半変動関数のパラメータθを推定します。
予測: 未知の入力値に対して、クリギングモデルを用いて予測値を計算します。
不確実性評価: 予測値の信頼区間を計算し、予測の不確実性を評価します。
Kriging Modelの応用
サロゲートモデル最適化: 複雑なシミュレーションモデルを近似し、最適化問題を効率的に解く。
工学最適化: 製品設計やプロセス最適化において、最適なパラメータを探索する。
Kriging Modelの利点

柔軟性: 様々な半変動関数を用いることで、異なる空間的な相関パターンをモデル化できる。
予測精度: 空間的な相関を考慮することで、高精度の予測が可能。
不確実性評価: 予測の信頼性を評価できる。
Kriging Modelの課題

計算コスト: データ量が増えると計算時間が長くなる。
パラメータチューニング: 半変動関数のパラメータを適切に選択することが重要。
Kriging Modelの今後の発展

深層学習との融合: 深層学習とクリギングモデルを組み合わせることで、より複雑な問題に対応。
多目的最適化: 多目的最適化問題への応用。
もし、特定の分野や応用例について詳しく知りたい場合は、お気軽にご質問ください。
## 2.3radial basis function
RBF Networkの概要
提案者: Hardy
特徴: 単一ユニットのニューラルネットワークモデル、非線形問題への適応性、線形問題での補正が必要
数学的表現: ŷ(x) = Σ(wi * φ(||x - xi||))
基底関数: 線形、立方、薄板スプラインなど
重要な概念の説明
ŷ(x): 未知サンプルの予測値
wi: ｉ番目の基底関数の係数
φ(||x - xi||): 基底関数、サンプル間のユークリッド距離を関数として受け取る
n: サンプル数
xi: 既知のサンプル点
RBF Networkの仕組み
データ収集: 既知の入力値とそれに対応する出力値のペアを収集します。
基底関数選択: 適切な基底関数を選択します。
パラメータ推定: データに基づいて、基底関数の係数wiを推定します。
予測: 未知の入力値に対して、RBFネットワークを用いて予測値を計算します。
RBF Networkの応用
関数近似: 複雑な関数を近似する。
パターン認識: 画像認識、音声認識などのパターン認識タスク。
制御: ロボット制御やプロセス制御。
RBF Networkの利点
非線形問題への適応性: 非線形な関係をモデル化できる。
柔軟性: 様々な基底関数を用いることができる。
高速な学習: 一般的に、学習速度が速い。
## RBF Networkの課題
基底関数選択: 適切な基底関数の選択が重要。
パラメータチューニング: 基底関数の係数を適切に調整する必要がある。
サンプル密度: サンプルが密集している場合、行列が病的条件になる可能性がある。
RBF Networkと他のモデルとの比較
PRS (Polynomial Response Surface): PRSは多項式を用いて近似する。RBFはより柔軟な基底関数を使用できる。
Kriging: Krigingは空間的な相関を考慮する。RBFはより一般的な関数近似に適している。
RBF Networkの今後の発展

深層RBFネットワーク: 深層学習の概念をRBFネットワークに適用する。
ハイブリッドモデル: RBFネットワークと他のモデルを組み合わせる。
## 2.4support vector machine
SVMの概要
提案者: Boser et al. (1992)
特徴: 非線形回帰問題を線形回帰問題に変換、凸最適化問題として定式化
数学的表現: ŷ(x) = w^T x + b
重要な概念の説明
ŷ(x): 未知サンプルの予測値
w, b: 推定すべきパラメータ
ε: 許容誤差
ξi, ξ*i: 緩和因子
SVMの仕組み
データ収集: 既知の入力値とそれに対応する出力値のペアを収集します。
カーネル関数: 非線形変換を行うためのカーネル関数を選択します。
最適化: 凸最適化問題を解いて、パラメータwとbを推定します。
予測: 未知の入力値に対して、SVMモデルを用いて予測値を計算します。
SVMの応用
パターン認識: 画像認識、音声認識、テキスト分類など。
異常検知: データ異常を検出する。
回帰分析: 非線形回帰問題を解決する。
SVMの利点
非線形問題への適応性: カーネル関数を使用することで、非線形な関係をモデル化できる。
汎化性能: 過学習を抑制し、未知のデータに対する予測精度が高い。
凸最適化: 効率的な最適化アルゴリズムが利用できる。
SVMの課題
カーネル関数選択: 適切なカーネル関数の選択が重要。
計算コスト: データ量が増えると計算時間が長くなる。
ハイパーパラメータチューニング: カーネル関数のパラメータや緩和因子を適切に調整する必要がある。
SVMの今後の発展
深層SVM: 深層学習の概念をSVMに適用する。
多目的SVM: 多目的最適化問題への応用。
オンラインSVM: ストリームデータに対する学習。


# section3 それぞれの問題に関してclassifiesと表現

## 3.1 Single-objective のSAEAs使わないバージョン
・3層のRBFを使った。(Li, 2022)
・Zhou (2022)は近傍の回帰を行った。
・近傍の構成を予測するために回帰を組み込む
・CaiはPSOを用いたSurrogate を行った。これは局所領域で得られた逐次解近似最適解によって得られた粒子の更新をガイドとすることでアルゴリズムの精度向上をはあkる。
・EUSPのハイブリッド型のアルゴリズムでEAとPSOの組み合わせによって提案されたもの。
・Li(2020)は良いサンプルを算出するために、正確な評価値を選ぶことで２つの基準を設けた（１つ目の基準はperformance-basedとuncertainity-based)の２つだ。
　　　１．今のglobal bestと収束率を加速されることでおこなう。
　　　２．explorationを高める。
EUSPのハイブリッドなアルゴリズムを紹介するにあたり、Aydilekはfireflyの最適化とPSOの合わせたEAを提案しました。
・Li(2021)は一番良い個体を既存のサンプルから選び、補完することを提案しました。
・Liu(2021)は不確かな基準をとります。そしえ不確かなグループ別に補完を行っていきます。
・Liu(2021)はRBFとLSBTを用いてsurrogateモデルを構築し、RBFベースと、LSBTベースは３つのソリューションからランダムなものを更新します。

・より一般的なsurrogatemodelの生成のために、アンサンブルあるいはハイブリッド型のsurrogate modelを提案します。異なるsurrogate modelを組み合わせることによって。He 2020,Yi 2019)
・アンサンブルあるいはハイブリッドのsurrogate model
・prediction modeによって１つのsurrogate modelの平均の重さあるいは、一番よいものを使います。
・Ye（2020)はsurrogate model決定された２つのsurrogate modelのアンサンブルを用います。gloalなlocalエラーを最小するようなことを行います。
・Li(2021)では混乱ベースでのアンサンブルのフレームワークを提供します。
・フレームワークは２つのメカニズムからなっており、１つ目は異なる世代のメカニズムでなっており、利用可能なデータからの。２つ目は整数ていなメカニズムです。アンサンブルのモデルを
これらはマルチsurrogate の結果を改善することができる。

## 3.2singe-objectiveでSAEAsを使うバージョン
RBFはWu et al. (2018)
Kring. Li et al. (2019)
Liu, Wan, Liu, Li, and Liu (2021)　adaptive surrogate model
## 3.3多目的最適化のSAEAs使わない
## 3.4多目的最適化のSAEAsを使うバージョン
## 3.5いろいろな問題でSAEAsを使う。
small sample のdata-drivenからのデータセットで近似しようという考え方。

## さいごに
まだまだ途中で編集中です。後日公開していきます。