最適化とは

私見ですが画像認識と並んで社会実装が進んでいるAI分野は最適化だと思っています。
今回はそんな最適化技術について概要を説明していきたいと思います。

最適化の概要

最適化というのは手法の名前というより問題設定の名前になります。

大枠で言うと何かしらの定量化された指標があって、その指標を色々な制約を満たしながら、最小化(もしくは最大化)するための条件を探すような問題設定全般のことを言います。

遠足のお菓子を最適化しよう

例えば、お小遣いとして300円持っていて、お小遣いでお菓子を買うことを考えます。
お菓子としては下記の３種類あるとして、今回の目的は300円で最も満足度の高い組み合わせを考えることです。

	うまい棒	ポテチ小	ガム
値段	10円	90円	100円
満足度	1	10	10

うまい棒を30個とかガムを3個とか色々考えられますが、この人の場合は買うものによって満足度が同じでも値段が違ったりしていますね。
今回の答えとしてはポテチ小を3個、うまい棒を3個の合計満足度33が答えとなります。

この例では

• 定量化された指標 = 満足度の合計値
• 色々な制約 = お小遣いが300円しか無い

という条件で最適化を行なっています。

最適化用語をもう少しちゃんと表現

上記では砕けた表現をしましたが、最適化では下記のような表現がよく使われます。

最適化用語	上で使ってた表現	例
目的関数・評価関数	何かしらの定量化された指標	満足度の合計値
制約条件	色々な制約	お小遣いが300円
変数	最小化するための条件	各お菓子の購入個数

最適化を改めて最適化用語で表現すると

目的関数を制約条件を守りながら最小化する変数を決定する問題

といった感じになります。

最適化の種類

最適化は大別して２種類に分かれます。

• 離散最適化（組み合わせ最適化）
• 連続最適化

離散最適化（組み合わせ最適化）とは

変数として整数などの離散値を含むような最適化問題のことを離散最適化や組み合わせ最適化と言います。

最初はイメージがわかないと思いますが、実はビジネス的な様々な問題は組み合わせ最適化問題として表現できるのものがめちゃくちゃ多いです。
そのため、最適化エンジニアになりたいと思っている方は後で説明する連続最適化というよりは組み合わせ最適化について勉強するのが重要になります。

組み合わせ最適化問題として有名な定型問題がいくつもあります。

• ナップサック問題
• 巡回セールスマン問題
• スケジューリング問題

などなど。

上記のお菓子の例などはナップサック問題とみなして解くことが可能です。

そしてこれらの定型問題をどうやって解けば良いかということもよく研究されています。
細かいことはまた別で説明したいと思いますが、以下のように手法を分類できるかなと思います。

• 最適化ソルバ
• ヒューリスティクス
• メタヒューリスティクス
• 深層学習系

組み合わせ最適化の勉強をする際はどんな定型問題があって、それを解くための手法はどういったものがあるのか、と言うところから勉強していくと仕事にも活かしやすいんじゃないかなと思います。

連続最適化とは

連続最適化とは変数として連続値だけを扱うような最適化問題となります。

問題設定として有名なのは

• 線形計画問題
• ２次計画問題

とかかなと思います。

組み合わせ最適化に比べて業務で取り扱うことは少ないですが、線形計画問題に問題を当てはめて取り組んだことがあります。

実はAIエンジニアであれば連続最適化自体にはいつもお世話になっていたりします。
ニューラルネットで学習をするために最急降下法が使われていますが、実はあれが連続最適化になります。

解き方としては

• 最適化ソルバ
• 最急降下法
• ニュートン法

などがあります。

まとめ

今回は最適化の概要についてまとめてみました。

細かい話は全てすっ飛ばしているので、そちらについてはまた記事を作りたいと思いますが、雰囲気を掴んでもらえたら嬉しいです。