Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Neuer Abschnitt in Lösen eines TSP durch 96 französiche

Das symmetrische Rundreiseproblem(Travelling Salesman Problem) und der Ameisenalgorithmus

Bild schwarz und orange: 2 Rundreisen. Definition eines symmetrischen Rundreiseproblems: Gegeben sind n Städte (bei mir n = 96). Eine Rundreise ist ein geschlossener Weg durch alle Städte, bei dem jede Stadt genau 1x besucht wird. Bei einem symmetrischen Rundreiseproblem gilt: d(a,b) = d(b,a) mit d als Abstand zwischen Stadt a und b. Gesucht ist von allen Rundreisen die kürzeste. Eigenschaften eines Rundreiseproblems: - es gibt ca. n! Rundreisen (bei n = 96 sind das ca. 9.9*10^149) - es ist NP-vollständig, also algorithmisch schwer lösbar (siehe Literatur) - als Bezeichnung wird verwendet: Rundreiseproblem, Travelling-Salesman-Problem oder auch Travelling-Salesperson-Problem (mein Rundreiseproblem kann man "TSP96" nennen)
eine globale Pheromonmatrix - ziemlich am Ende der Optimierung Kurzbeschreibung eines Ameisenalgorithmus: Ein Lauf des Ameisenalgorithmus besteht aus: Es laufen nacheinander n Ameisen mit den n Städten als Startpunkt der Route Rundreisen. Dabei wird die nächste Stadt in einer Route nach bestimmten Formeln bestimmt. Die beste der n Rundreisen wird gemerkt. Es werden eine globale Pheromonmatrix (ameise2 oder Tau) und eine temporäre Pheromonmatrix (ameise3 oder Delta-Tau) benutzt. Während eines Laufes werden die Ameisen "versuche"-mal auf eine Rundreise geschickt. Ein paar Formeln: - in der Pheromonmatrix werden neue/gute Wege mit hohen Werten belegt und erhalten so eine höhere Chance(Wahrscheinlichkeit) ausgewählt zu werden p_(ij)^k = ([\tau_(ij) (t)]^\alpha [\eta_(ij)]^\beta ) / sum([\tau_(ij) (t)]^\alpha [\eta_(ij)]^\beta,k \notel tabu_k ) mit \tau als globaler Pheromonmatrix und \eta_(ij) = 1/d(i,j) bzw. ug(j+1) = ug(j) + ameise2 ^ alpha*( 1.0d0/dist(i,j) ) ^ beta mit ug werden im Programm Intervallgrenzen bezeichnet. Aus den Intervallen wird dann zufällig eines ausgewählt. - in der temporären Pheromonmatrix (Matrix ameise3 oder \delta \tau ) werden die Wege, die zum Rundenminimum gehören belohnt(mit Zahl \delta ) \delta \tau(xx(i),xx(i+1)) = \delta \tau(xx(i),xx(i+1)) + \delta - die Pheromonmatrix "vergisst" mit der Zeit alte Wege (Bild oben Matrixeinträge in der globalen Pheromonmatrix aus schwarz wird kontinuierlich grau wird weiß) \tau(i,j) = max( , (\gamma*\tau(i,j)+\delta\tau(i,j)\, 1) ) - Verhinderung eines zu großen Anwachsens der globalen Phermomonmatrix durch leichtes Rücksetzen der temporären Pheromonmatrix Richtung 1 \tau(xx(i),xx(i+1)) = (1-\phi)*\tau(xx(i),xx(i+1))+\phi*1 - mit der Wahrscheinlichkeit \epsilon wird das größte Intervall (in der ersten Formel) ausgewählt, sonst zufällig eines der Intervalle Diese und noch mehr Formeln sind in dem Programm "TSP_81_96_Ameise.for" enthalten. Das Programm kann in meinem Notizbuch gefunden werden. Am Ende des Artikels habe ich ein paar Zahlenwerte für Parameter angegeben. Links: de.wikipedia.org/wiki/Problem_des_Handlungsreisenden de.wikipedia.org/wiki/Ameisenalgorithmus activevb.de/tutorials/tut_antalgo/tut_antalgo.html
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]