9-24. 遺伝的アルゴリズム（vcopt）でラテ欄の縦読みを作ってみた

GA / vcopt

2021/02/24

やること
使用したもの
実行環境
pipインストール
ポケモン名の読み込み
評価関数
GAで最適化（その１）
GAで最適化（その２）
GAで最適化（その３）
まとめ

やること

新聞のラテ欄の縦読みはご存知でしょうか。若い方は新聞は取らないでしょうし、「テレビも無ェ、ラジオも無ェ」な生活だと思いますので「ラテ欄とは？」な状況かもしれません。

TBS系列各局のラテ欄タテ読みまとめ

更新日:5月21日10時41分

縦読みは組合せ最適化問題ですので、遺伝的アルゴリズムで作れると思います。詳しい説明はナシでどんどんやってみましょう。

使用したもの

ポケモンデータ

vcoptでポケモン「いろは歌」できるかな（世界初）でもお世話になったポケモンのcsvを使わせていただきます。※第8世代版が公開されていることに気が付かず今回は第7世代版でやっています…

前処理

ポケモン名の中の改行、スペースを取り除き、アルファベットは全角と半角が入り混じっているので全角に統一しました。処理後のcsvをこちらに置いておきます。

pokemon_status_3 ダウンロード

実行環境

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

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net

Portable Scientific Python 2/3 32/64bit Distribution for Windows

Google Colaboratoryが利用可能です。

Google Colab

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

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

pipインストール

vcoptをインストールします。

pip install vcopt

ポケモン名の読み込み

最近、pd.read_csv() を使うとcsvファイルが簡単に読み込めることに気が付きました。

import numpy as np
import pandas as pd
from copy import deepcopy
from vcopt import vcopt

#完成したい文字列
tateyomi_aim = 'フウフエンマン'

#完成したい文字列バラバラに格納
tateyomi_aim = np.array(list(tateyomi_aim))
#データ読み込み
data = pd.read_csv('pokemon_status_3.csv', encoding='shift-jis')
#ポケモン名だけ抽出
data = np.array(data['ポケモン名'])

print('ポケモンの数:{}'.format(len(data)))
print('最初の４匹:{}'.format(data[:4]))

ポケモンの数:909
最初の４匹:['フシギダネ' 'フシギソウ' 'フシギバナ' 'メガフシギバナ']

評価関数

paraを受け取り、次のように処理していきます。

paraをポケモン名に変換
ポケモン名を「▽」で繋ぐ
「#」を追加して文字列を10の倍数にする
一行が10字になるように成形
一列目の文字列を抽出
目標の文章と比べる

目標の文章と比べて先頭から連続して一致している数をスコアとして返します。

#評価関数
def tateyomi_score(para, show=False):
    #paraのポケモンを抽出
    names = data[para]
    
    #▽で結合して文章に
    sentence = '▽'.join(names)
    
    #文章を10の倍数文字に調整
    while len(sentence) % 10 != 0:
        sentence += '#'
    
    #幅10文字に成形
    reshaped = np.array(list(sentence)).reshape(-1, 10)
    
    #縦読みを抽出
    tateyomi = reshaped[:, 0]
    
    #手前から連続で目標と一致している数をスコアとする
    l = min(len(tateyomi), len(tateyomi_aim))
    match = (tateyomi[:l] == tateyomi_aim[:l])
    try:
        score = np.where(match==False)[0][0]
    except:
        score = l
    
    #表示オプション
    if show:
        for i in range(l):
            print(''.join(reshaped[i]))
    
    return score
    
#最初の10匹で確認
para = np.arange(10)
print(tateyomi_score(para, True))

フシギダネ▽フシギソ
ウ▽フシギバナ▽メガ
フシギバナ▽ヒトカゲ
▽リザード▽リザード
ン▽メガリザードンX
▽メガリザードンY▽
ゼニガメ######
3

目標を「フウフエンマン」としていたので「フウフ」まで一致で３点でした。５字目の「ン」も一致していますが、先頭から連続で一致している数がスコアとなります。

GAで最適化（その１）

次の文章で試してみましょう。

tateyomi_aim = 'ビネクラノサイテキカハスゴイ'

パラメータ数は縦読みの文字数×２としました。１行にポケモンが２匹入るくらいの計算ですが多い分には問題ありません。また今回の問題は評価値の離散性が非常に高いため、個体数を次元数の200倍まで増やしました（通常は次元数の10倍）。

#パラメータ範囲
poke_num = len(tateyomi_aim) * 2
para_range = [[i for i in range(0, len(data))] for j in range(poke_num)]

#GAで最適化
para, score = vcopt().dcGA(para_range,               #para_range
                           tateyomi_score,           #評価関数
                           len(tateyomi_aim),        #評価目標値
                           show_pool_func='print',   #表示オプション
                           pool_num=poke_num*200)    #個体数を次元の200倍（通常は10倍）
#結果の表示
tateyomi_score(para, True)

________________________________________ info ________________________________________
para_range     : n=28
score_func     : <class 'function'>
aim            : ==14.0
show_pool_func : 'print'
seed           : None
pool_num       : 5600
max_gen        : None
core_num       : 1 (*vcopt, vc-grendel)
_______________________________________ start ________________________________________
Scoring first gen 5600/5600        
gen=       0, best_score=   1.000, mean_score=   0.011, mean_gap=  13.989, time=   1.7
gen=    5600, best_score=   1.000, mean_score=   0.021, mean_gap=  13.979, time=   2.9
gen=   11200, best_score=   1.000, mean_score=   0.042, mean_gap=  13.958, time=   4.2
gen=   16800, best_score=   1.000, mean_score=   0.082, mean_gap=  13.918, time=   5.5
・
・
・
gen=  509600, best_score=  13.000, mean_score=  10.133, mean_gap=   3.867, time= 110.8
gen=  515200, best_score=  13.000, mean_score=  10.201, mean_gap=   3.799, time= 112.0
gen=  520800, best_score=  13.000, mean_score=  10.287, mean_gap=   3.713, time= 113.2
gen=  526400, best_score=  14.000, mean_score=  10.408, mean_gap=   3.592, time= 114.4
_______________________________________ result _______________________________________
para = np.array([378, 242, 90, 693, 267, 328, 338, 360, 37, 440, 282, 903, 713, 49, 243, 668, 303, 311, 767, 19, 513, 271, 622, 437, 712, 348, 399, 249])
score = 14.0
________________________________________ end _________________________________________
ビブラーバ▽メガハガ
ネール▽ドククラゲ▽
クマシュン▽キングド
ラ▽キノガッサ▽マク
ノシタ▽バルビート▽
サンドパン▽ゲンシカ
イオーガ▽スイクン▽
テッカグヤ▽モノズ▽
キュウコン▽ブルー▽
カブルモ▽グラエナ▽
ハスボー▽ニャオニク
ス♀▽メガスピアー▽
ゴンベ▽オドシシ▽ホ
イーガ▽ラティオス▽

できていますね！ただこの設計では「意図しない収束」によって後半は多様性が失われた状態から探索開始になるため、文章が長くなるほど苦しくなりそうです。

夏目漱石の少し長い文章でも試してみましょう。

tateyomi_aim = 'ワガハイハネコデアル▽ナマエハマダナイ'

_______________________________________ result _______________________________________
para = np.array([295, 418, 711, 366, 620, 257, 665, 451, 0, 437, 531, 664, 63, 603, 522, 196, 29, 68, 315, 498, 613, 174, 368, 313, 420, 339, 757, 71, 897, 450, 324, 80, 370, 879, 694, 862, 903, 708])
score = 19.0
________________________________________ end _________________________________________
ワカシャモ▽トドゼル
ガ▽クイタラン▽サメ
ハダー▽ハハコモリ▽
イノムー▽シキジカ▽
ハヤシガメ▽フシギダ
ネ▽ラティオス▽ジバ
コイル▽バイバニラ▽
ディグダ:A▽ギガイ
アス▽ドクロッグ▽ヨ
ルノズク▽オニドリル
▽ペルシアン▽コノハ
ナ▽ブニャット▽オタ
マロ▽フリーザー▽ホ
エルコ▽ルンパッパ▽
ハンテール▽ハリテヤ
マ▽フラエッテ▽ゴル
ダック▽ソルガレオ▽
ナエトル▽メガサーナ
イト▽ユンゲラー▽ド

最適化の挙動を見ると、もうかなりギリギリの感じを受けます。

ラテ欄風の画像も置いておきますね。

GAで最適化（その２）

より長い縦読みを想定し、手前から順次最適化する多段階GAに変更します。ポケモンは６匹ずつ探索し、１匹だけを確定させて次のステップに移ります。６匹＝約３行分です。このあたりのテクニックはスーパーマリオの勉強会でも説明しました。

#確定遺伝子
para_fix = np.array([], int)
miss = 0

#ステップを繰り返し
for step in range(1, len(tateyomi_aim)*2 + 1):
    print('=== step {} ==='.format(step))

    #パラメータ範囲
    para_range = []
    for i in range(len(para_fix)):
        para_range.append([para_fix[i]]) #確定分は選択肢が一つだけ
    for i in range(6):
        para_range.append([j for j in range(0, len(data))]) #6体ずつ探索
    
    #GAで最適化
    para, score = vcopt().dcGA(para_range,            #para_range
                               tateyomi_score,        #評価関数
                               len(tateyomi_aim),     #評価目標値
                               show_pool_func=None,   #表示オプション
                               pool_num=6*200)        #個体数を次元の200倍
    
    #1体を確定遺伝子に加える
    para_fix = deepcopy(para[:step])
    #print(para_fix)
    
    #このステップの結果の表示
    tateyomi_score(para_fix, True)

=== step 1 ===
ワカシャモ#####
=== step 2 ===
ワカシャモ▽プロトー
ガ#########
=== step 3 ===
ワカシャモ▽プロトー
ガ▽ライチュウ###
=== step 4 ===
ワカシャモ▽プロトー
ガ▽ライチュウ▽ウソ
ハチ########
・
・
・
=== step 38 ===
ワカシャモ▽プロトー
ガ▽ライチュウ▽ウソ
ハチ▽アブリボン▽ス
イクン▽バクフーン▽
ハリマロン▽フシギダ
ネ▽キバゴ▽チョロネ
コ▽トルネロス霊獣▽
デンチュラ▽グレイシ
ア▽ヒポポタス▽ジガ
ルデ50%▽ラブカス
▽ルナアーラ▽マギア
ナ▽アルセウス▽イト
マル▽ルナトーン▽ホ
エルコ▽カイリュー▽
ハリーセン▽ビリリダ
マ▽コンパン▽サメハ
ダー▽セレビィ▽マイ
ナン▽ソルロック▽ラ
イチュウ:A▽マグカ

さっきとは違うポケモンたちで成立しました。この方法であれば無限に長い縦読みに対応できます。使用実績の少ない文字があると一定確率で失敗することもあるので、その場合は個体数を増やして踏ん張ってください。

GAで最適化（その３）

一列目ではなく５列目に縦読みを揃えてみましょう。評価関数中の一箇所を修正するだけでOKです。

太宰治でやってみましょう。

tateyomi_aim = 'メロスハゲキドシタ▽カナラズカノジャチ'

=== step 38 ===
ハヤシガメ▽ベイリー
フ▽ギャロップ▽メガ
ギャラドス▽マーイー
カ▽サメハダー▽バイ
バニラ▽ゲンシグラー
ドン▽ユキワラシ▽メ
ガボスゴドラ▽コラッ
タ:A▽シルヴァディ
▽イベルタル▽ペルシ
アン:A▽ヒヒダルマ
N▽モウカザル▽サン
ダース▽ナゾノクサ▽
メガプテラ▽マンタイ
ン▽モノズ▽ヌマクロ
ー▽マラカッチ▽ジラ
ーチ▽オノンド▽バル
チャイ▽ジュカイン▽
バケッチャ特大▽スト
ライク▽チルット▽ブ

完璧です。ラテ欄風の画像も置いておきます。