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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

Реконструкция томографии - это обратная задача это часто некорректно из-за отсутствия данных и / или шума. Ответ на обратную задачу не однозначен, и в случае экстремального уровня шума он может даже не существовать. Входные данные алгоритма реконструкции могут быть заданы как Преобразование радона или синограмма данных для восстановления . неизвестно; известен. Сбор данных в томографии можно смоделировать как:

куда матрица системы или оператор проекции и соответствует некоторым Пуассоновский шум. В этом случае реконструкция соответствует обращению Преобразование радона:

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

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

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

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


алгоритм алгоритм полета является    Вход: количество мух (N), введите данные проекции (пссылка)        выход: популяция мух (F) прогнозы, оцененные из F (ппо оценкам) трехмерный объем, соответствующий вокселизации F (VF)        постусловие: разница между ппо оценкам и пссылка минимально. НАЧНИТЕ     1.   // Инициализация 2.   // Устанавливаем положение N летает, т.е. создает первоначальное предположение 3.   для каждого летать я в популяция мух F делать 4.       F(я)Икс ← случайный (0, 1) 5. F(я)y ← случайный (0, 1) 6. F(я)z ← random (0, 1) 7. Добавить F(я) в ппо оценкам 8.    9.   // Вычислить производительность популяции (т.е. глобальную пригодность)10.   граммфитнес(F) ← Ошибкаметрики(пссылка, ппо оценкам)11.    12.   жубийство ← Выбрать случайный полет F13. 14. Удалить жубийствовклад от ппо оценкам15.    16.   // Вычислить производительность популяции без fубийство17.   граммфитнес(F-{жубийство}) ← Ошибкаметрики(пссылка, ппо оценкам) 18. 19. // Сравните характеристики, т.е. вычислите локальную приспособленность мухи 20. Lфитнес(жубийство) ← граммфитнес(F-{жубийство}) - граммфитнес(F)21.    22.   Если локальная пригодность больше 0, // пороговый выбор плохой мухи, которую можно убить23. тогда переходите к Шагу 26. // fубийство хорошая муха (производительность популяции лучше, когда fубийство входит): не надо его убивать24.       еще переходите к Шагу 28. // fубийство плохая муха (производительность популяции хуже, когда fубийство входит в комплект): мы можем избавиться от этого25. 26. Восстановите вклад мухи, затем перейдите к шагу 12.27. 28. Выберите генетического оператора29. 30. Если генетический оператор - мутация, 31. тогда перейти к шагу 34.32. еще перейти к Шагу 50. 33. 34. жвоспроизводить ← Выберите случайный полет F35. 14. Удалить жвоспроизводитьвклад от ппо оценкам37.    38.   // Вычислить производительность популяции без fвоспроизводить39.   граммфитнес(F-{жвоспроизводить}) ← Ошибкаметрики(пссылка, ппо оценкам) 40. 41. // Сравните характеристики, т.е. вычислите локальную приспособленность мухи 42. Lфитнес(жвоспроизводить) ← граммфитнес(F-{жвоспроизводить}) - граммфитнес(F) 43. 44. Восстановить вклад мухи 45. 46. Если локальная приспособленность ниже или равна 0, // пороговый выбор хорошей мухи, способной к размножению47. еще перейти к Шагу 34. // fубийство плохая муха: мы не должны позволять ей воспроизводить48.       тогда перейдите к Шагу 53. // fубийство хорошая муха: мы можем позволить ей воспроизводить49.    50.   // Новая кровь / Иммиграция51. Заменить жубийство новой мухой со случайной позицией перейти к шагу 57. 52. 53. // Мутация54. Копировать жвоспроизводить в жубийство55. Слегка и хаотично переделать жубийствоПозиция56. 57. Добавьте вклад новой мухи в популяцию58. 59. Если Остановить реконструкцию, 60. тогда перейти к Шагу 63. 61. еще перейти к Шагу 10.62. 63. // Извлекаем раствор64.   VF ← вокселизация F65.    66.   возвращаться VF      КОНЕЦ

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

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

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

куда это входное изображение, и - координаты пикселей по горизонтальной и вертикальной оси соответственно, и ширина и высота изображения в пикселях соответственно, популяция мухи, и - это оператор проекции, который создает изображение из мух. Этот оператор проекции может принимать разные формы. В своей работе З. Али Абудд [16] использует OpenGL для создания различных эффектов (например, мозаики или аэрозольной краски). Для ускорения оценки фитнес-функций OpenCL тоже используется. Алгоритм начинается с популяции который генерируется случайным образом (см. Строку 3 в алгоритме выше). затем оценивается с использованием глобальной пригодности для вычисления (см. Строку 10). это показатель ошибок, его необходимо минимизировать.

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

Рекомендации

  1. ^ Колле, Пьер; Лоше, Жан (октябрь 2009 г.). «Искусственная эволюция и парижский подход: приложения в обработке сигналов и изображений». В Сиарри, Патрик (ред.). Оптимизация обработки сигналов и изображений. Wiley-ISTE. ISBN  9781848210448.
  2. ^ а б c Лоше, Жан (февраль 2000 г.). L'algorithme des mouches: индивидуальная стратегия эволюции, применяемая в стереовидении. Reconnaissance des Formes et Intelligence Artificielle (RFIA2000).
  3. ^ а б c Лоше, Жан (сентябрь 2000 г.). Стереоанализ с использованием индивидуальной стратегии эволюции. Труды 15-й Международной конференции по распознаванию образов, 2000 (ICPR’00). Барселона, Испания: IEEE. С. 908–911. Дои:10.1109 / ICPR.2000.905580. ISBN  0-7695-0750-6.
  4. ^ а б Лоше, Жан (июнь 2001 г.). «Использование индивидуальной стратегии развития стереозрения». Генетическое программирование и эволюционирующие машины. 2 (2): 101–109. Дои:10.1023 / А: 1011544128842. S2CID  8953837.
  5. ^ а б Boumaza, Amine; Лоше, Жан (апрель 2003 г.). «Слияние сенсоров мобильного робота с помощью мух». Конспект лекций по информатике. Европейская конференция по генетическому программированию (EuroGP 2003). 2611. Эссекс, Великобритания: Springer. С. 357–367. Дои:10.1007/3-540-36605-9_33. ISBN  978-3-540-00976-4.
  6. ^ а б Louchet, Жан; Гийон, Мод; Лесо, Мари-Жанна; Бумаза, Амин (март 2002 г.). "L'algorithme des mouches dynamic: guider un robot par évolution artificielle en temps réel" (PDF). В Латто, Клод (ред.). Apprentissage Automatique et Evolution Artificielle (На французском). Публикации Hermes Sciences. ISBN  978-2746203600.
  7. ^ а б Луше, Жан; Гийон, Мод; Лесо, Мари-Жанна; Бумаза, Амин (январь 2002 г.). «Dynamic Flies: новый инструмент распознавания образов, применяемый для обработки стереопоследовательностей» (PDF). Письма с распознаванием образов. 23 (1–3): 335–345. Дои:10.1016 / S0167-8655 (01) 00129-5.
  8. ^ а б Boumaza, Amine; Лоше, Жан (апрель 2001 г.). «Динамические мухи: использование эволюции в робототехнике в реальном времени». Конспект лекций по информатике. Искусственная эволюция в анализе изображений и обработке сигналов (EVOIASP2001). 2037. Комо, Италия: Springer. С. 288–297. Дои:10.1007/3-540-45365-2_30. ISBN  978-3-540-41920-4.
  9. ^ а б Louchet, Жан; Сапин, Эммануэль (2009). «Мухи открывают дверь, чтобы хлопнуть». Конспект лекций по информатике. Приложения эволюционных вычислений (EvoApplications 2009). 5484. Тюбинген, Германия: Springer. С. 385–394. Дои:10.1007/978-3-642-01129-0_43.
  10. ^ а б Буске, Орели; Луше, Жан-Мари; Роккизани, Жан (октябрь 2007 г.). «Полностью трехмерная томографическая эволюционная реконструкция в ядерной медицине» (PDF). Конспект лекций по информатике. Материалы 8-й международной конференции по искусственной эволюции (EA’07). 4926. Тур, Франция: Шпрингер, Гейдельберг. С. 231–242. Дои:10.1007/978-3-540-79305-2_20. ISBN  978-3-540-79304-5.
  11. ^ а б Видаль, Франк П .; Лазаро-Понт, Дельфина; Легупиль, Самуэль; Louchet, Жан; Латтон, Эвелин; Роккизани, Жан-Мари (октябрь 2009 г.). «Искусственная эволюция для 3D реконструкции ПЭТ» (PDF). Конспект лекций по информатике. Материалы 9-й международной конференции по искусственной эволюции (EA’09). 5975. Страсбург, Франция: Шпрингер, Гейдельберг. С. 37–48. Дои:10.1007/978-3-642-14156-0_4. ISBN  978-3-642-14155-3.
  12. ^ а б Видаль, Франк П .; Louchet, Жан; Латтон, Эвелин; Роккизани, Жан-Мари (октябрь – ноябрь 2009 г.). «Реконструкция ПЭТ с использованием стратегии совместной коэволюции в пространстве LOR». Отчет о конференции симпозиума по ядерной науке IEEE (NSS / MIC), 2009 г.. Конференция по медицинской визуализации (MIC). Орландо, Флорида: IEEE. С. 3363–3366. Дои:10.1109 / NSSMIC.2009.5401758.
  13. ^ а б Видаль, Франк П .; Луше, Жан; Роккизани, Жан-Мари; Луттон, Эвелин (апрель 2010 г.). «Новые генетические операторы в алгоритме Fly: приложение для реконструкции медицинских изображений с помощью ПЭТ» (PDF). Конспект лекций по информатике. Европейский семинар по эволюционным вычислениям в анализе изображений и обработке сигналов (EvoIASP’10). 6024. Стамбул, Турция: Спрингер, Гейдельберг. С. 292–301. Дои:10.1007/978-3-642-12239-2_30. ISBN  978-3-642-12238-5.
  14. ^ а б Видаль, Франк П .; Латтон, Эвелин; Луше, Жан; Роккизани, Жан-Мари (сентябрь 2010 г.). «Пороговый отбор, митоз и двойная мутация в кооперативной коэволюции: приложение к медицинской 3D-томографии» (PDF). Конспект лекций по информатике. Международная конференция по параллельному решению проблем с помощью натуры (PPSN'10). 6238. Краков, Польша: Шпрингер, Гейдельберг. С. 414–423. Дои:10.1007/978-3-642-15844-5_42.
  15. ^ а б Али Аббуд, Зайнаб; Lavauzelle, Julien; Латтон, Эвелин; Роккизани, Жан-Мари; Луше, Жан; Видаль, Франк П. (2017). «Вокселизация в алгоритме 3-D Fly для ПЭТ» (PDF). Рой и эволюционные вычисления. 36: 91–105. Дои:10.1016 / j.swevo.2017.04.001. ISSN  2210-6502.
  16. ^ а б c Али Аббуд, Зайнаб; Амлал, Осман; Видаль, Франк П. (апрель 2017 г.). «Эволюционное искусство с использованием алгоритма полета» (PDF). Конспект лекций по информатике. Приложения эволюционных вычислений (EvoApplications 2017). 10199. Амстердам, Нидерланды: Springer. С. 455–470. Дои:10.1007/978-3-319-55849-3_30.
  17. ^ Месехо, Пабло; Ибанез, Оскар; Фернандес-бланко, Энрике; Седрон, Франсиско; Пазос, Алехандро; Порто-Пазос, Ана (2015). «Искусственный нейрон - подход к обучению сетей Glia, основанный на кооперативной коэволюции» (PDF). Международный журнал нейронных систем. 25 (4): 1550012. Дои:10.1142 / S0129065715500124. HDL:2183/17502. PMID  25843127.
  18. ^ Кеннеди, Дж; Эберхарт, Р. (1995). Оптимизация роя частиц. Труды Международной конференции IEEE по нейронным сетям. IEEE. С. 1942–1948. Дои:10.1109 / ICNN.1995.488968.
  19. ^ Ши, Й; Эберхарт, Р. (1998). Модифицированный оптимизатор роя частиц. Труды Международной конференции IEEE по эволюционным вычислениям. IEEE. С. 69–73. Дои:10.1109 / ICEC.1998.699146.
  20. ^ Аббуд, Зайнаб Али; Видаль, Франк П. (2017). «Основные, двойные, адаптивные и направленные операторы мутации в алгоритме полета». Конспект лекций по информатике. 13-я Биеннальная международная конференция по искусственной эволюции (EA-2017). Париж, Франция. С. 106–119. ISBN  978-2-9539267-7-4.
  21. ^ Аббуд, Зайнаб Али; Видаль, Франк П. (октябрь 2017 г.). "Fly4Arts: эволюционное цифровое искусство с алгоритмом Fly". Искусство и наука. 17- 1 (1): 1–6. Дои:10.21494 / ISTE.OP.2017.0177.
  22. ^ Видаль, Франк П .; Латтон, Эвелин; Louchet, Жан; Роккизани, Жан-Мари (сентябрь 2010 г.). «Пороговый отбор, митоз и двойная мутация в кооперативной коэволюции: применение в медицинской 3D-томографии» (PDF). Конспект лекций по информатике. Параллельное решение проблем с натуры - PPSN XI. 6238. Краков, Польша: Springer Berlin / Heidelberg. С. 414–423. Дои:10.1007/978-3-642-15844-5_42. ISBN  978-3-642-15843-8.
  23. ^ Али Аббуд, Зайнаб; Видаль, Франк П. (октябрь 2017 г.). «Основные, двойные, адаптивные и направленные операторы мутации в алгоритме полета». Конспект лекций по информатике. 13-я Биеннальная международная конференция по искусственной эволюции. Париж, Франция: Springer-Verlag.