私たちが持っていると仮定して：
関数cost（R）を最小化しながら、UからセットRにSベクトルを選択するアルゴリズムが必要です
cost(R) = sum(abs(c-sumVectors(R))*w)
（sumVectorsは、次のようにすべてのベクトルを合計する関数です。whileはスカラー6sumVectors({< 1,2 >; < 3 ,4>}) = < 4,6 >を返します）sum(< 1, 2, 3 >)
ソリューションは最適である必要はありません。事前に設定された時間内に取得できる最善の推測を取得する必要があります。
どこから始めればいいですか？（できれば、遺伝的アルゴリズムよりも高速/スマートなものが望ましい）
これは最適化問題です。最適解は必要ないので、ランダムな解 (R のランダムなサブセット) から始めて、隣接する解のセット (追加または削除現在のソリューションのコンポーネントの 1 つ) で、それぞれのコスト関数が優れているものを示します。
より良い解決策を得るために、シミュレーテッド アニーリングをヒル クライミング検索に追加することもできます。場合によっては、より悪い解決策に移行し、後でより良い解決策にたどり着く必要があるという考え方です。シミュレーテッド アニーリングは、プロセスの開始近くでより悪いソリューションに移行できるため、より適切に機能します。アルゴリズムは、プロセスが進行するにつれて、より悪い解を許可する可能性が低くなります。
ここにあなたの問題を解決するために、いくつかのヒルクライミングのPythonコードのサンプルを貼り付けます: https://gist.github.com/921f398d61ad351ac3d6
サンプル コードでは、 はR常に へのインデックスのリストを保持し、ユークリッド距離Uを使用して近隣間の類似性を比較します。確かに、独自のニーズを満たす他の距離関数を使用できます。また、コードに注意してください。私はその場で隣人を取得しています。にベクトルの大きなプールがある場合は、事前に計算された近傍をキャッシュするか、比較を避けるために局所性に依存するハッシュを検討することもできます。シミュレーテッド アニーリングは、上記のコードに追加できます。UO(n^2)
ランダムに 1 回実行した結果を以下に示します。
U, =10で 20 個のベクトルのみを使用しSて、結果を最適解と比較できるようにします。山登りプロセスは 4 番目のステップで停止し、k 最近傍を 1 つだけ置き換えるより良い選択肢がなくなります。
また、考えられるすべての組み合わせを繰り返す徹底的な検索も実行します。網羅的なアプローチと比較して、山登りの結果がかなり良いことがわかります。82K ステップ以上の徹底的な検索を必要とする比較的小さなコスト (ただし局所的な最小値) を取得するのに 4 ステップしかかかりません。
initial R [1, 3, 4, 5, 6, 11, 13, 14, 15, 17]
hill-climbing cost at step 1: 91784
hill-climbing cost at step 2: 89574
hill-climbing cost at step 3: 88664
hill-climbing cost at step 4: 88503
exhaustive search cost at step 1: 94165
exhaustive search cost at step 2: 93888
exhaustive search cost at step 4: 93656
exhaustive search cost at step 5: 93274
exhaustive search cost at step 10: 92318
exhaustive search cost at step 44: 92089
exhaustive search cost at step 50: 91707
exhaustive search cost at step 84: 91561
exhaustive search cost at step 99: 91329
exhaustive search cost at step 105: 90947
exhaustive search cost at step 235: 90718
exhaustive search cost at step 255: 90357
exhaustive search cost at step 8657: 90271
exhaustive search cost at step 8691: 90129
exhaustive search cost at step 8694: 90048
exhaustive search cost at step 19637: 90021
exhaustive search cost at step 19733: 89854
exhaustive search cost at step 19782: 89622
exhaustive search cost at step 19802: 89261
exhaustive search cost at step 20097: 89032
exhaustive search cost at step 20131: 88890
exhaustive search cost at step 20134: 88809
exhaustive search cost at step 32122: 88804
exhaustive search cost at step 32125: 88723
exhaustive search cost at step 32156: 88581
exhaustive search cost at step 69336: 88506
exhaustive search cost at step 82628: 88420
すべての可能なセット R と最小化のコストを確認する必要があります。追加するたびにコストを最小化する段階的な方法でベクトルを選択すると、最小コストのセットが見つからない場合があります。ベクトルのセット U が非常に大きく、計算が遅すぎる場合は、段階的な方法を使用せざるを得ない場合があります。
あなたの問題は本質的に組み合わせ最適化の問題です。これらを解決するのは難しいですが、いくつかの提案をすることができます。それらは、すべての組み合わせを探索することはできないという考えに基づいているため、貪欲に最適なソリューションの近くで探索する必要があります。
beam-searchと呼ばれる非常に一般的な方法があります。これは、限られたメモリ (ビーム幅) で動作するようにベスト ファースト検索を本質的に変更するヒューリスティックな方法です。これは、特定の部分解について、新しいメンバーをセットに追加することに関連するスコアと、現在のセットのスコアを計算できるという概念に依存しています (問題ない目的関数があるため)。次に、空のセットから開始し、スタック上のすべての状態に対して n 個の最良の次の状態を継続的に選択し、すべてが展開されたら、スタック上の n 個の最良の状態を除くすべてを破棄して繰り返すという考え方です。これにより、n 個の可能なソリューションが得られ、最高のスコアを選択できます。
ただし、目的関数の詳細により、この選択ベクトルがすぐに制約に近くなり、(コスト ベクトルとコンポーネント ベクトルの相対的なスケールに応じたいくつかのステップの後) 小さなベクトルを探すため、これはうまくいかない場合があります。差を縮めます。その場合、この方法の解を使用して、ランダム ウォーク/シミュレーテッド アニーリング戦略を初期化し (セットからランダムに追加または削除できるようになります)、ビーム検索で得た解に近いより良い解を探すことができます。