Benutzer:Rberlich/Optimierungsumgebungen

aus Wikipedia, der freien Enzyklopädie

Dieser Artikel möchte Computer-implementierte Optimierungsumgebungen an Hand der implementierten Algorithmen sowie zusätzlichen Eigenschaften wie der Fähigkeit zur parallelen und verteilten Ausführung, der Fähigkeit zur Mischung unterschiedlicher Parametertypen, den implementierten Methoden zur Behandlung von Randbedingungen oder der verwendeten Lizenz kategorisieren. Die Nennung erfolgt ohne Wertung in alphabetischer Reihenfolge.

Ein Optimierungsproblem ist über eine Abbildung (oft Ziel- oder Fitnessfunktion, gelegentlich auch Solver genannt) definiert, das einem Raum von Eingabeparametern ein oder mehrere numerische Fitnesskriterien zuordnet: . Das Ziel der Optimierung ist im Falle eines einzelnen Fitnesskriteriums (Einkriterienoptimierung) die Bestimmung des Extremwerts (Maximums oder Minimums) von . Bei mehreren gleichberechtigten Fitnesskriterien spricht man von Mehrkriterienoptimierung. Hier ist das Ziel auf Grund der bei mehreren Bewertungskriterien fehlenden eindeutigen Metrik unter den Lösungen meist die Bestimmung eines ganzen Lösungsraums, also mehrerer gleichberechtigter Lösungen, unter denen erst nach Abschluss der Optimierung eine Auswahl getroffen werden kann. Ein bekannter Vertreter der Mehrkriterenoptimierung ist die Paretooptimierung.

kann entweder einen rein mathematischen Ausdruck darstellen, wird aber besonders bei technischen und wissenschaftlichen Problemstellungen oft auch als Computerprogramm oder -prozedur implementiert sein, dessen Komponenten eine Behandlung mit herkömmlichen mathematischen Verfahren ausschließen. Insbesondere kann die Differenzierbarkeit der Zielfunktion nicht oder nur näherungsweise (Stichwort "Differenzenquotient") vorausgesetzt werden. Ein Beispiel wären etwa Zielfunktionen, die auf dem Durchlauf einer Simulation mit den von einer Optimierungsumgebung bereitgestellten Parametern basiert.

Dieser Artikel versucht, sowohl Algorithmen für die rein mathematische Optimierung zu berücksichtigen als auch die Optimierung auf Basis von Algorithmen, die lediglich die Bewertbarkeit einzelner Parametersätze voraussetzen.

Liste von Optimierungsumgebungen

Name Algorithmen Datentypen Constraintbehandlung Betriebssysteme Programmiersprachen Parallelität Mehrkriterienoptimierung Lizenz Einsatzbereich Solver-Implementierung
Geneva Optimization Library EA, PSO, GD, SA, DOE d, i32, b Parameter-basiert, Inter-Parameter Constraints Linux, FreeBSD C++ Threads, Cluster, Grid/Cloud, GPGPU Pareto (EA) Affero GPL v3, proprietär Automotive, Wissenschaft, besonders rechenaufwändige Bewertungsfunktionen Ableitung von Basisklassen oder externes Executable

Beschreibung verwendeter Kategorien

Name: Eine Kurzbezeichnung der Optimierungsumgebung. Diese ist, soweit möglich, mit der zugehörigen Wikipediaseite verlinkt

Algorithmen: Die durch die Optimierungsumgebung implementierten Optimierungsalgorithmen. Hierbei werden die folgenden Abkürzungen für "Reinformen" (in alphabetischer Reihenfolge) verwendet:

Abkürzung Algorithmenname Anmerkung
CG Conjugate Gradient
DOE Parameter-Scan / Design of Experiment
EA Evolutionärer Algorithmus Sammelbegriff für Evolutionsstrategien und Genetische Algorithmen
ES Evolutionsstrategie
GA Genetic Algorithms
GD Gradient Descent Einfaches Gradientenverfahren (vgl. Conjugate Gradient)
PSO Particle Swarm Optimization
SA Simulated Annlealing
SMPL Simplex

Implementationsdetails werden hierbei aus Gründen der Lesbarkeit so weit wie möglich ignoriert. Unterartikel zu den einzelnen Optimierungsumgebungen können auf diese näher eingehen.

Datentyp(en): Die Typen unterstützter Datentypen. Hierbei finden die folgenden Abkürzungen Verwendung:

Abkürzung Datentype Anmerkung
d double precision IEEE floating point
f single precision IEEE floating point
i32 32-bit Integer
b boolean/bits

Constraintsbehandlung: Verwendete Methoden zum Umgang mit individuellen oder kombinierten Randbedingungen

Betriebssysteme: Die von der Optimierungsumgebung unterstützten Betriebssysteme. Insofern eine Einschränkung auf eine bestimmte Hardwareplattform bekannt ist, wird dies in Klammern angegeben (Beispiel: "Linux (x86-64)" ).

Programmiersprachen: Die für die Implementierung verwendete Programmiersprache, also z.B. C, C++ oder Python. Insofern für die Implementierung mehrere Sprachen verwendet wurden, werden alle bekannten Sprachen angegeben.

Parallelität: Beschreibt, ob und welche Form paralleler und/oder verteilter Ausführung eine Optimierungsumgebung unterstützt. Der Artikel macht keine Aussage über die Art der Implementierung von Parallelität. In vielen Fällen wird diese auf der Ebene der Bewertung von Kandidatenlösungen erfolgen. Auch wird keine Aussage über die verwendeten Toolkits zur Implementierung von Parallelität (etwa Boost.Thread, MPI etc.) getroffen.

Mehrkriterienoptimierung Unterstützte Formen der Mehrkriterienoptimierung oder "keine"

Lizenz: Hier wird die für die Gesamtumgebung verwendete Lizenz angegeben, insofern diese durch einen Namen identifizierbar und im World Wide Web verlinkbar ist. Rein kommerzielle Optimierungsumgebungen werden mit dem Attribut "proprietär" versehen.

Einsatzbereich: Eine stichwortartige Beschreibung des Haupt-Einsatzfeldes, soweit bekannt (etwa: "Automotive" oder "Bio-Informatik")

Solver-Implementierung: Stichwortartige Beschreibung des Vorgehens zur Definition eines Optimierungsproblems sowie ggf. besondere Anforderungen an die Fitnessfunktion (z.B. "differenzierbarkeit")

Besonderheiten einzelner Optimierungsumgebungen können in eigenen Wikipediaartikeln beschrieben werden.