Genetische Algorithmen mit SQL

Bot Square-300x183 in Genetische Algorithmen mit SQL

Fleissiger Data Mining Bot!

Data Mining nur mit SQL als Sprache wird häufig nicht in Betracht gezogen und doch eignet es sich zur Lösung mancher Probleme, wie folgender Artikel A Genetic Algorithm Sample in T-SQL von William Talada zeigt.
Er löst das folgende Problem auf eindrucksvolle Weise.

Auf einem 10×10 Feld umgeben von einer Mauer liegen in der Hälfte der Felder leere Dosen. Ein Roboter startet in diesem Feld und kann 200 Aktionen ausführen, um all diese Dosen einzusammeln und das Feld zu reinigen. Er kann in alle Himmelsrichtungen gehen oder eine Dose aufheben. Seine Sichtweite ist auf fünf Felder beschränkt, das auf dem er steht und die vier angrenzenden Felder.


Ein Feld kann drei Zustände haben, leer, Mauer oder mit einer Dose belegt. Da er fünf Felder sehen kann, ergibt das eine Menge von 3x3x3x3x3 = 243 Möglichkeiten. Auf jedem Feld hat der Roboter also 243 Möglichkeiten für ein Ergebnis. Der Roboter kann auf jedem Feld eine von sechs Aktionen ausführen, sich in eine von vier Richtungen bewegen, etwas aufheben oder zufällig bewegen. Das ergibt insgesamt 243^6 = 1,23×10^189 Möglichkeiten. Diese kann man nicht einfach durchrechnen.
Der Data Mining Algorithmus simuliert eine Million Schritte und kommt zu einem fast idealen Ergebnis. Das Ergebnis ergibt sich aus folgenden Punktzahlen. Für eine aufgehobene Dose gibt es +10 Punkte, beim Versuch in eine Wand zu laufen -5 und beim Versuch eine Dose aufzuheben wo keine ist -1. Also kann der Roboter in einem perfekten Lauf 500 Punkte erzielen.

Das Script für den Algorithmus ist dem Artikel angehängt und erläutert die Abläufe. Die Laufzeit ist mit 20 Minuten für eine Million geprüfte Möglichkeiten auch relativ schnell.

Die Idee zu diesem Artikel stammt aus dem Buch „Complexity: A Guided Tour“ von Melanie Mitchell. Das Buch gibt einen Überblick über den Stand der Forschung und der Möglichkeiten auf dem Gebiet der komplexen Systeme und wie diese praktisch eingesetzt werden können, z.B. durch die hier im Beispiel genannten, genetischen Algorithmen.

2 Kommentare zu Genetische Algorithmen mit SQL

Antwort verfassen

 

 

 

Diese HTML Tags sind erlaubt

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>