Мастер-алгоритм от Nervous System совершает прорыв в информатике

Оптимизация совместных поездок и проблемы информатики

Когда вы просите приложение для совместных поездок найти вам автомобиль, компьютеры компании приступают к работе. Они знают, что вы хотите быстро добраться до места назначения. Они знают, что вы не единственный пользователь, которому нужна поездка. И они знают, что водители хотят свести к минимуму время простоя, подхватив кого-то поблизости. По словам доцента лаборатории Колд-Спринг-Харбор Сакет Навлаха, работа компьютера заключается в том, чтобы соединять водителей с пассажирами таким образом, чтобы максимизировать всеобщее счастье. Специалисты по информатике называют это двудольным соответствием. С той же задачей сталкиваются системы, объединяющие доноров органов с кандидатами на трансплантацию, студентов-медиков с программами ординатуры и рекламодателей с рекламными местами. Таким образом, тема является предметом интенсивного изучения. «Это, наверное, одна из 10 самых известных проблем в информатике», – говорит Навлаха.

Схема на рисунке иллюстрирует, как двигательные нейроны и мышечные волокна организма связаны до (слева) и после (справа) обрезки связей. «Каждая капля соответствует моторному блоку, – объясняет Навлаха. «Малые двигательные единицы очень активны и задействуются в первую очередь во время сокращения мышц (потому что их нейроны имеют низкие пороги возбуждения) и обеспечивают небольшую силу. Крупные двигательные единицы менее активны и привлекаются последними (поскольку их нейроны имеют большие пороги срабатывания) и обеспечивают большее усилие».

Теперь найден способ сделать алгоритмы лучше, взяв за основу биологию. Навлаха обнаружил решение проблемы двустороннего согласования в проводке нервной системы. У взрослых животных каждое из мышечных волокон тела сопряжено ровно с одним нейроном, который контролирует его движение. Тем не менее, в раннем возрасте каждое волокно является мишенью для многих нейронов. Чтобы животное двигалось эффективно, необходимо обрезать лишние соединения. У нервной системы есть эффективное решение. Навлаха объясняет, что нейроны, изначально подключенные к одному и тому же мышечному волокну, конкурируют друг с другом, чтобы поддерживать свою функцию, используя нейротрансмиттеры в качестве «торговых» ресурсов. Нейроны, проигравшие этот биологический аукцион, могут взять свои нейротрансмиттеры и сделать ставку на другие волокна. Таким образом, каждый нейрон и волокно в конечном итоге оказываются у одного владельца.

Навлаха придумал способ реализации этой стратегии сопоставления за пределами нервной системы. «Это простой алгоритм», – говорит он. «Это всего лишь два уравнения. Одно из них описывает конкуренцию между нейронами, подключенными к одному и тому же волокну, а второе – перераспределение ресурсов».

Проверенный в сравнении с лучшими двудольными программами сопоставления, алгоритм, вдохновленный нейробиологией, работает очень хорошо. Он создает почти оптимальные пары и оставляет меньше неразрешенных связей. В повседневных приложениях это может означать сокращение времени ожидания для пассажиров и меньшее количество больниц без врачей.

Навлаха указывает на еще одно преимущество. Новый алгоритм сохраняет конфиденциальность. Большинство двусторонних систем сопоставления требуют, чтобы соответствующая информация передавалась на центральный сервер для обработки. Но во многих случаях – от онлайн-аукционов до сопоставления донорских органов – может быть предпочтительным распределенный подход. Таким образом имеется бесчисленное множество потенциальных применений нового алгоритма, и Навлаха надеется, что другие адаптируют его к своим собственным инструментам.

Источник: https://scitechdaily.com/nervous-systems-master-matchmaker-sparks-breakthrough-in-computer-science/