Революция в принятии решений с помощью Python и слизевиков: путешествие в мир естественных вычислений

Естественные вычисления – это область исследований, в которой используются естественные системы, такие как биологические организмы или процессы, для решения сложных вычислительных задач. Слизевики — одна из таких естественных систем, которая в последние годы привлекла внимание своей способностью решать проблемы оптимизации и принятия решений новым и эффективным способом.

Слизевики — это простые организмы, принадлежащие к группе протистов, обладающие уникальной способностью перемещаться и расти в направлении источников пищи таким образом, который кажется разумным, несмотря на отсутствие центральной нервной системы. Исследователи изучили поведение слизевиков и обнаружили, что они могут решать целый ряд задач: от поиска кратчайшего пути между двумя точками до оптимизации транспортных сетей и даже разработки эффективных компьютерных алгоритмов.

Алгоритм оптимизации Physarum — это вычислительная модель, которая имитирует поведение слизевиков для решения задач оптимизации. Он основан на наблюдении, что слизевики будут распространяться и расти к источникам пищи наиболее эффективным способом, следуя кратчайшему пути, чтобы соединить различные части своего тела. Алгоритм работает, представляя проблему в виде сети и моделируя рост и распространение агентов слизевиков по сети. Концентрация слизи в каждом узле указывает оптимальный путь между двумя точками в сети.

Хотя это пробудило ваше любопытство относительно того, как организм может прокладывать пути для решения человеческих проблем, я считаю, что здесь необходимо ухватить понимание естественных вычислений и того, как слизевики могут использоваться в качестве модельных организмов для решения сложных проблем. Я верю, что это само по себе создает основу для понимания основных принципов алгоритма оптимизации Physarum и его возможных применений.

Чтобы проиллюстрировать алгоритм оптимизации Physarum, в этом посте я буду использовать простой пример, такой как «поиск кратчайшего пути между двумя точками в сети». Как я упоминал ранее, мне нужно будет продемонстрировать, как работает алгоритм, распространяя/распространяя агенты плазмодия по всей сети, чтобы воспроизвести активность слизевика, и продемонстрировав, как концентрация слизи в каждом узле показывает кратчайший путь между двумя точками. Алгоритм работает, имитируя поведение слизевика, чтобы найти оптимальный путь между двумя точками.

Давайте посмотрим, как работает алгоритм оптимизации Physarum:

1. Мы начинаем с инициализации сети и размещения агентов плазмодия в каждом узле.

2. Затем мы моделируем поведение агентов, перемещая их по сети на основе набора правил, имитирующих поведение слизевиков. Например, агенты могут перемещаться в районы с высокой концентрацией питательных веществ (т. е. туда, где раньше перемещались другие агенты) и избегать районов с низкой концентрацией.

3. Когда агенты перемещаются по сети, они оставляют след из слизи, который указывает на концентрацию слизевиков в каждом узле.

4. Затем мы будем использовать концентрацию слизи в каждом узле, чтобы определить кратчайший путь между двумя узлами в сети. Путь с наибольшей концентрацией слизи представляет собой оптимальный путь между двумя узлами.

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

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

Одним из многих преимуществ алгоритма оптимизации Physarum является его способность эффективно решать логистические задачи, что приводит к снижению затрат для участников логистической деятельности. Исследовательская группа по оптимизации Physarum провела всесторонний обзор приложений для оптимизации Physarum polycephalum, типа слизевиков, которые использовались в качестве модельного организма для естественных вычислений и оптимизации (Chu et al., 2021). В своем обзоре, опубликованном в Swarm and Evolutionary Computation, авторы представляют обзор того, как Physarum polycephalum использовался для решения различных задач оптимизации, включая проблемы маршрутизации в коммуникационных сетях, проблемы кластеризации при интеллектуальном анализе данных и проблемы оптимизации в инженерии и дизайне. Также подчеркивается потенциал Physarum polycephalum для будущих приложений в таких областях, как робототехника и групповой интеллект. Этот обзор служит ценным ресурсом для исследователей и практиков, заинтересованных в использовании алгоритмов, основанных на слизевиках, для решения задач оптимизации и принятия решений.

Теперь давайте перейдем к нему, используя Python, чтобы проиллюстрировать действия слизевиков, перечисленные ранее.

Во-первых, мы импортируем зависимости для выполнения этого алгоритма оптимизации Physarum:

# Import dependencies
import numpy as np
import scipy.sparse as sparse
import networkx as nx
from queue import PriorityQueue

:::подсказка * NumPy для числовых вычислений, * SciPy Sparse для разреженного матричного представления, * NetworkX для создания графиков и * PriorityQueue для реализации алгоритма Дейкстры

:::

Далее мы инициализируем граф через networkx и добавим в него ребра:

# Initialize the network
G = nx.Graph()
G.add_edges_from([(0,1), (1,2), (2,3), (3,0)])

:::подсказка Это инициализирует неориентированный граф G и добавляет ребра между четырьмя узлами (0,1), (1,2), (2 ,3) и (3,0).

:::

Затем мы можем инициализировать такие параметры, как агенты плазмодия, скорость испарения слизи (это естественное поведение слизевиков), концентрация слизи в каждом узле и т. д.:

# Initialize the parameters
N = 100  # number of plasmodium agents. For test purposes, you can lower this number to 10 or thereabout
evaporation_rate = 0.1  # rate of slime evaporation
slime_concentration = sparse.csr_matrix((1, len(G.nodes)))  # concentration of slime at each node
plasmodium = np.zeros((len(G.nodes)))

:::подсказка Эти строки/блок инициализируют параметры, используемые в моделировании. N — количество агентов плазмодиев, которые будут смоделированы, evaporation_rate – скорость испарения слизи, а slime_concentration – разреженная матрица. который представляет концентрацию слизи в каждом узле.

:::

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

start_node = np.random.choice(list(G.nodes))
end_node = np.random.choice(list(G.nodes))

:::подсказка Это происходит из-за того, что агент плазмодия хочет распространяться между start_node и end_node. Другая возможность — сгенерировать статические start_node и end_node, однако это сделает наш код менее надежным. Так что лучше иметь случайность, просто чтобы увидеть красоту алгоритма, основанного на режиме слизи.

:::

Теперь приступим к размножению плазмодия:

queue = PriorityQueue()
queue.put((-plasmodium[start_node], start_node))
while not queue.empty():
    current_node = queue.get()[1]
    if current_node == end_node:
        break
    neighbors = list(G.neighbors(current_node))
    if len(neighbors) == 0:
        break
    for neighbor in neighbors:
        next_concentration = plasmodium[current_node] / len(neighbors)
        if next_concentration > slime_concentration[0, neighbor]:
            slime_concentration[0, neighbor] = next_concentration
            queue.put((-next_concentration, neighbor))
        plasmodium[neighbor] += plasmodium[current_node] / len(neighbors)

    # Update the slime concentration at each node
    slime_concentration *= (1 - evaporation_rate)

:::подсказка Этот блок распространяет агент плазмодия по графу, используя структуру данных очереди приоритетов. Очередь инициализируется начальным узлом и соответствующим ему значением плазмодия. В цикле while текущий узел извлекается из очереди, и если он совпадает с конечным узлом, цикл прерывается. Соседи текущего узла извлекаются, и если соседей нет, цикл прерывается. Для каждого соседа рассчитывается следующая концентрация слизи на основе текущей концентрации плазмодия и количества соседей. Если следующая концентрация больше, чем текущая концентрация шлама на соседнем узле, то концентрация шлама обновляется, и сосед добавляется в очередь со следующим значением концентрации. Концентрация плазмодия у соседа также обновляется на основе текущей концентрации и количества соседей.

В том же цикле while.. затем мы обновляем концентрацию слизи в каждом узле, умножая ее на скорость испарения.

:::

На данный момент мы проделали большую работу с распространением. Зная, как работают слизевики, вы наверняка никогда не сможете достичь временной сложности O(1) в этом алгоритме. Но вы можете сделать его лучше, оптимизировав алгоритмические сложности для этого алгоритма оптимизации Physarum (Slime). Возможно, вам придется посмотреть видео в ссылках, чтобы понять лиды со слизевиками и начать думать, как лучше вы перепишете этот код.

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

path = [start_node]
while path[-1] != end_node:
    neighbors = list(G.neighbors(path[-1]))
    next_node = neighbors[np.argmax(slime_concentration[0, neighbors])]
    path.append(next_node)

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

:::

Теперь мы можем вывести кратчайший путь с помощью функции print():

# Print the shortest path
print(path)

:::подсказка На выходе оператора печати в написанном нами коде для первой симуляции я получил [2, 1, 0]. Не забывайте, что в начальном и конечном узле есть случайность, поэтому мы всегда будем получать разные результаты, и это действительно характерно для слизевиков. Предположим, что начальным узлом является 0, а конечным узлом является 3. Список path инициализируется начальным узлом, и мы продолжаем добавлять соседа с наибольшей концентрацией слизи, пока не достигнем конечного узла.

В этом случае кратчайший путь между узлом 0 и узлом 3 в зависимости от концентрации шлама составляет [0, 1, 2, 3]. Однако фактический путь, найденный алгоритмом в этом конкретном запуске моделирования, оказался [2, 1, 0]. Это связано со случайностью, связанной с симуляцией — агент плазмодия начинает со случайного узла, и алгоритм выбирает случайные конечные узлы для каждого запуска.

:::

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

Этот алгоритм может быть полезен при моделировании движения агентов или частиц в сети и поиске наиболее эффективного пути между двумя точками на основе некоторых критериев. Вы можете найти полный репозиторий на моем github (https://github.com/AfolabiOlaoluwa/physarum_optimization_algorithm).

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

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

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

Ссылка:

1. Проводной. «Миколог объясняет, как слизевики могут решать лабиринты». Видеоклип онлайн. YouTube. YouTube, 5 апреля 2018 г. https://www.youtube.com/watch?v=7YWbY7kWesI. ли>

2. Биографический. (2016, 7 июня). Линза времени: Slime Lapse. https://www.biographic.com/lens-of-time-slime-lapse/. https://youtu.be/olCEGsKWQ3c.

3. Чу, Д., Ма, В., Ян, З., Ли, Дж., Дэн, Ю., & Чеонг, KH (2021). Всесторонний обзор приложений для оптимизации Physarum polycephalum. Swarm and Evolutionary Computation, 64, 100937. doi: 10.1016/j.swevo.2021.100937.

4. Л. Лю, Ю. Сонг, Х. Чжан, Х. Ма и А. В. Василакос, «Оптимизация физарума: основанный на биологии алгоритм решения задачи дерева Штейнера в сетях», в IEEE Transactions on Computers, vol. 64, нет. 3, стр. 818–832, март 2015 г., doi: 10.1109/TC.2013.229.

5. А. Хагберг, Д. Шульт, П. Сварт, Изучение структуры, динамики и функций сети с помощью NetworkX в Материалы 7-й конференции Python в науке (SciPy 2008), G. Varoquaux, T Vaught, J Millman (Eds.), стр. 11–15.