特定の場所で特定の数のノードを接続する最も効率的な方法を見つける遺伝的アルゴリズムを開発しようとしています。
ネットワーク上のすべてのノードがサーバー ノードに接続できる必要があり、ネットワーク内にサイクルがあってはなりません。基本的に木です。
任意のネットワーク レイアウトの「適合性」を測定できる機能があります。私を止めているのは、2つのネットワーク構造（親）を取り、それらを何らかの形で混合して上記の条件を満たす子孫を作成するクロスオーバー関数を考えられないことです。
何か案は？
明確化: 各ノードには固定の x、y 座標位置があります。それらの間のルートのみを変更できます。
Amir- 生成されたすべてのツリーには、異なる順序で配置された同じノード セットが含まれるという考えだと思います。
おそらく、交差ベースの遺伝的アルゴリズムを使用するよりも、生物学的影響の少ない山登りアルゴリズムを使用した方がよいでしょうか? 一連のスワップ (ノード間で子を交換するなど) を定義して、可能な突然変異として機能させ、反復的に突然変異させ、フィットネス関数に対してチェックします。この種のすべての検索の場合と同様に、局所的な最大値に行き詰まる可能性があるため、さまざまな開始位置から多くの実行を行うことをお勧めします。
クロスオーバー演算子をチェックして、子染色体に繰り返しノードがないことを確認できます。それらのクロスオーバー演算子のカップルは、オーダークロスオーバー（OX）とエッジクロスオーバー演算子です。このようなクロスオーバー演算子は、GAを使用してTSPを解くのにも役立ちます。
その後、サイクルが発生しているかどうかを確認する必要があります。はいの場合、染色体の新しいペアを生成します。もちろん、これはブルートフォースです。
最小スパニングツリーネットワークを作成する必要があるようです。これはあなたの遺伝的アルゴリズムの質問に実際には答えないことを私は知っていますが、これは非常によく理解されている問題です。2つの古典的な方法は、PrimとKrustalです。たぶん、これらのアルゴリズムとそれらが接続するエッジを選択するために使用する方法は、あなたにいくつかの手がかりを与えるかもしれません。たぶん、遺伝子はネットワークを説明していませんが、代わりに特定のエッジを介してノードを接続する可能性を説明していますか？または、次に接続するノードを選択する方法はありますか？
または、以前にこれを行った人、またはこれをチェックしてください。
質問であなたの質問に答えることから始めましょう：
「サイクルなし」ルールと「サーバーへの接続」ルールに違反するネットワークレイアウトを作成した場合、適応度関数はどのように動作しますか？
フィットネススコアが低いために特定のネットワークレイアウトを単純に罰する場合は、2つのネットワークレイアウトを取得して、レイアウトAから1/2、レイアウトBから1/2を交差させる以外に、特別なことをする必要はありません。これは非常に重要です。基本的なクロスオーバー機能、そしてそれは動作するはずです。
ただし、有効なレイアウトを作成する責任があり、無効なレイアウトが単純に削除されることに依存できない場合は、さらに作業を行う必要があります。
遺伝的アルゴリズムにおけるクロスオーバーの目的は、ある親の適切な部分解を別の親の部分解と混合する可能性があることです。この場合の部分解について考える 1 つの方法は、密接に接続されたノードのサブツリーです。ツリー全体のローカライズされた部分への小さな変更に関してフィットネス関数がかなりスムーズである場合、これは交差について考えるのに役立つ方法かもしれません。
これを考えると、考えられるクロスオーバーの 1 つの形式は次のようになります。
2 つの親ツリーP1とP2から始めます。N1とN2の 2 つのノードをランダムに選択します (ノード間の最小距離になんらかの強制が適用される可能性があります) 。
ノードごとに、ツリーC1をP1のリンケージに従ってN1から外側に「成長」させ、同時に別のツリーをP2から開始してN2から外側に成長させます。両方のツリーに同じノードを追加しないでください。ノードのセットを完全に切り離してください。すべてのノードがC1またはC2に追加されるまで続行します。これにより、非環式であることが保証された形で、再結合する各親の「特性」が得られます。
再結合は、 C1からC2への追加のリンクを追加して、新しい子Cを作成することによって行われます。どのリンクを選択するかについては、ランダムに (一様に、または何らかの分布に従って) 選択することも、貪欲なアルゴリズム (ヒューリスティックまたは新しいツリーCの全体的な適合性に基づく) によって選択することもできます。
初期の会議の 1 つに、巡回セールスマンの次のアルゴリズムを提案する論文がありました。これをいくつかのグラフの問題に適用して成功させました。
人口全体にわたって、接続数の降順でノードを計算およびソートします (つまり、N0 が一部の個人で N1、N2、N3 に接続されている場合、3 つの接続があり、N1 が常に N4 に接続されている場合は、接続が 3 つしかありません)。 1)。
最初に、カウントが最大のノードを取得します。これを current_gene_node と呼びます。(たとえば、N0)
LOOP: current_gene_node を子孫に追加します。
そのノードを接続のリストから削除します。(サイクルがないため、N0 を考慮から除外します。)
current_gene_node が母集団に接続を持たない場合、母集団でランダムに選択されていないノードを選択します (突然変異)
そうでない場合は、そのノードの接続のリストから、母集団全体の接続の普及率に基づいて抽選を行います (current_gene_node = N0 で、接続 N0 が N1 = 50%、N2 = 30%、N3 = 20 の場合)。 % -- N1 が次の current_gene_node になる確率は 50% です)。
すべてのノードが接続されるまで LOOP に進む
2 人の親から直接選択するという意味では、実際には遺伝的ではありませんが、人口の有病率に基づいて選択するという同じ数学的圧力に従います。だから、それは私にとって「十分に遺伝的」であり、私にとってはかなりうまく機能しています:-)
試すアイデア: ノードの位置を計量空間 (3 次元ユークリッド空間など) にエンコードします。「間違った」割り当てがないため、クロスオーバーは決して破壊的ではありません。このような割り当てから、最近傍ツリー、最小スパニング ツリーなどをいつでも構築できます。
これは、より一般的なアイデアの単なる例です。ツリーを直接エンコードせず、常にツリーを構築できる情報をエンコードします。難しいのは、子ツリーが親の重要なプロパティを保持するようにすることです。