3

GA を使用して、特定の条件 (長さ、ターン数など) を満たす A から B への最適なパスを決定したい。

パスの例: 上 4、左 8、下 3、右 3、下 1、左 10、上 4、左 1、上 3

問題は、特にパスが可変長であるため、このような情報を GA で使用するのに適した方法で表現する良い方法を本当に知らないことです。

このようなことを行う方法を知っている人はいますか?

4

5 に答える 5

2

A* 最適化アルゴリズム のようなものを本当に使用したいようです。これは、パス検索に一般的に (効果的に) 使用されます。適切なソリューションを取得するために、任意のヒューリスティック関数を指定できます。

于 2009-05-25T22:22:57.723 に答える
1

GA は可変長の染色体を扱うことができます。実際の個人は非常に複雑な場合があります。たとえば、いくつかの固定長ビット、文字列 (固定長ではない)、および共役複素数のペアのセットを含めることができます。さらに、共役複素数のペアは、常にいくつかの条件を維持する必要があります。それは可能ですが、個体が複雑になればなるほど、遺伝子操作も複雑になります (交差、突然変異など)。おそらく、Fitness 関数にはさらに数行のコードが必要になるでしょう。しかし、それはまだ可能です。

おそらく、数値コード化されたパス表現を選択することもできますが、Osama ALASSIRYが提案したようにコード化された例でも実行できます: UUUULLLLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU。
クロスオーバーの場合:

  • 突然変異演算子に与えられた個体の現在の長さ1を読み取らせ、
  • x1,y1 =< length1 と x1 != y1 の両方の 2 つの乱数 x1,y1 を生成します (これは、個々の 1 のカット ポイントです)。
  • 個々の 2 に対して同じことを行うと、(x1,y1) と (x2,y2) の 2 つのペアができます。
  • 個体 1 から x1 と y1 の間にあるものをコピーし、値 x2 と y2 の間の個体 2 に挿入します。個人 2 の新しいバージョンは、x1y1 と x2y2 の間の遺伝子の数が異なる可能性があるため、その長さを変更する可能性がありますが、それは問題ありません。
  • x2y2 間の個体 2 の元のバージョンにあったものは、x1y1 間の個体 1 の新しいバージョンに挿入する必要があります (その長さも変更されます)。

明確にするために:
親 A: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU親
B: DRRRRLULUDDDR 0
から遺伝子をカウントすると仮定して、ランダムペアペア A(4,18)、ペア B(0,5) を生成 します。 UUUU DRRRRL LLLLLLLLLLUUUULUUU LLLLLLLLDDDRRRD ULUDDDRが得られ ました。カットの 1 つのポイントを使用することも、ポイントを掛けることもできます。





突然変異に関して：

  • 0 から個体の長さまでの数を生成し、
  • 1 ～ 4 の番号を生成し、その遺伝子を更新します。(1 が生成された場合は、U、2-D、3-L、4-R に変更します)

あなたは突然変異をしただけです。複数の遺伝子を変異させることもできます。

しかし、私が言ったように、他の可能性があります。

于 2009-11-04T20:44:51.660 に答える
1

U、D、L、R....を使用します。

したがって、「上 4、左 8、下 3、右 3、下 1、左 10、上 4、左 1、上 3」は次のようになります。

うううううううううううううううううううう

このような糸を繁殖させる方がはるかに簡単です。

A (15 文字) と B (3 文字) の場合、A と B の間の繁殖関数は次のようになります。

  • 1 から MAX(LEN(A), LEN(B)) {1 から 15 の間} の間で任意の長さ (len) を選択します。
  • 1 と len の間のランダムな分割ポイントを選択します。
  • A または B をランダムに最初に移動するかどうかを選択します。
  • 最初に行くものから最初の s 文字を取り、他のものから最後の (len-s) 文字を取ります。
于 2009-05-25T22:18:01.977 に答える
0

私には、これは巡回セールスマンの問題に非常に似ているように思えますが、そのページには有用な情報が含まれていますか?

于 2009-04-13T22:02:11.537 に答える