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.
