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

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

История

Алгоритм 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:

• Алгоритм 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 f}$, что известно.

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

Реконструкция томографии - это обратная задача это часто некорректно из-за отсутствия данных и / или шума. Ответ на обратную задачу не однозначен, и в случае экстремального уровня шума он может даже не существовать. Входные данные алгоритма реконструкции могут быть заданы как Преобразование радона или синограмма ${ Displaystyle влево (Y вправо)}$ данных для восстановления ${ Displaystyle влево (е вправо)}$. ${ 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}$, что сводит к минимуму метрики ошибок (здесь ℓ²-норма, но можно использовать и другие показатели ошибок) между ${ displaystyle Y}$ и ${ displaystyle { hat {Y}}}$. Обратите внимание, что срок регуляризации могут быть введены для предотвращения переоснащения и сглаживания шума при сохранении краев. Итерационные методы могут быть реализованы следующим образом:

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

  (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 лиц. Ее можно решить как задачу реконструкции следующим образом:

${ displaystyle reconame = operatorname {arg , min} { overset {x$

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

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

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

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