Python での遺伝的アルゴリズムによるガベージコレクション戦略の最適化

遺伝的アルゴリズムは、進化のプロセスに性質が似ている最適化手法です。これは乱暴な例えかもしれませんが、よく見ると、ダーウィンの自然選択は、環境内で繁栄するのに完全に適合した生物を生み出すことを目標とする最適化タスクに大体似ています。

この記事では、わずか数時間でガベージ収集ロボットを「進化」させる遺伝的アルゴリズムを Python で実装する方法を紹介します。

[[348489]]

背景

私がこれまでに出会った遺伝的アルゴリズムの原理に関する最高のチュートリアルは、Melanie Mitchell 著の『Complexity: A Guided Tour』という複雑系に関する優れた本からのものです。

ある章で、ミッチェルは、ゴミを拾うことだけが人生の目的であるロビーというロボットを紹介し、GA を使用してロビーの制御ポリシーを最適化する方法について説明します。以下では、この問題に対する私のアプローチを説明し、Python でアルゴリズムを実装する方法を示します。この種のアルゴリズムを構築するための優れたパッケージがいくつかあります (DEAP など) が、このチュートリアルでは基本的な Python、Numpy、および TQDM (オプション) のみを使用します。

これは単なる例ですが、GA は多くの実際のアプリケーションで使用されています。データサイエンティストとして、私はハイパーパラメータの最適化とモデルの選択にこれらを頻繁に使用します。計算コストは高くなりますが、GA を使用すると、検索空間の複数の領域を並行して探索できるため、勾配を計算する場合に適しています。

問題の説明

Robby という名前のロボットは、ゴミで満たされ、4 つの壁に囲まれた 2D グリッドの世界に住んでいます (下の図を参照)。このプロジェクトの目標は、ロボットが効率的にゴミを拾い、壁に衝突しないようにするための最適な制御戦略を開発することです。

ロビーは、自分の周囲の上、下、左、右の 4 つのブロックと、自分がいるブロックしか見ることができません。各ブロックには、空、ゴミあり、壁の 3 つのオプションがあります。したがって、ロビーには 3⁵ = 243 通りのケースが存在します。ロビーは、上、下、左、右（4 種類）に移動する、ランダムに移動する、ゴミを拾う、静止する、という 7 つの異なるアクションを実行できます。

したがって、ロビーの制御戦略は、0 から 6 までの 243 個の数字 (ロビーが 243 の考えられる状況で実行すべきアクションに対応) で構成される「DNA」文字列としてエンコードできます。

方法

あらゆる GA の最適化手順は次のとおりです。

問題に対する初期のランダムな解決策の「集団」を生成する
個人の「適応度」は、問題をどれだけうまく解決できるかに基づいて評価されます。
最も適切な解決策は、「生殖」し、「遺伝」物質を次の世代の子孫に伝えることである。
最適化されたソリューションのセットが得られるまで、手順2と3を繰り返します。

このタスクでは、ランダムな DNA 文字列 (ランダム制御ポリシーに対応) に初期化された Robby の第 1 世代を作成しました。次に、シミュレーションでは、これらのロボットをランダムに割り当てられたグリッドワールドで実行し、そのパフォーマンスを観察します。

適合性

ロボットの適応度は、n 回の移動でどれだけのゴミを拾うか、何回壁に衝突するかによって決まります。この例では、ロボットがゴミを拾うたびに 10 ポイントが与えられ、壁にぶつかるたびに 5 ポイントが減点されます。その後、ロボットは適応度に関連した確率で「交尾」し（つまり、ゴミをたくさん拾うロボットは繁殖する可能性が高くなります）、新しい世代のロボットが誕生します。

交尾

「交配」を実現するにはいくつかの方法があります。ミッチェルのバージョンでは、両親の2本のDNA鎖をランダムにつなぎ合わせて結合し、次世代の子供を作った。私の実装では、各親から各遺伝子をランダムに割り当てます (つまり、243 個の遺伝子のそれぞれについて、コインを投げてどの遺伝子が継承されるかを決定します)。

たとえば、私の方法を使用すると、最初の 10 個の遺伝子のうち、親と子の可能性のある遺伝子は次のようになります。

親 1: 1440623161
親2: 2430661132
子供: 2440621161

突然変異

このアルゴリズムで再現する自然選択からのもう一つの概念は「突然変異」です。子どもの遺伝子の大部分は両親から受け継がれますが、遺伝子変異（ランダム割り当て）の可能性もわずかながら考慮に入れました。この突然変異率により、新たな可能性を探求することができます。

Python実装

最初のステップは、必要なパッケージをインポートし、このタスクのパラメータを設定することです。これらのパラメータは出発点として選択しましたが、調整可能なので、ぜひ実験してみてください。

 「」 「 」
パッケージのインポート
「」 「 」
 numpyをnpとしてインポートする
tqdm.notebookからtqdmをインポート
 
 「」 「 」
パラメータの設定
「」 「 」
 # シミュレーション設定
pop_size = 200 # 世代ごとのロボットの数
num_breeders = 100 # 各世代で交配できるロボットの数
num_gen = 400 # 世代の総数
iter_per_sim = 100 # 各ロボットのガベージコレクションシミュレーションの数
moves_per_iter = 200 # シミュレーションごとにロボットが実行できる移動回数
 
 # グリッド設定
rubbish_prob = 0.5 # 各グリッド内のゴミの確率
grid_size = 10 # 0 グリッドサイズ（壁を除く） 
 
 # 進化設定
wall_penalty = -5 # 壁にぶつかったときに減点されるフィットポイントの数
no_rub_penalty = -1 # 空のマスにあるゴミを拾うとペナルティポイントが加算されます
rubbish_score = 10 # ゴミを拾うとポイントがもらえます
突然変異率 = 0.01 # 突然変異の確率

次に、グリッドワールド環境のクラスを定義します。各セルには、それぞれ空のセル、ゴミのあるセル、壁に対応するマーカー「o」、「x」、「w」が付けられます。

クラス環境:
 「」 「 」
    ゴミで満たされたグリッド環境を表すために使用されるクラス。各セルは次のように表すことができます。
 'o' : 空
'x' : ゴミ
'w' : 壁
「」 「 」
    def __init__(self, p=rubbish_prob, g_size=grid_size):
        self.p = p # セルがゴミである確率
        self.g_size = g_size # 壁は含まれません
 
        # グリッドを初期化し、ランダムにガベージを割り当てる
        self.grid = np.random.choice([ 'o' , 'x' ],サイズ=(self.g_size+2,self.g_size+2), p=(1 - self.p, self.p)) 
         
        # 外側の四角を壁として設定する
        self.grid[:,[0,self.g_size+1]] = 'w'  
        self.grid[[0,self.g_size+1], :] = 'w'   
 
    show_grid(self)を定義します。
        # 現在の状態のグリッドを印刷する
        印刷(self.grid) 
 
    def remove_rubbish(self,i,j):
        # 指定されたセル (i,j) からゴミを消去します
        if self.grid[i,j] == 'o' : # セルはすでに空です
戻る 間違い 
それ以外：
            自己.グリッド[i,j] = 'o'  
戻る 真実  
 
    get_pos_string(self,i,j)を定義します。
        # ロボットに「見える」セル (i,j) 内のセルを示す文字列を返します
self.grid[i-1,j] + self.grid[i,j+1] + self.grid[i+1,j] + self.grid[i,j-1] + self.grid[i,j] を返す

次に、ロボットを表すクラスを作成します。このクラスには、アクションを実行し、適応度を計算し、親ロボットのペアから新しい DNA を生成するメソッドが含まれています。

クラスロボット:
 「」 「 」
    ゴミ収集ロボットを表すために使用される
「」 「 」
    def __init__(self, p1_dna=None, p2_dna=None, m_rate=mutation_rate, w_pen=wall_penalty, nr_pen=no_rub_penalty, r_score=rubbish_score):
        self.m_rate = m_rate # 突然変異率
        self.wall_penalty = w_pen # 壁にぶつかったときのペナルティ
        self.no_rub_penalty = nr_pen # 空のマスにあるゴミを拾った場合のペナルティ
        self.rubbish_score = r_score # ゴミ拾いの報酬
        self.p1_dna = p1_dna # 親2のDNA
        self.p2_dna = p2_dna # 親2のDNA 
         
        # シーン文字列から遺伝子インデックスを検索するための辞書を生成する
        con = [ 'w' , 'o' , 'x' ] # 壁、空、ゴミ
        自己.situ_dict = dict()
カウント= 0
詐欺の場合：
のために 右 欠点：
ダウンインコンの場合：
のために 左 欠点：
 pos in conの場合:
                            self.situ_dict[上+右+下+左+位置] =カウント 
カウント+= 1 
         
        # DNAを初期化する
        自己.get_dna() 
 
    get_dna(self)を定義します。
        # ロボットのDNA文字列を初期化する
        self.p1_dnaがNone の場合:
            # 親がいないときにDNAをランダムに生成する
            self.dna = '' . join ([str(x) for x in np.random.randint(7, size = 243)])
それ以外：
            自己.dna = 自己.mix_dna() 
 
    mix_dna(self)を定義します。
        # 親のDNAからロボットのDNAを生成する
        mix_dna = '' . join ([np.random.choice([self.p1_dna,self.p2_dna])[i]の範囲(243)]のiについて
 
        #突然変異を追加
iが範囲内(243)の場合:
            np.random.rand() > 1 の場合 - self.m_rate:
                mix_dna = mix_dna[:i] + str(np.random.randint(7)) + mix_dna[i+1:] 
 
 mix_dnaを返す
 
    def シミュレート (self、n_iterations、n_moves、debug = False ):
        # ガベージコレクションをシミュレートする
        合計スコア = 0
範囲内(n_iterations)の場合:
            self.score = 0 # 適合スコア
            self.envir = 環境()
            self.i, self.j = np.random.randint(1,self.envir.g_size+1, size =2) # 初期位置をランダムに割り当てる
            デバッグの場合:
                print( '前' )
                print( '開始位置:' , self.i, self.j)
                自己.envir.show_grid()
のために 動く 範囲内(n_moves):
                自己.行動()
            tot_score += 自己スコア
            デバッグの場合:
                print( 'after' )
                print( '終了位置:' ,self.i, self.j)
                自己.envir.show_grid()
                print( 'スコア:' , self.score)
 tot_score / n_iterations # n 回の反復の平均スコアを返します
 
    def act(self):
        # DNAとロボットの位置に基づいてアクションを実行する
        post_str = self.envir.get_pos_string(self.i, self.j) # ロボットの現在の位置
        gene_idx = self.situ_dict[post_str] # 現在の位置のDNAの関連インデックス
        act_key = self.dna[gene_idx] # DNAからアクションを読み取る
        act_key == '5'の場合:
            # ランダム移動
            act_key = np.random.choice([ '0' , '1' , '2' , '3' ]) 
 
        act_key == '0'の場合:
            自己.mv_up()
        act_key == '1'の場合:
            自己.mv_right()
        act_key == '2'の場合:
            自己.mv_down()
        act_key == '3'の場合:
            自己.mv_left()
        act_key == '6'の場合:
            自己ピックアップ() 
 
    mv_up(自分)を定義します。
        # 上に移動
        self.i == 1の場合:
            自己スコア += 自己壁ペナルティ
それ以外：
            自分.i -= 1 
 
    mv_right(自分)を定義します。
        # 右に移動
        self.j == self.envir.g_sizeの場合:
            自己スコア += 自己壁ペナルティ
それ以外：
            自己.j += 1 
 
    mv_down(self)を定義します。
        # 下に移動
        self.i == self.envir.g_size の場合:
            自己スコア += 自己壁ペナルティ
それ以外：
            自分.i += 1 
 
    mv_left(self)を定義します。
        # 左に移動
        self.j == 1の場合:
            自己スコア += 自己壁ペナルティ
それ以外：
            自己.j -= 1 
 
    def pickup(自分):
        # ゴミ拾い
        成功 = self.envir.remove_rubbish(self.i, self.j)
        成功した場合:
            # ゴミ拾いに成功しました
            自己スコア += 自己ゴミスコア
それ以外：
            # 現在のブロックではゴミは拾われていません
            自己スコア += 自己無こすりペナルティ

最後に、遺伝的アルゴリズムを実行します。以下のコードでは、ロボットの初期集団を生成し、自然淘汰を実行させます。このアルゴリズムを実装するには、確かにより高速な方法 (並列化を活用するなど) がありますが、このチュートリアルでは、わかりやすくするために速度を犠牲にしました。

 # 初期人口
pop = [Robot()のxが範囲内(pop_size)]
結果 = [] 
 
 # 進化を実行する
iがtqdm(range(num_gen))の場合:
    スコア = np.zeros(pop_size) 
     
    # すべてのロボットをループする
enumerate(pop)のidx、robの場合:
        # ガベージコレクションシミュレーションを実行し、適合度を計算する
        スコア = rob.simulate(iter_per_sim、 moves_per_iter)
        スコア[idx] = スコア
 
    results.append([scores.mean(), scores.max ()]) # 各世代の平均値と最大値を保存する
 
    best_robot = pop[scores.argmax()] # 最高のロボットを保存する
 
    # 交尾できるロボットの数を制限する
    inds = np.argpartition(scores, -num_breeders)[-num_breeders:] # 適応度に基づいて上位ロボットのインデックスを取得します
    サブポップ = []
 indsのidxの場合:
        サブポップ.append(pop[idx])
    スコア = スコア[inds] 
 
    # 二乗して正規化する
    norm_scores = (スコア -スコア.min ()) ** 2
    norm_scores = norm_scores / norm_scores.sum () 
 
    # 次世代ロボットの創出
    新しいポップ = []
範囲(pop_size)内の子の場合:
        # 適合度の高い親を選択する
        p1、p2 = np.random.choice(サブポップ、p = norm_scores、サイズ= 2、置換= False )
        new_pop.append(ロボット(p1.dna、p2.dna)) 
 
    ポップ = new_pop

当初、ほとんどのロボットはゴミを拾わず、常に壁にぶつかっていましたが、数世代後には、いくつかの単純な戦略（「ゴミがある場合は拾う」、「壁の隣にある場合は壁にぶつからない」など）が見られるようになりました。何百回もの反復を経て、驚くべきガベージコレクションの天才たちの世代が誕生しました。

結果

下のグラフは、400 世代にわたってロボットの集団で成功するガベージコレクション戦略を「進化」させることができたことを示しています。

進化した制御戦略の品質を評価するために、直感的に理解できるルールをいくつか含むベンチマーク戦略を手動で作成しました。

ゴミが現在のブロックにある場合は、それを拾います
隣接するマスにゴミが見えている場合は、そのマスに移動する
壁に近い場合は反対方向に移動する
それ以外の場合はランダムに移動する

平均すると、このベースラインポリシーは 426.9 の適応度を達成しましたが、最終的な「進化した」ボットは平均 475.9 の適応度を達成しました。

戦略分析

この最適化アプローチの素晴らしい点は、直感に反する解決策を見つけることができることです。ロボットは人間が設計する可能性のある合理的なルールを学習できただけでなく、人間が決して考えないような戦略を自発的に考案することもできました。近視や記憶障害を克服するために「マーカー」を使用する高度な技術が登場した。

たとえば、ロボットが現在ゴミのあるマスにいて、東と西のマスにゴミがあるのが見えている場合、単純なアプローチとしては、現在のマスにあるゴミをすぐに拾い、ゴミのあるマスに移動することになります。この戦略の問題点は、ロボットがいったん（たとえば西に）移動すると、東にもう 1 つのジャンクがあることを思い出す方法がないことです。この問題を克服するために、私たちは進化するロボットが次の手順を実行するのを観察しました。