Фахівці з упаковки з Майнца: номер один у світі
Вчені Майнца побили світові рекорди за найкраще розташування круглих дисків - публікація в Physical Review E
Як завантажити машину, щоб усе помістилося? Як упакувати посилку, щоб вона була добре заповнена? Скільки посуду міститься в кухонній шафі? Коли справа доходить до упаковки, вчені Майнца неперевершені. Усі вони зрівняли або побили світові рекорди, встановлені на міжнародному конкурсі на найкраще рішення конкретної проблеми пакування.«Ми вже деякий час працюємо над міждисциплінарним проектом між теоретичною фізикою та інформатикою, щоб розробити найкращий можливий комп’ютерний алгоритм для задач пакування», — пояснює д-р. Йоганнес Йозеф Шнайдер з нещодавно заснованого центру вивчення комп’ютерних методів дослідження в природничих науках в Університеті Йоганна Гутенберга в Майнці. Коли вчені дізналися про змагання незадовго до його завершення, вони змогли встановити лише світовий рекорд, інакше результати деяких інших груп були трохи кращими. Керуючись прагненням перемогти найкращі світові групи, деякі з яких багато років працювали над такими проблемами, вони далі розвивали свої комп’ютерні алгоритми і тепер змогли побити світові рекорди, встановлені під час змагань, і в більшості випадків значно. Робота була опублікована у відомому журналі статистичної фізики Physical Review E.
Конкурс полягав у тому, щоб розташувати по колу круглі диски різного розміру, щоб вони займали якомога менше місця. Тому радіус великого кола, в яке упаковані менші диски, повинен бути якомога меншим. У конкурсі взяли участь 155 груп із 32 країн, які подали свої рішення. Шнайдер, проф. д-р. Ельмар Шьомер з Інституту комп’ютерних наук і аспірант Андре Мюллер знайшли на сьогоднішній день найкращі рішення. Для менших проблем з 24 дисками і менше вони були на одному рівні з найкращими рішеннями на сьогоднішній день, що говорить про те, що для цього не може бути кращого рішення. «Для цієї проблеми з круглими дисками різного розміру ми розробили найкращий у світі алгоритм пакування», — резюмує Шнайдер.
Проте вчені не лише розглядають такі наукові проблеми, а й переносять їхні алгоритми на практичне застосування. Наприклад, група досліджує, як найкраще виміряти об’єм багажника великого німецького виробника автомобілів. Відповідно до стандарту, встановленого Європейським Союзом, тетрапаки певного розміру повинні бути упаковані в даний багажник таким чином, щоб простір було максимально заповнено. «До цих пір дерев’яні блоки використовувалися, щоб спробувати вмістити якомога більше тетрапаків», – пояснює Шнайдер. У США, навпаки, набори валіз від супербагатих доводиться максимально оптимально упаковувати в багажник, тому інформація про те, скільки місця в багажнику, не зовсім збігається між німецькими та американськими. рекламні брошури. Виходячи з порівняння з результатами конкурсу, вчені тепер впевнені, що їхній алгоритм також може оптимально вирішити ці проблеми пакування багажників.
Але такі алгоритми оптимізації можна використовувати і для абсолютно різних питань. Наприклад, поїздки від молочного заводу до ферм можна оптимізувати таким чином, щоб відстані, які вантажівки проїжджають для збору молока, були якомога коротшими – залежно від порядку під’їзду до ферм. Іншим прикладом з автомобільної промисловості є остаточне складання транспортних засобів: за допомогою комп’ютера можна визначити, в якому порядку окремі збірні кузови повинні бути доставлені на конвеєр, щоб виробництво могло здійснюватися максимально рентабельно. якомога. На такі проблеми також проводяться конкурси, деякі з яких навіть організовують компанії. Будучи докторантом у Регенсбурзі, один Шнайдер посів четверте місце на конкурсі, проведеному баварським виробником автомобілів кілька років тому, залишивши далеко позаду компанії, які створені в області оптимізації та найняли цілі групи людей для конкурсу.
Вчені з Майнца знаходять найкращий метод вирішення, наближаючись до рішення, наближаючись до нього. Для цього на комп’ютері моделюються випадкові події за допомогою симуляції Монте-Карло – названий на честь району Монако зі знаменитим казино. «Це працює як у казино, де число дванадцять випадковим чином з’являється на столі в рулетку, а комп’ютер випадково генерує домовленість», — пояснює Шнайдер. У прикладі з круглими дисками комп’ютер потім переміщує один із дисків кудись і порівнює це нове рішення з попереднім. Ця зміна буде відкатана, якщо рівень деградації занадто великий, інакше нове рішення залишиться. «Таким чином ви змінюєте розташування круглих дисків крок за кроком, поки не отримаєте остаточний результат».
Вражає, що різні рішення, які майже так само хороші, як і найкраще, часто мають щось спільне. На думку Шнайдера, є структури, які є поширеними. Наприклад, у змаганні з круговими дисками найбільші круглі диски часто знаходяться близько один до одного у випадку хороших рішень. Спільне у хороших і найкращих рішень – це те, що вчені досліджують у своїй власній роботі, яка незабаром також буде опублікована в Physical Review E.
Університетом Йоханнеса Гутенберга нещодавно було створено акцент на комп’ютерних методах дослідження в природничих науках, щоб краще підтримати видатні позиції природничих наук у Майнці за допомогою потужної та інноваційної інформатики.
Оригінальний випуск:
Андре Мюллер, Йоганнес Дж. Шнайдер, Ельмар Шьомер Упакування багатодисперсної системи жорстких дисків у круговому середовищі Physical Review E, том 79, номер 021102, 2 лютого 2009 р.
Джерело: Майнц [ JGU ]
