無線ノードのセットが互いに近接しており、重複を最小限に抑えるために周波数を割り当てたいと考えています。エリアを完全にカバーするには、無線チャネルをオーバーサブスクライブする必要があるため、近くの無線が同じ周波数で送信されます。
サンプルデータ:
5 周波数
343 ラジオ
4158 エッジ
私の現在の最良の推測は、周波数割り当ての母集団をランダムに生成し、最高のスコアが 10 世代にわたって改善されなくなるまで無線間で周波数を交換することです。スコアは、同じ周波数の無線の 1/range^2 の合計です。
各エッジは無線間の距離で、壁と床を補正したものです。最大無線距離の 2 倍を超えるエッジはリストから除外されています。
より良い方法はありますか？
これは基本的に、ひねりを加えたグラフ彩色の問題です。スコアリングアルゴリズムで定義されているように、すべての適切なカラーリングが同等に優れているのではなく、一部の適切なカラーリングが他のカラーリングよりも優れています。
あなたの遺伝的アプローチは実用的であり、良い（証明できるほど最適ではないにしても）解決策を生み出すと思いますが、グラフ彩色の論文を見て、それらがどれほど適用可能かを確認することをお勧めします。アルゴリズムが利用可能な選択肢をどのように考慮するかを決定するためのいくつかの素晴らしいアイデアを得る可能性が非常に高いです。
ランダムな初期割り当てとそれに続く最適化に基づくシミュレーションが良いアプローチであることに同意しますが、私が正しく理解していれば、最適ではないように見える最適化手順を説明しています（私が読んだ場合、周波数をランダムに交換することを計画していますあなたは正しく）。各最適化ステップで、各周波数グループから1つの無線を取得し、それらの2つの間の周波数の可能なスワップを検討することにより、「合理的な」改善を5*4/2=10選択し、最良のもの、または（たとえば）正のデルタスコアを持つものの1つを選択できます。 、スコアのデルタに比例する確率で。
「シミュレーテッドアニーリング」の精神で、全体的なスコアがほぼ安定しているように見えたら、5つの無線機のセットを選択するだけの「高温」（高ランダム性）に少数のステップを切り替えることができます。そして、それらすべてを交換します。たとえば、周波数割り当ての循環順列を使用します。これを数回実行してから、上記の手順（最大勾配降下の安価なシミュレーションを取得しようとします）を使用して、「クールダウン」部分に再度進みます。 ;-)。
私がすぐに突き刺したのは、薄板スプライン（または、同様の、より巧妙な線形代数手法）を使用して、周波数密度の関数に平面を適合させることです。次に、各平面の平均「高度」（周波数ごと）は、周波数が過剰に使用されているかどうか（つまり、他の周波数よりも高い場合）を示します。傾きは、空間分布の指標になります。