Beitrag vom Institut für Automatisierung der Chinesischen Akademie der Wissenschaften

Qubits |. Öffentliches Konto QbitAI

Die Lösung des stochastischen Planungsproblems dauert nur 15 Sekunden, was 1440-mal schneller ist als herkömmliche Methoden!

Neue Forschungen des Instituts für Automatisierung der Chinesischen Akademie der Wissenschaften haben GCN genutzt, um bei solchen Problemen neue Durchbrüche zu erzielen. Das Papier wurde für ICML 2024, die führende KI-Konferenz, ausgewählt.

Dadurch ist eine effiziente Entscheidungsfindung auch unter unsicheren Bedingungen möglich.

Die Entscheidungsfindung unter Unsicherheit ist eine wichtige Art von Entscheidungsproblem, bei dem Entscheidungsträger alle zufälligen Situationen vollständig berücksichtigen und die vernünftigste Entscheidung treffen müssen.

Im Bereich der Mathematik ist die stochastische Programmierung eine häufig verwendete Lösung, die Zufallsvariablen in mathematische Programmiermodelle einbezieht.

Unter diesen ist die zweistufige stochastische Programmierung (2SP) eine wirksame Methode zur Modellierung solcher Entscheidungsprobleme und wird häufig verwendet.

Diese Errungenschaft des Instituts für Automatisierung der Chinesischen Akademie der Wissenschaften, das HGCN2SP-Modell (HGCN steht für Hierarchical Graph Convolution Network), ist genau die Kombination der 2SP-Methode undBildIn Kombination mit Faltungsnetzwerken kann das Modell verwendet werden, um solche Probleme effizienter zu lösen.

Der Erstautor der Arbeit ist Wu Yang, ein Doktorand am Institut, und der Forscher Zhang Yifan ist der korrespondierende Autor.

Was ist zweistufige stochastische Programmierung?

Die Grundidee der stochastischen Planung besteht darin, die möglichen zukünftigen Situationen des Problems in mehrere Beispielszenarien umzuwandeln, dann jedes Beispielszenario zu optimieren und schließlich die Optimierungsergebnisse aller Szenarien zu integrieren, um aktuelle Entscheidungen zu leiten.

Zu den Anwendungsbereichen gehören Lieferkettenmanagement, Finanzinvestitionen, Energieverteilung, Katastrophenmanagement usw.

Die zweistufige stochastische Planung unterteilt den Prozess, wie der Name schon sagt, in zwei Phasen.

Insbesondere erfordern diese beiden Phasen Makro- und Mikroentscheidungen, um die Gesamtkosten zu minimieren bzw. den Gesamtnutzen zu maximieren.

Entscheidungen in der ersten Phase werden getroffen, bevor sich Unsicherheit manifestiert, mit dem Ziel, die anfängliche Entscheidung zu optimieren, um einer Vielzahl möglicher Zukunftsszenarien gerecht zu werden.

Entscheidungen in der zweiten Phase werden getroffen, nachdem Unsicherheit auftritt, und auf der Grundlage der Entscheidungen in der ersten Phase und der tatsächlichen Ereignisse angepasst, um das Gesamtergebnis zu optimieren.

Durch das 2SP-Modell müssen Entscheidungsträger die Auswirkungen verschiedener Szenarien, die während des Entscheidungsprozesses auftreten können, vollständig berücksichtigen, um so die Robustheit und Flexibilität der Entscheidungsfindung zu verbessern und wissenschaftlichere und effizientere Entscheidungen zu treffen.

Angenommen, wir möchten einige von 10 Kandidatenstandorten für den Bau von Lagerhäusern auswählen, um den Anforderungen von 20 umliegenden Gebieten gerecht zu werden.

Im ersten Schritt muss entschieden werden, welcher dieser 10 Kandidatenstandorte ausgewählt werden soll;

In der zweiten Stufe muss die Verteilungsbeziehung zwischen dem Lager und der Region bestimmt werden. Zu diesem Zeitpunkt beträgt die Anzahl der Entscheidungsvariablen bis zu 200 (dh ob Lager i an Region j verteilt).

△Bild erstellt von DALL·E

Mathematisch wird das 2SP-Problem normalerweise wie folgt ausgedrückt:

Unter diesen stellt Q(x,ξ) das Optimierungsproblem der zweiten Stufe dar, wenn die Entscheidung x und das Szenario ξ der ersten Stufe gegeben sind, und seine Form ist:

In der tatsächlichen Lösung werden im Allgemeinen N Szenen abgetastet, um den entsprechenden Q-Wert zu berechnen und die Erwartung anzunähern.

Je größer N ist, desto glaubwürdiger ist die Näherung. Mit zunehmender Anzahl von Szenarien nimmt jedoch die Größe des Problems schnell zu, was zu einer erheblichen Verlängerung der Lösungszeit führt.

Lassen Sie uns das Problem der Lagerstandortauswahl veranschaulichen. Um bessere Standortauswahlentscheidungen treffen zu können, müssen wir unsichere Faktoren wie Nachfrage, Wetter, Personenfluss, Verkehr usw. berücksichtigen, und Änderungen in jedem Faktor entsprechen einem Szenario.

Das bedeutet, dass N verschiedene Szenarien großflächig untersucht werden müssen, um die reale Situation so genau wie möglich zu simulieren. Zu diesem Zeitpunkt beträgt die Gesamtzahl der Entscheidungsvariablen in der zweiten Stufe bis zu 200 N, was die Lösungszeit extrem lang macht.

Wenn N 500 beträgt, dauert es sogar mit dem fortschrittlichsten kommerziellen Löser Gurobi mindestens 6 Stunden, um die optimale Entscheidung zu treffen.

Herkömmliche Methoden verwenden normalerweise Zufallsstichproben- oder Clustering-Techniken, um eine kleine Anzahl von Szenarien (z. B. 10 oder 20) für eine ungefähre Lösung auszuwählen. Obwohl die Zeit verkürzt wird, ist die Qualität der resultierenden Entscheidungen häufig nicht ideal.

Auf dieser Grundlage wird die Entwurfsidee des HGCN2SP-Modells abgeleitet: Bei gleichzeitiger Reduzierung der Anzahl der Abtastszenen sollen möglichst genaue Ergebnisse erzielt werden.

Verwendung von Graph-Faltungsnetzwerken zur Lösung des 2SP-Problems

Das Forschungsteam schlug das HGCN2SP-Modell vor, das auf einem hierarchischen Graphenfaltungsnetzwerk basiert, um das zweistufige stochastische Programmierproblem zu lösen.

Insbesondere im Hinblick auf das Algorithmusdesign charakterisierte das Team das 2SP-Problem durch die Konstruktion eines hierarchischen Diagramms, bei dem das untere Diagramm zur Darstellung der Eigenschaften jeder Szene und das obere Diagramm zur Darstellung der Beziehung zwischen Szenen verwendet wurde.

Anschließend wird das Hierarchical Graph Convolutional Network (HGCN) verwendet, um die Einbettungsinformationen des zugrunde liegenden Szenenuntergraphen und die Strukturinformationen des Szenenraums der obersten Ebene zu extrahieren und die Szenendarstellung zu extrahieren.

Der auf dem Aufmerksamkeitsmechanismus basierende Decoder wird verwendet, um Szenen in der richtigen Reihenfolge auszuwählen. Er kann nicht nur repräsentative Szenen finden, um das Problem zu vereinfachen, sondern auch die Auswahl der Anfangsbasis verbessern, wenn das Problem durch die Simplex-Methode gelöst wird Szenen. Verbessert die Lösungszeit erheblich.

△HGCN2SP-Modellrahmen

Das Team kombinierte außerdem Reinforcement Learning (RL), um die Qualität der Entscheidungsfindung und die Lösungszeit umfassend zu untersuchen und so die Modellparameter zu optimieren und so die Effizienz und Qualität der Problemlösung deutlich zu verbessern.

Obwohl HGCN2SP im obigen Lagerstandortproblem nur 10 Szenarien auswählte, betrug der Unterschied zwischen seinen Entscheidungsergebnissen und der vom Gurobi-Löser in 6 Stunden getroffenen Entscheidung nur 1,7 %, und die Lösungszeit betrug nur 15 Sekunden, was der Geschwindigkeit entspricht Die Verbesserung beträgt das 1440-fache, was die Wirksamkeit dieser Methode voll und ganz widerspiegelt.

Darüber hinaus erzielte HGCN2SP im Experiment zum Network Design Problem (NDP) ähnliche Entscheidungseffekte in weniger als der Hälfte der Zeit wie bestehende Methoden.

Insbesondere in großen Instanzen und einer großen Anzahl von Szenarien verfügt HGCN2SP weiterhin über starke Generalisierungsfähigkeiten.

Der Vorschlag von HGCN2SP bietet eine neue Idee und ein neues Werkzeug zur Lösung komplexer 2SP-Probleme und bietet breite Anwendungsaussichten.

Das Forschungsteam plant, das Modell weiter zu optimieren, die Schulungskosten zu senken und seine Anwendung bei praktischeren Problemen zu untersuchen.

Papieradresse:
https://openreview.net/forum?id=8onaVSFTEj