1

最近、マルチナップザック問題の伝統的な遺伝的アルゴリズムを改善しています。したがって、私の改良された遺伝的アルゴリズムは、従来の遺伝的アルゴリズムよりもうまく機能しています。テストしました。(私は OR-Library ( http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html ) から公開されているものを使用して GA をテストしました。) 他の改善された GA を知っている人はいますか? 他の改良された遺伝的アルゴリズムと比較したかったのです。実はネットで調べました。しかし、比較するのに適したアルゴリズムが見つかりませんでした。

4

3 に答える 3

1

比較できる適切なGAメソッドはいくつもあるはずです。ただし、最初に、すでにテストした「従来の」GAメソッドを正確に確立するようにしてください。

私がお勧めできる良い方法の1つは、多目的最適化のために開発されたNSGA-IIアルゴリズムです。

他のアイデアについては、以下をご覧ください。

于 2010-06-23T02:23:12.910 に答える
1

解は、エンコーディングとフィットネス関数がまったく同じ問題 (同等の問題であることを意味します) とのみ比較できます。問題が異なる場合、問題が変化するにつれて、比較はすぐに無関係になります。これは、ほとんどの場合、解決しようとしているものに対してフィットネス関数がアドホックであるためです。実際、遺伝的アルゴリズム ツールキットを使用する場合、コーディングする必要があるのはフィットネス関数だけです。他のすべては通常、箱から出してすぐに使用できます。

一方、適合度関数が同じ場合、異なる突然変異率、交差の異なる実装、さらには共進化、遺伝子発現などの完全に異なる進化パラダイムなど、異なるパラメーターを指定して結果を比較することは理にかなっています。標準GAなどに。

于 2010-06-10T16:09:36.787 に答える
0

遺伝的アルゴリズムを使用して、最先端のマルチナップザック ソルバーを改善しようとしていますか? それとも、マルチナップザックをテスト プラットフォームとして使用して、遺伝的アルゴリズム技術を進歩させようとしていますか? （はっきりさせてもらえますか？）

どちらを目標にするかによって、質問に対する答えはまったく異なります。他の人が後者の質問に取り組んでいるので、私は前者を想定します。

基本的な遺伝的アルゴリズムに関しては、大きな飛躍と限界はほとんどありません。遺伝的アルゴリズムを使用してマルチナップザックを解決する際の最良の改善は、結果のパフォーマンスに桁違いの違いをもたらし、基本的な遺伝的アルゴリズムへの微調整を水から吹き飛ばすことができる、突然変異およびクロスオーバー演算子のエンコーディングを改善することです。 . ミューテーション オペレーターとクロスオーバー オペレーターをマルチナップザックに合わせて作成するためにできることはたくさんあります。

まず、マルチナップサックに関する文献を調査して、人々がマルチナップサックで使用したさまざまな種類の検索スペースとソリューション テクニックを確認します。最適または準最適な方法 (遺伝的アルゴリズムとは無関係) では、どのような種類の検索演算子を使用しますか? 何を変数としてエンコードし、何を値としてエンコードしますか? どのヒューリスティック評価関数が使用されていますか? 彼らはどのような制約をチェックしますか? 次に、それらのエンコーディングを突然変異演算子と交差演算子に適合させ、遺伝的アルゴリズムでどれだけうまく機能するかを確認します。

マルチナップザック問題の効率的な検索空間エンコーディングまたは正確なヒューリスティック評価関数は、非常に効果的な突然変異および交差演算子に変換できる可能性が非常に高いです。マルチナップザックは、研究文献の大規模なコーパスで非常によく研究されている問題であるため、あなたにとっては金鉱になるはずです。

于 2010-06-23T07:22:37.603 に答える