これは、アルゴリズム Advent Calendar 2015の3日目の記事です。
はじめに
実験計画法の簡単な紹介と、その発展として組合せ最適化によるアプローチを紹介します。
背景
- センサー情報からある解析をしたいとします。
- センサーは、1万円のものと3万円のものがあり、置かないこともあるので、3種類の選択があります。
- センサーの設置場所は、20カ所の候補があります。
- 全センサーの総購入費用は5万円以下に抑えないといけません。
- どこにいくらのセンサーを置いたら、効率よく検証できるのかを知りたいものとします。
ケースの例としては、「A地点とB地点に1万円のセンサー、C地点に3万円のセンサーを配置」となります。
用語
下記の用語を使います。
- 要因：水準を決めたい検討対象。今回は、センサーの配置候補。
- 水準：要因の取り得る値。今回は、センサーの費用で、0万円、1万円、3万円の3種類。
- 交互作用：ある要因の与える影響が他の要因の水準によって変わること。
- ラテン方陣：数字の行列で、その行やどの列にも同じ数字がないもの。
- 実験計画法：効率のよい実験を行う方法。ここでは、ケース数の削減を目指します。
今回は、交互作用はないものとします。
実験計画法を用いたケース数の求め方。
背景の話とは別に一般論として、要因が3種類、水準が3種類の例を示します。単純に考えると$3^3 = 27$通りのケース数が必要になります。
実験計画法では、ラテン方陣(下図)を元にケース数を作成することができます。
| 1 | 2 | 3 |
|---|---|---|
| 2 | 3 | 1 |
| 3 | 1 | 2 |
ラテン方陣を使うと以下のように9ケースで効率よく行うことができます。この9ケースは、全ての要因・水準の組合せを含んでいて、どの要因・水準の数も同じになっています。
選択された9ケース(各要因ごとの水準)
- 1,1,1
- 1,2,2
- 1,3,3
- 2,1,2
- 2,2,3
- 2,3,1
- 3,1,3
- 3,2,1
- 3,3,2
ラテン方陣の9マスそれぞれがケースに対応するので、行番号を要因1、列番号を要因2、マスの数字を要因3の水準と考えます。
実験計画法の欠点
実験計画法では、以下の欠点があります。
- 特定の要因数、水準数しかできません。
- 追加の条件があっても考慮できません。
組合せ最適化による考え方
実験計画法では、要因・水準の組みを一定数確保した上で、なるべく少ないケース数になるように選んでいました。
同じことを最適化問題として考えることができます。
具体的には、各要因の各水準を含むケースの最低数を指定して、ケースの選択方法を混合整数最適化によって求めます。
定式化
| 目的関数 | $\sum_i{v_i}$ | 必要ケース数 |
|---|---|---|
| 制約条件 | $\sum_i{\{C_{ij} v_i ｜ C_{ij} = k\}} \ge N$ $\forall j \lt 3, \forall k \in \{0, 1, 3\}$ | 各要因、各水準ごとにケース数が最低数以上あること |
| 変数 | $v_i \in \{0, 1\} \forall i \lt 総ケース数$ | 各ケースごとに選択するかどうか |
$C_{ij}$は$i$番目のケースの$j$番目の水準を、$N$は最低数を表します。
Pythonを用いると以下のように求めることができます。(変数casesに、購入費用が5万円以下の総ケースが入っているものとします。)
from pulp import *
r = [0, 1, 3] # 水準
for N in [20, 40, 60, 120]: # 最低数
m = LpProblem()
v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cases))]
m += lpSum(v)
for j in range(len(cases[0])):
for k in r:
m += lpSum(v[i] for i in range(len(cases)) if cases[i][j] == k) >= N
m.solve()
print(N, LpStatus[m.status], value(m.objective)) # 最低数、ステータス、ケース数
結果
ランダムサンプリングの場合と比較してみます。ランダムサンプリングの最低数はシミュレーションで出したおおよその値です。
組合せ最適化を用いることで効率よくケースを選択できたことがわかります。
| 最低数 | 組合せ最適化 | ランダムサンプリング |
|---|---|---|
| 20 | 400ケース | 3200ケース |
| 40 | 800ケース | 5700ケース |
| 60 | 1200ケース | 7900ケース |
| 120 | 2400ケース | 14400ケース |