| テーマ概要 |
私は人工知能・計算知能の一分野である進化計算の基礎研究に興味があります. 今期のROUTEでは, 私は次の9つのテーマを提案します. もちろん, 学生からの独自テーマの希望を歓迎します. ただし, 今学期のみで達成可能なテーマに限定します. お気軽にご相談ください.
1. 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法の性能に関する知見の獲得を目指します.
2. 遺伝的プログラミングにおける集団更新モデルの再考
背景: 遺伝的プログラミングは様々な機械学習タスクに応用されています. 一般的に, (mu, lambda)型, mu+lambda型, またはそれに準ずる集団更新モデルが遺伝的プログラミングでは採用されています.
問題: 例えば遺伝的アルゴリズムや差分進化 (https://easychair.org/publications/preprint/MtB7) といった他の進化アルゴリズムでは, 集団更新モデルがその性能に与える影響はよく調査されています. 一方, 遺伝的プログラミングの性能に与える影響はよくわかっておりません. もしかすると, 集団更新モデルを変えるだけで遺伝的プログラミングの性能が簡単に改善できる可能性があります.
本テーマ: 遺伝的プログラミングにおける様々な集団更新モデルの有用性を調査します. どの集団更新モデルが最も遺伝的プログラミングに適しているかを明らかにすることが目的です. Pythonの進化計算ライブラリであるDEAP (https://deap.readthedocs.io/en/master/index.html) を使う予定です. もちろん, 既存の集団更新モデルが最も良かったという可能性もあります.
3. 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ユーザの役に立ちます.
4. 代表的なベイズ最適化手法の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 functions (https://github.com/numbbo/coco) でベンチマーキングします. 現在利用可能な最適化手法がどの程度の性能を有するのか明らかにすることで, 今後の後続研究にベースラインを提供します. 本テーマの実験は全てPythonで完結します.
5. Noveltyに基づく適応度関数によるPlateauを有する連続最適化における進化アルゴリズムの改良
背景: 変数が連続値をとるブラックボックス連続最適化にて, plateau (平坦な地形) は現れうる性質です. 例えば, 工業製品設計最適化にてネジなどの部品の大きさが0.009, 0.0095, 0.0104, 0.0118, ...などの特定の値しか取れない場合は変数値を丸め込む必要があります. この際, 異なる解xと解yでも同じ目的関数値f(x)=f(y)となりえるため, plateauが発生します.
問題: Plateauを有する最適化問題は, 探索方向が消失し探索が停滞するため, 進化アルゴリズムにとって困難です. 特に高次元な問題 (変数が多い問題) ではその傾向が顕著になります. Plateauは実問題にて現れうる性質のため, 有効な対処方法が求められています.
本テーマ: Noveltyに基づく適応度関数Fを使用することで, plateauを有する連続最適化における進化アルゴリズムの性能改良を目指します. Novelty (好奇心) とは, 現在の探索地点からの距離指標dを適度に最大化することで, 新しい探索領域を探そうという一般的な戦略の概念です. 通常は適応度関数F(x) = 目的関数f(x)です. 本テーマでは, もしplateauにトラップされたら (集団の全ての個体の目的関数値が等しくなったら), 適応度関数F(x) = -距離指標d(x)と切り替えることでplateauからの脱出を狙います. dをどのように設計すれば期待通りの振る舞いになるか工夫することに, 本テーマの面白さがあります.
関連文献:
https://www.ini.rub.de/upload/file/1511450809_aa0c37cfca112b564f00/cuccu2011.pdf
https://doi.org/10.1145/3321707.3321805
https://arxiv.org/abs/2009.12867
6. 疑似乱数生成器がHypervolume近似法の性能に与える影響の解析
背景: 進化型多目的最適化の分野において, hypervolume (N次元空間の体積のようなもの) は非常に重要です. ほとんどの研究はhypervolumeに基づき手法の性能の良し悪しを議論しています. しかし, 目的数 (次元数) が増加すると, hypervolumeの計算コストは高くなり, 現実的な時間では計算できなくなる場合があります. この問題を解決するために, 厳密なhypervolume値の計算を諦めて, モンテカルロ法で値を近似しようというアプローチがあります. 単純に, ランダム生成した点が領域内に入った割合で体積を推定します.
問題: コンピューターシミュレーションでは疑似乱数 (真の乱数ではない) が乱数として一般的に使用されます. 疑似乱数を生成するために, 線形合同法やメルセンヌツイスタなど, これまでに様々な生成器が提案されています. 一方, 疑似乱数生成器がモンテカルロ法に基づくhypervolumeの近似法に与える影響はよくわかっておりません. もし特定の疑似乱数生成器を使用することによって近似値が悪化するようですと, 大きな問題になります.
本テーマ: 疑似乱数生成器がモンテカルロ法に基づくhypervolume近似法に与える影響を明らかにします. アルゴリズムは同じでも, プログラムにおいてどの疑似乱数生成器を使うかで性能が (恐らく) 変化する, というアルゴリズムを実装する上での落とし穴を体験してもらうという目的もあります. ソボル列などの超一様分布列, ラテン超方格サンプリングなどを疑似乱数生成器として使用してみても面白いかもしれません.
7. Nadir pointが不明な多目的最適化問題への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は比較的単純なアルゴリズムながら, 代表的な進化型多目的最適化手法よりも優れた性能を有すると報告されています.
問題: COMO-CMA-ESの問題点は, nadir pointが不明な多目的最適化問題に適用 (ほぼ) 不可能であり, そうした問題が実応用では頻出することです. 一般的に, 実問題では事前にパレートフロントの形状を知ることはできません.
本テーマ: Nadir pointが不明な多目的最適化問題へのCOMO-CMA-ESの拡張を試みます. 探索中に真のnadir pointを得ることは困難ですが, nadir pointを近似することは可能です. 近似したnadir pointを使用したCOMO-CMA-ESの性能調査から, 本テーマは始めることになります. 著者らによって公開されているPythonプログラム (https://github.com/CMA-ES/pycomocma) を修正して利用することになると思います.
8. Multi-funnel構造を有する巡回セールスパーソン問題インスタンスの自動生成
背景: 巡回セールスパーソン問題 (TSP) は重要な組合せ最適化問題です. 厳密, 非厳密を問わずこれまでにいくつもの解法が提案されています. TSPのfunnel構造 (大域的な適応度景観) はsingle-funnel (大きな谷が1つ) であるとされています. この前提を元に, いくつかの効率的な非厳密解法が提案されています.
問題: 一方, 近年の研究ではmulti-funnel (大きな谷が複数) であるTSPインスタンスの存在が指摘されています. しかし, どのようなTSPインスタンスがsingle-funnel, またはmulti-funnel構造を有するのかは定かではありません.
本テーマ: Multi-funnel構造を有するTSPインスタンスを自動生成する仕組みを開発します. 生成されたTSPインスタンスの都市配置を解析することで, どのような場合にfunnel構造が変化するのかを明らかにします. この知見は新しい手法の開発, および手法の選定 (algorithm selection) に役立ちます. 異なる2つの手法の優劣関係がはっきりするような, TSPインスタンスを自動生成するという先行研究があります (https://github.com/jakobbossek/tspgen). 本テーマではそのような既存アプローチを修正することから取り組みます.
9. 水のフレーバーの対話型進化計算による最適化
背景: 水や炭酸水に加えるフレーバーがいくつか販売されています. 簡単に自宅でオリジナルフレーバードリンクを楽しめます. メーカーからは推奨されていないと思いますが, いくつかのフレーバーをブレンドして自分だけのオリジナルのフレーバーを作ることもできます.
問題: しかし, (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です.
|
