問題を解決するためにシミュレーテッド アニーリング ヒューリスティックを実行することを追求する中で、現在提案されているソリューションの近傍を生成する最良の方法を見つけようとしています。
ソリューションは、整数位置 (p1、...、pN) のベクトルの形で提供されます。これは、バイナリ チェーンとして理解しています。
0 0 0 0 1 0 ... 0 0 1 0 ... 0 1 0 0
p1 pj pN
いくつかの制限があります (すべての j について pj - p(j-1) > D、および p1 > D/2、長さ - pN > D/2)。
今、私の考えは、レーベンシュタイン距離に似たものを使用して新しいソリューションを作成することです。したがって、[0,1,0,0,1,0] (D=3) があり、より少ない距離内に新しい状態が必要な場合または1に等しい場合、たとえば[1,0,0,0,1,0]を取得できますが、[1,0,0,1,0,0]は取得できません。
私が（Rで）行うことは次のとおりです。
GenNewSeq <- function(seq, D, dist){
for(i in 1:dist){
Diffs <- c((ceiling(D/2)+seq[1]),diff(seq),(ceiling(D/2)+seq[length(seq)]))
position <- sample((2:length(seq))[Diffs > D], size=1)
move <- sample(c(-1*as.integer(Diffs[position-1]>D),0,1*as.integer(Diffs[position]>D)), size = 1)
seq[position-1] <- seq[position-1]+move
}
seq
}
少しあいまいかもしれませんが、必要に応じて、それが何をするのかをよりよく説明できます。問題は、これが 1) 遅い (回避方法がわからないfor)、2) 奇妙に意図したとおりに動作しないことです。最後の位置だけを移動したり、常に同じ要素を前後に移動して安定させることは多すぎる傾向があるため、シミュレーテッド アニーリングで偏った結果が得られます。
距離の制限を取り除き、フィットネス関数 ( のようなものexp(D-(pj-p(j-1)))) に入れることを考えたので、単純に法線で移動するか、完全に移動させてから振動させることができます...そして、そうなると思い始めています。最も簡単な方法であること。ただし、私が求めることを実行する効率的で信頼性の高いアルゴリズムをどのように実行できるかについてのリファレンスをいただければ幸いです.Cで実行する必要があるかどうかは気にしません.これを確認しましたが、できませんでした.私の疑問を解決するために。
ご助力ありがとうございます。