Planungsproblem: Genetischer Algorithmus?

Hallo,

ich wollte mich etwas mit automatisiertem Scheduling und der gleichen beschäftigen. Da mir momentan nichts sinnvolleres eingefallen ist, ist mein Projekt folgendes:

Ein "intelligenter" Raidplaner für OGame.
Bei OGame kann man andere Spieler(Planeten) Raiden (angreifen um Resourcen zu klauen), Planeten können sowohl mit Schiffen als auch fixer Verteidigung verteidigt werden. Mit sog. Spionageberichten erfährt man was genau auf diesem Planeten vorhanden ist.

Der Ablauf soll folgendermaßen sein: Man spioniert beliebig viele Planeten aus, fügt die Spionageberichte in das Programm ein und gibt dazu noch seine verfügbare Flotte an. Das Programm soll dann versuchen den optimalen Raidplan zu erstellen.

Folgende Begrenzungen existieren: *Maximal X Angriffe können in einem Plan enthalten sein. Die Zahl ist bekannt und wird vor dem Start angegeben. *Es steht eine begrenzte Flotte (verschiedene Schiffsarten, verschiedene Anzahl / Schiffsart) zur verfügung, ebenfalls bekannt. *Schiffe die in einem Plan bereits eingesetzt werden, können im selben Plan nicht erneut eingesetzt werden. *Planeten bei denen ein Angriff nicht über einem bestimmten Gewinn liegt bzw. in einem Verlust resultiert sollen ignoriert werden. *Die Simulation eines Angriffes auf einen Planeten dauert zwischen 10ms und 500ms, im Schnitt ca. 200ms. *Es stehen maximal 25 Minuten pro Planerstellung zur verfügung.

Mein Ansatz wären hier jetzt zwei genetische Algorithmen:
Einmal einen der versucht die optimale Fleetzusammenstellung pro Planet herauszufinden (aus den zu dem Zeitpunkt noch verfügbaren Schiffen) und dann noch einmal einen der den gesamten Plan optimiert.

Gibt es für so etwas einfachere / schnellere / bessere Alternativen? Es geht mir nicht um den optimalen Raidplan sondern nur etwas annähernd optimales.

Hallo MaXeM,

was genau willst du denn jetzt hören. Grundsätzlich kannst du das wie beschrieben machen. Ich vermute außerdem, dass genetische Algorithmen hier eine passende Wahl sind.

herbivore

Ohne eine konkrete Antwort geben zu können:

Genetische (genauer: Evolutionäre) Algorithmen stehen und fallen mit der Qualität des Crossover-Operators. Ich weiß nicht, ob in deinem Fall ein sinnvoller Operator existiert.

Ansonsten kann auch eine nicht populationsbasierte Metaheuristik (z.B. Simulated Annealing) sinnvoll sein.

Viele Grüße,
Uwe

dadurch das du ja die online-simulation verwenden willst und ein genetischer slgorithmus meist eine etwas größere population benötigt, würde ich dir das simulated annealing nahelegen.

Hallo JAck30lena,

die Population wäre hier die Menge der verschiedenen (zunächst zufällig ausgewählten) Angriffsmöglichkeiten und die ist doch sehr groß.

herbivore

es geht nicht darum, das er eine große population als startvorraussetzung benötigt, es geht darum das es schlecht für ihn ist, wenn er eine große population benötigt.