A Study on Design for Metaheuristic Optimization Algorithms Based on Invariance and Parameter Tuning

「最適化」は工学に限定されることなく，経済学，社会学等の幅広い分野に及んで応用され，その重要性は広く認識されている。工学的応用を念頭においた最適化は，①実システムの大規模さ・複雑さ，②システムのモデリング・シミュレーション技術，③コンピュータの計算能力，④最適化理論および最適化手法，の 4 つの主要な要素が互いに強い影響を与えながら発展してきた。近年のシステムの大規模化・複雑化やシステム・工業製品の性能に対する要求の高度化が進んでいる一方で，2010年頃から，第3次人工知能ブームを牽引する深層学習の登場や，General-Purpose Computing on Graphics Processing Unitsによる並列化・コンピュータパワーの増大などを背景にモデリング・シミュレーション技術も進化している。以上のように，最適化技術を取り巻く環境は急速に変化しており，これらの変化に対応可能な最適化技術が求められている。 古典的な最適化技法を集大成した数理最適化（数理計画法）は，1970年代の高速・大容量のコンピュータの出現を原動力にして，単体法や準 Newton 法をはじめとする実用的なアルゴリズムの構築と有用性の検証が急速に進展した。非線型連続最適化では，目的関数のクラスや性質（非凸性・悪スケール性・変数間依存性）が問題となるが，数理最適化は目的関数の解析的情報（勾配やHesse 行列など）を使用することで，悪スケール性と変数間依存性に対処している。一方，近年，シミュレータなどのブラックボックスな入出力情報のみを用いて，良好な解を探索する問題，ブラックボックス最適化（Black-Box Optimization：BBO）の形態が，製品設計，機械学習のハイパーパラメータ決定，実験データベースを活用した新素材探索などにおいて増えている。BBOでは，対象の目的関数の解析的情報は得られず，数理最適化は適用できないため，入力（決定変数値情報）と出力（目的関数値情報）のみだけで探索が可能なアルゴリズムである，直接探索法の適用が必要である。代表的な直接探索法の枠組みとしてメタヒューリスティクスが知られている。メタヒューリスティクスは，生物現象や自然現象などの経験的に優れたメカニズムからのアナロジーにより構築されており，実用的な時間に応じて最適性の高い近似解を求めることができる発見的近似解法である。また，多点・確率的探索であるため，並列処理に適している，非凸性に対応可能である点からも，環境変化に対応可能な最適化の枠組みとして期待できる。 しかし，メタヒューリスティクスは調整可能なパラメータを有しているが，十分な探索性能を発揮するには，パラメータ設定に関する使用者の高い専門的な知識・経験や試行錯誤を必要とする。さらに，BBOでは，目的関数の構造や性質が得られないため，これらの有無や変化に対してアルゴリズムの探索性能が影響されないことに加え，パラメータ設定がなるべく不要で探索性能を十分に発揮できることが望ましい。このため，BBOを解くアルゴリズムは，高いロバスト性や適応性を具備すべきである。ロバスト性とは，探索過程でアルゴリズムのパラメータを固定した状態でも，目的関数の構造や性質に対して探索性能が維持できる性質を表し，適応性とは，探索過程で逐次得られる問題構造の情報を活用して，アルゴリズムのパラメータを動的に調整することで，対象問題に適応する性質を表す。以上の背景から，高いロバスト性・適応性を具備するBBOのためのメタヒューリスティクスの開発は重要な課題となっている。 ロバスト性を実現する性質として変換不変性が，適応性を実現する機能としてパラメータ調整が挙げられる。よって，変換不変性とパラメータ調整に基づくメタヒューリスティクスは，BBOのための高いロバスト性・適応性を具備すると考えられる。以上の背景を踏まえ，本論文では，変換不変性とパラメータ調整に基づくメタヒューリスティクスの解析と開発に関する検討を行った。メタヒューリスティクスの探索構造が変換不変性の定義を満たすかどうかを調べれば，その変換不変性の有無を指摘することが可能である。本論文では，このアプローチによって様々な既存手法の変換不変性の有無を明らかにすることで課題を指摘した後，代表的なメタヒューリスティクスであるParticle Swarm Optimization（PSO）， Artificial Bee Colony Algorithm（ABC）， Cuckoo Search（CS）において欠如していた変換不変性を付加することで，不変性を有する手法を提案した。 また，本論文では，下記の(1)および(2)のロバスト性と適応性の観点に基づき， CSとPSOのパラメータ調整則を設計し，不変性を有する適応型メタヒューリスティクスを提案した。 (1) 有効な探索戦略として多様化・集中化が知られており，多様化・集中化をより明確に実現することで，探索性能の向上が期待できる。多様化・集中化の観点からメタヒューリスティクスの探索状態を評価する指標を定義した後，メタヒューリスティクスが有するパラメータを解析し，評価指標に基づき探索過程で探索状態を有効に制御するパラメータ調整則を検討した。 (2) メタヒューリスティクスの変換不変性は，パラメータ調整則の付加によって，その有無が変わることがある。これを用いて，①欠如している変換不変性を補完し，探索構造全体が多くの変換不変性を有しているかのようにパラメータ調整則を付加する，②有している変換不変性を維持するようにパラメータ調整則を付加する，という不変性に基づく二つの設計指針を提示した。これらの設計指針に従い，探索構造全体が多くの変換不変性を獲得するように，あるいは維持するようにパラメータ調整則を検討した。 さらに，本論文では，欠如している変換不変性を付加する上記のアプローチは，他の変換不変性を犠牲にすることが多く，より一般のアフィン変換不変性を獲得することが困難であることを指摘した。なお，アフィン変換は，回転変換，スケール変換，平行移動変換を含んでおり，解空間に施すことで変数間依存性，悪スケール性，原点依存性を発生させることができる。これを踏まえ，本論文では，アフィン変換不変性を具備する最適化アルゴリズムの「フレームワーク」を提案し，このフレームワークに対して不変性定理を与えた。この定理は，フレームワークの範囲で設計された全てのアルゴリズムに対して適用可能であり，要求条件さえ満たすようにアルゴリズムを設計すれば，アフィン変換不変性を具備することを表すものである。このフレームワークに従えば，アフィン変換不変性を具備することを保証しながら，様々な最適化能力を自由に付与でき，さらにパラメータ調整則を付加することも可能である。つまり，高いロバスト性と適応性の具備が可能な汎用的なフレームワークであるといえる。 本論文は，全 7 章より構成されており，各章の概要および得られた成果は以下の通りである。 第1章は序論であり，最適化のニーズや最適化アルゴリズムの発展を概観するとともに，BBOでの適用を目的とした最適化アルゴリズムが具備すべき基本的な要件を系統的に整理し，本論文の概要と位置付けを記載した。 第2章では，本論文の主眼としているBBOの最適化問題の性質と，BBOで使用される最適化アルゴリズムについて概観し，その数理的構造や特徴を記述している。特に，BBOのための最適化アルゴリズムには，ロバスト性と適応性が求められることを述べ，第 3 章以降へ繋がる問題提起を行った。 第3章では，第4章以降の数理的解析のための基盤を形成するために，既存のメタヒューリスティクスを概観しながら，その探索構造を解析し，共通の構造を抽出した。 第 4 章では，まず変換不変性の定義を述べ，様々な既存のメタヒューリスティクスの変換不変性について解析・評価した。そして，PSO に対して共分散行列を用いて回転不変性を付加した手法を提案し，数値実験を通じて回転変換に対してロバスト性が向上したことを確認した。さらに，ABCに対して超球を用いて回転不変性を付加した手法を提案し，数値実験を通じて回転変換に対してロバスト性が向上したことを確認した。最後に，CSに対して共分散行列を用いてアフィン変換不変性を付加した手法を提案し，数値実験を通じてアフィン変換に対してロバスト性が向上したことを確認した。 第 5 章では，既存のパラメータ調整則を概観しながら，変換不変性とパラメータ調整則の関連を明らかにし，不変性に基づくパラメータ調整則の設計指針を二つ提示した。一つ目の指針に従い，CSに対してスケール不変性の補完と適応性の向上が可能なパラメータ調整則を付加することで適応型CSを提案し，数値実験を通じてそのロバスト性・適応性を確認した。さらに，二つ目の指針に従い，第4章で提案した回転不変性を有するPSOに対して，不変性の維持と適応性の向上が可能なパラメータ調整則を付加することで，回転不変性を有する適応型PSOを提案し，数値実験を通じてそのロバスト性・適応性を確認した。 第6章では，第4章を含む，変換不変性を付加するアプローチは，他の変換不変性を犠牲にすることが多く，より一般のアフィン変換不変性を獲得することが困難であることを指摘した。そこで，アフィン変換不変性をすでに具備することが保証された，最適化アルゴリズムの「フレームワーク」を構築し，このフレームワークのもとで様々な最適化能力を付与することで，具体的なアルゴリズムを設計する新たなアプローチを提案した。このフレームワークに従って，PSO に着想を得た新たなアルゴリズムを設計し，数値実験を通じて，アフィン変換に対するロバスト性を有することを確認した。 第 7 章は，本論文の結論であり，本論文で得られた研究成果および今後の研究の展望をまとめた。