Un colaborador importante de este artículo parece tener una estrecha conexión con su tema. ( Julio de 2018 ) |
El algoritmo Fly es un tipo de coevolución cooperativa basada en el enfoque parisino. [1] El algoritmo Fly se desarrolló por primera vez en 1999 en el ámbito de la aplicación de algoritmos evolutivos a la visión estéreo por computadora . [2] [3] A diferencia del enfoque clásico de la estereovisión basado en imágenes, que extrae primitivas de imagen y luego las empareja para obtener información en 3-D, el Agoritmo Fly se basa en la exploración directa del espacio en 3D de la escena. . Una mosca se define como un punto tridimensional descrito por sus coordenadas ( x , y , z). Una vez que se ha creado una población aleatoria de moscas en un espacio de búsqueda correspondiente al campo de visión de las cámaras, su evolución (basada en el paradigma de la Estrategia Evolutiva) utilizó una función de aptitud que evalúa la probabilidad de que la mosca esté acostada sobre la superficie visible de un objeto, basado en la consistencia de sus proyecciones de imagen. Para ello, la función fitness utiliza los niveles de gris, colores y / o texturas de las proyecciones calculadas de la mosca.
El primer campo de aplicación del algoritmo Fly ha sido la estereovisión. [2] [3] [4] [5] Mientras que los enfoques clásicos de "prioridad de imagen" utilizan características coincidentes de las imágenes estéreo para construir un modelo 3-D, el algoritmo Fly explora directamente el espacio 3-D y usa datos de imagen evaluar la validez de hipótesis 3-D. Una variante llamada "Dynamic Flies" define la mosca como un 6-uple ( x , y , z , x ' , y' , z ' ) que involucra la velocidad de la mosca. [6] [7]Los componentes de la velocidad no se tienen en cuenta explícitamente en el cálculo de la aptitud, pero se utilizan en la actualización de las posiciones de las moscas y están sujetos a operadores genéticos similares (mutación, cruce).
La aplicación de Moscas para evitar obstáculos en vehículos [8] aprovecha el hecho de que la población de moscas es una representación de la escena que se adapta al tiempo y que evoluciona casi continuamente para generar directamente señales de control de vehículos a partir de las moscas. El uso del algoritmo Fly no está estrictamente restringido a imágenes estéreo, ya que se pueden agregar otros sensores (por ejemplo, sensores de proximidad acústicos, etc.) como términos adicionales a la función de acondicionamiento físico que se está optimizando. La información de odometría también se puede usar para acelerar la actualización de las posiciones de las moscas y, a la inversa, las posiciones de las moscas se pueden usar para proporcionar información de localización y mapeo. [9]
Otro campo de aplicación del algoritmo Fly es la reconstrucción para tomografía de emisión en medicina nuclear . El algoritmo Fly se ha aplicado con éxito en la tomografía computarizada por emisión de fotón único [10] y la tomografía por emisión de positrones [11] . [12] Aquí, cada mosca se considera un emisor de fotones y su aptitud se basa en la conformidad de la iluminación simulada de los sensores con el patrón real observado en los sensores. Dentro de esta aplicación, la función de aptitud se ha redefinido para utilizar el nuevo concepto de "evaluación marginal". Aquí, la aptitud de un individuo se calcula como su contribución (positiva o negativa) a la calidad de la población mundial. Se basa en elprincipio de validación cruzada de dejar uno fuera . Una función de aptitud global evalúa la calidad de la población en su conjunto; solo entonces la aptitud de un individuo (una mosca) se calcula como la diferencia entre los valores de aptitud global de la población con y sin la mosca particular cuya función de aptitud individual debe evaluarse. [13] [14] En [15] la aptitud de cada mosca se considera un "nivel de confianza". Se utiliza durante el proceso de voxelización para modificar la huella individual de la mosca mediante un modelado implícito (como las metabolas ). Produce resultados suaves que son más precisos.
Más recientemente se ha utilizado en el arte digital para generar imágenes en forma de mosaico o pintura en aerosol. [16] Se pueden encontrar ejemplos de imágenes en YouTube.
Aquí, la población de individuos se considera como una sociedad donde los individuos colaboran hacia un objetivo común. Esto se implementa utilizando un algoritmo evolutivo que incluye todos los operadores genéticos comunes (por ejemplo, mutación, cruce, selección). La principal diferencia está en la función de fitness. Aquí se utilizan dos niveles de función de fitness:
Además, se requiere un mecanismo de diversidad para evitar que los individuos se reúnan en solo unas pocas áreas del espacio de búsqueda. Otra diferencia está en la extracción de la solución del problema una vez que termina el ciclo evolutivo. En los enfoques evolutivos clásicos, el mejor individuo corresponde a la solución y el resto de la población se descarta. Aquí, todos los individuos (o individuos de un subgrupo de la población) se cotejan para construir la solución del problema. La forma en que se construyen las funciones de aptitud y la forma en que se realiza la extracción de la solución dependen, por supuesto, del problema.
Ejemplos de aplicaciones de Parisian Evolution incluyen:
La coevolución cooperativa es una amplia clase de algoritmos evolutivos en los que un problema complejo se resuelve descomponiéndolo en subcomponentes que se resuelven de forma independiente. El enfoque parisino comparte muchas similitudes con el algoritmo coevolutivo cooperativo . El enfoque parisino hace uso de una sola población, mientras que las múltiples especies pueden usarse en un algoritmo coevolutivo cooperativo . En el algoritmo evolutivo clásico , el algoritmo coevolutivo cooperativo y la evolución parisina se consideran motores evolutivos internos similares . La diferencia entre el algoritmo coevolutivo cooperativo y la evolución parisina reside en la semántica de la población. El algoritmo coevolutivo cooperativo divide un gran problema en subproblemas (grupos de individuos) y los resuelve por separado hacia el gran problema. [17] No hay interacción / reproducción entre individuos de las diferentes subpoblaciones, solo con individuos de la misma subpoblación. Sin embargo, los algoritmos evolutivos parisinos resuelven todo un problema como un gran componente. Todos los individuos de la población cooperan juntos para conducir a toda la población hacia áreas atractivas del espacio de búsqueda.
La coevolución cooperativa y la optimización del enjambre de partículas (PSO) comparten muchas similitudes. PSO se inspira en el comportamiento social de la bandada de aves o la formación de bancos de peces. [18] [19] Inicialmente se introdujo como una herramienta para la animación realista en gráficos por computadora. Utiliza individuos complejos que interactúan entre sí para construir comportamientos colectivos visualmente realistas mediante el ajuste de las reglas de comportamiento de los individuos (que pueden usar generadores aleatorios). En la optimización matemática, cada partícula del enjambre sigue de alguna manera su propio camino aleatorio sesgado hacia la mejor partícula del enjambre. En el algoritmo Fly, las moscas apuntan a construir representaciones espaciales de una escena a partir de datos de sensores reales; las moscas no se comunican ni cooperan explícitamente, y no utilizan ningún modelo de comportamiento.
Ambos algoritmos son métodos de búsqueda que comienzan con un conjunto de soluciones aleatorias, que se corrigen iterativamente hacia un óptimo global. Sin embargo, la solución del problema de optimización en el algoritmo Fly es la población (o un subconjunto de la población): las moscas colaboran implícitamente para construir la solución. En PSO la solución es una sola partícula, la que tiene la mejor aptitud. Otra diferencia principal entre el algoritmo Fly y con PSO es que el algoritmo Fly no se basa en ningún modelo de comportamiento, sino que solo construye una representación geométrica.
La reconstrucción de la tomografía es un problema inverso que a menudo está mal planteado debido a la falta de datos y / o al ruido. La respuesta al problema inverso no es única y, en caso de un nivel de ruido extremo, es posible que ni siquiera exista. Los datos de entrada de un algoritmo de reconstrucción se pueden dar como la transformada de Radon o sinograma de los datos a reconstruir . es desconocido; es conocida. La adquisición de datos en tomografía se puede modelar como:
donde es la matriz del sistema o el operador de proyección y corresponde a algún ruido de Poisson . En este caso la reconstrucción corresponde a la inversión de la transformada Radon :
Tenga en cuenta que puede tener en cuenta el ruido, la geometría de adquisición, etc. El algoritmo Fly es un ejemplo de reconstrucción iterativa . Los métodos iterativos en la reconstrucción tomográfica son relativamente fáciles de modelar:
donde es una estimación de , que minimiza una métrica de error (aquí ℓ 2 -norm , pero se podrían usar otras métricas de error) entre y . Tenga en cuenta que se puede introducir un término de regularización para evitar el sobreajuste y suavizar el ruido conservando los bordes. Los métodos iterativos se pueden implementar de la siguiente manera:
(i) La reconstrucción comienza utilizando una estimación inicial de la imagen (generalmente una imagen constante), (ii) Los datos de proyección se calculan a partir de esta imagen, (iii) Las proyecciones estimadas se comparan con las proyecciones medidas, (iv) Se realizan correcciones para corregir la imagen estimada, y (v) El algoritmo itera hasta la convergencia de los conjuntos de proyección estimados y medidos.
El pseudocódigo siguiente es una descripción paso a paso del algoritmo Fly para la reconstrucción tomográfica . El algoritmo sigue el paradigma de estado estacionario. Con fines ilustrativos, se ignoran los operadores genéticos avanzados, como la mitosis, la mutación dual, etc. [22] [23] . Se puede encontrar una implementación de JavaScript en Fly4PET .
algoritmo fly-algoritmo es de entrada: número de moscas ( N ), datos de proyección de entrada ( p referencia ) salida: la población de moscas ( F ), las proyecciones estimadas a partir de F ( p estimada ) el volumen 3-D correspondiente a la voxelización de F ( V F ) postcondition: la diferencia entre p estima y p referencia es mínimo. COMIENZO 1. // Inicialización 2. // Establecer la posición de las N moscas, es decir, crear una estimación inicial 3. para cada mosca i en la población de moscas F do 4. F ( i ) x ← aleatorio (0, 1) 5. F ( i ) y ← aleatorio (0, 1) 6. F ( i ) z ← aleatorio (0, 1) 7. Sume la proyección de F ( i ) en p estimado 8. 9. // Calcular el rendimiento de la población (es decir, la aptitud global) 10. G de fitness ( F ) ← error métricas ( p referencia , p estima ) 11. 12. f kill ← Selecciona una mosca aleatoria de F13. 14. Quite la contribución de f kill de p estimada15. 16. // Calcular el rendimiento de la población sin f matanza 17. G de fitness ( F - { f matanza }) ← error métricas ( p referencia , p estimado ) 18. 19. // Compara los rendimientos, es decir, calcula la aptitud local de la mosca. 20. L fitness ( f matar ) ← G fitness ( F - { f kill }) - G fitness ( F ) 21. 22. Si la aptitud local es mayor que 0, // Selección de umbral de una mosca mala que se puede matar 23. luego vaya al paso 26. // f kill es una buena mosca (el rendimiento de la población es mejor cuando se incluye f kill ): no debemos matarlo 24. de lo contrario, vaya al paso 28. // f kill es una mala mosca (el desempeño de la población es peor cuando se incluye f kill ): podemos deshacernos de él25. 26. Restaure la contribución de la mosca, luego vaya al Paso 12. 27. 28. Seleccione un operador genético 29. 30. Si el operador genético es una mutación, 31. luego vaya al paso 34. 32. de lo contrario, vaya al paso 50. 33. 34. f reproducir ← Seleccionar una mosca aleatoria de F35. 14. Quite la contribución de f reproduce de p estimada37. 38. // Calcular el rendimiento de la población sin f reproducen 39. G de fitness ( F - { f reproducen }) ← error métricas ( p referencia , p estimado ) 40. 41. // Compara los rendimientos, es decir, calcula la aptitud local de la mosca. 42. L fitness ( f reproducir ) ← G fitness ( F - { f reproducir }) - G fitness ( F ) 43. 44. Restaura la contribución de la mosca 45. 46. Si la aptitud local es menor o igual a 0, // Selección de umbral de una buena mosca que pueda reproducirse 47. de lo contrario, vaya al paso 34. // f kill es una mosca mala: no debemos permitir que se reproduzca 48. luego vaya al paso 53. // f kill es una buena mosca: podemos permitir que se reproduzca49. 50. // Sangre nueva / Inmigración 51. Reemplace f kill por una nueva mosca con una posición aleatoria, vaya al paso 57. 52. 53. // Mutación 54. Copie f reproducir en f kill 55. Altere leve y aleatoriamente la posición de f kill56. 57. Sume la contribución de la nueva mosca a la población. 58. 59. Si detiene la reconstrucción, 60. luego vaya al paso 63. 61. de lo contrario, vaya al paso 10. 62. 63. // Extraer la solución 64. V F ← voxelización de Fsesenta y cinco. 66. volver V F FIN
En este ejemplo, una imagen de entrada debe aproximarse mediante un conjunto de mosaicos (por ejemplo, como en un mosaico antiguo ). Un mosaico tiene una orientación (ángulo θ), tres componentes de color (R, G, B), un tamaño (w, h) y una posición (x, y, z). Si hay N fichas, hay 9 Nnúmeros de coma flotante desconocidos para adivinar. En otras palabras, para 5,000 fichas, hay 45,000 números para encontrar. Utilizando un algoritmo evolutivo clásico donde la respuesta al problema de optimización es el mejor individuo, el genoma de un individuo estaría compuesto por 45.000 genes. Este enfoque sería extremadamente costoso en términos de complejidad y tiempo de cálculo. Lo mismo se aplica a cualquier algoritmo de optimización clásico. Usando el algoritmo Fly, cada individuo imita un mosaico y puede ser evaluado individualmente usando su aptitud local para evaluar su contribución al rendimiento de la población (la aptitud global). Aquí un individuo tiene 9 genes en lugar de 9 N , y hay N individuos. Se puede resolver como un problema de reconstrucción de la siguiente manera:
donde es la imagen de entrada y son las coordenadas de píxeles a lo largo del eje horizontal y vertical respectivamente, y son el ancho y alto de la imagen en número de píxeles respectivamente, es la población de moscas y es un operador de proyección que crea una imagen a partir de moscas. Este operador de proyección puede adoptar muchas formas. En su trabajo, Z. Ali Aboodd [16] utiliza OpenGL para generar diferentes efectos (por ejemplo, mosaicos o pintura en aerosol). Para acelerar la evaluación de las funciones de fitness, también se utiliza OpenCL . El algoritmo comienza con una población que se genera aleatoriamente (vea la Línea 3 en el algoritmo anterior).luego se evalúa utilizando la aptitud global para calcular (ver Línea 10). es una métrica de error, debe minimizarse.