3行で

遺伝的アルゴリズムでFizzBuzzの解を導く。
言語はPython、ライブラリ等は無しでフルスクラッチ。
アルゴリズム的にどこまで正しいかはわからないが答えは出せた。

1. やりたかったこと

Pythonで遊びたかった。
遺伝的アルゴリズムを組んでみたかった。
お題として解き方が明確(評価関数が簡単)なFizzBuzzを選択。
1-100で正しいFizzBuzzを出力することをゴールとする。

2. 遺伝的アルゴリズムとは

このスライドに触発されたところが大きい。
参考：遺伝的アルゴリズム（Genetic Algorithm）を始めよう！

生物進化における遺伝と適者生存による自然淘汰の仕組みをソフトウェア的に模すことで複雑な問題に対する最適解を探索する手法
ある命題に対する解の候補を遺伝子(gene)とその集合体である染色体(chromosome)で表現した個体(individual)を複数用意し、適応度(fitness)の高い個体を優先して交叉(crossover)、突然変異(mutation) などの操作を繰り返しながら最適解の探索をおこなう

ランダムに生成した個体のうち適応度の高い個体同士を掛け合わせ、
より適応度の高い個体を選別していくイメージ。

3. どのようにFizzBuzzを遺伝的アルゴリズムに落とし込むか

用語などは全て上記スライドから。

遺伝子：数字、Fizz、Buzz、FizzBuzzのそれぞれを数値化して遺伝子とする。
符号化方式：実数値エンコーディングとする。具体的にはIntEnum列挙型で0:数字``1:Fizz``2:Buzz``3:FizzBuzzとした。
染色体：FizzBuzzの答えとなる1-100までの遺伝子。具体的には上記遺伝子Enumのlist[100]。
個体：1つ、または複数の染色体からなる解の候補、ということで１染色体を個体とした。

4. 実装

4-1. 選択

ルーレット方式(roulette wheel selection)を実装した。
random.choices()で適応度を比重として重複を除き選択。

fizzbuzzga.py

# 比重を意識して要素を重複無くランダムに取得する
def get_sample_weight(population, number_of_samples=1):
  """population is list. number_of_samples is int.

  population.item[0] weight
  population.item[1] value

  >>> if True:
  ...   l = [[1,'a'],[2,'b'],[3,'c']]
  ...   s = get_sample_weight(l,2)
  ...   print(len(s), len(set([i[1] for i in s])))
  2 2
  """
  pop = dict(enumerate(population))
  k = number_of_samples
  samples = []
  new_samples = []
  # random.choces()[重複あり]でインデックスを取り出した後、set()で重複を除く
  # 重複を除いたインデックスでサンプルを取りだす
  while(k>0):
    new_samples = set(
      random.choices(list(pop), weights=[v[0] for v in pop.values()], k=k))
    samples += [pop.pop(i) for i in new_samples]
    k -= len(new_samples)

  return samples[0] if number_of_samples==1 else samples

# 選択
# ルーレット
def roulette_wheel_selection(population):
  return [i[1] for i in get_sample_weight(population, 2)]

# ランキング
def ranking_selection(population):
  pass

# トーナメント
def tournament_selection(population):
  pass

# エリート主義
def elitism(population):
  pass

4-2. 交叉

二点交叉(two-point crossover)と一様交叉(uniformcrossover)を実装した。
二点交叉はランダムに２点を取ってスライスして入れ替え、一様交叉は２個体をzip()でまとめてforに入れてランダムに取っていった。
各交叉方式に重みをつけ、個体ごとにランダムに採用する。(二点交叉の割合を高くした。)

fizzbuzzga.py

# 指定された範囲からランダムに２つの数値を返す
# from,toとも返す数値に含む  
def get_two_point(from_num, to_num):
  """return sorted 2 numbers.

  >>> get_two_point(0, 1)
  [0, 1]
  """
  return sorted(random.sample(range(from_num, to_num+1), 2))

# 交差
# 二点交差
def two_point_clossover(individual1, individual2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(individual1), len(individual2)))
  p1, p2 = get_two_point(0, L)
  c1 = individual1[0:p1] + individual2[p1:p2] + individual1[p2:]
  c2 = individual2[0:p1] + individual1[p1:p2] + individual2[p2:]
  # assert len(c1)==L and len(c2)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}][{}] OUT[{}][{}]'.format(individual1, individual12, c1, c2)
  return c1, c2

# 一様交差
def position_based_crossover(individual1, individual2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(individual1), len(individual2)))
  c1, c2 = [], []
  for i,j in zip(individual1, individual2):
    if random.randrange(0,2)%2==0:
      c1.append(i)
      c2.append(j)
    else:
      c1.append(j)
      c2.append(i)
  # assert len(c1)==L and len(c2)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}][{}] OUT[{}][{}]'.format(individual1, individual12, c1, c2)
  return c1, c2

4-3. 突然変異

置換(substitution)、摂動(perturbation)、交換(swap)、逆位(inversion)、撹拌(scramble)を実装した。
転座(translocation)は面倒になったのでパス。
各突然変異方式に重みをつけ、個体ごとにランダムに採用する。(今回は全て同じ重みにしている。)

fizzbuzzga.py

# 突然変異
# 置換
def substitution(individual, p=0.04):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  buf = individual[:]
  for i in range(len(buf)):
    if random.random()<=p:
      buf[i] = random.choice([g for g in list(gene) if g!=buf[i]])  
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 交換
def swap(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L-1)
  buf = individual[:]
  buf[p1], buf[p2] = buf[p2], buf[p1]
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 逆位
def inversion(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L)
  buf = individual[:]
  buf[p1:p2] = (buf[p1:p2])[::-1]
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 撹拌
def scramble(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L)
  buf = individual[:]
  p1p2 = buf[p1:p2]
  random.shuffle(p1p2)
  buf[p1:p2] = p1p2
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 転座
def translocation(individual):
  pass

4-4. 世代交代

離散世代モデル(discrete generation model)と連続世代モデル(continuous generation model)を実装した。
連続世代モデルでは、一定割合をエリート主義で採用し、残りはランダムに採用した。
各世代交代方式に重みをつけ、世代ごとにランダムに採用する。(連続世代モデルの割合を高くした。)

fizzbuzzga.py

# 世代交代
# 離散
def discrete_generation(population1, population2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(population1), len(population2)))
  return population2

# 連続
def continuous_generation(population1, population2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(population1), len(population2)))
  elit_len = int(N * Peli)
  othe_len = N - elit_len
  # 両世代合わせてソートしてエリートと駄民で扱いを分ける
  sorted_population = sorted(
    population1+population2, key=lambda v:v[0], reverse=True)
  upper = sorted_population[0:elit_len]
  lower = sorted_population[elit_len:]
  return upper + random.sample(lower, othe_len)

4-5. 評価関数

予め正解となる結果配列をベタ書きして比較する。

fizzbuzzga.py

# 評価用
scoring_chart = [0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2]
# 適応度の評価関数
def scoring(individual):
  """
  >>> scoring([0])[0]
  1
  >>> scoring([1])[0]
  0
  >>> scoring([2])[0]
  0
  >>> scoring([3])[0]
  0
  >>> scoring([0,1,1,0,2,1,0,0,1,2,0,1,0,0,3])[0]
  14
  """
  return (
    len([1 for i in zip(individual, scoring_chart) if i[0]==i[1]]),
    individual)

4-6. 初期収束への対策

最初は二点交叉と世代交代時にエリート優先採用したところ初期収束が激しかった。
一様交叉をランダムに挟み、世代交代時のエリート割合を減らすことで多様性を保つよう努めた。
また一定確率で大変異を起こすよう実装を追加した。

4-7. ヒッチハイキングへの対応

二点交叉によるところが大きいため、一様交叉の割合を増やすことで対策した。

5. 各種パラメータ

fizzbuzzga.py

# パラメータ
# 遺伝子長 -> 100までのFizzBuzz
L = 100
# 個体数 
N = 100
# 交叉確率 80〜95%
Pc = 0.90
# 交叉方法と比重
Pc_weight = {(0.70, two_point_clossover), (0.30, position_based_crossover)}
# 突然変異確率 0.1〜1%
Pm = 0.01
# 突然変異方法と比重
Pm_weight = {(0.25, substitution), (0.25, swap), (0.25, inversion), (0.25, scramble)} 
# 大変異確率
Plm = 0.01
# 大変異時の突然変異確率
PlmPm = 0.40
# 世代交代方法と比重
Pg_weight = {(0.05, discrete_generation), (0.95, continuous_generation)}
# 世代交代が連続の場合のエリート選択割合
Peli = 0.20

# 終了条件 最大適応度100(遺伝子長と同じ)で完了とする
MAX_APP=L

6. 結果

パラメータの調整にもよるが、GPCの無料インスタンスで数秒〜数十秒程度で適応率100になった。
色々パラメータをいじってみたが、１世代当たりの個体数を増やすのが最も早く（早い世代で）解に辿り着いた。
ただし１世代の個体数＊世代数で見た「解までに必要になった個体数」は１世代1000個体よりも１世代300個体の方が少なかった。

１世代の個体数	解までの世代数(10回の平均)	解までに必要になった個体数
30	4161.3	124,839
100	1148.6	114,860
300	138.9	41,670
1000	56.1	56,100

１世代100個体で100世代ごとに途中経過を表示すると、だいたい最初の100世代で適応度90前後まで最適化されている。
500世代程度で適応度99までいくが、そこから適応度100までが長い。

世代	適応度	FizzBuzz(太字は誤っている箇所)
1	35	1, Buzz, Fizz, 4, FizzBuzz, Buzz, 7, FizzBuzz, 9, Fizz, Buzz, 12, 13, Buzz, 15, Fizz, Fizz, 18, 19, Buzz, Fizz, 22, Fizz, FizzBuzz, Buzz, Fizz, Fizz, 28, 29, 30, Fizz, FizzBuzz, FizzBuzz, 34, FizzBuzz, Fizz, 37, FizzBuzz, Buzz, 40, 41, Buzz, FizzBuzz, 44, 45, Fizz, Fizz, Fizz, FizzBuzz, FizzBuzz, Fizz, Fizz, Buzz, Buzz, FizzBuzz, 56, Fizz, Fizz, Buzz, 60, 61, 62, FizzBuzz, 64, FizzBuzz, Buzz, 67, 68, FizzBuzz, FizzBuzz, Buzz, Fizz, 73, Fizz, Buzz, Buzz, Fizz, 78, Fizz, FizzBuzz, Fizz, Buzz, 83, Buzz, 85, Buzz, 87, 88, FizzBuzz, Buzz, 91, 92, Buzz, Fizz, FizzBuzz, 96, Fizz, Buzz, Fizz, 100
101	88	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, Buzz, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, Buzz, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, FizzBuzz, FizzBuzz, 46, 47, Fizz, Buzz, 50, Fizz, 52, 53, Fizz, Buzz, 56, 57, 58, 59, FizzBuzz, 61, Fizz, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Fizz, Buzz, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, Fizz, 98, Fizz, 100
201	94	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, 50, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Fizz, Buzz, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, Fizz, 98, Fizz, 100
301	95	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, 50, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, Buzz, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, FizzBuzz, 98, Fizz, 100
401	97	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, 50, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, 100
501	98	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, 100
601	98	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, 100
701	99	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz
801	99	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz
901	99	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz
1001	99	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz
1101	99	FizzBuzz, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz
1109	100	1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz, 26, Fizz, 28, 29, FizzBuzz, 31, 32, Fizz, 34, Buzz, Fizz, 37, 38, Fizz, Buzz, 41, Fizz, 43, 44, FizzBuzz, 46, 47, Fizz, 49, Buzz, Fizz, 52, 53, Fizz, Buzz, 56, Fizz, 58, 59, FizzBuzz, 61, 62, Fizz, 64, Buzz, Fizz, 67, 68, Fizz, Buzz, 71, Fizz, 73, 74, FizzBuzz, 76, 77, Fizz, 79, Buzz, Fizz, 82, 83, Fizz, Buzz, 86, Fizz, 88, 89, FizzBuzz, 91, 92, Fizz, 94, Buzz, Fizz, 97, 98, Fizz, Buzz

7. 課題

個体数が少ない場合、やはり初期収束し解の多様性が失われているように思われる。
多様性を保つため以下のような案が考えられる。
- 交叉時に「同じ個体同士」は選ばないようにしているが、「同じ遺伝子を持つ異なる個体同士」の組み合わせにも制限を設ける。
  → 気をつけないと無限ループしそう。
- 世代交代時、同じ遺伝子を持つ個体の数を制限する。

8. ソース全文

fizzbuzzga.py

import random
import sys
from enum import IntEnum

# 遺伝的アルゴリズムでFizzBuzz

# 数値、Fizz、Buzz、FizzBuzzの染色体
class gene(IntEnum):
  NUM = 0
  FIZZ = 1
  BUZZ = 2
  FIZZBUZZ = 3

# N個のランダムな個体を生成する
def create_population(N):
  """
  >>> len(create_population(10))
  10
  """
  list_gene = list(gene)
  return [random.choices(list_gene, k=L) for i in range(N)]

# 全固体の適応度を計算する
def scoring_all(population):
  """
  >>> scoring_all([[0],[1],[2],[3]])
  [(1, [0]), (0, [1]), (0, [2]), (0, [3])]
  """
  result = []
  for individual in population:
    result.append(scoring(individual))
  return result

# 評価用
scoring_chart = [0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2,0,1,0,0,3,0,0,1,0,2,1,0,0,1,2]
# 適応度の評価関数
def scoring(individual):
  """ IN:[indivicual], OUT:[SCORE,[individual]].

  >>> scoring([0])[0]
  1
  >>> scoring([1])[0]
  0
  >>> scoring([2])[0]
  0
  >>> scoring([3])[0]
  0
  >>> scoring([0,1,1,0,2,1,0,0,1,2,0,1,0,0,3])[0]
  14
  """
  return (
    len([1 for i in zip(individual, scoring_chart) if i[0]==i[1]]),
    individual)

# 比重を意識して要素を重複無くランダムに取得する
def get_sample_weight(population, number_of_samples=1):
  """population is list. number_of_samples is int.

  population.item[0] weight
  population.item[1] value

  >>> if True:
  ...   l = [[1,'a'],[2,'b'],[3,'c']]
  ...   s = get_sample_weight(l,2)
  ...   print(len(s), len(set([i[1] for i in s])))
  2 2
  """
  pop = dict(enumerate(population))
  k = number_of_samples
  samples = []
  new_samples = []
  # random.choces()[重複あり]でインデックスを取り出した後、set()で重複を除く
  # 重複を除いたインデックスでサンプルを取りだす
  while(k>0):
    new_samples = set(
      random.choices(list(pop), weights=[v[0] for v in pop.values()], k=k))
    samples += [pop.pop(i) for i in new_samples]
    k -= len(new_samples)

  return samples[0] if number_of_samples==1 else samples

# 選択
# ルーレット
def roulette_wheel_selection(population):
  return [i[1] for i in get_sample_weight(population, 2)]

# ランキング
def ranking_selection(population):
  pass

# トーナメント
def tournament_selection(population):
  pass

# エリート主義
def elitism(population):
  pass

# 指定された範囲からランダムに２つの数値を返す
# from,toとも返す数値に含む
def get_two_point(from_num, to_num):
  """return sorted 2 numbers.

  >>> get_two_point(0, 1)
  [0, 1]
  """
  return sorted(random.sample(range(from_num, to_num+1), 2))

# 交差
# 二点交差
def two_point_clossover(individual1, individual2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(individual1), len(individual2)))
  p1, p2 = get_two_point(0, L)
  c1 = individual1[0:p1] + individual2[p1:p2] + individual1[p2:]
  c2 = individual2[0:p1] + individual1[p1:p2] + individual2[p2:]
  # assert len(c1)==L and len(c2)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}][{}] OUT[{}][{}]'.format(individual1, individual12, c1, c2)
  return c1, c2

# 一様交差
def position_based_crossover(individual1, individual2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(individual1), len(individual2)))
  c1, c2 = [], []
  for i,j in zip(individual1, individual2):
    if random.randrange(0,2)%2==0:
      c1.append(i)
      c2.append(j)
    else:
      c1.append(j)
      c2.append(i)
  # assert len(c1)==L and len(c2)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}][{}] OUT[{}][{}]'.format(individual1, individual12, c1, c2)
  return c1, c2


# 突然変異
# 置換
def substitution(individual, p=0.04):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  buf = individual[:]
  for i in range(len(buf)):
    if random.random()<=p:
      buf[i] = random.choice([g for g in list(gene) if g!=buf[i]])  
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 交換
def swap(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L-1)
  buf = individual[:]
  buf[p1], buf[p2] = buf[p2], buf[p1]
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 逆位
def inversion(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L)
  buf = individual[:]
  buf[p1:p2] = (buf[p1:p2])[::-1]
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 撹拌
def scramble(individual):
  # print(sys._getframe().f_code.co_name, 'called. [{}]'.format(len(individual)))
  p1, p2 = get_two_point(0, L)
  buf = individual[:]
  p1p2 = buf[p1:p2]
  random.shuffle(p1p2)
  buf[p1:p2] = p1p2
  # assert len(buf)==L, sys._getframe().f_code.co_name + ' Error.' + 'IN[{}] OUT[{}]'.format(individual, buf)
  return buf

# 転座
def translocation(individual):
  pass

# 世代交代
# 離散
def discrete_generation(population1, population2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(population1), len(population2)))
  return population2

# 連続
def continuous_generation(population1, population2):
  # print(sys._getframe().f_code.co_name, 'called. [{}][{}]'.format(len(population1), len(population2)))
  elit_len = int(N * Peli)
  othe_len = N - elit_len
  # 両世代合わせてソートしてエリートと駄民で扱いを分ける
  sorted_population = sorted(
    population1+population2, key=lambda v:v[0], reverse=True)
  upper = sorted_population[0:elit_len]
  lower = sorted_population[elit_len:]
  return upper + random.sample(lower, othe_len)

# 最大スコアの個体を返す
def get_best_individual(population):
  return sorted(population, key=lambda v:v[0], reverse=True)[0]

def score_to_string(population):
  score_max = max([s[0] for s in population])
  score_sum = sum([s[0] for s in population])
  return 'N[{}] MAX[{}] SUM[{}] AVE[{:0.02f}]'.format(
    len(population), score_max, score_sum, score_sum/len(population))

# 表現型への変更
to_phenotype = {
  gene.NUM:      lambda i: str(i+1), 
  gene.FIZZ:     lambda i: 'Fizz', 
  gene.BUZZ:     lambda i: 'Buzz', 
  gene.FIZZBUZZ: lambda i: 'FizzBuzz' 
}
def decoding(individual):
  return [to_phenotype[g](i) for i, g in enumerate(individual)]

# 選択
def selection(scored_population):
  return roulette_wheel_selection(scored_population)

# 交叉
def crossover(c1, c2):
  if random.random()<=Pc:
    c1, c2 = get_sample_weight(Pc_weight)[1](c1,c2)
  return c1, c2

# 突然変異
def mutation(is_lm, c1, c2):
  if (is_lm and random.random()<=PlmPm) or random.random()<=Pm:
    c1 = get_sample_weight(Pm_weight)[1](c1)
    c2 = get_sample_weight(Pm_weight)[1](c2)
  return c1, c2

def main():
  # 集団を生成
  population = create_population(N)
  # 交叉を行う回数
  co_count = int(N / 2)
  # 適応度付き集団
  scored_population = scoring_all(population)
  sys.stdout.write('GENERATION[001] ' + score_to_string(scored_population))
  # 最優の個体
  best_individual = get_best_individual(scored_population)

  generation = 0
  while(best_individual[0]<MAX_APP):
    generation += 1
    next_population = []
    # 大変異判定
    is_lm = random.random()<=Plm
    for j in range(co_count):
      # 選択
      c1, c2 = selection(scored_population)
      # 交叉
      c1, c2 = crossover(c1, c2)
      # 突然変異
      c1, c2 = mutation(is_lm, c1, c2)
      next_population += [c1, c2]
    # 世代交代
    scored_next_population = scoring_all(next_population)
    scored_population = get_sample_weight(Pg_weight)[1](scored_population, scored_next_population)
    sys.stdout.write('\rGENERATION[{:03d}] '.format(generation+1) + score_to_string(scored_population))
    # 最優の個体
    best_individual = get_best_individual(scored_population)
  else:
    print()

  phenotype = decoding(best_individual[1])
  print('\n'.join(phenotype))


# パラメータ
# 遺伝子長 -> 100までのFizzBuzz
L = 100
# 個体数 
N = 100
# 交叉確率 80〜95%
Pc = 0.90
# 交叉方法と比重
Pc_weight = {(0.70, two_point_clossover), (0.30, position_based_crossover)}
# 突然変異確率 0.1〜1%
Pm = 0.01
# 突然変異方法と比重
Pm_weight = {(0.25, substitution), (0.25, swap), (0.25, inversion), (0.25, scramble)} 
# 大変異確率
Plm = 0.01
# 大変異時の突然変異確率
PlmPm = 0.40
# 世代交代方法と比重
Pg_weight = {(0.05, discrete_generation), (0.95, continuous_generation)}
# 世代交代が連続の場合のエリート選択割合
Peli = 0.20

# 終了条件 最大適応度100(遺伝子長と同じ)で完了とする
MAX_APP=L


if __name__=='__main__':
  import doctest
  doctest.testmod()
  main()