なにこれ
この論文の状況を参考にして、下記の問題を組合せ最適化を使って解きます。
(元の論文とは、別の問題です)
問題
100色 使用されている画像があります。ある人にとっては、赤と緑など、認識困難な色の組合せがいくつかあります。全ての認識困難な色の組合せに対し、色を変換することによって、認識しやすくなるようにしたいとします。なるべく変換する色数を最小化するには、どの色を変換したらいいでしょうか？
前提
- 色は0から99の数字で表される。
- 認識困難な色の組合せは3色からなる。
- 3色のうち少なくとも1色を未使用にすれば、認識困難でなくなる。
- 未使用にされた色は、色番号が1つ隣の色に変更する。
- 色番号が連続するものは、未使用にしない。例えば、33と34を両方とも未使用にはしない。
- 認識困難な色の組合せの数は20とする。
問題のパラメータ
ここでは、ランダムに作成します。
python
import numpy as np
from pulp import *
from itertools import combinations
from ortoolpy import addbinvars
N = 100 # 色数
np.random.seed(183)
acmb = list(combinations(range(N), 3)) # 全組合せ
# ランダムに20個の組合せを「認識困難な組合せとする」
cmb = [acmb[i] for i in np.random.choice(range(len(acmb)), 20, False)]
print(cmb)
>>>
[(28, 31, 73), (13, 65, 76), (17, 50, 52), (10, 81, 89), (3, 17, 21),
(3, 12, 92), (4, 23, 24), (12, 24, 39), (9, 16, 31), (38, 78, 99),
(10, 15, 79), (24, 33, 72), (26, 57, 89), (6, 51, 65), (8, 24, 33),
(40, 52, 88), (57, 75, 99), (16, 24, 75), (73, 86, 97), (20, 80, 97)]
定式化して解く
隣り合う色は未使用にしないので、「色XとYを未使用にしたが、Xの変更先がYになる」という状況は起こりません。なので、変更先は気にすることなく、未使用にする色だけ考えれば大丈夫です。
python
m = LpProblem() # 数理モデル
x = addbinvars(N) # 未使用にする色
m += lpSum(x) # 未使用にする色数の最小化
for i in range(N):
m += x[i]+x[(i+1)%N] <= 1 # 隣り合う色を同時に未使用にしない
for s in cmb:
m += lpSum(x[i] for i in s) >= 1 # 組合せ s の中の色を少なくとも1つは未使用にする
m.solve()
print('未使用にする色数 %d -> %d'%(len(np.unique(cmb)),
int(round(np.vectorize(value)(x).sum()))))
>>>
未使用にする色数 41 -> 9
20個の組合せの中で、41個の色が使用されていました。
9個選んで未使用にすることにより、全組合せで認識困難さをなくすことができました。
以上