17
Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen optimiert mit Ameisen Seminar Seminar Heuristische Verfahren Heuristische Verfahren Das Das Tastatur-Anordnungs-Problem Tastatur-Anordnungs-Problem Susin Savas 03.02.2004

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Embed Size (px)

Citation preview

Page 1: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1

optimiert mit Ameisenoptimiert mit Ameisenoptimiert mit Ameisenoptimiert mit Ameisen

SeminarSeminarHeuristische VerfahrenHeuristische Verfahren

Das Das Tastatur-Anordnungs-Tastatur-Anordnungs-

ProblemProblem

SeminarSeminarHeuristische VerfahrenHeuristische Verfahren

Das Das Tastatur-Anordnungs-Tastatur-Anordnungs-

ProblemProblem

Susin Savas

03.02.2004

Susin
Ameisenbild hierTastaturbild heir
Page 2: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 2

Motivation

• Layout einer Tastatur scheinbar ungeordnet? Alphabetisch Treffer-Rate Ergonomisch

• Ursprünglich für Schreibmaschinen entworfen• QWERTY Layout, Sholes Brüder, 1873• Keine Verklemmungen der Tasten• Entworfen für Remington II

Jahrzehnte lang StandardVerbesserungen in Ergonomie undTrefferrate (Marsan, Dvorak) nicht durchgesetzt

Page 3: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 3

Motivation

Ergonomische Nachforschung für das Anordnungs-Problem erfolglos

Grund: unrealistische Modelle, keine Optimierungs-Methode

Beispiele: Tipp-Geschwindigkeit, schnelles Erlernen des Tipp Systems von Norman und

Fischer, 1982 komplexere ergonomische Kriterien von Pollatschek 1975, Burkard und

Offermann 1977

Lösung: 6 theoretisch abgeleitete heuristische Regeln, experimentell geprüft

Susin
Fehler hier: - es geht darum, daß zu viele Möglichkeiten existieren, die nicht effizient überprüft werden können
Page 4: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 4

Das Tastatur-Anordnungs-Problem

Lösungs-Ansatz:

Ein abstraktes Tastatur Modell definieren

Eine Bewertungsfunktion (Optimierungsfunktion) definieren, basierend auf ergonomischen Regeln

Susin
Clipart Frage
Page 5: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 5

Repräsentation einer Tastatur

Aufteilung der Tastatur in: Rechte Hand, linke Hand Spalten (0-7 rechte Hand und 0-8 linke Hand) Zeilen (0-5)

Zur exakten Identifikation jeder einzelnen Taste

Page 6: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 6

Kriterien für Ergonomie

•ZieleErmüdungsfreies TippenMaximieren der Tipp-GeschwindigkeitVermindern von Tipp-FehlernEinfaches Erlernen des Layouts

•Optimierungs-Funktionlineare Kombination aus 6 Teilfunktionenliefern quantitative Ergebnisse ergonomischer Kriterien

Susin
auflockern
Page 7: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 7

Kriterien für Ergonomie

1. Erreichbarkeit & Belastung Lastverteilung möglichst auf

Alle Finger

Beide Hände

Unterschiedliche Erreichbarkeit von Tasten

2. Anzahl der Tasten-Drücke Möglichst minimal

3. Hand-Wechsel Aufeinanderfolgende Tasten-Drücke

möglichst mit wechselnder Hand

21 )(

1

optm

mm i

mi

iffv

d

i

i

ddfv

3

3

ckeTastenddrüZeichenv ##

2

Page 8: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 8

Kriterien für Ergonomie

4. Fortlaufender Gebrauch des gleichen Fingers Möglichst abwechselnde Finger

5. Vermeiden großer Sprünge Aufeinanderfolgende Tasten

möglichst eng zusammen

6. Treffer-Richtung Aufeinanderfolgende Tasten

bei gleicher Hand möglichstvon Außen nach Innen

)(4

4 id

d ddisfvd

i

i

d

i

i

ddi fdkv

5

)(5

d

i

i

ddfv

6

6

Page 9: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 9

Grundidee: Basiert auf natürlichem Verhalten der Ameisen Ameisen finden kürzesten (optimalen) Weg Nest ↔ Nahrungsquelle Verwendung von Pheromon-Spuren

Beschreibung:1. Initiale Phase

Parameter auf Anfangswerte setzen

2. Iterative Phasesolange wiederholen bis vordefinierte Bedingung erreicht

Zeichen-nach-Taste Zuordnung: Berechnung der wahrscheinlich günstigsten Taste für das Zeichen

Ameisen-Algorithmus

Page 10: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 10

Ameisen-Algorithmus

Initiale Phase:

Ameisen-Sammlung von N Agenten Text-Quelle definieren Jeder Ameise leere Zeichen Kette der fixen Länge l zuweisen Jeder Ameise eine leere Tastatur zuweisen Eine Pheromon-Matrix erstellen,

u.U. ihre Elemente auf Werte, die von Lösung einer hoch qualitativen Tastatur-Anordnung stammen, initialisieren

Page 11: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 11

Ameisen-Algorithmus

Iterative Phase: Die zu Ameisen zugeordneten Tastaturen werden geleert Den Ameisen werden Zeichen-Ketten aus dem Text zugeordnet

Jede Ameise liest ihre Zeichen-Kette Produziert Menge kombinierte Zeichen (CCS) CCS werden der Tastatur zugeordnet bis Ende der Zeichen Kette Restliche CCS werden zufällig der restlichen Tasten zugeordnet

Jede Ameise bewertet ihre Lösung Mit dem Koeffizient ρall Pheromon Matrix verdampfen ד ← ρall ד

Auswahl der besten Lösungen mit ∆ד ·q(k) verstärken Pheromon Matrix auf das Intervall [דmin ,דmax] beschränken

Page 12: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 12

Ameisen-Algorithmus

Zuordnung der Zeichen-nach-Taste:

Für alle freie Tasten j Berechnung einer Wahrscheinlichkeit gemäß:

CCS an der gewählten Taste platzieren Die Zuordnung verdampfen lassen

][][

][][

ikikk

ijijijp

ijij

Page 13: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 13

Ergebnisse

Beste Tastatur-Anordnung: Französische Tastatur AZERTY als Referenz (Wert 1.0) 2000 Iterationen in 14h an einem 400 MHz PC Textquelle „Le Monde“ Endergebnis 0.487

Gute Tastaturen haben gleiche Haupteigenschaften: Alle Vokale mit einer Hand Seltene Konsonanten auf der gleichen Seite wie Vokale Position von Vokalen und häufig benutzten Konsonanten zueinander gleich

Page 14: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 14

Ergebnisse

Für Deutsche und Englische Tastaturen: Textquelle „Spiegel“ und „USA Today“ Referenz-Tastaturen QWERTZ bzw. QWERTY (1.0) Werte der Optimierungsfunktionen 0.592, 0.593 Zum Vergleich: Dvorak 0.61

Page 15: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 15

Fazit

Die Arbeiten zeigen:

Ameisen Algorithmus effektiv und liefert effizient sehr gute Lösungen

Dvorak- und Marsan-Tastaturen sind übertroffen Theoretisches Tastatur-Modell wertvoll für (andere)

Simulationen Spezielle Rechts- oder Linkshänder-Tastaturen Mehrsprachige Tastaturen Besondere Tastaturen, z.B. Industrie-Einsatz

Praktische Überprüfung der Ergebnisse bisher ausgeblieben

Page 16: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 16

Literatur

Jan Eggers et al., „Optimization of the keyboard arrangement problem using an Ant Colony algorithm“, European Journal of Operational Research 148 (2003), Seiten 672-686

Page 17: Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 1 optimiert mit Ameisen Seminar Heuristische Verfahren Das Tastatur-Anordnungs-Problem

Seminar Heuristische Verfahren – Das Tastatur-Anordnungs-Problem mit Ameisen 17

Fragen

?