Pythonでライブラリを使わずに、OneMax問題をやってみました。
機械学習の技術を実用的なレベルまで持っていきたく試行錯誤を繰り返しているのですが、最適化という部分をまだあまり突き詰めていませんでした。
ハイパーパラメータの最適化には色々な手法があるみたいですが、ここに遺伝的アルゴリズムを使うことができるようです。
最近では、Bayesian Optimization(ベイズ最適化)が使われているようですが、引き出しは多い方がいいのでやってみました。
(実際にニューラルネットとか機械学習で使うとなれば、実数値遺伝的アルゴリズムを使うようになると思います。)
遺伝的アルゴリズムについて
色々なサイトや文献を読み漁りましたが、遺伝的アルゴリズムをPythonで入門だけすることを前提とすれば、
と、ここで紹介されていた
www.slideshare.net で十分かなと思います。実装
「個体集団」を用意し、「選択」、「交叉」、「突然変異」の3種類を順に実装していきます。
用語
上記サイトより抜粋しました。
| 用語 | |
|---|---|
| Gene | 遺伝子 |
| Chromosome | 染色体 |
| Individual | 個体 |
| Population | 個体集団 |
| Fitness | 適応度 |
| Mutation | 突然変異 |
| Phenotype | 表現型 |
| Locus | 遺伝子座 |
| Genotype | 遺伝子型 |
| Offspring | 子孫 |
| Selection | 選択 |
| Roulette wheel selection | ルーレット方式 |
| Ranking selection | ランキング方式 |
| Tournament selection | トーナメント方式 |
| Elitism | エリート主義 |
| Crossover | 交叉 |
| Single point crossover | 一点交叉 |
| Two-point crossover | 二点交叉 |
| Multi-point crossover | 多点交叉 |
| Uniform drossover | 一様交叉 |
個体の生成
class Individual: def __init__(self, chromosome, fitness=None): self.chromosome = chromosome self.fitness = fitness def mutate(self, mutation): for i in self.chromosome: if mutation > (random.randint(0, 100) / 100): self.chromosome[i] = random.randint(0, 1) def fit(self): self.fitness = sum(self.chromosome) / len(self.chromosome) def create_individual(chr_size): return Individual([random.randint(0, 1) for i in range(chr_size)])
1つの個体は、染色体を1つだけ持つようにしてみます。
chromosme は、適当なサイズの遺伝子のリストを持ちます。
fitness は、OneMax問題の場合は単純で、遺伝子の値が0 or 1 なので、染色体の遺伝子の合計値を、染色体の長さで割ります。
なので、答えが1の場合が最適応となります。
mutate() でランダムに遺伝子を突然変異させます。
選択
エリート主義で、適応度の高いものからいくつか選択します。
def select_individual(population, elite_size): population = sorted(population, reverse=True, key=lambda i: i.fitness) elite = [population.pop(0) for i in range(elite_size)] random.shuffle(population) return elite, population
交叉
二点交叉を行います。
def crossover(a, b): # Two-point crossover a_chr = a.chromosome b_chr = b.chromosome size = len(a_chr) f = random.randint(0, size) s = random.randint(f, size) _a = a_chr[:f] + b_chr[f:s] + a_chr[s:] _b = b_chr[:f] + a_chr[f:s] + b_chr[s:] return [Individual(_a), Individual(_b)]
突然変異
ある個体の染色体の遺伝子を突然変異させます。
def mutate(population, individual_mutation, gene_mutation): for i in range(len(population)): if individual_mutation > (random.randint(0, 100) / 100): population[i].mutate(gene_mutation) return population
実行その1
世代数を指定する場合です。
まず、適当な個体集団をつくり、適応度を計算します。
その個体集団から、エリートをいくつか選出します。
選出したエリートは、交叉や突然変異をすることなく、次の世代に渡します。
残りの個体集団は、交叉、突然変異させて、個体の数を調整して次の世代に渡します。
import random random.seed(64) CHROMOSOME_SIZE = 10 GENE_MUTATION = 0.1 INDIVIDUAL_MUTATION = 0.1 POPULATION_SIZE = 100 ELITE_SIZE = 2 GENERATION_MAX = 3 if __name__ == '__main__': # Population of the first generation population = [create_individual(CHROMOSOME_SIZE) for i in range(POPULATION_SIZE)] # Start print("START\n", population[0].chromosome, "\n") for generation in range(GENERATION_MAX): # Fit [population[i].fit() for i in range(POPULATION_SIZE)] # Result result = [p.fitness for p in population] print("{0} Generation ---".format(generation + 1)) print("\tMIN: {0}".format(min(result))) print("\tMAX: {0}".format(max(result))) print("\tAVG: {0}".format(round(sum(result) / len(result), 3)), "\n") # Select selected_individual, population = select_individual(population, ELITE_SIZE) # Crossover crossover_individual = [] for i in range(len(population)-1): crossover_individual.extend(crossover(population[i], population[i+1])) random.shuffle(crossover_individual) # Mutate, Generate offspring offspring = mutate(crossover_individual[:POPULATION_SIZE-ELITE_SIZE], INDIVIDUAL_MUTATION, GENE_MUTATION) offspring.extend(selected_individual) # Update population population = offspring print("-"*30, "\nResult:") print(selected_individual[0].chromosome)
とりあえず。3世代で回してみます。
START
[1, 0, 1, 0, 0, 1, 0, 0, 0, 1]
1 Generation ---
MIN: 0.0
MAX: 1.0
AVG: 0.498
2 Generation ---
MIN: 0.2
MAX: 0.8
AVG: 0.508
3 Generation ---
MIN: 0.2
MAX: 0.9
AVG: 0.507
------------------------------
Result:
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
実行その2
今度は、エリート以外の子孫をだんだん減らしていき、最終的にエリートのみを残してみます。
import random random.seed(64) CHROMOSOME_SIZE = 10 GENE_MUTATION = 0.1 INDIVIDUAL_MUTATION = 0.1 POPULATION_SIZE = 100 ELITE_SIZE = 2 if __name__ == '__main__': # Population of the first generation population = [create_individual(CHROMOSOME_SIZE) for i in range(POPULATION_SIZE)] # Start print("START\n", population[0].chromosome, "\n") generation = 0 while 1: generation += 1 # Fit [population[i].fit() for i in range(POPULATION_SIZE)] # Result result = [p.fitness for p in population] print("{0} Generation ---".format(generation)) print("\tMIN: {0}".format(min(result))) print("\tMAX: {0}".format(max(result))) print("\tAVG: {0}".format(round(sum(result) / len(result), 3)), "\n") # Select selected_individual, population = select_individual(population, ELITE_SIZE) # Crossover crossover_individual = [] for i in range(len(population)-1): crossover_individual.extend(crossover(population[i], population[i+1])) random.shuffle(crossover_individual) POPULATION_SIZE -= ELITE_SIZE # Mutate, Generate offspring offspring = mutate(crossover_individual[:POPULATION_SIZE], INDIVIDUAL_MUTATION, GENE_MUTATION) offspring.extend(selected_individual) # Update population population = offspring if len(population) <= ELITE_SIZE: break print("-"*30, "\nResult:") print(population[0].chromosome)
こちらは、毎回エリートの数分減らしていき、最終的にエリートのみになるまでに50世代回ります。
START [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] 1 Generation --- MIN: 0.2 MAX: 0.9 AVG: 0.515 ... 50 Generation --- MIN: 0.6 MAX: 1.0 AVG: 0.825 ------------------------------ Result: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
最後に
一通り遺伝的アルゴリズムを書いてみましたが、これが果たして正しいやり方なのかどうか、正直不安です。
一応、最適解を導き出してはいますが…。
この記事を参考になさるときは他の文献も合わせて読んで頂き、間違いがあればご指摘頂ければ嬉しいです。
