Lade Inhalt...

Methoden in der Bionik: Lokale Suche und Optimierung

von Dipl.-Ing. Michael Dienst (Autor)

Wissenschaftlicher Aufsatz 2012 6 Seiten

Mathematik - Angewandte Mathematik

Leseprobe

Lokale Suche und Optimierung

Abstract. Der Aufsatz behandelt die Frage der numerischen Optimierung technischer Entwicklungssysteme. Das Grundschema einfachster Suchalgorithmen wird am Beispiel einer Evolutionsstrategie geklärt, Anwendungsgebiete und Entwicklungsbedarfe benannt und der kompakte Code eines lokalen Algorithmus zur Integration in komplexe Systementwicklungsumgebungen angegeben.

Im industriellen Ingenieurbereich, der Fluidmechanik, in der Visualisierungstechnik und dem Design werden zunehmend robuste und universal einsetzbare Algorithmen zur Integration in komplexe Systementwicklungsumgebungen nachgefragt. Im Engineering sind dies heute die Strukturanalyse mit der Methode der Finiten Elemente (FEM) und die computerunterstützte Strömungssimulation (computational fluid dynamics, CFD) [Abt-03][Har-07][Bre-09][Kre-08], im Designbereich Realzeitsimulationen, Visualisierung und Generatives Gestalten [Rea- 07][Boh-09]. Abhängig von speziellen Rand-, Neben und Anfangsbedingungen, existieren Methoden, schlecht strukturierte Probleme in wohllösbare Optimierungsaufgaben zu verwandeln. In der Praxis hat sich hier die so genannte „lokale Suche“ als ein leistungsstarkes Instrument etabliert. Als „lokal“ werden Suchalgorithmen dann bezeichnet, wenn diese eine von einer komplexen Qualitätsfunktion aufgespannte Topologie in einem begrenzten Gebiet um den aktuellen Arbeitspunkt herum untersuchen. Lokale Suchalgorithmen sind robust, benötigen geringen strukturellen Aufwand und arbeiten schnell. Ihr Einsatzgebiet ist das hochdimensionale Qualitätsgelände nicht geschlossen beschreibbarer Funktionen. Der auf Iterationen basierende Kernmechanismus eines lokalen Suchalgorithmus ist die Ähnlichkeitsvariation der Objektvariablen V einer beliebigen Qualitätsfunktion. Die Variation ΔVn der Objektvariablen V ist komplementär zu ihrer Variablenvergangenheit Vn .

Abbildung in dieser Leseprobe nicht enthalten

Die Lokale Suche ist transient. Sie nutzt Eigenschaften einer (fluktuativen) Entwicklung des Systems hinsichtlich seiner Zustandseigenschaften über die Zeit. In fortschreitenden diskreten Intervallen (n) erhalten wir eine über das Qualitätsgelände der gestellten Optimierungsaufgabe verlaufende Spur der Systemzustände, beschrieben durch den Vektor V der Objektvariablen in einer Ahnenfolge (Vn+1, Vn+2, Vn+3,….usw.).

Zu den leistungsfähigsten lokal arbeitenden Optimierungsstrategien gehören heute die Evolutionären Algorithmen: Genetische Algorithmen

(GA) und Evolutionsstrategie (ES). Bei der Evolutionsstrategie wird die Ähnlichkeitsvariation ΔVn durch den mit der Variationsschrittweite δn dotierten Zufallszahlenvektor Z bestimmt:

Abbildung in dieser Leseprobe nicht enthalten

Evolutionäre Algorithmen (hier Evolutionsstrategien) simulieren das biologische Wechselspiel von Variation und Selektion in jeder Generation und wenden es auf mathematisch modellierte Optimierungsaufgaben an. Dabei werden in einem einfachsten Szenario m Kopien eines Startsystems erstellt. Zufällige Modifizierungen führen auf eine Schar von m Variationen ΔVm,n des Elter-Systems (Mutation).

In jeder Generation n werden alle Variationen des aktuellen Elter (in bestimmten Strategien einschließlich dem Elter, siehe [Rec-94]) mittels einer Zielfunktion einer Bewertung unterzogen, die Qualität aller Systeme wird berechnet oder gemessen (Evaluation). MUTANTEN und ELTER, respektive ihre Qualitäten, bilden somit ein gemeinsames Selektionsensemble. Aus der Schar bewerteter Systeme wird ein neuer, aktueller Elter für die folgende Generation erwählt (Selektion). Mit der Variation dieses Elter-Systems setzt sich die Kampagne fort. Auf diese Weise steigt die Qualität des Ensembles von Generation zu Generation, bzw. fällt nicht hinter die des aktuellen Elter zurück. Aus biologistischer Sicht betrachtet, untersuchen Evolutionsstrategien (jedoch nur) den Phänotyp eines Zielsystems und zielen somit auf das „äußere Evolutionsgeschehen“.

Der Variation kommt bei evolutionären Algorithmen eine besondere Bedeutung zu. In unserem Szenario sollen normalverteilt zufällige Variationen den Objektvariablen- Vektor des Nachkommen von dem des ELTER unterscheiden.

Neben den Merkmalen des als ELTER der nächsten Generation bestellten Nachkommen wird ein Strategieparameter vererbt: die Variations-Schrittweite δ. Sie ist in einfachen Evolutionsstrategien ein Skalar δn (globale Schrittweite) oder den Komponenten des Objektvariablen- Vektors Vm, n zugeordnet δ m, n (individuelle Schrittweite) Ein einfachster evolutionärer Algorithmus besteht wenigstens aus den drei formalen Elementen:

Abbildung in dieser Leseprobe nicht enthalten

Mit dem Grad der Nachahmung der biologischen Evolution nimmt die Güte der Algorithmen zu. Effiziente Evolutionsstrategien und Genetische Algorithmen waren und sind Ziel intensiver Forschung und Entwicklung [Kos-03][Her-00][Her-05][Rec-94][Sche-85][Schw-95][Die-10].

Tab.: 1. Code einer Evolutionsstrategie mit globaler Schrittweite (in SciLab).

Abbildung in dieser Leseprobe nicht enthalten

Der Code einer (1,m)-Evolutionsstrategie ist sehr kompakt (10 Zeilen lang; in der Hand eines Experten wahrscheinlich noch eleganter), schnell und in beliebigen Programmiersprachen implementierbar. Tabelle 1 zeigt den Code einer Evolutionsstrategie in der c-basierten Programmiersprache SciLAB.

Bibliographie und weiterführende Literatur

Abbildung in dieser Leseprobe nicht enthalten

[...]

Details

Seiten
6
Jahr
2012
ISBN (eBook)
9783656117872
Dateigröße
369 KB
Sprache
Deutsch
Katalognummer
v188085
Note
Schlagworte
methoden bionik lokale suche optimierung

Autor

  • Dipl.-Ing. Michael Dienst (Autor)

    113 Titel veröffentlicht

Teilen

Zurück

Titel: Methoden in der Bionik: Lokale Suche und Optimierung