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

История

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

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

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

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

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

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

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

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

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

Примеры приложений Parisian Evolution включают:

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

Значения

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

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

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

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

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

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

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

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

синограмма $(Y)$ из $f$, что известно.

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

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

$Y=P[f]+\epsilon$

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

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

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

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

где ${\hat {f}}$ это оценка $f$, что минимизирует метрику ошибки (здесь ℓ ² -norm , но можно использовать и другие метрики ошибок) между $Y$ и ${\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.

Псевдокод ниже представляет собой пошаговое описание алгоритма Fly для томографической реконструкции . Алгоритм следует установившейся парадигме. В иллюстративных целях используются продвинутые генетические операторы, такие как митоз, двойная мутация и т. д. игнорируются. Реализацию 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.   // freproduce is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // freproduce 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 плиток нужно найти 45 000 чисел. Используя классический эволюционный алгоритм, в котором ответом на задачу оптимизации является лучший индивидуум, геном индивидуума будет состоять из 45 000 генов. Этот подход будет чрезвычайно дорогостоящим с точки зрения сложности и времени вычислений. То же самое относится и к любому классическому алгоритму оптимизации. Используя алгоритм Fly, каждый человек имитирует плитку, и его можно индивидуально оценить, используя его локальную приспособленность, чтобы оценить ее вклад в производительность популяции (глобальная приспособленность). Здесь у особи 9 генов вместо 9 N , а N. особей Ее можно решить как задачу реконструкции следующим образом:

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

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

См. также

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