遺伝的アルゴリズムのクロスオーバー部分について読むとき、本や論文は通常、複製される2つの選択された候補のデータのビットを単純に交換する方法を指します。
実際の業界アプリケーションに実装された遺伝的アルゴリズムの実際のコードはまだ見ていませんが、単純なデータ型を操作するのに十分であるとは想像しがたいです。
私は常に、遺伝的アルゴリズムのさまざまな段階が、単一の整数の一部のビットを単に交換するのではなく、複雑な数学演算を含む複雑なオブジェクトに対して実行されることを想像していました。
ウィキペディアでさえ、クロスオーバーのためのこれらの種類の操作をリストしているだけです。
私は何か重要なものを見逃していますか、それともこれらの種類のクロスオーバーメソッドは本当に使用されている唯一のものですか？
使用されるものはいくつかあります...並列性と数世代（そして時には大きな人口）の必要性は、うまく機能する技術を使用することにつながります...
覚えておくべきもう一つのポイントは、正しくモデル化されたときの「いくつかのビットを交換する」ことは、自然に起こること（遺伝子の組換え、突然変異）の単純でかなり正確なバージョンに似ているということです...
非常にシンプルで見事に書かれたウォークスルーについては、http： //www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolveing-hello-world/を参照してください。
詳細については、を参照してください
私は常に、遺伝的アルゴリズムのさまざまな段階が、単一の整数の一部のビットを単に交換するのではなく、複雑な数学演算を含む複雑なオブジェクトに対して実行されることを想像していました。
遺伝的アルゴリズムは複雑なオブジェクトを変更する必要があると思うので、おそらく複雑な数学演算が使用されていると思います。これは通常、遺伝的アルゴリズムが機能する方法ではありません。
では、何が起こりますか？さて、通常、プログラマー（または科学者）は構成内のさまざまなパラメーターを識別し、それらのパラメーターを整数/浮動小数点数にマップします。これは、アルゴリズムが探索できる方向を制限しますが、結果を得る唯一の現実的な方法です。
アンテナの進化を見てみましょう。銅分子を再配置する遺伝的アルゴリズムを使用して複雑なシミュレーションを実行することもできますが、それは非常に複雑で、永遠にかかります。代わりに、アンテナの「パラメータ」を特定します。ほとんどのアンテナは、特定の長さのワイヤで構成されており、カバレッジ領域を最大化するために特定の場所で曲げられています。したがって、開始ワイヤの数、セクションの長さ、曲げの角度など、いくつかのパラメータを特定できます。これらはすべて整数として簡単に表現できるため、遺伝的アルゴリズムで簡単に操作できます。結果として得られる操作を「アンテナシミュレーター」に入力して、信号の受信状態を確認できます。
要するに、あなたが言うとき：
単純なデータ型を操作するだけで十分だとは想像しがたいです。
単純なデータ型をはるかに複雑な構造にマッピングできることを理解する必要があります。遺伝的アルゴリズムは、これらの複雑な構造について何も知る必要はありません。知っておく必要があるのは、複雑な構造を構築するパラメーターをどのように操作できるかということだけです。つまり、結局のところ、DNAが機能する方法です。
遺伝的アルゴリズムでは、通常、いくつかの種類のビットワッピングが使用されます。
あなたが言ったように：
遺伝的アルゴリズムのさまざまな段階が、複雑な数学演算を含む複雑なオブジェクトに対して実行されることを常に想像していました
私があなたが探していると思うのは、染色体がプログラムを記述する遺伝的プログラミングです。この場合、クロスオーバーを適用するときに演算子を使ってより多くのことを行うことができます。
また、遺伝的アルゴリズムの適応度関数と、遺伝的プログラミングの染色体内の演算子の違いを理解していることを確認してください。
アプリケーションが異なれば、必要なエンコンディグも異なります。目標は確かに最も効果的なエンコーディングを見つけることであり、多くの場合、単純なエンコーディングの方が適しています。したがって、たとえば、ジョブショップスケジューリング問題は、さまざまなマシンでのジョブの実行順序を表す順列のリストとして表される場合があります（いわゆるジョブシーケンスマトリックス）。ただし、スケジュールを構成する優先ルールのリストとして表すこともできます。巡回セールスマン問題または二次割り当て問題は、通常、ある場合にはツアーを、別の場合には割り当てを示す単一の順列によって表されます。シミュレーションモデルのパラメーターを最適化するか、複雑な数学関数の根を見つけることは、通常、実数値のベクトルで表されます。
それらすべてについて、まだ単純な型のクロスオーバーおよび突然変異演算子が存在します。順列の場合、これらは、たとえばOX、ERX、CX、PMX、UBX、OBXなどです。いくつかの単純な表現を組み合わせて複雑な問題の解決策を表すことができる場合は、これらの操作を再利用して、各コンポーネントに個別に適用できます。
クロスオーバーが効果的に機能するために重要なことは、いくつかのプロパティが満たされる必要があるということです。
クロスオーバーでのいわゆる不要な突然変異を避けたいと考えています。その観点から、クロスオーバー後に染色体の大部分を修復する必要も避けたいと考えています。これは、不要な突然変異も引き起こすためです。
さまざまな演算子や問題を試してみたい場合は、GUI駆動の優れたソフトウェアHeuristicLabがあります。
単純なビットスワッピングが通常の方法です。注意すべき重要な点は、各候補解で使用されるエンコーディングです。ソリューションは、新しい子孫に導入されるエラーが最小限になるか、まったく発生しないようにエンコードする必要があります。エラーが発生した場合は、アルゴリズムが修正を提供する必要があり、処理時間が長くなります。
例として、私はC＃で大学のタイムテーブルジェネレーターを開発しました。これは、整数エンコーディングを使用して、毎日利用可能なタイムスロットを表します。この表現により、LINQ交差関数を使用して親を組み合わせる、非常に効率的なシングルポイントまたはマルチポイントのクロスオーバー演算子が可能になります。
山登り法による典型的なマルチポイントクロスオーバー
public List<TimeTable> CrossOver(List<TimeTable> parents) // Multipoint crossover
{
var baby1 = new TimeTable {Schedule = new List<string>(), Fitness = 0};
var baby2 = new TimeTable {Schedule = new List<string>(), Fitness = 0};
for (var gen = 0; gen < parents[0].Schedule.Count; gen++)
{
if (rnd.NextDouble() < (double) CrossOverProb)
{
baby2.Schedule.Add(parents[0].Schedule[gen]);
baby1.Schedule.Add(parents[1].Schedule[gen]);
}
else
{
baby1.Schedule.Add(parents[0].Schedule[gen]);
baby2.Schedule.Add(parents[1].Schedule[gen]);
}
}
CalculateFitness(ref baby1);
CalculateFitness(ref baby2);
// allow hill-climbing
parents.Add(baby1);
parents.Add(baby2);
return parents.OrderByDescending(i => i.Fitness).Take(2).ToList();
}