owned this note
owned this note
Published
Linked with GitHub
# 田邊研究室でのROUTEテーマ候補
[toc]
## SciPyのブラックボックス最適化手法の自動アルゴリズム構成
**背景** SciPyはPythonの数値計算ライブラリです. その中でも, [SciPy optimize](https://docs.scipy.org/doc/scipy/reference/optimize.html) は様々な連続最適化手法を提供します. SciPy optimizeは簡単に利用できるため, 工学分野にて幅広く使用されています.
**問題** 一般的に, 最適化アルゴリズムの性能はハイパーパラメータの設定に強く依存します. 不適切なハイパーパラメータを使用した場合, 期待通りの結果が得られないことがあります. しかし, SciPy optimizeのいくつかのブラックボックス最適化手法 (differential_evolutionなど) のハイパーパラメータのデフォルト設定は不適切である可能性があります (https://easychair.org/publications/preprint/MtB7).
**本テーマ** SciPy optimizeのブラックボックス最適化手法を自動アルゴリズム構成することで, より良いハイパーパラメータ設定を求めてみましょう. 自動アルゴリズム構成には, 機械学習分野にて一般的な[SMAC](https://automl.github.io/SMAC3/master/) を使用します. 本テーマの実験は全てPythonで完結します. より良い設定が見つかれば, 全世界のSciPyユーザの役に立ちます.
## 選好に基づく進化型多目的最適化におけるSteady-state型集団更新モデルの解析
**Colabでのデモ**
- [EMOアルゴリズム](https://colab.research.google.com/drive/1rVQA2QCF49DXt_88hcIoZXQIv-4Q-UUe?usp=sharing)
- [PBEMOアルゴリズム](https://colab.research.google.com/drive/12fkUpw43STew1osV-WZbMf2_v49J6Fb0?usp=sharing)
**背景** 進化型多目的最適化 (evolutionary multi-objective optimization, EMO) ではパレートフロントを目的空間にて近似する非劣解集合の獲得が目標です. 獲得された非劣解集合は意思決定に使用されます. つまり, EMOアルゴリズムの最適化には意思決定者の選好情報は使用されず, 最適化後に初めて意思決定者が介入します. しかし, 例えば「値段が1234円, 性能が567馬力の解が欲しい」というような意思決定者の選好情報が**最適化の事前に**利用できる場合があります. この際, この選好情報をEMOアルゴリズムがうまく利用できれば, 意思決定者が選好する非劣解集合のみを効率的に獲得できることが期待されます.
選好に基づくEMO (preference-based EMO, PBEMO) は意思決定者の選好情報を最適化に利用するEMOです. 選好情報を表現するアプローチは数多く提案されていますが, 参照点$\mathbf{z}=(z_1, \ldots, z_m)^{\top}$に基づくアプローチはその中でも幅広く使用されています. 例えば上記の例では参照点は$\mathbf{z}=(1234, 567)^{\top}$などとなります.
**問題** ほぼ全てのEMOアルゴリズムは$(\mu+\lambda)$型です. $\mu$は集団$\mathcal{P}$のサイズ, $\lambda$は子個体集団$\mathcal{Q}$のサイズを表します. 各反復にて, 子個体集団$\mathcal{Q}$を生成し, $\mathcal{P} \cup \mathcal{Q}$の$\mu + \lambda$個の個体を何らかの方法でランク付けし, 上位$\mu$個体を次反復の$\mathcal{P}$とする集団更新モデルです. 一般的に$\lambda=\mu$です.
これに対して, $(\mu+1)$型は$\lambda=1$とした特別な型であり, steady-state型とも言います. 一般的に従来型よりもsteady-state型の方が, 優れた子個体を即座に探索に利用できるためパレートフロントへの収束速度が早いと言われています. PBEMOではパレートフロント上における多様性を考慮する必要はないため, 単純にsteady-state型の方が利点がありそうです. しかし, PBEMOにおけるsteady-state型の有用性は未検証です. $\lambda=1$とするだけで, もしかすると既存のPBEMOアルゴリズムの性能が向上できるかもしれません.
**本テーマ** 本研究では代表的なPBEMOアルゴリズム (R-NSGA-IIなど) におけるsteady-state型の有用性を解析します. プログラミングは, 既存のプログラムを少しいじって$\lambda=1$とするだけです. どちらかというと実験結果をどのように取るか, 実験結果をどのように解釈するかが重要なテーマです.
## 選好に基づく多目的最適化へのTPBの拡張
**背景** 目的関数の計算が高価なため, 解の評価をたかだか数十回, 数百回しかできない場合が実問題ではあります. このような問題設定に対して, [A two-phase framework with a Bézier simplex-based interpolation method (TPB)](https://arxiv.org/abs/2203.15292) は設計されました. TPBはその名のとおり2つの段階から成ります. 1段階目ではスカラー化関数の最適化を適当な単目的最適化手法 (論文中では[BOBYQA](https://numericalalgorithmsgroup.github.io/pybobyqa/build/html/index.html)) でします. 1段階目にて得られた最良解集合Bは, 2段階目にてベジエ単体モデルのフィッティングに使用されます. ベジエ単体モデルでBを補完するような解を生成します. 先行研究では, 2目的最適化にてTPBは良好な性能を示すことを報告しています.
**問題** TPBはパレートフロント全体を近似する非劣解集合の獲得のために設計されました. しかし, 実応用では意思決定者の選好情報が利用でき, パレートフロントの一部分のみを近似しさえすれば良い場合があります. そのような選好情報が利用できる場合においても, TPBには選好情報を扱うことができません.
**本テーマ** TPBを拡張し, 選好情報を扱えるようにします. 例えば[スカラー化関数に基づくEMOアルゴリズムに選好情報を組み込む汎用的な手法](https://arxiv.org/abs/1701.05935)を使えば, 意外と簡単にできるかもしれません. 楽観的ですが, [TPBのPythonプログラム](https://github.com/ryojitanabe/tpb)をゴリゴリ修正するということにはならないと思います.
## HMO-CMA-ESのWarm-Start PhaseのPythonでの再実装
**背景** 2目的black-box最適化のために設計された[HMO-CMA-ES](https://arxiv.org/abs/1605.02720)は, 合計4つのアルゴリズムを逐次的に実行します. この逐次実行は良いanytime性能 (いつ探索を止めても良い解が得られる) の実現を目的としています. HMO-CMA-ESは2016年に提案されましたが, 2023年現在でもstate-of-the-artな性能を示しています. 特に, 極少数の計算資源で数理的最適化手法[BOBYQA](https://numericalalgorithmsgroup.github.io/pybobyqa/build/html/index.html)を逐次実行する第1段階 (warm-Start phase) は, 多目的Bayesian optimizationやsurrogate-assisted進化型多目的最適化手法と比べても良好な性能を有します.
**問題** 2023年現在でも非常に優れた性能を有するHMO-CMA-ESですが, その後続研究はなく, アルゴリズムの性質がよくわかっておりません. 特にwarm-start phaseの性能は目を見張るものがありますが, これまで特に注目されていませんでした. HMO-CMA-ESが注目をあまり集めていない原因として, 1) アルゴリズムが複雑, 2) コードがC++とMatlabで実装されており実行しづらいという点が考えられます. もしこれらを解決できれば, 優れた最適化手法を世界中のユーザがより手軽に使用でき, かつHMO-CMA-ESの解析に有益です.
**本テーマ** 本研究ではHMO-CMA-ESのwarm-start phaseをPythonで再実装します. 論文に書かれたアルゴリズムを元に, C++とMatlabで実装されたオリジナルのコードをPythonで移植する作業がメインです. [参考になりそうなプログラム](https://github.com/ryojitanabe/tpb)を昔書いたことがありますので, 完全にフルスクラッチというわけではありません. 余裕があればwarm-start phaseの解析をしても良さそうです.
## ノイズ付き多目的最適化におけるCOMO-CMA-ESの解析
**背景** [COMO-CMA-ES](https://arxiv.org/abs/1904.08823) は2019年に提案された有用な進化型多目的最適化手法です. Uncrowded hypervolumeという新しい指標に基づき, 複数のCMA-ESを実行します. COMO-CMA-ESではnadir point (パレートフロントの最大値から成る点) をuncrowded hypervolumeの計算に使用します. COMO-CMA-ESは比較的単純なアルゴリズムながら, 代表的な進化型多目的最適化手法よりも優れた性能を有すると報告されています. ほとんどのEMOアルゴリズムがエリート選択を採用している一方, COMO-CMA-ESは非エリート選択を導入可能という, 珍しい特徴を持ちます.
**問題** 実問題では目的関数値にノイズが含まれるノイズ付き最適化が現れます. 例えば乱数を用いたシミュレーションにより解の目的関数値を計算する問題にて発生します. 一般的にノイズ付き最適化はノイズなし最適化よりも困難です. 従来のエリート型EMOアルゴリズムでは[何かしらの工夫](https://ore.exeter.ac.uk/repository/bitstream/handle/10871/17063/fieldsend_everson_RTEA_revision.pdf?sequence=1)が必要です. 一方, ノイズ付き**単目的**最適化では, 非エリートな進化アルゴリズム (CMA-ESなど) が特別な工夫をせずとも良好な性能を示しています.
**本テーマ** 非エリートなCOMO-CMA-ESをノイズ付き多目的最適化に適用し, その性能を解析します. 非エリートなCOMO-CMA-ESならば, 特別な工夫をせずともノイズ付き多目的最適化でも良好な性能を示すと期待できます. 「特別な工夫」をする従来型アプローチとは全く別のアプローチを採用することで, 新しい知見が得られることを期待しています. 著者らによって公開されている[Pythonプログラム](https://github.com/CMA-ES/pycomocma) を修正して利用することになると思います.
## 代表的なベイズ最適化手法のMixed-integer BBOB Function Setにおけるベンチマーキング
**背景** ベイズ最適化手法は目的関数の計算コストが高いブラックボックス最適化問題に対して有用です. 自動機械学習の分野では頻繁に使用されています. [optuna](https://www.preferred.jp/ja/projects/optuna/) や[SMAC](https://automl.github.io/SMAC3/master/) などの様々なPythonライブラリが開発されています.
**問題** 進化計算コミュニティでは整数混合最適化問題の研究はあまりされておりません. その中でも, 目的関数の計算コストが高く, 解の評価回数が厳しく制限される状況を想定した研究は特にされておりません. 実応用では高コストなシミュレーションにより解を評価する状況は現れうるため, 効果的な最適化手法が望まれます.
**本テーマ** optunaやSMACにて利用可能な, 汎用的なベイズ最適化手法を[mixed-integer BBOB function suite](https://github.com/numbbo/coco) でベンチマーキングします. 現在利用可能な最適化手法がどの程度の性能を有するのか明らかにすることで, 今後の後続研究にベースラインを提供します. 本テーマの実験は全てPythonで完結します.
## Solis-Wets法の高次元ブラックボックス最適化問題でのベンチマーキング
**背景** [Solis-Wets法](https://www.math.ucdavis.edu/~rjbw/mypage/Miscellaneous_files/randSearch.pdf) は1981年に提案された古典的なブラックボックス最適化手法です. 一方, [いくつかの先行研究](https://link.springer.com/article/10.1007/s00500-010-0647-2) ではSolis-Wets法は高次元 (設計変数の多い) ブラックボックス最適化問題にて有用であると報告しています.
**問題** しかし, Solis-Wets法のベンチマーキング研究は不十分で, どのような問題でうまく動作するのか, 次元数に対するスケール性などの重要な情報が不明です.
**本テーマ** Solis-Wets法を自分でフルスクラッチ実装して, 複数のテスト関数でベンチマーキングします. これにより, Solis-Wets法の性能に関する知見の獲得を目指します.
## Parameter LandscapeのExploratory Landscape Analysisによる地形解析
**背景** 例えば遺伝的アルゴリズムは集団数, 交叉率などのハイパーパラメータを有します. これらハイパーパラメータの空間をParameter landscapeといいます. Parameter landscapeを理解することは, 効率的なチューニング手法の設計に役立ちます. [先行研究](https://ada.liacs.leidenuniv.nl/papers/PusHoo18.pdf) では, 1つのパラメータのみを対象に地形解析をしています.
**問題** 各パラメータをスライスして地形解析をした場合, 1つのパラメータに対する感度しか解析できません. また, 具体的にどのような地形であるのか, それはどの程度一般的な知見なのかは不明です.
**本テーマ** Exploratory landscape analysis (ELA) を用いてparameter landscapeを解析します. チューニング対象はoff-the-shelfな適当な手法を予定しています. もし「どのチューニング問題もXXXである」のような共通事項がわかれば面白いかと思います.
## ハイパーパラメータチューニングにおける多様性最適化
**背景** 一般的にハイパーパラメータチューニングでは1つのパラメータ設定しか獲得できません.
**問題** もし同じ効用を有する複数のパラメータ設定が獲得できれば, アルゴリズムの解析に役立ちます. パラメータAが小さければパラメータBを大きくする必要がある (vice versa) などです.
**本テーマ** ハイパーパラメータチューニングにおける多様性最適化をします. 得られたパラメータ設定群がどのくらい多様なのかを計測するため, 連続値パラメータのみを扱います. とりあえず既存の多様性最適化手法を簡単なパラメータチューニング問題に適用してうまく動作するか確認します. 例えばERTが12345以下のパラメータが欲しい, などという問題設定にしても良さそうです.
## 疑似乱数生成器がHypervolume近似法の性能に与える影響の解析
**背景** 進化型多目的最適化の分野において, hypervolume (N次元空間の体積のようなもの) は非常に重要です. ほとんどの研究はhypervolumeに基づき手法の性能の良し悪しを議論しています. しかし, 目的数 (次元数) が増加すると, hypervolumeの計算コストは高くなり, 現実的な時間では計算できなくなる場合があります. この問題を解決するために, 厳密なhypervolume値の計算を諦めて, モンテカルロ法で値を近似しようというアプローチがあります. 単純に, ランダム生成した点が領域内に入った割合で体積を推定します.
**問題** コンピューターシミュレーションでは疑似乱数 (真の乱数ではない) が乱数として一般的に使用されます. 疑似乱数を生成するために, 線形合同法やメルセンヌツイスタなど, これまでに様々な生成器が提案されています. 一方, 疑似乱数生成器がモンテカルロ法に基づくhypervolumeの近似法に与える影響はよくわかっておりません. もし特定の疑似乱数生成器を使用することによって近似値が悪化するようですと, 大きな問題になります.
**本テーマ** 疑似乱数生成器がモンテカルロ法に基づくhypervolume近似法に与える影響を明らかにします. アルゴリズムは同じでも, プログラムにおいてどの疑似乱数生成器を使うかで性能が (恐らく) 変化する, というアルゴリズムを実装する上での落とし穴を体験してもらうという目的もあります. ソボル列などの超一様分布列, ラテン超方格サンプリングなどを疑似乱数生成器として使用してみても面白いかもしれません.
## 制約付きブラックボックス最適化における適応Differential Evolutionの振る舞いの解析
**背景** 適応Differential Evolution (DE) は無制約単目的ブラックボックス最適化にて良好な性能を有することが報告されています. 適応DEでは自身の制御パラメータを適応的に自動で調整します.
**問題** 無制約単目的ブラックボックス最適化におけるパラメータ適応メカニズムはある程度解析されています. しかし, 制約付きブラックボックス最適化における解析はほとんどされていません. 制約の有無でどのようにパラメータ適応が変化するのかがわかれば, 新しいより効率的な適応DEの設計が期待できます.
**本テーマ** 制約付きブラックボックス最適化における適応DEの振る舞いを解析します. 直感的に, 制約違反空間と目的空間の性質は異なりますので, 実行不可能領域と実行可能領域を探索する際のパラメータ適応はそれぞれ異なるはずです.
## 適応Differential Evolutionにおける成功の定義の再考
**背景** 適応DEでは個体ごとに制御パラメータを生成し, 目的関数値f(x)が改善できれば成功, できなければ失敗とラベル付けします. そして, 成功と判定されたパラメータ群を用いて, 次世代のパラメータ生成分布を更新します. 田邊の先行研究にて, 適応型DEは目的関数値f(x)が悪い個体はどのようなパラメータでもf(x)を改善できる可能性が高いことを明らかにしました.
**問題** つまり, f(x)が悪い個体ではほぼランダムにパラメータを生成しても成功と判定されることが多いということです. 対象問題に適していない, 適当なパラメータも成功と判定されてしまうと, パラメータ生成分布の更新に余計なノイズが入ってしまいます.
**本テーマ** 成功の定義を再考します. 例えば, 親個体を基準にせずに, 集団中の個体の目的関数値の中央値を基準にする, noveltyを使うなどすれば, より良い「成功の定義」が定義できるかもしれません. このコンテクストではありませんが, 実際にこうしたアイディアを試した先行研究はあります.
## 水のフレーバーの対話型進化計算による最適化
**背景** 水や炭酸水に加えるフレーバーがいくつか販売されています. 簡単に自宅でオリジナルフレーバードリンクを楽しめます. メーカーからは推奨されていないと思いますが, いくつかのフレーバーをブレンドして自分だけのオリジナルのフレーバーを作ることもできます.
**問題** しかし, (1) どのフレーバーを, (2) どの割合でブレンドすればいいのかは不明です. また, 嗜好は個人に依存するため, 万人に対して最適な(1)と(2)は存在しません. また, ブレンドフレーバーの良し悪しを評価するためには実際に自分で試飲する必要がありますが, 胃の容量は有限であることから試飲可能な回数は限られています.
**本テーマ** Human-in-the-loopな[対話型進化計算](https://www.jstage.jst.go.jp/article/jjsai/13/5/13_692/_article/-char/ja/) で(1)と(2)を最適化を試みます. ユーザが主観的に解の良し悪しを評価する (今回の場合は試飲) 対話型進化計算ならば, 適当にブレンドするよりも良いフレーバーを求めることが期待されます. 本テーマは学術研究というよりも, アプリ開発です. 使用プログラミング言語は何でもOKです.