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

概要

巡回セールスマン問題を解くための著名な粒子群最適化に基づく手法の比較研究

アクハンド・マー、シャイク・イムラン・ホセイン、シャヒナ・アクテル

自然現象にヒントを得た計算方法は、近年大きな関心を集めています。開発されたアルゴリズムの中で、鳥の群れや魚の群れの行動を模倣する粒子群最適化 (PSO) は、そのシンプルさとパフォーマンスから最も有名な方法のようです。最も一般的な組み合わせ問題である巡回セールスマン問題 (TSP) に対して、さまざまな PSO ベースの方法が開発されました。この研究の目的は、TSP を解決するためのいくつかの著名な PSO ベースの方法を比較研究することです。この研究が重要なのは、さまざまな PSO ベースの方法がさまざまな研究者によって開発され、さまざまな問題セットでテストされているためです。したがって、同様の方法で著名な PSO ベースの方法を説明すると、個々の異なる特徴が明らかになります。さらに、共通のベンチマーク TSP データ セットでの実験結果から、各方法のパフォーマンスが明らかになります。この研究では、多数のベンチマーク TSP で方法をテストし、TSP を解決するための著名な方法である蟻コロニー最適化 (ACO) と同様に、結果を比較しました。実験結果から、強化された自己試行 PSO (ESTPSO) と速度試行 PSO (VTPSO) が ACO より優れ、自己試行 PSO (STPSO) が ACO と競合することが明らかになりました。一方、実験分析により、ESTPSO は他のものよりも計算量が多く、VTPSO はベンチマーク問題を解決するのに最も時間がかからないことが明らかになりました。各方法のパフォーマンスと時間要件の背後にある理由が説明され、VTPSO が TSP を解決するための最も効果的な PSO ベースの方法であることがわかりました。