search
LoginSignup
54

More than 5 years have passed since last update.

posted at

updated at

実験計画法と組合せ最適化

これは、アルゴリズム 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万円以下の総ケースが入っているものとします。)

python
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ケース

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
54