{"id":5908,"date":"2023-02-03T09:42:30","date_gmt":"2023-02-03T08:42:30","guid":{"rendered":"https:\/\/www.mi.uni-koeln.de\/NumSim\/?p=5908"},"modified":"2023-02-03T09:42:30","modified_gmt":"2023-02-03T08:42:30","slug":"thesis-snapshot-ameisenalgorithmen-metaheuristische-verfahren-zur-losung-des-travelling-salesman-problems-bachelorarbeit-von-marie-becker","status":"publish","type":"post","link":"https:\/\/www.mi.uni-koeln.de\/NumSim\/2023\/02\/03\/thesis-snapshot-ameisenalgorithmen-metaheuristische-verfahren-zur-losung-des-travelling-salesman-problems-bachelorarbeit-von-marie-becker\/","title":{"rendered":"Thesis Snapshot: Ameisenalgorithmen \u2013 Metaheuristische Verfahren zur L\u00f6sung des Travelling Salesman Problems (Bachelorarbeit von Marie Becker)"},"content":{"rendered":"\r\n
\r\n
\r\n

In den neunziger Jahren wurden erstmals Ameisenalgorithmen von Marco Dorigo vorgestellt. Der erste Algorithmus war das sogenannte Ant System (AS), welches in der Bachelorarbeit implementiert wurde, um das Travelling Salesman Problem zu l\u00f6sen. Dabei wird das Verhalten von Ameisen in einen Algorithmus \u00fcbertragen, um den k\u00fcrzesten Hamiltonkreis in einem Graphen zu finden.\r\n\r\nDie Ameisenalgorithmen bauen auf dem Prinzip auf, dass jede virtuelle Ameise, ausgehend von einem zuf\u00e4lligen Startknoten, einen Hamiltonkreis in dem gegebenen Graphen abl\u00e4uft und auf dieser Tour dann Duftstoffe, sogenannte Pheromone, hinterl\u00e4sst. Die hinterlassene Menge der Pheromone h\u00e4ngt dabei davon ab, wie lang die Tour einer Ameise ist. Durch die Duftstoffe werden andere Ameisen dazu angeregt, auch diesen Weg zu w\u00e4hlen. Je mehr Pheromone sich auf einer Kante befinden, desto wahrscheinlicher ist es, dass eine Ameise diese Kante in ihrer Tour w\u00e4hlt. Nach einigen Iterationen befindet sich also die gr\u00f6\u00dfte Menge der Pheromone auf dem k\u00fcrzesten Hamiltonkreis.\r\n\r\nEine Erweiterung dieses Algorithmus ist das Ant Colony System (ACS), welches ebenfalls auf das Travelling Salesman Problem angewandt wurde. Einer der Unterschiede zum Ant System ist es, dass die Ameisen alle die gleiche Menge an Pheromonen auf ihrer Tour hinterlassen und au\u00dferdem die beste Ameise ausgew\u00e4hlt wird, welche eine zus\u00e4tzliche Menge an Pheromonen auf ihrem Hamiltonkreis abgibt.\r\n\r\nIm Laufe der Jahre wurden weitere Modifikationen entwickelt, die sich auch auf andere Optimierungsprobleme anwenden lassen.<\/p>\r\n<\/div>\r\n<\/div>\r\n\r\n\r\n\r\n

\r\n