algorithm - 選択と突然変異だけの遺伝的アルゴリズムは、ヒル クライミング アルゴリズムとどのように同じですか?

Question

選択と突然変異のみを使用する (交叉なし) 遺伝的アルゴリズムを考えてみましょう。これは山登りアルゴリズムにどのように似ていますか?

記事でこのステートメントを見つけましたが、その理由がわかりませんか?

Answer 1

クロスオーバーのないヒル クライミングと遺伝的アルゴリズムはどちらも局所探索手法です。そういう意味では似ていますが、同じとは言えません。

山登りにはさまざまな形がありますが、遺伝的アルゴリズムにはないいくつかの特性を共有しています。

• 明確に定義された近隣関数が 1 つあります (1 つの解が与えられた場合、すべての近隣関数を列挙できます)。
• キャンセルされない限り、アルゴリズムは改善が見られる限り継続します (一定数の世代の後ではありません)。
• 反復中、ソリューションは 1 つだけです (ソリューションのプールではありません)。

実際には、適切な近傍関数を選択すると、ヒル クライミング アルゴリズムの有効性に大きな影響を与える可能性があります。ここで、追加のドメイン知識を使用できる場合があります。

遺伝的アルゴリズムでは、私が見た限りでは、ドメイン知識はミューテーターには使用されません。ほとんどの場合、ビットの反転や数値へのランダム ノイズの追加などの単純な手法を使用します。

ヒル クライミングは、ランダム性のない決定論的アルゴリズムとしてうまく機能します。問題によっては、それが重要なプロパティである場合とそうでない場合があります。そうでない場合は、山登りをランダムに再スタートすると、多くの場合、より良い結果が得られます。

要約すると、交叉なしで遺伝的アルゴリズムを使用すると、最終的にかなり悪いローカル検索アルゴリズムになります。優れたヒル クライミング アルゴリズムは、特に厳しい時間制約 (リアルタイム システム) の下にあるシナリオでは、それよりも優れていると期待しています。