Wer war da?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Organic Computing
Hallo,
im Sommersemester 06 gab es zum zweiten Mal Organic Computing, diesmal aber ohne Bobda.
War jemand von euch dort oder kennt jemanden, der es gehört hat?
Ich kann mich nicht mehr so recht daran erinnern, wer da so im Publikum saß, und hab jetzt bald Prüfung drüber…
cu
Ford Prefect
Dann missbrauche ich diesen Thread mal für eine Frage zum Ant-Cycle:
Wie genau läuft das jetzt ab?
Nachdem alle Ameisen ihre Tour gelaufen sind, wird die beste Tour (die die Ameise k gefunden hat) genommen und ihr Länge bestimmt: L(k).
Anschließend wird über jede Kante iteriert und wenn diese ein Teil dieser besten Tour war bekommt sie noch einen Pheromon-Schub: + Q3 / L(k) inklusive Verwitterung des alten Intensitätswerts?
Habe ich das so richtig verstanden?
Ahh, danke. Das war also ein „Q_3“, nicht „Q_2“, so macht das gleich viel mehr Sinn :-). (Spätestens jetzt) versteh ich das als komplett eigenständige Pheromonausschüttung, also nicht „noch ein Schub“, sondern in den ersten n-1 Iterationen wird gar nichts verteilt und dann nur das. Warum ich das mit meiner Interpretation des Algorithmus als einzig sinnvolle Approximation von echten Ameisen ansehe, folgt in der folgenden Beschreibung meines Problems 
:
(*) Ich bin mir momentan nicht sicher, ob ich die ersten 2 Varianten richtig verstanden habe. Bei Nr. 2 ist die Pheromonausschüttung ja nur von der Kantenlänge abhängig, also egal wie schlecht der Gesamtweg ist, kurze Kanten bekommen immer viele Pheromone. Das steht im Gegensatz zu realen Ameisen: Die Pheromonkonzentration auf einer „kurzen Kante“ die in einem langen Weg enthalten ist, hat natürlich die selbe (niedrige) Konzentration, wie die langen Kanten auf dem (Gesamt-)Weg. Wie oft die reale Ameise auf einem Wegstück vorbeikommt, hängt ja von der Gesamtweglänge ab.
Hier setzt Q3 an: Es ist natürlich auch unlogisch, die Pheromone erst am Ende zu verteilen. Aber: Eine Ameise, die eine Distanz von L^(k) zurücklegen muss, erhöht die Konzentration auf jedem „Wegstück“ um 1 / L^(k), was genau der Aufenthaltswahrscheinlichkeit entspricht. Besser versteht man mich vielleicht mit 100 Ameisen, L = 10m: Dann verteilen auf jedem Meter 100 * 1m/10m = 10 Ameisen Pheromone, die Konzentration ist korrekt approximiert.
Folglich erhöht sich die Konzentration aller beteiligten Kanten um 1 / L^(k), kurze Wege haben eine hohe Konzentration und ich bin glücklich. [speziell @Nyx: Das Maß löst damit auch das Problem mit der Wahl des Startpunkts, falls du dich an die Diskussion erinnerst]
Nun zu meinem Problem, namentlich Ant Quantity und Ant Density, also die Maße mit Q_1 und Q_2. So wie ich Q_2 im Absatz (*) beschrieben habe, dürfte doch nicht viel mehr passieren, als das kurze Kanten immer mehr Pheromone anhäufen. Das ist natürlich prinzipiell nicht schlecht, aber wenn das wirklich das einzige ist, könnte ich die Sache mit den Pheromonen auch sein lassen, jede Ameise wählt die Kanten mit Wahrscheinlichkeit (1 / Kantenlänge) / (Summe aller Wskten). Q_1 würde sich durch die Sichtbarkeit η = 1 / Kantenlänge vermutlich ähnlich verhalten.
Den Vorteil realer Ameisen, dass Kanten, die Teil eines kürzeren Weges sind, öfter besucht werden, verlieren wir ja durch unsere diskreten Zeitschritte. (Abgesehen von Q_3, wo wir das künstlich wieder einbauen)
Was übersehe ich, das den Pheromonen bei Q_1 und Q_2 einen wirklichen Sinn verleiht??
So, nachdem ich mittlerweile komplett verwirrt war, habe ich zum guten alten Buch über Ant Colony Optimization gegriffen, das in unserem Haushalt noch so rumlag (wie konnte ich das überhaupt vergessen!?). [Buch]
Ich zitiere:
Damit hat sich also schonmal ein Denkfehler von mir geklärt: das sind drei komplett unterschiedliche Systeme und der Ant-cycle mischt sich nicht noch in die anderen Systeme ein - was ich ja dachte.
In der Aufzeichnung steht zwar auch Q2, aber Q3 macht mehr Sinn und wurde auch in der Vorlesung von vor 2 Jahren hingeschrieben. Also wahrscheinlich diesmal nur ein kleiner Tafelanschriebsfehler.
Ich vermute, dass du prinzipiell zwar recht hast, aber dass es sich eben bloß um eine Heuristik handelt. Und anscheinend keine sehr guten:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.9732&rep=rep1&type=pdf
Vielleicht lass ich die Ants dann nochmal gegen die alleinige “Kantenlängenheuristik” (bzw. ne höhere Potenz davon) antreten. Ich würde da keinen all zu großen Unterschied erwarten, mal sehen.
Hi,
Maddoc und ich haben in der Vorlesung fleissig mitgetext, hier das Ergebnis.
Falls was falsch sein sollte darf gemeckert werden 
http://uni.0xce.de/file/OC__Mitschrift.pdf
Letzte Aenderung:
-chris
2 „Gefällt mir“
Echt gute Arbeit!
Hab ne frage zur Seite 13, muss das beim Punkt Ameisenkolonie wirklich argmax [und nicht wie ich glaube argmin] sein?
Wenn ich das richtig verstanden habe würde argmax uns doch dann zu der Strecke führen, wo am meisten Phermone drauf sind und nicht zu der mit den wenigsten. Das verwirrt mich gerade ein wenig. [Bei mir steht nämlich auch argmax] Wenn nein warum nicht?
Overall Skript bekommt von mir die Note 1.0
Hoffe daraus folgt auch eine Solche Note in der Prüfung
Ps.:
- (13) Ich hab im argmax noch einen Wahlweisen Parameter S drinnen, der steuert die Exploration. Aber der ist nicht zwingend notwendig.
- (14) Beim Graphen hab ich vor der Terminierungsbed. nochmal eine Selektion drinnenstehen (Wie auf den Folien mit Sel.1 & Sel.2)
Hi,
die Umweltselektion hab ich an der Stelle irgendwo verloren.
Ist in der aktuellen Version eingefuegt.
Zum Thema [m]argmax[/m]:
Wenn man die Kante mit dem maximalen Pheromon verwendet, dann wuerde man die Kante auswaehlen, die sowieso mit bereits hoher Wahrscheinlichkeit gewaehlt worden waere.
Von daher muss ich dir an der Stelle recht geben: argmin wuerde mehr Sinn machen.
An welcher Stelle hast du denn den Parameter S ? Wenn ich dich richtig verstehe, dann steht das S im argmax - was hat das dann ueberhaupt fuer einen Einfluss?
-chris
Ich hab mir noch notiert, dass Prof. Wanka etwas im Stil von „könnte auch die kürzeste / längste / min. Intensität Kante sein“ gesagt hat, also Hauptsache irgendetwas anderes.
Edit: Von einem S steht bei mir nix.
ok, ich mal grad drüber nachgedacht. Es macht einfach kein Sinn, dass da ein S steht 
Aber bei mir steht: argmax{tau_{i,j}^alpha * S}
Falls mir noch eine ominöse Erklärung dafür einfällt, dann werde ich das hier kundtun. Aber nunja bis hierhin erstmal quark mit soße.
Das. Ein konstanter Faktor in der argmax Funktion würde irgendwie keinen Sinn machen 
1 „Gefällt mir“