Mainzin pakkausasiantuntijat: numero yksi maailmanlaajuisesti
Mainzin tiedemiehet asettivat maailmanennätykset pyöreiden levyjen parhaaksi järjestelyksi - julkaistu Physical Review E: ssä
Miten voin ladata auton, jotta kaikki mahtuu? Miten voin pakata paketin niin, että se on hyvin täytetty? Kuinka paljon ruokia menee keittiökaappiin? Pakkauksen yhteydessä Mainzin tiedemiehet ovat lyömättömiä. Maailman ennätykset, jotka on asetettu kansainväliseen kilpailuun parhaan ratkaisun löytämiseksi tietylle pakkausongelmalle, voitaisiin kaikki asettaa tai voittaa."Olemme työskennelleet jonkin aikaa teoreettisen fysiikan ja tietojenkäsittelytieteen välisessä tieteidenvälisessä projektissa parhaan mahdollisen tietokonealgoritmin kehittämiseksi pakkaamisongelmille", kertoo Dr. Johannes Josef Schneider vastikään perustetusta tieteellisistä tutkimusmenetelmistä luonnontieteissä Johannes Gutenbergin yliopistossa Mainzissa. Kun tutkijat saivat tietää kilpailusta vähän ennen sen päättymistä, he pystyivät asettamaan vain yhden maailmanennätyksen, muuten joidenkin muiden ryhmien tulokset olivat hieman parempia. Pyrkimyksenä voittaa maailman parhaat ryhmät, joista osa oli työskennellyt jo vuosien ajan, he kehittivät edelleen tietokonealgoritmejaan ja pystyivät alittamaan kilpailun aikana saavutetut maailmanennätykset ja suurimmaksi osaksi merkittävästi. Teos julkaistiin tunnetussa tilastofysiikan Physical Review E -lehdessä.
Kilpailussa pyrittiin järjestämään erikokoisia pyöreitä levyjä ympyrään niin, että ne vievät mahdollisimman vähän tilaa. Suuren ympyrän, johon pienemmät pyöreät levyt on pakattu, säteen tulisi siksi olla mahdollisimman pieni. Kilpailuun osallistui 155 ryhmää 32 maasta ja lähetti ratkaisunsa. Schneider, professori Dr., tohtori 24, enintään 50 erikokoisen pyöreän levyn ongelmiin Elmar Schömer Tietojenkäsittelytieteen instituutista ja jatko-opiskelija André Müller löysivät ylivoimaisesti parhaat ratkaisut. Pienempiin ongelmiin, joissa on 23 pyöreää levyä ja vähemmän, ne olivat tähän mennessä parhaiden ratkaisujen kanssa - mikä viittaa siihen, että vieläkään parempaa ratkaisua ei voi olla. "Siksi olemme kehittäneet tähän ongelmaan maailman parhaan pakkausalgoritmin erikokoisilla pyöreillä levyillä", Schneider tiivistää.
Tutkijat eivät kuitenkaan vain ota huomioon tällaisia tieteellisiä ongelmia, vaan myös siirtävät algoritminsa käytännön sovelluksiin. Esimerkiksi ryhmä tutkii, kuinka tavaratilan tilavuus voidaan parhaiten mitata suurelle saksalaiselle autovalmistajalle. Euroopan unionin määrittelemän standardin mukaan tietyn kokoiset Tetrapaksit on pakattava tiettyyn tavaratilaan, jotta tila olisi mahdollisimman täynnä. "Tähän mennessä olemme yrittäneet laittaa mahdollisimman monta Tetrapakia puupalikoilla", Schneider kertoo. Toisaalta Yhdysvalloissa superrikkaiden matkalaukkusetit on pakattava tavaratilaan mahdollisimman optimaalisesti, minkä vuoksi tiedot siitä, kuinka paljon tilaa tavaratilassa on, eivät täsmää saksalaisten ja amerikkalaisten mainosesitteiden kanssa. Kilpailutuloksiin tehdyn vertailun perusteella tutkijat voivat nyt olla varmoja siitä, että heidän algoritminsa voi myös ratkaista optimaalisesti nämä tavaratilan pakkausongelmat.
Tällaisia optimointialgoritmeja voidaan käyttää myös täysin erilaisiin kysymyksiin. Esimerkiksi maitotehtaan matkat maatiloille voidaan optimoida siten, että kuorma-autojen maidon keräämiseksi tekemät matkat ovat mahdollisimman lyhyet - riippuen maatilojen lähestymisjärjestyksestä. Toinen esimerkki autoteollisuudesta on ajoneuvojen lopullinen kokoonpano: Tietokoneen avulla voidaan määrittää, missä järjestyksessä yksittäiset esivalmistetut rungot on tuotava kokoonpanolinjalle, jotta tuotanto voidaan suorittaa mahdollisimman kustannustehokkaasti. Tällaisista ongelmista järjestetään myös kilpailuja, joista osan järjestävät jopa yritykset. Regensburgissa tohtorikoulutettavana Schneider saavutti yksin neljännen sijan kilpailussa, jonka eräs baijerilainen autonvalmistaja oli mainostanut muutama vuosi sitten, jättäen optimointiin perustetut yritykset ja työllistävät kokonaisia työntekijäryhmiä kilpailuun kaukana .
Mainzin tutkijat löytävät parhaan ratkaisumenetelmän lähestymällä ratkaisua. Tätä tarkoitusta varten satunnaisia tapahtumia simuloidaan tietokoneella Monte Carlon simulaatioilla - nimetty Monacon piirin mukaan kuuluisalla kasinolla. "Se on kuin kasinossa, jossa luku kaksitoista tapahtuu satunnaisesti rulettipöydällä, joten tietokone luo satunnaisen järjestelyn", Schneider selittää. Esimerkissä, jossa on pyöreät levyt, tietokone siirtää sitten yhden levyistä jonnekin ja vertaa tätä uutta ratkaisua edelliseen. Tämä muutos kumotaan, jos huononemisen laajuus on liian suuri, muuten uusi ratkaisu jää. "Tällä tavalla muutat pyöreiden levyjen asettelua askel askeleelta, kunnes lopputulos on käytettävissä."
On huomattavaa, että erilaisilla ratkaisuilla, jotka ovat melkein yhtä hyviä kuin paras ratkaisu, on usein jotain yhteistä. Schneiderin mukaan on olemassa rakenteita, joita löytyy usein. Esimerkiksi kiertolevykilpailussa hyvien ratkaisujen kanssa suurimmat pyöreät levyt ovat usein lähellä toisiaan. Tutkijat tutkivat, mitä hyvillä ratkaisuilla ja parhaalla ratkaisulla on tarkalleen omassa artikkelissaan, joka ilmestyy pian myös Physical Review E -lehdessä.
Johannes Gutenbergin yliopisto perusti äskettäin keskittymisen tietokoneavusteisiin luonnontieteiden tutkimusmenetelmiin tukeakseen paremmin Mainzin luonnontieteiden erinomaista asemaa tehokkaan ja innovatiivisen tietojenkäsittelytieteen avulla.
Alkuperäinen julkaisu:
André Müller, Johannes J.Schneider, Elmar Schömer Monilevyisen kiintolevyjärjestelmän pakkaaminen pyöreään ympäristöön Physical Review E, 79, numero 021102, 2. helmikuuta 2009
Lähde: Mainz [JGU]
