Алгоритм Fly

редактировать

Содержание

1 История
2 Парижская эволюция
3 Устранение неоднозначности
- 3.1 Парижский подход и кооперативная коэволюция
- 3.2 Алгоритм Fly и оптимизация роя частиц
4 Применение алгоритма Fly
5 Пример: реконструкция томографии
6 Пример: Цифровое искусство
7 См. Также
8 Ссылки

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Синограмма

(Y) {\ displaystyle (Y)}

{\ displaystyle (Y)}

из

f {\ displaystyle f}

е

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

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

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

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

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

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

$f ^ = a r g m i n ⁡ | | Y - Y ^ | | 2 2 {\ displaystyle {\ hat {f}} = \ operatorname {arg \, min} || Y - {\ hat {Y}} || _ {2} ^ {2}}$ ${\ displaystyle {\ hat {f}} = \ operatorname {arg \, min} || Y - {\ hat {Y}} || _ {2} ^ {2}}$

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

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

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

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

алгоритме fly-algorithm isinput: количество мух (N), входные данные проекции (p ссылка) вывод: популяция мух (F), прогнозы, оцененные из F (p оценка), трехмерный объем, соответствующий вокселизации F (V F) постусловие: разница между p оценкой и p ссылкой минимальна. START 1. // Инициализация 2. // Устанавливаем положение N мух, т.е. создать начальное предположение 3. для каждой мухи i в популяции мух F до 4. F (i) x ← random (0, 1) 5. F (i) y ← random (0, 1) 6. F (i) z ← random (0, 1) 7. Добавить F (i) проекция в p оценка 8. 9. // Вычислить производительность совокупности (т.е. глобальную приспособленность) 10. G приспособленность (F) ← Метрики ошибки (p ссылка, p оценка) 11. 12. f kill ← Выбрать случайную муху F 13. 14. Удалить f Убить вклад с p оценочно 15. 16. // Вычисляем производительность популяции без f kill 17. G пригодность (F- {f kill }) ← Ошибка метрики (p ссылка, p оценка) 18. 19. // Сравниваем характеристики, т.е. вычисляем локальную приспособленность мухи 20. L fitness (f kill) ← G fitness (F- {f kill }) - G пригодность (F) 21. 22. Если локальная пригодность больше 0, // Выбор порога плохой мухи, которая может быть убит 23. затем перейти к шагу 26. // f kill - хорошая муха (производительность популяции лучше, когда включено f kill): мы не должны его убивать 24. else перейти к шагу 28. // f kill - плохая муха (производительность популяции хуже, если включено f kill): мы можем избавиться от него 25. 26. Восстановите вклад мухи, затем перейдите к шагу 12. 27. 28. Выберите генетический оператор 29. 30. Если генетический оператор - мутация, 31. затем перейти к шагу 34. 32. иначе перейти к шагу 50. 33. 34. f воспроизвести ← Выбрать случайный пролет F 35. 14. Удалить f воспроизвести вклад из p оценки 37. 38. // Рассчитываем производительность популяции без f воспроизводить 39. G пригодность (F- {f воспроизвести }) ← Ошибка метрики (p ссылка, p оценка) 40. 41. // Сравните характеристики, т.е. вычислите локальную приспособленность мухи 42. L пригодность (f воспроизвести) ← G пригодность (F- {f воспроизводить }) - G приспособленность (F) 43. 44. Восстановить вклад мухи 45. 46. Если локальная приспособленность ниже или равна 0, // Пороговый выбор хорошей мухи, способной воспроизвести 47. else перейти к шагу 34. // f kill - плохая муха: мы не должны позволять ей воспроизводить 48. затем перейти к шагу 53. // f kill - хорошая муха: мы можем позволить ему воспроизвести 49. 50. // Новая кровь / Иммиграция 51. Заменить f kill новой мухой со случайной позицией, перейдите к шагу 57. 52. 53. // Мутация 54. Скопируйте f воспроизведите в f kill 55. Слегка и случайным образом измените положение f kill 56. 57. Добавьте вклад новой мухи в популяцию 58. 59. Если остановить реконструкцию, 60. тогда перейти к шагу 63. 61. else перейти к шагу 10. 62. 63. // Извлечь раствор 64. V F ← вокселизация F 65. 66. return VFКОНЕЦ

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

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

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

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

$реконструкция = argmin ⁡ ∑ y = 0 x < W ∑ j = 0 j < H | i n p u t ( x, y) − P [ F ] ( x, y) | {\displaystyle reconstruction=\operatorname {arg\,min} {\overset {x$ ${\ 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) |}$

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

См. Также

Ссылки