TSPは、この質問の説明としてはあまり適切ではない可能性があります。理由は、あなたが単にいくつかの良いセットリストを探しているので、実際に最高のセットリストを探していないからです。
そうは言っても、あなたの問題は、何かがどこにあるかを見つけようとするために粒子フィルターを使用することをたくさん思い出させます。
メソッドをかなり微調整すると、次のようになります。
- 重み付き確率を使用して、100個のセットリストをランダムに生成します。それらのいくつかを手で選んでもらうと便利かもしれません。
- 各セットリストのスコアを計算し、それらを重みとして使用して、10個のセットリストをランダムに選択します。
- これらのセットリストごとに、加重確率を使用してランダムに10曲を生成します。たとえば、曲のスコアを重みとして使用して、変更する必要があるかどうかを判断できます(相対スコアが低いと、曲が変更される可能性が高くなります)。
- 必要に応じて、手順2と3を繰り返します。
- 現在のベストを選択するか、現在の100のいずれかをランダムに選択します。
100の例を使用しましたが、実行に時間がかかる場合を除いて、おそらく100万程度未満のほぼすべてのサンプルサイズを使用できます。選択した数と、選択したものから生成した数に注意してください。選択した数に生成された数を掛けたものが、最初に開始した数と同じである必要があります。
編集:
加重確率に精通しているのかわからないので、アルゴリズムにとってかなり重要なので、おそらく要約する必要があります。それぞれ重みが1〜3のACの曲があるとします。重み付けされた確率を処理する1つの方法は、[A、B、C](重み付けされていない)から100個の要素をランダムに選択する代わりに、実際には[A、B、B、C、C、C]から100個の要素をランダムに選択することです。Cの重さはAの3倍なので、ピッキングされる可能性は3倍です。
理想的には、その方法を使用している場合は、スコアを整数として保持し、比較的低くする必要があります(要素を選択するリストの最大長が長くなりすぎないようにするため)。精度の低下を気にしない場合(この場合はおそらく問題ありません)、確率を正規化し、それを使用して、サイズの点ではるかに予測可能なリストを作成することもできます。これは、重みを合計し、それぞれを合計で除算してから、すべての結果に1つの数値を掛けることによって実行できます。したがって、たとえば、重みが1〜3ではなく[1000,10000,100000]の場合、それぞれを合計(111000)で割ると、約[0.009,0.090,0.901]になり、これに100を掛けます(リストサイズが得られます)。約100)であり、最も近い整数に丸めると、次のようになります。[1,9、90]したがって、要素をランダムに選択するリストには、正確に1つのA、9つのB、および90のCが含まれている必要があります。再サンプリング(ステップ3)にAのみが選択される可能性がありますが、それが発生した場合は問題が発生しますが、それはかなりありそうにありません。その場合、おそらくプログラムを再実行する必要があります。それを回避する方法はいくつかありますが、アルゴリズムのランダム性の多くを失うことになります。
3)曲を変更するときは、その曲を置き換える可能性のあるすべての曲のスコアを計算します。重みが低い、または重みの一部未満*の曲をすべて削除し、スコアを重みとして使用して、それに置き換わる新しい曲をランダムに選択します(スコアがかなり高い場合は、実際には同じ曲になる可能性があります)。 。
*これはオプションですが、重量を0.0未満に設定できるので便利だと思われる場合は、実装するのは悪い考えではありません。