Das Ameise Kolonie Optimization (ACO) ist eine Metaheuristik für Verfahren der kombinatorischen Optimierung, die auf dem modellhaften Verhalten von realen Ameisen bei der Futtersuche basiert[1]. Viele Probleme können durch ACO sehr effizient bearbeitet werden. Zum Beispiel Job-Shop[2,3], Flow-Shop[4], Minimum Cost Permutation[5], Maschinenbelegungsprobleme, Minimierung der Transportzeit bei räumlich weit auseinander liegenden Produktionsstätten(Single Machine Total Tardiness problem)[6] usw. Marco Dorigo und Thomas Stützle[7] haben über das Problem des Handlungsreisenden (TSP) viele hilfreiche Formeln vorgestellt, um ein besseres Ergebnis zu bekommen. In dieser Masterarbeit werden durch Formeln einfach getestet bzw. ermittelt, wie gut das Ergebnis aussieht. Anschließend wird ein akuelles Thema GSP (The Gas Station Problem) vorgestellt. Samir Khuller, Azarakhsh Malekain und Julian Mestre[8] haben in ihrer Arbeit einige konkrete Probleme diskutiert. Dort haben sie auf theoretischer Ebene die günstigere Tour ermittelt. Zum Beispiel gibt es einige Tankstellen mit unterschiedlichen Benzin-Preisen. Ein Auto fährt von einer Startstadt zu einer Zielstadt und der Fahrer entscheidet, wieviel und wo das Benzin getankt wird. In dieser Masterarbeit werden zudem noch kompliziertere Annahmen beachten. Es kann entweder mit Strom oder Benzin auf den Straßen fahren. Zusätzlich kann das Auto noch unterwegs von Strom auf Benzin oder umgekehrt umschalten. Es kann beispielsweise das erste Drittel des Wegs mit Strom und den Rest mit Benzin fahren. Das Ziel ist es dabei, einen kürzeren Weg dazu so billig wie möglich zu finden. Wir versuchen, dieses Problem durch ACO durchlaufen zu lassen. Im allgeimeinen Fall findet jede Ameise eine günstige Tour d.h. die Ameise stirbt niemals unterwegs. Aber bei diesem Problem darf die Ameise irgendwo sterben, zum Beispiel stirbt sie in einer Stadt, weil sie nicht genug Benzin oder Strom im Tank hat. In dem Kapitel bzgl. der Zukunft der Arbeit stellen wir noch andere Algorithmen bzw. ACO kombiniert mit PSO vor. Der Unterschied zwischen diesen zwei Methoden ist der, dass bei ACO das Auto von Stadt i zu Stadt j immer auf einer geraden Linie und bei ACO mit PSO in einer Kurve fährt. Falls die Ameise einen Berg oder Fluß passiert, leitet sie den Weg um.
Das Ameise Kolonie Optimization (ACO) ist ein sehr mächtiger Algorithmus. Es gibt viele Varianten von ACO, die sich mit TSP beschäftigen. Es gibt keine Ideallösung, sondern es geht darum, immer eine bessere Lösung zu finden. Die konkrete Arbeitsweise wird im folgenden Kapitel mit einigen einfachen Beispielen erklärt.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:17250 |
| Date | 01 March 2018 |
| Creators | Xia, Chaohui |
| Contributors | Middendorf, Martin, Universität Leipzig |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German, German |
| Detected Language | German |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:15-qucosa2-163403, qucosa:16340 |
Page generated in 0.0083 seconds