遺伝的アルゴリズムを勉強する(1)-基本的なＯｎｅＭａｘ問題

遺伝的アルゴリズムの勉強

platypus、deapを動かすのに必要な遺伝的アルゴリズムの知識を、日経ソフトウェアの２０１９年３月号の特集記事をもとに勉強しています。

遺伝的アルゴリズムとは

遺伝アルゴリズムとは「選択（淘汰）」「交叉」「突然変異」と言った遺伝的進化を模したアルゴリズムです。
また遺伝的アルゴリズムは、乱数を多く利用するため、乱択アルゴリズムでもある。

解ける問題は次の２つを満たすこと。
・入力パラメーターに対する数値化（評価）ができる問題
・数値が最大化、最小化となる入力を探す問題

遺伝子：形質を表現するための構成要素
染色体：複数の遺伝子が集まったもの
個体：一つの染色体によって表現される形質（個体＝染色体と言う場合もある。）

個体が環境にどれだけ適しているかの評価値が「適応度」

この適応度を高めるために３つの操作を行う。
選択（淘汰）：適応度が高いものを残す（適応度が低いものを淘汰する）
交叉：２つの親から遺伝子を引き継いだ子を生成する
突然変異：個体の遺伝子を一定確率で変化させる。

交叉が遺伝的アルゴリズムの特徴である。

これらの操作が一回すべて終了すると世代が１つ進む。

OneMax問題とは

OneMax問題とは、[1,0,0,0,1,0,1,1]のように１と０からなるリストの和が最大になるようなリストを探し出す問題です。
遺伝子：０または１
染色体：[1,0,0,0,1,0,1,1]
適応度：リストの和（この場合は、[1,0,0,0,1,0,1,1]=4)

プログラムは、次の要素でできている。
パラメータ設定
関数（適応度を計算、集団を適応度順にソート、選択:適応度の高い個体を残す、交叉、突然変異）
メイン処理（初期集団を生成、選択、交叉、突然変異）

パラメーターの設定

パラメーターとして与えるのは、５つ。遺伝子の長さ、個体数、世代数、突然変異の確率、選択割合

import random
import copy
# パラメータ
LIST_SIZE = 10       # 0/1のリスト長（遺伝子長）
POPULATION_SIZE = 10 # 集団の個体数
GENERATION = 25      # 世代数
MUTATE = 0.1         # 突然変異の確率
SELECT_RATE = 0.5    # 選択割合

この例では、GENERATION = 25なので、２５世代で終了します。一般的には、適応度が変化しなくなったら終了するなどにします。LIST_SIZEを大きくした場合は、POPULATION_SIZEGENERATIONを大きくしないと最適解に到達しない可能性がある。突然変異の確率、選択割合などのチューニングが重要だが、今回は適当に決めている。

関数

# 適応度を計算する
def calc_fitness(individual):#individualは染色体
  return sum(individual)  # 染色体リスト要素の合計
# 集団を適応度順にソートする
def sort_fitness(population):
  # 適応度と個体をタプルにしてリストへ格納する
  fp = []
  for individual in population:
    fitness = calc_fitness(individual)#適応度を計算してfitnessに入れる。
    fp.append((fitness, individual)) #fp に適応度と染色体を順に入れる
  fp.sort(reverse=True)  # 適用度でソート(降順)

  sorted_population = [] # ソートした個体を格納する集団
  for fitness, individual in fp: # 個体を取り出し、集団に格納する
    sorted_population.append(individual)
  return sorted_population #この中に、適用度が高い順にソートされた適用度と染色体が保存されている。

#　選択
# 適応度の高い個体を残す
def selection(population):
  sorted_population = sort_fitness(population)#sort_populationにソートされた適用度と染色体が入っている。
#残す個体数。パラメーター設定で0.5なので個体数１０×０．５で５個残る
  n = int(POPULATION_SIZE * SELECT_RATE)  
  return sorted_population[0:n]#最初から５個が残る。0,1,2,3,4
#交叉
#まず、ind1をコピーして新しい個体indを作る。その後、ランダムに決めたr1～r2の範囲をind2の遺伝子に置き換える
def crossover(ind1, ind2):
  r1 = random.randint(0, LIST_SIZE - 1)#r1の位置をランダムに決める
  r2 = random.randint(r1 + 1, LIST_SIZE)#r1以降でランダムにr2の位置を決める。
  ind = copy.deepcopy(ind1)#ind1のコピーを作る
  ind[r1:r2] = ind2[r1:r2]#染色体ind2からランダムにきめたr1からr2の範囲を取り出し、ind1のコピーへ置き換える、。
  return ind

#突然変異:設定した突然変異確率に従って突然変異させる
def mutation(ind1):
  ind2 = copy.deepcopy(ind1)#コピーでind2を作る。
  for i in range(LIST_SIZE):
    if random.random() < MUTATE:#ランダムに数値を作り、突然変異率以下なら突然変異がおきる
      ind2[i] = random.randint(0, 1)#突然変異のおきたところに０か１を入れる
  return ind2

メイン処理（初期集団を生成、選択、交叉、突然変異）

#初期集団を生成
population = []  # 集団
for i in range(POPULATION_SIZE):
  individual = []    # 染色体
  for j in range(LIST_SIZE):
    # 0/1を乱数で追加
    individual.append(random.randint(0, 1))  
  population.append(individual)

for generation in range(GENERATION):
  print(str(generation + 1) + u"世代")

  #選択
  population = selection(population)

  # 交叉と突然変異を繰り返す。交叉と突然変異で増やす個体数
  n = POPULATION_SIZE - len(population)  
  for i in range(n):
    # 集団から2個体をランダムに選び、
    # 交叉した個体を生成する
    r1 = random.randint(0, len(population) - 1)
    r2 = random.randint(0, len(population) - 1)
    #交叉
    individual = \
      crossover(population[r1], population[r2])

    #突然変異
    individual = mutation(individual)  

    #集団に追加する
    population.append(individual)  

  for individual in population:
    print(individual)

これでOne-Max問題が解けるプログラムです。

結果です。

1世代
[1, 1, 1, 0, 1, 1, 0, 0, 1, 1]
[1, 0, 1, 1, 0, 0, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 1, 0, 1, 1, 0]
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 1, 0, 1, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 1, 0, 0, 1, 0]
[0, 1, 1, 0, 1, 1, 0, 0, 1, 0]
[0, 1, 1, 0, 1, 1, 1, 0, 1, 0]
[1, 0, 1, 1, 0, 1, 0, 0, 1, 0]
[1, 0, 1, 1, 1, 1, 0, 1, 1, 0]

第１４世代で、最適解が見つかりました。
14世代
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1]

第２０世代で、６つまで最適解になりました。
20世代
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

第２５世代ですべて最適解になりました。
25世代
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

これが基本のOneMax問題の解き方です。

次回は、巡回セールスマン問題を解こうと思います。