LoginSignup
7
7

More than 1 year has passed since last update.

数理最適化Advent Calendar 2022Day 8
@oddgai

DEAP×Streamlitで遺伝的アルゴリズムのアプリを作ってみた

Last updated at Posted at 2022-12-07

進化計算ライブラリDEAPとPythonのWEBフレームワークStreamlitを使って、文字列を入力すると遺伝的アルゴリズムでゼロからその文字列を当ててくれるアプリを作りました。

数理最適化の理論的な話をしたり、ゴリゴリ実装するような記事ではないので、ぜひライトな気持ちで読んでいただけると嬉しいです。

作ったもの

imageonline-gifspeed-1570116.gif
アプリへのリンクとソースコードはそれぞれこちらです（アプリはスリープしてる可能性があるので、アクセス後に少し待ってみてください）。

ソースコードを見ていただけるとわかりますが、アルゴリズムや画面の実装などがすべてPythonで完結し、100行以内に収まっています。
DEAPはちょっとした最適化アルゴリズム実装に、Streamlitはプロトタイプ作成＆公開にとても便利で、どちらも比較的気軽に試せるものなので、興味のある方はぜひ触ってみてください。特にStreamlitは、これを読んでいる方とは相性が良いものな気がしています。

遺伝的アルゴリズムの実装

遺伝的アルゴリズムとは

遺伝的アルゴリズム（Genetic Algorithm, GA）の詳細については、いろんな書籍やサイトで解説されているので省略します。
簡単にいうと、生物が交配や突然変異を繰り返して進化しているのと同じように、複数の解を混ぜたり、たまに別の解に変化させることを繰り返して良い解を探そうという最適化手法です。
生物の進化にヒントを得て研究されている「進化的アルゴリズム」の中では、最もポピュラーな手法の一つだと思います。

書籍だとこのあたりに詳しく書いてありました。

また、解説ではありませんがこういう動画もありました。寝る前にずっと観ちゃうやつですね。

問題の定式化

実装の説明をする前に、アプリ内で解いている問題をちゃんと定義します。
今回は「すべての文字の順列の中から、入力した文字列（正解文字列）を当てる」という問題を解きたいので、以下のように定式化しました。

  • 目的関数（最大化）
    • 正解文字列と、解の文字列の一致度
  • 制約条件
    • 解の文字列の長さ＝正解文字列の長さ
    • 解の文字列は、事前に与えられた文字リスト内の文字によって構成される
      • 今回は「半角記号、英数字、ひらがな、カタカナ、常用・人名用漢字」に限定しています

目的関数の「2つの文字列の一致度」にはいくつかの考え方がありますが、今回は以下のように「同じ位置の文字がどのくらいが一致しているか」で計算しました。

# 2つの文字列の一致度
def obj_func(x, target_code):
	match = [i == j for i, j in zip(x, target_code)]
	obj = sum(match) / len(match)
	return obj,  # DEAPで使うときはreturnの後に,をつける必要があるらしい

また、準備として以下の変数と関数を定義しておきます。

  • 正解文字列をord()でUnicode値に変換したもの
  • 正解文字列の長さ
  • ランダムなUnicode値を返す関数
# 答えを文字コードに変換
# target_string = "数理最適化はいいぞ"
target_code = [ord(s) for s in target_string]
size = len(target_code)

### 常用漢字、人名用漢字のリストを読み込む
kanji_list = np.loadtxt("src/kanji_list.txt", dtype=object, delimiter=" ")
kanji_unicode_list = [ord(s) for s in kanji_list]

def random_character_code():
	'''ランダムな文字列のUnicode値を返す'''
	# 半角記号、英数字、ひらがな、カタカナ、だいたいの漢字
	char_code = list(range(32, 126)) + list(range(12289, 12541)) + kanji_unicode_list
	return random.choice(char_code)

DEAPによるGAの実装

さて、問題が定義できたのでDEAPを使ったGAの実装に入ります。

DEAPでは、以下のような流れで簡単にGAを実装できます。

  1. 評価関数や個体のクラス定義
  2. 交叉や淘汰の方法、突然変異確率などのパラメータ設定
  3. forループによる解の探索

順に説明していきます。

まず、評価関数や個体のクラスを定義します。評価関数のweightsは最大化問題だと(1.0,)、最小化問題だと(-1.0,)になるようです。
今回は最大化問題なのでweights=(1.0,)とします。また、個体の型をlistとして定義します。

from deap import algorithms, base, creator, tools

# 評価関数と個体のクラスを定義
creator.create(name="TransformCharacter", base=base.Fitness, weights=(1.0,))  # 最大化問題なので(1.0,)
creator.create(name="Individual", base=list, fitness=creator.TransformCharacter)  # 個体Individualをlistとして定義

次に、交叉や淘汰（選択）の方法、突然変異確率などのパラメータ設定をします。今回は以下のような設定にしました。

  • 選択：トーナメント方式（k=5）
    • ランダムにトーナメントを作って、評価関数で勝負して残ったk組を次世代の親とする
  • 交叉：二点交叉
  • 遺伝子の突然変異確率：0.6
    • 本当はもっと小さい値が適切だと思いますが、いろんな文字列を作って画面上での見栄えが良くなるように確率を高くしてます

詳細な説明は公式ドキュメントに譲りますが、選択方式や交叉関数、突然変異などは関数が用意されているので、凝ったことをしなければ以下のように簡単に実装できます。

### 各種設定
toolbox = base.Toolbox()

# 遺伝子g: Unicode値
toolbox.register("g", random_character_code)

# 各個体x: gをsize回くり返したlist
toolbox.register("x", tools.initRepeat, creator.Individual, toolbox.g, n=size)

# 1世代の集団
toolbox.register("population", tools.initRepeat, list, toolbox.x)

# 選択方式: トーナメント方式
toolbox.register("select", tools.selTournament, tournsize=5)

# 交叉関数: 二点交叉
toolbox.register("mate", tools.cxTwoPoint)

# 突然変異関数（indpb: 遺伝子の突然変異率）
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.6)

# 目的関数である文字列の一致度をそのまま評価関数とする
toolbox.register("evaluate", obj_func, target_code)

最後に、forループによって解を探索します。ここでも世代の更新や評価関数の計算には関数が用意されているので、単純なものであれば下のようにコンパクトに書けます。
今回は世代数を100に固定していて、第100世代までに正解文字列が見つかればOK、見つからなかったらそのまま終了としています（なので、30文字くらいの長い文字列を入れるとそこそこ失敗します）。

# パラメータ
NGEN = 100  # 世代数
POP = 10000  # 1世代内の個体数
CX_PB = 0.5  # 交叉確率
MUT_PB = 0.6  # 個体の突然変異確率

### GA実行
# 最初の世代
population = toolbox.population(n=POP)
for gen in range(NGEN):
    # 今の世代の個体から次世代の個体を生み出す
    offspring = algorithms.varAnd(population, toolbox, cxpb=CX_PB, mutpb=MUT_PB)

    # 評価関数値を計算
    fits = toolbox.map(toolbox.evaluate, offspring)
    for fit, ind in zip(fits, offspring):
        ind.fitness.values = fit

    # 世代の中で最も評価関数が高い個体
    best_ind = tools.selBest(population, 1)[0]
    best_ind_char = "".join([chr(i) for i in best_ind])  # Unicode値を文字に変換

    # 暫定解を表示
    if best_ind.fitness.values:
        print(best_ind_char)  # 暫定解
        print(best_ind.fitness.values[0])  # 目的関数値

    #  評価関数が1（答えに一致）になったら終了
    if best_ind.fitness.values == (1,):
        result = 1
        break
    # 一致しなかったら淘汰しつつ次の世代へ
    else:
        population = toolbox.select(offspring, k=len(population))

以上がアルゴリズム部分の実装になります。もっと詳細な使い方を知りたい方は公式のExample集を見てみてください。

画面の実装

次に、画面部分の実装について説明します。最初にも書いている通り、画面はStreamlitというフレームワークを使っています。簡単なPythonコードだけでサクッといい感じの画面が作れて公開も簡単にできるので、「作ったAPIの動作や分析したデータを画面で見せたいけど、HTMLとかJavaScript書くのはちょっと面倒だな」みたいなときにとても便利です。特定の人だけに公開するのもできるようなので、社内向けプロトタイプなどにも使えそうです。

正直、公式のギャラリー集やドキュメントが非常に充実しているので、それを読んでもらうのが良いのですが、今回の実装について簡単に説明します。

まず、正解文字列の入力フォームと「探索スタート」のボタンを作ります。
これはとても簡単で、下のように書くと

import streamlit as st

st.title("遺伝的アルゴリズムで答えを探します")
target_string = st.text_input("答えを教えてね（2文字以上）")
start_btn = st.button("探索スタート")

このような画面ができます。
スクリーンショット 2022-12-07 4.22.24.png
フォームに入力された文字列は変数（上でいうとtarget_string）に格納されるので、画面側とロジック部分の接続もシームレスです（「もっとしっかり分離したい」と思う人もいるかもしれませんが）。

また「ボタンが押されたら処理を実行する」という動作は以下のようなコードで実現できます。この部分もちゃんとアプリを作ったことがある人は気持ち悪さを感じるかもしれませんが、個人的には単純で良いと思っています。

if start_btn:
    # 処理
    # ...

次に、暫定の目的関数値を表すプログレスバーと暫定解、「探索中」や「正解しました！」などの表示は下のように書いています（GAに関する処理は省略します）。

# 目的関数値と暫定解の初期化
current_string = st.empty()
current_fitness = st.empty()
search_progress_bar = st.progress(0)

if start_btn:
    with st.spinner("探索中・・・"):
        # ...
        # GAのforループ
        for gen in range(NGEN):
            best_ind_char = "".join([chr(i) for i in best_ind])
            
            # 暫定解を表示
			if best_ind.fitness.values:
				current_string.write(f"### {best_ind_char}")
				current_fitness.caption(f"正解率: {np.int8(best_ind.fitness.values[0] * 100)} %")
				search_progress_bar.progress(best_ind.fitness.values[0])
            
            # 答えに一致したら表示
			if best_ind.fitness.values == (1,):
				result = 1
				break
            else:
				population = toolbox.select(offspring, k=len(population))

    if result == 1:
		st.success("正解しました！ほめてください！")
	else:
		st.error("だめでした・・・次回にご期待ください！")

まず、暫定解の情報を表すcurrent_string, current_fitnessなどの変数をst.empty()で初期化しておき、後から更新できるようにしておきます。プログレスバーsearch_progress_barもst.progress(0)として0%で初期化します。

また、ボタンが押されてから探索終了までの間だけ「探索中」という表示を出すために、下のように書いています。

with st.spinner("探索中・・・"):
    # 処理

そして、探索の中で暫定解を表示するために、先ほど初期化した変数とプログレスバーを更新します。

current_string.write(f"### {best_ind_char}")
current_fitness.caption(f"正解率: {np.int8(best_ind.fitness.values[0] * 100)} %")
search_progress_bar.progress(best_ind.fitness.values[0])

どちらの更新も簡単で、変数の更新にはwrite()とcaption()などが使えます。write()は単純なテキストだけでなくマークダウン記法が使えるので、write(f"# {text}")のように書くことで文字の大きさを変えることができます。caption()はwrite()よりも文字が小さくなって色も灰色になるので、そこまで目立たせたくないテキストに使えます。
プログレスバーの更新はprogress()でできます。

最後に、下のように書くことで、成功時と失敗時でメッセージを出し分けています。

if result == 1:
    st.success("正解しました！ほめてください！")
else:
    st.error("だめでした・・・次回にご期待ください！")

以上が画面部分の実装でした。まとめると、今回のような単純なものであれば、20行くらいのコードでリッチな画面が作れてしまいます。
再掲しますが、公式のギャラリー集にはいろんなサンプルがあり、眺めるだけでもおもしろいので、興味をもった方はぜひ見てみてください。

アプリの公開

Streamlitでは、Streamlit Cloudというプラットフォームによって簡単にアプリを公開できます。ざっくりいうと、以下のたったの3 Stepで公開できてしまいます。

  1. ソースコードをGitHubにPush
    1. その際に、必要なパッケージをまとめたrequirements.txtやPipfileなどを置く
  2. Streamlit CloudとGitHubを連携する
  3. Streamlit Cloudの画面から、アプリのリポジトリとファイルを指定する

また、デプロイ時に以下のような設定もできるので、プロトタイプを社内のみに公開したいときにも使えそうです（実際に使うときは所属のポリシーに従う必要がありますが）。

  • 完全にパブリックにはせず、Emailで共有相手を招待する
  • アクセスキーなどの認証情報は環境変数として外部には見えない形で設定できる（GitHubと切り離せる）

他にもURLを指定できたり、アクセス数をモニタリングできるなどの機能があります。これらも含め、詳細は公式ドキュメントを参照してください。

さいごに

今回は、進化計算ライブラリDEAPとWEBフレームワークStreamlitを使って、遺伝的アルゴリズムのデモアプリを作ってみました。少しでも興味をもっていただけていれば嬉しいです。

学生時代に数理最適化を専攻してたものの、業務ではなかなか触る機会がないので、欲望を発散する良い機会になりました。
本当はPython-MIPを使ってもっと本格的なWEBアプリを作る予定だったのですが、パルデア地方の探索に思ったより時間がかかっているため、少し前に作ったものの紹介をしました。探索が落ち着いたらちゃんと時間を確保して取り掛かりたいです。

7
7
0

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
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
7