「最適化」の話

おはようございます。気のせいか体の節々に軽い痛みを感じることもあって、特に足についてその頻度がやや多い気がしてて、歳が歳だけに軟骨でもすり減ってきたのかな、と多少気になりだした今日このごろです。で、早朝から過去のSNS投稿見てて、ふとこの話を扱いたくなったので書ける範囲で書きます。「最適化」の話。

ちょっと流石にこの話題を全く調べずに書くのも負担の大きい事かも知れず、多少は引用など交えながら書きます。最初に、そもそも「最適化」とは何かを定義すると、一言で言えば「各種の制約条件の中で、目的関数を最大化（最小化）する」ことと言えるかと思います。仮に例えば、工業製品の生産において、保有原材料から最終製品を製造して、販売したときの利潤をどう最適化するか、という問題かと思います（実際には、これは非常に複雑な話になるのでここまで細かいことはここでは扱いません）。

ざっくりとこの話題を大別すると、その中身はちょっと難しく言えば「微分可能な問題」の最適化と、「微分不可能な問題」の最適化に分けることが出来、前者を「数理最適化」、後者を「離散最適化」と呼ぶことが可能かと思います。

で、まず数理最適化について見ると、その中身は様々で広義には高校数学等で習う「線形計画法」と言ったものもその中に含まれ、その拡張とも言える、より多項の連立式に応用可能な「掃き出し法」というものも同様と言えます。これらも、誤解を恐れず言えば数学的に例えば方程式等で表現できる問題をそれこそ数理を用いて解の最適化を行なうもの、と言えるかと思います。数学的に表現できる問題の中でも、「曲線」で表される多少複雑な問題については、手法としては例えば「最急降下法」と言ったそれもまた数学的な解法が存在します。但し、こうした手法には対象の問題が仮に微分可能な連続性のある問題であっても、いわゆる「局所解」に収束する可能性があり、そういった問題の広域最適化を行なう場合は、数学的なものとは全く別のアプローチ、ヒューリスティックな各種の手法が用いられる場合もあります（GAなど）。

次に、離散最適化について扱うと、これは上記のような連続性で表現できる問題とは異なり、その領域における解と解の間に連続性がなく、これを数学的に言えば「微分不可能」となりますが、例えば最急降下法のような関数の「傾き」に基づく最適解の探索が行えない問題ということが出来ます。一例を挙げると、よく例にされるのは閉塞空間において多数の通過点（ノード）がある中で、どのノードを通過すれば出発点から到着点までの経路を最短に出来るか、と言ったような「経路探索問題」が代表的なものかと思います。具体的な例では、よく入門的に扱われるのが「巡回セールスマン問題」等と思います。

こうした離散最適化問題の多くは、扱う問題における解候補の集合の大きさ（ここでは母集合、とします）によって問題の複雑さが変わると言え、そのため母集合の大きさによっては、数学的な手法ではそもそも実時間内での解の探索が行えないこととなります。話を飛躍させればそれこそ「将棋」における最適な次の一手の探索、と言った話になるかと思いますが、これは、母集合に含まれる解候補の数によって、探索を行なう必要のある組み合わせが母集合の大きさによって指数級数的に増大することが原因となります。そのため、こうした問題の最適値の探索には、それこそヒューリスティックな手法、言い換えるとAI領域の各分野の技術（深層学習、GAなど）が用いられることとなります。

こうした最適化も、冒頭で述べたような「入力に対する出力の最大化」と言った話から、例えば部屋の中の家具の配置を過ごしやすいようにする、と言った多少「定性的」な要素を含む話にも必要な場合があり、そうした目的や
問題に対して先程述べたような対象問題に応じた各種の手法があるかと思います。

今日では、様々な製造や計画の現場でこうした最適化問題を解くことも多数あると思いましたので、今日は書ける範囲で概要的なことを書いてみました。言葉足らずの内容とは思いますが、何かのお役に立てば幸いです。以上です。