第一回 面白アルゴリズム紹介 (遺伝的アルゴリズム編)

 こんにちは、せしょうです。


今回は「面白アルゴリズム 」ということで、遺伝的アルゴリズム(GA: Genetic Algorithm)について紹介したいと思います。


アルゴリズムの中には、 生物の進化の仕組みや習性などを模したようなアルゴリズムが存在します。

GAは、上記で言うところの生物の進化の仕組みを模したアルゴリズムです。


　今回は紹介と言うことで、去年(2022年)に流行ったWordle(っぽいもの)を題材に、GAを使って最良解を求めていこうと思います。



目次

  1. 遺伝的アルゴリズム(GA)とは？

  2. GAの何が面白いの？何が凄いの？

  3. 今回使用する題材「Wordle」の簡単な説明

  4. 今回の目的：「Wordleっぽいもの」の最良解を導出するぞ

  5. GAの大きな３つのフェーズ

    1. 交叉

    2. 突然変異

    3. 自然淘汰

  6. 結果

  7. まとめ

  8. おまけ(GA実装部分のコード)

遺伝的アルゴリズム(GA)とは？

　遺伝的アルゴリズム(GA:Genetic Algorithm)は、1975年にJohn Henry Hollandによって提案された 生物進化(自然淘汰、交叉、突然変異)の現象を、模倣した確率的探索・最適化などを行うための一手法です。

　GAは、個体と呼ばれる染色体(解候補)の集合が外部環境(評価関数)に適応するために、遺伝子操作を行い世代ごとにその染色体を生成することによって、最良解を求めることに使用されます。

　生物の遺伝操作を、GAでは以下のようにとらえることが出来ます。

  • 自然淘汰

    • 環境への適合度の高い個体ほど生存確率が高く、適合度が低いほど生存確率が低い

  • 交叉

    • ２つの親個体の遺伝子を元に、新しい個体(子個体)を作成する操作(生殖)

  • 突然変異

    • 親個体の遺伝子に対して、一部の遺伝子を変換する操作


生物は、現在までに環境に適応できるように 「自然淘汰」、「交叉」、「突然変異」の遺伝子操作を繰り返して進化してきました。 


GAはこの生物の’’環境への適応’’を ‘’最良解の導出’’に応用した手法なのです。

GAの何が面白いの？何が凄いの？

私がGAって面白い・凄いと感じた個所が２点ほどあります。

  1. 生物の進化の過程をアルゴリズム化したということ

  2. 人(PC)含め、計算量が大変な問題に対して 最良解(<=正解)を導いてくれる。


1. については、そもそも生物の進化(環境への適応)を模倣したという発想が、既に面白いし凄いですよね。どうしたら、生物の進化をアルゴリズムに変換しよう！ となるんでしょうか。


　私は生物専攻というわけではありませんが、 今現代に生きている生物は過酷な環境を生き抜くために進化を繰り返して 現在の環境に適応している生物ばかりだと思います。

　そう考えると、そんな成功例のある 生物の進化を模倣すれば 上手くいくだろうというのは感覚的に みなさんも分かると思うのですが これが本当に上手く最良解を導いてくれるんですよね。

　ただし、正しく最良解を導いてくれるには、その外部環境(評価関数)だったり、交叉方法や自然淘汰(選択)の方法が重要だったりします。　その手法も 過去 いくつも提案されているため、色々と調べていても楽しいです。


２. について

例えば、みなさん今 サイ〇リヤにいて、手元に 10,000円あったとします。

このとき、10,000円以内で 一番カロリーが高くなる組み合わせを答えなさい。と言ったような問題があったとします。

　この問題は、いわゆるナップザック問題と呼ばれます。この問題は、原理的に考えると全ての通り数を列挙すれば答えが見つかります。

　しかしながら、正直 これを計算するには骨が折れます。サイ〇リヤの商品が例えば、30種類あった場合 単純に商品を重複しないという条件をつけたとしても、その組み合わせ数は2^30=1,073,741,824 通りあります。


　ちなみに、2.7 * 10^32解の演算を行おうとすると 10年以上前のスパコンにはなりますが、約100億年かかると言われてました。 ﾏｼﾞｽｶ──Σ(∀ﾟﾉ)ﾉ──ｯ!?


その問題に対して、GA君は正解でないにしろ、その正解に近い最良解を 100億年経たずとも導出することができるとても優秀な子なのです。凄い！！


大きくこの２点が私がGA君を面白い・凄いと感じた部分なのですが、伝わりましたでしょうか？


そんな面白くて、優秀なGA君には、今回「Wordleっぽいもの」の最適解を求めてもらおうと思います！　


GA君 よろしくお願いします。_(._.)_


今回使用する題材「Wordle」の簡単な説明

今回題材としたWordleは、 お題となる単語を推理していくクイズゲームです。

Wordleのルールとしては、以下のようなものがあります。

  • ６ターン以内に、お題となっている英単語を当てる

  • お題の単語は５文字

  • 答えと同じ位置に該当のアルファベットがあると、〇色にしてプレイヤーに伝えてくれる

  • 答えと異なる位置に該当のアルファベットがあると、✖色にしてプレイヤーに伝えてくれる

図2.1 Wordleのルール例

今回の目的：「Wordleっぽいもの」の最良解を導出するぞ

先ほど、Wordleの説明をしましたが、今回は、紹介ということで もっと条件を緩くして以下のような条件で行います。

  • ６ターン　　　　⇨  世代交代を500回 or 3000回

  • ５文字の単語　　⇨  Gluegent

より細かい条件

  1. お題となる単語： Gluegent

  2. 使用する文字列：アルファベットの大小文字

  3. 世代交代： 500回 (3000回)

  4. 遺伝子数：20個

  5. 交叉率：60%

  6. 突然変異率：20% (1%)

  7. 自然淘汰方法：ルーレット選択方式

  8. 評価(適応度の算出)

    1. 「答えと同じ位置に該当するアルファベット」と「違う位置に該当するアルファベット」の両方を評価する。

評価a：「答えと同じ位置に該当するアルファベット」と「違う位置に該当するアルファベット」の両方を評価することができる。

式で表すと以下のように書ける。

例)

図3.1 適応度の評価式の例

今回の目的は、この適合度を求める評価式を基に「Gluegent」という単語(適合度を 1)に近づけるのが目的となります。

GAの大きな３つのフェーズ

GAのフェーズには、大きく３つのフェーズがあります。

「交叉」、「突然変異」、「自然淘汰」のフェーズです。


今回の流れを図で書くと、以下のようになります。



図4.1.1 今回使用するGAの処理の流れ

交叉

交叉は、２つの親個体を元に交叉を行い、新しい個体(子個体)を作成する操作を言います。


今回は交叉の手法として、２点間交叉法を使用します。

２点間交叉法は、親となる個体の遺伝子の中から２点をランダムに選び(sp1, sp2とする)

その２点間を入れ替える操作を言います。

図4.2.1 交叉の操作

【コード】

def _cross_over(self,parent1:list, parent2:list) -> list:

        """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.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]

結果

一部抜粋

条件１） 

世代交代： 500回

遺伝子数：30個

交叉率：60%

突然変異率：20%



条件２） 

世代交代： 3000回

遺伝子数：30個

交叉率：60%

突然変異率：20%


条件３） 

世代交代： 3000回

遺伝子数：30個

交叉率：60%

突然変異率：1%

この結果から、 今回の題材で安定して最良解を求めることができていたことから、 突然変異発生率が重要だったのでは？と思われます。　

　今回使用した2点交叉は、ランダムで選んだ2点間の遺伝子を入れ替えるというものでした。今回使用した評価関数は、「生成した文字列のアルファベットの位置が答えのアルファベットと同じ位置にある」という点を重視した評価関数となってます。

　そのため、交叉による 入れ替えよりも、突然変異を何回も起こし、該当箇所のアルファベットを出現させることで、局所解にハマって抜け出せなくなるようなこともなく、安定して最良解を求められたのだと思われます。


　今回は簡単な題材でしたが、途中で 局所解にハマって抜け出せず Gluegentにまでたどり着かなかったパターンもありました。

 これをどうやって、局所解から抜け出させるかというのを考えるのも実装する際の楽しみです。

まとめ

　今回は、面白アルゴリズムと言うタイトルで、遺伝的アルゴリズム(GA:Genetic Algorithm)について、紹介させていただきました。

  最初に生成する単語はランダムなのに、 世代が増えるにつれ、右肩上がりに適合度が上昇するのは面白いですよね。こうやって、生き物は環境に適応して生き残ってきたのか...笑

　この記事を通してみなさんにも、こんなアルゴリズムがあるんだと、少しでも興味を持ってもらえたら嬉しいです。　GA君はとても優秀でした！

　

　　なお、今回は 説明のために、一部コードに起こしましたが、 pythonではGAのライブラリがあるのでシンプルな実装はすぐにお試しできます。

　また、もし興味を持ってくださった方は、巡回セールスマン問題(TSP)や配送計画 などの最適化問題等をググってみるといいかもしれません。 

　

　今後も、面白そうなアルゴリズムについて紹介していけたらと思うので、ぜひまた見ていってください！

　それでは、また次回の記事でお会いしましょう！(@^^)/~~~

(せしょう)



おまけ(GA実装部分のコード)

import numpy as np

import random


class EncoderDecoder:

    def encode(self, chr):

        return ord(chr)

   

    def decode(self, ord):

        return chr(ord)


class Individual:

    def __init__(self, gean):

        self.gean = gean

        self.fitness = 0


    def set_fitness(self, fitness):

        self.fitness = fitness


class Wordle:

    def __init__(self, target, N, pop, cp, mp):

        self.encoder_decoder = EncoderDecoder()


        self.target = target

        self.target_len = len(target)

        self.target_unicode = [self.encoder_decoder.encode(chr) for chr in self.target]

        self.N = N

        self.pop = pop

        self.cp = cp

        self.mp = mp


        self.alphabet_unicode = [i for i in range(97, 97+26)] + [i for i in range(65, 65+26)]


        self.parent = []

        self.child = []


    def _create_first_generation(self):

         for _ in range(self.pop):

            individual = Individual(np.random.choice(self.alphabet_unicode, size=self.target_len))

            self.parent.append(individual)


    def _create_parent_pair(self):

        parents1 = random.sample(self.parent[::2], k=int(self.pop/2))

        parents2 = random.sample(self.parent[1::2],k=int(self.pop/2))

        return parents1, parents2

   

    def _cross_over(self,parent1:list, parent2:list) -> list:

        """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



    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


    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]

   

    def _culc_perfect_match(self, string_unicode):

        value = 0

        for ord1, ord2 in zip(self.target_unicode, string_unicode):

            if ord1 == ord2:

                value += 1

        return value


    def _culc_same_word_match(self, string_unicode):

        value = 0

        string = [self.encoder_decoder.decode(int(ord)) for ord in string_unicode]

        for chr in [self.encoder_decoder.decode(int(ord)) for ord in self.target_unicode]:

            if chr in string:

                value += 1

                string.remove(chr)

        return value/self.target_len

   

    def _evaluate(self, chromesome):

        for individual in chromesome:

            fitness = 0

            fitness += self._culc_perfect_match(list(np.copy(individual.gean)))

            fitness += self._culc_same_word_match(list(np.copy(individual.gean)))

            fitness = fitness/(self.target_len + 1)

            individual.set_fitness(fitness)


    def _run(self):

        self._create_first_generation()

        for _ in range(self.N):

            # 交叉

            parents1, parents2 = self._create_parent_pair()

            for parent1, parent2 in zip(parents1, parents2):

                if random.random() < self.cp:

                    self.child.extend(self._cross_over(list(np.copy(parent1.gean)), list(np.copy(parent2.gean))))

            # 突然変異

            for parent in self.parent:

                if random.random() < self.mp:

                    self.child.append(self._mutation(list(np.copy(parent.gean))))

            # 評価

            self._evaluate(self.parent+self.child)

            # 自然淘汰(選択)

            self.parent = self._selection(self.parent + self.child)

            self.child = []

           

wordle = Wordle(

    "Gluegent",

    500,

    30,

    0.6,

    0.2

)


wordle._run()