皆さんは、最適化アルゴリズムという言葉を聞いたことがありますか？
私たちは日々の生活の中で、最善の選択肢を導き出そうと工夫する機会がたくさんあります。
例えば、買い物をするときには、価格を抑えながらも品質を考慮して商品を選んだり、料理をするときには時間と美味しさのバランスを取るように調節したり...などです。
では、数学的・数値的に「最良」な解をどのようにして得ることができるのでしょうか？
また、変数が変化した場合に、それが関数で表されるとしたら、最適解をどのようにして導き出せるでしょうか？
今回は、そんな私たちの実生活にも深く応用されている「最適化アルゴリズム」についてざっっっっくりと紹介したいと思います。
（僕自身も勉強中のため、厳密には定義から逸れている可能性もあります。大枠のイメージを掴む程度にご活用ください。）
結論：最適化アルゴリズムとは？
最適化アルゴリズムとは「問題の最適解を探し出す手法」のことです。
より詳しく言うと「与えられた目的関数を最小化または最大化するためのアルゴリズム」です。
この目的関数とはどのようなものでしょうか？目的関数とは、最適解を求めたいものの変数を定式化し、関数として表したものです。
例を挙げて考えてみましょう。例えば、仮想的なレストランがあるとします。売り上げを$R$、商品の価格を$P$、販売数量を$Q$とすると、
$$R=PQ$$
と定式化することができます。
このように、最適解を求めたいものを定式化し、関数で表したものが目的関数です。
具体的な目的関数としては、
・二乗誤差の和
・尤度
・ヒンジ損失の和
などの目的関数があります。
最適化アルゴリズムでは、この目的関数における最も大きい点、もしくは最も小さい点を見つけることが最終的な目標です。
2.局所最適解と大域最適解
目的関数の最適解を求める代表的な方法として、「勾配降下法」という方法があります。これは関数を微分して（勾配ベクトルの逆向きに移動して）勾配が低い方に移動し続けるアルゴリズムです。
（勾配降下法のイメージ | 出典：https://en.wikipedia.org/wiki/Gradient_descent）
定式化するとこのような感じです。
$$x_{n+1}=x_n- \alpha \cdot \nabla f(x_n)$$
ここでクイズです。
【関数を微分して最も勾配が低い点が最適解と言えるでしょうか？】
正解はノーです。
例えば、目的関数が$y=x\sin(x)$という関数$(-8 \leqq x \leqq 8)$だとします。
これをグラフに表すと下のグラフのような曲線を得ることができます。
一見、この最適解を見つけるためには微分を繰り返して、勾配が最も低くなる点を探せば良いと思うかもしれません。
しかし、この関数には下に凸かつ勾配が0になる最適解が3つあります。
それは、この3点です。
このうち、$x= \pm 4.5$近辺にある最適解はこの関数の中で最も最小となる点となります。
一方、$x=0$の場合、勾配は0ですが、最小ではありません。
このような、全体の中で最も最小（最大）となる点を「大域最適解」、周辺の近傍において優れている一方で最小（最大）ではない点を「局所最適解」と言います。
つまり、先述の例の場合だと、$x= \pm 4.5$近辺にある点が大域最適解、$x=0$の点が局所最適解となります。
最適化アルゴリズムでは、この大域最適解を求めることが最終的な目標です。
3.最適化アルゴリズムとAI
最適化アルゴリズムは、近年話題のAIにおいても非常に重要な役割を果たしています。
AIでは出力された結果を私たちが求めている結果に近づけるために、様々なパラメーター（重みやバイアスなど）を調節しなければいけません。
このパラメーターをどのように調節すれば良いのかを、最適化アルゴリズムを使うことで求めることができます。
ニューラルネットワークでは、ニューロンに入力された値が重みやバイアスなどといったパラメーターによって調節され、それがReLuやシグモイド関数といった活性化関数に通されて、0~1の値になります。
例えば、手書きの文字を判別するAIを考えてみましょう。
（出典：3Blue1BlownJapan | https://www.youtube.com/watch?v=0AX3KSKjyog)
0~9の数字を表すニューロンが計10個あり、「1」と言うニューロンが1.00の値を、それ以外のニューロンは0.00と言う値を取って欲しいという目標があるとします。
このとき、実際に出力された値と予想していた値の差を取り、二乗して平均を取ることで、その出力された値がどのくらい予想していた値とずれているのかを検証することができます。この予測値との差を検証する関数を「損失関数」と言います。
ではこの差をどのように少なくすることができるのでしょうか？
それは、入力をxy軸に、損失関数をz軸とした3次元空間に置き換えることで考えることができます。
（出典：3Blue1BlownJapan | https://www.youtube.com/watch?v=0AX3KSKjyog)
この曲面における最適解に近づけるようにパラメーターを調節することで、より精度の高いAIになることがわかると思います。
このように、最適化アルゴリズムはAIにも利用されています。
4.有名な最適化アルゴリズム〜基礎編〜
それでは実際に、有名な最適化アルゴリズムを見ていきましょう！
・勾配降下法
勾配降下方は最適化アルゴリズムの中でも最も基本的なアルゴリズムです。関数を微分して勾配を計算することで最適解へと近づきます。
・モーメンタム
勾配降下法に慣性項を追加したもので、探索が鞍点などで止まってしまうことを防ぎます。
・アダム
モーメンタムとRMSPropのアイデアを組み合わせた方法で、学習率の調整が可能です。
・ニュートン法
二次導関数（ヘッセ行列）を使用して関数の最小値を見つけるためのアルゴリズムです。
5.有名な最適化アルゴリズム〜自然現象アルゴリズム編〜
最適化アルゴリズムの中には自然現象からヒントを得て作られたアルゴリズムがたくさんあります。その中でも有名なものを紹介します。
・遺伝的アルゴリズム(GA)
生物の進化のプロセスを模倣したアルゴリズムで、選択、交叉、突然変異という操作を通じて解の集合を進化させます。
・粒子群最適化(PSO)
鳥の群れや魚の群れの振る舞いを模倣したアルゴリズムで、解の集合（粒子）が解空間を探索し、最良の解に向かって移動します。
・焼きなまし法(シミュレーテッドアニーリング)
金属の精錬過程を模倣した確率的なアルゴリズムで、解空間をランダムに探索し、一定の確率で劣った解を採用することで局所最適解からの脱出を試みます。
・蟻コロニー最低化(ACO)
アリの食物探索の振る舞いを模倣したアルゴリズムで、アリがフェロモンの情報を利用して最短経路を見つける様子を模倣します。
（ACOのアルゴリズム | 出典：https://www.opentextbooks.org.hk/ditatopic/27149）
6.ちょっと変わった面白いアルゴリズム
最適化アルゴリズムの中にはちょっと変わった面白いアルゴリズムもあります。今回はその中でも特にユニークなものを紹介します。
・リーグチャンピオンシップアルゴリズム(LCA)
このアルゴリズムはリーグ戦のシステムから発想を得ているアルゴリズムです。各チーム（解）が他の全てのチームと対戦し、その結果に基づいてランキングが更新されます。これにより、最適な解（チャンピオン）が見つかることを目指します。
このアルゴリズムは制約なし最適化（制約が定まっていない数理最適化問題のこと）に適応することができるアルゴリズムです。
・地雷爆破アルゴリズム(MBA)
このアルゴリズムはなんと地雷爆弾の爆発からヒントを得ているアルゴリズムです。
地雷爆弾の爆発では、投げられた破片が爆発エリア付近の他の地雷爆弾と衝突して爆発します。このアルゴリズムの目標は地雷を見つけることですが、最も爆発効果が高く、最も多くの死傷者を出すことができる最適なポイント$x$にある地雷（大域最適解）を導き出す、というコンセプトです。
・帝国主義競争アルゴリズム(ICA)
このアルゴリズムは、帝国主義的な競争を模倣して最適化を行っています。解は「帝国」を形成し、帝国間の競争によって最適な解が見つかることを目指します。
・バレーボールプレミアリーグアルゴリズム(VPLA)
このアルゴリズムではバレーボールの試合を模倣して最適化を行います。各解がバレーボールのプレーヤーとして試合を行い、その結果に基づいて解の品質が評価されます。
7.現在僕が興味があるアルゴリズム〜SAA〜
SAA(Snow Avalanches algorithm)は2023年にKeyvan Golalipourらによって提唱されたアルゴリズムで、雪崩の様子から開発された最適化アルゴリズムです。
このアルゴリズムでは変数が少なく、解への収束が早いことが特徴です。
SAAではスキーヤーやスノーボーダーが雪崩を引き起こすと仮定し、スキーヤーやスノーボーダーまでがアルゴリズム変数に加わっているため、非常に驚きました。
8.現代の最適化アルゴリズム 〜MHAs〜
近年、メタヒューリスティクスアルゴリズム（MHAs）という最適化アルゴリズムが開発されています。
最適化アルゴリズムは①Traditional Algorithms、②meta-heuristic algorithm（MHA）と言う2つのアルゴリズムに分類することができます。
Traditional Algorithmsは、4の「有名な最適化アルゴリズム〜基礎編〜」にあるような微分や導関数を元にした最適化アルゴリズムです。
一方、MHAsは5の「有名な最適化アルゴリズム〜自然現象アルゴリズム編〜」や6の「ちょっと変わった面白いアルゴリズム」にあるような、微分や勾配計算だけではなく、自然的現象や社会的現象を加えることで、より汎用的に使えるアルゴリズムです。
MHAsについてや、最適化アルゴリズムがたくさんある理由については、次回の記事で詳しく解説したいと思います。
24/4/6補足：紹介した中には共進化アルゴリズム（Coevolutionary Algorithm）というアルゴリズムもあります。これはメタヒューリスティクスアルゴリズムとは異なりNFL定理が適応されないという特徴があります。
9.最適化アルゴリズムのこれからの課題と展望
この最適化アルゴリズムにはまだいくつかの課題があります。
例えば、鋭い局所的最適解がある場合や、工学などの複雑な最適化が必要なシーン、微分をすることができない場合などは、大域最適解に辿り着くことが保証されなかったり、最適解に収束するまでの時間がかかってしまいます。
より早く、楽に、大域最適解を導き出せるように、日々より良いアルゴリズムが開発され続けています。
10.まとめ
最適化アルゴリズムの全体像を、ざっくりと理解していただけたでしょうか？
僕も最適化の研究をしたいと決めてまだ数ヶ月、わからない所やあいまいな所も沢山ありますが、どんどん勉強して社会に貢献できるアルゴリズムを作りたいと思っています。
今後も研究に関連する記事を書こうと考えていますので、どうぞよろしくお願いします。
もし記事の中に誤った知識や表現、アドバイスなどがあれば、各種SNSやメールアドレス（hikkaruk@gmail.com）にご連絡ください。
最後まで読んでくださり、本当にありがとうございました！
参考文献：
梅谷俊二 (2020). しっかり学ぶ数理最適化 モデルからアルゴリズムまで. KS情報科学専門書.
Keyvan Golalipour(2023). Snow avalanches algorithm (SAA): A new optimization algorithm for engineering applications. Alexandria Engineering Journal, Volume 83, Pages 257-285. https://doi.org/10.1016/j.aej.2023.10.029
Ali Husseinzadeh Kashan(2011). An efficient algorithm for constrained global optimization and application to mechanical engineering design: League championship algorithm (LCA). https://www.sciencedirect.com/science/article/abs/pii/S0010448511001795
Ali Sadollah(2013). Mine blast algorithm: A new population based algorithm for solving constrained engineering optimization problems
Author links open overlay panel. https://www.sciencedirect.com/science/article/abs/pii/S1568494612005108
Jun-lin-lin(2012). Interaction Enhanced Imperialist Competitive Algorithms. https://www.mdpi.com/1999-4893/5/4/433
Reza Moghdani(2018). Volleyball Premier League Algorithm. https://www.sciencedirect.com/science/article/abs/pii/S1568494617307068
Xin-She Yang(2021). Genetic Algorithm. https://www.sciencedirect.com/science/article/abs/pii/S1568494617307068
Yudai Sadakuni(2018). 勾配降下法について. https://qiita.com/YudaiSadakuni/items/ece07b04c685a64eaa01
リュディア(2020). G検定 局所最適解と大域的最適解. https://note.com/lydiacorp/n/n077def41bf63
3Blue1BlownJapan. 深層学習の仕組み, 勾配降下 | Chapter 2, 深層学習（ディープラーニング）. https://www.youtube.com/watch?v=0AX3KSKjyog
※表紙の画像はAdobe Filefly(https://www.adobe.com/jp/products/firefly.html)によって生成しました。
