Веселое программирование с помощью Swarm Intelligence

См. Репозиторий GitHub для этого фрагмента

Возможно, вы были очарованы завораживающим потоком стаи птиц, летящих на фоне заходящего солнца. Сотни или даже тысячи птиц, летающих вместе, образуя бесконечные формы, как если бы они были одним целым, - невероятное зрелище.

Для многих это романтическая сцена, но сегодня не время для поэзии или романтики. Вместо этого я собираюсь реализовать нечто подобное в Python, сделав один маленький шаг к пониманию сложных систем. По словам физика, лауреата Нобелевской премии Ричарда П. Фейнмана:

Я не понимаю, что не могу создать.

Приступим к веселью!

Рой интеллект

Я не буду углубляться в интеллект роя, но постараюсь резюмировать его основные моменты. Проще говоря, классическое понимание природы с ограниченными взаимодействующими агентами - например, несколько частиц, оказывающих силы друг на друга, - не лучшая модель для сложной системы с чем-то большим, чем дюжиной частиц и сотнями взаимодействий. Классические системы имеют смысл, потому что они следуют так называемому «здравому смыслу». Классическая картина реальности основана на нескольких предположениях, из которых я назову наиболее актуальные для нас:

  1. Сложная система должна иметь сложные правила, управляющие ею.
  2. Сложной системе нужен управляющий (или создатель), чтобы создавать, поддерживать и управлять ею.

Эти правила просто не верны для реальных систем (которые сложны), и здесь история становится интересной!

Во-первых, сложные системы могут следовать очень простому и ограниченному набору правил. Но как эти системы проявляют сложное поведение? Ответ заключается в механизме, известном как возникновение.

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

Крейг Рейнольдс представил систему, известную как boids, которая может имитировать что-то похожее на поведение стаи птиц. Его модель искусственной жизни следовала трем простым правилам:

  • разделение: держитесь, чтобы не теснить местных товарищей по стае.
  • выравнивание: держитесь ближе к среднему заголовку местных сородичей.
  • сплоченность: держитесь, чтобы приблизиться к среднему положению (центру масс) местных сородичей.

С помощью только приведенных выше правил вы можете увидеть, как почти из ничего возникает возникающая сложность.

Реализация на Python

Поскольку мы хотим видеть результаты, мы должны использовать библиотеку, которая может позаботиться о графике. Я использую библиотеку p5 - библиотеку Python, основанную на исходной библиотеке js. Вы также можете использовать другие библиотеки. По этому поводу есть хороший Youtube-учебник, которому я постараюсь следовать и реализовать на Python.

Для начала нам нужно установить p5:

pip install p5

Затем нам нужно создать несколько «боидов» в качестве наших птиц. Мы будем называть их боидами, а не птицами, потому что птицы - лишь одна из возможных моделей - это могут быть рыбы или любой другой образец стайки. Для этого создаем класс:

Понятно, что нам нужна позиция для каждого boid, поэтому мы создаем другой файл с именем main.py и помещаем туда обработку графики. В p5 у нас есть две важные функции: setup, которая подготавливает холст и запускается только один раз в начале, и функция draw, которая выполняется в цикле и отвечает за изменения, которые создают финальную анимацию:

Если вы запустите приведенный выше код, вы должны увидеть пустой холст определенного размера и цвета. В draw мы каждый раз делаем одно и то же: рисуем холст определенным цветом rgb. Анимации пока нет.

Теперь мы хотим создать множество статических изображений на холсте. Я добавляю функцию show в класс выше:

функция stroke определяет цвет обводки, а функция circle создает круг в заданной позиции с заданным радиусом.

Теперь вернемся к main.py, чтобы создать 30 boid со случайными позициями:

Обратите внимание, что random.rand генерирует случайные числа. Теперь у нас есть что-то похожее на этот сюжет:

Теперь, если мы хотим, чтобы эти точки двигались, нам нужно определить их скорость и ускорение. Если вы помните физику в средней школе, вы знаете, что скорость и ускорение - векторные объекты. Хорошая новость в том, что вам не нужно определять класс Vector, потому что p5 уже реализовал его со всеми его методами и атрибутами:

И еще одна функция, обновляющая значения:

Итак, нам нужно добавить это в main.py:

Результатом этого шага будет множество boids, которые беспорядочно летают и исчезают:

Как нам хранить их в коробке? Мы должны сделать коробку всем миром, поэтому всякий раз, когда боид покидает коробку, он снова появляется на противоположной стороне. Для этого нам нужно добавить еще одну функцию в boids.py:

После добавления этой функции это результат:

Вы можете видеть, что бои начинаются медленно, а затем сходят с ума. Мы хотим более плавных движений. Для этого мы должны нормализовать векторы и создать для них max_speed предел. В следующем фрагменте кода мы устанавливаем max_speed равным 5:

Вот результат:

Выглядит хорошо! Теперь пришло время добавить поведения стае, вместо того, чтобы оставлять ее беспорядочно плавающей.

Из механики мы знаем, что то, что изменяет скорость, называется силой, и что сила равна ускорению, умноженному на массу. Здесь мы можем использовать ускорение вместо силы. С другой стороны, мы сказали, что каждый боид видит только местные боиды вокруг себя. Для выравнивания мы смотрим на локальные боиды, вычисляем их среднее направление (которое является частью вектора скорости) и следуем ему.

На рисунке выше зеленый boid - это текущий boid. направление текущего боида показано зеленым вектором, но среднее направление местных собратьев показано синей линией, идущей от него. Мы должны приложить силу от текущего направления к желаемому направлению. Этот вектор показан красной стрелкой - вычитание двух других векторов:

рулевое управление = avg_vec - собственная скорость

Алгоритм следующий:

Обратите внимание, что в цикле для всех boids мы ищем только boids на определенном расстоянии - это расстояние мы называем perception (здесь оно равно 100). Это имеет смысл, потому что в реальном мире птицы видят только местных товарищей по стае и управляют им, основываясь на местной информации. Мы также должны быть осторожны, если boid один, чтобы убедиться, что он ничего не делает (всего ›0). Затем мы нормализуем вектор, потому что нам просто нужно направление, и умножаем его на max_speed. Наконец, мы делаем вычитание.

Мы также создаем еще одну функцию, apply_behaviour,, которая отвечает за применение каждого правила по мере продвижения:

Затем мы добавляем его в функцию рисования в main.py:

С этого момента мы больше ничего не меняем в main.py. Результат:

Пока все выглядит отлично! Но у нас есть еще кое-что.

Сплоченность означает движение к центру масс местных собратьев. Мы делаем это, чтобы тела плотно прилегали друг к другу и не делились.

Мы должны попытаться направить текущий боид (зеленый) к центру масс локальных боидов, как показано зеленой точкой. Поскольку все боиды имеют одинаковую массу, центр масс равен их среднему положению. Найдя center_of_mass, мы вычитаем из него позицию. Другими словами:

vec_to_com = center_of_mass - собственное положение

рулевое управление = vec_to_com - собственная скорость

Функция будет похожа на выравнивание:

В приведенном выше коде мы выполняем нормализацию дважды - один раз для вектора к центру масс и второй раз для рулевого управления. Опять же, мы делаем это, потому что нам нужно направление, контроль величины должен выполняться другим параметром (здесь max_speed и max_force).

Теперь мы добавляем функцию сцепления к функцииapply_behaviour, но мы хотим видеть ее без правила выравнивания:

Вот что произойдет, если мы установим max_force на 1 и max_speed на 10:

Как видите, боиды стараются держаться близко друг к другу, что мы и ожидали.

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

Есть только одна тонкость: мы хотим, чтобы боид больше держался подальше от более близких, по сравнению с дальними в пределах их видимости (круг). Более близкие действуют с большей силой. Нам нужно использовать закон обратной длины:

Как видите, в основном цикле мы отслеживаем расстояния и делим вектор diff - направление выхода - на расстояние до этого конкретного товарища по стае. Если мы просто добавим это правило, мы получим:

Вы можете видеть желание каждого бойца держаться подальше от всех остальных - как будто они не любят общаться!

В этой статье я использовал силу и ускорение как взаимозаменяемые. Теперь мы можем применить все ускорение одновременно, используя закон силы, добавив:

Поэтому мы просто используем векторное добавление:

Это чистый результат применения всех этих правил:

Это то, что я искал! Следует упомянуть несколько вещей. Это не поведение реальных птиц в полной мере. Это искусственное создание жизни, которое пытается имитировать явление реального мира и демонстрирует, как реальные системы могут следовать простым правилам, но при этом проявлять сложное поведение. Боиды показывают нам, что сложность может возникнуть в процессе самоорганизации.

В этом виде программирования есть нечто иное: вы не определяете, какие закономерности проявляются. Конечно, вы можете настроить параметры, чтобы увидеть различные классы поведения, но в конечном итоге система дает уникальные шаблоны. Это взаимодействие правил и случайности.

Одна техническая деталь

Если вы запустите коды, вы поймете, что это очень медленно, когда количество boid превышает 50 (в зависимости от вашего оборудования). Причина, очевидно, в том, что код неэффективен и имеет сложность O (n²), что очень медленно с точки зрения алгоритмов информатики. Вы, вероятно, понимаете, что нет необходимости для каждого boid проверять все остальные boid, поэтому алгоритм можно оптимизировать, разделив пространство. Это похоже на проблему оптимизации алгоритма Knn. Вы можете найти некоторые лекарства здесь.

Я пробовал использовать библиотеку Ray для распараллеливания правил, но это не имело большого значения. Вы можете увидеть это в моем репозитории на GitHub. Если вы найдете какие-либо решения, которые значительно улучшают скорость, отправьте мне push-запрос!