AntME und Simulated Annealing

Hallo Community!

Im Rahmen einer Semesterarbeit sollten wir uns mit einem frei wählbaren Artikel beschäftigen, diesen analysieren und bewerten. Desweiteren sollen wir einen eigenen Ansatz entwicklen und umsetzen.
Mein gewählter Artikel befasste mit sich der Entwicklung einer KI für das Spiel DEFCON. Die Autoren verwendeten unter anderem dafür Simulated Annealing (SA). SA ist vergleichbar mit genetischen Algorithmen, also Algorithmen zum Lösen kombinatorisch komplexer Probleme.
In meinem eigenen Ansatz würde ich auch gerne SA verwenden, am liebsten in dem Framework AntME. Nur leider fällt mir kein Anwendungsfall ein, wo ich SA in diesem "Spiel" verwenden kann.

ich hoffe ihr habt ne gute idee

Gruß Athlord

Von welcher Schulstufe reden wir?
Habe irgendwie den Eindruck, dass du dich damit übernimmst.

Schulstufe? Semesterarbeit... Er ist an der Uni, Junge!

hehe keine schule, bin masterstudent
mein problem ist, das ich irgendwie keine kombinatorisches Problem in antme finde... kann aber gut sein das ich etwas blind bin... habe noch nie antme verwendet...

vieleicht gibst du uns mal ein paar details zu dem was genau du in antme machen willst/sollst. die infos auf deren seite sind viel zu vage. und lust mich damit jetzt intensiver zu beschäftigen nur um dir da ne antwort zu geben hab ich auch nicht grad.

und musst du SA verwenden oder willst du es nur? ich frage weil SA ansich für die meisten anwendungsfälle, besonders für die von dir genannten szenarien inklusive defcon (hab das paper dazu sogar gefunden) eine durchaus schlechte wahl ist.

SA ist gut, wenn man so gut wie nichts über das zu lösende problem weiß und damit keine angrifspunkte hat um eine speziell auf das problem zugeschnitte lösung basteln zu können.
deswegen wäre es sehr wichtig zu wissen was genau du in antme zu tuen hast, was genau die spielregeln sind etc.
das ist im grunde, was sie bei DefCon gemacht haben.

aber generell zu SA als mittel zur KI:
was man machen kann um mithilfe von SA eine KI zu etnwerfen ist z.b. sowas:

man definiert sich formal einen raum von strategien. d.h. eine strategie wird irgendwie formal definiert udn parametrisiert. das problem ist es nun mit den parametern so zu spielen, dass man eine beste strategie findet (für das gegebene spiel).

nun, ich nehme ja an, dass du bereits weißt wie SA funzt.
also, was dir fehlt ist eine fittnessfunktion, die deine strategien bewertet. die fitnesfunktion ist aber hier wie gut deine ameisen im spiel büerleben.

- d.h. was du machen musst/kannst ist eine startlösung zu wählen (eine erste strategie)
- dann bewertest du diese indem du die simulation eine fixes zeit lang laufen läst
- dann triffst du deine etnscheidungen und ggf. wählst du eine nachbarlösung aus (SA)
- und dann musst du die neu gewählte strategie wieder bewerten in dem du das spiel weiter laufen läßt, jetzt aber mit der neuen strategie für deine ameisen.

noch etwas. du kannst mit SA natürlich auch nur einen teil deiner ki so bestimmen. also die strategie, die du mit SA verbesserst ist nur ein baustein deiner gesamten ki.

Bei antMe handelt es sich um eine Simulation einer Ameisenkolonie. Das Framework biete eine grafische Darstellung der Ameisen an. Der Entwickler muss "lediglich" das Verhalten der Ameisen programmieren. Zum Beispiel müssen Ameisen losgeschickt werden um die Umgebung zu erkunden und es müssen gewisse Ressourcen eingesammelt werden, welche Punkte geben. Desweiteren gibt es Ameisenfeinde in Form von Käfern.Vor diesen kann man fliehen oder diese angreifen... usw. Ziel des Spiels ist es die höchste Punktzahl zu erreichen.

Ich will SA verwenden, weil es in dem paper vorkommt. Auf antme bin ich gestoßen und dachte halt das es eine recht interessantes framework für KIs ist. Was wir in unserem eigenen Ansatz verwenden ist uns überlassen. Jedoch macht es, so finde ich, Sinn SA und KI zu verwenden, wenn es in dem Paper vorkommt Wenn du eine andere Idee hast wo ich SA und KI verbinden kann, immer her damit das wäre auch toll! bin für vorschläge offen bin halt auf der suche diese beiden Sachen zu verbinden, da es in dem artikel vorkommt.

gedacht habe ich an so etwas wie das TSP (traveling salesman-Problem). Zum Beispiel eine wegfinduns-methode, basiert auf SA. oder ein anderes kombinatorisches Problem. Mein Problem ist, das ich mich zu wenig mit antMe auskenne um beurteilen zu können ob man SA in antMe verwenden kann. habe halt gehofft jmd kennt antME und SA (nicht böse gemeint )

übrigens macht die Verwendung von SA in der DEFCON-KI durchaus Sinn, die Autoren verwenden das um einen synchronisierten Angriff durchzuführen (Abschnitt 6 glaube ich). Das kobinatorische Problem ist da die Anzahl an möglichen Städten im Verhältniss zu dem maximalen Schaden... aber egal darum geht es nicht und führt zu weit

ich hoffe ich konnte deine fragen beantworten und danke für dein Interesse !

das mit dem ändenr der parameter habe ich auch schon gedacht. tatsächlich gibt es diese Parameter:
GeschwindigkeitModifikator = 0,
DrehgeschwindigkeitModifikator = 0,
LastModifikator = 0,
ReichweiteModifikator = 0,
SichtweiteModifikator = 0,
EnergieModifikator = 0,
AngriffModifikator = 0

du meinst also, dass man diese variabeln mit SA ändert und jedesmal in der Simulation bewerten lässt... eine gute idee... und auch interessant... meint problem ist... das ich von antME nicht weiß ob das geht. also so wie ich antme kenne, ist es so, dass du deine ki entwickelst und sie dann testes... wobei ein durchlauf dann mehrere minuten dauert.. das ist natürlich für die fitness-funktion viel zu langsam...

ich müsste irgendwie rausbekommen wie man bei antme eine simulation startet und der Rechner die sofort durchführt, also ohne grafische darstellung...

aber super idee, danke !

also, du programmierst doch eine z.b. c++ funktion, welche deine ki darstellt, richtig?

na dann geht das doch sehr wohl:

eine KI-funktion hat halt die startlösung (strategie) zu anfang. und macht für ne weile immer wenn deine ki-unftion aufgerufen wird ncihts anderes als diese eine strategie zu verfolgen und infos über den erfolt im allgemeinen zu sammeln.

aber dann irgendwann macht deine funtion erstmal was anderes:
nämlich sich nach einer besseren strategie um zu schauen, indem es ganz SA konform eine auswürfelt . diese neue wird jetzt ne weile benutzt statt der startvariante.

nachdem diese eine weile benutzt wurde wird entschieden ganz nach SA ob sie beibehalten wird, oder wieder die vorige genommen wird.

wohl gemerkt, dass ist nur ein ansatz. es gibt auch ganz andere möglichketien sa hier zu benutzen. das hängt alles davon ab, wie genau du dein ki problem definierst.


aber nochmal zu defcon und sa: mir scheint und ich mag mich irren, dass dir der sinn von SA nicht ganz klar ist. SA ist kurz gesagt eine mieserable methode probleme zu lösen. im grunde so ziemlich das schlechteste, was man machen kann... IMMER! es gibt keine probleme für die SA gut geeignet ist.

es gibt lediglich probleme zu denen uns nichts besseres einfällt.

SA ist genau dann sinnvoll, wenn einem mit den infos über die problemstellung nichts besseres einfällt als dumm rum zuraten. hier hilft SA das raten in die richtige richtung langfristig zu lenken. das ist aber SEHR langfristig. die analyse von SA garantiert zwar theoretisch das ereichen eines globalen optimus, bei genügend relaxierten bedingungen, aber das kann nahezu unendlich lange dauern.

ki in seinen varianten war mein vertiefungsfach. meine dipel hab ich aber in der theoretischen informatik gemacht (ja ki zählt trotz nicht zu verachtenden theoretischen anspruch meist zur praktischen informatik, z.m. bei uns). und ich arbeite seit kanpp 6 jahren in der forschung der theoretischen informatik an der uni.

ach noch etwas, wenn du für verschiedene ameisen verschiedene ki-funktionen nutzen kannst, dann geh doch ein bissle mehr in die evolutionären algorithmen. d.h. es bietet sich an parallel mehrere strategien laufen zu lassen und sich die stärkste selbst den weg erkämpfen lassen. man kann da auch mit sa kombinieren.

den weg den du zuletzt beschrieben hast, habe ich auch gedacht... jedoch wusste ich nich wie man das mit sa verbindet jetzt weiß ich es .

meine idee, welche ich oben versucht hatte zu beschreiben, ist wie folgt:

in antme gibt es schon vorgefertigte KIs. Beispielsweise eine KI die sich auf das sammeln von Zucker spezialisiert hat (es gibt als ressource zucker und äpfel, welches beides vor- und nachteile hat).
es gibt noch andere, fertig implementierte KIs, zum Beispiel eine Kampf-KI, welche die Feinde (in form von Käfern) angreifen, auch das gibt Punkte.
Die Parameter, welche ich oben gepostet hab, geben die allgemeinen Eigenschaften einer Ameise an. Also wie schnell sie sich dreht, wie viel Lebensenergie sie hat usw. wie du siehst realtiv viele Parameter. Diese Parameter kann man beliebig ändern, jedoch muss die summe aller Parameter immer 0 ergeben. Daraus ergibt sich eine unendliche anzahl an Kombinationen.
Meine Idee war es nun, eine vorgefertigte KI zu verwenden (also keine eigene zu entwickeln) und bei jedem durchlauf mit SA diese Parameter zu verändern und in dem Spiel zu testen. Das Spiel wäre dann meine Fitness-Funktion.

mich würde interessieren ob du meine Idee verstanden hast und ob du sie für SA geeignet findest.

zu dem thema das SA nicht performant ist: kannst du durchaus recht haben, ich habe mich mit dem paper das erste mal mit heuristischen Verfahren beschäftigt und SA. in dem was ich zu SA gelesen habe, steht halt drin das SA nicht die gesamte Lösungsmenge betrachtet, sondern nur einen Teil davon. Eine Frage nich. wenn du SA als so schlecht einstufst, siehst du dann genetische Algorithemn ähnlich ? weil die Funktionsweise ist ja (relativ) ähnlich. da stochert man ja auch "im dunkeln " rum oder ?

danke für deine kompetente antwort!

ich hab deinen ansatz verstanden und er ist durchaus gut geignet für SA, oder auch genetische ansätze.

zu deiner allgemeinen frage:
1. SA kann durch aus die gesamte lösungsmenge betrachten. ob es das tut hängt von der definition der nachbarchaft ab und vom zufall
2. wie ich sagte, sa hat durch aus seine anwendungsgebiete. insofern ist es kein schlechtes verfahren. nur oft wird sa benutzt, weil sich diejeningen nicht passendere optimierte algorithmen überlegen konnten/wollten.
3. genetische algorithmen sind sa durchaus sehr ähnlich. es sind halt beides randomisierte lokale suchen.
4. es gibt eine recht flotte alternative zu SA, nennt sich Kernighan-Lin (bzw. Lin-Kernighan). das eine ist eine lokale suche für Graph Bisection und das andere für TSP. In der praxis bringt es genau so gute ergegnisse wie SA jedoch um faktoren schneller. KL wird auch als lokale suche in variabler tiefe bezeichnet. die kunst ist hier eine geeignete nachbarschaft zu definieren und eine geeignete mutations funktion (funktionen um einen nachbarn zu wählen), aber das problem hat man ja auch bei SA.