# 田邊研究室でのROUTEテーマ候補
[toc]

## TSPに対するアリコロニー最適化のソフトウェアの実装

[模擬講義動画](https://www.youtube.com/watch?v=CWLc14GOPpg)にて, アリコロニー最適化の解説をしました. その説明資料を作る際に, ざっとPythonでアルゴリズムを実装してみました. が, 結局未完成のままでした.　その未完成のPythonコードは[こちら](https://drive.google.com/file/d/1h3XMzS_JM5p4qE3QBSJbvEBWIddcOZcq/view?usp=sharing)からダウンロードできます.

このテーマの目標は, 上記の未完成のPythonコードを完成させることです. イメージ的に, [伊庭先生の研究室で提供されているJavaソフトウェア](http://www.iba.t.u-tokyo.ac.jp/software.html)のように, 探索過程が可視化できればいいなと思っています.　アルゴリズムの実装は既にできていますので, 後はGUIが実装できればいいなと思います.

本テーマは研究要素はないです. プログラミングの勉強がてらに, 何でもいいからとりあえず作ってみたいという方にお勧めです.

## 水のフレーバーの対話型進化計算による最適化

**背景** 水や炭酸水に加えるフレーバーがいくつか販売されています. 簡単に自宅でオリジナルフレーバードリンクを楽しめます. メーカーからは推奨されていないと思いますが, いくつかのフレーバーをブレンドして自分だけのオリジナルのフレーバーを作ることもできます.

**問題** しかし, (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です. [「Optunaでおいしいコーヒーの淹れ方を探索する」](https://qiita.com/shu65/items/68d161b02a91396e854a)のやり方がそのまま使えるかもしれません.

## 味わいフローチャート図の対話型進化計算による最適化

[例えばこのお菓子](https://www.malebranche-shop.jp/ic/1001)の味わいフローチャート図のようなものを自動生成できたらいいなというテーマです. こうした味のことは私は全くわかりませんが, こうした図があると, そのお菓子を食べるときに楽しくなります. どんな人手ででも作れると思いますが, 進化計算で自動生成できたら便利かなと思います.

予め図形や当てはまるフレーズをそれぞれ数パターン用意しておき, 固定長の解でフローチャート図を表現します. 目的関数はその解 (フローチャート図) が実際の味わいの変化をどのくらい表していたかです. もちろん「味わいの変化をどのくらい表していたか」は客観的に評価できませんので, 人間が主観的に評価する必要があります.

研究というよりも, アプリケーション開発の要素が強いです. 英語論文として発表するというよりも, GitHubに書いたコードをアプロードし, Qiitaに記事を書くのがとりあずの目標になりそうです.

## 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ユーザの役に立ちます.

## 選好に基づく多目的最適化へのTPBの拡張

**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)

**背景** 目的関数の計算が高価なため, 解の評価をたかだか数十回, 数百回しかできない場合が実問題ではあります. このような問題設定に対して, [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の解析をしても良さそうです.

## 代表的なベイズ最適化手法の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法の性能に関する知見の獲得を目指します.

## ハイパーパラメータチューニングにおける多様性最適化

**背景** 一般的にハイパーパラメータチューニングでは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を使うなどすれば, より良い「成功の定義」が定義できるかもしれません. このコンテクストではありませんが, 実際にこうしたアイディアを試した先行研究はあります.