データサイエンティスト スキルチェックリストver.3
『データサイエンティスト スキルチェックリストver.3』はデータサイエンティストに必要とされるスキルをチェックリスト化したもので、データサイエンティストに求められるスキルを「ビジネス力」「データサイエンス力」「データエンジニアリング力」の３分野に分けて定義したものです。
本記事では、データサイエンス力のチェックリストNo.269にある項目について、学んだことをまとめてみます。
| スキルカテゴリ | スキルレベル | サブカテゴリ | チェック項目 |
|---|---|---|---|
| 最適化 | ★★ | 最適化 | 組み合わせ最適化問題において、代表的な解法の概念を説明することができる（厳密解法（分枝限定法、動的計画法、切除平面法）、近似解法（局所探索、貪欲法など）、メタヒューリスティック解法（遺伝的アルゴリズム、タブーサーチなど）） |
特に本記事は、この中でも厳密解法について記述していきます。
組み合わせ最適化
参考：https://annealing-cloud.com/knowledge/1.html
組合せ最適化問題とは、様々な制約の下で多くの選択肢の中から、ある指標（価値）を最も良くする変数の値（組合せ）を求めることです。
問題
ナップサック問題
「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。
例えば、ナップサックの重量制限が4[kg]の下で、以下のような表があるとします。
| 商品 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重さ[kg] | 2 | 3 | 1 | 3 |
| 価値[万円] | 3 | 4 | 1 | 2 |
定式化
今、ナップサックの重量制限が$C$[kg]で、商品$n$個に、重さ$c_i$と価値$p_i$があるとします。
そうすると、ナップサック問題は以下のように定義できます。
\begin{align}
\max &\ f(x) = \sum_{i=1}^n c_i p_i \\
s.t. &\ \sum_{i=1}^n c_i x_i \leq C \\
&\ x_i \in \{0,1\}
\end{align}
$x_i$はその商品を入れるか(1)入れないか(0)を表した変数です。
上であげた例題を定式化してみると、以下のようになります。
\begin{align}
\max &\ \ 3x_1 + 4x_2 + x_3 + 2x_4\\
s.t. &\ \ 2x_1 + 3x_2 + x_3 + 3x_4 \leq 4 \\
&\ \ x_i \in \{0,1\} \ \ (i=1,\dots,4)
\end{align}
巡回セールスマン問題
都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
※巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される。
定式化
都市$i$から都市$j$までの距離を$c_{ij}$とし、都市$i$から$j$にセールスマンが行く場合$1$(それ以外は0)となる変数$x_{ij}$を用いると、以下のようになります。
\begin{align}
\min &\ \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}\\
s.t. &\ x_{ij} \in \{0,1\} \\
&\ \sum_{j:j \neq i} x_{ij} = 1 \ (i=1,\dots,n)\\
&\ \sum_{i:i \neq j} x_{ij} = 1 \ (j=1,\dots,n)\\
&\ \sum_{i\in S} \sum_{j\in S} x_{ij} \leq |S| - 1 \ (S \subset \{1,\dots,n\})
\end{align}
制約条件の2つ目と3つ目は都市$i$を出発する回数と都市$j$に到着する回数がそれぞれ1回ずつであることを示しています。
また、制約条件の4つ目は部分巡回路がないことを意味しています。部分巡回路は、例えば7つの都市がある場合に、4つの都市と3つの都市で、それぞれ四角形、三角形を作るような巡回路です。この問題では、7つの都市ならば、全てがつながって七角形を作ることが条件となっているため、この条件が加わっています。
解法
解法の分類
まずは、算出される最適解の厳密性で定義される分類として、厳密解法と近似解法があります。
- 厳密解法
- 大域的最適解を保証する
- 一般に計算量が大きくなる傾向にある
- 近似解法
- 大域的最適解は保証しない
- 良い解を高速に算出する
次に、問題の汎化性に関するものとして、ヒューリスティック解法とメタヒューリスティック解法があります。
- ヒューリスティック解法
- 発見的手法と言われ、そこそこの近似解を算出する方法
- 一般的にある問題に特化した方法
- メタヒューリスティック解法
- ヒューリスティック解法の内、特定の問題に依存せず手法のみが独立した汎用的な近似アルゴリズム
- 特定の問題のヒューリスティック解法に精度は劣ることが多いが、その分、汎化性を得ている
本記事では、厳密解法について紹介していきます。
- 分枝限定法
- 動的計画法
厳密に解く場合、解の候補を全列挙していけば解けることは確かです。
しかし、それでは問題の規模とともに、計算時間が膨大になり、現実的な時間で解けなくなります。
そこで、厳密解法では解の列挙に関して、なるべく無駄を省いていく形でアルゴリズムが作られています。
分枝限定法
分岐限定法は、分岐操作と限定操作から成ります。
分岐操作とは、場合分けによって問題を、部分問題に分割する操作を指します。
例えば、重量制限が4[kg]のナップサック問題の場合、
| 商品 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重さ[kg] | 2 | 3 | 1 | 3 |
| 価値[万円] | 3 | 4 | 1 | 2 |
\begin{align}
\max &\ \ 4x_2 + x_3 + 2x_4 + 3 \\
s.t. &\ \ 3x_2 + x_3 + 3x_4 \leq 2 \\
&\ \ x_i \in \{0,1\} \ \ (i=2,\dots,4)
\end{align}
- 商品1を入れた場合 ：重量制限が2[kg]で商品2-4が候補にあるナップサック問題になります(既に価値3[万円]がある状態)
- 商品1を入れない場合：重量制限が4[kg]で商品2-4が候補にあるナップサック問題になります
この２つの問題は、元の問題の部分問題と言えます。
場合分け1の場合、問題は、
\begin{align}
\max &\ \ 3x_1 + 4x_2 + x_3 + 2x_4\\
s.t. &\ \ 2x_1 + 3x_2 + x_3 + 3x_4 \leq 4 \\
&\ \ x_i \in \{0,1\} \ \ (i=1,\dots,4)
\end{align}
であり、場合分け2の場合、問題は
\begin{align}
\max &\ \ 4x_2 + x_3 + 2x_4\\
s.t. &\ \ 3x_2 + x_3 + 3x_4 \leq 4 \\
&\ \ x_i \in \{0,1\} \ \ (i=2,\dots,4)
\end{align}
となります。
そして、更に場合分けを続けます。
- において商品2を入れるという分岐は重量制限により出来ず、商品2を入れないという分岐しかありえません。
- において重量制限によって荷物2の操作が決まることはありません。
ここまでを図に示すと以下のようになります。
制約条件に従わない場合については以降の分岐は切り捨てて良いということになります。
これが解を列挙する上で必要のない部分を省略する考え方の1つになります。
もう1つの方法を紹介します。それが前回の記事で紹介した近似解法の『貪欲法』と『線形緩和法』を用いたやり方です。
簡単におさらいをすると、ナップサック問題における代表的な貪欲法は、価値/重量が大きい順に並べ替え、入るだけ荷物を入れていくというものでした。今回の問題に関する解は$(1,0,1,0)$の時に$4$となり、下界となります。
また、線形緩和法は、変数にかけられている$0$か$1$しか取らないという制約を、$0$以上$1$以下に置き換えて、連続最適化として解く方法です。今回の問題に関する解は$(1,2/3,0,0)$の時に$17/3$となり、上界となります。
さて、各場合分けした後の問題(部分問題と言います)について、線形緩和法の答えが出せます。
この答えは、『これよりはこの部分問題の解は良くならないよ』ということになります。
従って、もしこの部分問題の線形緩和解が4よりも小さければ、その場合分けでは今の$4$という解を超えることがないので、無視して良いでしょう。
これまで、制約条件を満たさない分岐、線形緩和解が下界を下回っている場合、以降の場合分けは必要ないことを紹介しました。
このような操作を限定操作といいます。
つまり、分枝限定法においては、場合分けによる部分問題への分割(分岐操作)と、そこに答えがないとわかった部分問題はそれ以上分割しない(限定操作)によって成り立っています。
厳密解法ですので、限定されない部分に関しては、候補の走査を行っていきます。
動的計画法
動的計画法は、以下のようなアルゴリズムになります(Wikipedia)
細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
・帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
・計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。
ここで『同じ計算を何度も行うことを避ける』という部分が、解の列挙に関して、無駄を省いていく点になりそうです。
動的計画法でナップサック問題を解いていく場合、以下のような帰納的な関係を用いる解法が知られています。
- 元の問題
- 商品N個で重量制限がWのときの、最大価値を求める
- 小さな問題
- i番目の商品までで、重量制限がcのときの、最大価値を求める
この小さな問題を$i=0,1,\dots,N$まで順番に解を求めていき、最後に重量制限$W$とした場合についての解を取り出すことで、元の問題を解きます。
では、前述した、重量制限が4[kg]のナップサック問題の場合について解いてみましょう ($W=4,N=4$)
| 商品 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重さ[kg] | 2 | 3 | 1 | 3 |
| 価値[万円] | 3 | 4 | 1 | 2 |
まず、全部の荷物を入れると9[kg]なので、以下のような箱を用意します。
横が重さで、縦が商品番号です。
まず、$i=0$について考えます。0番目の商品では、何も入っていないので0[kg]で価値も0です。
次に、$i=1$について、商品1を入れるか入れないかで分岐します。
更に、$i=2$について考えます。
ここで、$i=1$の時の解がわかっているので、そこからスタートすると、荷物2を入れるか入れないかだけを考えれば良いことになります。
※ $i=1$の答えを使わないと、荷物1と2をどう入れるか(4通り)についてすべて考える必要がありますが、$i=1$の結果を使うことで、荷物2を入れるかどうか(2通り)で済みます。これが帰納的な関係の利用です。
※ また、$i=1$は今、縦が1の箱に入っているので簡単に使うことができます。これが計算結果の記録を用いていることになります。
また、$i=3$について考えます。
この時、重さ3について、二方向から矢印が伸びていることがわかります。今は最大価値を求めるので、それぞれの矢印の結果で大きい方を取れば良いことがわかります。
$i=4$についても考えます。
最後に、元の問題では、重量制限が4ですので、重さ(横)が4で、商品(縦)が4の箱を見ればよいです。
こうして最大価値は$5$であるとわかりました。
また、矢印をたどることで、$(x_1,x_2,x_3,x_4)=(0,1,1,0)$であることもわかります。
最後に
今回は厳密解法について簡単にまとめていきました。
いずれも全探索に比べてどのように省略するかの考え方が大事になるアルゴリズムでした。