遺伝的アルゴリズムのクラス階層を構成する方法は?
-
05-07-2019 - |
質問
私は、遺伝的アルゴリズムでいくつかの作業を行っており、独自のGAクラスを作成したいと考えています。 GAには、選択、突然変異、クロスオーバー、初期集団の生成、適合度の計算、アルゴリズムの終了を行うさまざまな方法があるため、これらのさまざまな組み合わせをプラグインする方法が必要です。私の最初のアプローチは、これらすべてのメソッドを純粋仮想として定義した抽象クラスを作成することでした。具体的なクラスはそれらを実装する必要があります。たとえば同じクロスオーバーメソッドを使用する2つのGAを試してみたい場合は、GeneticAlgorithmを継承し、クロスオーバーメソッドを除くすべてのメソッドを実装する抽象クラスを作成し、次に2つの具象クラスを作成する必要があります。このクラスを継承し、クロスオーバーメソッドのみを実装します。これの欠点は、1つまたは2つのメソッドを交換して新しいものを試すたびに、1つ以上の新しいクラスを作成する必要があることです。
この問題により適切な別のアプローチがありますか?
解決
私は、アルゴリズム全体をカプセル化する1つの大きなクラスではなく、多くのオブジェクトのコラボレーションとしてGAにアプローチします。基本的に、すべての大きなクラスに対して抽象クラスを使用できます バリエーションのポイント、および必要な実装の選択肢ごとの具体的なクラス。次に、必要な具象クラスをさまざまな種類のGAに組み合わせます。
また、戦略パターンに慣れておくとよいでしょう: http://en.wikipedia.org/wiki/Strategy_pattern
他のヒント
GAフレームワークを実装するときに取ったアプローチは次のとおりです。 次のクラスを作成します。 世代 遺伝的アルゴリズム 遺伝的アルゴリズム GeneticAlgorithmParameters 人口 個人
さまざまな操作の戦略パターンを実装しませんでしたが、GeneticAlgorithmインスタンスのパラメーターとしてさまざまなGA操作実装を作成するのは簡単です。
GeneticAlgorithmクラスは、基本的なアルゴリズムをキャプチャします。実際には、さまざまなステップ(母集団の作成、個々のランダム化、選択、交叉、突然変異など)を定義するだけで、アルゴリズムの実行中に個人の母集団を管理します。ここで、必要に応じてさまざまな操作をプラグインできると思います。
本当の魔法はアダプターにあります。これは、問題のドメイン(個人の特定のサブクラス、関連するすべてのデータ)を遺伝的アルゴリズムに適合させるものです。ここではジェネリックを頻繁に使用するため、特定の種類の母集団、パラメーター、および個人が実装に渡されます。これにより、アダプターの実装のインテリセンスと強力な型チェックが可能になります。アダプターは基本的に、特定の個人(およびそのゲノム)に対して特定の操作を実行する方法を定義する必要があります。たとえば、アダプタのインターフェイスは次のとおりです。
/// <summary>
/// The interface for an adapter that adapts a domain problem so that it can be optimised with a genetic algorithm.
/// It is a strongly typed version of the adapter.
/// </summary>
/// <typeparam name="TGA"></typeparam>
/// <typeparam name="TIndividual"></typeparam>
/// <typeparam name="TPopulation"></typeparam>
public interface IGeneticAlgorithmAdapter<TGA, TIndividual, TGeneration, TPopulation> : IGeneticAlgorithmAdapter
where TGA : IGeneticAlgorithm
where TIndividual : class, IIndividual, new()
where TGeneration : class, IGeneration<TIndividual>, new()
where TPopulation : class, IPopulation<TIndividual, TGeneration>, new()
{
/// <summary>
/// This gets called before the adapter is used for an optimisation.
/// </summary>
/// <param name="pso"></param>
void InitialiseAdapter(TGA ga);
/// <summary>
/// This initialises the individual so that it is ready to be used for the genetic algorithm.
/// It gets randomised in the RandomiseIndividual method.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="individual">The individual to initialise.</param>
void InitialiseIndividual(TGA ga, TIndividual individual);
/// <summary>
/// This initialises the generation so that it is ready to be used for the genetic algorithm.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="generation">The generation to initialise.</param>
void InitialiseGeneration(TGA ga, TGeneration generation);
/// <summary>
/// This initialises the population so that it is ready to be used for the genetic algorithm.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="population">The population to initialise.</param>
void InitialisePopulation(TGA ga, TPopulation population);
void RandomiseIndividual(TGA ga, TIndividual individual);
void BeforeIndividualUpdated(TGA ga, TIndividual individual);
void AfterIndividualUpdated(TGA ga, TIndividual individual);
void BeforeGenerationUpdated(TGA ga, TGeneration generation);
void AfterGenerationUpdated(TGA ga, TGeneration generation);
void BeforePopulationUpdated(TGA ga, TPopulation population);
void AfterPopulationUpdated(TGA ga, TPopulation population);
double CalculateFitness(TGA ga, TIndividual individual);
void CloneIndividualValues(TIndividual from, TIndividual to);
/// <summary>
/// This selects an individual from the population for the given generation.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="generation">The generation to select the individual from.</param>
/// <returns>The selected individual.</returns>
TIndividual SelectIndividual(TGA ga, TGeneration generation);
/// <summary>
/// This crosses over two parents to create two children.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="parentsGeneration">The generation that the parent individuals belong to.</param>
/// <param name="childsGeneration">The generation that the child individuals belong to.</param>
/// <param name="parent1">The first parent to cross over.</param>
/// <param name="parent2">The second parent to cross over.</param>
/// <param name="child">The child that must be updated.</param>
void CrossOver(TGA ga, TGeneration parentsGeneration, TIndividual parent1, TIndividual parent2, TGeneration childsGeneration, TIndividual child);
/// <summary>
/// This mutates the given individual.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="generation">The individuals generation.</param>
/// <param name="individual">The individual to mutate.</param>
void Mutate(TGA ga, TGeneration generation, TIndividual individual);
/// <summary>
/// This gets the size of the next generation to create.
/// Typically, this is the same size as the current generation.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="currentGeneration">The current generation.</param>
/// <returns>The size of the next generation to create.</returns>
int GetNextGenerationSize(TGA ga, TGeneration currentGeneration);
/// <summary>
/// This gets whether a cross over should be performed when creating a child from this individual.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="currentGeneration">The current generation.</param>
/// <param name="individual">The individual to determine whether it needs a cross over.</param>
/// <returns>True to perform a cross over. False to allow the individual through to the next generation un-altered.</returns>
bool ShouldPerformCrossOver(TGA ga, TGeneration generation, TIndividual individual);
/// <summary>
/// This gets whether a mutation should be performed when creating a child from this individual.
/// </summary>
/// <param name="ga">The genetic algorithm that is running.</param>
/// <param name="currentGeneration">The current generation.</param>
/// <param name="individual">The individual to determine whether it needs a mutation.</param>
/// <returns>True to perform a mutation. False to allow the individual through to the next generation un-altered.</returns>
bool ShouldPerformMutation(TGA ga, TGeneration generation, TIndividual individual);
}
適切なアダプターを作成するだけで、さまざまな問題ドメインにGA実装を簡単に再利用できるため、このアプローチがうまく機能することがわかりました。異なる選択、クロスオーバー、またはミューテーションの実装に関して、アダプターは関心のある実装を呼び出すことができます。通常は、適切な戦略を調査しながら、アダプターのさまざまなアイデアをコメントアウトします。
これが役立つことを願っています。必要に応じて、さらにガイダンスを提供できます。このようにデザインを正すことは困難です。
あなたはあなたのアプローチで物事を複雑にしていると思います。 GAlib パッケージをダウンロードすることをお勧めします。ドキュメントをhtmlまたはpdf形式でプルする場合でも。これらのライブラリはしばらく前から存在しており、GAlibでどのように実行されているかを調べることで、libを構造化する方法を学ぶことができると確信しています。
私の一部からのランダムなビット:
- (アプローチとして)チェックアウトする必要があるプロジェクトは、 watchmaker です。
- GAを構築する上で最も難しいのは、問題に対する賢明な遺伝的表現を見つけ、特定の母集団に対して fitness の良好な分布を持つフィットネス関数を構築することです
- (m)あらゆる厳しい制約を扱う場合、(可能な)ジャンクDNAと少しのパフォーマンスを犠牲にして、厳しい制約を処理する Translator クラスを導入することを考えることができます
実装は、デコレーターパターンのように見えます。
人々が言うように、1つの巨大なクラスにしないでください。それは恐ろしいことです。動作を異なるクラスにカプセル化します。戦略は解決策です。
サンプルが必要な場合は、 JGAP のソースと例をダウンロードしてください。遺伝的プログラミングと遺伝的アルゴリズムをサポートしています。素敵なデザインが表示されます。 Mutation、Crossover、Selection、Population、Gene-これらはすべて別個のクラスです。使用する実装で定義済みのインターフェイスを開始するConfigurationオブジェクトをセットアップし、適切なアルゴリズムパラメーターを渡して実行するだけです。本当にパッケージは巨大で、javadocが素晴らしく、いつでもソースを調べたり、メールグループでいくつかの回答を確認したりできます。 GAパッケージを探していたとき、GAlibなどを見ましたが、これは本当にすてきなデザインで最も完全だと思います。