進化的最適化アルゴリズム
.jpg "James McCaffrey")
進化的最適化アルゴリズムとは、生物が進化するしくみをモデル化したメタヒューリスティックの実装です。このアルゴリズムを使えば、解決が困難または不可能に思える、数値最小化問題の近似解法を見つけることができます。進化的最適化アルゴリズムを取り上げる理由は 3 つあります。まず、このようなアルゴリズムをコーディングする方法は、開発者、マネージャー、テスターのスキルに加える実用的知識として役に立ちます。2 つ目に、トーナメント選択など一部の技法を、別のアルゴリズムやコーディングのシナリオで再利用できます。最後に、きっと多くのエンジニアに興味深く感じてもらえるアルゴリズムだからです。
進化的最適化アルゴリズムは、本質的に遺伝アルゴリズムの一種で、仮想染色体がビット表現の形式ではなく実際の値から作られます。図 1 と図 2 を見てみるのが一番の近道です。
.jpg)
図 1 Schwefel 関数
.jpg)
図 2 進化的最適化のデモ
図 1 のグラフが Schwefel 関数で、標準ベンチマークの数値最小化問題を示します。Schwefel 関数は次のように定義されます。
f(x,y) = (-x * sin(sqrt(abs(x)))) + (-y * sin(sqrt(abs(y))))
関数は、x = y = 420.9687 のとき、最小値 -837.9658 になります。図 1 では、この最小値はグラフの左端隅になります。この関数は、膨大な数の誤った極小値によって、最適化アルゴリズムの解が求めにくくなるよう意図的に設計されています。
図 2 のスクリーンショットは、C# コンソール アプリケーションの出力を示しています。プログラムは、いくつか情報メッセージを表示した後、8 個のパラメーターを設定してから、最適解を探すために進化的アルゴリズムを使用しています。この例では、アルゴリズムは (420.9688, 420.9687) という最善の解を見つけていますが、これは最適解である (420.9687, 420.9687) ときわめて近いものの、まったく同じではありません。
進化的最適化アルゴリズムは、個体における染色体として解をモデル化します。図 2 に実装されているアルゴリズムは、大まかな擬似コードでは次のようになります。
initialize a population of random solutions
determine best solution in population
loop
select two parents from population
make two children from the parents
place children into population
make and place an immigrant into population
check if a new best solution exists
end loop
return best solution found
次のセクションでは、図 2 のスクリーンショットを生成したすべてのコードを示します。コードには archive.msdn.microsoft.com/mag201206TestRun (英語) からもアクセスできます。今回は、中上級のプログラミング スキルがあることを前提にしています。また、少なくとも、ごく基本的な遺伝アルゴリズムについての知識があることも想定しています。デモ プログラムのコードは C# で記述しましたが、コードは Visual Basic、.NET、IronPython などの別の言語に簡単にリファクタリングできます。
プログラムの構造
プログラム構造全体を図 3 に示します。まず、Visual Studio 2010 で、EvolutionaryOptimization という新しい C# コンソール アプリケーション プロジェクトを作成しました。ソリューション エクスプローラー ウィンドウで、Program.cs を EvolutionaryOptimizationProgram.cs という名前に変更しました。これによって、自動的に Program クラスの名前が変更されます。また、テンプレートが生成した不要な using ステートメントはすべて削除します。
図 3 EvolutionaryOptimization プログラムの全体構造
using System;
namespace EvolutionaryOptimization
{
class EvolutionaryOptimizationProgram
{
static void Main(string[] args)
{
try
{
int popSize = 100;
int numGenes = 2;
double minGene = -500.0; double maxGene = 500.0;
double mutateRate = 1.0 / numGenes;
double precision = 0.0001;
double tau = 0.40;
int maxGeneration = 8000;
Evolver ev = new Evolver(popSize, numGenes,
minGene, maxGene, mutateRate,
precision, tau, maxGeneration);
double[] best = ev.Evolve();
Console.WriteLine("\nBest solution found:");
for (int i = 0; i < best.Length; ++i)
Console.Write(best[i].ToString("F4") + " ");
double fitness = Problem.Fitness(best);
Console.WriteLine("\nFitness of best solution = "
+ fitness.ToString("F4"));
}
catch (Exception ex)
{
Console.WriteLine("Fatal: " + ex.Message);
}
}
}
public class Evolver
{
// Member fields
public Evolver(int popSize, int numGenes,
double minGene, double maxGene,
double mutateRate, double precision,
double tau, int maxGeneration) { ... }
public double[] Evolve() { ... }
private Individual[] Select(int n) { ... }
private void ShuffleIndexes() { ... }
private Individual[] Reproduce(Individual parent1,
Individual parent2) { ... }
private void Accept(Individual child1,
Individual child2) { ... }
private void Immigrate() { ... }
}
public class Individual : IComparable<Individual>
{
// Member fields
public Individual(int numGenes,
double minGene, double maxGene,
double mutateRate, double precision) { ... }
public void Mutate() { ... }
public int CompareTo(Individual other) { ... }
}
public class Problem
{
public static double Fitness(double[] chromosome) { ... }
}
} // NS
EvolutionaryOptimization デモには、メイン プログラム クラスに加え、プログラムで定義するクラスが 3 つあります。Evolver クラスに、大半のアルゴリズム ロジックを含めます。Individual クラスは、最小化問題の可能性のある解をモデル化します。Problem クラスは、最小化する関数を定義します (この場合は Schwefel 関数です)。これとは別に、Evolver クラス内に Individual クラスを含める設計構造もあります。
Individual クラス
Individual (個体) クラスの定義は以下のように始まります。
public class Individual : IComparable<Individual>
{
public double[] chromosome;
public double fitness;
private int numGenes;
private double minGene;
private double maxGene;
private double mutateRate;
private double precision;
static Random rnd = new Random(0);
...
このクラスは、Individual オブジェクトの配列が適応度によって自動的に並べ替えられるように、IComparable インターフェイスから継承します。クラスには 8 個のデータ メンバーを用意します。chromosome (染色体) 配列は、対象となる問題の可能性のある解を表します。chromosome は、主に遺伝アルゴリズムによって使用されるビット表現形式の配列ではなく、double の配列にしています。進化的最適化アルゴリズムは、実数値遺伝アルゴリズムと呼ばれることもあります。
fitness (適応度) フィールドは、染色体の解がどの程度最適解に近いかを示す尺度です。最小化問題の場合、fitness の値は小さい方が優れています。わかりやすくするため、chromosome と fitness は、Evolver クラスのロジックに公開されるように、パブリック スコープで宣言しています。遺伝子 (gene) は chromosome 配列の値の 1 つで、numGenes フィールドは可能性のある解の実際の値の数を保持します。Schwefel 関数では、この値は 2 に設定されます。多くの数値最適化問題で、各遺伝子の最小値と最大値は指定することができ、この値は minGene と maxGene に格納します。これらの値がわからない場合、minGene と maxGene には double.MinValue と double.MaxValue を設定できます。mutateRate フィールドと precision フィールドについては、後ほどコードに出てきたときに説明します。
Individual クラスの定義は、以下のように、クラス コンストラクターに続きます。
public Individual(int numGenes, double minGene, double maxGene,
double mutateRate, double precision)
{
this.numGenes = numGenes;
this.minGene = minGene;
this.maxGene = maxGene;
this.mutateRate = mutateRate;
this.precision = precision;
this.chromosome = new double[numGenes];
for (int i = 0; i < this.chromosome.Length; ++i)
this.chromosome[i] = (maxGene - minGene)
* rnd.NextDouble() + minGene;
this.fitness = Problem.Fitness(chromosome);
}
クラス コンストラクターは、chromosome 配列にメモリを割り当て、範囲内 (minGene、maxGene) のランダム値を遺伝子の各セルに割り当てます。fitness フィールドの値が、外部で定義される Fitness メソッドを呼び出すことで設定されている点に注目してください。別の手法として、Delegate によって Fitness メソッドへの参照をコンストラクターに渡すこともできます。Mutate (突然変異) メソッドは次のように定義されます。
public void Mutate()
{
double hi = precision * maxGene;
double lo = -hi;
for (int i = 0; i < chromosome.Length; ++i) {
if (rnd.NextDouble() < mutateRate)
chromosome[i] += (hi - lo) * rnd.NextDouble() + lo;
}
}
突然変異演算は chromosome 配列全体を処理して、ランダムに選択された遺伝子を、範囲内 (lo、hi) のランダム値に変換します。割り当てる値の範囲は、precision および maxGene メンバー値によって決まります。図 2 の例では、precision に 0.0001 を設定し、maxGene に 500 を設定しています。遺伝子の突然変異に可能性のある最高値は、0.0001 * 500 = 0.05 です。つまり、遺伝子が突然変異した場合、新しい値は、古い値に -0.05 ～ +0.05 の間のランダム値が加減されたものになります。precision 値は、解の小数点以下桁数を表します。これは、precision 値に使用するのに理にかなったヒューリスティックです。突然変異率の値は、染色体の遺伝子がいくつ変更されるかを制御します。mutateRate (突然変異率) フィールド値の 1 つのヒューリスティックは、Mutate が呼び出されるたびに染色体の遺伝子が平均して 1 つ突然変異するよう、1.0 / numGenes を使用することです。
Individual クラスの定義は、以下のように、CompareTo メソッドで締めくくります。
...
public int CompareTo(Individual other)
{
if (this.fitness < other.fitness) return -1;
else if (this.fitness > other.fitness) return 1;
else return 0;
}
}
CompareTo メソッドは、Individual オブジェクトの既定の並べ替え順を定義します。この場合は、最小 (最善) の適応度から最大の適応度という順番になります。
Problem クラス
Problem クラスは、以下のように、進化アルゴリズムの対象となる問題をカプセル化します。
public class Problem
{
public static double Fitness(double[] chromosome)
{
double result = 0.0;
for (int i = 0; i < chromosome.Length; ++i)
result += (-1.0 * chromosome[i]) *
Math.Sin(Math.Sqrt(Math.Abs(chromosome[i])));
return result;
}
}
chromosome 配列は可能性のある解を表すため、Fitness メソッドの入力パラメーターとして渡されます。任意の最小化問題では、最小化する関数は一般的に "コスト関数" と呼ばれます。ところが、進化的アルゴリズムや遺伝アルゴリズムでは、この関数は通常 "適応度関数" と呼ばれます。最小化問題では、適応度の値は低いほど良いので、この用語は少し奇妙に感じられます。この例では、適応度関数は完全に自己完結型です。多くの最適化問題の適応度関数には、データ行列や外部データ ファイルへの参照など、追加の入力パラメーターが必要になります。
Evolver クラス
Evolver (進化するもの) クラスの定義は、以下のように始まります。
public class Evolver
{
private int popSize;
private Individual[] population;
private int numGenes;
private double minGene;
private double maxGene;
private double mutateRate;
private double precision;
private double tau;
private int[] indexes;
private int maxGeneration;
private static Random rnd = null;
...
popSize メンバーは、集団の中の個体数を保持します。popSize の値が大きいほど、アルゴリズムの速度が犠牲になり、精度が増加する傾向にあります。進化的アルゴリズムは、実際の値を操作し、ビット表現の変換および操作のオーバーヘッドが生じないため、普通の遺伝アルゴリズムよりもずっと高速なのが一般的です。Evolver クラスの中心部は、population (集団) という Individual オブジェクトの配列です。この後すぐに説明しますが、tau メンバーおよび indexes メンバーは、Selection メソッドによって使用されます。
Evolver クラスの定義は、コンストラクター定義に続きます (図 4 参照)。
図 4 Evolver クラス コンストラクター
public Evolver(int popSize, int numGenes, double minGene, double maxGene,
double mutateRate, double precision, double tau, int maxGeneration)
{
this.popSize = popSize;
this.population = new Individual[popSize];
for (int i = 0; i < population.Length; ++i)
population[i] = new Individual(numGenes, minGene, maxGene,
mutateRate, precision);
this.numGenes = numGenes;
this.minGene = minGene;
this.maxGene = maxGene;
this.mutateRate = mutateRate;
this.precision = precision;
this.tau = tau;
this.indexes = new int[popSize];
for (int i = 0; i < indexes.Length; ++i)
this.indexes[i] = i;
this.maxGeneration = maxGeneration;
rnd = new Random(0);
}
コンストラクターは、population 配列用にメモリを割り当てたら、ランダムな遺伝子値を持つ個体を配列に格納するために Individual コンストラクターを使用します。indexes という配列は、2 つの親を選択する Select メソッドで使用します。indexes については後ほど説明しますが、コンストラクターは、個体ごとに 1 つのセルを割り当てて、0 ～ popSize - 1 の整数を連続して割り当てています。
Evolve (進化) メソッドは、図 5 のように驚くほど短いメソッドです。
図 5 Evolve メソッド
public double[] Evolve()
{
double bestFitness = this.population[0].fitness;
double[] bestChomosome = new double[numGenes];
population[0].chromosome.CopyTo(bestChomosome, 0);
int gen = 0;
while (gen < maxGeneration) {
Individual[] parents = Select(2);
Individual[] children = Reproduce(parents[0], parents[1]);
Accept(children[0], children[1]);
Immigrate();
for (int i = popSize - 3; i < popSize; ++i) {
if (population[i].fitness < bestFitness) {
bestFitness = population[i].fitness;
population[i].chromosome.CopyTo(bestChomosome, 0);
}
}
++gen;
}
return bestChomosome;
}
Evolve メソッドは、見つかった最適解を double 型の配列として返します。この方法とは別に、chromosome が見つかった最適解を保持している、Individual オブジェクトを返すこともできます。Evolve メソッドは、まず、最適適応度と最適染色体を、集団の中の最初の適応度と染色体に初期化します。その後、gen (generation、世代) をループ カウンターとして使用して、正確な maxGeneration の数だけ反復処理します。あるいは、何回か反復処理を行った後、何の改良も見られない場合に停止するという方法もあります。Select メソッドは、適応度が適切であっても必ずしも最善ではない個体を集団から 2 つ返します。2 つの子を作って返す Reproduce にこの 2 つを親として渡します。Accept メソッドは、2 つの子を集団に配置して、2 つの既存の個体を置き換えます。Immigrate (移住) メソッドは、新しいランダムな個体を生成して、集団に配置します。その後、集団の中の新しい個体 3 つのいずれかが新しい最適解であるかどうかを確認するために、この新しい集団をスキャンします。
Select メソッドは次のように定義します。
private Individual[] Select(int n)
{
int tournSize = (int)(tau * popSize);
if (tournSize < n) tournSize = n;
Individual[] candidates = new Individual[tournSize];
ShuffleIndexes();
for (int i = 0; i < tournSize; ++i)
candidates[i] = population[indexes[i]];
Array.Sort(candidates);
Individual[] results = new Individual[n];
for (int i = 0; i < n; ++i)
results[i] = candidates[i];
return results;
}
このメソッドは、選択する必要がある、適応度が適切な個体の数を受け取り、Individual 型の配列にそれらを返します。ここでは、コードをできる限り少なくするために、要求される個体数が集団の個体数より少ないかどうかの検証など、通常のエラー チェックを省略しています。Select メソッドは、トーナメント選択方式を採用します。この手法では、ランダムに選び出した、候補となる個体のサブセットを生成し、そのうち適応度が最も適切である n 個の個体を返します。候補数は、tournSize という変数に算出します。これは、集団の総個体数の一部分 (tau) です。tau の値が大きいほど、適応度が最も適切な 2 つの個体が選択される確率が高まります。
Evolver クラスには、0..popSize-1 という値を持つ indexes という名前のメンバー配列を用意しました。ShuffleIndexes ヘルパー メソッドは、配列のインデックスの値を、ランダムな順序に並べ替えます。これらのランダムなインデックスの先頭にある n 個の値を、集団から候補を取得するのに使用します。その後、Array.Sort メソッドは、最小 (最善) の適応度から最大の適応度に、候補の個体を並べ替えます。その後、並べ替えた候補の先頭にある n 個の個体を返します。進化的選択アルゴリズムには多くの種類がありますが、トーナメント選択がその他多くの手法より優れている点は、tau パラメーターを変更することで、選択圧を調整できるところです。
ShuffleIndexes ヘルパー メソッドは、以下のように、標準の Fisher-Yates シャッフル アルゴリズムを使用します。
private void ShuffleIndexes()
{
for (int i = 0; i < this.indexes.Length; ++i) {
int r = rnd.Next(i, indexes.Length);
int tmp = indexes[r];
indexes[r] = indexes[i];
indexes[i] = tmp;
}
}
図 6 に Reproduce メソッドを示します。このメソッドはまず、ランダムな交差点を生成します。インデックスの作成はやや複雑ですが、child1 は parent1 の左側部分と parent2 の右側部分から作成されます。child2 は、parent2 の左側部分と parent1 の右側部分から作成されます。この考え方を図 7 に示しています。5 個の遺伝子のある 2 つの親があり、交差点は 2 です。または、複数の交差点を使用する設計も一般的です。Individual 子オブジェクトを作成した後は、子オブジェクトが突然変異して、新しい適応度が計算されます。
図 6 Reproduce メソッド
private Individual[] Reproduce(Individual parent1, Individual parent2)
{
int cross = rnd.Next(0, numGenes - 1);
Individual child1 = new Individual(numGenes, minGene, maxGene,
mutateRate, precision);
Individual child2 = new Individual(numGenes, minGene, maxGene,
mutateRate, precision);
for (int i = 0; i <= cross; ++i)
child1.chromosome[i] = parent1.chromosome[i];
for (int i = cross + 1; i < numGenes; ++i)
child2.chromosome[i] = parent1.chromosome[i];
for (int i = 0; i <= cross; ++i)
child2.chromosome[i] = parent2.chromosome[i];
for (int i = cross + 1; i < numGenes; ++i)
child1.chromosome[i] = parent2.chromosome[i];
child1.Mutate(); child2.Mutate();
child1.fitness = Problem.Fitness(child1.chromosome);
child2.fitness = Problem.Fitness(child2.chromosome);
Individual[] result = new Individual[2];
result[0] = child1; result[1] = child2;
return result;
}
.png)
図 7 交差のメカニズム
Accept メソッドは、以下のように、Reproduce によって作成された 2 つの子個体を集団に配置します。
private void Accept(Individual child1, Individual child2)
{
Array.Sort(this.population);
population[popSize - 1] = child1;
population[popSize - 2] = child2;
}
population 配列を適応度順に並べ替え、配列の最後のセル 2 つに適応度の最も不適切な個体を配置します。これらの個体は、その後子に置き換えられます。死滅する 2 つの個体を選ぶ方法は他にもたくさんあります。たとえば、ルーレット選択方式を使用して、適応度の不適切な個体が置換される確率が高い状態で、置き換える 2 つの個体を確率から選択することも可能です。
Immigrate メソッドは、新しいランダムな個体を生成して、生成したばかりの 2 つの子の真上にある集団に配置します (移住は、局所的最小解から進化的アルゴリズムが抜け出せなくなるのを防ぎます。これに代わるものとしては、1 つより多くの移民を作成して、集団のランダムな場所に移民を配置するという設計もあります)。
private void Immigrate()
{
Individual immigrant =
new Individual(numGenes, minGene, maxGene, mutateRate, precision);
population[popSize - 3] = immigrant;
}
実験の開始点
今回は、進化的最適化を、数学方程式の最小値を推定するのに使用しました。進化的最適化アルゴリズムは確かにこのようにも使えますが、効果的な決定アルゴリズムが存在しない、より規模の大きな最適化問題で、一連の数値パラメーターの値を見つけるために使用する方が一般的です。たとえば、将来のデータについて予測するために、既存のデータを分類するのにニュートラル ネットワークを使用する場合、主な課題は、一連のニューロンの荷重とバイアスを決定することです。最適な荷重値とバイアス値を推定する方法の 1 つが、進化的最適化アルゴリズムです。ただし、進化的最適化アルゴリズムは、総経路長が最も短い都市の組み合わせを見つけることを目的とする巡回セールスマン問題など、数値以外の組み合わせ最適化問題にはあまり適していないことがほとんどです。
純粋な遺伝アルゴリズムのように、進化的アルゴリズムはメタヒューリスティックです。つまり、特定の問題を解決する特定のアルゴリズムを作成できる、全般的フレームワークおよび一連の概念的なガイドラインとして機能します。ですので、今回紹介した例は、不変の静的なコード ベースというよりは、実験および進化的最適化コード作成の出発点と考えてください。
Dr. James McCaffrey は Volt Information Sciences Inc. に勤務し、ワシントン州レドモンドにあるマイクロソフト本社で働くソフトウェア エンジニアの技術トレーニングを管理しています。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。また、『.NET Test Automation Recipes: A Problem-Solution Approach』(Apress、2006 年) の著者でもあります。連絡先は jammc@microsoft.com (英語のみ) です。
この記事のレビューに協力してくれた技術スタッフの Anne Loomis Thompson に心より感謝いたします。