最適化手法と求解速度の関係
はじめに
はじめまして、ギリアでエンジニアをしている柏野と申します。
昨今、大規模言語モデルや画像生成AIの普及により「AIと言えば機械学習！」という認識が広まってきていると感じています。一方で、AIとはArtificial Intelligence（人工知能）の略で、広く捉えると「人が作り上げた知的に振る舞うもの」はすべてAIです。
ギリアではこの「より広い意味でのAI」を扱っており、機械学習系のほか、データドリブンなシステムの作成やあらゆる分野での最適化に関する仕事をしています。
今回は後者の「最適化」に関して、最適化とはなんぞや、最適化の速度に関する話と実験・結果などをまとめてみました。
最適化とは
まずはコトバンクから定義を引いてみましょう：
システム工学などで、特定の目的に最適の計画・システムを設計すること。コンピューターでは、プログラムを特定の目的に最も効率的なように書き換えること。オプティマイズ。オプティマイゼーション。
これだけを見るとシステム工学やコンピューター工学の分野専用な言葉のように感じますが、個人的にはそんなことはないと思っています。分野にかかる言葉を省くと「特定の目的に最適な〇〇を設計すること」になります。更に単純に言うと「目的に最も適した〇〇を見つけ出すこと」とも言えるでしょう。
「駅への最短距離」の「徒歩経路」を探索するあなた、「最強コスパ」の「今日の食堂メニュー」を探しているあなた、そして「最も無駄なく客先を回る」ための「訪問順」を考えるあなたも、日々最適化を行っています。
このような一般的に行われる最適化の他、わたしたちの社会を支える最適化は多くあります。運搬経路計画、生活インフラの設計・供給、工場の運営など、様々な見えるところ見えないところで最適化が行われています。社会の中で最適化が行われているからこそ、ネット上で頼んだ荷物が翌日に届き、低コストで良い商品を広く提供することが可能になっていると言っても過言ではないでしょう。
場合によっては迅速に最適な〇〇を求める必要があります。例えば、新しい注文が入った際の再計画や、刻一刻と変わる状況に対応できる人員配置などです。しかしながら、最適な〇〇を見つけるのが難しかったり時間がかかったりする場合もあります。食堂のメニューが毎日変わり選択肢が増えると、その日の最強コスパの一品または組合せを見つけるのが難しいのと同じです。最適化においての頑張りどころは「いかに早く良い〇〇を出すようなAIを作ることができるか」にあります。
求解速度と最適化手法
ここまで〇〇と呼んでいたものは最適化分野においては「解」と呼ばれ、良い「解」を得る速度を「求解速度」と呼びます。この求解速度に影響する要因は、問題の特性、解を求める手法、利用している計算機など様々です。今回は手法に関してお話しします。
最適化手法は多く、汎用的なもの・特定の問題に特化したもの、いくつかの選択肢から選ぶ離散問題・連続している数値を選ぶ連続問題に対応しているもの、解がどのように評価されているか知る必要がある・ないもの、など様々な特性を有しています。求解速度の観点から言うと、手法が必要とする試行回数と一試行あたりの時間が最も重要になってきます。賢く解を探索する手法は「試行回数を少なくすること」で、それによってより早く良い解にたどり着くことができます。一方で、比較的単純な探索方法で試行時間を短くし、数をこなす、というアプローチもあります。もちろん、理想的な手法は一回の試行で早く最適解を出せる手法なのですが、多くの場合はこれが叶わないのが現実です……。
そこで、問題に適した手法を用いたり作成したりすることで最も低い「試行回数×試行時間」を求めるのが我々の仕事です（最適化問題を解くことも最適化問題！）。今回は連続・離散問題に対して代表的な手法を用いて解を求めた場合の求解速度を計測し、その結果を通して手法の速度傾向について少し語らせていただきます。
求解速度
今回は離散と連続問題に対して各３手法での求解を行いました。離散問題は、決められた複数の地点を巡回して出発地に戻る場合の移動距離が最小となるルートを求める巡回セールスマンの問題を、連続問題は1次元系の単純な位置制御問題と比較的単純な問題を対象としました。
手法については、ランダム求解、勾配法、メタヒューリスティック法、強化学習を用いた機械学習エージェント手法を対象としました。表１ではそれぞれの説明と「最も頑丈な建物」の「梁と柱に使う材料」を探し当てる際の挙動の例を記載しました。
ランダム求解は、深い思考をせず選択肢を選ぶため、試行が早いことが想像できます。一方で、良い選択肢にたどり着くまで多くの試行回数が必要だと言うことも予想できます。
地形同様、最適化問題の目的にも「坂」という概念があり「良い解に近づく方向」という概念も存在します。これを利用したのが勾配法で、最も単純な場合、ひたすら坂を下りる（上る）ことで良い解を求めます。ランダム求解より賢い分、試行回数少なく良い解にたどり着けそうです。一方で、勾配法は「坂」を計算する時間が必要であり、盆地にハマり山向の谷底（最も良い解）にたどり着けない可能性もありますので万能とは言えません。
今回の検証で用いた「焼きなまし法」というメタヒューリスティック法の一種は、盆地（局所最適解）にハマる問題を解消するために乱数要素を取り入れたもので、一定確率で登る方向への移動も可能とし、谷底（全体最適解）にもたどり着けるようにしたものです。一歩進めるための手順が多い分、試行時間が比較的長い一方で、より良い解にたどり着ける可能性は存在しそうだと予想できます（メタヒューリスティック法は、金属工学から生物学まで色々なところからインスピレーションを得ているものがあり多彩なので、興味のある方は調べてみてください）。
機械学習エージェント手法による最適化は、我々が最も共感できる方法かもしれません。様々な経験を通して学んだ感覚から良い解を探します。感覚的な探索なので試行時間は短く、感覚が良ければ早く良い解にたどり着けることが予想できます。一方で、感覚が悪ければ、あるいは経験が少なく学びが足りない場合には十分に対応できない可能性があり、人が記述した手順より悪い結果を得ることになる可能性があります。
それぞれの問題に対して利用した手法と得られた結果は表２、表３に示しています。学習時間と平均求解時間は最も長い学習時間を基準に正規化しています。平均求解時間、目的関数の値は低いほうが良い表現となっています。
上記の結果から観察できる内容とそれから得られる結論を表４にまとめました。
まとめ
色々と語らせていただきましたが、最後に重要なポイントをまとめてみましょう：
最適化問題はどこにでもあって様々な面で大変重要な問題である
高速に最適化問題を解く需要があるが、これは大変難しい問題である
今回検証に使った手法の大まかな傾向は：
速度
メタヒューリスティック法＜勾配法＜＜＜機械学習エージェント手法≒ランダム求解
望める性能
離散の場合
ランダム求解＜機械学習エージェント手法＜メタヒューリスティック法
連続の場合
メタヒューリスティック法＜勾配法＜機械学習エージェント手法
従来の最適化手法に比べて、機械学習エージェント手法はランダム求解とほぼ同等の速度と高い性能の両方が望める手法となっていて、最先端の研究開発においても注目されています。複雑な関係性を紐解いて学び瞬時に正解を見出すAIによる求解は、人間が設計した手法に匹敵する性能と高い速度を両立させる可能性を秘めています。これは今回の結果からも見られる傾向でしたが、同時に勾配法やメタヒューリスティック法の従来手法が有効となる条件も確認できました。手法と問題には相性があり、それを見極めてソリューションを設計するのが重要だと感じています。
今回は最適化手法を４つピックアップして実験の対象としましたが、実際にはより多くの手法が存在します。また、手法の組合せなども含めると更に莫大な数のアプローチが可能になります。この莫大な数のアプローチから問題との相性、手法間の相性などを考慮してソリューションを作っていく必要性があります。例えば、人間が設計した手法で解を求めるのが難しい場合には機械学習を利用するのも一手、逆に、人の手で設計可能なシステムで解を求められるならそれもまた一手。いいとこ取りをして部分的に機械学習手法と設計したものを組み合わせるのも良いのです。
業務や開発の中でもヒトとAIとの共生を目指すギリアの柏野から、最適化という分野の概要、最適化手法と求解速度についてご紹介しました。
実験の実装と実行を担ってくれたエンジニアの東さん、インターンの濱さん、ありがとうございました！