Michael Ostermeier wrote:
> Der Evolutionsalgorithmus an sich ist aber meiner Meinung nach noch
> verbesserbar. Insbesondere ist schon auf der NeoCon ’10 von irgendwem
> gesagt worden, dass am Anfang mehr als ein Paar getauscht werden
> sollte, um zu verhindern, dass nur lokale Minima gefunden werden.
Ich habe dafür mal getestet, wie die Evolution läuft, wenn nach einer
bestimmten Anzahl von erfolglosen Mutationen immer zwei getauscht werden.
Das Ergebnis war schlicht, dass mehr Zeit verbraucht wurde, aber die
Evolution wurde nicht besser (der code hängt noch in evolve drin, IIRC, wird
aber nicht mehr genutzt).
Problem: Es gibt viel mehr Doppelvertauschungen als Einzelvertauschungen, so
dass die Mutationen sehr viel weniger leicht einen großen Teil der
Möglichkeiten abdecken können.
Deswegen versuche ich die lokalen Minimal zu vermeiden, indem jedes mal mit
einem neuen zufallslayout angefangen wird.
Der einfachste Weg um sicher zu stellen, dass jede Kombination erreicht
wird, wäre, einfach mit dem schlechtest-möglichen Layout anzufangen (bzw.
mit einem absichtlich schlechten).
Eine andere Möglichkeit: Die besten Layouts als Grundlage nehmen. Dann ~5
zufällige Vertauschungen machen (aus dem lokalen Minimum stoßen) und wieder
optimieren (was deutlich kürzer dauern sollte).
> Meine Idee:
Kurz, wie man sie realisieren kann:
> 1. Man erzeugt zufällige Layouts und wählt die besten 10 aus
./check_neo.py --best-random-layout
(macht aktuell nur 1000 Zufallsvertauschungen und beginnt jedes Mal mit Neo)
Das gibt allerdings nur das jeweils beste Layout. Einfach 100-mal ausführen
und dann die 10 besten nehmen, dann wurden effektiv num_to_try * 100
getestet :)
(auch wenn es nicht notwendigerweise die echten Top 10 wären).
> 2. Zufälliges Buchstabentauschen
>a) nacheinander werden bei jedem Layout drei Buchstabenpaare
> getauscht
>b) nach jedem erfolgreichen Tausch fällt das schlechteste Layout raus
>c) hat es länger keinen erfolgreichen Tausch gegeben, dann weiter
> mit Zweierpaaren, Einzelpaaren oder 3.
http://bitbucket.org/ArneBab/evolve-keyboard-
layout/src/tip/check_neo.py#cl-1462
Aktuell läuft es umgekehrt, aber halt nur für ein einzelnes Layout.
Bei 1000 schlechteren (lokales Minimum) gibt es Doppelvertauschungen).
…ich dachte, den Code hätte ich rausgenommen, aber er springt erst ab >1000
ein, so dass wir ihn nicht mehr gesehen haben :)
(nicht Geschwindigkeitsrelevant: Nur ein einzelnes log() gegenüber der
extrem teuren total_cost() Funktion)
Die Dreier- und Doppelvertauschungen haben übrigens das Problem, dass kleine
Verschlechterungen gemacht werden, wenn eine der Vertauschungen eine große
Verbesserung bringt.
Nehmen wir an, x und e wären auf Neo vertauscht. Dann wäre die Vertauschung
(xe, nb, al) vermutlich eine positive Vertauschung.
Bei einfach zufälliger Wahl der einzelnen zu vertauschenden Tasten, würden
nb und al nicht gemacht werden. Dafür hat die Tastatur jetzt aber wieder die
möglichen Vertauschungen nb und al, die wieder andere, aber kleinere
Verschlechterungen bringen können.
Ich weiß nicht, ob der aktuelle Ansatz (einfach viele zufällige Layouts als
Anfang) oder der Mehrfachvertauschungsansatz effizienter ist. Aber effektiv
sagt der Mehrfachvertauschungsansatz, dass eine bestimmte Vertauschung nur
dann sinnvoll ist, wenn bestimmte andere Tasten in bestimmten für sie
alleine nicht optimalen Positionen sind. Der Einzelvertauschungsansatz
bekommt das gleiche Ergebnis, indem jedes Mal eine neue Zufallstastatur
genommen wird. In einigen dieser Tastaturen ist die Vertauschung sinnvoll
(die anderen Tasten liegen richtig) in anderen nicht.
Die Auswahl der besten davon sollte uns an lokalen Minima vorbeibringen.
> 3. kontrollierte Evolution der besten 10 Layouts
Was haben wir danach?
Die Schwierigkeit ist leider, dass sich immernoch nur sehr schwer ermessen
lässt, wo wir damit eigentlich sind.
Interessant wären Messungen beider Algorithmen: Wie gut werden die
Tastaturen nach welcher Zeit.
PS: Dank frakturfreak werden jetzt im controlled-tail aa und konsorten nicht
mehr getestet.
