> Die bisherigen Optimierer von Arne und Andreas berechnen beide eine
> Kostenfunktion für jedes generierte Layout. Diese Kostenfunktion ist
> frei von irgendwelchen Vorgaben. Bei dem neuen Ansatz müsste man sich
> der Form des QAPs unterwerfen.
Mein Optimierer verwendet eine (leicht erweiterte) QAP Formulierung, und
ich vermute, bei Arne ist es nicht viel anders. Das aufstellen der
Matrizen A und B ist von der eigentlichen Optimierung getrennt.
Die leicht Erweiterung in meinem Fall ist ein Term für gleichmässige
Fingerbelastung (nichtlinear in den Buchstabenhäufigkeiten). Ausserdem
gibt es auf Wunsch noch Trigramme, mit einem Summationsindex mehr. Bei
Arne sieht es ähnlich aus, soweit ich weiss.
> • mittels Matrix C: Häufige Buchstaben auf guten Plätzen
Nur dann, wenn man in C Häufigkeiten und Aufwände verwurstelt. Ich
mache das nicht explizit, sondern habe Terme analog zu A*B, nur dass
dort nur ein Summationsindex auftritt.
So wie im Artikel formuliert würde C zum Beispiel erlauben auszudrücken,
dass Belegungen, die eine Referenz-Belegung ähnlich sind besser sind als
solche, die das nicht sind (Stichwort: Ctrl-XCV). Ich glaube Arne hat
sowas, ich nicht.
> • Shiftkollisionen oder allgemeiner: Modifierkollisionen
> Allgemein über Optimierung auf mehreren Ebenen (mit Modifiern) habe
> ich mir noch keine näheren Gedanken gemacht. Prinzipiell lassen
> sich Shiftkollisionen durchaus berücksichtigen, allerdings
> bräuchten wir keine nxn-Matrix, sondern eine 2nx2n, was das QAP um
> einiges erschweren würde (unnötigerweise aus meiner Sicht).
So schlimm ist es nicht. Der Aufwand vervierfacht sich nur (in einer
naiven Implementierung), man hat ja nach wie vor nur n Tasten.
> • Es lassen sich durch (meta-)heuristische Methoden sehr schnell
> hinreichend gute Lösungen erzielen. Es erleichtert das Arbeiten an den
> Optimierungsparametern ungemein, wenn man sie einstellen und nach
> einigen Sekunden ein Layout präsentiert bekommt, das dem Optimum sehr
> nahe kommt. Der Arbeitszyklus:
> Parameter einstellen >> Gute Lösung finden >> Testen/Beurteilen >>
> Parameter verändern
> würde kürzer werden.
Stimmt, Tempo ist wichtig, und ich behaupte, dass mein Optimierer deinen
"einige Sekunden" nahe kommt.
> Es folgt eine kleine Buchstaben-Legende für die Ausgabe des
> hasqap-optimierers³, gleich gefolgt von dem Optimierungsprozess, bei
> dem immer die aktuell beste Lösung in Form einer Permutation ausgegeben
> wird.
Auf Deutsch komme ich auf folgende Auswertung:
Stephan 271.330 Gesamtaufwand 190.231 Lageaufwand links rechts
1.390 Kollisionen 17.048 Shift-Kollisionen ob 7.9 8.6
äuopü ßflmvx 71.165 Handwechsel 18.134 Shift-Handwechsel mi 36.5 30.2
aietc gsnrhk 1.563 Ein-/Auswärts --.--- IndirKollision un 6.1 10.7
.öy,q dwjzb 15.796 benachbart 21.592 Shift-benachbart sum 50.5 49.5
10.3 11.2 18.0 11.1 --.- --.- 16.1 13.2 10.5 9.7 Sh 3.7 1.7
Nicht schlecht, es wird auch kein Finger über Gebühr belastet. Zum Vergleich:
Aus der Neo-Welt 244.135 Gesamtaufwand 189.847 Lageaufwand links rechts
1.054 Kollisionen 2.155 Shift-Kollisionen ob 6.8 11.6
kuü.ä vgcljf 71.373 Handwechsel 25.977 Shift-Handwechsel mi 34.5 32.5
hieao dtrnsß 1.525 Ein-/Auswärts --.--- IndirKollision un 5.4 9.2
xyö,q bpwmz 10.353 benachbart 22.340 Shift-benachbart sum 46.7 53.3
9.2 11.1 16.2 10.2 --.- --.- 16.5 10.9 15.4 10.5 Sh 3.8 1.6
Mit Englisch sieht es nicht ganz so gut aus, aber immer noch ok.
Andreas
