Алгоритм Fly

Алгоритм Fly относится к классу кооперативной коэволюции и реализует т. н. парижский подход^[1]. Алгоритм был впервые разработан в 1999 году в рамках применения эволюционных алгоритмов к задаче компьютерное стереозрение^[2][3]. В отличие от классических методов стереозрения, где выделяются примитивы на изображениях и сопоставляются для получения информации о глубине, алгоритм Fly осуществляет прямое исследование 3D-пространства сцены. Мушка определяется как 3D-точка, задаваемая координатами (x, y, z). После создания случайной популяции мушек в пространстве поиска (области видимости камер) эволюция популяции (по парадигме эволюционной стратегии) опирается на функцию пригодности, оценивающую вероятность того, что мушка находится на видимой поверхности объекта, исходя из согласованности её проекций на изображениях. Для этого функция учитывает оттенки серого, цвета и/или текстуры вычисленных проекций мушки.

Изначально алгоритм Fly применялся в стереозрении^[2][3][4][5]. В то время как классические методы «приоритет образа» используют сопоставление признаков по стереопаре для построения 3D-модели, алгоритм Fly работает непосредственно с пространством сцены, используя изображение для оценки состоятельности 3D-гипотез. Вариант «Динамические мушки» определяет мушку как 6-мерный вектор (x, y, z, x’, y’, z’), включая параметры скорости^[6][7]. Скорость мушек не входит явно в функцию пригодности, но применяется при обновлении позиций и подвергается тем же генетическим операторам (мутация, кроссовер).

Алгоритм также применяется для избегания препятствий на транспортных средствах^[8], используя свойство, что популяция мушек является непрерывно эволюционирующим представлением сцены и позволяет напрямую формировать управляющие сигналы транспортных средств. Применение алгоритма Fly не ограничивается исключительно стереоизображениями — к функции пригодности можно добавлять данные других сенсоров (например, акустические датчики приближения), а также использовать одометрическую информацию для ускорения обновления положения мушек или, наоборот, извлекать данные о локализации и построении карты по положениям мушек^[9].

Другим направлением применения алгоритма Fly стала реконструкция по эмиссионной томографии в ядерной медицине. Алгоритм успешно применялся для однофотонной эмиссионной компьютерной томографии^[10] и позитронно-эмиссионной томографии^[11][12]. В этих задачах каждая мушка рассматривается как источник фотонов, а её пригодность определяется степенью соответствия смоделированного сигнала измеренному сигналу на детекторах. Здесь была введена концепция «маргинальной оценки»: функция пригодности отдельной мушки определяется через её (положительный или отрицательный) вклад в глобальное качество популяции, что рассчитывается по принципу выключения одного элемента. Сначала рассчитывается глобальная функция пригодности для всей популяции, затем — разность этого значения с и без конкретной мушки^[13][14]. В работе^[15] пригодность интерпретируется как «уровень достоверности» и используется при вокселизации для уточнения вклада каждой мушки с помощью неявного моделирования (например, метаболлы), обеспечивая гладкие и точные результаты.

В последнее время алгоритм применяется в цифровом искусстве, например, для генерации мозаикоподобных изображений или эффектов «спрея»^[16].

В этой парадигме популяция особей рассматривается как «общество», где все они сотрудничают для достижения общей цели. Реализация включает стандартные генетические операторы (мутация, скрещивание, селекция). Главное отличие — в организации функции пригодности:

• Локальная функция пригодности — оценивает эффективность особи (используется при селекции);
• Глобальная функция пригодности — измеряет результативность всей популяции; её максимизация (или минимизация) — цель развития популяции.

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

Примеры применения парижской эволюции:

• Алгоритм Fly
• Текстовая аналитика
• Распознавание жестов
• Моделирование сложных взаимодействий в пищевой промышленности
• Реконструкция позитронно-эмиссионной томографии

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

• В кооперативной коэволюции задача делится на подзадачи (группы особей), которые решаются отдельно^[17].
• В парижской эволюции вся популяция работает над общей задачей, особи направляют друг друга к перспективным областям пространства поиска.

Метод роя частиц (англ. particle swarm optimisation, PSO) имеет сходство с кооперативной коэволюцией. PSO вдохновлён коллективным поведением стай птиц или рыб^[18][19] и изначально применялся для анимации в графике. В задачах оптимизации каждая частица следует своему траектории, подстраиваясь к лучшей особи роя. В алгоритме Fly мушки воссоздают пространственное представление сцены на основе сенсорных данных; прямого взаимодействия между ними или модели поведения нет.

Оба метода стартуют с множества случайных решений, постепенно корректируемых к глобальному оптимуму. Однако в Fly Algorithm решением задачи является вся популяция или её часть: мушки неявно сотрудничают для формирования ответа. В PSO — ответ даёт единственная частица с наилучшей пригодностью. Другое отличие — в Fly Algorithm основацию составляет построение геометрической структуры, а не поведенческая модель.

• Компьютерное стереозрение^[2][3][4][5]
• Избегание препятствий^[6][8][7]
• SLAM^[9]
• Реконструкция ОФЭКТ^[10]
• Реконструкция ПЭТ^{[11][12][13][14][15][20]}
• Цифровое искусство^[16][21]

Реконструкция по томографическим данным — это обратная задача, часто некорректная задача из-за шума или неполноты данных. Решение зачастую неоднозначно. Исходной информацией для алгоритма служат данные в виде преобразования Радона или синограммы ${\displaystyle \left(Y\right)}$ для объекта ${\displaystyle \left(f\right)}$. ${\displaystyle f}$ — неизвестно, ${\displaystyle Y}$ — известно.

Процесс сбора данных можно описать уравнением:

${\displaystyle Y=P[f]+\epsilon }$

где ${\displaystyle P}$ — матрица системы либо оператор проецирования, ${\displaystyle \epsilon }$ — пуассоновский шум. Тогда задача реконструкции соответствует обращению преобразования Радона:

${\displaystyle f=P^{-1}[Y]}$

Где ${\displaystyle P^{-1}}$ принимает во внимание шум, параметры сбора, и пр. Алгоритм Fly реализует подход итеративная реконструкция. Итерационные методы томографической реконструкции обычно формализуются так:

${\displaystyle {\hat {f}}=\operatorname {arg\,min} ||Y-{\hat {Y}}||_{2}^{2}}$

где ${\displaystyle {\hat {f}}}$ — оценка ${\displaystyle f}$, минимизирующая ошибку (здесь — евклидова норма между синограммами), возможен также учёт регуляризации для борьбы с переобучением и сглаживания шума при сохранении границ.

Общий алгоритм состоит из следующих этапов:

  (i) Начинаем с первичной оценки изображения (обычно константа),
  (ii) Вычисляем проекцию из этого изображения,
  (iii) Сравниваем вычисленную и измеренную проекции,
  (iv) Корректируем изображение для уменьшения расхождений,
  (v) Повторяем до сходимости.

Ниже приведён псевдокод для алгоритма Fly, реализующего реконструкцию по томографическим данным. Описан базовый вариант, игнорирующий сложные генетические операторы типа митоза, двойной мутации и т. д.^[14][20] Функционирующая JavaScript-реализация доступна на Fly4PET.

алгоритм algorithm-fly принимает
    входные данные: число мушек (N), 
           данные проекций (preference)

    выходные данные: популяция мушек (F), 
            оценки проекций на основании F (pestimated)
            трёхмерный массив (VF) после вокселизации F

    постусловие: отличие между pestimated и preference минимально.

    СТАРТ

 1.   // Инициализация: создаём стартовые позиции для N мушек
 2.   для каждой' мушки i из F
 3.       F(i)x ← random(0, 1)
 4.       F(i)y ← random(0, 1)
 5.       F(i)z ← random(0, 1)
 6.       Добавить проекцию F(i) в pestimated
 7.   
 8.   // Вычисление глобальной пригодности популяции
 9.   Gfitness(F) ← Errormetrics(preference, pestimated)
10.    
11.   fkill ← выбрать случайную мушку из F
12.    
13.   Удалить вклад fkill из pestimated
14.    
15.   // Глобальная пригодность без выбранной мушки
16.   Gfitness(F–{fkill}) ← Errormetrics(preference, pestimated)
17.    
18.   // Сравнить пригодности; вычислить локальную пригодность для мушки
19.   Lfitness(fkill) ← Gfitness(F–{fkill}) – Gfitness(F)
20.    
21.   если локальная пригодность > 0, // «хорошая» мушка
22.      то перейти к шагу 25.   // не убиваем её
23.      иначе перейти к шагу 27. // «плохая» мушка — её можно удалить
24.    
25.   Восстановить вклад мушки, далее — к шагу 11.
26.    
27.   Выбрать генетический оператор
28.    
29.   если оператор — мутация,
30.      то перейти к шагу 33.
31.      иначе перейти к шагу 49.
32.    
33.   freproduce ← выбрать случайную мушку из F
34.    
35.   Удалить вклад freproduce из pestimated
36.    
37.   // Глобальная пригодность без этой мушки
38.   Gfitness(F–{freproduce}) ← Errormetrics(preference, pestimated)
39.    
40.   // Сравнение и вычисление локальной пригодности
41.   Lfitness(freproduce) ← Gfitness(F–{freproduce}) – Gfitness(F)
42.    
43.   Восстановить вклад мушки
44.    
45.   если локальная пригодность ≤ 0, // «хорошая» мушка — допускается к размножению
46.      то перейти к шагу 52;
47.      иначе — к шагу 33.
48.    
49.   // Иммиграция — замена плохой мушки новой с случайной позицией
50.   Заменить fkill новой мушкой со случайным положением, затем — к шагу 56.
51.    
52.   // Мутация
53.   Скопировать freproduce в fkill
54.   Незначительно модифицировать положение fkill
55.    
56.   Добавить новую мушку в популяцию
57.    
58.   если остановка реконструкции,
59.      то к шагу 62;
60.      иначе к шагу 9.
61.    
62.   // Вокселизация
63.   VF ← вокселизация F
64.    
65.   вернуть VF

    КОНЕЦ

В данной задаче входное изображение аппроксимируется набором элементарных фрагментов (например, подобно древней мозаике). Каждый фрагмент характеризуется ориентацией (угол θ), тремя цветовыми компонентами (R, G, B), размерами (w, h) и позицией (x, y, z). При N фрагментах необходимо подобрать 9N действительных чисел. Для 5000 элементов их 45 000. При классическом эволюционном подходе каждый индивидуум содержит весь этот набор признаков, что требует огромных вычислительных затрат. В алгоритме Fly каждому индивидууму (мушке) соответствует отдельный фрагмент, а пригодность оценивается по вкладу в глобальный результат. Таким образом, требуется всего 9 параметров на одну мушку при N особях.

Задачу можно сформулировать как оптимизационную:

${\displaystyle reconstruction=\operatorname {arg\,min} {\overset {x<W}{\underset {x=0}{\sum }}}{\overset {y<H}{\underset {y=0}{\sum }}}|input(x,y)-P[F](x,y)|}$

где ${\displaystyle input}$ — исходное изображение; ${\displaystyle x}$, ${\displaystyle y}$ — координаты пикселя; ${\displaystyle W}$, ${\displaystyle H}$ — ширина и высота изображения; ${\displaystyle F}$ — популяция мушек; ${\displaystyle P}$ — оператор проекции (отображает популяцию в изображение). Параметр ${\displaystyle P}$ может реализовываться по-разному; напр., в работе Z. Ali Abbood используются OpenGL и OpenCL для ускорения вычислений^[16]. Алгоритм стартует с случайной популяции ${\displaystyle F}$, затем вычисляется глобальная пригодность ${\displaystyle G_{fitness}(F)={\overset {x<W}{\underset {x=0}{\sum }}}{\overset {y<H}{\underset {y=0}{\sum }}}|input(x,y)-P[F](x,y)|}$, минимизируемая в процессе оптимизации.