Συνεισφορά από το Ινστιτούτο Αυτοματισμού, Κινεζική Ακαδημία Επιστημών

Qubits | Δημόσιος λογαριασμός QbitAI

Χρειάζονται μόνο 15 δευτερόλεπτα για να λυθεί το πρόβλημα του στοχαστικού σχεδιασμού, το οποίο είναι 1440 φορές ταχύτερο από τις παραδοσιακές μεθόδους!

Νέα έρευνα από το Ινστιτούτο Αυτοματισμού της Κινεζικής Ακαδημίας Επιστημών χρησιμοποίησε το GCN για να επιτύχει νέες ανακαλύψεις σε τέτοια προβλήματα Η εργασία επιλέχθηκε για το ICML 2024, το κορυφαίο συνέδριο AI.

Αυτό σημαίνει ότι η αποτελεσματική λήψη αποφάσεων μπορεί να επιτευχθεί ακόμη και υπό αβέβαιες συνθήκες.

Η λήψη αποφάσεων σε συνθήκες αβεβαιότητας είναι ένας σημαντικός τύπος προβλήματος λήψης αποφάσεων, το οποίο απαιτεί από τους λήπτες αποφάσεων να εξετάζουν πλήρως όλες τις τυχαίες καταστάσεις και να λαμβάνουν την πιο λογική απόφαση.

Στον τομέα των μαθηματικών, μια ευρέως χρησιμοποιούμενη λύση είναι ο στοχαστικός προγραμματισμός, ο οποίος περιλαμβάνει τυχαίες μεταβλητές σε μοντέλα μαθηματικού προγραμματισμού.

Μεταξύ αυτών, ο Στοχαστικός Προγραμματισμός Δύο Σταδίων (2SP) είναι μια αποτελεσματική μέθοδος για τη μοντελοποίηση τέτοιων προβλημάτων λήψης αποφάσεων και χρησιμοποιείται ευρέως.

Αυτό το επίτευγμα του Ινστιτούτου Αυτοματισμού της Κινεζικής Ακαδημίας Επιστημών, το μοντέλο HGCN2SP (HGCN σημαίνει Hierarchical Graph Convolution Network), είναι ακριβώς ο συνδυασμός της μεθόδου 2SP καιεικόναΣε συνδυασμό με συνελικτικά δίκτυα, το μοντέλο μπορεί να χρησιμοποιηθεί για την αποτελεσματικότερη επίλυση τέτοιων προβλημάτων.

Ο πρώτος συγγραφέας της εργασίας είναι ο Wu Yang, διδακτορικός φοιτητής στο ινστιτούτο, και ο ερευνητής Zhang Yifan είναι ο αντίστοιχος συγγραφέας.

Τι είναι ο στοχαστικός προγραμματισμός δύο σταδίων;

Η βασική ιδέα του στοχαστικού σχεδιασμού είναι να μετατρέψει τις πιθανές μελλοντικές καταστάσεις του προβλήματος σε πολλά δείγματα σεναρίων, στη συνέχεια να βελτιστοποιήσει κάθε δείγμα σεναρίου και τελικά να ενσωματώσει τα αποτελέσματα βελτιστοποίησης όλων των σεναρίων για να καθοδηγήσει τις τρέχουσες αποφάσεις.

Οι τομείς εφαρμογής του περιλαμβάνουν τη διαχείριση της εφοδιαστικής αλυσίδας, τις οικονομικές επενδύσεις, την αποστολή ενέργειας, τη διαχείριση έκτακτης ανάγκης καταστροφών κ.λπ.

Ο στοχαστικός σχεδιασμός δύο σταδίων, όπως υποδηλώνει το όνομα, χωρίζει τη διαδικασία σε δύο στάδια.

Συγκεκριμένα, αυτά τα δύο στάδια απαιτούν τη λήψη μακροοικονομικών και μικρο-αποφάσεων αντίστοιχα για την ελαχιστοποίηση του συνολικού κόστους ή τη μεγιστοποίηση των συνολικών οφελών.

Οι αποφάσεις στο πρώτο στάδιο λαμβάνονται πριν εκδηλωθεί η αβεβαιότητα, με στόχο τη βελτιστοποίηση της αρχικής απόφασης προσαρμογής σε μια ποικιλία πιθανών μελλοντικών σεναρίων.

Οι αποφάσεις στο δεύτερο στάδιο λαμβάνονται μετά την εμφάνιση της αβεβαιότητας και προσαρμόζονται με βάση τις αποφάσεις στο πρώτο στάδιο και το τι πραγματικά συνέβη για τη βελτιστοποίηση του συνολικού αποτελέσματος.

Μέσω του μοντέλου 2SP, οι υπεύθυνοι λήψης αποφάσεων πρέπει να εξετάσουν πλήρως τον αντίκτυπο διαφορετικών σεναρίων που μπορεί να προκύψουν κατά τη διαδικασία λήψης αποφάσεων, βελτιώνοντας έτσι την ευρωστία και την ευελιξία της λήψης αποφάσεων και τη λήψη πιο επιστημονικών και αποτελεσματικών αποφάσεων.

Για παράδειγμα, ας υποθέσουμε ότι θέλουμε να επιλέξουμε μερικές από τις 10 υποψήφιες τοποθεσίες για την κατασκευή αποθηκών για να καλύψουμε τις ανάγκες 20 γύρω περιοχών.

Αυτό που πρέπει να αποφασιστεί στο πρώτο στάδιο είναι ποια από αυτές τις 10 υποψήφιες τοποθεσίες θα πρέπει να επιλεγεί.

Στο δεύτερο στάδιο, η σχέση διανομής μεταξύ της αποθήκης και της περιοχής πρέπει να καθοριστεί.

△Εικόνα που δημιουργήθηκε από DALL·E

Μαθηματικά, το πρόβλημα 2SP εκφράζεται συνήθως ως:

Μεταξύ αυτών, το Q(x,ξ) αντιπροσωπεύει το πρόβλημα βελτιστοποίησης δεύτερου σταδίου δεδομένης της απόφασης πρώτου σταδίου x και του σεναρίου ξ, και η μορφή του είναι:

Στην πραγματική λύση, γενικά γίνεται δειγματοληψία Ν σκηνών για να υπολογιστεί η αντίστοιχη τιμή Q για να προσεγγιστεί η προσδοκία.

Προφανώς, όσο μεγαλύτερο είναι το N, τόσο πιο αξιόπιστη είναι η προσέγγιση. Ωστόσο, καθώς αυξάνεται ο αριθμός των σεναρίων, το μέγεθος του προβλήματος επεκτείνεται γρήγορα, γεγονός που θα οδηγήσει σε σημαντική αύξηση του χρόνου επίλυσης.

Ας χρησιμοποιήσουμε αυτό το πρόβλημα τοποθεσίας της αποθήκης για να δείξουμε καλύτερα τη θέση, πρέπει να λάβουμε υπόψη αβέβαιους παράγοντες όπως η ζήτηση, ο καιρός, η ροή των ανθρώπων και η κίνηση, και οι αλλαγές σε κάθε παράγοντα αντιστοιχούν σε ένα σενάριο.

Αυτό σημαίνει ότι N διαφορετικά σενάρια πρέπει να δειγματιστούν ευρέως για να προσομοιωθεί η πραγματική κατάσταση όσο το δυνατόν πλησιέστερα. Αυτή τη στιγμή, ο συνολικός αριθμός των μεταβλητών απόφασης στο δεύτερο στάδιο θα είναι τόσο υψηλός όσο 200N, καθιστώντας τον χρόνο επίλυσης εξαιρετικά μεγάλο.

Στην πραγματικότητα, όταν το N είναι 500, ακόμη και χρησιμοποιώντας τον πιο προηγμένο εμπορικό λύτη Gurobi, θα χρειαστούν τουλάχιστον 6 ώρες για να ληφθεί η βέλτιστη απόφαση.

Οι παραδοσιακές μέθοδοι χρησιμοποιούν συνήθως τεχνικές τυχαίας δειγματοληψίας ή ομαδοποίησης για την επιλογή ενός μικρού αριθμού σεναρίων (όπως 10 ή 20) για κατά προσέγγιση λύση Αν και ο χρόνος μειώνεται, η ποιότητα των αποφάσεων που προκύπτουν συχνά δεν είναι ιδανική.

Με βάση αυτό, προκύπτει η σχεδιαστική ιδέα του μοντέλου HGCN2SP - μειώνοντας τον αριθμό των σκηνών δειγματοληψίας, αποκτήστε όσο το δυνατόν πιο ακριβή αποτελέσματα.

Χρήση συνελικτικών δικτύων γραφημάτων για την επίλυση του προβλήματος 2SP

Η ερευνητική ομάδα πρότεινε το μοντέλο HGCN2SP που βασίζεται σε δίκτυο συνέλιξης ιεραρχικού γραφήματος για να λύσει το πρόβλημα του στοχαστικού προγραμματισμού δύο σταδίων.

Συγκεκριμένα, όσον αφορά τον σχεδιασμό αλγορίθμων, η ομάδα χαρακτήρισε το πρόβλημα 2SP κατασκευάζοντας ένα ιεραρχικό γράφημα, στο οποίο το κάτω γράφημα χρησιμοποιήθηκε για να αναπαραστήσει τα χαρακτηριστικά κάθε σκηνής, ενώ το επάνω γράφημα χρησιμοποιήθηκε για να αναπαραστήσει τη σχέση μεταξύ των σκηνών.

Στη συνέχεια, το συνελικτικό δίκτυο ιεραρχικού γραφήματος (HGCN) χρησιμοποιείται για την εξόρυξη των πληροφοριών ενσωμάτωσης του υποκειμένου υπογράφου σκηνής και των δομικών πληροφοριών του χώρου σκηνής ανώτατου επιπέδου για την εξαγωγή της αναπαράστασης σκηνής.

Ο αποκωδικοποιητής που βασίζεται στον μηχανισμό προσοχής χρησιμοποιείται για την επιλογή σκηνών με τη σειρά. Μπορεί όχι μόνο να βρει αντιπροσωπευτικές σκηνές για την απλοποίηση του προβλήματος, αλλά και να βελτιώσει την επιλογή της αρχικής βάσης κατά την επίλυση του προβλήματος με τη μέθοδο simplex βελτιστοποιώντας τη σειρά του. σκηνές Βελτιώνει σημαντικά το χρόνο επίλυσης.

△Πλαίσιο μοντέλου HGCN2SP

Η ομάδα συνδύασε επίσης την ενισχυτική μάθηση (RL) για να εξετάσει διεξοδικά την ποιότητα λήψης αποφάσεων και τον χρόνο λύσης για τη βελτιστοποίηση των παραμέτρων του μοντέλου, βελτιώνοντας σημαντικά την αποτελεσματικότητα και την ποιότητα της επίλυσης προβλημάτων.

Στο παραπάνω πρόβλημα θέσης αποθήκης, αν και το HGCN2SP επέλεξε μόνο 10 σενάρια, η διαφορά μεταξύ των αποτελεσμάτων της απόφασής του και της απόφασης που έλαβε ο λύτης Gurobi σε 6 ώρες ήταν μόνο 1,7% και ο χρόνος λύσης ήταν μόνο 15 δευτερόλεπτα, που ισοδυναμεί με ταχύτητα Η βελτίωση είναι 1440 φορές, γεγονός που αντικατοπτρίζει πλήρως την αποτελεσματικότητα αυτής της μεθόδου.

Επιπλέον, στο πείραμα του Προβλήματος Σχεδιασμού Δικτύου (NDP), το HGCN2SP πέτυχε παρόμοια αποτελέσματα λήψης αποφάσεων σε λιγότερο από το μισό χρόνο από τις υπάρχουσες μεθόδους.

Ειδικά σε περιπτώσεις μεγάλης κλίμακας και σε μεγάλο αριθμό σεναρίων, το HGCN2SP εξακολουθεί να διατηρεί ισχυρές δυνατότητες γενίκευσης.

Η πρόταση του HGCN2SP παρέχει μια νέα ιδέα και εργαλείο για την επίλυση πολύπλοκων προβλημάτων 2SP και έχει ευρείες προοπτικές εφαρμογής.

Η ερευνητική ομάδα σχεδιάζει να βελτιστοποιήσει περαιτέρω το μοντέλο, να μειώσει το κόστος εκπαίδευσης και να διερευνήσει την εφαρμογή του σε πιο πρακτικά προβλήματα.

Διεύθυνση χαρτιού:
https://openreview.net/forum?id=8onaVSFTEj