Osallistuja: Institute of Automation, Kiinan tiedeakatemia

Qubits |. Julkinen tili QbitAI

Stokastisen suunnitteluongelman ratkaiseminen kestää vain 15 sekuntia, mikä on 1440 kertaa nopeampi kuin perinteiset menetelmät!

Kiinan tiedeakatemian automaatioinstituutin uusi tutkimus on käyttänyt GCN:ää uusien läpimurtojen saavuttamiseen tällaisissa ongelmissa. Paperi on valittu ICML 2024:n huippukokoukseen.

Tämä tarkoittaa, että tehokas päätöksenteko voidaan saavuttaa myös epävarmoissa olosuhteissa.

Päätöksenteko epävarmuudessa on tärkeä päätöksenteko-ongelma, joka edellyttää päättäjiltä kaikkien satunnaisten tilanteiden täysimääräistä huomioimista ja järkevimmän päätöksen tekemistä.

Matematiikan alalla yleisesti käytetty ratkaisu on stokastinen ohjelmointi, joka sisältää satunnaismuuttujia matemaattisissa ohjelmointimalleissa.

Niistä kaksivaiheinen stokastinen ohjelmointi (2SP) on tehokas menetelmä tällaisten päätöksentekoongelmien mallintamiseen ja sitä käytetään laajalti.

Tämä Kiinan tiedeakatemian automaatioinstituutin saavutus, HGCN2SP-malli (HGCN tulee sanoista Hierarchical Graph Convolution Network), on täsmälleen yhdistelmä 2SP-menetelmästä jakuvaYhdessä konvoluutioverkkojen kanssa mallia voidaan käyttää tällaisten ongelmien ratkaisemiseen tehokkaammin.

Paperin ensimmäinen kirjoittaja on Wu Yang, instituutin tohtoriopiskelija, ja tutkija Zhang Yifan on vastaava kirjoittaja.

Mitä on kaksivaiheinen stokastinen ohjelmointi?

Stokastisen suunnittelun perusideana on muuntaa ongelman mahdolliset tulevaisuuden tilanteet useiksi näyteskenaarioiksi, sitten optimoida jokainen esimerkkiskenaario ja lopuksi integroida kaikkien skenaarioiden optimointitulokset ohjaamaan nykyisiä päätöksiä.

Sen sovellusalueita ovat toimitusketjun hallinta, taloudelliset investoinnit, energian lähettäminen, katastrofihätätilanteiden hallinta jne.

Kaksivaiheinen stokastinen suunnittelu jakaa nimensä mukaisesti prosessin kahteen vaiheeseen.

Erityisesti nämä kaksi vaihetta edellyttävät makro- ja mikropäätösten tekemistä kokonaiskustannusten minimoimiseksi tai kokonaishyötyjen maksimoimiseksi.

Ensimmäisen vaiheen päätökset tehdään ennen epävarmuuden ilmenemistä, ja tavoitteena on optimoida alkuperäinen päätös sopeutuakseen erilaisiin mahdollisiin tulevaisuuden skenaarioihin.

Toisen vaiheen päätökset tehdään epävarmuuden ilmaantumisen jälkeen ja niitä mukautetaan ensimmäisen vaiheen päätösten ja todellisten tapahtumien perusteella kokonaistuloksen optimoimiseksi.

2SP-mallin avulla päättäjien on otettava täysin huomioon erilaisten päätöksentekoprosessin aikana mahdollisesti ilmenevien skenaarioiden vaikutukset, mikä parantaa päätöksenteon kestävyyttä ja joustavuutta sekä tekee tieteellisempiä ja tehokkaampia päätöksiä.

Oletetaan esimerkiksi, että haluamme valita 10:stä ehdokaspaikasta varastojen rakentamiseen 20 ympäröivän alueen tarpeisiin.

Ensimmäisessä vaiheessa on päätettävä, mikä näistä 10 ehdokaspaikasta valitaan;

Toisessa vaiheessa on määritettävä jakelusuhde varaston ja alueen välillä. Tällä hetkellä päätösmuuttujien määrä on jopa 200 (eli jakaako varasto i alueelle j).

△DALL·E:n luoma kuva

Matemaattisesti 2SP-ongelma ilmaistaan ​​yleensä seuraavasti:

Niiden joukossa Q(x,ξ) edustaa toisen vaiheen optimointiongelmaa ensimmäisen vaiheen päätöksen x ja skenaarion ξ perusteella, ja sen muoto on:

Varsinaisessa ratkaisussa N kohtausta otetaan yleensä näytteitä vastaavan Q-arvon laskemiseksi odotusten likimääräiseksi.

Ilmeisesti mitä suurempi N on, sitä uskottavampi likiarvo on. Kuitenkin skenaarioiden määrän kasvaessa ongelman koko laajenee nopeasti, mikä johtaa ratkaisevaan pidentymiseen.

Havainnollistetaan tätä varaston sijaintiongelmaa Jotta voimme tehdä parempia sijaintipäätöksiä, meidän on otettava huomioon epävarmat tekijät, kuten kysyntä, sää, ihmisvirta ja liikenne, ja kunkin tekijän muutokset vastaavat skenaariota.

Tämä tarkoittaa, että N erilaista skenaariota on otettava laajasti näytteitä, jotta todellista tilannetta voidaan simuloida mahdollisimman tarkasti. Tällä hetkellä päätösmuuttujien kokonaismäärä toisessa vaiheessa on jopa 200N, mikä tekee ratkaisuajasta erittäin pitkän.

Itse asiassa, kun N on 500, jopa edistyneimmällä kaupallisella ratkaisijalla Gurobia käytettäessä optimaalisen päätöksen tekeminen kestää vähintään 6 tuntia.

Perinteiset menetelmät käyttävät yleensä satunnaisotantaa tai klusterointitekniikoita valitakseen pienen määrän skenaarioita (kuten 10 tai 20) likimääräistä ratkaisua varten. Vaikka aika on lyhentynyt, tuloksena olevien päätösten laatu ei usein ole ihanteellinen.

Tämän perusteella johdetaan HGCN2SP-mallin suunnitteluidea - samalla kun vähennät näytteenottokohtausten määrää, saat mahdollisimman tarkat tulokset.

Graafisten konvoluutioverkkojen käyttäminen 2SP-ongelman ratkaisemiseen

Tutkimusryhmä ehdotti hierarkkiseen graafikonvoluutioverkkoon perustuvaa HGCN2SP-mallia kaksivaiheisen stokastisen ohjelmoinnin ongelman ratkaisemiseksi.

Erityisesti algoritmisuunnittelun suhteen ryhmä luonnehti 2SP-ongelmaa rakentamalla hierarkkisen kaavion, jossa alempaa käytettiin edustamaan kunkin kohtauksen ominaisuuksia, kun taas yläkaaviota käytettiin kuvaamaan kohtausten välistä suhdetta.

Sitten hierarkkista graafikonvoluutioverkkoa (HGCN) käytetään taustalla olevan kohtauksen aligraafin upotustietojen ja ylimmän tason kohtaustilan rakenteellisten tietojen louhimiseen kohtausesityksen poimimiseksi.

Tarkkailumekanismiin perustuvaa dekooderia käytetään valitsemaan kohtauksia järjestyksessä. Se ei voi vain löytää edustavia kohtauksia yksinkertaistaakseen ongelmaa, vaan myös parantaa alkuperäisen perustan valintaa ratkaistaessa ongelma simplex-menetelmällä optimoimalla niiden järjestyksen. parantaa merkittävästi ratkaisuaikaa.

△HGCN2SP-mallikehys

Tiimi yhdisti myös vahvistusoppimisen (RL) tutkiakseen kattavasti päätöksenteon laatua ja ratkaisuaikaa malliparametrien optimoimiseksi, mikä parantaa merkittävästi ongelmanratkaisun tehokkuutta ja laatua.

Vaikka yllä olevassa varaston sijaintiongelmassa HGCN2SP valitsi vain 10 skenaariota, ero sen päätöstulosten ja Gurobin ratkaisijan 6 tunnissa tekemän päätöksen välillä oli vain 1,7 % ja ratkaisuaika vain 15 sekuntia, mikä vastaa nopeutta. Parannus on 1440-kertainen, mikä kuvastaa täysin tämän menetelmän tehokkuutta.

Lisäksi Network Design Problem (NDP) -kokeessa HGCN2SP saavutti samanlaisia ​​päätöksentekovaikutuksia alle puolessa aikaisemmissa menetelmissä.

Erityisesti suurissa tapauksissa ja useissa skenaarioissa HGCN2SP ylläpitää edelleen vahvat yleistysominaisuudet.

HGCN2SP:n ehdotus tarjoaa uuden idean ja työkalun monimutkaisten 2SP-ongelmien ratkaisemiseen, ja sillä on laajat sovellusmahdollisuudet.

Tutkimusryhmä suunnittelee mallin edelleen optimointia, koulutuskulujen alentamista ja sen soveltamista käytännön ongelmiin.

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