Warum 'Barbarische Tools'? Diese Programme sind Antworten von mir auf ein Werkzeug von R. Nowagk namens 'Conan'. Conan steht für Constrained Randomization und war ein AWK-Script, welches eine zufällige Ziehung von Stimuli unter Berücksichtigung von Randbedingungen erlaubte und in der Psychologie eingesetzt wurde.
Was nicht nur mich, sondern auch andere Benutzer daran störte, war, daß das Werkzeug 'Conan' nicht deterministisch arbeitete. 'Conan' hat folgenden Algorithmus als Grundprinzip:
Der Auslöser ein eigenes Toolset zu schreiben gaben drei Gründe. Erstens benötigt 'Conan' schon eine Datei, die alle möglichen Kombinationen enthält, zweitens ist 'Conan' langsam, sehr langsam -- und drittens forderte mich Tobias Hammerschmidt mit seinem 'Conan'-Ersatz 'Rando' heraus. Er verwendet genetische Algorithmen für die Suche nach den Randbedingungen.
Dieses Programm ist in Ocaml geschrieben und bildet alle Wörter der Länge n aus den gegebenen Symbolen. Das Programm tut dies auf äußerst effektive Art und Weise.
Es bildet rekursiv Teilwörter und setzt diese so zusammen, daß die Teilwörter nicht mehr verändert werden. Aus den Symbolen A, B und C werden zum Beispiel zuerst die Teilwortlisten
L1=[A] [B] [C]
undL2=[A] [B] [C]
gebaut. Eine davon wird mit der jeweils letzten kombiniert:
PR=L1 L1=L1xL2 + L1xL1 = [A A] [A B] [A C] [B A] .. [C C] L2=PR=[A] [B] [C]
gebildet. Diese werden mit der jeweils letzten Teilwortliste kombiniert:
PR=L1 L1=L1xL2 + L1xL1 = [A AA] [A AB] [A AC] .. [C CC] [AA AA] [AA AB] .. [CC CC] L2=PR=[A A] [A B] [A C] [B A] .. [C C]
Der nächste Schritt sähe so aus:
PR=L1 L1=L1xL2 + L1xL1 = [AA AAA] [AA AAB] .. [CC CCC] [AAA AAA] [AAA AAB] .. [CCC CCC]
Da die Teilwortfolgen erhalten bleiben ist diese Art des Permutationsaufbaus gut geeignet beim Aufbau schon gegen Randbedingungen testen zu können.
Auch 'red sonja' ist in Ocaml entwickelt wurden. Es benutzt den gleichen Grundalgorithmus, wie 'varna', testet aber beim Aufbau der Teilkombinationen diese gegen die Randbedingungen. Wenn die Randbedingungen stark sind, wird der exponentielle Suchraum zur Laufzeit stark eingeschränkt.
Der Vorteil dieses Lösungsansatzes ist, daß er deterministisch ist, alle Lösungen liefert und dem Benutzer auch mitteilt, wenn es keine Lösung geben sollte. Gerade der letzte Punkt wird von 'Conan', wie auch von 'rando' nicht berücksichtigt.
'redsonja' wurde hier erstmal als Prototyp in Perl vorgestellt, da sich so schneller die Idee für erste Tests umsetzen lässt.
Da ja Sequenzen zufällig gezogen werden sollen, die bestimmten Bedingungen genügen, wäre es hilfreich, alle möglichen Sequenzkombinationen zu bilden, die den Randbedingungen genügen und dann zufäälig aus diesem Set eine Variante zu ziehen. Erstens kann man dann Aussagen treffen, welche Möglichkeiten überhaupt existieren und andererseits ist die Modellierung der Bedingungen nicht mehr ein technisches Problem des Präsentationsprogrammes, sondern kann effizient vor Beginn des Experimentes geprüft werden.
In der Nutzung der Programme gibt es natürliche Grenzen. So ergibt sich die Zahl der Möglichkeiten aus N_set = Alphabet ^ Wortlänge. Da der zur Verfügung stehende Speicher in der Regel auf Größenordnungen von 10^9 Bytes begrenzt ist, kommt es gerade bei der Nutzung von Varna schnell zu Engpäßen. Bei Redsonja hängt die natürliche Grenze sehr stark von den angegebenen Randbedingungen ab. Da die Wörter rekursiv aus Teilwortlisten zusammengesetzt werden, ist es wichtig, diese Randbedingungen so zu wählen, daß nicht zuviel pro Rekursionsschritt weggeschnitten wird, aber auch die expoentielle Explosion nicht zuschlägt.
Ich bin an Rückmeldungen sehr interessiert. Bitte meldet Euch, wenn ihr Verbesserungsvorschläge, aber auch nur Fehlermeldungen habt und sendet eine Mail an mich
Mein Dank geht an alle, die mir geholfen haben dieses Tool zu entwickeln, insbesondere von der Ocaml Beginners-Mailingliste: