1

やあみんな、私自身のためのまったく新しいプロジェクトでまた戻ってきました。以前の投稿では、特定の仕事をするためのプログラミングに慣れていましたが、慣れるのはかなり簡単でしたが、今では、より創造的なプログラミングで何ができるかを見たいと思っています.

そこで、アルゴリズムに関連する一連の質問をします。スクービーが本当に何であるか、またはスクービーを書く方法を持っていません。しかし、私が興味を持っているのはGA（遺伝的アルゴリズム）です。

私は何を試みて達成しようとしているのかを分解しましたが、プログラムで考えて自分の道に進むには、開始点といくつかのプログラミング (コンソール c#) が必要です。読んで楽しんで、私の道を助けてくれることを願っています。

すべての生物は細胞からできています。各細胞には同じ染色体のセットがあります。染色体は DNA のひもであり、生物全体のモデルとして機能します。染色体は、遺伝子、つまり DNA のブロックで構成されています。各遺伝子は特定のタンパク質をコードしています。基本的に、各遺伝子は目の色などの特徴をコードしていると言えます。特性 (青、茶色など) の可能な設定は対立遺伝子と呼ばれます。各遺伝子は、染色体内で独自の位置を持っています。この位置を軌跡と呼びます。

遺伝物質の完全なセット (すべての染色体) はゲノムと呼ばれます。ゲノム内の特定の遺伝子セットは、遺伝子型と呼ばれます。遺伝子型は、生物の表現型、目の色、知性などの身体的および精神的特徴の基礎となる出生後の発達に伴います。

基本的な遺伝的アルゴリズムの概要

  1. [開始] n 個の染色体のランダムな母集団を生成します (問題の適切な解)
  2. [適応度]集団内の各染色体 x の適応度 f(x) を評価する
  3. 【新しい集団】新しい集団が完成するまで、以下の手順を繰り返して新しい集団を作成する 1. 【選択】母集団から適応度に応じて 2 つの親染色体を選択する (適応度が高いほど、選択される可能性が高くなる) 2. [クロスオーバー] ]交差確率で親を交差させて、新しい子孫 (子供) を形成します。クロスオーバーが実行されなかった場合、子孫は親の正確なコピーです。3. [Mutation]突然変異の確率で、各遺伝子座（染色体上の位置）で新しい子孫を突然変異させます。4. [承認] 新しい子孫を新しい集団に配置する
  4. [置換]アルゴリズムをさらに実行するために新しく生成された母集団を使用する
  5. [テスト]終了条件が満たされた場合は停止し、現在の母集団での最適解を返します
  6. [ループ]ステップ 2 へ

染色体のコード化

染色体には、それが表す解に関する情報が何らかの形で含まれているはずです。最もよく使用されるエンコード方法は、バイナリ文字列です。染色体は次のようになります。

Chromosome 1    1101100100110110
Chromosome 2    1101111000011110

各染色体には 1 つのバイナリ文字列があります。この文字列の各ビットは、ソリューションの特性を表すことができます。または、文字列全体で数値を表すこともできます。これは、基本的な GA アプレットで使用されています。

もちろん、エンコードの方法は他にもたくさんあります。これは主に解決された問題に依存します。たとえば、整数または実数を直接エンコードできます。場合によっては、いくつかの順列などをエンコードすると便利です。

クロスオーバー

使用するエンコーディングを決定したら、クロスオーバーへのステップを踏み出すことができます。交差は、親染色体から遺伝子を選択し、新しい子孫を作成します。これを行う最も簡単な方法は、ランダムに交点を選択し、この点より前のすべてを最初の親からコピーし、次に交点より後のすべてを 2 番目の親からコピーすることです。

クロスオーバーは次のようになります ( | はクロスオーバー ポイントです)。

Chromosome 1    11011 | 00100110110
Chromosome 2    11011 | 11000011110
Offspring 1     11011 | 11000011110
Offspring 2     11011 | 00100110110

クロスオーバーを作成する方法は他にもあります。たとえば、より多くのクロスオーバー ポイントを選択できます。クロスオーバーはかなり複雑になる可能性があり、染色体のエンコーディングのエンコーディングに大きく依存します。特定の問題に対して作成された特定の交叉は、遺伝的アルゴリズムのパフォーマンスを向上させることができます。

突然変異

クロスオーバーが実行された後、突然変異が発生します。これは、母集団内のすべての解が、解かれた問題の局所最適解に陥るのを防ぐためです。突然変異は新しい子孫をランダムに変化させます。バイナリ エンコーディングでは、ランダムに選択されたいくつかのビットを 1 から 0 または 0 から 1 に切り替えることができます。ミューテーションは次のようになります。

Original offspring 1    1101111000011110
Original offspring 2    1101100100110110
Mutated offspring 1     1100111000011110
Mutated offspring 2     1101101100110110

突然変異は、エンコーディングとクロスオーバーに依存します。たとえば、順列をエンコードしている場合、突然変異は 2 つの遺伝子を交換している可能性があります。

4

1 に答える 1

2

あなたの説明を見てください。

基本的な遺伝的アルゴリズムの概要

  1. [開始] n 個の染色体のランダムな母集団を生成します (問題の適切な解)
  2. [適応度]集団内の各染色体 x の適応度 f(x) を評価する
  3. 【新規個体群】新規個体群が完成するまで以下の手順を繰り返して新規個体群を作成します
    1. [選択]適合度に応じて母集団から 2 つの親染色体を選択します (適合度が高いほど、選択される可能性が高くなります)。
    2. 【交叉】交叉確率で親を交配し、新たな子孫（子）を形成します。クロスオーバーが実行されなかった場合、子孫は親の正確なコピーです。
    3. [Mutation]突然変異の確率で、各遺伝子座（染色体上の位置）で新しい子孫を突然変異させます。
    4. [承認]新しい子孫を新しい集団に配置する
  4. [置換]アルゴリズムをさらに実行するために新しく生成された母集団を使用する
  5. [テスト]終了条件が満たされた場合は停止し、現在の母集団での最適解を返します
  6. [ループ]ステップ 2 へ

それはすでにプログラムのように非常によく見えます。それをコードに変換すると、約 95% の作業が完了しているはずです。あなたが見逃しているのは、基本的にソリューションの実行と成功の基準である「フィットネス機能」です。それは質問ごとに異なるため、そこにはあまり役に立ちません。しかし、問題の複雑さに応じて、染色体のビットをフラグまたはオペコードとして使用する可能性が高く、染色体が高速かどうか、および高速かどうかを確認します (つまり、現在のビット/バイト/フラグ/オペコード/何でも）問題を解決しました。

于 2011-04-17T12:00:06.190 に答える