Алгоритм полета - Fly algorithm

История

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

Первой областью применения алгоритма полета было стереозрение. В то время как классические подходы с «приоритетом изображения» используют функции сопоставления из стереоизображений для построения трехмерной модели, алгоритм Fly непосредственно исследует трехмерное пространство и использует данные изображения для оценки достоверности трехмерных гипотез. Вариант, названный «Динамические мухи», определяет муху как шестерку ( x , y , z , x ' , y' , z ' ), включающую скорость мухи. Компоненты скорости не учитываются явно при расчете приспособленности, но используются при обновлении положений мух и подвергаются аналогичным генетическим операторам (мутация, кроссовер).

Применение мух для обхода препятствий в транспортных средствах использует тот факт, что популяция мух является согласованным со временем, квазинепрерывным представлением сцены для непосредственной генерации сигналов управления транспортным средством от мух. Использование алгоритма Fly не ограничивается строго стереоизображениями, поскольку могут быть добавлены другие датчики (например, акустические датчики приближения и т. Д.) В качестве дополнительных условий к оптимизируемой функции приспособленности. Информация об одометрии также может использоваться для ускорения обновления местоположения мух, и, наоборот, положения мух могут использоваться для предоставления информации о местоположении и картировании.

Еще одна область применения алгоритма Fly - реконструкция для эмиссионной томографии в ядерной медицине . Алгоритм Fly успешно применяется в однофотонной эмиссионной компьютерной томографии и позитронно-эмиссионной томографии . Здесь каждая муха считается излучателем фотонов, и ее пригодность основана на соответствии смоделированного освещения датчиков фактическому рисунку, наблюдаемому на датчиках. В этом приложении функция приспособленности была переопределена, чтобы использовать новую концепцию «предельной оценки». Здесь приспособленность одного человека рассчитывается как его (положительный или отрицательный) вклад в качество населения мира. Он основан на принципе перекрестной проверки с исключением по одному . Глобальная функция пригодности оценивает качество населения в целом; только тогда приспособленность особи (мухи) рассчитывается как разница между глобальными значениями приспособленности популяции с конкретной мухой и без нее , индивидуальная функция приспособленности которой должна быть оценена. В пригодности каждой мухи рассматривается "уровень уверенности". Он используется во время процесса вокселизации, чтобы настроить индивидуальный след мухи с помощью неявного моделирования (например, метабаллов ). Он дает более плавные и точные результаты.

Совсем недавно он использовался в цифровом искусстве для создания мозаичных изображений или аэрозольной краски. Примеры изображений можно найти на YouTube

Парижская эволюция

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

• Функция локальной пригодности для оценки результатов работы конкретного человека (обычно используется в процессе отбора).
• Глобальная фитнес-функция для оценки работоспособности всего населения. Максимизация (или минимизация в зависимости от рассматриваемой проблемы) этого глобального приспособления является целью населения.

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

Примеры приложений Parisian Evolution:

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

Устранение неоднозначности

Парижский подход vs кооперативная коэволюция

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

Алгоритм полета против оптимизации роя частиц

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

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

Применение алгоритма Fly

• Компьютерное стереозрение
• Избегание препятствий
• Одновременная локализация и отображение (SLAM)
• Реконструкция однофотонной эмиссионной компьютерной томографии (ОФЭКТ)
• Реконструкция с помощью позитронно-эмиссионной томографии (ПЭТ)
• Цифровое искусство

Пример: реконструкция томографии

Синограммы из , которая , как известно.${\ displaystyle (Y)}$${\ displaystyle f}$

Пример реконструкции фантома хот-рода с использованием алгоритма Fly.

Реконструкция томографии - это обратная задача, которая часто некорректно ставится из-за отсутствия данных и / или шума. Ответ на обратную задачу не однозначен, и в случае экстремального уровня шума он может даже не существовать. Входные данные алгоритма восстановления могут быть представлены в виде преобразования Радона или синограммы данных для восстановления . неизвестно; известен. Сбор данных в томографии можно смоделировать как: ${\ Displaystyle \ влево (Y \ вправо)}$${\ Displaystyle \ влево (е \ вправо)}$${\ displaystyle f}$${\ displaystyle Y}$

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

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

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

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

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

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

Итерационная коррекция при реконструкции томографии.

  (i) The reconstruction starts using an initial estimate of the image (generally a constant image),
  (ii) Projection data is computed from this image,
  (iii) The estimated projections are compared with the measured projections,
  (iv) Corrections are made to correct the estimated image, and
  (v) The algorithm iterates until convergence of the estimated and measured projection sets.

Псевдокод ниже описание шаг за шагом Мухи алгоритма для томографической реконструкции . Алгоритм следует парадигме установившегося состояния. В иллюстративных целях игнорируются продвинутые генетические операторы, такие как митоз, двойная мутация и т. Д. JavaScript реализации можно найти на Fly4PET .

algorithm fly-algorithm is
    input: number of flies (N), 
           input projection data (preference)
    
    output: the fly population (F), 
            the projections estimated from F (pestimated)
            the 3-D volume corresponding to the voxelisation of F (VF)
    
    postcondition: the difference between pestimated and preference is minimal.
    
    START
    
 1.   // Initialisation
 2.   // Set the position of the N flies, i.e. create initial guess
 3.   for each fly i in fly population F do
 4.       F(i)x ← random(0, 1)
 5.       F(i)y ← random(0, 1)
 6.       F(i)z ← random(0, 1)
 7.       Add F(i)'s projection in pestimated
 8.   
 9.   // Compute the population's performance (i.e. the global fitness)
10.   Gfitness(F) ← Errormetrics(preference, pestimated)
11.    
12.   fkill ← Select a random fly of F
13.    
14.   Remove fkill's contribution from pestimated
15.    
16.   // Compute the population's performance without fkill
17.   Gfitness(F-{fkill}) ← Errormetrics(preference, pestimated)
18.    
19.   // Compare the performances, i.e. compute the fly's local fitness
20.   Lfitness(fkill) ← Gfitness(F-{fkill}) - Gfitness(F)
21.    
22.   If the local fitness is greater than 0, // Thresholded-selection of a bad fly that can be killed
23.       then go to Step 26.   // fkill is a good fly (the population's performance is better when fkill is included): we should not kill it
24.       else go to Step 28.   // fkill is a bad fly (the population's performance is worse when fkill is included): we can get rid of it
25.    
26.   Restore the fly's contribution, then go to Step 12.
27.    
28.   Select a genetic operator
29.    
30.   If the genetic operator is mutation,
31.       then go to Step 34.
32.       else go to Step 50.
33.    
34.   freproduce ← Select a random fly of F
35.    
14.   Remove freproduce's contribution from pestimated
37.    
38.   // Compute the population's performance without freproduce
39.   Gfitness(F-{freproduce}) ← Errormetrics(preference, pestimated)
40.    
41.   // Compare the performances, i.e. compute the fly's local fitness
42.   Lfitness(freproduce) ← Gfitness(F-{freproduce}) - Gfitness(F)
43.    
44.   Restore the fly's contribution
45.    
46.   If the local fitness is lower than or equal to 0, // Thresholded-selection of a good fly that can reproduce
47.       else go to Step 34.   // fkill is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // fkill is a good fly: we can allow it to reproduce
49.    
50.   // New blood / Immigration
51.   Replace fkill by a new fly with a random position, go to Step 57.
52.    
53.   // Mutation
54.   Copy freproduce into fkill
55.   Slightly and randomly alter fkill's position
56.    
57.   Add the new fly's contribution to the population
58.    
59.   If stop the reconstruction,
60.       then go to Step 63.
61.       else go to Step 10.
62.    
63.   // Extract solution
64.   VF ← voxelisation of F
65.    
66.   return VF
   
   END

Пример: цифровое искусство.

Эволюционный поиск.

Изображение восстановлено после оптимизации с использованием набора полос в качестве шаблона для каждой плитки.

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

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

где - входное изображение, и - координаты пикселей по горизонтальной и вертикальной осям соответственно, и - ширина и высота изображения в количестве пикселей соответственно, - популяция мух, и - оператор проекции, который создает изображение из мух. Этот оператор проекции может принимать разные формы. В своей работе З. Али Абудд использует OpenGL для создания различных эффектов (например, мозаики или аэрозольной краски). Для ускорения оценки фитнес-функций также используется OpenCL . Алгоритм начинается с случайно генерируемой популяции (см. Строку 3 в алгоритме выше). затем оценивается с использованием глобальной пригодности для вычислений (см. Строку 10). это показатель погрешности, его необходимо минимизировать. ${\ displaystyle input}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle W}$${\ displaystyle H}$${\ displaystyle F}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle F}$${\ displaystyle F}$${\ Displaystyle G_ {фитнес} (F) = {\ overset {x <W} {\ underset {y = 0} {\ sum}}} {\ overset {j <H} {\ underset {j = 0} { \ sum}}} | input (x, y) -P [F] (x, y) |}$${\ displaystyle G_ {фитнес}}$

Смотрите также

• Математическая оптимизация
• Метаэвристический
• Алгоритм поиска
• Стохастическая оптимизация
• Эволюционные вычисления
• Эволюционный алгоритм
• Генетический алгоритм
• Мутация (генетический алгоритм)
• Кроссовер (генетический алгоритм)
• Отбор (генетический алгоритм)

использованная литература