GECCO 21 Parallel GA KNP

アルゴリズム選択問題の解決を高速化する並列遺伝アルゴリズム

著者:

• アレハンドロ・マレロ --- @amarrerod
• エドゥアルド・セグレド --- @esegredo
• コロモト・レオン --- @cleon

抽象的な：

特定の最適化問題を解決するためにどの最適化手法を使用するかを決定することは、最適化の分野で数十年にわたって直面してきた重要かつ困難な課題です。上記の問題は、アルゴリズム選択問題 (ASP) として知られています。多くの研究者が、ASP を使用してさまざまな問題を解決しようと試みてきました。これまで検討されてきた最適化手法は、主に高速に実行できる最適化手法でした。ただし、進化的アルゴリズムなど、ASP を解決するためのより高度な最適化アプローチを考慮すると、関連する計算コストが大幅に増加します。私たちは、よく知られている NP ハード 0/1 ナップサック問題 (KNP) に適用される遺伝的アルゴリズム (GA) のさまざまな構成を考慮して ASP を解決することに興味があります。上記には、KNP のさまざまな機能を備えた広範囲のインスタンスに適用した場合のパフォーマンスを評価するために、前述の GA の多数の構成を実行する必要があり、これは計算コストのかかるタスクです。したがって、現在の研究の主な目的は、ASP を解決するための最初のステップとして、最適な目標値の観点から、短期間で競合する結果を達成できる効率的な並列 GA を提供することです。計算結果は、私たちのアプローチが効率的に拡張でき、KNP インスタンスを解決するための平均経過時間を大幅に短縮できることを示しています。

---

紙

結果

スケーラビリティテーブル