Evolutionäre Algorithmen: Darstellung, Beispiele, Betriebswirtschaftliche Anwendungsmöglichkeiten

ISBN-13: 9783824402175 / Niemiecki / Miękka / 1994 / 490 str.

Volker Nissen

Opis

Evolutionare Algorithmen sind breit anwendbare Such- und Optimierungsverfahren, die auf abstrakter Ebene den Grundmechanismus von Variation und Selektion der naturlichen Evolution nachahmen."

Spis treści

1 Einleitung.- 1.1 Gegenstand und Ziele der Arbeit.- 1.2 Aufbau der Arbeit.- 2 Kurzer Abriß relevanter Elemente der Evolutionstheorie.- 3 Evolutionäre Algorithmen (EA).- 3.1 Überblick und historischer Rückblick.- 3.2 Hauptformen Evolutionärer Algorithmen.- 3.2.1 Genetische Algorithmen (GA).- 3.2.1.1 GA-Grundkonzept.- 3.2.1.2 Erweiterungen.- 3.2.1.2.1 Überblick.- 3.2.1.2.2 Lösungsrepräsentation und Codierung.- 3.2.1.2.3 Populationskonzept.- 3.2.1.2.4 Selektionsmechanismus und Fitneßfunktion.- 3.2.1.2.5 Suchoperatoren und Einstellen von Strategieparametern.- 3.2.1.2.6 Mehrzieloptimierung.- 3.2.1.2.7 Berücksichtigung von Nebenbedingungen.- 3.2.1.2.8 Leistungsmaße und Konvergenzindikatoren.- 3.2.1.3 Eigenständige GA-Varianten.- 3.2.1.3.1 Einleitung.- 3.2.1.3.2 Messy-GA.- 3.2.1.3.3 Genetische Programmierung.- 3.2.1.3.4 Ein Überblick weiterer GA-Varianten.- 3.2.1.4 Ausgewählte Ergebnisse der GA-Theorie.- 3.2.1.4.1 Überblick.- 3.2.1.4.2 Schema-Theorem und Implikationen.- 3.2.1.4.3 Erweiterungen von Hollands Schema-Begriff.- 3.2.1.4.4 Deception und Royal Road-Funktionen.- 3.2.1.4.5 Zur Bedeutung von Lösungscodierung und Fitneßgebirge für den GA-Erfolg.- 3.2.1.4.6 Optimale Populationsgrößen.- 3.2.1.4.7 Konvergenzeigenschaften.- 3.2.2 Evolutionsstrategien (ES).- 3.2.2.1 Standard-ES.- 3.2.2.2 Vorläufer der Standard-ES: (1+1)-ES und (?+l)-ES.- 3.2.2.3 Erweiterungen der Standard-ES.- 3.2.2.3.1 Überblick.- 3.2.2.3.2 Populationskonzept.- 3.2.2.3.3 Selektionsvarianten.- 3.2.2.3.4 Rekombinationsvarianten.- 3.2.2.3.5 Korrelierte Mutationen.- 3.2.2.3.6 Kombinatorische Optimierung und diskrete Variablen.- 3.2.2.3.7 Mehrzieloptimierung.- 3.2.2.3.8 Berücksichtigung von Nebenbedingungen.- 3.2.2.4 Die ES-Variante von Ablay.- 3.2.2.5 Ausgewählte Ergebnisse der ES-Theorie.- 3.2.3 Evolutionäre Programmierung (EP).- 3.2.3.1 Standard-EP.- 3.2.3.2 Erweiterungen von Standard-EP.- 3.2.3.3 Experimente mit endlichen Automaten.- 3.2.3.4 Ausgewählte Ergebnisse der EP-Theorie.- 3.3 Das Verhältnis von GA, ES und EP zur Evolutionstheorie, sowie Verfahrensvergleich und Unifizierung.- 3.3.1 Zum Verhältnis von EA und Evolutionstheorie.- 3.3.1.1 Populationskonzept.- 3.3.1.2 Fitneß und Selektionsmechanismus.- 3.3.1.3 Mutation und Crossover.- 3.3.1.4 Zusammenfassung und Exkurs zu Artificial Life.- 3.3.2 Gegenüberstellung äußerer Merkmale und Unifizierung von GA, ES und EP.- 4 Anwendungsbeispiele.- 4.1 Überblick.- 4.2 EA für das Quadratische Zuordnungsproblem und die Standortplanung.- 4.2.1 Überblick.- 4.2.2 Problemformulierung, Eigenschaften und Anwendungsbezug des QAP.- 4.2.3 Neue Lösungsverfahren für das QAP.- 4.2.3.1 Verwendete Testprobleme.- 4.2.3.2 Exemplarische Ergebnisse nicht-evolutionärer Lösungsverfahren.- 4.2.3.3 Evolutionäre Ansätze anderer Autoren für das QAP.- 4.2.3.4 Neue Ansätze auf GA-Basis: MPGA und mGA.- 4.2.3.4.1 MPGA - ein Multipopulations-GA.- 4.2.3.4.1.1 Voruntersuchung und Darstellung des Verfahrens.- 4.2.3.4.1.2 Empirische Ergebnisse.- 4.2.3.4.2 mGA — Implementierung eines Messy-GA.- 4.2.3.4.2.1 Darstellung des Verfahrens.- 4.2.3.4.2.2 Empirische Ergebnisse.- 4.2.3.5 Ein Ansatz auf EP-Basis: CEP.- 4.2.3.5.1 Darstellung des Verfahrens.- 4.2.3.5.2 Empirische Ergebnisse.- 4.2.3.6 Ein Ansatz auf ES-Basis: CES.- 4.2.3.6.1 Darstellung des Verfahrens.- 4.2.3.6.2 Empirische Ergebnisse.- 4.2.3.7 Vergleichende Beurteilung der vorgestellten neuen EA für das QAP.- 4.2.3.8 Zusammenfassung.- 4.2.4 Erweiterung — innerbetriebliche Standortplanung.- 4.2.4.1 Grundlagen.- 4.2.4.2 Eingesetzte Verfahren zur Berücksichtigung von Nachbarschaftsrestriktionen.- 4.2.4.3 Empirische Ergebnisse.- 4.3 Evolutionäre Algorithmen für ein stochastisches Lagerhaltungsproblem.- 4.3.1 Überblick.- 4.3.2 Das Modell.- 4.3.3 Gestaltung der Zielfunktion.- 4.3.4 Optimierung der Entscheidungsgrößen des Lagerhaltungsmodells.- 4.3.4.1 Einleitung.- 4.3.4.2 Darstellung der konventionellen Optimierungsverfahren.- 4.3.4.3 Darstellung der implementierten EA-Varianten.- 4.3.4.4 Empirische Ergebnisse.- 5 Betriebswirtschaftliche Anwendungsmöglichkeiten von Evolutionären Algorithmen.- 5.1 Überblick.- 5.2 Stand der Anwendung.- 5.2.1 Datenlage und Abgrenzungen.- 5.2.2 Praktische betriebswirtschaftliche Anwendungen.- 5.2.3 Anwendungsorientierte Forschungsprojekte aus dem betriebswirtschaftlichen Bereich.- 5.2.4 Anwendungsbereichsunabhängige Problemklassen.- 5.3 Stärken und Schwächen von EA als Optimierungsverfahren und Rückschlüsse auf betriebswirtschaftliche Anwendungsmöglichkeiten.- 5.3.1 Überblick.- 5.3.2 Stärken von EA.- 5.3.2.1 Breite Anwendbarkeit.- 5.3.2.2 Flexible Verfahrensgestaltung.- 5.3.2.3 Eignung für hochkomplexe Suchräume.- 5.3.2.4 Gute Parallelisierbarkeit.- 5.3.2.5 Sonstige Stärken.- 5.3.3 Schwächen von EA.- 5.3.3.1 Heuristischer Charakter — fehlende Optima-litätsgarantie.- 5.3.3.2 Hoher Rechenaufwand.- 5.3.3.3 Know-How-Defizite.- 5.3.3.4 Sonstige Schwächen.- 5.3.4 Rückschlüsse auf betriebswirtschaftliche Anwendungsmöglichkeiten von EA.- 5.3.4.1 Allgemeine Überlegungen.- 5.3.4.2 Mögliche zukünftige Anwendungsschwerpunkte.- 5.3.4.2.1 Entwerfen mathematischer Formeln und Modelle.- 5.3.4.2.2 Regelinduktion.- 5.3.4.2.3 Komplexe kombinatorische Problemstellungen der Praxis.- 5.3.4.2.4 Ganzzahlige Optimierung.- 5.4 Hybridsysteme und betriebswirtschaftliche Anwendungsmöglichkeiten.- 5.4.1 Überblick.- 5.4.2 Hybridisierung mit konventionellen Verfahren.- 5.4.2.1 Grundlagen.- 5.4.2.2 Heuristische Initialisierung der EA-Start-population.- 5.4.2.3 Konventionelles Verfahren beeinflußt grundsätzlichen EA-Ablauf.- 5.4.2.4 Expertensystem setzt EA-Strategieparameter.- 5.4.2.5 Sequentielle Kombination von EA und konventionellen Lösungsverfahren.- 5.4.2.6 Konventionelles Verfahren als Operator in EA integriert.- 5.4.2.7 Intelligente Decodierung und Lösungreparatur.- 5.4.2.8 EA optimiert Strategieparameter eines konventionellen Lösungsverfahrens.- 5.4.2.9 Auswahl und Generierung von Eingabedaten für konventionelle Verfahren.- 5.4.3 Neuroevolutionäre Systeme.- 5.4.3.1 Grundlagen.- 5.4.3.2 Anwendungen von NN auf EA.- 5.4.3.3 Auswahl und Generierung von NN-Trainingsdaten mit EA.- 5.4.3.4 Parameteroptimierung bei NN-Lernverfahren.- 5.4.3.5 Generieren von Lernregeln.- 5.4.3.6 Optimieren von Verbindungsgewichten mit EA.- 5.4.3.7 Optimieren von Netzarchitektur (und Netzparametern).- 5.4.3.8 Analyse von NN mit EA.- 5.4.3.9 Zukünftige betriebswirtschaftliche Anwendungsmöglichkeiten neuroevolutionärer Systeme.- 5.4.4 Lernende Classifier Systeme.- 5.4.4.1 Grundlagen.- 5.4.4.2 Entwicklungstendenzen.- 5.4.4.3 Betriebswirtschaftliche Anwendungsmöglichkeiten.- 5.4.4.4 Leistungsvergleiche mit anderen ML-Ansätzen und Fazit.- 5.4.5 Evolutionäre Simulation.- 5.4.5.1 Grundlagen.- 5.4.5.2 Auffinden guter Werte für Entscheidungsvariablen.- 5.4.5.3 Evolution der Modellstruktur.- 5.4.5.4 Metaebenen-EA.- 5.4.5.5 Simulations-Metamodelle.- 5.4.5.6 Emergent Computation.- 5.4.5.7 EA als Modelle evolutionärer ökonomischer Prozesse.- 5.4.6 Fuzzyevolutionäre Systeme.- 5.4.6.1 Grundlagen.- 5.4.6.2 Anwendungen des Konzeptes unscharfer Mengen auf EA.- 5.4.6.3 Fuzzyevolutionäre Controller und betriebswirtschaftliche Implikationen.- 5.4.6.4 Fuzzy Classifier-Systeme und fuzzyevolutionäre Netzwerke.- 5.4.6.5 Fuzzyevolutionäre Datenanalyse.- 5.4.6.6 EA und Fuzzy Petri-Netze.- 6 Zusammenfassung.

O autorze

Prof. Dr. Volker Nissen ist seit 2005 Professor für Wirtschaftsinformatik (Schwerpunkt Dienstleistungsunternehmen) an der Technischen Universität Ilmenau. Zuvor war er viele Jahre in verschiedenen Funktionen der IT-Beratung tätig. Prof. Nissen ist Sprecher des Arbeitskreises IV-Beratung in der Gesellschaft für Informatik e.V. und Vorsitzender der Gesellschaft für Consulting Research e.V.