遺伝的アルゴリズムの一様交叉についての質問です。

前提

実現したいこと

以前もここで質問されてたのですが詳細が書いていなかったためもう一度質問します
ythonで遺伝的アルゴリズムを使い、OneMax問題を解くプログラムを作成したいのですが、一様交叉の部分がうまくいっていません。エラーは起きていないのですが、配列に変化が起きていないので交叉の部分がよくないと考えているのですが、原因がわかりません。
何が悪いのか、これを試してはという意見がありましたら教えていただきたいです。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

python
ソースコード

import random
import copy

random.seed(1870258)
gene_length = 10 # 遺伝子長
individual_length = 10 # 個体数
generation = 30 # 世代数
elite_rate = 0.2 # エリート選択の割合

#個体生成
def get_population():
    population = []
    for i in range(individual_length):  #遺伝子長
        population.append([random.randint(0,1) for j in range(gene_length)])  #個体数
    return population

#適応度
def fitness(pop):
    return sum(pop)

#評価
def evaluate(pop):
    pop.sort(reverse=True)  
    return pop

#エリート選択
def select(eva,pop):
    elites = eva[:int(len(pop)*elite_rate)]   
    return elites

#一様交叉
def cxUniform(parent1, parent2):  
    for i in range(len(parent1)): 
        if random.random() < 0.5:
            parent1[i], parent2[i] = parent2[i], parent1[i]
    return random.choice([parent1,parent2])

def main():
    # 初期個体生成
    pop = evaluate([(fitness(p), p) for p in get_population()])
    print('Generation: 0')
    print('Min : {}'.format(pop[-1][0]))
    print('Max : {}'.format(pop[0][0]))
    print('--------------------------')
    
    for g in range(generation):
        if 10 != pop[0][0] and 10 != pop[-1][0]:
        
            g += 1
            print('Generation: ' + str(g))

            #選択
            eva = evaluate(pop) 
            elites = select(eva,pop) 
            
            #交叉
            new_pop = elites
            while len(new_pop) < individual_length:  
                m1 = random.randint(0, len(elites)-1) 
                m2 = random.randint(0, len(elites)-1) 
                child = cxUniform(elites[m1][1], elites[m2][1])    
                new_pop.append((fitness(child), child))  
            
            new_pop = evaluate(new_pop)
        
            print('Min : {}'.format(pop[-1][0]),'  Result : {}'.format(pop[-1]))
            print('Max : {}'.format(pop[0][0]),'  Result : {}'.format(pop[0]))
            print('--------------------------')
        else:
            break
                
        
        
    print('\n--------------------------End of evolution--------------------------')
    print('Generation: ' + str(g))
    print('Min : {}'.format(pop[-1][0]),'  Result : {}'.format(pop[-1]))
    print('Max : {}'.format(pop[0][0]),'  Result : {}'.format(pop[0]))

    

if __name__ == '__main__':
    main()
### 試したこと
ここに問題に対して試したことを記載してください。
実行結果

Generation: 0
Min : 2
Max : 8
--------------------------
Generation: 1
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 1, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 2
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 3
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 4
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 5
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 1, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 6
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 7
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 8
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 9
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 1, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 10
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 1, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 11
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 12
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 13
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 14
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 1, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 15
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 16
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 17
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 18
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 1, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 19
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 20
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 1, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 21
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 22
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 23
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 24
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 1, 1, 1, 1, 1, 1, 1])
--------------------------
Generation: 25
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 26
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 27
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 1, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 28
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 0, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 29
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------
Generation: 30
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
--------------------------

--------------------------End of evolution--------------------------
Generation: 30
Min : 2   Result : (2, [1, 0, 0, 0, 0, 0, 1, 0, 0, 0])
Max : 8   Result : (8, [1, 1, 0, 0, 1, 1, 0, 1, 1, 1])
### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

回答1件

ベストアンサー

① 一様交叉処理のバグ

python
1def main():
2（略）
3                child = cxUniform(elites[m1][1], elites[m2][1]) 
4                new_pop.append((fitness(child), child))

python
1#一様交叉
2def cxUniform(parent1, parent2):  
3    for i in range(len(parent1)): 
4        if random.random() < 0.5:
5            parent1[i], parent2[i] = parent2[i], parent1[i]
6    return random.choice([parent1,parent2])
7

cxUniform において、 parant 間で一様交叉を行ったあと元の parant の参照を返しているため、
new_pop には elite が持つリストへの参照を持つ子が追加されてしまうことになります。

つまり、elite と elite 以外の個体との間で同じ遺伝子を共有している状態になってしまうということです。
この結果、（popの内容を表示したとき）elite 間の遺伝子組み換えの結果が elite 以外の個体にも反映されたように見えてしまいます。

一様交叉の結果得られる個体は新しい個体と考えるならば、cxUniform 関数は、新しいリストを返すようにするべきでしょう。

python
1#一様交叉
2def cxUniform(parent1, parent2):  
3    for i in range(len(parent1)): 
4        if random.random() < 0.5:
5            parent1[i], parent2[i] = parent2[i], parent1[i]
6    return random.choice([parent1[:], parent2[:]])  // 修正

② コードを素直に読んだ場合、アルゴリズムとして、下記のような流れになっているようです。

select 関数で、全個体数のうち上位 elite_rate の割合の個体をエリートとして選出（エリート選出数＝全個体数 × elite_rate ）
選出したエリートからランダムに２つ（その２つが同一個体である場合も含む）を選び出して、一様交叉を行う。
一様交叉を行ってできた２パターンからランダムに１つを選ぶ。
上記の操作を、「全個体数－エリート選出数」の回数だけ行う。
上記のループを、generation 回行う。ただし、最上位の個体もしくは最下位の個体の評価値が 10 になった場合はその時点でループ処理を抜ける。

ここで、ループ中、上位 {全個体数 × elite_rate} 個以上の個体がすべて同じ遺伝子パターンを有している状況になると、両親と同じ遺伝子パターンを有する子しか生み出されなくなり、その時点の最上位エリートを超える評価値を持つ個体が生まれなくなります 。

質問記載のコードのパラメータ設定の場合、個体数が10個で elite_rate が 0.2 であり、常に上位2つの個体のみエリートとして選ばれるため、早々にして上位2個の個体が同じ遺伝子パターンになる可能性が高くなります。

いったん上位2個の個体が同じ遺伝子パターンを有してしまうと、どんなに世代数を重ねても、遺伝子パターンは変化しません。

これが評価値が頭打ちになる原因です。

この状況を回避するには、上位エリートの遺伝子パターンを変える状況、たとえば一定確率でエリートに突然変異を起こす等のやり方が考えられます。（もちろん突然変異の設定確率によっては世代数をもっと多くしないと効果は現れません）

③ 途中経過表示で new_pop と pop が反映されていないように思われます。

diff
1-           new_pop = evaluate(new_pop)
2+           pop = evaluate(new_pop)        
3            print('Min : {}'.format(pop[-1][0]),'  Result : {}'.format(pop[-1]))
4            print('Max : {}'.format(pop[0][0]),'  Result : {}'.format(pop[0]))
5            print('--------------------------')
6        else:
7            break

④ エリート間一様交叉処理のループを抜ける条件が固定値（10）になっているので、ここは gene_length とした方がより汎用的になると思います。

diff
1    for g in range(generation):
2-        if 10 != pop[0][0] and 10 != pop[-1][0]:
3+        if gene_length != pop[0][0] and gene_length != pop[-1][0]:

投稿2022/08/28 11:59

編集2022/08/28 13:03