Iepakošanas speciālisti no Maincas: pirmais pasaulē

Maincas zinātnieki pārspēja pasaules rekordus par labāko apļveida disku izvietojumu - Publikācija Physical Review E

Kā iekraut auto, lai viss ietilptu? Kā es varu iesaiņot paku, lai tā būtu pareizi aizpildīta? Cik trauku nonāk virtuves skapī? Runājot par iepakošanu, Maincas zinātnieki ir nepārspējami. Viņi visi spēja uzstādīt vai pārspēt pasaules rekordus, kas tika uzstādīti starptautiskā konkursā par labāko risinājumu īpašai iepakošanas problēmai.

"Mēs jau kādu laiku esam strādājuši starpdisciplinārā projektā starp teorētisko fiziku un datorzinātnēm, lai izstrādātu labāko iespējamo datora algoritmu iepakošanas problēmu risināšanai," skaidro Dr. Johanness Jozefs Šneiders no jaunizveidotās, pievēršoties datorizētām pētniecības metodēm dabaszinātnēs Johannesa Gūtenberga Universitātē Mainz. Kad zinātnieki uzzināja par sacensībām īsi pirms tā beigām, viņi varēja uzstādīt tikai vienu pasaules rekordu, pretējā gadījumā dažu citu grupu rezultāti bija nedaudz labāki. Ambīcijas pārspēt pasaules labākās grupas, no kurām dažas bija strādājušas pie šādām problēmām jau daudzus gadus, viņi turpināja pilnveidot savus datoralgoritmus un tagad spēja pārspēt sacensību laikā uzstādītos pasaules rekordus, turklāt lielākoties ievērojami. . Darbs tika publicēts slavenajā statistikas fizikas žurnālā Physical Review E.

Konkurss bija par dažāda izmēra apaļo disku izkārtošanu aplī tā, lai tie aizņemtu pēc iespējas mazāk vietas. Tāpēc lielā apļa rādiusam, kurā ir iepakoti mazākie diski, jābūt pēc iespējas mazākam. Konkursā piedalījās un savus risinājumus iesniedza 155 grupas no 32 valstīm. Par problēmām ar 24 līdz maksimāli 50 dažāda izmēra apļveida diskiem Schneider, Prof. Dr. Elmārs Šēmers no Datorzinātņu institūta un maģistrants Andrē Millers atrada līdz šim labākos risinājumus. Mazākām problēmām ar 23 un mazākiem diskiem tie bija līdzvērtīgi līdz šim labākajiem risinājumiem, kas liecina, ka nevar būt labāka risinājuma. "Šai problēmai ar dažāda izmēra apļveida diskiem mēs esam izstrādājuši pasaulē labāko iepakošanas algoritmu," rezumē Šneiders.

Tomēr zinātnieki ne tikai apsver šādas zinātniskas problēmas, bet arī nodod to algoritmus praktiskiem lietojumiem. Piemēram, grupa pēta, kā lielajam Vācijas autoražotājam vislabāk var izmērīt bagāžnieka tilpumu. Saskaņā ar Eiropas Savienības noteikto standartu noteikta izmēra Tetrapaks ir jāiepako dotajā bagāžniekā tā, lai vieta būtu maksimāli aizpildīta. "Līdz šim tika izmantoti koka bloki, lai mēģinātu uzņemt pēc iespējas vairāk tetrapaku," skaidro Šneiders. Savukārt ASV čemodānu komplekti no superbagātniekiem pēc iespējas optimālāk jāiepako bagāžniekā, tāpēc informācija par to, cik bagāžniekā ir vietas, ne visai sakrīt starp vācieti un amerikāni. reklāmas brošūras. Pamatojoties uz salīdzinājumu ar konkursa rezultātiem, zinātnieki tagad ir pārliecināti, ka viņu algoritms var arī optimāli atrisināt šīs bagāžnieka iepakošanas problēmas.

Bet šādus optimizācijas algoritmus var izmantot arī pavisam citiem jautājumiem. Piemēram, braucienus no piena rūpnīcas līdz fermām var optimizēt tā, lai attālumi, ko kravas automašīnas veic, lai savāktu pienu, būtu pēc iespējas īsāki – atkarībā no saimniecības piebraukšanas secības. Vēl viens piemērs no autobūves nozares ir transportlīdzekļu galīgā montāža: ar datora palīdzību var noteikt, kādā secībā atsevišķas saliekamās virsbūves jānogādā uz montāžas līnijas, lai ražošanu varētu veikt pēc iespējas izdevīgāk. pēc iespējas. Par šādām problēmām tiek rīkoti arī konkursi, no kuriem daļu pat organizē uzņēmumi. Būdams doktorants Rēgensburgā, Šneiders viens pats ieņēma ceturto vietu Bavārijas automobiļu ražotāja rīkotajā konkursā pirms dažiem gadiem, atstājot tālu aiz muguras optimizācijas jomā nodibinātus uzņēmumus, kuri nodarbina veselas cilvēku grupas.

Maincas zinātnieki atrod labāko risinājuma metodi, tuvojoties risinājumam, tuvojoties tam. Šim nolūkam datorā ar Montekarlo simulācijām tiek simulēti nejauši notikumi – nosaukts pēc Monako rajona ar slaveno kazino. "Tas darbojas kā kazino, kur pie ruletes galda nejauši parādās skaitlis divpadsmit, un dators nejauši ģenerē izkārtojumu," skaidro Šneiders. Piemērā ar apļveida diskiem dators pēc tam pārvieto vienu no diskiem kaut kur un salīdzina šo jauno risinājumu ar iepriekšējo. Šīs izmaiņas tiks atceltas, ja degradācijas līmenis būs pārāk liels, pretējā gadījumā jaunais risinājums paliks. "Tādā veidā jūs soli pa solim maināt apļveida disku izvietojumu, līdz iegūstat gala rezultātu."

Pārsteidzoši, ka dažādiem risinājumiem, kas ir gandrīz tikpat labi kā labākais risinājums, bieži ir kaut kas kopīgs. Saskaņā ar Šneidera teikto, ir struktūras, kas ir izplatītas. Piemēram, apļveida disku sacensībās lielākie apļveida diski labos risinājumos bieži atrodas cieši blakus. Labajiem risinājumiem un labākajiem risinājumiem kopīgs ir tas, ko zinātnieki pēta savā darbā, kas drīzumā tiks publicēts arī izdevumā Physical Review E.

Johanesa Gūtenberga universitāte nesen izveidoja galveno uzsvaru uz datorizētām pētniecības metodēm dabaszinātnēs, lai labāk atbalstītu izcilās dabaszinātņu pozīcijas Maincā ar spēcīgu un novatorisku datorzinātni.

Original publikācijas:

André Müller, Johannes J. Schneider, Elmar Schömer Cieto disku daudzšķautņainas sistēmas iepakošana cirkulārā vidē. Fiziskais apskats E, 79. sējums, numurs 021102, 2. gada 2009. februāris

Avots: Mainca [ JGU ]