Re: [Neo] Evolution verbessern (was: Tipptests)

2010-09-08 Diskussionsfäden Arne Babenhauserheide
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 num of random layouts to try
(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. 



[Neo] Evolution verbessern (was: Tipptests)

2010-09-07 Diskussionsfäden Michael Ostermeier
Hallo Neo 3-Linge,

 Dem effchen (ein ehemaliger Neoling der leider nur auf #neo aktiv ist)
 ist die Idee gekommen, bestimmte Tasten festzulegen und von diesen aus
 dann optimale Layouts zu berechnen. So weit nichts neues, nur nimmt
 effchen subjektiv die Buchstaben die bei vielen optimalen Layouts
 gleich positioniert sind und legt sie fest.

Mit jeder neuen Config müssen dann aber zum Festlegen dieser Tasten
jeweils gute Layouts vorliegen. Und man schließt einige Layouts aus,
die vielleicht besser sein könnten. Eine vollständige Suche ist bei 32!
also ca. 2,6 * 10³⁵ Möglichkeiten aber sowieso nicht möglich.

 Dachte ich schreib diesen Ansatz mal an die Mailinglist, vielleicht hat
 ja noch jemand Ideen dazu ;)

Vielleicht könnte man die Tastatur in zwei Bereiche einteilen und die
Buchstaben in drei Kategorien. Kategorie A darf nur in Bereich 1, weil
häufig betätigt. Kategorie B darf in beide Bereiche und Kategorie C
will ich auf keinen Fall auf guten Positionen.

Das Entfernen von gleichwertigen Tauschpaaren (a mit b oder b mit a zu
tauschen ist dasselbe) bringt nur bei der kontrollierten Evolution am
Ende die doppelte Geschwindigkeit. Bei der Zufälligen ist das egal,
solange nicht a mit a getauscht wird.

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.

Meine Idee:
1. Man erzeugt zufällige Layouts und wählt die besten 10 aus
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.
3. kontrollierte Evolution der besten 10 Layouts

 22:30  effchen_NTxcv2 eine variante davon hat 19.22237 punkte erhalten
 …
 23:11  Mike1 effchen_NTxcv2: wie sieht dein bisher bestes Layout aus?
 23:11  effchen_NTxcv2 xuc.ö vwsh,q
 23:11  effchen_NTxcv2 miaeo dtrnlk
 23:11  effchen_NTxcv2 jüzäy bgßfp
 
 Er weißt allerdings darauf hin das die Punkte eventuell nicht mit
 Arnes Top3 verleichbar sind

In der Tat, es sind 20.013, wenn man das richtig berechnet.

Gruß

Miche