В последние годы в нашей повседневной речи плотно закрепилось словосочетание «нейронные сети». Этот термин означает набор методов и программных решений из машинного обучения, дискретной математики и информатики. Но про что совсем часто забывают — он происходит из нейробиологии. Несмотря на очевидное название, нейросети — это не набор операторов IF и ELSE, а модели, вдохновлённые нервной системой живых организмов. Их эффективность в пору, когда у нас есть такие генеративные модели как GigaChat и Kandinsky, наглядно видна каждому. 

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

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

Миксомицеты

Возможно, вы слышали историю про то, как токийское метро «проектировала» плесень. История отчасти верна, разве что это была не плесень, а слизневик, он же микосомицет. Общего с грибами они кроме названия имеют достаточно мало, да и с названием есть нюанс. Полное название в английском языке — slime molds в американском диалекте или slime moulds в британском, что по-русски ближе к слизневикам, а не к плесени, под которой обычно подразумеваются конкретно грибы. 

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

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

Всё дело в том, что для нас — эукариот — в рамках одного вида характерна смена поколений, размножающихся половым и бесполым путём. Характерно это в том числе и для грибов, которых почему-то все записывают в бесполые на основание того, что они размножаются спорами. У большей части нашей эукариотической братии половое и бесполое поколение — это самостоятельные, зачастую кардинально различающиеся организмы. В зависимости от вида, половое поколение может быть активно двигающимся, а бесполое — неподвижным, либо наоборот. Общим является разве что принцип, по которому определяются типы спаривания: бесполое (гаметы) поколение обладает полным набором хромосом и образуется в результате слияния бесполого поколения, обладающего неполным набором хромосом. 

В случае нашего вида, «бесполое поколение» — это мы, а производимые нами половые клетки — «половое». Факт наличия у нашего «полового поколения» различий в генетике и морфологии также не является чем-то уникальным. Число типов спаривания у различных организмов может переваливать за сотни и даже тысячи. Например, у трёх видов грибов рода трихаптум в сумме было обнаружено 17 550 типов спаривания. От «пола» типы спаривания отличаются как по терминологии, так и по сути, упрощая которые в угоду научпопу можно докатиться и до утверждения, что дельфин — это рыба. 

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

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

Микроскопический метрополитен

После того, как мы узнали, кто такие слизевики, вернёмся к тому, как же они послужили на пользу Токийскому метро? Говоря кратко — никак. Тут мы снова сталкиваемся со «сломанным телефоном», порождённым упрощателями от мира научпопа. Миксомицет вида физарум многоголовый (Physarum polycephalum), использовался для анализа уже существующей инфраструктуры токийского метро.

Исследование было проведено в 2010 году командой из японских и британских учёных, методология его заключалась в следующем. Физарум поместили в среду, где было размещено 36 кусочков пищи, каждый из которых обозначал определённый район Токио. А для имитации таких препятствий строительству, как гористая местность или озёра, на некоторые участки светили светом различной интенсивности, потому что плазмодий физарума стремится избегать яркого света. У получившейся сети измерили длину пути между узлами, общую длину сети, её устойчивость к происшествиям, а также пропускную способность. В последнем случае с помощью формулы течения Пуазёйля оценивали объём проходящей протоплазмы по выростам плазмодиям.

Результаты исследования далеко не такие однозначные, как обычно преподносят в научпопе. К примеру по отказоустойчивости узлы реального метро оказывались изолированы только в 4 % случаев, для плазмодия же вероятность составляла 13-20 %. Но в целом параметры реального метро и сети маленького одноклеточного на квадрате 17х17 см оказались схожими. Разве что последнему потребовалось для планирования не много месяцев, а всего лишь один день. 

В 2018 году всё тот же физарум и вовсе «решил» задачу коммивояжёра для 8 городов. Казалось бы, ничего необычного. Но, в отличие от классических алгоритмов, сложность физарума росла не по экспоненте, а линейно.

Slime Mold Algorithm

Казалось бы, учёные не должны были пройти мимо такой эффективности. Но, на удивление, с 2010 года, поведение слизевика 10 лет никто не формализовал в алгоритмическом виде. Хотя это так и напрашивалось. Тот же муравьиный алгоритм всем знаком ещё с 1991 года. Наконец в 2020 маленького трудягу физарума запрягли для симуляции распределения тёмной материи во Вселенной. И в том же году вышла статья «Slime mould algorithm: A new method for stochastic optimization».

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

Algorithm 1 Pseudo-code of SMA
Initialize the parameters popsize, Max_iteration;
Initialize the positions of slime mould Xi (i = 1,2,...,n);
While (t ≤ Max_iteration)
    Calculate the fitness of all slime mould;
    update bestFitness, Xb;
    Calculate the W by Eq. (2.5);
    For each search portion
        update p, vb, vc;
        update positions by Eq. (2.7);
    End For
    t = t + 1;
End While
Return bestFitness, Xb;

В математическом же виде алгоритм выглядит следующим образом:

1. Поиск пищи:

где:

• vb — это параметр в диапазоне [-a, a];

• vc линейно стремится от 1 до 0;

• t — текущая итерация;

• Xb представляет собой точку, которая сильнее всего пахнет едой;

• X — это расположение физарума;

• XА и XB — две случайных точки относительно X;

• W — это вес физарума;

• p — считается по следующей формуле: 

где: 

• в i входит множество натуральных чисел;

• S(i) это приспособленность X;

• DF — максимальная приспособленность за все итерации.

a находится по следующей формуле:

где max_t — это максимум возможных итераций;

W же раскрывается так:

где:

• S(i) — это первая половина популяции;

• r —  случайное значение в интервале между [0,1];

• bF — оптимальная приспособленность, полученная за прошедшие итерации;

• SmellIndex — отсортированные по возрастанию значения приспособленности.

Поглощение пищи, дополненная формула с учётом смены местоположения физарума:

• LB и UB обозначают нижнюю и верхнюю границу диапазона;

• rand и r — случайные числа в диапазоне [0,1];

• z задаётся индивидуально.

Если от всего этого у вас уже повысилась температура центрального черепного процессора, то вы не одиноки. Поэтому перейдём к более знакомому — реализации алгоритма в коде.

import numpy as np
import random
import matplotlib.pyplot as plt
import seaborn as sns

def objective_function(x): return np.sum(x**2)  # Вычисление суммы квадратов элементов вектора

num_agents = 50  # Количество Физарумов
dimensions = 10  # Количество измерений в пространстве поиска
max_iters = 100  # Максимальное количество итераций
lb, ub = -5, 5  # Границы пространства поиска
w, vb, z = 0.9, 0, 0.1  # Весовой параметр, параметр колебаний, случайный параметр

positions = np.random.uniform(lb, ub, size=(num_agents, dimensions))  # Инициализация позиций Физарумов
fitness_history = []  # Список для хранения истории приспособленности всех Физарумов

for i in range(max_iters):  # Основной цикл алгоритма, итерации от 0 до max_iters-1
    fitness_value = np.array([objective_function(pos) for pos in positions])  # Расчет приспособленности каждого Физарума
    fitness_history.append(fitness_value)  # Добавление текущей приспособленности в историю
    positions = positions[np.argsort(fitness_value)]  # Сортировка Физарумов по убыванию приспособленности
    w *= np.exp(-i / max_iters)  # Адаптивное уменьшение весового параметра

    for j in range(num_agents):  # Цикл по всем Физарумам для обновления их позиций
        if random.random() < w:  # Вероятностная проверка на использование стратегии эксплуатации
            positions[j] += np.random.rand() * (positions[0] - positions[j])  # Движение к лучшей позиции
        else:  # Если условие не выполнено, выбирается стратегия исследования
            random_pos = positions[random.randint(0, num_agents - 1)]  # Выбор случайной позиции для исследования
            positions[j] += z * np.random.rand() * (random_pos - positions[j])  # Случайное перемещение
        positions[j] += vb * np.random.randn(dimensions)  # Добавление случайных колебаний
        positions[j] = np.clip(positions[j], lb, ub)  # Обеспечение, чтобы позиции не выходили за границы

best_pos = positions[0]  # Лучшая позиция после всех итераций
best_fitness = objective_function(best_pos)  # Лучшая приспособленность

# Визуализация изменения средней приспособленности
mean_fitness = np.mean(fitness_history, axis=1)
sns.lineplot(x=np.arange(max_iters), y=mean_fitness)
plt.title('История приспособленности')
plt.xlabel('Итерации')
plt.ylabel('Средняя приспособленность')
plt.show()

print("Лучшее конечное решение:", best_pos)
print("Лучшая конечная приспособленность:", best_fitness)

Для чего это всё?

Да, в общем-то, как и любой алгоритм из области дискретной математики — для всего. В первой статье от 2020 года, в которой формализован алгоритм, были приведены примеры его использования от топологии и материаловедения до нейросетей. Тут он, к примеру, использовался для анализа рентгенограмм у пациентов, больных COVID-19.

Однако метод ещё относительно новый и только набирающий популярность. IT хоть и развивается бурными темпами, когда дело касается написания очередного веб-фреймворка, однако в фундаментальном плане информатика развивается наравне с другими естественными науками. Так, за 2021 год, по теме SMA-алгоритма вышло всего лишь 76 статей.

Приходилось ли вам самим использовать где-то алгоритм SMA? Или же во время прочтения у вас появились идеи где бы он мог хорошо себя показать?