Ameisenalgorithmus (am Traveling salesman problem) |
| 16.05.2010, 22:07 | Letley | Auf diesen Beitrag antworten » |
| Ameisenalgorithmus (am Traveling salesman problem) Hallo alle zusammen, Ich muss zur zeit eine Projektarbeit an der schule leisten, mein thema lautet Ameisenalgorithmus und dies werd cih anhand des TSP vorführen. Ich hab nun alle mathemtischen formeln dafür zusammengefasst, doch so ganz versteh ich die mathematik nicht dahinter: Verwendung des Ant System am TSP Das Ant System gehört zu der Klasse von approximativen Lösungsverfahren. Um das Ant System auf eine modellierte Welt zu übertragen bietet sich hier das Traveling Salesman Problem (TSP) an. Das Travelling Salesman Problem ist ein kombinatorisches Optimierungsproblem, dessen Aufgabe es ist, die kürzeste Reisestrecke des Handlungsreisenden, welcher mehrere Orte einer gegebenen Menge (n) genau ein Mal besucht und wieder zum Ausgangsort reist, zu bestimmen. Dieses Problem ist NP-hart, welches bedeutet dass die Algorithmen nur mit exponentieller Laufzeit bekannt sind, die zu einem optimalen Lösungsverfahren führen. Mathematisch gesehen gibt es für dieses Problem n! mögliche Reisestrecken, sie lassen sich auch Graphisch darstellen G = (N, E) , wobei N = {1, 2, . . . , n ) die Anzahl der Städte angibt und E die Verbindungen der Städten präsentiert. Die Entfernung zwischen den Städten i und j können auf der euklidischen Ebene berechnet werden(Euklidischer Abstand) , dir Formel dafür lautet. Auf der Strecke von Stadt i und j liegt nun das Pheromon, es wird als Variable dargestellt, diese Variable spiegelt sich an dem Lernprozess der Ameisen wieder und für jede Iteration ändern sich die Werte. Außerdem wird noch eine Art Gedächtnis der Ameisen k modelliert, Diese Variable ist die Menge der noch nicht besuchenden Städte am Standpunkt i der Ameise. Der Übergang einer Ameise von Stadt i nach Stadt j wird als Wahrscheinlichkeit beschrieben welche sich mit der Formel erfassen lässt. Hier wandert eine Ameise k aus der Stadt i in die nächste Stadt j, deren Verbindung die höchste Wahrscheinlichkeit hat. Außerdem wird in der Formel die Attraktivität eines Pfades und deren Pheromonkonzentration , welches sich auf dem Pfad befindet, beschrieben. Hier werden zwei Parameter eingesetzt, die das Verhalten der Ameisen zu einer exakten Messgröße einstellen (justieren), wie z.B. ob sie explorativ neue Wege beschreiten werden. Die Formel beschreibt die Menge der Ausschüttung an Pheromon einer virtuellen Ameise auf einem Pfad. Im Gegensatz zu realen Ameise, welche ihre Pheromonspur direkt beim Beschreiten des Weges markiert, geschieht es bei virtuellen Ameisen erst nachdem eine vollständige Tour von einer Ameise konstruiert wurde. Der Parameter Q ist frei bestimmbar, die dadurch entstehende Größe des Betrags ist abhängig von der Länge der Tour , welche die Ameise bestritten hat. So errichtet jede virtuelle Ameise eine komplette Tour, welche sich von der Geschwindigkeit der anderen Touren unterscheidet(Zeiteinheit). Trifft der Fall ein, dass eine Kante (i,j) des Graphen nicht zur Tour der Ameise gehört, so wird keine Pheromonspur auf diesem Weg hinterlassen. Nun werden mehrere Zeiteinheiten summiert, so dass das Pheromon auf allen Kanten aktualisiert wird und die Summe der Pheromone der einzelnen Ameisen auf allen Pfaden addiert wird. Außerdem verdunstet das Pheromon (Evaporation) auf den längeren Wegen, da diese nach einer Zeit nicht mehr belaufen werden, weil die kürzeren Wege von den Ameisen bevorzugt werden. Die natürliche Evaporation p der Pheromone wird durch eine einfache Multiplikation modelliert. Da nun die kürzesten Reisestrecken der Ameisen eine sehr hohe Pheromonkonzentration haben, wird sie auch häufiger belaufen und die Pheromonkonzentration auf den längeren Wegen verdunstet. So entsteht wie im biologischen Vorbild die kürzeste Strecke. ok das is jetzt bitter die formeln wurden nicht mit kopiert, wenn ihr interesse habt mri zu helfen meine email adresse lautet [email protected] Meine Ideen: Dies wollte ich nun Anhand einer Beispiel aufgabe erklären indem ich mir koordinaten aus städten in deutschland ausgesucht habe: Bremen(136/436) Hamburg(214/482) Berlin(457/382) München(314/0) Düsseldorf(0/264) und Bremen ist der Startpunkt. http://ultrashare.de/f/6441/Ameisenalgorithmus-AS.odt.html (mit formeln! , ist für openoffice) unter diesen link könnt ihr meine gesammte arbeit des projektes runterladen ich hoffe ich habe viele von euch ebgeistert und hoffe ihr könnt mir weiter helfen 
|
||
| 16.05.2010, 22:35 | Letley | Auf diesen Beitrag antworten » |
http://ultrashare.de/f/3461/Ameisenalgorithmus.doc.html (für microsoft word mit formeln
) |
||
|
|
