PythonのライブラリDEAPを使えば、簡単に遺伝的アルゴリズム(GA)によるシミュレーションを行うことが出来る。その際に、最適解に関してある程度事前知識があり計算時間を短縮したいなどの事情により初期集団を固定したい場合がある。
例えばこちらの例のように機械学習の特徴量選択に応用する際、これまで試行したベストモデルからスタートしたいというケースが考えられる。100~数百であれば初期値設定は不要だが、後先考えずに10万程度の特徴量を機械的に作ってしまった人間には需要がある。
その様な場合の対応方法は公式ドキュメントにも案内があるが、実際にテストした情報がウェブ上にあまりないのでここに記載しておく。
公式ドキュメントのOne-Maxモデルによる実験
0or1からなる配列の合計値を評価関数とし、最大化するGAの実装
最適解は全て1の配列、評価関数の最大値が配列の長さとなる
http://deap.gel.ulaval.ca/doc/default/examples/ga_onemax.html
http://deap.gel.ulaval.ca/doc/default/examples/ga_onemax_short.html
1. 公式ドキュメント通りのランダムな初期集団からのGA
# ライブラリインポート
import numpy as np
import random
from deap import algorithms
from deap import base
from deap import creator
from deap import tools
1-1. 評価関数作成
0or1からなる100要素の配列の合計値
def evalOneMax(individual):
return sum(individual), #返り値が一つでもコンマを付ける
1-2. Creatorの作成
createでcreatorにFitnessMax、Individualメソッドを追加。
weights=(1.0,)とすることで評価関数の最大化を評価する。
creator.create("FitnessMax", base.Fitness, weights=(1.0,)) #引数が一つでもコンマを付ける
creator.create("Individual", list, fitness=creator.FitnessMax)
1-3. toolboxの作成
resisterでtoolboxに第一変数の名前のメソッドを追加する。
toolbox.attr_bool: random.randint(0,1)
toolbox.individual: toolbox.attr_boolを使って01乱数 > tools.initRepeatによって100回繰り返し100要素のリストを作成(=個体生成)
toolbox.polulation: toolbox.individualによる個体生成を繰り返し、個体集団作成
del toolbox
toolbox = base.Toolbox()
# Attribute generator
toolbox.register("attr_bool", random.randint, 0.0, 1.0)
# Structure initializers
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
続いてalgorithms.eaMuPlusLambdaによるGA実行に必要なメソッド
toolbox.evaluate(評価), toolbox.mate(交叉), toolbox.mutate(変異), toolbox.select(選別)を定義する。
deap.toolsを使って下のように書ける。
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selNSGA2)
1-4. statsおよび初期集団作成
pop: 初期集団
hof: ベスト個体の保存
stats: 集団の評価関数の統計値の保存
"""遺伝的アルゴリズム設定
NGEN 世代まで
1世代の個体数 LAMBDA
次世代に引き継ぐ個体数 MU
交叉確率 CXPB
突然変異確率 MUTPB
"""
random.seed(4)
NGEN = 10
MU = 50
LAMBDA = 100
CXPB = 0.7
MUTPB = 0.3
#個体集団作成
pop = toolbox.population(n=MU)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean, axis=0)
stats.register("std", np.std, axis=0)
stats.register("min", np.min, axis=0)
stats.register("max", np.max, axis=0)
1-5. algorithms.eaMuPlusLambdaによるGA実行
pop, log = algorithms.eaMuPlusLambda(pop,
toolbox,
mu=MU,
lambda_=LAMBDA,
cxpb=CXPB,
mutpb=MUTPB,
ngen=NGEN,
stats=stats,
halloffame=hof)
gen nevals avg std min max
0 50 [50.32] [4.71355492] [41.] [63.]
1 100 [56.] [2.02977831] [53.] [63.]
2 100 [59.3] [2.3] [57.] [68.]
3 100 [62.56] [2.03135423] [60.] [69.]
4 100 [65.58] [1.96051014] [63.] [72.]
5 100 [68.46] [1.52590956] [66.] [73.]
6 100 [70.4] [1.34164079] [69.] [74.]
7 100 [72.36] [1.10923397] [71.] [76.]
8 100 [74.06] [1.06602064] [73.] [77.]
9 100 [75.38] [0.79724526] [74.] [77.]
10 100 [76.36] [0.62481997] [76.] [78.]
乱数でスタートしたので、初期個体の評価値は41~63におさまっている。
10世代では収束していないが、収束させるのが目的ではないので別にOK。
2. 自分で初期集団を定義する方法
初期集団をある特定の値に固定して始めたい場合、公式ドキュメントの該当箇所を以下のように書き換える。
2-1. 自作初期集団の用意
自作初期集団=個体のリストを作成する。
例えば全て0で構成される個体のクローン集団L00から遺伝的アルゴリズムを始めたい場合は以下の様になる。
MU = 50
# individual
L0 = [0] * 100
# list of individuals
L00 = [L0] * MU
2-2. creatorの作成
1-2と同じ。
2-3. toolboxの作成
toolbox.population に代わるメソッドtoolbox.population_guessを定義する。
toolbox = base.Toolbox()
# population_guessで使う関数
def initPopulation(pcls, ind_init, file):
return pcls(ind_init(c) for c in file)
# population_guessメソッドの作成
# creator.Individualによって各個体にFitnessを追加する
toolbox.register("population_guess", initPopulation, list, creator.Individual, L00)
# ここは一緒
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selNSGA2)
2-4. 初期集団作成
hofやstatは同じなので省略
#初期個体生成をpopulation_guessに変える
#pop = toolbox.population(n=MU)
pop = toolbox.population_guess()
2-5. algorithms.eaMuPlusLambdaによるGA実行
pop, log = algorithms.eaMuPlusLambda(pop,
toolbox,
mu=MU,
lambda_=LAMBDA,
cxpb=CXPB,
mutpb=MUTPB,
ngen=NGEN,
stats=stats,
halloffame=hof)
gen nevals avg std min max
0 50 [0.] [0.] [0.] [0.]
1 100 [3.54] [3.04111822] [0.] [9.]
2 100 [8.3] [2.0808652] [6.] [15.]
3 100 [12.4] [2.45764115] [10.] [21.]
4 100 [16.38] [1.92758917] [14.] [22.]
5 100 [20.36] [2.10485154] [18.] [29.]
6 100 [24.52] [1.5651198] [22.] [29.]
7 100 [28.02] [1.74917123] [26.] [33.]
8 100 [31.3] [2.21133444] [29.] [39.]
9 100 [35.] [1.69705627] [33.] [40.]
10 100 [38.16] [1.71300905] [36.] [43.]
評価値の最小値０、最大値０の集団 = 自作の初期集団からGAを始めることができた。