Замечательная способность одноклеточного амебоидного организма к решению проблем и его механизм

Абстрактный

Правильный и быстрый выбор лучшего хода-это фундаментальный навык живых организмов, соответствующий решению вычислительной задачи. Одноклеточный плазмодий Physarum polycephalum ищет решение проблемы коммивояжера (TSP) путем изменения его формы, чтобы свести к минимуму риск подвергнуться воздействию неприятных световых стимулов. В наших предыдущих исследованиях мы сообщали о результатах решения TSP для восьми городов. В этом исследовании мы показываем, что время, затрачиваемое плазмодием на поиск достаточно высококачественного решения TSP, линейно растет по мере увеличения размера задачи с четырех до восьми. Интересно, что качество решения не ухудшается, несмотря на взрывное расширение пространства поиска. Формулируя вычислительную модель, мы показываем, что линейно-временное решение может быть достигнуто, если внутренняя динамика может выделять внутриклеточные ресурсы для роста терминалов плазмодия с постоянной скоростью, даже реагируя на стимулы. Эти результаты могут привести к разработке новых аналоговых компьютеров, позволяющих приближенно решать сложные задачи оптимизации в линейном времени.

1. Введение

Ожидается, что биологически инспирированные вычислительные устройства и архитектуры будут дополнять, а в некоторых случаях и превосходить традиционные технологии решения вычислительно сложных задач, благодаря своей способности принимать правильные решения в неопределенных средах [1,2] и снижать энергопотребление [3,4]. Плазмодий истинного слизевика Physarum polycephalum (рис.1a) был активно исследован с этой целью из-за его интригующих децентрализованных вычислительных возможностей. Деформируя свое аморфное тело, плазмодий ищет оптимальный маршрут среди источников пищи [5-9], формирует регулярные графики [10] и предвосхищает периодические события [11].

Рис. 1.

Вычислительная система на основе амебы. а) Амебоидный организм P. polycephalum помещается в покрытый Au 64-полосный чип, покоящийся на богатой питательными веществами агаровой пластине. Из-за своей привлекательности к питательному веществу и отвращения к металлу, plasmodium остает внутри обломока где агар подвергается действию. Для получения изображения передаваемого света с помощью видеокамеры организм и микросхема подсвечиваются снизу оранжевым поверхностным источником света, который не влияет на поведение организма. Записанные изображения обрабатываются цифровым способом с помощью ПК для обновления изображений в оттенках серого для стимуляции видимого света с помощью проектора (материал и методы). b) типичная временная эволюция участка ответвления в полосе, где красный и синий профили показывают, что ответвления росли и были изъяты соответственно из-за отсутствия и наличия световой стимуляции.

    Скачать figureOpen в новый tabDownload в PowerPoint

Считается, что эти вычислительные возможности происходят из автономной колебательной динамики плазмодия, в котором объем каждой части колеблется с периодом около 1 мин [12]. При размещении в многополосных чип звездчатые показано на рис. 1А, плазмодий растет ее ложноножками-как ветви, повторяя подачи и снятия его внутриклеточных ресурсов (протоплазмы) в каждом цикле колебаний (рис. 1Б). Хотя временной ряд движения роста ветви кажется зашумленным, он содержит временную корреляцию, сопоставимую с периодом колебаний, который хаотично колеблется [13,14]. Кроме того, колебательные движения удаленных ветвей пространственно коррелированы, так как они демонстрируют фазовые синхронизации, которые производят различные пространственно-временные паттерны бегущих фазовых волн [15,16].

Aono et al. ранее была разработана "вычислительная система на основе амеб" [13,14,17,18], которая использует динамику изменения формы плазмодия в звездчатом чипе для решения комбинаторных задач оптимизации путем введения уникального оптического управления с обратной связью, называемого "контролем возврата" (рис.1a). Плазмодий нормально растет во всех ветвях по мере того как внутриклеточный ресурс (вход) поставлен от тела, так, что они займут всю зону Майн и увеличат нутриент абсорбцию от плиты агара. Однако ветви отступают при воздействии видимого света (рис. 1b); это вызвано изъятие (выбытие) из внутриклеточных ресурсов из освещенной области из-за ответ photoavoidance. В то время как плазмодий меняет свою форму во время нашего эксперимента, его общий объем ресурса одноклеточного тела приблизительно сохраняется; уменьшение объема в одной ветви немедленно компенсируется увеличением объема в одной или нескольких ветвях. Kim et al. вычислительно показано, что этот закон сохранения объема позволяет ветвям быстро обмениваться информацией о стимулированном опыте пространственно коррелированным образом [19,20]. Управление отскока уточняет светлое стимулирование всех Майн на интервалах 6 s, в зависимости от изменения в форме plasmodium. Соответственно, плазмодий пытается деформироваться в оптимальную форму, максимизируя площадь тела для максимального поглощения питательных веществ, минимизируя риск подвергнуться воздействию неприятных световых стимулов.

В контроле bounceback световая стимуляция обновляется в соответствии с моделью, полученной из рекуррентной нейронной сети Хопфилда–танка–Амари [21] для поиска решения задачи коммивояжера (TSP) [14,17,18]. TSP является одной из наиболее изученных задач комбинаторной оптимизации и формулируется следующим образом: на карте n городов (рис.2) Найдите кратчайший тур для посещения каждого города Ровно один раз и возвращения в начальный город [22]. Существует (n-1)!/2 возможных экскурсии называют ‘возможно’. TSP-недетерминированная полиномиальная задача времени (NP)-трудная задача, и все известные верные методы получения точного оптимального решения (кратчайшего тура) среди всех возможных для "общего" или "неограниченного" экземпляра (т. е. E. Его междугородние расстояния не ограничены определением на Евклидовой плоскости, удовлетворяющей особым условиям, таким как неравенство треугольника), требуют времени, которое растет как экспоненциальная функция n [23-26]. Для быстрого получения качественного решения (удовлетворительный короткий тур) было предложено множество приближенных методов поиска, таких как алгоритм Лина–Кернигана [27], имитационный отжиг [28], нейронная сеть [21], генетический алгоритм [29], ДНК-вычисления [30] и оптимизация муравьиных колоний [1]. Эти приближенные методы поиска сталкиваются с компромиссом между временем, затраченным на поиск, и качеством решения.

Рис. 2.

Карты TSP, используемые в экспериментах. (A-e) "неограниченные" экземпляры четырех-, пяти-, шести-, семи - и восьми-городских TSP (левые панели). Мы разработали каждую карту таким образом, что ее междугородние расстояния производят унимодальное распределение длин возможных туров со средним значением приблизительно 150 (правые панели) и дают уникальный самый короткий (синий) и самый длинный тур длин 100 и 200, соответственно. Это естественный подход для объективной оценки зависимости поисковой способности от n.

    Скачать figureOpen в новый tabDownload в PowerPoint

Как показано на рисунке 3, N-city TSP может быть решена с помощью звездчатого чипа, имеющего n ? n полос, каждая из которых помечена Vk. Когда плазмодий достаточно удлиняет свою ветку в переулке ВК, это указывает на то, что город V посетил К-й продавец. Таким образом, чтобы представить один из туров, плазмодий должен вытянуть только соответствующие n ветвей. Например, форма плазмодия, показанная на рисунке 3e (справа), который имеет восемь ветвей, вытянутых в полосах C1, H2, D3, E4, G5, F6, A7 и B8, представляет собой тур TSP из восьми городов C ? H ? D ? E ? G ? F ? A ? B ? C. Обратный контроль разработан таким образом, что форма плазмодия, минимизирующая риск воздействия на него отвращающих световых стимулов, сопоставляется с кратчайшим туром TSP и становится наиболее комфортным условием для плазмодия [17].

Рис. 3.

Решения TSP, полученные вычислительной системой на основе амебы. (A-e) примеры четырех -, пяти -, шести -, семи-и восьми-городских туров TSP, полученных в экспериментах, где каждый тур окрашен в красный цвет на соответствующей карте на рисунке 2. Левые панели показывают переданные светлые изображения начальных состояний. Все ветви плазмодия (темно-оранжевые) собирались выйти на полосы (светло-оранжевые), приняв значение Xvk ? 0.0. Синие трапеции обозначают освещенные области. Для N < 8 64 ? N2 полосы чипа были отключены путем применения постоянной подсветки, о чем свидетельствуют синие трапеции на немаркированных полосах. Правые панели указывают на цифровые изображения удовлетворительных коротких туров, найденных удлиненными ветвями плазмодия, где каждый красный и желтый пиксель указывает на то, что толщина соответствующей области плазмодия увеличилась или уменьшилась соответственно.

    Скачать figureOpen в новый tabDownload в PowerPoint

Задача plasmodium найти самый короткий тур заключается в том, что его ветви не должны входить в часто освещаемые полосы и должны удлиняться в оптимальную комбинацию наименее часто освещаемых полос. Однако оптимальное сочетание не может быть найдено до тех пор, пока ветви всегда подчиняются принципу управления; если всегда ветви сжимаются при освещении и расширяются, когда они не освещены, плазмодий не избежит попадания в локальный минимум. Для лучшего изучения потенциального энергетического ландшафта и нахождения глобального минимума (кратчайшего тура) плазмодию необходимо с определенной малой вероятностью неправильно распределить ресурс по своим ветвям, а ветви должны нарушать принцип управления, так как длины туров могут быть сопоставлены только тогда, когда ветви работают вопреки их реакции фотодоступности [17]. То есть, в соответствующие сроки, места и частоты, ветви должны расширить, даже когда горит и сжимается, даже когда не горит. В нашем эксперименте, благодаря внутренней пространственно-временной колебательной динамике плазмодия, каждая ветвь могла соответствующим образом варьировать свои реакции на световые стимулы в зависимости от фазы колебаний; в восходящей фазе ветвь расширяется даже при освещении, в то время как в нисходящей фазе она сжимается, даже если не освещена. Следовательно, плазмодий нашли достаточно качественные решения с высокой вероятностью и займет более комфортное состояние для себя (рис. 3).

В контексте биологических вычислений наибольший интерес представляет вопрос о том, будет ли производительность поиска плазмодия, вычислительная способность быстро и правильно выбирать более удобное состояние, масштабироваться, когда окружающая его среда резко увеличивает его сложность. Таким образом, в этом исследовании, проводя эксперимент 1, который увеличивает размер задачи n с четырех до восьми, мы исследуем, как время, необходимое для плазмодия, чтобы найти возможное решение, растет в зависимости от n и оценить, как качество решения изменяется по мере взрывного расширения пространства поиска. Согласно результатам, приведенным в нашей предыдущей работе [18], было высказано предположение, что пространственные и временные корреляции в колебательной динамике плазмодия необходимы для повышения его вычислительной способности. Чтобы изучить эту гипотезу, в эксперименте 2 мы добавляем случайный шум при применении управления отскоком, так что пространственно-временные корреляции в колебательной динамике практически повреждены. Сравнение результатов экспериментов 1 и 2 показывает значимость пространственно-временных корреляций для повышения эффективности поиска. Затем, чтобы исследовать механизм поиска решений плазмодия, мы формулируем вычислительную игрушечную модель нашей вычислительной системы, основанной на амебе, которая связывает динамику изменения формы движений плазмодия и управления отскоком. Показано, что результаты моделирования, полученные на основе расчетной модели, хорошо воспроизводят экспериментальные результаты.
2. Материал и методы

Мы следовали протоколам, описанным в наших предыдущих работах [13,14,17,18].
2.1. Культура Physarum

В амебовидные плазмодии, плазмодии в истинной слизь плесень Physarum polycephalum (штамм: HU195x200, предоставляемых из Университета Хоккайдо), был сохранен с овсяные хлопья (чистые Овсяная мука, Ниппон производитель продуктов питания) на 1% агар пластины при 25°C в темноте. Богатый питательными веществами агар, используемый для эксперимента, включал: ультрачистую воду (Милли-Q) 100 мл, Бактоагар 1,5 г, глюкозу 0,36 г, ККЛ 0,074 г, солодовый экстракт 1 г и пептон 0,1333 г. Мы добавили раствор гемина (0,5 мл) к этим ингредиентам после стерилизации автоклава (120°C, 20 мин). Раствор гемина содержал Гемин (25 мг) и NaOH (1 г), разбавленный сверхчистой водой (50 мл). Поверхность пластины была покрыта пластиковым слоем (прозрачный лист, окрашенный в черный цвет) для предотвращения испарения влаги, что привело к уменьшению высоты стружки.
2.2. Изготовление звездчатого чипа

64 дорожки чипов звездчатые был изготовлен из ultrathick смолы фоторезиста (СУ-8 3050) с использованием метода фотолитографии. При изготовлении мы использовали разделительный слой (Omnicoat), съемник (XP 101A Developer) и проявитель (Su-8 Developer) (все эти реагенты являются продуктами корпорации MicroChem). Верхняя и нижняя поверхности чипа были покрыты Ау с помощью магнетрона sputterer (МСП-10, Shinkuu устройства Co., Лимитед.) Размеры чипа были следующими: толщина-приблизительно 0,1 мм; Диаметр-23,5 мм; диаметр центрального диска-12,5 мм; и каждая полоса-0,45 ? 3 мм.
2.3. Условия окружающей среды

Эксперименты проводились в камере темного термостата и увлажнителя воздуха (28 ± 0,5°С, относительная влажность 70 ±5%, THG102FB, Advantec Toyo Kaisha, Ltd). Для визуализации пропускаемого света образец помещали на поверхностный световод (MM80-1500, Suruga Seiki Co., Ltd) подключен к источнику света галогенной лампы (Techno Light KTX-100R, Kenko Co. ООО) оборудованы полосового фильтра (46159-Ф, Эдмунд оптики Инк.). Образец освещался светом (интенсивностью 2 мкВт мм-2) на длине волны 600 ± 10 нм, при котором не наблюдалось влияния на поведение плазмодия [31].
2.4. Условия освещения

Интенсивность белого света (монохром цвет R255 : G255 : B255) подсветка с проектором (W6000, компания BenQ; 2500 Лм, контрастностью 5000 : 1) был 352 мкВт мм?2, для которого мы измерили белым узором (р:г:Б=255 : 255 : 255) используя измеритель мощности (Мощность/счетчик энергии модель 1825-с, Ньюпорт). Внешний край звездчатого чипа (граница между чипом и областью агара) всегда освещался, чтобы предотвратить выход плазмодия за пределы края. Программные коды для обработки изображений в реальном времени для оптического управления были написаны на Visual C++ с использованием коммерческой студии разработчика (Visual Studio 2008 Express Edition, Microsoft). Замедленно видео изображения были захвачены с видео-камеры (программное обеспечение ArtCam-036MI, Artray; разрешение: 640 ? 480) с интервалом в 6 сек. Яркости (интенсивности) каждого пикселя в записи (предварительно бинаризован) отражение вертикальной толщиной соответствующей области плазмодий, как образ был записан с подсветкой свет из-под полупрозрачной пластинки агара.
2.5. Контроль возврата

Для каждого ВК в момент времени t, состояние XVk(Т) ? [0.0, 1.0] определяется как доля площади, занятой филиал плазмодия внутри соответствующую полосу (т. е. XVk = площадь филиал ВК делится на площадь всего региона Майна ВК) и получается в результате цифровой обработки изображений. При отсутствии световых стимулов каждая ветвь будет полностью вытянута, чтобы принять значение XVk ? 1.0.

Освещая полосу ВК, мы можем ингибировать долгосрочный рост ветви ВК, вследствие отрицательной фототаксиса плазмодия. Когда полоса Vk освещена с максимальной интенсивностью света, мы обозначаем это состояние как LVk = 1.0, тогда как LVk = 0.0 обозначает отсутствие освещения. Для больших XVk, долгосрочное уменшение в XVk может быть повышено освещением LVK > 0.5. Plasmodium освещается путем проецирования изображения в оттенках серого с помощью проектора ПК. Картина изображения, которая названа "картина освещения", определяет загоренные и non-illuminated майны которые покрашены белым и черным, соответственно.

Все световые стимулы лвк обновляются синхронно на основе следующей рекуррентной динамики нейронной сети [14,17,18], которая была получена из модели Хопфилда-танка-Амари [21].

LVk(t+?t)=1??1000,?0.5(?UlWVk,Ul??35,0.6(XUl(t))),

2.1

??,?=1/(1+exp(???(x??))),

2.2

WVk,Ul=??????????????????dist(V,U)0(if?V=U?and?k?l),(if?V?U?and?k=l),(if?V?U?and?|k?l|=1),(otherwise).

2.3

Сигмоидная функция ?35, 0.6 регулирует чувствительность управления, ?1000, -0.5 выполняет аналогичную шаговую функцию, а ингибирующая масса связи WVk, Ul (= WUl, Vk < 0) приводит к уменьшению XUl с увеличением XVk и наоборот. Параметры ? = 0,5, ? = 0,5 и ? накладывают на TSP соответственно следующие ограничения: (i) запрет на повторное посещение одного города, (ii) запрет на одновременное посещение нескольких городов и (iii) минимизация общего расстояния, где dist (V, U) - расстояние между городами V и U. Чтобы максимизировать эффект (iii), необходимо установить ? как можно больше, чтобы максимально усилить различия в междугородних расстояниях. Однако ? должно быть ниже верхнего предела ??, иначе некоторые ветви будут подсвечиваться даже при выборе возможных туров. Значение предела ??=??/(Р(З?,В'?)+Р(В'?,В"?)) получается численно, где ? = -0.5 и {с V?,В'?,В"?}=argmax{у,у',Х"}(р(у,у')+р(В',В")). Таким образом, ?, ? и ? могут быть автоматически определены для данной карты. Для восьми-карта города, мы устанавливаем ? для ???0.008197>?=0.0081. Аналогичным образом, для четырех-, пяти-, шести - и семи-карты города, мы ? = 0.00495, 0.00565, 0.0067 и 0.0076, соответственно.

3. Результаты
3.1. Эксперимент 1

Мы использовали идентичный чип с 64 полосами для всех n ? {4, 5, 6, 7, 8} зафиксировать физический размер обломока. Это произошло потому, что нас интересует проблема-размер масштабируемость системы, но не пространство-размер масштабируемости и поэтому время, необходимое для связи между ветвями плазмодий должны быть уравнены независимой от N. Потому что мы только нуждались N2 блоки для n-город ТСП, для N < 8, 64 ? Н2 полосы чипа были отключены путем применения постоянного свечения.

Мы начали эксперимент с помещения плазмодия внутрь чипа. Все начальные состояния должны быть установлены как XVk (0) ? 0.0. Таким образом, мы осветили все полосы, чтобы блокировать вторжение плазмодия, и подождали, пока агар-открытая область в Центральном диске чипа не будет полностью покрыта телом плазмодия.

После начала вычислений plasmodium расширялся и сжимал свои ответвления в включенных N2 полосах. Плазмодий проявлял сложные колебательные движения своих ветвей с пространственно-временными коррелированными флуктуациями и вызывал разнообразные картины освещения, так что он мог найти наименее часто освещаемые N ветвей, чтобы удлиниться исключительно в поиске тура. Считалось, что система нашла тур, когда картина освещения оставалась неизменной более 3 минут. Мы определили время поиска, необходимое для поиска тура, как время, прошедшее с момента первого освещения некоторых полос до момента, когда форма плазмодия впервые представляет тур.

Используя карты, показанные на рисунке 2, мы исследовали, как plasmodium управляет компромиссом качества времени, когда размер задачи n был увеличен с 4 до 8. Каждая из этих карт была построена случайным образом, чтобы иметь нормальное распределение длин туров со средним значением приблизительно 150, где самая короткая и самая длинная длины были установлены в 100 и 200, соответственно.

Для каждого N, мы провели более десяти испытаний (табл. 1), где для каждой пробы мы использовали различные плазмодия (Рисунок 3) с первоначального объема сравнял счет (средний вес 11.97 мг) не зависит от Н. Хотя число всех возможных туров выросла factorially от 3 до 2520 как функция N (рис. 4а), плазмодий успешно нашли подходящего решения с высокой вероятностью (рис. 4Б). Несмотря на стремительный рост числа кандидатов на решение, среднее время, необходимое для нахождения приемлемого решения, выросло почти только линейно (рис.4С).

Рис.4.

Статистика решения TSP в лабораторных экспериментах и вычислительном моделировании. a) Число всех возможных решений. b-d) результаты, полученные в ходе обычных (безшумных) лабораторных экспериментов, тогда как e,f) показывают результаты экспериментов с добавлением шума. b) степень успеха в поиске приемлемого решения после проведения многочисленных судебных разбирательств. c) среднее время, необходимое плазмодию для нахождения решения. Это оценивается как время, прошедшее с момента, когда некоторые полосы были впервые освещены до момента, когда состояния системы впервые представили решение; то же самое относится и к (ф). Планки погрешностей показывают стандартное отклонение. d) для каждого n средняя продолжительность найденных туров (красная) была разделена на среднюю возможную стоимость тура, рассчитанную на основе карты, как показано на рисунке 2 (Черная). e) степень успеха и f) качество найденного решения резко ухудшились, когда корреляции в пространственно-временной колебательной динамике были нарушены добавлением шума. g) среднее число итераций, необходимых для нахождения решения с помощью имитационной модели AmoebaTSP. (ч) средняя продолжительность туров найдены AmoebaTSP (синий) был разделен на среднее возможным экскурсионное длина значения (черный) оценивается как 100 н по строительству карте.

Если предполагалось, что плазмодий не обладает способностью "оптимизации" и случайно выбирает один из туров, то средняя длина туров, найденных плазмодием, должна приближаться к среднему значению (ок. 150) из всех возможных длин (n-1)!/2 туры. Однако, как показано на рисунке 4d, средняя длина тура, найденного плазмодием, оставалась значительно короче среднего значения для всех n, где каждая красная точка указывает на первое значение, деленное на последнее значение (черная точка). То есть качество найденного плазмодием решения не ухудшалось даже при увеличении размера задачи. Эти результаты позволяют предположить, что плазмодий обладает способностью искать достаточно качественное решение при низкой стоимости разведки, включая линейно подавленное время.
3.2. Эксперимент 2

Чтобы подорвать пространственно-временные корреляции в динамике поиска, мы добавили белый шум с плоской спектральной плотностью мощности ?Vk(t) ? [ ? d, d] к измеряемой величине XVk (t), где d, называемый "уровнем шума", определяет максимальную амплитуду шума. То есть в динамике управления возвратом аргумент XVk(t) был заменен на добавленный шум аргумент XVk(t) + ?Vk(t). Рис. 5а,б показаны исходный XVk эволюции(T) и шума-добавлено XVk эволюции(Т) + ?Vk(т), соответственно. Поскольку шум ?i генерируется без какой-либо корреляции, он повреждает временную корреляцию. Поскольку все ?i независимы, пространственная корреляция между ветвями также повреждена. Чтобы оценить влияние этих повреждений на производительность поиска, мы сосредоточились на примере восьми городов, показанном на рисунке 2e, и рассмотрели производительность двух уровней шума d = 0.03 и 0.05 (Таблица 1).

Рис. 5.

Типичные нормальные и шумовые данные временных рядов. а) временная эволюция дробной области ветви плазмодия XVk (t). (б) шум-добавлено эволюции XVk(Т) + ?Vk(T), где ?i(т) ? [?г, г] - белый шум с уровнем шума д = 0.05.

    Скачать figureOpen в новый tabDownload в PowerPoint

Протестировав два уровня шума, мы заметили, что снижение корреляций приводит к значительному снижению успешности поиска приемлемого решения (рис.4e) и снижению качества найденного решения (рис. 4f). Эти наблюдения подтверждают нашу гипотезу о том, что пространственные и временные корреляции в колебательной динамике плазмодия имеют важное значение для повышения эффективности его поиска.
3.3. Компьютерное моделирование

Чтобы понять механизм, используемый плазмодием для поиска возможного решения в линейном времени, мы сформулировали вычислительную игрушечную модель нашей вычислительной системы, основанной на амебе, под названием "амеба" (см. Приложение для его псевдо-кода и электронного дополнительного материала для его кода Fortran). В Амебацп внутриклеточные ресурсы, необходимые для роста ветвей плазмодия, поступают из дискообразной центральной области с постоянной скоростью ?in. Ресурсы поставлены постоянн даже пока некоторые из ветвей отступают от загоранных Майн. Для каждого n в диапазоне от 10 до 20 мы построили карту TSP, показанную на рисунке 6, и выполнили 500 пробных имитаций Монте-Карло, установив скорость притока ресурсов ?in и скорость оттока ?out равными 0,001. Как показано на рисунке 4g, среднее число итераций, необходимых AmoebaTSP для нахождения допустимого решения, растет почти линейно в зависимости от n. Качество решения, найденного AmoebaTSP, поддерживалось на разумном уровне независимо от n (рис.4h). Полученные результаты позволяют предположить, что линейно-временная поисковая способность плазмодия обусловлена его относительно простым механизмом отклика. А именно, даже без сложной нервной системы не только плазмодий, но и любые относительно простые физические системы, способные запасать поступающие ресурсы и равномерно и постоянно перераспределять их на терминалы, продемонстрировали бы способность находить достаточно качественное решение задач комбинаторной оптимизации в линейное время.

Рис. 6.

Гистограммы междугородних расстояний на картах TSP, используемые в компьютерном моделировании.

    Скачать figureOpen в новый tabDownload в PowerPoint

4. Обсуждение и заключение

Одна из наших будущих тем-изучить, может ли линейно-временная поисковая способность плазмодия быть подтверждена даже при использовании различных карт, в которых их длины тура не распределены нормально, как это можно увидеть в реальных приложениях. Неформально, случайно выбранные карты с нормально распределенными междугородними расстояниями, которые мы использовали в этом исследовании, могут быть "сложнее", чем карты с аномально распределенными расстояниями, которые отражают реальные ситуации. В результатах показано в [22], к решению президиума ТСП экземпляры с нормально распределенной тура длины, определенный на Евклидовой плоскости, как правило, требуют больше процессорного времени, чем на устранение эталоном случаях, указанных в TSPLIB [32], который включает в себя множество промышленных применений и географической точки множеств.

Причина, по которой в этом исследовании число городов n было ограничено восемью, заключалась в том, что мы не смогли изготовить чип с более чем 64 полосами из-за ограничения размера фотолитографического оборудования. Ширина каждой полосы чипа должна была составлять 0,45 мм; ниже этой ширины ветвь плазмодия не могла войти в полосу, а выше этой ширины мы не могли избежать роста более одной ветви в полосе. В природе наблюдается, что площадь плазмодия вырастает до нескольких квадратных метров в ширину. Поэтому, как только мы сможем изготовить более крупный чип, плазмодий будет решать более крупные экземпляры TSP с несколькими сотнями городов, так как количество его ветвей будет оцениваться в несколько десятков тысяч.

Колебательные движения удаленных ветвей плазмодия пространственно коррелированы, так как они демонстрируют фазовые синхронизации, порождающие различные пространственно-временные паттерны бегущих фазовых волн [14]. Экспериментально показано, что более короткий тур TSP может быть найден, когда плазмодий проявляет меньшее число бегущих фазовых волн, что указывает на высокую когерентность динамики и корреляцию по всему глобальному телу [18]. Хотя наша вычислительная модель, AmoebaTSP, в ее нынешнем виде не вводит никакой корреляции между флуктуациями ветвей, модификация динамики ветвей с привлечением пространственно-временных корреляций может еще больше повысить способность находить качественное решение.

Amoebatsp был сформулирован таким образом, что планируется достичь одного из возможных решений после числа итераций, которое растет линейно как функция n; для этой цели мы ввели ограничение, что постоянное количество ресурса должно быть распределено на неосвещенные ветви для каждой итерации путем тушения запаса отступивших ресурсов из освещенных ветвей. Подтверждено, что это ограничение обеспечивает линейный рост числа итераций. Однако, когда amoebatsp моделируется на традиционном цифровом компьютере, время процессора, необходимое для достижения возможного решения, растет нелинейно. Основная причина заключается в том, что весовая матрица (уравнение (2.3)) рекуррентной динамики нейронной сети для определения картины освещенности имеет n4 элемента, которые должны обрабатываться последовательно в ЦП. Поэтому АМЕБАТСП, имитируемый процессором, не будет использоваться для получения приближенного решения TSP в линейное практическое время для задачи размером более нескольких сотен городов.

Но, используя некоторые другие вычислительные платформы, физические процессы которых позволяют параллельно обновлять состояния всех ветвей Амебатсп при вычислении динамики нейронной сети и динамики распределения ресурсов с постоянной скоростью, мы ожидаем, что приближенное решение TSP станет доступным в линейное практическое время. Перспективным кандидатом такой вычислительной платформы является аналоговая электронная схема. Фактически, некоторые авторы исследовали использование электронных схем, вдохновленных амебой, для решения проблемы удовлетворения ограничений [33], проблемы выполнимости [34], аналого-цифрового преобразования [35] и нахождения маневра ходьбы многоногого робота [36]. Такой подход к использованию физического параллелизма может разработать новую аналоговую вычислительную парадигму, обеспечивающую мощные методы аппроксимации для решения сложных задач оптимизации, возникающих в широком спектре реальных приложений.
Приложение A

А. 1. AmoebaTSP

Под управлением bounceback, описанным уравнением (2.1), AmoebaTSP запасает отток ресурсов от удаленных ветвей и равномерно перераспределяет их на ветви в неосвещенных полосах. Мы приводим псевдокод Амебацп следующим образом, где скорость притока ресурса ?in и скорость оттока ?out являются постоянными параметрами.

t = 0 ;

FOR Vk = City11 to Citynn, Ul = City11 to Citynn

Determine coupling weight WVk,Ul according to Eq. (3) ;

FOR Vk = City11 to Citynn

Initialize XVk(0) = X0 such that ?35,0.6(X0) = 1/(n2 ? 1) ;

Initialize S(0) = 0 ;

WHILE t < tMax do

IF a configuration of all XVk(t) represents a consistent TSP tourTHEN RETURN the tour ;ELSEFOR Vk = City11 to CitynnDetermine ?Vk(t) as a randomly chosen real number in (?0.003, 0.003) ;Determine LVk(t?+?1)?=?1????1000,?0.5(?UlWVk, Ul?·??35,0.6(XUl(t)?+?Vk(t))) ;IF lane Vk is illuminated (LVk(t + 1) > 0.5)THEN Determine OVk(t+1)=2??out??20,0.6(XVk(t)+?Vk(t))

;

ELSE Determine OVk(t + 1) = 0 ;CALL StockRedistribution ;FOR Vk = City11 to CitynnIF lane Vk is not illuminated (LVk(t + 1) ? 0.5)THEN Update XVk(t + 1) = XVk(t) + IVk(t + 1) ;ELSE Update XVk(t + 1) = XVk(t) ? OVk(t + 1) ;

END WHILE

RETURN "Not Found" ;

SUBROUTINE: StockRedistribution

Determine Loff(t + 1) as the number of non-illuminated (LVk(t + 1) ? 0.5) lanes ;IF Loff(t + 1) = 0THEN Update S(t+1)=S(t)+?VkOVk(t+1)+?in

;

Determine IVk(t + 1) = 0 ;ELSE Update S(t + 1) = 0 ;Determine IVk(t+1)=(S(t)+?VkOVk(t+1)+?in)/Loff(t+1)

;

END SUBROUTINE

А. 2. Карты задач коммивояжера, используемые в компьютерном моделировании

Для оценки несмещенной зависимости поисковых возможностей Амебацпа от n для каждого n построена карта TSP с нормальным распределением длин туров и средней длиной туров около 100n. Для этой цели мы сначала подготовили набор нормально распределенных вещественных чисел со средним значением около 100 и дисперсией около 17. Затем для каждого n мы построили карту TSP, определив N (n ? 1)/2 междугородних расстояния, назначенных на карте, каждый из которых был случайным образом выбран из множества нормально распределенных вещественных чисел. Распределение междугородних расстояний построенных карт TSP показано на рисунке 6.
Доступность данных

Наборы данных, подкрепляющие эту статью, были загружены в качестве части электронных дополнительных материалов. Электронные дополнительные материалы и фильмы доступны в интернете по адресу https://doi.org/10.5281/zenodo.1481594 и https://doi.org/10.5281/zenodo.1481610 соответственно.
Вклад авторов

М. А., С.-Х. К. и М. Х. исследования; М. А. и Л. З., проведенные эксперименты; С.-П. К. и М. А. разработана модель; М. А. выполнено компьютерное моделирование; все авторы проанализировали данные; М. А. писал статьи; Все авторы рецензируемой рукописи. Корреспонденция должна быть адресована А. М. (aono@sfc.keio.ac.jp) или С.-Ж. К. (songju@sfc.keio.ac.jp).
Соперничающие интересы

У нас нет конкурирующих интересов.
Финансирование

Эта работа была частично поддержана поддержана KAKENHI (22700322), престо-разъем инновационные нано-электроники на основе междисциплинарного сотрудничества материалы, устройства и системы слоев грант нет. 13416898, JPMJPR1321 и реализации сквозных проектов развития технологий для развития Интернета вещей (IoT)’ по заказу новых энергетических и промышленных технологий развития Организации (недо).
Выражение благодарности

Мы благодарим т. Isoshima для сотрудничества в разработке оптических приборов, Ю. Хасегава за поддержку в обработке Physarum, М. Вакабаяши и Х. Хори за плодотворные дискуссии и RIKEN за предоставление услуг, необходимых для завершения этой работы.

Источник: royalsocietypublishing.org

Комментарии: