群知能と進化的計算の国際ジャーナル

概要

Open MP を使用した Ant Colony Optimization の並列化のパフォーマンス分析とチューニング

アハメド・A・アブエルファラグ、ワリド・モハメド・アリ、アシュラフ・G・エルビアリ

要約: 蟻コロニー最適化アルゴリズム (ACO) は、群知能法に属するソフトコンピューティングメタヒューリスティックです。ACO は、多項式時間で特定の NP 困難問題を解く際に優れたパフォーマンスを発揮することが証明されています。この論文では、Open MP フレームワークを使用した並列メタヒューリスティックとしての ACO の分析、設計、実装について説明します。ACO 並列化の効率を向上させるために、スレッドのスケジュール、競合の危険性、有効なスレッド数の効率的な調整など、さまざまな関連する側面が検討されます。提案されたアプローチのパフォーマンスを評価するために、さまざまな構成を使用して巡回セールスマン問題 (TSP) を解決するケーススタディが提示されます。実験結果では、順次実装に比べて実行時間が 3 倍以上大幅に高速化されることが示されています。