こんにちは、せしょうです。
今回は「面白アルゴリズム 」ということで、遺伝的アルゴリズム(GA: Genetic Algorithm)について紹介したいと思います。
アルゴリズムの中には、 生物の進化の仕組みや習性などを模したようなアルゴリズムが存在します。
GAは、上記で言うところの生物の進化の仕組みを模したアルゴリズムです。
今回は紹介と言うことで、去年(2022年)に流行ったWordle(っぽいもの)を題材に、GAを使って最良解を求めていこうと思います。
目次
遺伝的アルゴリズム(GA)とは?
GAの何が面白いの?何が凄いの?
今回使用する題材「Wordle」の簡単な説明
今回の目的:「Wordleっぽいもの」の最良解を導出するぞ
GAの大きな3つのフェーズ
交叉
突然変異
自然淘汰
結果
まとめ
おまけ(GA実装部分のコード)
遺伝的アルゴリズム(GA)とは?
GAの何が面白いの?何が凄いの?
今回使用する題材「Wordle」の簡単な説明
今回の目的:「Wordleっぽいもの」の最良解を導出するぞ
GAの大きな3つのフェーズ
交叉
突然変異
自然淘汰
結果
まとめ
おまけ(GA実装部分のコード)
遺伝的アルゴリズム(GA)とは?
遺伝的アルゴリズム(GA:Genetic Algorithm)は、1975年にJohn Henry Hollandによって提案された 生物進化(自然淘汰、交叉、突然変異)の現象を、模倣した確率的探索・最適化などを行うための一手法です。
GAは、個体と呼ばれる染色体(解候補)の集合が外部環境(評価関数)に適応するために、遺伝子操作を行い世代ごとにその染色体を生成することによって、最良解を求めることに使用されます。
生物の遺伝操作を、GAでは以下のようにとらえることが出来ます。
自然淘汰
環境への適合度の高い個体ほど生存確率が高く、適合度が低いほど生存確率が低い
交叉
2つの親個体の遺伝子を元に、新しい個体(子個体)を作成する操作(生殖)
突然変異
親個体の遺伝子に対して、一部の遺伝子を変換する操作
生物は、現在までに環境に適応できるように 「自然淘汰」、「交叉」、「突然変異」の遺伝子操作を繰り返して進化してきました。
GAはこの生物の’’環境への適応’’を ‘’最良解の導出’’に応用した手法なのです。
自然淘汰
環境への適合度の高い個体ほど生存確率が高く、適合度が低いほど生存確率が低い
交叉
2つの親個体の遺伝子を元に、新しい個体(子個体)を作成する操作(生殖)
突然変異
親個体の遺伝子に対して、一部の遺伝子を変換する操作
GAの何が面白いの?何が凄いの?
私がGAって面白い・凄いと感じた個所が2点ほどあります。
生物の進化の過程をアルゴリズム化したということ
人(PC)含め、計算量が大変な問題に対して 最良解(<=正解)を導いてくれる。
1. については、そもそも生物の進化(環境への適応)を模倣したという発想が、既に面白いし凄いですよね。どうしたら、生物の進化をアルゴリズムに変換しよう! となるんでしょうか。
私は生物専攻というわけではありませんが、 今現代に生きている生物は過酷な環境を生き抜くために進化を繰り返して 現在の環境に適応している生物ばかりだと思います。
そう考えると、そんな成功例のある 生物の進化を模倣すれば 上手くいくだろうというのは感覚的に みなさんも分かると思うのですが これが本当に上手く最良解を導いてくれるんですよね。
ただし、正しく最良解を導いてくれるには、その外部環境(評価関数)だったり、交叉方法や自然淘汰(選択)の方法が重要だったりします。 その手法も 過去 いくつも提案されているため、色々と調べていても楽しいです。
2. について
例えば、みなさん今 サイ〇リヤにいて、手元に 10,000円あったとします。
このとき、10,000円以内で 一番カロリーが高くなる組み合わせを答えなさい。と言ったような問題があったとします。
この問題は、いわゆるナップザック問題と呼ばれます。この問題は、原理的に考えると全ての通り数を列挙すれば答えが見つかります。
しかしながら、正直 これを計算するには骨が折れます。サイ〇リヤの商品が例えば、30種類あった場合 単純に商品を重複しないという条件をつけたとしても、その組み合わせ数は2^30=1,073,741,824 通りあります。
ちなみに、2.7 * 10^32解の演算を行おうとすると 10年以上前のスパコンにはなりますが、約100億年かかると言われてました。 マジスカ──Σ(∀゚ノ)ノ──ッ!?
その問題に対して、GA君は正解でないにしろ、その正解に近い最良解を 100億年経たずとも導出することができるとても優秀な子なのです。凄い!!
大きくこの2点が私がGA君を面白い・凄いと感じた部分なのですが、伝わりましたでしょうか?
そんな面白くて、優秀なGA君には、今回「Wordleっぽいもの」の最適解を求めてもらおうと思います!
GA君 よろしくお願いします。_(._.)_
生物の進化の過程をアルゴリズム化したということ
人(PC)含め、計算量が大変な問題に対して 最良解(<=正解)を導いてくれる。
今回使用する題材「Wordle」の簡単な説明
今回題材としたWordleは、 お題となる単語を推理していくクイズゲームです。
Wordleのルールとしては、以下のようなものがあります。
6ターン以内に、お題となっている英単語を当てる
お題の単語は5文字
答えと同じ位置に該当のアルファベットがあると、〇色にしてプレイヤーに伝えてくれる
答えと異なる位置に該当のアルファベットがあると、✖色にしてプレイヤーに伝えてくれる
6ターン以内に、お題となっている英単語を当てる
お題の単語は5文字
答えと同じ位置に該当のアルファベットがあると、〇色にしてプレイヤーに伝えてくれる
答えと異なる位置に該当のアルファベットがあると、✖色にしてプレイヤーに伝えてくれる
今回の目的:「Wordleっぽいもの」の最良解を導出するぞ
先ほど、Wordleの説明をしましたが、今回は、紹介ということで もっと条件を緩くして以下のような条件で行います。
6ターン ⇨ 世代交代を500回 or 3000回
5文字の単語 ⇨ Gluegent
6ターン ⇨ 世代交代を500回 or 3000回
5文字の単語 ⇨ Gluegent
より細かい条件
お題となる単語: Gluegent
使用する文字列:アルファベットの大小文字
世代交代: 500回 (3000回)
遺伝子数:20個
交叉率:60%
突然変異率:20% (1%)
自然淘汰方法:ルーレット選択方式
評価(適応度の算出)
「答えと同じ位置に該当するアルファベット」と「違う位置に該当するアルファベット」の両方を評価する。
評価a:「答えと同じ位置に該当するアルファベット」と「違う位置に該当するアルファベット」の両方を評価することができる。
式で表すと以下のように書ける。
お題となる単語: Gluegent
使用する文字列:アルファベットの大小文字
世代交代: 500回 (3000回)
遺伝子数:20個
交叉率:60%
突然変異率:20% (1%)
自然淘汰方法:ルーレット選択方式
評価(適応度の算出)
「答えと同じ位置に該当するアルファベット」と「違う位置に該当するアルファベット」の両方を評価する。
図3.1 適応度の評価式の例
今回の目的は、この適合度を求める評価式を基に「Gluegent」という単語(適合度を 1)に近づけるのが目的となります。
GAの大きな3つのフェーズ
GAのフェーズには、大きく3つのフェーズがあります。
「交叉」、「突然変異」、「自然淘汰」のフェーズです。
今回の流れを図で書くと、以下のようになります。
図4.1.1 今回使用するGAの処理の流れ
交叉
交叉は、2つの親個体を元に交叉を行い、新しい個体(子個体)を作成する操作を言います。
今回は交叉の手法として、2点間交叉法を使用します。
2点間交叉法は、親となる個体の遺伝子の中から2点をランダムに選び(sp1, sp2とする)
その2点間を入れ替える操作を言います。
図4.2.1 交叉の操作
【コード】
def _cross_over(self,parent1:list, parent2:list) -> list:
"""2点交叉
2つの親個体の遺伝子を元に、新しい個体(子個体)を作成する操作
Args:
parent1 np.array: 親1
parent2 np.array: 親2
Returns:
Individual: 子1
Individual: 子2
Note:
self.target_len int: お題の単語の長さ
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
# 交叉点をランダムに取得
fp = random.randint(0, self.target_len-1)
sp = random.randint(0, self.target_len-1)
# 交叉点の小さい方をfpとする
if fp > sp:
fp, sp = sp, fp
child1 = Individual(np.array(parent1[0:fp] + parent2[fp:sp] + parent1[sp:]))
child2 = Individual(np.array(parent2[0:fp] + parent1[fp:sp] + parent2[sp:]))
return child1, child2
図4.2.1 交叉の操作
【コード】
def _cross_over(self,parent1:list, parent2:list) -> list:
"""2点交叉
2つの親個体の遺伝子を元に、新しい個体(子個体)を作成する操作
Args:
parent1 np.array: 親1
parent2 np.array: 親2
Returns:
Individual: 子1
Individual: 子2
Note:
self.target_len int: お題の単語の長さ
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
# 交叉点をランダムに取得
fp = random.randint(0, self.target_len-1)
sp = random.randint(0, self.target_len-1)
# 交叉点の小さい方をfpとする
if fp > sp:
fp, sp = sp, fp
child1 = Individual(np.array(parent1[0:fp] + parent2[fp:sp] + parent1[sp:]))
child2 = Individual(np.array(parent2[0:fp] + parent1[fp:sp] + parent2[sp:]))
return child1, child2
突然変異
突然変異は、親染色体内の遺伝子の一部を変える操作を言います。
突然変異をすることで新たな子染色体が生まれ、染色体集団の中で多様性を保持するための操作です。
図4.3.1 突然変異の操作
【コード】
def _mutation(self, parent:list) -> list:
"""突然変異
親個体の遺伝子に対して、一部の遺伝子を変換する操作
Args:
parent np.array<int>: 親
Returns:
Individual: 子
Note:
self.alphabet_unicode list<int>: 大小英文字のリスト
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
idx = random.randint(0,self.target_len-1)
parent[idx] = random.choice(self.alphabet_unicode)
child = Individual(parent)
return child
突然変異は、親染色体内の遺伝子の一部を変える操作を言います。
突然変異をすることで新たな子染色体が生まれ、染色体集団の中で多様性を保持するための操作です。
図4.3.1 突然変異の操作
【コード】
def _mutation(self, parent:list) -> list:
"""突然変異
親個体の遺伝子に対して、一部の遺伝子を変換する操作
Args:
parent np.array<int>: 親
Returns:
Individual: 子
Note:
self.alphabet_unicode list<int>: 大小英文字のリスト
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
idx = random.randint(0,self.target_len-1)
parent[idx] = random.choice(self.alphabet_unicode)
child = Individual(parent)
return child
自然淘汰
自然淘汰は、各染色体の評価関数で算出した、適合度の高さに応じて 親・子染色体を選択し、次世代の染色体集団を構成するための操作です。
今回は、自然淘汰の手法として、ルーレット選択を使用します。
ルーレット選択は、適応度が高い個体が選ばれやすいのが特徴です。以下の画像のように、適応度が高いほど選ばれる確率が高くなります。
しかし、適応度が低い個体も選択の余地に入れることで、早い段階での収束による 局所解へ陥ることを防ぐこともできます。
図4.4.1 ルーレット選択
【コード】
def _selection(self, chromesomes:list) -> list:
"""ルーレット選択
Args:
chromesome list<Individual>: 染色体(親染色体と子染色体)
Returns:
list<Individual>: ルーレット選択により、選ばれた遺伝子
Note:
self.alphabet_unicode list<int>: 大小英文字のリスト
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
fitness_arr = np.array([chromesome.fitness for chromesome in chromesomes])
try:
idx_list = np.random.choice(
np.arange(fitness_arr.shape[0]),
size=self.pop,
replace=False,
p=fitness_arr/sum(fitness_arr))
except:
idx_list = np.random.choice(
np.arange(fitness_arr.shape[0]),
size=self.pop,
replace=False,
)
return [chromesomes[idx] for idx in idx_list]
自然淘汰は、各染色体の評価関数で算出した、適合度の高さに応じて 親・子染色体を選択し、次世代の染色体集団を構成するための操作です。
今回は、自然淘汰の手法として、ルーレット選択を使用します。
ルーレット選択は、適応度が高い個体が選ばれやすいのが特徴です。以下の画像のように、適応度が高いほど選ばれる確率が高くなります。
しかし、適応度が低い個体も選択の余地に入れることで、早い段階での収束による 局所解へ陥ることを防ぐこともできます。
図4.4.1 ルーレット選択
【コード】
def _selection(self, chromesomes:list) -> list:
"""ルーレット選択
Args:
chromesome list<Individual>: 染色体(親染色体と子染色体)
Returns:
list<Individual>: ルーレット選択により、選ばれた遺伝子
Note:
self.alphabet_unicode list<int>: 大小英文字のリスト
Individual Individual: 遺伝子情報を持つクラス
gean np.array: 生成された文字列(Unicode値)
fitness double: 適応度
"""
fitness_arr = np.array([chromesome.fitness for chromesome in chromesomes])
try:
idx_list = np.random.choice(
np.arange(fitness_arr.shape[0]),
size=self.pop,
replace=False,
p=fitness_arr/sum(fitness_arr))
except:
idx_list = np.random.choice(
np.arange(fitness_arr.shape[0]),
size=self.pop,
replace=False,
)
return [chromesomes[idx] for idx in idx_list]