Mathematische Optimierung

Mathematische Optimierung Illustration
© Fraunhofer IIS

Um KI-Systeme zur Entscheidungsunterstützung und ultimativ für das automatisierte Treffen von Entscheidung einzusetzen, braucht es mathematische Optimierungsverfahren. Diese erlauben es, basierend auf einem regelbasierten Ansatz zur Beschreibung des betrachteten Systems, optimale Entscheidungen abzuleiten, z. B. bei Produktionsprozessen, im öffentlichen Verkehr oder bei der Regelung von Energiesystemen. Die zu Grunde liegenden mathematischen Modelle werden mit spezifischen Daten für die gewählte Aufgabenstellung angereichert und machen darauf basierend Vorschläge für den umzusetzenden Plan oder geben direkt Steuerungsimpulse an das zu regelnde System. Eine wichtige Aufgabe der Kompetenzsäule »Mathematische Optimierung« im ADA Lovelace Center ist die Weiterentwicklung der Modellierungs- und Lösungsmechanismen, die für diese Fragestellungen benötig werden.

Die Weiterentwicklung der mathematischen Methoden ermöglicht effiziente Optimierungsverfahren

In den letzten 50 Jahren haben mathematische Optimierungsmodelle und –algorithmen ihre universelle Einsetzbarkeit in vielen Bereichen der Entscheidungs- und Planungsunterstützung bewiesen. Gerade in den letzten beiden Jahrzehnten hat die mathematische Forschung zur Entwicklung moderner Optimierungsalgorithmen beigetragen, mit denen sich heutzutage Problemgrößen behandeln lassen, die vor 10 Jahren noch undenkbar schienen. So lassen sich lineare Programme mit Milliarden von Variablen und Nebenbedingungen effizient lösen, bei ganzzahligen Programmen ist man immerhin bereits im Millionenbereich. Einen Überblick über die zurückliegenden Effizienzsteigerungen in der Löserentwicklung gibt die folgende Grafik am Beispiel zweier führender kommerzieller Löser für diese Sorte von Problemen.

Mathematische Optimierung
© Bob Bixby
Effizienzsteigerungen in der Löserentwicklung.

Wie sich entnehmen lässt, hat allein die Entwicklung besserer mathematischer Verfahren einen Geschwindigkeitsschub von Faktor 4,7 Millionen gebracht. Im Vergleich dazu liegt der Speed-Up-Faktor durch bessere Hardware gerade bei 1600. Insgesamt lassen sich damit heute Optimierungsprobleme innerhalb von 1 Sekunde lösen, die vor 25 Jahren noch unlösbar schienen.

Von der Planung zur Echtzeitoptimierung

Die Partner im ADA Lovelace Center entwickeln bereits seit vielen Jahren effiziente mathematische Verfahren für Planungsprobleme aller Art. Dies umfasst z. B. die Felder Verkehr und Logistik, Energieerzeugung und Übertragung, Supply-Chain-Management, Gebäudeinfrastrukturen, Automobile, Finanzen sowie Anwendungen aus dem Ingenieurswesen. Gleichzeitig werden optimierungstheoretische Probleme untersucht, deren Ergebnisse zum Beispiel in die Beschleunigung allgemeiner Lösercodes eingehen.

Mit der Integration von Verfahren des maschinellen Lernens mit Optimierungsverfahren wurde in jüngster Zeit ein ganz neues Feld aufgetan, was den Weg von Offline-Optimierungsproblemen (mit bekannten, statischen Parametern) hin zu Online-Optimierungsproblemen in Echtzeitanwendungen (unter dynamischen, zeitlich veränderlichen Parametern) betrifft. Für die oftmals hochdynamischen Randbedingungen heutiger Anwendungen, z. B. der Planung von Logistikketten, wird die Verfügbarkeit solcher Verfahren von besonderer Wichtigkeit sein. So haben wir beispielweise gezeigt, dass es möglich ist, Prioritäten und Kostenfunktionen in Planungsproblemen aus beobachteten Entscheidungen der Vergangenheit abzuleiten. Die Fähigkeit, aus vergangenen Entscheidungen explizite Planungsregeln herzuleiten, sorgt daher für eine höhere Automatisierbarkeit und Objektivierbarkeit der zu treffenden Planungsentscheidungen. Die Weiterentwicklung solcher Ansätze im Rahmen lernender Verfahren nimmt im ADA Lovelace Center einen besonderen Stellenwert ein. Es wird durch unsere Arbeit erstmals möglich, aus den bislang nur in der Theorie gegebenen Gütegarantien dieser Verfahren praktisch nutzbare Algorithmen zu machen, welche für den Anwender einen entscheidenden Wettbewerbsvorteil ausmachen.
 

Mitlernende mathematische Entscheidungsmodelle durch die Kombination von Datenanalyse und Optimierung

Datenanalyse und Optimierung waren bislang in der Entwicklung von Systemen der Entscheidungsunterstützung zwei getrennte, aufeinanderfolgende Arbeitsschritte. Dieser Ansatz stößt aber gleich aus mehreren Gründen zunehmend an seine Grenzen: Im Zeitalter zunehmend größer werdender Datenmengen ist allein die Auswahl der für ein Optimierungsproblem relevanten Parameter eine große Herausforderung. Auch ist unklar, welche Merkmale eines Systems für das Treffen guter Planungsentscheidung relevant sind, oder welche Effekte Einfluss auf die Performanz des gewählten Plans haben. Hier gewinnt die Integration der Ansätze aus Datenanalyse und Optimierung an Wichtigkeit. Sehr vielversprechend erscheint für die Zukunft der Weg, mit generischen Basismodellen zur Beschreibung einer Anwendung zu starten und sowohl die Bewertungsfunktion als auch die speziellen Randbedingungen aus den verfügbaren Daten zu lernen. Diese Form der automatischen Modellbildung wird den heutzutage ständig wechselnden Planungsbedingungen deutlich gerechter, denn hier hat man es oft mit einem konstanten Zustrom neuer Daten zu tun, die sofort in die nächste Regelungsaktion für das System einfließen müssen, um es im Optimalzustand zu halten.

Im ADA Lovelace Center werden insbesondere Techniken entwickelt, die in der Lage sind, sich auf die Dynamik eines gegebenen Systems einzustellen und für dieses optimale Entscheidungen zu treffen. Die so »gelernten« Entscheidungen werden dadurch im Laufe der Zeit, und mit mehr Trainingsdaten, immer besser die realen, zeitlich variablen Rahmenbedingungen reflektieren. Die Nutzbarmachung dieser Technik zur Herleitung von Optimierungsmodellen ebnet den Weg hin zu mitlernenden mathematischen Entscheidungsmodellen, welche einen großen Fortschritt im Bereich der automatischen Planung und Steuerung darstellen. Bisher für diese Fragestellung verfügbare Verfahren, wie die mehrstufige stochastische Optimierung, scheitern hier oftmals wegen ihres exorbitanten Rechenaufwandes. Online-Learning bietet eine intrinsisch leichtgewichtige Alternative, denn zu seiner Philosophie gehört es, jeden Datenpunkt nur einmal zu betrachten, was zu einer bedeutenden Entkopplung entlang der zeitlichen Achse und somit zu deutlich geringerer Rechenkomplexität führt. Auch wird so sichergestellt, dass nicht mehr aktuelles Wissen vergessen werden kann, denn weiter zurückliegende Beobachtungen erhalten ein deutlich kleineres Gewicht als kürzlich aufgenommene Daten.

Lernende Optimierungsverfahren

Lernende Optimierungsverfahren sind auch ein wesentlicher Beitrag zum besseren Verständnis eines gegebenen Systems. In vielen Bereichen der praktischen Planung eines Unternehmens beruhen die getroffenen Entscheidungen auf impliziten, nicht formalisierten Regeln (mitunter »Bauchentscheidungen«). Diese sind nicht an sich schlecht, sind aber oft schwer nachvollziehbar und damit schwer automatisierbar. Auch geht diese Form des Expertenwissens oft verloren, wenn die zuständigen Mitarbeiter die Firma wechseln oder in den Ruhestand gehen. Lernende Optimierungsmodelle versetze eine Firma in die Lage, das bei ihr implizit vorhandene Planungswissen in eine mathematische Form zu gießen, die es erlaubt, dieses Wissen verstehbar und für die automatisierte Entscheidungsfindung nutzbar zu machen. Auf einem Feld, das in der Lage ist, die Wettbewerbsfähigkeit der deutschen Industrie ganz entscheidend zu steigern, gehört das ADA Lovelace Center zu den Pionieren dieses Forschungszweiges und liefert maßgebliche Impulse.

Eine weitere Herausforderung moderner Optimierungsverfahren liegt in der Reduktion der Modellkomplexität. Diese ist von immenser Wichtigkeit insbesondere angesichts der immer weiter wachsenden Datenmengen, die in die Entscheidungsfindung einbezogen werden müssen. Für das Dilemma, dass exakte Verfahren der ganzzahligen Optimierung in der Regel eine mit der Eingabegröße exponentiell wachsende Laufzeit aufweisen, versprechen moderne mathematische Methoden Abhilfe. Das Trennen relevanter von irrelevanten Parametern durch die Integration von Datenanalyseverfahren und Optimierungsalgorithmen erlaubt es auch bei sehr großen Datenmengen, Signal und Rauschen voneinander zu unterscheiden. Durch diese repräsentative Auswahl der Effekte in der Zielsetzung und den Nebenbedingungen des gewählten Optimierungsmodells kann so die Rechenzeit deutlich gesenkt werden. Ein Beispiel dafür ist die jüngste Entwicklung von Lernalgorithmen zur Auswahl repräsentativer Szenarien in der Optimierung unter Datenunsicherheiten. Letztere stellt eine Technik dar, um Entscheidungen zu treffen, die auch unter unsicheren (z. B. auf Messungen oder Prognosen basierenden) Eingabedaten qualitativ hochwertig und umsetzbar bleiben. Solche algorithmischen Methoden, die die Auswahl repräsentativer Szenarien unter einer großen Vielzahl denkbarer Szenarien ermöglichen, sind ein wichtiger Beitrag für die Anwendbarkeit dieser Verfahren in der Praxis. Auch hier setzt das ADA Lovelace Center mit seiner Forschung international sichtbare Akzente.

Anwendung der Methoden und Kompetenzen in konkreten Applikationen

Das richtige Mischverhältnis finden mit Mathematischer Optimierung

Mathematische Optimierungsmethoden sind für die Beschreibung und effiziente Planung komplexer Systeme unverzichtbar. Diese treten u.a. dort auf, wo bereits die schiere Anzahl der darin interagierenden Komponenten für eine Explosion in der Kombinatorik der zulässigen Lösungen sorgt. Gerade im Rahmen logistischer Entscheidungsprozesse spielt die Optimierung komplexer Systeme eine wesentliche Rolle. Man denke hierbei zum Beispiel an die Produktion in der Lebensmittelindustrie. Dort sind die Rohstoffe in gewissen, festgelegten Verhältnissen zu mischen, um die fertigen Produkte herzustellen. Die Anforderungen an die Inhaltstoffe sowie die gesetzlichen Vorgaben sind mittlerweile so komplex geworden, dass allein die Aufstellung einer zulässigen Zuordnung der Rohstoffchargen zu den Mischaufträgen bereits ein sehr schweres Problem darstellt; gar nicht zu reden vom Finden möglichst kostensparender Pläne. In der Applikation »selbstoptimierende adaptive logistische Netzwerke« entwickeln wir mathematische Modelle und Algorithmen zur Lösung solcher Problemstellungen.

Fahrplanoptimierung zur Energieeinsparung im Schienenverkehr

Im deutschen Schienennetz sind jeden Tag etwa 30.000 Züge unterwegs, die bei der Erstellung von Fahrplänen berücksichtigt werden müssen. In den letzten Jahren hat zusätzlich zu den üblichen Anforderungen an die Fahrplangestaltung, wie Pünktlichkeit und Betriebssicherheit, der Aspekt des Energieverbrauchs immer stärker an Bedeutung gewonnen. Will man im Rahmen der Fahrplanoptimierung auch den Energieverbrauch der Züge optimieren, inkl. ihrer Bewegungsdynamik, so entsteht ein Optimierungsproblem mit physikalischen Nebenbedingungen in Verbindung mit Schaltvorgängen. Die Mischung aus kontinuierlichem und diskretem Problemanteil führt dazu, dass man zur Lösung auf Verfahren der jeweils anderen Disziplin zurückgreifen kann. So sind oftmals Differenzialgleichungen zu linearisieren bevor diskrete Optimierungstechniken wieder zum Einsatz kommen können. Dies kann beispielsweise auf Basis von sog. stückweisen Linearisierungen erfolgen. Diese Technik erlaubt es, nichtlineare Funktionen in einem Optimierungsmodell durch Setzen von Stützstellen linear anzunähern. Solche und weitere Techniken werden im ADA Lovelace Center in der Applikation »Fahrerassistenzsysteme im Schienenverkehr« entwickelt und eingesetzt. In einem gemeinsamen Projekt mit der Verkehrs-Aktiengesellschaft VAG werden diese Techniken verwendet, um die Energieeffizienz des Nürnberger U-Bahn-Verkehrs zu erhöhen.

Optimale Netzauslegung in Gleichstromnetzen

Leistungselektronische Bausteine bilden den Kern unzähliger Anwendungen und Anlagen in Industrie, Energietechnik, Haustechnik und Mobilität. Verbaute Leistungswandler messen kontinuierlich Kenngrößen wie Strom, Spannung, und deren Änderung über die Zeit und ermitteln darüber indirekt den Zustand des verbundenen Gesamtsystems (beispielsweise des Energienetzes, einer Fertigungsanlage, eines Speichers oder Elektromotors). In der Applikation »Intelligente Leistungselektronik« entwickeln wir mathematische Modelle, um mit Hilfe dieser Daten die Stabilität von Gleichstromnetzen zu optimieren. Das Ziel ist dabei die Auswahl geeigneter Bauteile und die Justierung der Softwaresteuerung, um das Netz auf eine gewisse Bandbreite an Lastszenarien hin optimal auszurichten. Da die Simulation des Lastflusses in Gleichstromnetzen zu aufwändig ist, um sie direkt in ein Optimierungsmodell zu integrieren, trainieren wir Klassifikationsmodelle wie z. B. Entscheidungsbäume um die komplexen Einflüsse von Bauteilen und Software auf die Netzstabilität zu repräsentieren. Diese Randbedingungen werden gemischt-ganzzahlig reformuliert und stellen so die gelernten Zusammenhänge in deutlich einfacherer Form approximativ im Optimierungsmodell dar. Speziell darauf angepasste Dekompositionsalgorithmen sorgen für eine schnellere Berechnung der Lösung. Dadurch erhalten wir effiziente Verfahren zur Berechnung optimaler Netzauslegungen.

»ADA wills wissen« Podcast

In unserer neuen Podcast-Reihe »ADA wills wissen« befinden sich die Kompetenzsäulen-Verantwortlichen mit Ada im Gespräch und geben Einblick in ihre Forschungsschwerpunkte, Herausforderungen und Methoden. Den Auftakt bildet Andreas Bärmann mit einer Folge zur Mathematischen Optimierung. Hören Sie jetzt rein!

»ADA wills wissen« Podcast für Mathematische Optimierung mit Dr. Andreas Bärmann

Die KI-Kompetenzsäulen des ADA Lovelace Centers

Automatisches Lernen
© Fraunhofer IIS

Das automatische Lernen deckt einen großen Bereich ab, der bei der Automatisierung der Merkmalserkennung und -auswahl für gegebene Datensätze sowie der Modellsuche und -optimierung beginnt, über deren automatisierte Bewertung reicht und bis hin zur adaptiven Anpassung der Modelle durch Trainingsdaten und Systemfeedback geht. Dies spielt z.B. bei der datengetriebenen Entscheidungshilfe durch Assistentensysteme eine große Rolle. 

Sequenzbasiertes Lernen beschäftigt sich mit zeitlichen und kausalen Zusammenhängen in Daten wie sie z. B. in der Sprachverarbeitung, Ereignisverarbeitung, Biosequenzanalyse oder auch in Multimediadaten auftreten. Dabei wird aus beobachteten Ereignissen der aktuelle Systemzustand erkannt und zukünftige Zustände vorhergesagt, was sowohl möglich ist, wenn nur die Reihenfolge ihres Auftretens bekannt ist, als auch dann, wenn sie genaue Zeitstempel tragen.

Als erfahrungsbasiertes Lernen bezeichnet man Methoden, die es einem System erlauben, sich selbst zu optimieren, indem es mit der Umwelt interagiert und deren Feedback auswertet, oder sich an veränderliche Umweltbedingungen dynamisch anpasst. Hierzu zählen die automatisierte Erzeugung von Modellen zur Bewertung und Optimierung von Geschäftsprozessen, Transportabläufen oder auch Robotersteuerungen in der industriellen Fertigung. 

Few Labels Learning
© Fraunhofer IIS

Die bahnbrechenden Erfolge der KI bei Aufgaben wie Spracherkennung, Objekterkennung oder maschineller Übersetzung sind u.a. auf die Verfügbarkeit von enorm großen, annotierten Datensätzen zurückzuführen. Allerdings ist diese in vielen realen Szenarien, besonders im Industrieumfeld, begrenzt. Daher erforschen wir das Lernen mit wenigen annotierten Daten im Kontext von Techniken des unüberwachten, semi-überwachten- und des Transfer-Lernens.

 

Das digitale Datenvolumen (sog. »Big Data«) wächst seit einigen Jahren ungebremst. Bei der Wissensgenerierung müssen die erzielten Ergebnisse und Vorhersagen den Anwendern in geeigneter Weise plausibel und transparent gemacht werden. Dieser Aspekt wird im ADA Lovelace Center unter dem Stichwort erklärbares Lernen erforscht, und sorgt dafür, die Akzeptanz der künstlichen Intelligenz bei Anwendern in Wirtschaft, Wissenschaft und Gesellschaft zu erhöhen.

 

Prozessbewusstes Lernen stellt das Bindeglied zwischen der Modellierung und Analyse von Prozessen und dem Data Mining dar. Im Fokus steht dabei die Prozesserkennung, Konformitätsprüfung und Prozessverbesserung auf Daten in Form von Ereignisprotokollen. Sie dient dem Vergleich von Soll- und Ist-Zuständen, z.B. bei Geschäftsprozessen in Form von Workflow-Management-Systemen (WMS) oder Enterprise-Resource-Planning-Systemen (ERP).

Die Aufgabe der Semantik ist es, Daten und Datenstrukturen formal definiert, standardisiert, inhaltlich widerspruchsfrei und eindeutig zu beschreiben. So müssen bei Industrie 4.0 verschiedenste Entitäten (wie Sensoren, Produkte, Maschinen oder Transportsysteme) in der Lage sein, deren Eigenschaften, Fähigkeiten oder Zustände anderer Entitäten in der Wertschöpfungskette zu interpretieren.

Few Data Learning beschäftigt sich mit der Aufbereitung und Vervollständigung von Daten sowie der Erzeugung einer ausreichenden Menge an Datensätzen, z. B. KI-Anwendungen auf Materialstammdaten in der Industrie. Das umfasst die Aufbereitung fehlerhafter Datensätze und den Einsatz von Simulationstechniken um fehlende Daten zu erzeugen.

Das könnte Sie auch interessieren

 

Energieeffiziente Fahrplanoptimierung

Experten der Friedrich-Alexander-Universität Erlangen-Nürnberg und des Fraunhofer-Instituts für Integrierte Schaltungen IIS arbeiten zusammen mit der VAG Verkehrs-Aktiengesellschaft daran, durch eine effizienten Fahrweise in Verbindung mit einer intelligenten Koordination aller Bahnen den Energieverbrauch der Nürnberger U-Bahn zu senken.

Weiterbildungen am ADA Lovelace Center

Das ADA Lovelace Center for Analytics, Data and Applications bietet – gemeinsam mit seinen Kooperationspartnern – Weiterbildungsprogramme rund um Konzepte, Methoden und konkrete Anwendungen im Themenbereich Data Analytics und KI.

Hierzu werden Seminare mit den folgenden Schwerpunkten angeboten:

Maschinelles Lernen

Reinforcement Learning

Deep Learning and Computer Vision