AI Lab Algorithmsチームの濱野です．本稿では，リスクのある解の評価を回避しながら最適化を行う手法を提案した研究について解説します．本研究成果は，進化計算分野におけるトップカンファレンスであるGECCO2024に採択されています．

Kento Uchida, Ryoki Hamano, Masahiro Nomura, Shota Saito, and Shinichi Shirakawa. CMA-ES for Safe Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’24), 2024. [arXiv]

本研究が対象とする問題

本研究では，リスクのある解の評価を回避しながら最適化を行うSafe Optimizationを扱います．例として「ある製品のパフォーマンスが最大となるような内部設計を探索する問題」を考えてみます．このとき，製品の内部設計を決定し，パフォーマンスを計測した結果が目的関数値となります．では，「内部設計によっては製品が故障してしまう可能性がある」という問題設定が追加された場合はどうなるでしょうか？

パフォーマンスの計測を重ねるごとに，より良い内部設計が発見されることが期待されますが，その過程で製品が何度も故障することがあれば大きな損失につながってしまいます．つまりこのような問題設定では，良い解を探索することに加え，リスクのある解の評価回数を抑えることが要求されます．

以下はSafe Optimizationの実例です．

問題設定の定式化

Safe Optimizationでは最小化（最大化）対象である目的関数に加えて，解にリスクがあるかどうかを判定するSafety関数を定義します．ここで，目的関数とSafety関数は解析的に与えられないブラックボックス関数であることを仮定します．ある解を評価すると目的関数とSafety関数の値を得ることができます．このとき，Safety関数の値があらかじめ設定されたしきい値を超えた場合にリスクのある解として判定されます．以下，Safety関数の値がしきい値を超えた解をUnsafeな解，そうでない解をSafeな解と呼びます．

決められた解の評価回数以内で「どれだけ目的関数を最小化するSafeな解を発見できたか」「どれだけUnsafeな解の評価回数を抑えられたか」によって最適化のクオリティが決まります．目的関数をより最小化する解を発見するために多様な解を評価しようとすると，Unsafeな解を評価する可能性が高まるため，この2つの指標は多くの場合トレードオフの関係にあると言えます．

提案手法：Safe CMA-ES

本研究では，ブラックボックス連続最適化の有力な手法であるCMA-ES [3]をSafe Optimizationに適用できるよう拡張したSafe CMA-ESを提案しました．CMA-ESは多変量ガウス分布を用いた確率的な探索手法で，分布からの解の生成，解の評価，評価情報にもとづく分布の更新を繰り返すことで探索を行います．

図1. CMA-ESのアルゴリズムの流れ．多変量ガウス分布から生成された解の候補を目的関数で評価して重みづけし，より良い解がより生成されやすくなるように分布を更新する．

CMA-ESは目的関数を最小化することだけを考えた手法であるため，Safe Optimizationにそのまま適用した場合にUnsafeな解の評価回数を抑えることができません．そこでSafe CMA-ESでは，Safeな解が得られるSafe領域を計算し，Unsafeな解をSafe領域内の解に写像するアプローチを考えます．

Safe領域の計算方法と写像方法

任意の解がSafeな解となるかどうかは，実際にSafety関数で評価を行わないと判定することができません．さらに，Safety関数はブラックボックスであるため事前にSafe領域を計算することもできません．Safe CMA-ESではまず，評価済みの解を用いてSafety関数のガウス過程回帰を行います．そして，ガウス過程回帰によるSafety関数の予測値からリプシッツ定数を推定することで，Safe領域を計算します．ガウス過程回帰に必要な評価済みの解が少ない場合の対処法や，CMA-ESのもつ多変量ガウス分布の状態を考慮したリプシッツ定数の推定など，Safe領域の計算には様々な工夫点がありますので，気になった方は論文をご参照ください．

Safe領域の計算後は，多変量ガウス分布から生成された解をSafe領域内の最近傍の解に写像する操作を行います．そうすることで，Safe CMA-ESはUnsafeな解の評価を抑制しながら，効率的な最適化を行うことが可能になります．

図2. Safe CMA-ESにおけるSafe領域の計算と，Safe領域内の最近傍の解への写像．

比較実験

実問題の最適化で重要となる性質をもつベンチマーク関数を用いた数値実験を行いました．比較手法は，最近傍の評価済みの解がSafeな解となるよう解生成を行うViolation Avoidance [4]を導入したCMA-ESと，Safe Optimizationのためのベイズ最適化にもとづく手法であるSwarm-based SafeOpt [5]とSwarm-based SafeOpt-UCB [1]です．提案手法であるSafe CMA-ESは，効率的な目的関数の最適化と，Unsafeな解の評価回数の抑制を両立できていることがわかります．

図3. 最適化中の最良評価値とUnsafeな解の評価回数の推移．どちらの指標も小さい（少ない）ほど良い．横軸は目的関数とSafety関数の評価回数．

さいごに

本研究ではSafe Optimizationに対する有力な手法としてSafe CMA-ESを提案しました．CMA-ESの強力な探索性能を活かしながら，Safe領域の計算によるアプローチでUnsafeな解の評価回数を抑えることに成功しました．Safe CMA-ESの詳細が気になった方は，論文を読んでいただければ幸いです．

参考文献

[1] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe Exploration for Optimization with Gaussian Processes. In Proceedings of the 32nd International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 37), 2015.

[2] Felix Berkenkamp, Andreas Krause, and Angela P. Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning 112, 10, 2023.

[3] Nikolaus Hansen. The CMA Evolution Strategy: A tutorial. arXiv preprint arXiv:1604.00772, 2016.

[4] Hirotaka Kaji, Kokolo Ikeda, and Hajime Kita. Avoidance of constraint violation for experiment-based evolutionary multi-objective optimization. In 2009 IEEE Congress on Evolutionary Computation, 2009.

[5] Rikky R.P.R. Duivenvoorden, Felix Berkenkamp, Nicolas Carion, Andreas Krause, and Angela P. Schoellig. Constrained Bayesian Optimization with Particle Swarms for Safe Adaptive Controller Tuning. IFAC-PapersOnLine 50, 1, 2017.