Жива природа є найдосконалішим в нашому світі. За своїми науковими можливостями людство лише намагається грубо копіювати її тво...

Жива природа проти комп'ютера або про одну задачу проектування залізничної мережі

        Жива природа є найдосконалішим в нашому світі. За своїми науковими можливостями людство лише намагається грубо копіювати її творіння. Вчені не знають відповідь на питання рівності класів P і NP, це по суті питання - чи можливо створити алгоритм для знаходження оптимуму у задачах планування великої складності. Тобто, будь-яке рішення задачі комбінаторного типу великої розмірності є субоптимальним або наближеним. Досі не відомо чи існує оптимум.
       На даний час не існує комп’ютера, який міг би знайти оптимальне рішення для проектування складних транспортних мереж. Наприклад, спроектувати мережу залізниць, тобто вирішити комбінаторну задачу як з’єднати велику кількість міст, знайшовши компроміс між зменшенням капітальних вкладень на будівництво великої кількості залізничних ліній (ідеальний варіант з’єднання кожного міста зі всіма іншими) та зручністю подорожі для пасажирів (доступністю кожного міста - тривалість подорожі, комфортність). З математичної точки зору дана задача є NP- повною і на даний час у світі не існує алгоритму для точного її рішення. Можна лише знайти наближене рішення. А ось багатоядерний одноклітинний організм під назвою слизова цвіль Physarum polycephalum, який часто населяє дерев'яні залишки, що гниють, вирішує таку задачу без всякої математики дуже ефективно.
       Їжею організму Physarum polycephalum стають спори бактерій або самі бактерії. Зустрічаючи нові джерела їжі в міру свого росту, цей організм розростається і починає з'єднувати різні позиції, в яких знаходиться їжа, трубками-каналами, по яких відбувається ефективне транспортування поживних речовин. Така здатність до самоорганізації дуже зацікавила вчених Великобританії та Японії на чолі з Toshiyuki Nakagaki з Університету Хоккайдо (Hokkaido University) і вони спробували зрозуміти, чи можна використовувати здатність цього організму підбирати оптимальну кількість і протяжність каналів між декількома джерелами живлення для проектування залізничної транспортної системи між великою кількістю великих населених міст в околиці Токіо. Був проведений дослід, в якому взяли підкладку з агару (поживна підкладка - тверде середовище на основі агару для підтримки життєдіяльності мікроорганізмів) і розклали на ній шматочки вівсяних пластівців (ласощі для слизовика) так, щоб ті являли собою точну карту міст, що лежать навколо японської столиці. Слизовик помістили в центр - він грав роль самого Токіо. Через 26 годин організм з'єднав трубками всі смачні «міста», причому раціональним способом. Дослід повторили кілька разів, і в дуже багатьох випадках мапа, яку виростив слизовик, непогано збігалася з мапою залізничних ліній навколо Токіо. При цьому організм P.polycephalum зміг "запропонувати" і ряд альтернативних, але так само надзвичайно ефективних рішень для сполучення японських міст залізничними лініями.

        Результати моделювання узяті з документа "Rules for biologically-inspired adaptive network design".
       Подальші дослідження авторів були спрямовані на побудову математичної моделі поведінки даного організму (англ., model of the slime mould), що дозволило вирішувати такі задачі більш точно. Це може в подальшому дозволити зрозуміти як знайти оптимум, якщо він існує. На даний час дуже інтенсивно розвивається дослідження в області inspired моделювання – в основі лежать ідеї, запозичені в природі, а також базові постулати універсальності і фундаментальності, властиві самоорганізації природних систем.
       Детально про те, що написано вище, тут

       Так звана біо-математика є дуже цікавою, на даний час вже існують алгоритми мурашиних колоній, бджолиної сім’ї, моделювання переміщення бактерії E.Coli тощо.

       P.S. Багато експлуатаційних задач планування на залізниці відносяться до класу NP. Це означає, що рішити їх комп'ютерною моделлю поки неможливо, і тому їх часто відмовляються вирішувати, перекладаючи знаходження оптимального рішення на процеси самоорганізації. Розрахунок ПФП, задача розподілу порожніх вагонів на залізничній мережі відносяться до класу NP.


       Читати додатково:
       Планування складної системи. Чи хтось мусить її контролювати?
       Постіндустріальна економіка та вантажні перевезення на залізницях Японії




1 коментар: