遺伝的アルゴリズム（Genetic Algorithm, GA）
遺伝的アルゴリズム（Genetic Algorithm, GA）とは？
遺伝的アルゴリズム（Genetic Algorithm, GA）は、自然選択や生物の進化を模倣したアルゴリズムの一種です。
遺伝的アルゴリズムは以下のステップで進行します：
初期個体群の生成：ランダムにソリューションの初期集団を生成します。
適応度の評価：各ソリューションの適応度を評価します。
選択：適応度に基づいて、次世代に引き継がれる個体を選択します。
交叉（クロスオーバー）：選択された個体からランダムにペアを作り、交叉を行い新たな個体を生成します。
突然変異：低確率で個体の一部をランダムに変化させます。
新世代の生成：交叉と突然変異を経て、新しい個体群が形成されます。
終了条件のチェック：特定の世代に達するか、十分な解が得られるまで繰り返します。
この記事では、Pythonで簡単な最適化問題を通して遺伝的アルゴリズムを実装してみます。
環境はGoogle Corabです。
インストール
!pip install deapDEAPをインストールします。遺伝的アルゴリズムのライブラリの一つに「DEAP」というライブラリがあります。今回はこちらを利用します。
ライブラリのインポート
import random
import numpy
from deap import base, creator, tools, algorithms最適化問題の設定
今回の最適化問題は各個体が10個の整数の和が100に最も近い値を目指すという簡単な問題を設定しました。目標値の100と整数の和の差を適応度として、差を小さくしていく最小化問題として個体と適応度の設定を行なっていきます。
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)DEAPではcreatorを使用して遺伝的アルゴリズムの実装に必要な個体と適応度の設定を行うことができます。FitnessMinは、base.Fitness を継承して新しい適応度のクラスを作成しています。適応度を評価するために使用されます。weights=(-1.0,)は適応度の評価が最小化問題であることを示しています。Individualは、個体の設定です。生成される個体がFitnessMinを適応度として持つ事になります。
個体の生成方法を設定
toolbox = base.Toolbox()遺伝的アルゴリズムの個体の生成、選択、交叉、突然変異といった操作はこのToolboxクラスを利用します。
toolbox.register("attribute", random.randint, 1, 10)個体の属性（attribute）を1から10の間のランダムな整数で生成しています。
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attribute, n=10)creator.Individualを個体のクラスとして使用し、toolbox.attribute を属性生成関数として使い、それを10回繰り返して個体を生成します。
これによって個体の各遺伝子が1から10のランダムな整数で構成されます。
toolbox.register("population", tools.initRepeat, list, toolbox.individual)個体群を生成する方法を定義しています。
リスト（個体群）に個体を追加する形で個体群を生成します。
評価
def evaluate(individual):
return (abs(100 - sum(individual)),)
toolbox.register("evaluate", evaluate)evaluate は個体の適応度を計算するための関数です。
目標値の100にどれだけ近いかを計算し、その差の絶対値を適応度としています。目的は差を0に近づけることです。
交叉（クロスオーバー）
toolbox.register("mate", tools.cxTwoPoint)tools.cxTwoPoint は二点交叉を行う関数です。これは、二つの親個体からランダムに二点を選び、それらの間の遺伝子を交換して新しい子供個体を生成します。
突然変異
toolbox.register("mutate", tools.mutUniformInt, low=1, up=10, indpb=0.2)tools.mutUniformInt は、個体の各遺伝子を一定の確率（indpb = 0.2、すなわち各遺伝子に対して20%の確率）で突然変異させます。この突然変異は、指定された範囲（low=1, up=10）内のランダムな整数によって遺伝子が置き換えられます。
選択
toolbox.register("select", tools.selTournament, tournsize=3)tools.selTournament はトーナメント選択を行う関数です。この方法では、個体群からランダムに3個体（tournsize=3）を選び、その中から最も適応度の高い個体を次世代に選択します。
アルゴリズムの実行
random.seed(42)
population = toolbox.population(n=300)
hof = tools.HallOfFame(1)toolbox.population 関数は、登録された個体生成関数を使用して個体群を初期化します。ここでは300個の個体からなる個体群を生成しています。
toolbox.HallOfFame （殿堂）は、最も優れた1個体を保存する設定となっています。
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", numpy.min)tools.Statistics を使って、個体群の適応度に関する統計情報を収集します。ここで登録されているのは適応度の最小値です。
population, log = algorithms.eaSimple(population, toolbox, cxpb=0.5, mutpb=0.2, ngen=40,
stats=stats, halloffame=hof, verbose=True)
best_ind = hof.items[0]
print("最も適応度の高い個体:", best_ind, "適応度:", best_ind.fitness.values[0])それではアルゴリズムの実行を行います。algorithms.eaSimple は、シンプルな遺伝的アルゴリズムの一形態を実行します。cxpb は交叉確率、mutpb は突然変異確率を指し、ngen は世代数です。
アルゴリズムの実行の結果、下記が出力されます。
最も適応度の高い個体: [10, 10, 10, 10, 10, 10, 10, 10, 10, 10] 適応度: 0.0
また実行中に下記のようにログ出力が行われます。
gen nevals min
0 300 15
1 191 15
2 175 14
3 180 12
4 190 10
5 178 10
6 177 7
7 178 4
8 186 3
9 190 3
10 188 2
11 196 1
12 180 1
13 179 0
14 152 0
15 170 0
16 185 0
17 168 0
18 175 0
19 194 0
20 152 0
21 186 0
22 176 0
23 196 0
24 189 0
25 178 0
26 190 0
27 176 0
28 173 0
29 177 0
30 194 0
31 167 0
32 188 0
33 185 0
34 162 0
35 175 0
36 189 0
37 184 0
38 177 0
39 179 0
40 180 0 遺伝的アルゴリズムが40世代にわたって実行された結果を示しています。
最小適応度（min）は最初の世代で15でしたが、世代が進むにつれて改善されていき、13世代目で0に達していることがわかります。