Nors Kalėdų Senelis gali turėti stebuklingas roges ir devynis išplėštus šiaurės elnius, kurie padėtų jam pristatyti dovanas, tokioms įmonėms kaip „FedEx“ efektyvaus atostogų paketų maršruto optimizavimo problema yra tokia sudėtinga, kad jos dažnai naudoja specializuotą programinę įrangą, kad rastų sprendimą.
Ši programinė įranga, vadinama mišrių sveikųjų skaičių linijinio programavimo (MILP) sprendėju, padalija didžiulę optimizavimo problemą į mažesnes dalis ir naudoja bendrus algoritmus, kad rastų geriausią sprendimą. Tačiau sprendėjui gali prireikti valandų ar net dienų, kol ras sprendimą.
Procesas yra toks sudėtingas, kad įmonė dažnai turi sustabdyti programinę įrangą, priimdama sprendimą, kuris nėra idealus, bet geriausias, kurį galima sukurti per tam tikrą laiką.
Mokslininkai iš MIT ir ETH Ciuricho panaudojo mašininį mokymąsi, kad paspartintų veiklą.
Jie nustatė pagrindinį tarpinį MILP sprendimų etapą, kuriame yra tiek daug galimų sprendimų, kurių išnarpliojimas užtrunka labai daug laiko, o tai lėtina visą procesą. Tyrėjai naudojo filtravimo techniką, kad supaprastintų šį veiksmą, tada naudojo mašininį mokymąsi, kad surastų optimalų konkrečios rūšies problemos sprendimą.
Jų duomenimis pagrįstas metodas leidžia įmonei naudoti savo duomenis, kad pritaikytų bendrosios paskirties MILP sprendimą pagal esamą problemą.
Ši nauja technika paspartino MILP sprendimus nuo 30 iki 70 procentų, nesumažėjus tikslumui. Šį metodą būtų galima panaudoti norint greičiau gauti optimalų sprendimą, o ypač sudėtingoms problemoms – geresnį sprendimą per trumpą laiką.
Šis metodas gali būti naudojamas visur, kur naudojami MILP sprendėjai, pavyzdžiui, pavėžėjimo tarnybos, elektros tinklų operatoriai, skiepų platintojai arba bet kuris subjektas, susiduriantis su sudėtinga išteklių paskirstymo problema.
„Kartais tokioje srityje kaip optimizavimas žmonės labai dažnai galvoja apie sprendimus kaip grynai mašininį mokymąsi arba grynai klasikinį. Esu tvirtai įsitikinęs, kad norime išnaudoti geriausius iš abiejų pasaulių, ir tai yra tikrai stiprus to hibridinio požiūrio pavyzdys“, – sako vyresnioji autorė Cathy Wu, Gilberto W. Winslow karjeros plėtros asistentė civilinės ir aplinkos inžinerijos srityje. CEE) ir Informacijos ir sprendimų sistemų laboratorijos (LIDS) bei Duomenų, sistemų ir visuomenės instituto (IDSS) narys.
Wu parašė darbą kartu su vienu iš pagrindinių autorių Sirui Li, IDSS absolventu, ir Wenbin Ouyang, Vidurio ir Rytų Europos magistrantūros studentu; taip pat Maxas Paulusas, ETH Ciuricho magistrantas. Tyrimas bus pristatytas Neuroninių informacijos apdorojimo sistemų konferencijoje.
Sunku išspręsti
MILP problemos turi eksponentinį galimų sprendimų skaičių. Pavyzdžiui, tarkime, kad keliaujantis pardavėjas nori rasti trumpiausią kelią aplankyti kelis miestus ir grįžti į savo kilmės miestą. Jei yra daug miestų, kuriuos būtų galima aplankyti bet kokia tvarka, galimų sprendimų skaičius gali būti didesnis nei atomų skaičius visatoje.
„Šios problemos vadinamos NP-hard, o tai reiškia, kad mažai tikėtina, kad yra veiksmingas algoritmas joms išspręsti. Kai problema yra pakankamai didelė, galime tikėtis pasiekti neoptimalių rezultatų“, – aiškina Wu.
MILP tirpiklis naudoja daugybę metodų ir praktinių gudrybių, kurios gali pasiekti pagrįstų sprendimų per trumpą laiką.
Įprastas sprendėjas naudoja „skaldyk ir valdyk“ metodą, pirmiausia padalydamas galimų sprendimų erdvę į mažesnes dalis, naudodamas techniką, vadinamą šakojimu. Tada sprendėjas naudoja techniką, vadinamą pjaustymu, kad sugriežtintų šias smulkesnes dalis, kad būtų galima greičiau jų ieškoti.
Pjovimas naudoja taisyklių rinkinį, kuris sutrumpina paieškos erdvę nepašalinant jokių įmanomų sprendimų. Šias taisykles generuoja kelios dešimtys algoritmų, vadinamų separatoriais, kurie buvo sukurti įvairioms MILP problemoms spręsti.
Wu ir jos komanda nustatė, kad idealaus naudotinų separatorių algoritmų derinio nustatymo procesas savaime yra problema, susijusi su eksponentiniu sprendimų skaičiumi.
„Separatorių valdymas yra pagrindinė kiekvieno sprendimo dalis, tačiau tai yra nepakankamai įvertintas problemos erdvės aspektas. Vienas iš šio darbo indėlių yra atskyriklio valdymo problemos nustatymas kaip mašininio mokymosi užduotis“, – sako ji.
Sprendimo erdvės mažinimas
Ji ir jos bendradarbiai sukūrė filtravimo mechanizmą, kuris sumažina šią separatoriaus paieškos erdvę nuo daugiau nei 130 000 galimų derinių iki maždaug 20 parinkčių. Šis filtravimo mechanizmas remiasi mažėjančios ribinės grąžos principu, kuris teigia, kad didžiausią naudą duos nedidelis algoritmų rinkinys, o papildomų algoritmų pridėjimas nepadės daug papildomo patobulinimo.
Tada jie naudoja mašininio mokymosi modelį, kad pasirinktų geriausią algoritmų derinį iš 20 likusių parinkčių.
Šis modelis yra apmokytas naudojant duomenų rinkinį, būdingą vartotojo optimizavimo problemai, todėl jis išmoksta pasirinkti algoritmus, kurie geriausiai atitiktų konkrečią vartotojo užduotį. Kadangi tokia įmonė kaip „FedEx“ jau daug kartų sprendė maršruto parinkimo problemas, naudojant tikrus duomenis, surinktus iš ankstesnės patirties, turėtų būti rasti geresni sprendimai, nei kiekvieną kartą pradedant nuo nulio.
Modelio kartotinis mokymosi procesas, žinomas kaip kontekstiniai banditai, sustiprinimo mokymosi forma, apima galimo sprendimo pasirinkimą, grįžtamąjį ryšį apie tai, koks jis buvo geras, ir tada vėl bandoma rasti geresnį sprendimą.
Šis duomenimis pagrįstas metodas paspartino MILP sprendimus nuo 30 iki 70 procentų, nesumažėjus tikslumui. Be to, pagreitis buvo panašus, kai jie jį pritaikė paprastesniam atvirojo kodo sprendimui ir galingesniam komerciniam sprendimui.
Ateityje Wu ir jos bendradarbiai nori pritaikyti šį metodą dar sudėtingesnėms MILP problemoms spręsti, kur pažymėtų duomenų rinkimas modeliui parengti gali būti ypač sudėtingas. Galbūt jie gali pritaikyti modelį mažesniam duomenų rinkiniui ir tada jį pakoreguoti, kad išspręstų daug didesnę optimizavimo problemą, sako ji. Tyrėjai taip pat domisi išmokto modelio interpretavimu, kad geriau suprastų skirtingų separatorių algoritmų efektyvumą.
Šį tyrimą iš dalies remia Mathworks, Nacionalinis mokslo fondas (NSF), MIT Amazon Science Hub ir MIT tyrimų paramos komitetas.
