Disumbangkan oleh Institut Otomasi, Akademi Ilmu Pengetahuan Tiongkok

Qubit |. Akun publik QbitAI

Hanya membutuhkan waktu 15 detik untuk menyelesaikan masalah perencanaan stokastik, yang 1440 kali lebih cepat dibandingkan metode tradisional!

Penelitian baru dari Institut Otomasi Akademi Ilmu Pengetahuan Tiongkok telah menggunakan GCN untuk mencapai terobosan baru dalam permasalahan tersebut. Makalah ini telah dipilih untuk ICML 2024, konferensi AI terkemuka.

Artinya pengambilan keputusan yang efisien dapat dicapai bahkan dalam kondisi yang tidak pasti.

Pengambilan keputusan dalam kondisi ketidakpastian adalah jenis masalah pengambilan keputusan yang penting, yang mengharuskan pengambil keputusan untuk sepenuhnya mempertimbangkan semua situasi acak dan membuat keputusan yang paling masuk akal.

Dalam bidang matematika, solusi yang umum digunakan adalah pemrograman stokastik, yang memasukkan variabel acak dalam model pemrograman matematika.

Diantaranya, Pemrograman Stokastik Dua Tahap (2SP) adalah metode yang efektif untuk memodelkan masalah pengambilan keputusan dan digunakan secara luas.

Pencapaian Institute of Automation, Chinese Academy of Sciences, model HGCN2SP (HGCN adalah singkatan dari Hierarchical Graph Convolution Network), merupakan kombinasi dari metode 2SP dangambarDikombinasikan dengan jaringan konvolusional, model ini dapat digunakan untuk memecahkan masalah tersebut dengan lebih efisien.

Penulis pertama makalah ini adalah Wu Yang, seorang mahasiswa doktoral di institut tersebut, dan peneliti Zhang Yifan adalah penulis korespondennya.

Apa itu pemrograman stokastik dua tahap?

Ide dasar dari perencanaan stokastik adalah untuk mengubah kemungkinan situasi masalah di masa depan menjadi beberapa skenario sampel, kemudian mengoptimalkan setiap skenario sampel, dan terakhir mengintegrasikan hasil optimasi dari semua skenario untuk memandu keputusan saat ini.

Area penerapannya meliputi manajemen rantai pasokan, investasi keuangan, pengiriman energi, manajemen darurat bencana, dll.

Perencanaan stokastik dua tahap, seperti namanya, membagi proses menjadi dua tahap.

Secara khusus, kedua tahap ini memerlukan pengambilan keputusan makro dan mikro masing-masing untuk meminimalkan total biaya atau memaksimalkan manfaat total.

Keputusan pada tahap pertama diambil sebelum ketidakpastian muncul, dengan tujuan mengoptimalkan keputusan awal untuk beradaptasi dengan berbagai kemungkinan skenario masa depan.

Keputusan pada tahap kedua diambil setelah ketidakpastian muncul dan disesuaikan berdasarkan keputusan pada tahap pertama dan apa yang sebenarnya terjadi untuk mengoptimalkan hasil secara keseluruhan.

Melalui model 2SP, pengambil keputusan perlu mempertimbangkan sepenuhnya dampak berbagai skenario yang mungkin terjadi selama proses pengambilan keputusan, sehingga meningkatkan ketahanan dan fleksibilitas pengambilan keputusan serta membuat keputusan yang lebih ilmiah dan efisien.

Misalnya, kita ingin memilih 10 calon lokasi untuk membangun gudang guna memenuhi kebutuhan 20 wilayah sekitarnya.

Yang perlu diputuskan pada tahap pertama adalah yang mana dari 10 calon lokasi tersebut yang harus dipilih;

Pada tahap kedua harus ditentukan hubungan distribusi antara gudang dengan wilayah. Pada saat ini, jumlah variabel keputusan sebanyak 200 (yaitu apakah gudang i mendistribusikan ke wilayah j).

△Gambar dihasilkan oleh DALL·E

Secara matematis, permasalahan 2SP biasanya dinyatakan sebagai:

Diantaranya, Q(x,ξ) mewakili masalah optimasi tahap kedua dengan keputusan tahap pertama x dan skenario ξ, dan bentuknya adalah:

Dalam solusi sebenarnya, N adegan umumnya diambil sampelnya untuk menghitung nilai Q yang sesuai guna memperkirakan ekspektasi.

Jelasnya, semakin besar N, semakin kredibel perkiraannya. Namun, seiring bertambahnya jumlah skenario, ukuran masalah akan meluas dengan cepat, yang akan menyebabkan peningkatan waktu penyelesaian yang signifikan.

Mari kita gunakan masalah pemilihan lokasi gudang sebagai ilustrasi. Untuk membuat keputusan pemilihan lokasi yang lebih baik, kita perlu memperhitungkan faktor-faktor yang tidak pasti seperti permintaan, cuaca, arus orang, lalu lintas, dll., dan perubahan pada setiap faktor sesuai dengan a. skenario.

Artinya, N skenario berbeda perlu diambil sampelnya secara luas untuk mensimulasikan situasi nyata sedekat mungkin. Saat ini, jumlah total variabel keputusan pada tahap kedua akan mencapai 200N, sehingga waktu penyelesaian menjadi sangat lama.

Faktanya, ketika N adalah 500, bahkan dengan menggunakan pemecah komersial tercanggih Gurobi, dibutuhkan setidaknya 6 jam untuk membuat keputusan yang optimal.

Metode tradisional biasanya menggunakan teknik pengambilan sampel secara acak atau pengelompokan untuk memilih sejumlah kecil skenario (seperti 10 atau 20) untuk perkiraan solusi. Meskipun waktunya dipersingkat, kualitas keputusan yang dihasilkan seringkali tidak ideal.

Berdasarkan hal ini, ide desain model HGCN2SP diturunkan - sambil mengurangi jumlah adegan pengambilan sampel, dapatkan hasil yang akurat sedekat mungkin.

Menggunakan jaringan konvolusional grafik untuk menyelesaikan masalah 2SP

Tim peneliti mengusulkan model HGCN2SP berdasarkan jaringan konvolusi grafik hierarki untuk menyelesaikan masalah pemrograman stokastik dua tahap.

Khusus dalam hal desain algoritma, tim mengkarakterisasi masalah 2SP dengan membuat grafik hierarki, di mana grafik bawah digunakan untuk mewakili karakteristik setiap adegan, sedangkan grafik atas digunakan untuk mewakili hubungan antar adegan.

Kemudian, jaringan konvolusional grafik hierarki (HGCN) digunakan untuk menambang informasi penyematan subgraf pemandangan yang mendasarinya dan informasi struktural ruang pemandangan tingkat atas untuk mengekstrak representasi pemandangan.

Decoder berdasarkan mekanisme perhatian digunakan untuk memilih adegan secara berurutan. Decoder tidak hanya dapat menemukan adegan yang representatif untuk menyederhanakan masalah, tetapi juga meningkatkan pemilihan basis awal saat menyelesaikan masalah dengan metode simpleks dengan mengoptimalkan urutan dari adegan tersebut. adegan. Secara signifikan meningkatkan waktu solusi.

△ Kerangka model HGCN2SP

Tim juga menggabungkan pembelajaran penguatan (RL) untuk memeriksa secara komprehensif kualitas pengambilan keputusan dan waktu solusi guna mengoptimalkan parameter model, sehingga secara signifikan meningkatkan efisiensi dan kualitas pemecahan masalah.

Pada permasalahan lokasi gudang di atas, walaupun HGCN2SP hanya memilih 10 skenario, namun selisih hasil keputusannya dengan keputusan yang diambil oleh pemecah Gurobi dalam waktu 6 jam hanya 1,7%, dan waktu penyelesaian hanya 15 detik, yang setara dengan kecepatan. Peningkatannya sebesar 1440 kali lipat, yang sepenuhnya mencerminkan efektivitas metode ini.

Selain itu, dalam eksperimen Network Design Problem (NDP), HGCN2SP mencapai efek pengambilan keputusan serupa dalam waktu kurang dari separuh waktu metode yang ada.

Khususnya dalam contoh skala besar dan skenario dalam jumlah besar, HGCN2SP masih mempertahankan kemampuan generalisasi yang kuat.

Usulan HGCN2SP memberikan ide dan alat baru untuk memecahkan masalah 2SP yang kompleks, dan memiliki prospek penerapan yang luas.

Tim peneliti berencana untuk lebih mengoptimalkan model, mengurangi biaya pelatihan, dan mengeksplorasi penerapannya dalam masalah yang lebih praktis.

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