Алгоритм полета

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

История [ править ]

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

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

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

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

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

Парижская эволюция [ править ]

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

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

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

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

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

Устранение неоднозначности [ править ]

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

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

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

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

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

Применение алгоритма Fly [ править ]

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

Пример: реконструкция томографии [ править ]

Реконструкция томографии - это обратная задача, которая часто некорректно ставится из-за отсутствия данных и / или шума. Ответ на обратную задачу не однозначен, и в случае экстремального уровня шума он может даже не существовать. Входные данные алгоритма восстановления могут быть представлены в виде преобразования Радона или синограммы данных для восстановления . неизвестно; известен. Сбор данных в томографии можно смоделировать как:${\ 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}}$

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

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

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

Алгоритм Муха-алгоритм является  ввод: количество мух ( N ), входные данные проекции ( ссылка p )  вывод: популяция мух ( F ), прогнозы, оцененные из F ( оценка p ) трехмерный объем, соответствующий вокселизации F ( V F )  Постусловие: разница между p оцененным и p эталонным минимальна.  НАЧНИТЕ  1. // Инициализация 2. // Установите положение N мух, т.е. создайте начальное предположение 3. для каждой мухи i  в популяции мух F  do 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 ) ← Ошибка метрика ( р ссылка , р оценки )11. 12. f kill ← Выбрать случайный налет F13. 14. Убрать вклад f kill из p оцениваемой15. 16. // Вычислить производительность населения без ф убийств
17. G фитнес ( F - { е убийства }) ← Error метрика ( р ссылки , р оценок )18. 19. // Сравните характеристики, т.е. вычислите локальную приспособленность мухи20. L фитнес ( f kill ) ← G фитнес ( F - { f kill }) - G фитнес ( F )21. 22. Если локальная пригодность больше 0, // пороговый выбор плохой мухи, которую можно убить23. затем переходите к шагу 26. // f kill - хорошая муха (производительность популяции лучше, если включено f kill ): мы не должны ее убивать
24. иначе переходите к шагу 28. // f kill - плохая муха (производительность популяции хуже при включении f kill ): мы можем избавиться от этого25. 26. Восстановите вклад мухи, затем перейдите к шагу 12.27. 28. Выберите генетического оператора.29. 30. Если генетический оператор - мутация,31. затем переходите к Шагу 34.32. иначе переходите к Шагу 50.33. 34. f воспроизвести ← Выбрать случайную муху F35. 14. Удалите вклад f воспроизводить из p оцениваемой37. 38. // Вычислить производительность населения без ф воспроизведи
39. G фитнес ( F - { е воспроизводимого }) ← Error метрика ( р ссылки , р оценок )40. 41. // Сравните характеристики, т. Е. Вычислите локальную приспособленность мухи42. L фитнес ( f воспроизводить ) ← G фитнес ( F - { f воспроизводить }) - G фитнес ( F )43. 44. Восстановить вклад мухи.45. 46. Если местная приспособленность ниже или равна 0, // Пороговая выборка хорошей мухи, способной воспроизводить47. иначе переходите к шагу 34. // f kill - плохая муха: мы не должны позволять ему воспроизводить
48. затем переходить к шагу 53. // f kill - хорошая муха: мы можем позволить ему воспроизвести49. 50. // New blood / Immigration
51. Замените f kill на новую муху со случайной позицией, переходите к шагу 57.52. 53. // Мутация
54. Копировать е воспроизвести Into ф убить
55. Слегка случайно альтер F убить «сек позиции56. 57. Добавьте вклад новой мухи в популяцию.58. 59. Если остановить реконструкцию,60. затем переходите к Шагу 63.61. иначе переходите к шагу 10.62. 63. // Экстракт раствора
64. V F ← вокселизация F65. 66. возврат  V F  КОНЕЦ

Пример: цифровое искусство [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]