Python でゼロから構築する進化戦略
進化戦略は、確率論的なグローバル最適化アルゴリズムです。
これは、遺伝的アルゴリズムなどの他のアルゴリズムに関連する進化的アルゴリズムですが、連続関数の最適化に特化して設計されています。
このチュートリアルでは、進化戦略の最適化アルゴリズムを実装する方法を学びます。
このチュートリアルを完了すると、次のことがわかります。
- Evolution Strategies は、自然選択による進化の生物学的理論に触発された確率的グローバル最適化アルゴリズムです。
- Evolution Strategies には標準用語があり、(mu, lambda)-ES および (mu + lambda)-ES と呼ばれる 2 つの一般的なバージョンのアルゴリズムがあります。
- Evolution Strategies アルゴリズムを実装して連続目的関数に適用する方法。
私の新しい本『Optimization for Machine Learning』 でプロジェクトをキックスタートします。これにはステップバイステップのチュートリアルとすべてのPython ソース コード ファイルが含まれています。例。
チュートリアルの概要
このチュートリアルは 3 つの部分に分かれています。彼らです:
- 進化戦略
- (mu, lambda)-ES を開発する
- (mu + lambda)-ES を開発する
進化戦略
Evolution Strategies (単数形) または ES とも呼ばれる Evolution Strategies は、確率的グローバル最適化アルゴリズムです。
この技術は 1960 年代に開発され、風洞内で空気抵抗を最小限に抑える設計のためにエンジニアが手動で実装しました。
Evolution Strategies (ES) として知られる一連のアルゴリズムは、1960 年代半ばにベルリン工科大学の Ingo Rechenberg と Hans-Paul Schwefel によって開発されました。
— 31 ページ、『メタヒューリスティックスの要点』、2011 年。
Evolution Strategies は進化アルゴリズムの一種で、自然選択による進化の生物学的理論にインスピレーションを得ています。他の進化的アルゴリズムとは異なり、いかなる形式のクロスオーバーも使用しません。代わりに、候補解の変更は突然変異演算子に限定されます。このように、進化戦略は一種の並行確率的山登りと考えることができます。
このアルゴリズムには、最初にランダムに生成される候補解の母集団が含まれます。アルゴリズムの各反復では、最初に解の母集団を評価し、次に、切り捨て選択と呼ばれる、最良の解のサブセットを除くすべてを削除します。残りの解 (親) はそれぞれ、多数の新しい候補解 (突然変異) を生成するための基礎として使用され、アルゴリズム (生成) の次の反復で考慮される母集団内の位置をめぐって親と置き換わったり、親と競合したりします。
この手順にはさまざまなバリエーションがあり、アルゴリズムを要約するための標準用語があります。母集団のサイズはラムダと呼ばれ、各反復で選択される親の数はミューと呼ばれます。
それぞれの親から作成される子の数は (lambda/mu) として計算され、割り算に剰余がないようにパラメータを選択する必要があります。
- mu: 各反復で選択された親の数。
- ラムダ: 人口のサイズ。
- lambda/mu: 選択した各親から生成される子の数。
括弧表記はアルゴリズム構成を記述するために使用されます。 (mu、ラムダ)-ES。たとえば、mu=5 と lambda=20 の場合、(5, 20)-ES として要約されます。 mu パラメータと lambda パラメータを区切るカンマ (,) は、アルゴリズムの反復ごとに子が親を直接置き換えることを示します。
- (mu, lambda)-ES: 子が親に取って代わる進化戦略のバージョン。
mu パラメーターと lambda パラメーターがプラス (+) で区切られている場合は、子と親が一緒になって次の反復の母集団を定義することを示します。
- (mu + ラムダ)-ES: 子と親が集団に追加される進化戦略のバージョン。
確率的山登りアルゴリズムは進化戦略として実装でき、(1 + 1)-ES という表記になります。
これは類似または標準的な ES アルゴリズムであり、文献には多くの拡張機能やバリアントが記載されています。
進化戦略について理解したので、アルゴリズムの実装方法を検討してみましょう。
(mu, lambda)-ES を開発する
このセクションでは、(mu, lambda)-ES、つまり子が親を置き換えるバージョンのアルゴリズムを開発します。
まず、アルゴリズムを実装するための基礎として、難しい最適化問題を定義しましょう。
Ackley 関数は、ローカル検索が行き詰まる可能性がある単一のグローバル最適値と複数のローカル最適値を持つマルチモーダル目的関数の例です。
したがって、全体的な最適化手法が必要になります。これは、[0,0] にグローバル最適値を持ち、0.0 と評価される 2 次元の目的関数です。
以下の例では、Ackley を実装し、大域最適値と複数の局所最適値を示す 3 次元曲面プロットを作成します。
# ackley multimodal function
from numpy import arange
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D
# objective function
def objective(x, y):
return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20
# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()
この例を実行すると、膨大な数の局所最適値を示す Ackley 関数の曲面プロットが作成されます。
ランダムな候補解と、既存の候補解の修正バージョンを生成します。すべての候補解が検索問題の範囲内にあることが重要です。
これを実現するために、候補解が検索範囲内にあるかどうかを確認し、範囲外の場合は候補を破棄し、別の解を生成する関数を開発します。
以下の in_bounds() 関数は、候補解 (ポイント) と検索空間の境界の定義 (境界) を受け取り、解が検索範囲内にある場合は True を返し、それ以外の場合は False を返します。 。
# check if a point is within the bounds of the search
def in_bounds(point, bounds):
# enumerate all dimensions of the point
for d in range(len(bounds)):
# check if out of bounds for this dimension
if point[d] < bounds[d, 0] or point[d] > bounds[d, 1]:
return False
return True
この関数は、「ラム」 (ラムダ など) ランダム候補解の初期母集団を生成するときに使用できます。
例えば:
...
# initial population
population = list()
for _ in range(lam):
candidate = None
while candidate is None or not in_bounds(candidate, bounds):
candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
population.append(candidate)
次に、アルゴリズムを固定回数繰り返します。各反復では、まず母集団内の各候補解を評価します。
スコアを計算し、別の並列リストに保存します。
...
# evaluate fitness for the population
scores = [objective(c) for c in population]
次に、目的関数を最小化しているため、最高スコア (この場合は最低スコア) を持つ「mu」親を選択する必要があります。
これを 2 つのステップで行います。まず、スコアに基づいて候補ソリューションを昇順にランク付けし、スコアが最も低いソリューションのランクが 0、次のソリューションのランクが 1 になるようにします。これを実現するには、argsort 関数の二重呼び出しを使用します。
次に、ランクを使用して、値「mu」よりも低いランクを持つ親を選択します。これは、5 つの親を選択するために mu を 5 に設定すると、ランクが 0 ~ 4 の親のみが選択されることを意味します。
...
# rank scores in ascending order
ranks = argsort(argsort(scores))
# select the indexes for the top mu ranked solutions
selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
次に、選択した親ごとに子を作成できます。
まず、親ごとに作成する子の合計数を計算する必要があります。
...
# calculate the number of children per parent
n_children = int(lam / mu)
次に、各親を反復処理して、それぞれの修正バージョンを作成できます。
確率的山登りで使用されるのと同様の手法を使用して子を作成します。具体的には、現在の値を平均とし、「ステップ サイズ」ハイパーパラメータとして提供される標準偏差を持つガウス分布を使用して各変数がサンプリングされます。
...
# create children for parent
for _ in range(n_children):
child = None
while child is None or not in_bounds(child, bounds):
child = population[i] + randn(len(bounds)) * step_size
また、検索の最後に最適なソリューションを返すことができるように、選択した各親がこれまでに確認された最適なソリューションよりも優れているかどうかを確認することもできます。
...
# check if this parent is the best solution ever seen
if scores[i] < best_eval:
best, best_eval = population[i], scores[i]
print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
作成された子はリストに追加でき、アルゴリズムの反復の最後に母集団を子のリストに置き換えることができます。
...
# replace population with children
population = children
これらすべてを、進化戦略アルゴリズムのカンマ バージョンを実行する es_comma() という名前の関数に結合できます。
この関数は、目的関数の名前、検索空間の境界、反復回数、ステップ サイズ、および mu および lambda ハイパーパラメーターを受け取り、検索とその評価中に見つかった最適な解を返します。
# evolution strategy (mu, lambda) algorithm
def es_comma(objective, bounds, n_iter, step_size, mu, lam):
best, best_eval = None, 1e+10
# calculate the number of children per parent
n_children = int(lam / mu)
# initial population
population = list()
for _ in range(lam):
candidate = None
while candidate is None or not in_bounds(candidate, bounds):
candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
population.append(candidate)
# perform the search
for epoch in range(n_iter):
# evaluate fitness for the population
scores = [objective(c) for c in population]
# rank scores in ascending order
ranks = argsort(argsort(scores))
# select the indexes for the top mu ranked solutions
selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
# create children from parents
children = list()
for i in selected:
# check if this parent is the best solution ever seen
if scores[i] < best_eval:
best, best_eval = population[i], scores[i]
print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
# create children for parent
for _ in range(n_children):
child = None
while child is None or not in_bounds(child, bounds):
child = population[i] + randn(len(bounds)) * step_size
children.append(child)
# replace population with children
population = children
return [best, best_eval]
次に、このアルゴリズムを Ackley 目的関数に適用できます。
アルゴリズムを 5,000 回反復実行し、検索空間でステップ サイズ 0.15 を使用します。 20 個の親 (mu) を選択して 100 個の母集団サイズ (ラムダ) を使用します。これらのハイパーパラメータは、少しの試行錯誤を経て選択されました。
検索の最後に、検索中に見つかった最適なソリューション候補をレポートします。
...
# seed the pseudorandom number generator
seed(1)
# define range for input
bounds = asarray([[-5.0, 5.0], [-5.0, 5.0]])
# define the total iterations
n_iter = 5000
# define the maximum step size
step_size = 0.15
# number of parents selected
mu = 20
# the number of children generated by parents
lam = 100
# perform the evolution strategy (mu, lambda) search
best, score = es_comma(objective, bounds, n_iter, step_size, mu, lam)
print('Done!')
print('f(%s) = %f' % (best, score))
これを結合して、Evolution Strategies アルゴリズムのコンマ バージョンを Ackley 目的関数に適用する完全な例を以下に示します。
# evolution strategy (mu, lambda) of the ackley objective function
from numpy import asarray
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import argsort
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed
# objective function
def objective(v):
x, y = v
return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20
# check if a point is within the bounds of the search
def in_bounds(point, bounds):
# enumerate all dimensions of the point
for d in range(len(bounds)):
# check if out of bounds for this dimension
if point[d] < bounds[d, 0] or point[d] > bounds[d, 1]:
return False
return True
# evolution strategy (mu, lambda) algorithm
def es_comma(objective, bounds, n_iter, step_size, mu, lam):
best, best_eval = None, 1e+10
# calculate the number of children per parent
n_children = int(lam / mu)
# initial population
population = list()
for _ in range(lam):
candidate = None
while candidate is None or not in_bounds(candidate, bounds):
candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
population.append(candidate)
# perform the search
for epoch in range(n_iter):
# evaluate fitness for the population
scores = [objective(c) for c in population]
# rank scores in ascending order
ranks = argsort(argsort(scores))
# select the indexes for the top mu ranked solutions
selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
# create children from parents
children = list()
for i in selected:
# check if this parent is the best solution ever seen
if scores[i] < best_eval:
best, best_eval = population[i], scores[i]
print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
# create children for parent
for _ in range(n_children):
child = None
while child is None or not in_bounds(child, bounds):
child = population[i] + randn(len(bounds)) * step_size
children.append(child)
# replace population with children
population = children
return [best, best_eval]
# seed the pseudorandom number generator
seed(1)
# define range for input
bounds = asarray([[-5.0, 5.0], [-5.0, 5.0]])
# define the total iterations
n_iter = 5000
# define the maximum step size
step_size = 0.15
# number of parents selected
mu = 20
# the number of children generated by parents
lam = 100
# perform the evolution strategy (mu, lambda) search
best, score = es_comma(objective, bounds, n_iter, step_size, mu, lam)
print('Done!')
print('f(%s) = %f' % (best, score))
この例を実行すると、候補ソリューションがレポートされ、より良いソリューションが見つかるたびにスコアが付けられ、検索の最後に見つかった最適なソリューションがレポートされます。
注: アルゴリズムや評価手順の確率的性質、または数値精度の違いにより、結果が異なる場合があります。例を数回実行して、平均結果を比較することを検討してください。
この場合、検索中に約 22 回のパフォーマンスの向上が見られ、最適なソリューションが最適値に近いことがわかります。
間違いなく、このソリューションは、ES のようなグローバル最適化アルゴリズムを使用する場合の一般的な手法である、ローカル検索アルゴリズムをさらに改良するための出発点として提供できます。
0, Best: f([-0.82977995 2.20324493]) = 6.91249
0, Best: f([-1.03232526 0.38816734]) = 4.49240
1, Best: f([-1.02971385 0.21986453]) = 3.68954
2, Best: f([-0.98361735 0.19391181]) = 3.40796
2, Best: f([-0.98189724 0.17665892]) = 3.29747
2, Best: f([-0.07254927 0.67931431]) = 3.29641
3, Best: f([-0.78716147 0.02066442]) = 2.98279
3, Best: f([-1.01026218 -0.03265665]) = 2.69516
3, Best: f([-0.08851828 0.26066485]) = 2.00325
4, Best: f([-0.23270782 0.04191618]) = 1.66518
4, Best: f([-0.01436704 0.03653578]) = 0.15161
7, Best: f([0.01247004 0.01582657]) = 0.06777
9, Best: f([0.00368129 0.00889718]) = 0.02970
25, Best: f([ 0.00666975 -0.0045051 ]) = 0.02449
33, Best: f([-0.00072633 -0.00169092]) = 0.00530
211, Best: f([2.05200123e-05 1.51343187e-03]) = 0.00434
315, Best: f([ 0.00113528 -0.00096415]) = 0.00427
418, Best: f([ 0.00113735 -0.00030554]) = 0.00337
491, Best: f([ 0.00048582 -0.00059587]) = 0.00219
704, Best: f([-6.91643854e-04 -4.51583644e-05]) = 0.00197
1504, Best: f([ 2.83063223e-05 -4.60893027e-04]) = 0.00131
3725, Best: f([ 0.00032757 -0.00023643]) = 0.00115
Done!
f([ 0.00032757 -0.00023643]) = 0.001147
進化戦略のコンマ バージョンの実装方法は理解できたので、プラス バージョンを実装する方法を見てみましょう。
(mu + lambda)-ES を開発する
Evolution Strategies アルゴリズムのプラス バージョンは、コンマ バージョンと非常に似ています。
主な違いは、最終的に子供だけではなく、子供と親が人口を構成することです。これにより、アルゴリズムの次の反復で親が子と選択を競うことができます。
これにより、検索アルゴリズムによるより貪欲な動作が発生し、局所最適 (準最適解) への早期収束が発生する可能性があります。利点は、アルゴリズムが、見つかった優れた候補ソリューションを活用し、その地域内の候補ソリューションに重点を置いて、さらなる改善を発見できる可能性があることです。
子の作成時に母集団に親を追加する関数を変更することで、アルゴリズムのプラス バージョンを実装できます。
...
# keep the parent
children.append(population[i])
この追加と新しい名前 es_plus() が追加された関数の更新バージョンを以下に示します。
# evolution strategy (mu + lambda) algorithm
def es_plus(objective, bounds, n_iter, step_size, mu, lam):
best, best_eval = None, 1e+10
# calculate the number of children per parent
n_children = int(lam / mu)
# initial population
population = list()
for _ in range(lam):
candidate = None
while candidate is None or not in_bounds(candidate, bounds):
candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
population.append(candidate)
# perform the search
for epoch in range(n_iter):
# evaluate fitness for the population
scores = [objective(c) for c in population]
# rank scores in ascending order
ranks = argsort(argsort(scores))
# select the indexes for the top mu ranked solutions
selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
# create children from parents
children = list()
for i in selected:
# check if this parent is the best solution ever seen
if scores[i] < best_eval:
best, best_eval = population[i], scores[i]
print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
# keep the parent
children.append(population[i])
# create children for parent
for _ in range(n_children):
child = None
while child is None or not in_bounds(child, bounds):
child = population[i] + randn(len(bounds)) * step_size
children.append(child)
# replace population with children
population = children
return [best, best_eval]
このバージョンのアルゴリズムは、前のセクションで使用したのと同じハイパーパラメーターを使用して Ackley 目的関数に適用できます。
完全な例を以下に示します。
# evolution strategy (mu + lambda) of the ackley objective function
from numpy import asarray
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import argsort
from numpy.random import randn
from numpy.random import rand
from numpy.random import seed
# objective function
def objective(v):
x, y = v
return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20
# check if a point is within the bounds of the search
def in_bounds(point, bounds):
# enumerate all dimensions of the point
for d in range(len(bounds)):
# check if out of bounds for this dimension
if point[d] < bounds[d, 0] or point[d] > bounds[d, 1]:
return False
return True
# evolution strategy (mu + lambda) algorithm
def es_plus(objective, bounds, n_iter, step_size, mu, lam):
best, best_eval = None, 1e+10
# calculate the number of children per parent
n_children = int(lam / mu)
# initial population
population = list()
for _ in range(lam):
candidate = None
while candidate is None or not in_bounds(candidate, bounds):
candidate = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
population.append(candidate)
# perform the search
for epoch in range(n_iter):
# evaluate fitness for the population
scores = [objective(c) for c in population]
# rank scores in ascending order
ranks = argsort(argsort(scores))
# select the indexes for the top mu ranked solutions
selected = [i for i,_ in enumerate(ranks) if ranks[i] < mu]
# create children from parents
children = list()
for i in selected:
# check if this parent is the best solution ever seen
if scores[i] < best_eval:
best, best_eval = population[i], scores[i]
print('%d, Best: f(%s) = %.5f' % (epoch, best, best_eval))
# keep the parent
children.append(population[i])
# create children for parent
for _ in range(n_children):
child = None
while child is None or not in_bounds(child, bounds):
child = population[i] + randn(len(bounds)) * step_size
children.append(child)
# replace population with children
population = children
return [best, best_eval]
# seed the pseudorandom number generator
seed(1)
# define range for input
bounds = asarray([[-5.0, 5.0], [-5.0, 5.0]])
# define the total iterations
n_iter = 5000
# define the maximum step size
step_size = 0.15
# number of parents selected
mu = 20
# the number of children generated by parents
lam = 100
# perform the evolution strategy (mu + lambda) search
best, score = es_plus(objective, bounds, n_iter, step_size, mu, lam)
print('Done!')
print('f(%s) = %f' % (best, score))
この例を実行すると、候補ソリューションがレポートされ、より良いソリューションが見つかるたびにスコアが付けられ、検索の最後に見つかった最適なソリューションがレポートされます。
注: アルゴリズムや評価手順の確率的性質、または数値精度の違いにより、結果が異なる場合があります。例を数回実行して、平均結果を比較することを検討してください。
この場合、検索中に約 24 のパフォーマンスの向上が見られたことがわかります。また、この目的関数のコンマ バージョンで見つかった 0.001147 と比較して、評価 0.000532 でより良い最終解が見つかったこともわかります。
0, Best: f([-0.82977995 2.20324493]) = 6.91249
0, Best: f([-1.03232526 0.38816734]) = 4.49240
1, Best: f([-1.02971385 0.21986453]) = 3.68954
2, Best: f([-0.96315064 0.21176994]) = 3.48942
2, Best: f([-0.9524528 -0.19751564]) = 3.39266
2, Best: f([-1.02643442 0.14956346]) = 3.24784
2, Best: f([-0.90172166 0.15791013]) = 3.17090
2, Best: f([-0.15198636 0.42080645]) = 3.08431
3, Best: f([-0.76669476 0.03852254]) = 3.06365
3, Best: f([-0.98979547 -0.01479852]) = 2.62138
3, Best: f([-0.10194792 0.33439734]) = 2.52353
3, Best: f([0.12633886 0.27504489]) = 2.24344
4, Best: f([-0.01096566 0.22380389]) = 1.55476
4, Best: f([0.16241469 0.12513091]) = 1.44068
5, Best: f([-0.0047592 0.13164993]) = 0.77511
5, Best: f([ 0.07285478 -0.0019298 ]) = 0.34156
6, Best: f([-0.0323925 -0.06303525]) = 0.32951
6, Best: f([0.00901941 0.0031937 ]) = 0.02950
32, Best: f([ 0.00275795 -0.00201658]) = 0.00997
109, Best: f([-0.00204732 0.00059337]) = 0.00615
195, Best: f([-0.00101671 0.00112202]) = 0.00434
555, Best: f([ 0.00020392 -0.00044394]) = 0.00139
2804, Best: f([3.86555110e-04 6.42776651e-05]) = 0.00111
4357, Best: f([ 0.00013889 -0.0001261 ]) = 0.00053
Done!
f([ 0.00013889 -0.0001261 ]) = 0.000532
さらに読む
さらに詳しく知りたい場合は、このセクションでこのトピックに関するさらなるリソースを提供します。
論文
- 進化戦略: 包括的な紹介、2002 年。
本
- メタヒューリスティックスの要点、2011 年。
- 最適化のためのアルゴリズム、2019 年。
- 計算知能: 入門、2007 年。
記事
- 進化戦略、ウィキペディア。
- 進化戦略、Scholarpedia。
まとめ
このチュートリアルでは、進化戦略の最適化アルゴリズムを実装する方法を学びました。
具体的には、次のことを学びました。
- Evolution Strategies は、自然選択による進化の生物学的理論に触発された確率的グローバル最適化アルゴリズムです。
- Evolution Strategies には標準用語があり、(mu, lambda)-ES および (mu + lambda)-ES と呼ばれるアルゴリズムの 2 つの一般的なバージョンがあります。
- Evolution Strategies アルゴリズムを実装して連続目的関数に適用する方法。
ご質問はありますか?
以下のコメント欄にご質問ください。できる限りお答えいたします。