問題タブ [hill-climbing]

少し奇妙な質問があります。誰かが情報を見つける場所を教えてもらえますか、または山登り法を使用する最短経路アルゴリズムの使用について少し紹介してもらえますか？私は両方の基本を理解していますが、2つを組み合わせることができません。ウィキペディアには、山登り法で巡回セールスマンを解決することについて興味深い部分がありますが、それを正確に行う方法についてのより詳細な説明は提供されていません。

たとえば、山登り法は巡回セールスマン問題に適用できます。すべての都市を訪問する解決策を見つけるのは簡単ですが、最適な解決策と比較すると非常に貧弱です。アルゴリズムはそのようなソリューションから始まり、2つの都市が訪問される順序を切り替えるなど、小さな改善を行います。最終的には、はるかに優れたルートが得られます。

私が理解している限りでは、任意のパスを選択し、それを繰り返して、途中で最適化を行う必要があります。たとえば、戻って開始ノードから別のリンクを選択し、それによってパスが短くなるかどうかを確認します。

申し訳ありませんが、私は自分自身をあまり明確にしませんでした。このアイデアを巡回セールスマンに適用する方法を理解しています。最短距離アルゴリズムで使用したいと思います。

ウサコ問題「電気柵」の解法を書いています。この問題では、大量の線分の中から点の最適な位置を見つける必要があるため、点と線分の間の距離の合計は可能な限り小さくなります。

ヒルクライムを実行できる可能性があるという考えがあり、すべてのテストケースで機能しました。与えられた分析では同様の方法が使用されましたが、なぜこれが機能するのかは説明されていませんでした。

したがって、与えられたタスクにおける局所最適の存在を証明することも反証することもできません。誘導を使用して実行できるという考えがありましたが、機能させることができませんでした。手伝って頂けますか？

更新された定義

(x1,y1,x2,y2) 線分の集合から、関数を最小化する (x,y) 点 P を見つけます。

なんらかの理由で、問題には局所最適値が 1 つしか含まれていないため、次の手順を使用して解決できます。

問題は次のとおりです。なぜこれは、グローバルな最適状態に向かう途中で行き詰まらないのでしょうか? この素朴な手順を屈服させる地元の丘の頂上がないのはなぜですか?

巡回セールスマン問題を解決するために、単純な山登りアルゴリズムを使用しようとしています。これを行うためのJavaプログラムを作成したいと思います。使用するのに最適ではないことはわかっていますが、主に結果を確認してから、結果を次のものと比較して、これも作成します。

• 確率的ヒルクライマー
• ランダムリスタートヒルクライマー
• 焼き鈍し法。

とにかく、単純な山登りアルゴリズムに戻ると、私はすでにこれを持っています：

必要なのはこれだけですか？このコードは正しいですか..？プログラムに読み取って結果を生成させたいテキストドキュメントには、さまざまなデータセットがあります。

これについての助けを本当にいただければ幸いです。

- - - 編集 - -

私はばかで、最初にメモ帳で開く必要があったときに、JavaファイルをEclipseで直接開いていました。これが私が今持っているコードです。

私はしばらく確率的ヒルクライマーを理解しようとしてきましたが、うまくいきませんでした。ヒューリスティックに関する本を調べて、疑似コードを入手しました。確率関数がどのように見えるべきかわかりません。新しいソリューションがランダムに抽出され、ある確率に基づいて受け入れられることを理解しています。得られないのは、この確率をプログラムする方法です。ありがとう

PSUEDO-CODE - How to Solve it: Modern Heuristics - Zbugniew Michalewicz、David Fogel より

山登り法の検索を行うために変換しようとしているBFSのLisp実装があります。

私のBFSコードは次のようになります。

これで、BFSのように常に左側のノードを拡張するのではなく、目標状態に最も近いと思われるノードを拡張する必要があることがわかりました。
私が使用しているグラフは次のようになります。

上記のBFS実装でこれを機能させるための変換関数がありますが、このグラフ形式を使用してこれを山登り法に変換する必要があります。

どこから始めればいいのかわからず、何の役にも立たないように努力してきました。主に関数を変更して最も近いノードを展開する必要があることはわかってexpand-queueいますが、どのノードが最も近いかを判別する関数を作成できないようです。

助けてくれてありがとう！

2つのノード名（AとEなど）を取り、再帰的に使用されるオプションのパラメーター（キュー）を持つ既存のヒルクライム関数を変更しようとしています。あるパスが別のパスよりも安いかどうかを評価する関数「cheaper」を定義しようとしています。また、1つのゴールノードの代わりに、ゴールノードのリストを渡そうとしています。これらのノードの1つに到達すると、関数は評価を停止します。

問題は、入力した開始ノードと空のリストを除いて、関数が何も返さないことです。

これが私のネットワーク/グラフと関連するコストです：

そして、これが私の修正されたヒルクライム関数です：

最後に、「コスト」関数と「安価」関数を次に示します。

編集：申し訳ありませんが、ここに「拡張」があります：

私が取り組んでいるプロジェクトの一部としてランダム突然変異山登りアルゴリズムを使用しましたが、局所最適点でスタックする可能性を最小限に抑えるためにシミュレーテッドアニーリングを使用する方がよいかどうか疑問に思いました。

私が持っている質問は、あなたの経験から一般的にどちらが速い傾向があるかということです。明らかに、両方のアルゴリズムには非常に豊富なアプリケーションがあります。必要に応じて、これはより一般化された熟考です。

ありがとうございました。

ソリューションをランダムに生成し、そのソリューションをコピーして少し変更して、最終的により良いソリューションになるかどうかを確認するヒル クライミング アルゴリズムを作成しました。その場合、新しいソリューションを保持し、古いソリューションを破棄します。

このアルゴリズムにシミュレートされたアニーリングを追加したい場合は、高い突然変異率から始めて、新しいソリューションが作成されるたびに突然変異率を少しずつ下げることはできますか?

その場合、突然変異率はシミュレーテッド アニーリング アルゴリズムの温度として機能すると思いますが、それは正しいですか?

このコードは、2つの適合度を比較し、最良のものを使用して解を見つけ、次の反復で最良のものを使用する必要があります。しかし、私が得る問題は、それが大きいか小さいかに関係なく、最新のフィットネスを使用しているだけであるということです。私のコードに間違いがある場合、誰かが私を見つけるのを手伝ってくれますか、ありがとう！

これを説明するのは少し難しいので、誰かがさらに説明が必要な場合は、質問してください。プロジェクト全体を投稿しますが、エラーはこの小さなコードセクションに関係していると思います。

SmallChangeは次のとおりです。

ScalesFitnessとScalesSolutionは次のとおりです。