Internationale Zeitschrift für Schwarmintelligenz und Evolutionsberechnung

Abstrakt

Eine vergleichende Studie prominenter Methoden auf Basis der Partikelschwarmoptimierung zur Lösung des Problems des Handlungsreisenden

Akhand MAH, Shaik Imran Hossain und Shahina Akter

Von Naturphänomenen inspirierte Computermethoden haben in den letzten Jahren stark an Interesse gewonnen. Unter den entwickelten Algorithmen scheint die Partikelschwarmoptimierung (PSO), die das Verhalten von Vogel- oder Fischschwärmen nachahmt, aufgrund ihrer Einfachheit und Leistung die bekannteste Methode zu sein. Für das Problem des Handlungsreisenden (TSP), das beliebteste kombinatorische Problem, wurde eine Vielzahl von PSO-basierten Methoden entwickelt. Ziel der Studie ist eine vergleichende Studie mehrerer bekannter PSO-basierter Methoden zur Lösung des TSP. Die Studie ist wichtig, da unterschiedliche PSO-basierte Methoden von verschiedenen Forschern entwickelt und an verschiedenen Problemstellungen getestet wurden. Daher offenbart die ähnliche Beschreibung der bekanntesten PSO-basierten Methoden unterschiedliche Merkmale der einzelnen Methoden. Darüber hinaus zeigen experimentelle Ergebnisse an einem gemeinsamen Benchmark-TSP-Datensatz die Leistung jeder Methode. In dieser Studie wurden die Methoden an einer großen Anzahl von Benchmark-TSPs getestet und die Ergebnisse untereinander sowie mit der Ameisenkolonieoptimierung (ACO), der bekanntesten Methode zur Lösung des TSP, verglichen. Die experimentellen Ergebnisse zeigten, dass Enhanced Self-Tentative PSO (ESTPSO) und Velocity Tentative PSO (VTPSO) ACO übertrafen; und Self-Tentative PSO (STPSO) ist mit ACO konkurrenzfähig. Andererseits ergab die experimentelle Analyse, dass ESTPSO rechenintensiver ist als andere und VTPSO am wenigsten Zeit benötigte, um ein Benchmark-Problem zu lösen. Die Gründe für Leistung und Zeitbedarf jeder einzelnen Methode werden erläutert und VTPSO ist die effektivste PSO-basierte Methode zur Lösung von TSP.