Уведомления
Авторизуйтесь или зарегистрируйтесь, чтобы оценивать материалы, создавать записи и писать комментарии.
Авторизуясь, вы соглашаетесь с правилами пользования сайтом и даете согласие на обработку персональных данных.
Стадное чувство: как математики вдохновляются жизнью животных
Выражение «стадное чувство» нечасто используется в положительном смысле. Между тем в природе сплошь да рядом живые организмы, обладающие сравнительно низким индивидуальным интеллектом, объединяются в сообщества, которые ведут себя намного умнее и организованнее, чем каждый из их членов по отдельности. Это навело математиков и физиков конца XX века на мысль о применении роевого, то есть коллективного, интеллекта в нашей жизни для решения сложных задач.
Представьте себе доставщика пиццы, которому надо развезти заказы в разные точки города и затем вернуться в ресторан, откуда он выезжал. Как ему оптимально построить маршрут? Математики называют это задачей коммивояжера. Методы решения таких задач разделяют на точные и эвристические. Первые, их еще называют классическими, основаны на полном переборе всех возможных решений, что, в свою очередь, делает их неэффективными в случае большого количества переменных или точек, которые надо посетить: поиск ответа может занять много лет.
Получается, что большинство практических задач комбинаторной оптимизации (например, маршрутизация грузовиков) требуют особого подхода. Эвристические методы, к которым относятся и роевые алгоритмы, производят относительно ограниченный поиск решений и находят, возможно, не лучшее, но точно близкое к нему решение за разумное время «методом проб и ошибок». Лучшие же современные алгоритмы позволяют находить решения, на 95-99% приближенные к оптимальным.
В этом месте нам стоит на минуту задержаться и объяснить, каким образом мы рассчитываем эффективность таких решений.
- Во-первых, для большинства задач можно получить оценку сверху (или снизу, в зависимости от задачи) для глобального оптимума, при этом не имея возможности найти сам глобальный оптимум. Например, перед нами стоит задача оптимально погрузить изделия сложной формы и большой массы в вагон — теоретический оптимум достигается при использовании 100% грузоподъемности и вагона, но не нарушатся ли при этом другие ограничения, ответить невозможно, не решив задачу оптимизации. Если роевой алгоритм находит решение, позволяющее достичь загрузки на 95% грузоподъемности, это можно считать приближенной оценкой точности алгоритма.
- Во-вторых, иногда мы можем узнать оптимальное значение функции, но при этом практическую ценность имеет значение аргумента, при котором функция достигнет оптимума, а найти его можно, только решив задачу оптимизации. Например: есть сложный производственный процесс с большим количеством переделов. Мы знаем, что минимальные издержки на производство партии продукции могут составить 95 рублей, но не знаем, как надо настроить оборудование и в какой последовательности обрабатывать изделия, чтобы достичь такого уровня затрат. Роевой алгоритм предлагает настройки и последовательность операций, при которых издержки составят 100 рублей. Таким образом, оценочная точность алгоритма составит 95%.
А теперь представьте, что есть организмы в животном мире, которые, конечно же, не знают, что такое математика, но бессознательно ежедневно действуют оптимально и эффективно. Жизнь некоторых из этих животных вдохновила ученых на разработку алгоритмов. Такие алгоритмы называют биоинспирированными, так как они повторяют поведение животных или природных явлений. Так, например, отдельная птица или рыба и не подозревает, что стая, в которой она живет, ведет себя как бы разумно. Каждая особь (в алгоритме — частица) меняет свою позицию в пространстве, ориентируясь на свой опыт и на положение соседей. Это помогает птицам не сталкиваться друг с другом и лететь по оптимальному маршруту к нужному месту.
Такое системное поведение животных иллюстрирует понятие «автосинхронизации», или «закона пяти процентов», встречающееся, в том числе, и в мире людей. Если в каком-то обществе 5% участников одновременно совершают определенное действие, например начинают аплодировать артистам на сцене, то остальные люди автоматически начинают делать то же самое: сначала порознь, а потом и синхронно. Похожим образом работает и муравьиный алгоритм: отдельный муравей будет очень долго искать оптимальный путь от еды или строительных материалов до дома. Но группа муравьев, объединенных в колонию, быстро находит наилучшее решение. Секрет заключается в феромонах, которые выделяют эти насекомые. Чем путь туда-обратно быстрее, тем больше по нему пробежит муравьев и тем сильнее будет запах внешней секреции, который как бы сигнализирует: «Следуй за мной».
Однако к эвристическим алгоритмам относят не только роевые. Некоторые из них были вдохновлены строгой иерархией в животном мире, то есть вертикальными связями, а не горизонтальными, как в случае роя. Например, в пчелином мире есть разведчики, которые первыми отправляются на поиски нектара вокруг улья и передают координаты на базу. Чем больше предполагается найти на лужайке нужных цветов, тем дольше и ярче танец пчелы. Остальные жители улья, если информация их удовлетворяет, отправляются уже на сбор нектара. Разведчики же улетают искать другие поляны, причем радиус поиска с каждым заходом увеличивается. Поиск останавливается, когда пчелы находят наилучшую по всем параметрам локацию или оптимальное решение, если мы говорим о пчелином алгоритме.
Похожих предводителей-агентов содержит и алгоритм серых волков, разработанный в 2014 году. В дикой природе в стае существует довольно четкая иерархия и распределение обязанностей, которое непосредственно влияет на охотничье поведение хищников. Это и легло в основу алгоритма. При поиске добычи (оптимального решения) волками предполагается, что альфа-самец (лучший кандидат) и бета-волки имеют более четкое и правильное представление о том месте, где может находиться добыча. Соответственно, оставшаяся часть стаи корректирует свое поведение и локацию в зависимости от позиции лучших поисковых агентов.
Выбор нужного алгоритма зависит от поставленной задачи, и универсального рецепта здесь нет. Теорема о бесплатном обеде (NFL), например, утверждает: если алгоритм хорошо работает с определенным классом задач, то это обязательно балансируется снижением производительности на множестве оставшихся проблем. Более того, надо брать во внимание вычислительные затраты, доступность программного обеспечения и время, отведенное на поиск решения, чтобы правильно выбрать алгоритм. Но даже в этом случае алгоритм не гарантирует, что вы нашли самое лучшее решение, которое по-научному называют еще глобальным оптимумом. Всегда искать глобальный оптимум за разумное время сможет, в теории, только квантовый компьютер. Несмотря на то что небольшие квантовые процессоры уже существуют, они не могут пока справиться с большим объемом переменных, а все практические задачи, как назло, именно такие.
Если бы у нас уже был достаточно мощный квантовый компьютер, мы могли бы с его помощью быстро и точно решать гораздо более масштабные и сложные задачи оптимизации, но его пока нет. Однако в нашем распоряжении есть эвристические алгоритмы, которые успешно применяются на обычных машинах. Более того, даже в этом случае мы уже можем использовать явления из квантовой физики в природных алгоритмах. Так, например, квантово-вдохновленный алгоритм роя частиц использует эффект туннелирования для преодоления высоких барьеров.
Для наглядности представьте, что вы играете в такой боулинг, где кегли расставлены за холмом. При этом ваших сил не хватает, чтобы шар перекатился через вершину и оказался на той стороне. Выход в нашем мире только один — не играть в такой странный боулинг. В квантовом же мире умный в гору не идет, а туннелирует ее. Когда полной энергии не хватает, чтобы просто забраться на гору, частицы проходят ее насквозь. Это противоречит законам классической механики и показывает квантовую природу явления, которую и используют современные алгоритмы. Эффект ускоряет вычислительный процесс и помогает не застрять в локальном оптимуме при поиске глобального.
Квантово-вдохновленные (quantum-inspired) алгоритмы применяют в фармакологии, промышленности, логистике, финансовой сфере и в поиске материалов. То есть везде, где можно оптимизировать путь, расписание или какой-то процесс. Пока считается, что quantum-inspired алгоритмы дают максимальный экономический эффект. Однако нет предела совершенству, и, хотя коммивояжер, выходя из дома на работу, уже может не ломать голову над маршрутом (по крайней мере, на 95-99%), остается еще много нерешенных задач оптимизации из разных областей науки, бизнеса и повседневной жизни, которые только предстоит решить с помощью квантово-вдохновленных алгоритмов.
*Дмитрий Васильков, основатель и CEO QuSolve
Ученые из Австралии исследовали влияние сексуальной активности, а именно — самоудовлетворения и полового контакта с партнером — на объективные и субъективные параметры сна, в том числе на мотивацию поутру и готовность к новому дню.
В 2023 году руководство особой экономической зоны «Алабуга» представило план развития до 2048-го: он предполагает освоение космического пространства.
Стартап «Фистех», созданный на базе Сколтеха, впервые в России сконструировал и успешно протестировал фотонные интегральные схемы (ФИС) для работы с высокочастотными сигналами с шириной полосы до 22 гигагерца. Разработка нацелена на обеспечение российских производителей телекоммуникационными решениями на базе отечественных ФИС.
Ученые из Сколтеха исследовали разнообразие молекул, которые могут образовываться из атомов кислорода и углерода. Помимо широко известных углекислого и угарного газов, моделирование обнаружило две сотни экзотических, но относительно стабильных соединений этих двух элементов, многие из которых не были описаны ранее. Этот класс веществ представляет интерес для исследований космоса, аккумуляторных технологий, биохимии и — неожиданным образом — для разработки промышленной взрывчатки и ракетного топлива. Как оказалось, некоторые из открытых веществ при распаде будут высвобождать более 75 процентов взрывной энергии тротила.
Два ключевых события сыграли решающую роль в формировании генетического профиля современных европейских народов. Первое связано с приходом ранних фермеров из Анатолии примерно восемь тысяч лет назад, второе — масштабная миграция на запад носителей ямной степной культуры, начавшаяся пять тысяч лет назад. Однако ученые видят множество отличий от общей картины в разных регионах. В новой работе они проанализировали ДНК древних жителей самого северо-запада Европы и обнаружили более тесную связь с охотниками-собирателями, чем где бы то ни было.
Ученые из Австралии исследовали влияние сексуальной активности, а именно — самоудовлетворения и полового контакта с партнером — на объективные и субъективные параметры сна, в том числе на мотивацию поутру и готовность к новому дню.
В двойственных, или обратимых, изображениях зритель может увидеть разные объекты в зависимости от того, на каких деталях концентрируется его внимание. Среди известных примеров таких рисунков — иллюзия «кролик-утка», сочетающая двух животных, и обратимая ваза (или ваза Рубина), которая может казаться двумя силуэтами лиц, если сосредоточиться на фоне. В соцсетях и популярных СМИ часто публикуют подобные картинки, утверждая, что по тому, какое изображение человек видит в первую очередь, можно судить о его личностных чертах и особенностях мышления. Двое психологов из Великобритании недавно проверили, так ли это на самом деле.
Когда пара расстается, многие люди продолжают испытывать чувства к своим бывшим. Если разрыв произошел по инициативе другой стороны и отношения длились много лет, полностью «забыть» еще недавно близкого человека может быть непросто. Существует мнение, что и после расставания привязанность к экс-партнерам в какой-то мере сохраняется. Впрочем, согласно другой точке зрения, со временем эта эмоциональная связь ослабевает и утрачивается. Разобраться, как происходит на самом деле и сколько времени может потребоваться на полный эмоциональный разрыв с бывшими возлюбленными, взялись психологи из Иллинойсского университета в Урбане-Шампейне (США).
Масштабный анализ геномов показал, что вид Homo sapiens возник в результате смешения двух древних популяций. Они разделились полтора миллиона лет назад, а затем воссоединились до расселения по миру.
Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.
ПонятноИз-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.
ПонятноНаши фильтры обнаружили в ваших действиях признаки накрутки. Отдохните немного и вернитесь к нам позже.
ПонятноМы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.
ПонятноМы скоро прочитаем его и свяжемся с Вами по указанной почте. Спасибо за интерес к проекту.
Понятно
Комментарии