氏名 熊谷ｸﾏｶﾞｲ

氏 名 熊谷

渉

所 属 理工学研究科 電気電子工学専攻 学 位 の 種 類 博士（工学）

学 位 記 番 号 理工博 第

号 学位授与の日付 令和

年

月

日

課程・論文の別 学位規則第４条第１項該当

学 位 論 文 題 名 変換不変性とパラメータ調整に基づくメタヒューリスティクスの設 計に関する研究

論 文 審 査 委 員 主査 教授 安田 恵一郎 委員 教授 杤久保 文嘉 委員 准教授 相馬 隆郎

【論文の内容の要旨】

「最適化」は工学に限定されることなく，経済学，社会学等の幅広い分野に及んで応用 され，その重要性は広く認識されている。工学的応用を念頭においた最適化は，①実シス テムの大規模さ・複雑さ，②システムのモデリング・シミュレーション技術，③コンピュ ータの計算能力，④最適化理論および最適化手法，の

つの主要な要素が互いに強い影響 を与えながら発展してきた。近年のシステムの大規模化・複雑化やシステム・工業製品の 性能に対する要求の高度化が進んでいる一方で，

年頃から，第

次人工知能ブームを 牽引する深層学習の登場や，

による並列化・コンピュータパワーの増大などを背景にモデリング・シミュレーション技 術も進化している。以上のように，最適化技術を取り巻く環境は急速に変化しており，こ れらの変化に対応可能な最適化技術が求められている。

古典的な最適化技法を集大成した数理最適化（数理計画法）は，

年代の高速・大容

量のコンピュータの出現を原動力にして，単体法や準

法をはじめとする実用的な

アルゴリズムの構築と有用性の検証が急速に進展した。非線型連続最適化では

目的関数の

クラスや性質（非凸性・悪スケール性・変数間依存性）が問題となるが

数理最適化は目的

関数の解析的情報（勾配や

行列など）を使用することで

悪スケール性と変数間依

存性に対処している。一方，近年

シミュレータなどのブラックボックスな入出力情報のみ

を用いて

良好な解を探索する問題

ブラックボックス最適化（

：

）の形態が，製品設計，機械学習のハイパーパラメータ決定，実験データベースを活

用した新素材探索などにおいて増えている。

では，対象の目的関数の解析的情報は得

られず，数理最適化は適用できないため，入力（決定変数値情報）と出力（目的関数値情

報）のみだけで探索が可能なアルゴリズムである，直接探索法の適用が必要である。代表 的な直接探索法の枠組みとしてメタヒューリスティクスが知られている。メタヒューリス ティクスは，生物現象や自然現象などの経験的に優れたメカニズムからのアナロジーによ り構築されており，実用的な時間に応じて最適性の高い近似解を求めることができる発見 的近似解法である。また，多点・確率的探索であるため，並列処理に適している，非凸性 に対応可能である点からも，環境変化に対応可能な最適化の枠組みとして期待できる。

しかし，メタヒューリスティクスは調整可能なパラメータを有しているが，十分な探索 性能を発揮するには，パラメータ設定に関する使用者の高い専門的な知識・経験や試行錯 誤を必要とする。さらに，

では，目的関数の構造や性質が得られないため，これらの 有無や変化に対してアルゴリズムの探索性能が影響されないことに加え，パラメータ設定 がなるべく不要で探索性能を十分に発揮できることが望ましい。このため，

を解くア ルゴリズムは，高いロバスト性や適応性を具備すべきである。ロバスト性とは，探索過程 でアルゴリズムのパラメータを固定した状態でも，目的関数の構造や性質に対して探索性 能が維持できる性質を表し，適応性とは，探索過程で逐次得られる問題構造の情報を活用 して，アルゴリズムのパラメータを動的に調整することで，対象問題に適応する性質を表 す。以上の背景から，高いロバスト性・適応性を具備する

のためのメタヒューリステ ィクスの開発は重要な課題となっている。

ロバスト性を実現する性質として変換不変性が，適応性を実現する機能としてパラメー タ調整が挙げられる。よって，変換不変性とパラメータ調整に基づくメタヒューリスティ クスは，

のための高いロバスト性・適応性を具備すると考えられる。以上の背景を踏 まえ，本論文では，変換不変性とパラメータ調整に基づくメタヒューリスティクスの解析 と開発に関する検討を行った。メタヒューリスティクスの探索構造が変換不変性の定義を 満たすかどうかを調べれば，その変換不変性の有無を指摘することが可能である。本論文 では，このアプローチによって様々な既存手法の変換不変性の有無を明らかにすることで 課題を指摘した後，代表的なメタヒューリスティクスである

（

） ，

（

） ，

（

）において欠如し ていた変換不変性を付加することで，不変性を有する手法を提案した。

また，本論文では，下記の

および

のロバスト性と適応性の観点に基づき，

と

のパラメータ調整則を設計し，不変性を有する適応型メタヒューリスティクスを提案した。

(1)

有効な探索戦略として多様化・集中化が知られており，多様化・集中化をより明確に実 現することで，探索性能の向上が期待できる。多様化・集中化の観点からメタヒューリ スティクスの探索状態を評価する指標を定義した後，メタヒューリスティクスが有する パラメータを解析し，評価指標に基づき探索過程で探索状態を有効に制御するパラメー タ調整則を検討した。

(2)

メタヒューリスティクスの変換不変性は，パラメータ調整則の付加によって，その有無

が変わることがある。これを用いて，①欠如している変換不変性を補完し，探索構造全

体が多くの変換不変性を有しているかのようにパラメータ調整則を付加する，②有して いる変換不変性を維持するようにパラメータ調整則を付加する，という不変性に基づく 二つの設計指針を提示した。これらの設計指針に従い，探索構造全体が多くの変換不変 性を獲得するように，あるいは維持するようにパラメータ調整則を検討した。

さらに，本論文では，欠如している変換不変性を付加する上記のアプローチは，他の変 換不変性を犠牲にすることが多く，より一般のアフィン変換不変性を獲得することが困難 であることを指摘した。なお，アフィン変換は，回転変換，スケール変換，平行移動変換 を含んでおり，解空間に施すことで変数間依存性，悪スケール性，原点依存性を発生させ ることができる。これを踏まえ，本論文では，アフィン変換不変性を具備する最適化アル ゴリズムの「フレームワーク」を提案し，このフレームワークに対して不変性定理を与え た。この定理は，フレームワークの範囲で設計された全てのアルゴリズムに対して適用可 能であり，要求条件さえ満たすようにアルゴリズムを設計すれば，アフィン変換不変性を 具備することを表すものである。このフレームワークに従えば，アフィン変換不変性を具 備することを保証しながら，様々な最適化能力を自由に付与でき，さらにパラメータ調整 則を付加することも可能である。つまり，高いロバスト性と適応性の具備が可能な汎用的 なフレームワークであるといえる。

本論文は，全

章より構成されており，各章の概要および得られた成果は以下の通りで ある。

第

章は序論であり， 最適化のニーズや最適化アルゴリズムの発展を概観するとともに，

BBO

での適用を目的とした最適化アルゴリズムが具備すべき基本的な要件を系統的に整理 し，本論文の概要と位置付けを記載した。

第

章では，本論文の主眼としている

の最適化問題の性質と，

で使用される 最適化アルゴリズムについて概観し，その数理的構造や特徴を記述している。特に，

のための最適化アルゴリズムには，ロバスト性と適応性が求められることを述べ，第

章 以降へ繋がる問題提起を行った。

第

章では，第

章以降の数理的解析のための基盤を形成するために，既存のメタヒュ ーリスティクスを概観しながら，その探索構造を解析し，共通の構造を抽出した。

第

章では，まず変換不変性の定義を述べ，様々な既存のメタヒューリスティクスの変 換不変性について解析・評価した。そして，

に対して共分散行列を用いて回転不変性 を付加した手法を提案し，数値実験を通じて回転変換に対してロバスト性が向上したこと を確認した。さらに，

に対して超球を用いて回転不変性を付加した手法を提案し，数 値実験を通じて回転変換に対してロバスト性が向上したことを確認した。最後に，

に対 して共分散行列を用いてアフィン変換不変性を付加した手法を提案し，数値実験を通じて アフィン変換に対してロバスト性が向上したことを確認した。

第

章では，既存のパラメータ調整則を概観しながら，変換不変性とパラメータ調整則

の関連を明らかにし，不変性に基づくパラメータ調整則の設計指針を二つ提示した。一つ

目の指針に従い，

に対してスケール不変性の補完と適応性の向上が可能なパラメータ調 整則を付加することで適応型

を提案し，数値実験を通じてそのロバスト性・適応性を確 認した。さらに，二つ目の指針に従い，第

章で提案した回転不変性を有する

に対し て，不変性の維持と適応性の向上が可能なパラメータ調整則を付加することで，回転不変 性を有する適応型

を提案し，数値実験を通じてそのロバスト性・適応性を確認した。

第

章では，第

章を含む，変換不変性を付加するアプローチは，他の変換不変性を犠 牲にすることが多く，より一般のアフィン変換不変性を獲得することが困難であることを 指摘した。そこで，アフィン変換不変性をすでに具備することが保証された，最適化アル ゴリズムの「フレームワーク」を構築し，このフレームワークのもとで様々な最適化能力 を付与することで，具体的なアルゴリズムを設計する新たなアプローチを提案した。この フレームワークに従って，

に着想を得た新たなアルゴリズムを設計し，数値実験を通 じて，アフィン変換に対するロバスト性を有することを確認した。

第

章は，本論文の結論であり，本論文で得られた研究成果および今後の研究の展望を

まとめた。