- 遺伝的アルゴリズムについて、基本的で簡単なところを勉強として書いていきます。
- 理解を深めるために遺伝的アルゴリズムを実際にPythonでコードを書いて、いくつか問題を解く形で動かしていきます。
遺伝的アルゴリズムとは
英語ではgenetic algorithm。初出は1975年、ミシガン大学のジョン・H・ホランド教授によって提案されたそうです。
ある程度、各個体で個別となる属性を持たせた「遺伝子」「染色体」扱いの要素を大量に生成し、ランダムな要素を絡めつつ目的とする問題に対して良い成績が出るまで次世代の生成を繰り返すアルゴリズムです。
ダーウィンの進化論のように（うまく生き残るかために適合できた個体が生き残るかのように）、運よく問題に対してうまく適合した要素を中心に次世代に残したり、そのうまくはまった要素を問題の解答としたりします。
アルゴリズム実行前に答えなどが存在せず、ランダム要素を絡めつつマッチした答えを探索していく計算で、教師無し学習の強化学習などとも少し近い面もあるかもしれません（コード自体も少し似ている実装になる箇所も出てきますし、強化学習界隈でも色々と出てきたりしています）。
どんな計算なのか
以降では要素1つを染色体（Chromosome）と表記していきます。
まずはランダムに染色体を生成します。この数は任意です。数が多い程1つの世代に対する計算が多くなる一方で、1世代の中で様々な条件のものが生成されバリエーションが多くなります。
続いて評価関数で各要素を評価して、次世代をどうするのか決定します。
この評価関数は問題にどのくらいフィットしているのかという値を返します。機械学習で言うと誤差関数のようなものになります。
評価関数の内容は問題に合わせて任意に決定します。生物的に例として言うと「どのくらい寒さに強いか」とか「どのくらい目が良いか」といったような指標になります。「現実問題では特定の問題に対してどのくらい得点が高くなるか」といったものになります。
次世代には現在の世代の各要素をベースに、一例として以下のような計算でどのように後々の世代に特徴を伝搬していくかを決定します（この辺りも色々と調整や選択ができます）。
交叉（crossover）
交叉は2つの染色体の特徴を半分ずつ受け継ぐような形で次世代に2つの染色体を残します。両親から半分ずつ特徴を受け継いで、2人の子供を次世代として扱うといったような計算になります。
突然変異（mutation）
突然変異は、次世代に一部もしくは大部分などでがらっと変わった性質を持った染色体を残します。
交叉などによって似たような染色体ばかりが残るのを防いで、局所解のようなケース（偏って最適な答えが出ないなど）を軽減するために使われたりします。
ルーレット選択（roulette wheel selection）
交叉などでの次世代への遷移の際にどのように2つの染色体を選択するか、という際の選択方式としてルーレット選択という方法があります。
これは、評価関数で高い成績を残している染色体ほど選択対象とする確率を高くする形でのランダムな選択となります。
評価関数での成績に応じて、ランダム抽出の際の確率の重みを決定するといった具合です。
トーナメント選択（tournament selection）
トーナメント選択は、染色体全体から一定数をランダムに抽出（たとえば全体で2000の染色体の中から100をランダムに抽出するなど）した後に、その中から評価関数で高いものを必要件数分（例えば交叉で必要なら2件）抽出します。
いつ計算を止めるか
評価関数の目標値が分かっている場合にはその値が出るまで世代数を膨大に設定して計算する場合があります。
たとえば経路探索であれば「何分以内にゴールに到達できるルート」みたいな条件でもOKであれば、その条件を満たしたら計算終わり、といった具合です。
もしくは目標値が分かっていない場合には一定数の世代まで達した時点で計算を止めて評価関数の値が最大の染色体の属性値を利用します。
こちらは明確な答えや許容値が事前に分からず、「とりあえず200世代分計算して一番成績の良いものを使う」みたいな計算の止め方になります。
どんな特徴があるのか / どんな時に向いているのか
遺伝的アルゴリズムは前述のように多くの計算でランダム要素が強く絡んできます。そのため、問題が解決となるまでの計算量は実行する度に毎回変わります。
また、すぐに解決することもあれば長時間解答に辿り着かないケースも発生します。
基本的には問題に向いたアルゴリズムがあるのであれば、そちらを利用した方が計算量がぐぐっと少なくなるケースが多めです。
良さそうな解答に辿り着いたとしても、それが最適解とは限らないケースも発生しうる形になります。
一方で、最適なアルゴリズムがいまいち思いつかず、探索的に答えを探っていきたいような緩いケースでも色々汎用的に利用していくことができます。
これらを踏まえて向いているようなユースケースの一例として、
- 100点（最適解）ではなく80点くらいの答えが求められればOKなケース
- 短い計算時間が求められないケース
- もっと最適なアルゴリズムが思いつかないケース
などが挙げられます。
Pythonでの実装
いくつかの問題を遺伝的アルゴリズムを使って解決していってみます。
使うもの
- Python 3.8.5
- Pylance (型チェック用)
※過去に書いた他の似たような記事と同様に、勉強のためにライブラリなどは使わずにビルトインモジュールを使って書いていきます。
留意点
向いているユースケースとして、「もっと最適なアルゴリズムが思いつかないケース」と触れましたがこの記事で触れていく問題に関しては勉強のためわざと簡単な問題であったりもっと最適な解き方が山ほどある問題に対して対応していきます。
最適なアルゴリズムを使うとさくっと終わる計算が長時間かかったりする点はご留意ください。
必要なモジュールのimport
まずはビルトインのもので利用するものをimportしていきます。
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
- annotations は、将来のPythonバージョンで採用予定の型アノテーションのものが使えるようになるため利用しています。
- 型アノテーションを利用するため、typing パッケージから必要なものをimportしています。
- choices は引数に指定したiterableのものから任意の個数のものをランダムに選択する関数です。次世代の個体の選択に使います。重みの引数で各個体ごとに対する確率の大きさを設定することもできます。
- random は0.0から1.0の範囲の乱数を取得する関数です。
- randrange はrangeで指定した時に得られる値の範囲からランダムに値を取得する関数です（0～9の中からどれかをランダムに得るといったように）。
- shuffle はiterableな要素をシャッフルする関数です。
- nlargest は指定されたiterableの要素内で大きなものを順番にn個取得する関数です。トーナメント選択で上位の個体を抽出する際に使います。
- 今回2つの問題を解くため、抽象クラスを利用するため abc (abstract base class)パッケージのものをimportしています。
- deepcopy はその名の通り要素をディープコピーする関数です。次世代の個体を作る時にディープコピーを利用しています。
個体の抽象クラスの定義
前述の通り、本記事では2つの問題を扱っていこうと思いますので、問題ごとに継承するための個体の抽象クラスを追加していきます。
@abstractmethodとデコレーターを追加することで、継承先のクラスでデコレーターが付いているメソッドを上書きしないとエラーで怒られるようにすることができます。
class Chromosome(ABC):
"""
染色体（遺伝的アルゴリズムの要素1つ分）を扱う抽象クラス。
"""
@abstractmethod
def get_fitness(self) -> float:
"""
対象の問題に対する染色体の優秀さを取得する評価関数Y用の
抽象メソッド。
Returns
-------
fitness : float
対象の問題に対する染色体の優秀さの値。高いほど問題に
適した染色体となる。
遺伝的アルゴリズムの終了判定などにも使用される。
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
ランダムな特徴（属性値）を持ったインスタンスを生成する
抽象メソッド。
Returns
-------
instance : Chromosome
生成されたインスタンス。
"""
...
@abstractmethod
def mutate(self) -> None:
"""
染色体を（突然）変異させる処理の抽象メソッド。
インスタンスの属性などのランダムな別値の設定などが実行される。
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : Chromosome
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of Chromosome
交叉実行後に生成された2つの個体（染色体）。
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
個体間の比較で利用する、評価関数の値の小なり比較用の関数。
Parameters
----------
other : Chromosome
比較対象の他の個体。
Returns
-------
result_bool : bool
小なり条件を満たすかどうかの真偽値。
"""
return self.get_fitness() < other.get_fitness()
遺伝的アルゴリズムで必要な評価関数（get_fitness）、変異（mutate）、交叉（exec_crossover）の各インターフェイスを設けてあります。内容はEllipsisインスタンス（...）のみ記載して他は省略しています（継承先で上書きします）。
また、アルゴリズムスタート前に最初の世代を生成する必要があるため、クラスメソッドとしてmake_random_instanceというメソッドを用意しています。
評価関数の値の上位に抽出などが必要になるため、比較用に__lt__のメソッドを定義して評価関数の値で小なりの比較をするようにしてあります。
遺伝的アルゴリズムのクラスの定義
遺伝的アルゴリズムのためのクラスを定義していきます。
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
遺伝的アルゴリズムを扱うクラス。
Parameters
----------
initial_population : list of Chromosome
最初の世代の個体群（染色体群）。
threshold : float
問題解決の判定で利用するしきい値。この値を超える個体が
発生した時点で計算が終了する。
max_generations : int
アルゴリズムで実行する最大世代数。
mutation_probability : float
変異確率（0.0～1.0）。
crossover_probability : float
交叉確率（0.0～1.0）。
selection_type : int
選択方式。以下のいずれかの定数値を指定する。
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
C = TypeVar('C', bound=Chromosome)という箇所は、ジェネリックとしての型の定義をしています（ChromosomeのC）。
利用する際に、ChromosomeのサブクラスなどだとPylanceの型チェックで（サブクラス ≠ Chromosomeクラスとして判定されて）引っかかってしまうしまうため利用しています。
bound引数は「ChromosomeもしくはChromosomeのサブクラスであればOK」といった制約を付与する引数です。
コンストラクタに関してはアルゴリズムで必要な「最初の個体群」「アルゴリズムの停止判定に使われる評価関数のしきい値」「世代数の上限」「変異確率」「交叉確率」「ルーレット選択などの選択方式」を指定しています。
その他にも選択方式の定数を定義しています（SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1など）。
ルーレット選択の実装
GeneticAlgorithm クラスにルーレット選択の処理を追加していきます。
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
ルーレット選択を行い、交叉などで利用する2つの個体（染色体）を
取得する。
Returns
-------
selected_chromosomes : list of Chromosome
選択された2つの個体（染色体）を格納したリスト。選択処理は評価関数
（fitnessメソッド）による重みが設定された状態でランダムに抽出される。
Notes
-----
評価関数の結果の値が負になる問題には利用できない。
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
ルーレット選択ではランダムで個体が選択されるものの、評価関数で得られる値が高い方が優先されるように重みが設定されます。
この重みに関しては、A～Eという5つの個体があるとして、以下のようなルーレットをイメージしてください。
各個体の評価関数の値がルーレット上の面積になります。面積の少ない個体（≒評価関数での評価が低い個体）も選択されうる形となりますが、確率は低くなります。
トーナメント選択の実装
同様にトーナメント選択も GeneticAlgorithm クラスに追加していきます。ルーレット選択とトーナメント選択のどちらが使われるかは、コンストラクタの selection_type の指定によって決まります。
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
トーナメント選択を行い、交叉などで利用するための2つの個体
（染色体）を取得する。
Returns
-------
selected_chromosomes : list of Chromosome
選択された2つの個体（染色体）を格納したリスト。トーナメント
用に引数で指定された件数分抽出された中から上位の2つの個体が
設定される。
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
トーナメント選択ではまずはトーナメントで使用する個体群の抽出をしています。今回はハードコーディングで個体群の半分を選択しています。
また、返却値は2件の個体なので、nlargest関数で上位2位までの個体を抽出しています。この関数の内部ではリスト内の要素同士の比較が必要になるため、Chromosomeクラスで__lt__のメソッドの設定が必要になります。
次世代への遷移の処理の実装
今度は現世代から次世代へ移るための処理を GeneticAlgorithm クラスに追加していきます。
やることとしては、
- [1]. 選択方式（ルーレット選択など）に応じた2個ずつの個体の抽出を行う（parentsという名前にしてあります）。
- [2]. コンストラクタで指定された交叉確率や変異確率に応じて抽出された2つの個体を変化させる（乱数と確率で、交叉などが発生しない場合は親の個体をそのまま次世代に設定する）。
- [3]. 次世代の個体のリストへ用意した2つの個体を追加する。
- [4]. 次世代の個体のリストが現世代の個体のリストと同数になるまで[1]～[3]を繰り返す。
という処理になります。
def _to_next_generation(self) -> None:
"""
次世代の個体（染色体）を生成し、個体群の属性値を生成した
次世代の個体群で置換する。
"""
new_population: List[Chromosome] = []
# 元の個体群の件数が奇数件数の場合を加味して件数の比較は等値ではなく
# 小なりの条件で判定する。
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
# 2件ずつ次世代のリストを増やしていく都合、元のリストよりも件数が
# 多い場合は1件リストから取り除いてリストの件数を元のリストと一致させる。
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
算出された親の2つの個体のリストから、次世代として扱う
2つの個体群のリストを取得する。
一定確率で交叉や変異させ、確率を満たさない場合には引数の値が
そのまま次世代として設定される。
Parameters
----------
parents : list of Chromosome
算出された親の2つの個体のリスト
Returns
-------
next_generation_chromosomes : list of Chromosome
次世代として設定される、2つの個体を格納したリスト。
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
選択方式に応じた親の2つの個体（染色体）のリストを取得する。
Returns
-------
parents : list of Chromosome
取得された親の2つの個体（染色体）のリスト。
Raises
------
ValueError
対応していない選択方式が指定された場合。
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'対応していない選択方式が指定されています : %s'
% self._selection_type)
return parents
アルゴリズムを動かすための処理の実装
評価関数の値がしきい値以上になる（≒目標値に達する個体が生まれた）か、もしくは世代数の上限を超えるまで次世代への遷移を繰り返す処理を書いていきます。
機械学習で言うと、学習のためのコードのようなところに該当します。世代が機械学習で言うところのエポックのようなものになります。世代ごとに最良の個体を情報としてprint関数で出力しています。
ただし、最良の個体は「全ての世代で最良の個体」が該当します。機械学習のようにエポックごとの値ではない点はご留意ください。
def run_algorithm(self) -> Chromosome:
"""
遺伝的アルゴリズムを実行し、実行結果の個体（染色体）のインスタンス
を取得する。
Returns
-------
betst_chromosome : Chromosome
アルゴリズム実行結果の個体。評価関数でしきい値を超えた個体
もしくはしきい値を超えない場合は指定された世代数に達した
時点で一番評価関数の値が高い個体が設定される。
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'世代数 : {generation_idx}'
f' 最良個体情報 : {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
個体群のリストから、評価関数の値が一番高い個体（染色体）を
取得する。
Returns
-------
best_chromosome : Chromosome
リスト内の評価関数の値が一番高い個体。
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
動作確認用のシンプルな式の問題を追加して動かしてみる
遺伝的アルゴリズムの実装の確認用にシンプルな問題を作ってアルゴリズムを動かしてみます。
以下の式の値が最大になるように、xとyを求めるという問題を使います。
6x - x^2 + 4y - y^2
答えはx = 3、y = 2の時に13となって最大となります。
動作確認を目的とするため、前述の通り遺伝的アルゴリズムを使うまでもない（むしろ計算時間的に好ましくない）点はスルーでお願いします。
事前に準備した抽象クラスの Chromosome クラスを継承していきます。
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
遺伝的アルゴリズムの動作確認用の、以下のシンプルな式
6x - x^2 + 4 * y - y^2
の値が最大になるxとyの値を求める問題を扱うクラス。
（正解はx = 3, y = 2）
Parameters
----------
x : int
xの初期値。
y : int
yの初期値。
"""
self.x = x
self.y = y
評価関数を追加していきます。評価関数の返却値は数値が大きいほど優秀と遺伝的アルゴリズムで判断されますが、今回の問題は単純に大きい値となるxとyを求める形なのでそのまま$6x - x^2 + 4y - y^2$の計算後の値を使います。
def get_fitness(self) -> float:
"""
現在のxとyの値による、6x - x^2 + 4 * y - y^2 の式の計算結果の
値を取得する評価関数として利用するメソッド。
Returns
-------
fitness : int
式の計算結果の値。
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
最初の個体群生成時に利用する make_random_instance のクラスメソッドは、xとyに0～99のランダムな値を設定するようにします。
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
ランダムな初期値を与えた SimpleEquationProblem クラスの
インスタンスを生成する。
Returns
-------
problem : SimpleEquationProblem
生成されたインスタンス。xとyには0～99までの範囲でランダムな
値が設定される。
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
変異はxもしくはyの値を1加算するか減算するかという計算にしました。
def mutate(self) -> None:
"""
個体を（突然）変異させる（乱数に応じて、xもしくはyの値を
1増減させる）。
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
交叉も同様に書いていきます。交叉は2つの個体の特徴を半分ずつ引き継ぐ形で、次世代の個体を2つ返却するようにします。
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : SimpleEquationProblem
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of SimpleEquationProblem
交叉実行後に生成された2つの個体を格納したリスト。親となる
個体それぞれから、xとyの値を半分ずつ受け継いだ個体となる。
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
アルゴリズム実行中に、各世代で最良の個体情報を出力したいため、そのための処理を__str__メソッドに書いておきます。
def __str__(self) -> str:
"""
個体情報の文字列を返却する。
Returns
-------
info : str
個体情報の文字列。
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
SimpleEquationProblem クラスの問題を動かしてみる
実際に動かしてみます。
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
個体数30、最大世代数100、変異確率20％、交叉確率30％、トーナメント選択の選択方式を選択しました。各数値は決め打ちなので特に選択理由はありません（雰囲気で選択）。
ただし、以下のように評価関数の値がマイナスになりうる場合にはルーレット選択は（重みなどの都合で）選択できないのでトーナメント選択を指定しています。
ルーレット選択
...
この方式はホランドが最初に提案したときに使われた選択方式であり、最も有名な選択方式であるが適応度が負の数を取らないことが前提になっている。
遺伝的アルゴリズム - Wikipedia
また、今回は最大値の答えが13と分かっているので、しきい値に13を指定しています。
実行すると以下のように出力されました。序盤のアルゴリズム説明の節で説明した通り、遺伝的アルゴリズムはランダム性が強いのですぐに終了する時もあれば世代数が多く必要になるケースもあり、実行の度に結果が変わります。
2020-10-31 19:24:39.948226 世代数 : 0 最良個体情報 : x = 14, y = 6, fitness = -124
2020-10-31 19:24:39.960250 世代数 : 1 最良個体情報 : x = 14, y = 5, fitness = -117
2020-10-31 19:24:39.961220 世代数 : 2 最良個体情報 : x = 13, y = 5, fitness = -96
2020-10-31 19:24:39.962218 世代数 : 3 最良個体情報 : x = 13, y = 4, fitness = -91
2020-10-31 19:24:39.975251 世代数 : 4 最良個体情報 : x = 12, y = 4, fitness = -72
2020-10-31 19:24:39.982250 世代数 : 5 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.982250 世代数 : 6 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.996219 世代数 : 7 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.997251 世代数 : 8 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.998224 世代数 : 9 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:39.999254 世代数 : 10 最良個体情報 : x = 11, y = 2, fitness = -51
2020-10-31 19:24:40.000221 世代数 : 11 最良個体情報 : x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 世代数 : 12 最良個体情報 : x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.001250 世代数 : 13 最良個体情報 : x = 9, y = 2, fitness = -23
2020-10-31 19:24:40.002251 世代数 : 14 最良個体情報 : x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.003250 世代数 : 15 最良個体情報 : x = 8, y = 2, fitness = -12
2020-10-31 19:24:40.004217 世代数 : 16 最良個体情報 : x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.005251 世代数 : 17 最良個体情報 : x = 6, y = 2, fitness = 4
2020-10-31 19:24:40.006252 世代数 : 18 最良個体情報 : x = 5, y = 3, fitness = 8
2020-10-31 19:24:40.006252 世代数 : 19 最良個体情報 : x = 5, y = 2, fitness = 9
2020-10-31 19:24:40.007219 世代数 : 20 最良個体情報 : x = 4, y = 2, fitness = 12
2020-10-31 19:24:40.008219 世代数 : 21 最良個体情報 : x = 3, y = 2, fitness = 13
今回は22個目の世代でx = 3、y = 2という解答が求められ、評価関数の値が13になっていることが確認できます（この辺りはディープラーニングの学習に似ていますね）。
SEND + MORE = MONEYの覆面算の問題を解いてみる
簡単な問題で動いてくれるのが確認できたので、もう少し複雑なものでもう一つ問題を解いていってみます。
覆面算（cryptarithmetic）と呼ばれるものの一つの、SEND + MORE = MONEY問題を扱っていきます。
SEND + MORE = MONEY問題とは
以下のような計算を成り立たせる問題です。SENDやらMONEYやらの単語に特段意味はありません。
各文字には0～9までの数字を当てはめることができます。例えばSに3、Eに5を割り当て・・・といった具合です（0を選択肢に含まないパターンもありますが、本記事では0を選択肢として含める形で進めます）。
ただし、同一の数字を他の文字に割り当てることはできません（Sに8を設定して、Eにもまた8を割り当てるといったことはできません）。
4桁のSの値、3桁のEの値、2桁のN、1桁のDから構成されるSENDの値と、4桁のM、3桁のO、2桁のR、1桁のEから構成されるMOREの値を合算した値が5桁のM、4桁のO、3桁のN、2桁のE、1桁のYから構成されるMONEYの値にぴったり一致させる組み合わせを求めるという問題です。
なお、同じ文字であれば割り当てる数字も一緒になります。つまりMOREのMに8を割り当てたらMONEYのMも8にしないといけないといった具合です。
SEND + MORE = MONEY問題のためのクラスの追加
SimpleEquationProblem クラスと同様に、 Chromosome クラスを継承する形でクラスを追加していきます。流れは SimpleEquationProblem とほぼ同じです。
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE = MONEYの覆面算の問題を遺伝的アルゴリズムで
解くためのクラス。
Parameters
----------
letters_dict : LetterDict
問題で利用する8個の各文字（キー）と割り振られた数値（値）
の初期値を格納した辞書。
"""
self.letters_dict: LetterDict = letters_dict
今回はキーに対象の文字、値に割り当てられた数字を持つ辞書を使っていくので、LetterDictという名前の型エイリアスを定義しました。
評価関数用のメソッドをSendMoreMoneyProblemクラスに追加していきます。評価関数はSENDやMORE、MONEYといった各値を各文字ごとに桁数を加味して作成し、MONEYの値とSEND + MOREの合算値の差分を求めています。
def get_fitness(self) -> float:
"""
現在の各文字に割り振られた数値によるSEND + MOREの数値と
MONEYの数値の差分による評価関数用のメソッド。
Notes
-----
遺伝的アルゴリズムの評価関数の値が評価が高い形となるため、
誤差が大きい程数値が低くなるように調整された状態で値が
返却される。
Returns
-------
fitness : int
SEND + MOREの数値とMONEYの数値の差分による評価値。
差分が小さいほど大きな値が設定される。
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
現在割り振られてい各文字の数値によるSENDの値を取得する。
Returns
-------
send_val : int
現在割り振られてい各文字の数値によるSENDの値。
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
現在割り振られてい各文字の数値によるMOREの値を取得する。
Parameters
----------
more_val : int
現在割り振られてい各文字の数値によるMOREの値
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
現在割り振られている各文字の数値によるMONEYの値を取得する。
Returns
-------
money_val : int
現在割り振られている各文字の数値によるMONEYの値。
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
遺伝的アルゴリズムでは値が大きい程優秀と判定される一方で、差分は小さい方が好ましいので、返却値は差分が大きいほど小さくなるように1 / (difference + 1)としています。
+ 1部分は0除算が発生しないようにするための値です。差分は最小で0なので、評価関数の最大値は1 / 1で1となることが分かります（そのため、アルゴリズム実行時のしきい値は1となります）。
インスタンス生成用のクラスメソッドを定義していきます。これは各文字に対して0～9までの数字を被らないように割り振るだけで、難しいことはしていません。
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
ランダムな初期値を与えた SendMoreMoneyProblem クラスの
インスタンスを生成する。
Returns
-------
problem : SendMoreMoneyProblem
生成されたインスタンス。各文字には0～9までの範囲で
数値が重複しない形で値が設定される。
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
変異の処理を書いていきます。変異もランダムに選択した1つの文字を被らないように他の数字に変えるだけのシンプルな内容にしています。
def mutate(self) -> None:
"""
個体を（突然）変異させる（ランダムに特定の文字の値を割り振られて
いない数値で差し替える）。
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
各文字に割り振られていない数字を取得する。
Returns
-------
not_assigned_num : int
各文字に割り振られていない数字。文字は8文字な一方で、
数字は0～9の10個なので、2個割り振られていない数値が存在し、
その中から1つが設定される。
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
続いて交叉の処理を書いていきます。交叉の処理をどうしようか・・・と考えたのですが、以下のような内容にしました。
- [1]. 親の個体をコピーする。
- [2]. 子の2つの個体で、それぞれ半分ずつ（SENDとMORYの4文字ずつ）別の親が持つ数値を引き継がせる（ただし、数値の重複が発生するため文字と数値の割り振りは一致しない）。
- [3]. もし引き継げない場合（両親間で重複している数値の利用が多い場合）は割り振られていない数値を割り振る。
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : SendMoreMoneyProblem
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
交叉実行後に生成された2つの個体を格納したリスト。
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
親に設定されている数値の中で、まだ子に設定されていない数値を
取得する。
Notes
-----
親と子の数値の組み合わせ次第では選択できる値が見つからないケース
があるので、その場合は0～9の値の中で割り振られていない数値が
設定される。
Parameters
----------
child : SendMoreMoneyProblem
子の個体。
parent : SendMoreMoneyProblem
親の個体。
Returns
-------
not_assigned_num : int
算出されたまだ割り振られていない数値。
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
最後に世代ごとの情報の出力用に、__str__メソッドで個体情報を返却するようにしておきます。
def __str__(self) -> str:
"""
個体情報の文字列を返却する。
Returns
-------
info : str
個体情報の文字列。
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
print関数などを通した際には以下のようなフォーマットで出力されます。
2020-10-31 20:51:15.345000 世代数 : 5 最良個体情報 :
S = 4 E = 6 N = 1 D = 9
M = 0 O = 5 R = 3 Y = 2
SEND = 4619 MORE = 536 MONEY = 5162 difference : 7
SendMoreMoneyProblem クラスの問題を動かしてみる
遺伝的アルゴリズムを動かしてみて、 SendMoreMoneyProblem クラスの問題を解いてみます。
if __name__ == '__main__':
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()
今回は SimpleEquationProblem よりも複雑な問題になるため、個体数も1000と多くしています（その分計算時間は長くなります）。
しきい値は評価関数の箇所で触れたように誤差が0になった場合の1.0です。
中々問題が解決しないケースも発生しうるため、最大世代数も1000と大きくしてあります。
今回は評価関数の値が負にはならないので、ルーレット選択が使えるので折角なのでルーレット選択を指定しています。
動かすと以下のように25個めの世代で誤差が0になりました。
2020-10-31 20:51:33.663973 世代数 : 24 最良個体情報 :
S = 5 E = 7 N = 3 D = 1
M = 0 O = 6 R = 4 Y = 8
SEND = 5731 MORE = 647 MONEY = 6378 difference : 0
--------------------------------
$5731 + 647 = 6378$という解が求まりました。この組み合わせは別の組み合わせでも成り立つので、実行結果は別の組み合わせになったりします。また、今回は比較的早めの世代で答えが求まりましたが、ランダムな結果に依存するのでもっと多い世代が必要になったり、逆に3世代目などにすぐ答えが見つかるケースも発生します。
コード全体
from __future__ import annotations
from typing import TypeVar, List, Dict
from random import choices, random, randrange, shuffle
from heapq import nlargest
from abc import ABC, abstractmethod
from copy import deepcopy
from datetime import datetime
class Chromosome(ABC):
"""
染色体（遺伝的アルゴリズムの要素1つ分）を扱う抽象クラス。
"""
@abstractmethod
def get_fitness(self) -> float:
"""
対象の問題に対する染色体の優秀さを取得する評価関数Y用の
抽象メソッド。
Returns
-------
fitness : float
対象の問題に対する染色体の優秀さの値。高いほど問題に
適した染色体となる。
遺伝的アルゴリズムの終了判定などにも使用される。
"""
...
@classmethod
@abstractmethod
def make_random_instance(cls) -> Chromosome:
"""
ランダムな特徴（属性値）を持ったインスタンスを生成する
抽象メソッド。
Returns
-------
instance : Chromosome
生成されたインスタンス。
"""
...
@abstractmethod
def mutate(self) -> None:
"""
染色体を（突然）変異させる処理の抽象メソッド。
インスタンスの属性などのランダムな別値の設定などが実行される。
"""
...
@abstractmethod
def exec_crossover(self, other: Chromosome) -> List[Chromosome]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : Chromosome
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of Chromosome
交叉実行後に生成された2つの個体（染色体）。
"""
...
def __lt__(self, other: Chromosome) -> bool:
"""
個体間の比較で利用する、評価関数の値の小なり比較用の関数。
Parameters
----------
other : Chromosome
比較対象の他の個体。
Returns
-------
result_bool : bool
小なり条件を満たすかどうかの真偽値。
"""
return self.get_fitness() < other.get_fitness()
C = TypeVar('C', bound=Chromosome)
class GeneticAlgorithm:
SelectionType = int
SELECTION_TYPE_ROULETTE_WHEEL: SelectionType = 1
SELECTION_TYPE_TOURNAMENT: SelectionType = 2
def __init__(
self, initial_population: List[C],
threshold: float,
max_generations: int, mutation_probability: float,
crossover_probability: float,
selection_type: SelectionType) -> None:
"""
遺伝的アルゴリズムを扱うクラス。
Parameters
----------
initial_population : list of Chromosome
最初の世代の個体群（染色体群）。
threshold : float
問題解決の判定で利用するしきい値。この値を超える個体が
発生した時点で計算が終了する。
max_generations : int
アルゴリズムで実行する最大世代数。
mutation_probability : float
変異確率（0.0～1.0）。
crossover_probability : float
交叉確率（0.0～1.0）。
selection_type : int
選択方式。以下のいずれかの定数値を指定する。
- SELECTION_TYPE_ROULETTE_WHEEL
- SELECTION_TYPE_TOURNAMENT
"""
self._population: List[Chromosome] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_probability: float = mutation_probability
self._crossover_probability: float = crossover_probability
self._selection_type: int = selection_type
def _exec_roulette_wheel_selection(self) -> List[Chromosome]:
"""
ルーレット選択を行い、交叉などで利用する2つの個体（染色体）を
取得する。
Returns
-------
selected_chromosomes : list of Chromosome
選択された2つの個体（染色体）を格納したリスト。選択処理は評価関数
（fitnessメソッド）による重みが設定された状態でランダムに抽出される。
Notes
-----
評価関数の結果の値が負になる問題には利用できない。
"""
weights: List[float] = [
chromosome.get_fitness() for chromosome in self._population]
selected_chromosomes: List[Chromosome] = choices(
self._population, weights=weights, k=2)
return selected_chromosomes
def _exec_tournament_selection(self) -> List[Chromosome]:
"""
トーナメント選択を行い、交叉などで利用するための2つの個体
（染色体）を取得する。
Returns
-------
selected_chromosomes : list of Chromosome
選択された2つの個体（染色体）を格納したリスト。トーナメント
用に引数で指定された件数分抽出された中から上位の2つの個体が
設定される。
"""
participants_num: int = len(self._population) // 2
participants: List[Chromosome] = choices(self._population, k=participants_num)
selected_chromosomes: List[Chromosome] = nlargest(n=2, iterable=participants)
return selected_chromosomes
def _to_next_generation(self) -> None:
"""
次世代の個体（染色体）を生成し、個体群の属性値を生成した
次世代の個体群で置換する。
"""
new_population: List[Chromosome] = []
# 元の個体群の件数が奇数件数の場合を加味して件数の比較は等値ではなく
# 小なりの条件で判定する。
while len(new_population) < len(self._population):
parents: List[Chromosome] = self._get_parents_by_selection_type()
next_generation_chromosomes: List[Chromosome] = \
self._get_next_generation_chromosomes(parents=parents)
new_population.extend(next_generation_chromosomes)
# 2件ずつ次世代のリストを増やしていく都合、元のリストよりも件数が
# 多い場合は1件リストから取り除いてリストの件数を元のリストと一致させる。
if len(new_population) > len(self._population):
del new_population[0]
self._population = new_population
def _get_next_generation_chromosomes(
self, parents: List[Chromosome]) -> List[Chromosome]:
"""
算出された親の2つの個体のリストから、次世代として扱う
2つの個体群のリストを取得する。
一定確率で交叉や変異させ、確率を満たさない場合には引数の値が
そのまま次世代として設定される。
Parameters
----------
parents : list of Chromosome
算出された親の2つの個体のリスト
Returns
-------
next_generation_chromosomes : list of Chromosome
次世代として設定される、2つの個体を格納したリスト。
"""
random_val: float = random()
next_generation_chromosomes: List[Chromosome] = parents
if random_val < self._crossover_probability:
next_generation_chromosomes = parents[0].exec_crossover(
other=parents[1])
random_val = random()
if random_val < self._mutation_probability:
for chromosome in next_generation_chromosomes:
chromosome.mutate()
return next_generation_chromosomes
def _get_parents_by_selection_type(self) -> List[Chromosome]:
"""
選択方式に応じた親の2つの個体（染色体）のリストを取得する。
Returns
-------
parents : list of Chromosome
取得された親の2つの個体（染色体）のリスト。
Raises
------
ValueError
対応していない選択方式が指定された場合。
"""
if self._selection_type == self.SELECTION_TYPE_ROULETTE_WHEEL:
parents: List[Chromosome] = self._exec_roulette_wheel_selection()
elif self._selection_type == self.SELECTION_TYPE_TOURNAMENT:
parents = self._exec_tournament_selection()
else:
raise ValueError(
'対応していない選択方式が指定されています : %s'
% self._selection_type)
return parents
def run_algorithm(self) -> Chromosome:
"""
遺伝的アルゴリズムを実行し、実行結果の個体（染色体）のインスタンス
を取得する。
Returns
-------
betst_chromosome : Chromosome
アルゴリズム実行結果の個体。評価関数でしきい値を超えた個体
もしくはしきい値を超えない場合は指定された世代数に達した
時点で一番評価関数の値が高い個体が設定される。
"""
best_chromosome: Chromosome = \
deepcopy(self._get_best_chromosome_from_population())
for generation_idx in range(self._max_generations):
print(
datetime.now(),
f'世代数 : {generation_idx}'
f' 最良個体情報 : {best_chromosome}'
)
if best_chromosome.get_fitness() >= self._threshold:
return best_chromosome
self._to_next_generation()
currrent_generation_best_chromosome: Chromosome = \
self._get_best_chromosome_from_population()
current_gen_best_fitness: float = \
currrent_generation_best_chromosome.get_fitness()
if best_chromosome.get_fitness() < current_gen_best_fitness:
best_chromosome = deepcopy(currrent_generation_best_chromosome)
return best_chromosome
def _get_best_chromosome_from_population(self) -> Chromosome:
"""
個体群のリストから、評価関数の値が一番高い個体（染色体）を
取得する。
Returns
-------
best_chromosome : Chromosome
リスト内の評価関数の値が一番高い個体。
"""
best_chromosome: Chromosome = self._population[0]
for chromosome in self._population:
if best_chromosome.get_fitness() < chromosome.get_fitness():
best_chromosome = chromosome
return best_chromosome
class SimpleEquationProblem(Chromosome):
def __init__(self, x: int, y: int) -> None:
"""
遺伝的アルゴリズムの動作確認用の、以下のシンプルな式
6x - x^2 + 4 * y - y^2
の値が最大になるxとyの値を求める問題を扱うクラス。
（正解はx = 3, y = 2）
Parameters
----------
x : int
xの初期値。
y : int
yの初期値。
"""
self.x = x
self.y = y
def get_fitness(self) -> float:
"""
現在のxとyの値による、6x - x^2 + 4 * y - y^2 の式の計算結果の
値を取得する評価関数として利用するメソッド。
Returns
-------
fitness : int
式の計算結果の値。
"""
x: int = self.x
y: int = self.y
return 6 * x - x ** 2 + 4 * y - y ** 2
@classmethod
def make_random_instance(cls) -> SimpleEquationProblem:
"""
ランダムな初期値を与えた SimpleEquationProblem クラスの
インスタンスを生成する。
Returns
-------
problem : SimpleEquationProblem
生成されたインスタンス。xとyには0～99までの範囲でランダムな
値が設定される。
"""
x: int = randrange(100)
y: int = randrange(100)
problem = SimpleEquationProblem(x=x, y=y)
return problem
def mutate(self) -> None:
"""
個体を（突然）変異させる（乱数に応じて、xもしくはyの値を
1増減させる）。
"""
value: int = choices([1, -1], k=1)[0]
if random() > 0.5:
self.x += value
return
self.y += value
def exec_crossover(
self, other: SimpleEquationProblem
) -> List[SimpleEquationProblem]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : SimpleEquationProblem
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of SimpleEquationProblem
交叉実行後に生成された2つの個体を格納したリスト。親となる
個体それぞれから、xとyの値を半分ずつ受け継いだ個体となる。
"""
child_1: SimpleEquationProblem = deepcopy(self)
child_2: SimpleEquationProblem = deepcopy(other)
child_1.y = other.y
child_2.x = self.x
result_chromosomes: List[SimpleEquationProblem] = [
child_1, child_2,
]
return result_chromosomes
def __str__(self) -> str:
"""
個体情報の文字列を返却する。
Returns
-------
info : str
個体情報の文字列。
"""
x: int = self.x
y: int = self.y
fitness: float = self.get_fitness()
info: str = f'x = {x}, y = {y}, fitness = {fitness}'
return info
LetterDict = Dict[str, int]
class SendMoreMoneyProblem(Chromosome):
LETTERS: List[str] = ['S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y']
def __init__(self, letters_dict: LetterDict) -> None:
"""
SEND + MORE = MONEYの覆面算の問題を遺伝的アルゴリズムで
解くためのクラス。
Parameters
----------
letters_dict : LetterDict
問題で利用する8個の各文字（キー）と割り振られた数値（値）
の初期値を格納した辞書。
"""
self.letters_dict: LetterDict = letters_dict
def get_fitness(self) -> float:
"""
現在の各文字に割り振られた数値によるSEND + MOREの数値と
MONEYの数値の差分による評価関数用のメソッド。
Notes
-----
遺伝的アルゴリズムの評価関数の値が評価が高い形となるため、
誤差が大きい程数値が低くなるように調整された状態で値が
返却される。
Returns
-------
fitness : int
SEND + MOREの数値とMONEYの数値の差分による評価値。
差分が小さいほど大きな値が設定される。
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
return 1 / (difference + 1)
def _get_send_val(self) -> int:
"""
現在割り振られてい各文字の数値によるSENDの値を取得する。
Returns
-------
send_val : int
現在割り振られてい各文字の数値によるSENDの値。
"""
s: int = self.letters_dict['S']
e: int = self.letters_dict['E']
n: int = self.letters_dict['N']
d: int = self.letters_dict['D']
send_val: int = s * 1000 + e * 100 + n * 10 + d
return send_val
def _get_more_val(self) -> int:
"""
現在割り振られてい各文字の数値によるMOREの値を取得する。
Parameters
----------
more_val : int
現在割り振られてい各文字の数値によるMOREの値
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
r: int = self.letters_dict['R']
e: int = self.letters_dict['E']
more_val: int = m * 1000 + o * 100 + r * 10 + e
return more_val
def _get_money_val(self):
"""
現在割り振られている各文字の数値によるMONEYの値を取得する。
Returns
-------
money_val : int
現在割り振られている各文字の数値によるMONEYの値。
"""
m: int = self.letters_dict['M']
o: int = self.letters_dict['O']
n: int = self.letters_dict['N']
e: int = self.letters_dict['E']
y: int = self.letters_dict['Y']
money_val = m * 10000 + o * 1000 + n * 100 + e * 10 + y
return money_val
@classmethod
def make_random_instance(cls) -> SendMoreMoneyProblem:
"""
ランダムな初期値を与えた SendMoreMoneyProblem クラスの
インスタンスを生成する。
Returns
-------
problem : SendMoreMoneyProblem
生成されたインスタンス。各文字には0～9までの範囲で
数値が重複しない形で値が設定される。
"""
num_list: List[int] = list(range(10))
shuffle(num_list)
num_list = num_list[:len(cls.LETTERS)]
letters_dict: LetterDict = {
char: num for (char, num) in zip(cls.LETTERS, num_list)}
problem: SendMoreMoneyProblem = SendMoreMoneyProblem(
letters_dict=letters_dict)
return problem
def mutate(self) -> None:
"""
個体を（突然）変異させる（ランダムに特定の文字の値を割り振られて
いない数値で差し替える）。
"""
target_char: str = choices(self.LETTERS, k=1)[0]
not_assigned_num: int = self._get_not_assigned_num()
self.letters_dict[target_char] = not_assigned_num
def _get_not_assigned_num(self) -> int:
"""
各文字に割り振られていない数字を取得する。
Returns
-------
not_assigned_num : int
各文字に割り振られていない数字。文字は8文字な一方で、
数字は0～9の10個なので、2個割り振られていない数値が存在し、
その中から1つが設定される。
"""
values: list = list(self.letters_dict.values())
not_assigned_num: int = -1
for num in range(10):
if num in values:
continue
not_assigned_num = num
break
return not_assigned_num
def exec_crossover(
self,
other: SendMoreMoneyProblem) -> List[SendMoreMoneyProblem]:
"""
引数に指定された別の個体を参照し交叉を実行する。
Parameters
----------
other : SendMoreMoneyProblem
交叉で利用する別の個体。
Returns
-------
result_chromosomes : list of SendMoreMoneyProblem
交叉実行後に生成された2つの個体を格納したリスト。
"""
child_1: SendMoreMoneyProblem = deepcopy(self)
child_2: SendMoreMoneyProblem = deepcopy(other)
for char in ('S', 'E', 'N', 'D'):
child_2.letters_dict[char] = self.\
_get_not_assigned_num_from_parent(
child=child_2,
parent=self,
)
for char in ('M', 'O', 'R', 'Y'):
child_1.letters_dict[char] = \
self._get_not_assigned_num_from_parent(
child=child_1,
parent=other,
)
result_chromosomes = [child_1, child_2]
return result_chromosomes
def _get_not_assigned_num_from_parent(
self, child: SendMoreMoneyProblem,
parent: SendMoreMoneyProblem) -> int:
"""
親に設定されている数値の中で、まだ子に設定されていない数値を
取得する。
Notes
-----
親と子の数値の組み合わせ次第では選択できる値が見つからないケース
があるので、その場合は0～9の値の中で割り振られていない数値が
設定される。
Parameters
----------
child : SendMoreMoneyProblem
子の個体。
parent : SendMoreMoneyProblem
親の個体。
Returns
-------
not_assigned_num : int
算出されたまだ割り振られていない数値。
"""
not_assigned_num: int = -1
for parent_num in parent.letters_dict.values():
child_nums: list = list(child.letters_dict.values())
if parent_num in child_nums:
continue
not_assigned_num = parent_num
if not_assigned_num == -1:
not_assigned_num = self._get_not_assigned_num()
return not_assigned_num
def __str__(self) -> str:
"""
個体情報の文字列を返却する。
Returns
-------
info : str
個体情報の文字列。
"""
send_val: int = self._get_send_val()
more_val: int = self._get_more_val()
money_val: int = self._get_money_val()
difference: int = abs(money_val - (send_val + more_val))
info: str = (
f"\nS = {self.letters_dict['S']}"
f" E = {self.letters_dict['E']}"
f" N = {self.letters_dict['N']}"
f" D = {self.letters_dict['D']}"
f"\nM = {self.letters_dict['M']}"
f" O = {self.letters_dict['O']}"
f" R = {self.letters_dict['R']}"
f" Y = {self.letters_dict['Y']}"
f'\nSEND = {send_val}'
f' MORE = {more_val}'
f' MONEY = {money_val}'
f' difference : {difference}'
'\n--------------------------------'
)
return info
if __name__ == '__main__':
simple_equation_initial_population: List[SimpleEquationProblem] = \
[SimpleEquationProblem.make_random_instance() for _ in range(30)]
ga: GeneticAlgorithm = GeneticAlgorithm(
initial_population=simple_equation_initial_population,
threshold=13,
max_generations=100,
mutation_probability=0.2,
crossover_probability=0.3,
selection_type=GeneticAlgorithm.SELECTION_TYPE_TOURNAMENT)
_ = ga.run_algorithm()
send_more_money_initial_population: List[SendMoreMoneyProblem] = \
[SendMoreMoneyProblem.make_random_instance() for _ in range(1000)]
ga = GeneticAlgorithm(
initial_population=send_more_money_initial_population,
threshold=1.0,
max_generations=1000,
mutation_probability=0.7,
crossover_probability=0.2,
selection_type=GeneticAlgorithm.SELECTION_TYPE_ROULETTE_WHEEL)
_ = ga.run_algorithm()