12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡

20-2. 遺伝的アルゴリズム（vcopt）でテント・アンド・ツリーパズルを解く

やること

テント・アンド・ツリーというパズルがあります。

Tents and Trees Puzzles - Apps on Google Play
Place a tent next to each tree in this picross-inspired chill puzzle game!
play.google.com

例題１

次の３つのルールを満たすように、黒いマスを「テント」か「芝生」で埋めていきます。

  1. 木の４近傍には必ずその木に所属するテントが１つある
  2. テントの８近傍には他のテントがあってはならない
  3. 各行、各列には数字の数だけテントが存在する

解答は一意に定まります。（芝生を１マスだけ残してあります）

今日は、このパズルをvcoptを用いて解いてみます。

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows
sourceforge.net

vcoptの使い方についてはチュートリアルをご参照ください。

お手軽最適化パッケージ「vcopt」チュートリアル
実行環境Windowsマシンで実行する方にはWinPython3.6をおすすめしています。インストール不要で、USBメモリに入れて持ち運ぶこともできます。...
vigne-cla.com
2019/09/23

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

お手軽最適化パッケージ「vcopt」仕様書
はじめにvcoptとは遺伝的アルゴリズム（Genetic Algorithm, GA）による本格的な組合せ最適化がお手軽にできる無料のPythonパッケージで...
vigne-cla.com
2019/09/22

考え方１

まず、テントが入る可能性があるマス（つまり木の４近傍のマス）の数だけ遺伝子座を用意し、各遺伝子座には０または１の遺伝子が入ることにします。０は芝生、１はテントを表します。

例題１の場合は13ヶ所です。

あとは評価関数において、パズルのルールが満たされているかを見て、満たされていなければペナルティを科します。

  1. 木の４近傍にあるテントの数が１でなければペナルティ
  2. テントの８近傍にある他のテントの数が０でなければペナルティ
  3. 各行、各列の「テントの数」と「数字」の差がペナルティ

ペナルティの合計が０になるように最適化します。なんだ簡単じゃないか！（）

考え方２

とフラグを立ててしまいましたが、実際にやってみるとうまくいきません。

例えば次のようなとき、

正解がパターン１であれば問題ないのですが、正解がパターン２であるときに困ります。下の木の４近傍にテントが２つあるためペナルティ＝１が科されます。最適化ではペナルティ０を目指すのでパターン１に近づきますが、正解はパターン２ですがら、正解から遠ざかっていまいます。

そこで、１番目のペナルティを修正します。

  1. 木の４近傍にあるテントの数が１または２でなければペナルティ
  2. テントの８近傍にある他のテントの数が０でなければペナルティ
  3. 各行、各列の「テントの数」と「数字」の差がペナルティ

※厳密に言えばこの条件では解が一意に定まらず、「その木に所属するテントが１つある」を満たさない解が出ることがありますが、今回はこれで良しとします。

pip, import

まだvcoptをpipしていない場合はpipします。

pip install vcopt

必要なパッケージをimportします。４近傍とか８近傍を畳み込むために signal.convolve2d() を用います。

import numpy as np
import numpy.random as nr
from copy import deepcopy
from scipy import signal
from vcopt import vcopt

パズル問題

パズル問題は ‘-‘ と ‘t’ で表現します。horizontal は右方向に並んだ数字、vertical は縦方向に並んだ数字です。

#============================
# パズル
#============================
pazzle = ['-----',
          '-t-t-',
          '-----',
          'tt---',
          '----t']
horizontal = [2,0,1,1,1]
vertical = [1,1,0,2,1]

前処理を行います。

#============================
# パズルの変換とフィルタの用意
#============================
tree = []
for line in pazzle:
    line = line.replace('-', '0')
    line = line.replace('t', '1')
    tree.append(list(line))
tree = np.array(tree, dtype=int)
print('tree\n{}'.format(tree))

tent = np.zeros(tree.shape, dtype=int)
print('tent\n{}'.format(tent))

horizontal = np.array(horizontal)
print('horizontal\n{}'.format(horizontal))
vertical = np.array(vertical)
print('vertical\n{}'.format(vertical))

#畳み込み用のフィルタ
filter_4 = np.array([[0, 1, 0],
                     [1, 0, 1],
                     [0, 1, 0]], dtype=int)
filter_8 = np.array([[1, 1, 1],
                     [1, 0, 1],
                     [1, 1, 1]], dtype=int)
tree
[[0 0 0 0 0]
 [0 1 0 1 0]
 [0 0 0 0 0]
 [1 1 0 0 0]
 [0 0 0 0 1]]
tent
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]
horizontal
[2 0 1 1 1]
vertical
[1 1 0 2 1]

木の配列、テントの配列（空っぽ）ができました。

評価関数

気になる方はコメントアウトを解除して詳しく見てみてください。

#評価関数
def score(para):
    #paraをテント配列に範反映
    tent_tmp = deepcopy(tent)
    tent_tmp[mask_candidate] = para
    #print('tent_tmp\n{}'.format(tent_tmp))
    
    #木の４近傍にあるテントの数
    tent_around_tree = signal.convolve2d(tent_tmp, filter_4, mode='same') * tree
    #print('tent_around_tree\n{}'.format(tent_around_tree))
    #それが１または２でない木
    penalty_tree = (tent_around_tree != 1) * (tent_around_tree != 2) * tree
    #print('penalty_tree\n{}'.format(penalty_tree))
    
    #テントの８近傍にあるテントの数
    tent_around_tent = signal.convolve2d(tent_tmp, filter_8, mode='same') * tent_tmp
    #print('tent_around_tent\n{}'.format(tent_around_tent))
    #それが０でないテント
    penalty_tent = (tent_around_tent != 0) * tent_tmp
    #print('penalty_tent\n{}'.format(penalty_tent))
    
    #horizontalのペナルティ。多いまたは少ない数
    penalty_horizontal = np.abs(np.sum(tent_tmp, axis=0) - horizontal)
    #print('penalty_horizontal\n{}'.format(penalty_horizontal))

    #verticalのペナルティ。多いまたは少ない数
    penalty_vertical = np.abs(np.sum(tent_tmp, axis=1) - vertical)
    #print('penalty_vertical\n{}'.format(penalty_vertical))
    
    #合計ペナルティ
    penalty = np.sum(penalty_tree) + np.sum(penalty_tent) + np.sum(penalty_horizontal) + np.sum(penalty_vertical)
    
    return penalty


#木の４近傍のマス
mask_candidate = (signal.convolve2d(tree, filter_4, mode='same') > 0) * (tree == 0)
print('mask_candidate\n{}'.format(mask_candidate))

#その数（＝遺伝子座の数）
para_num = np.sum(mask_candidate)
print('para_num\n{}'.format(para_num))

#その数だけランダムな遺伝子を用意する
para_random = nr.randint(0, 2, para_num)
print('para_random\n{}'.format(para_random))

#ペナルティを表示
print('penalty\n{}'.format(score(para_random)))
mask_candidate
[[False  True False  True False]
 [ True False  True False  True]
 [ True  True False  True False]
 [False False  True False  True]
 [ True  True False  True False]]
para_num
13
para_random
[0 0 1 1 0 0 1 0 1 0 0 0 1]
penalty
15

遺伝子座は13個で、ランダムな遺伝子（para）を評価関数に入れてみると、ペナルティ15が返ってきました。

GAで最適化

離散的なGAができる vcopt().dcGA() を用います。para_range は各遺伝子が取り得る [0, 1] という選択肢が13個並んだ２次元配列です。評価関数はペナルティを返すため、評価値０を目指します。

#===============================================
# GA
#===============================================
#para_range
para_range = [[i for i in range(2)] for j in range(para_num)]
print('para_range\n{}'.format(para_range))

#GA
para, score = vcopt().dcGA(para_range,              #パラメータ範囲
                           score,                   #評価関数
                           0,                       #目標値
                           show_pool_func='print')  #表示オプション

#GA後のテント配列
tent[mask_candidate] = para
print('tent\n{}'.format(tent))
para_range
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]
___________________ info ___________________
para_range : n=13
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 130
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 130/130        
gen=0, best_score=3.0, mean_score=15.6385, mean_gap=15.6385, time=0.0
gen=130, best_score=3.0, mean_score=12.4154, mean_gap=12.4154, time=0.1
gen=260, best_score=3.0, mean_score=9.8231, mean_gap=9.8231, time=0.1
gen=390, best_score=3.0, mean_score=8.1615, mean_gap=8.1615, time=0.1
gen=520, best_score=3.0, mean_score=6.8, mean_gap=6.8, time=0.2
gen=650, best_score=3.0, mean_score=5.6615, mean_gap=5.6615, time=0.2
gen=780, best_score=0.0, mean_score=4.8077, mean_gap=4.8077, time=0.3
__________________ results _________________
para : [0 1 1 0 0 0 0 0 1 1 1 0 0]
score : 0.0
____________________ end ___________________
tent
[[0 0 0 1 0]
 [1 0 0 0 0]
 [0 0 0 0 0]
 [0 0 1 0 1]
 [1 0 0 0 0]]

あっという間にペナルティ０になりました。解答と一致したでしょうか？

10*10の問題

次の問題です。

#============================
# パズル
#============================
pazzle = ['-t------t-',
          't----t----',
          '--------t-',
          '-tt-------',
          '----------',
          '-t---t----',
          'tt--t-t--t',
          '-----t----',
          't-------t-',
          '---t---t-t']
horizontal = [4,1,2,1,3,1,3,0,2,3]
vertical = [3,0,2,2,0,5,0,4,0,4]
___________________ info ___________________
para_range : n=47
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 470
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 470/470        
gen=0, best_score=31.0, mean_score=54.3681, mean_gap=54.3681, time=0.1
gen=470, best_score=29.0, mean_score=48.4021, mean_gap=48.4021, time=0.4
...
gen=9400, best_score=2.0, mean_score=5.6234, mean_gap=5.6234, time=3.1
gen=9870, best_score=0.0, mean_score=4.9298, mean_gap=4.9298, time=3.3
__________________ results _________________
para : [1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0
 0 0 0 0 0 1 0 1 1 1]
score : 0.0
____________________ end ___________________
tent
[[1 0 1 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 1]
 [1 0 0 1 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [1 0 1 0 1 0 1 0 0 1]
 [0 0 0 0 0 0 0 0 0 0]
 [0 1 0 0 1 0 1 0 1 0]
 [0 0 0 0 0 0 0 0 0 0]
 [1 0 0 0 1 0 1 0 1 0]]

3.3秒で解けました。

18*18の問題

大きなサイズに挑戦します。

#============================
# パズル
#============================
pazzle = ['---tt-----t-------',
          't-------tt---t--t-',
          't-----------t-t---',
          '-----t---t--------',
          '--t-t--------tt---',
          '-----t----------t-',
          '--t--t----t--t---t',
          '------t-t-t-----t-',
          '-tt---t-----t-----',
          '---t----t--t--t---',
          '---------t------t-',
          '------t--t------t-',
          '-t------------t---',
          '--t-t---t-----t---',
          '-----------t------',
          '---tt--t---------t',
          't-----------t-----',
          '----t-tt-t---tt-t-']
horizontal = [3,4,2,5,2,6,2,2,6,2,4,3,3,4,1,5,2,5]
vertical = [5,3,4,2,4,3,4,3,4,2,5,0,6,1,2,5,0,8]

___________________ info ___________________
para_range : n=159
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 1590
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1590/1590        
gen=0, best_score=119.0, mean_score=161.6346, mean_gap=161.6346, time=1.3
gen=1590, best_score=112.0, mean_score=149.8025, mean_gap=149.8025, time=2.4
...
gen=151050, best_score=2.0, mean_score=2.073, mean_gap=2.073, time=98.1
gen=152640, best_score=0.0, mean_score=2.0415, mean_gap=2.0415, time=98.9
__________________ results _________________
para : [1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1
 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1
 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0
 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0
 0 0 0 1 1 1 1 1 1 1 1]
score : 0.0
____________________ end ___________________
tent
[[1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1]
 [0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0]
 [0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0]
 [0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1]
 [0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1]
 [0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0]
 [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
 [0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1]]

99秒で解けました。これくらいのサイズだと成功率が低いので、pool_numオプションで個体数を増やしても良いかもしれません。

まとめ

GAはざっくり解法なので、論理的なパズルは苦手な傾向があります。実は数独もやってみたのですが非常に相性が悪かったです。GAでなくて、素直に論理的なプログラムを書いたほうが良いです。

SNS等でお気軽にご連絡ください

※当ブログに関することは何でもご相談・ご依頼可能です（Servicesになくても）
※TwitterはFF外の場合はDMではなく返信orメンションでお願いしますm(_ _)m

情報発信しています

Twitterを見る
Youtubeを見る

質問・コメントはSlackやDiscordでお気軽に

Slack「AI FASHION」に参加

勉強会の告知はこちらで

connpass「AI FASHION」
GA / vcopt
vcopt パズル 最適化
この記事を書いた人

博士（理学）。専門は免疫細胞、数理モデル、シミュレーション。米国、中国で研究に携わった。遺伝的アルゴリズム信者。物価上昇のため半額弁当とともに絶滅寸前。

この記事をシェアする
Yasuda
Vignette & Clarity（ビネット＆クラリティ）
タイトルとURLをコピーしました