Algoritmo de voo - Fly algorithm

História

O Fly Algorithm é um tipo de coevolução cooperativa baseada na abordagem parisiense. O Fly Algorithm foi desenvolvido pela primeira vez em 1999 no escopo da aplicação de algoritmos evolutivos à visão estéreo de computador . Ao contrário da abordagem clássica de estereovisão baseada em imagens, que extrai imagens primitivas e depois as combina para obter informações em 3-D, o Fly Agorithm é baseado na exploração direta do espaço 3-D da cena. Uma mosca é definida como um ponto 3-D descrito por suas coordenadas ( x , y , z ). Uma vez que uma população aleatória de moscas foi criada em um espaço de busca correspondente ao campo de visão das câmeras, sua evolução (com base no paradigma da Estratégia Evolutiva) usou uma função de aptidão que avalia a probabilidade de a mosca estar na superfície visível de um objeto, com base na consistência de suas projeções de imagem. Para tal, a função de fitness utiliza os níveis de cinza, cores e / ou texturas das projeções da mosca calculada.

O primeiro campo de aplicação do Fly Algorithm foi a estereovisão. Enquanto as abordagens clássicas de 'prioridade de imagem' usam recursos de correspondência das imagens estéreo para construir um modelo 3-D, o Fly Algorithm explora diretamente o espaço 3-D e usa dados de imagem para avaliar a validade das hipóteses 3-D. Uma variante chamada "Dynamic Flies" define a mosca como um 6-uple ( x , y , z , x ' , y' , z ' ) envolvendo a velocidade da mosca. Os componentes da velocidade não são explicitamente levados em consideração no cálculo da aptidão, mas são usados na atualização das posições das moscas e estão sujeitos a operadores genéticos semelhantes (mutação, cruzamento).

A aplicação de Moscas para evitar obstáculos em veículos explora o fato de que a população de moscas é uma representação da cena em evolução quase contínua, compatível com o tempo, para gerar diretamente sinais de controle de veículos das moscas. O uso do Fly Algorithm não é estritamente restrito a imagens estéreo, já que outros sensores podem ser adicionados (por exemplo, sensores acústicos de proximidade, etc.) como termos adicionais para a função de aptidão que está sendo otimizada. As informações de Odometria também podem ser usadas para agilizar a atualização das posições das moscas e, inversamente, as posições das moscas podem ser usadas para fornecer informações de localização e mapeamento.

Outro campo de aplicação do Fly Algorithm é a reconstrução para tomografia de emissão em medicina nuclear . O Fly Algorithm foi aplicado com sucesso na tomografia computadorizada por emissão de fóton único e tomografia por emissão de pósitrons . Aqui, cada mosca é considerada um emissor de fótons e sua adequação é baseada na conformidade da iluminação simulada dos sensores com o padrão real observado nos sensores. Dentro desta aplicação, a função de aptidão foi redefinida para usar o novo conceito de 'avaliação marginal'. Aqui, a aptidão de um indivíduo é calculada como sua contribuição (positiva ou negativa) para a qualidade da população global. Baseia-se no princípio de validação cruzada deixar um de fora . Uma função de aptidão global avalia a qualidade da população como um todo; somente então a aptidão de um indivíduo (uma mosca) é calculada como a diferença entre os valores globais de aptidão da população com e sem a mosca particular, cuja função de aptidão individual deve ser avaliada. No fitness de cada mosca é considerado um 'nível de confiança'. É usado durante o processo de voxelização para ajustar a pegada individual da mosca usando modelagem implícita (como metaballs ). Produz resultados suaves e mais precisos.

Mais recentemente, tem sido usado na arte digital para gerar imagens em mosaico ou tinta spray. Exemplos de imagens podem ser encontrados no YouTube

Evolução parisiense

Aqui, a população de indivíduos é considerada como uma sociedade onde os indivíduos colaboram para um objetivo comum. Isso é implementado usando um algoritmo evolutivo que inclui todos os operadores genéticos comuns (por exemplo, mutação, cruzamento, seleção). A principal diferença está na função de fitness. Aqui, dois níveis de função de aptidão são usados:

Uma função de aptidão local para avaliar o desempenho de um determinado indivíduo (geralmente usada durante o processo de seleção).
Uma função de aptidão global para avaliar o desempenho de toda a população. Maximizar (ou minimizar dependendo do problema considerado) essa aptidão global é o objetivo da população.

Além disso, um mecanismo de diversidade é necessário para evitar que os indivíduos se reúnam em apenas algumas áreas do espaço de busca. Outra diferença está na extração da solução do problema uma vez que o ciclo evolutivo termina. Nas abordagens evolucionárias clássicas, o melhor indivíduo corresponde à solução e o resto da população é descartado. Aqui, todos os indivíduos (ou indivíduos de um subgrupo da população) são agrupados para construir a solução do problema. A maneira como as funções de adequação são construídas e a maneira como a extração da solução é feita dependem, obviamente, do problema.

Exemplos de aplicações do Parisian Evolution incluem:

Desambiguação

Abordagem parisiense vs coevolução cooperativa

Coevolução cooperativa é uma ampla classe de algoritmos evolutivos em que um problema complexo é resolvido decompondo-o em subcomponentes que são resolvidos independentemente. A abordagem parisiense compartilha muitas semelhanças com o algoritmo coevolucionário cooperativo . A abordagem parisiense faz uso de uma única população, enquanto que as várias espécies podem ser usadas em algoritmos coevolucionários cooperativos . Motores evolutivos internos similares são considerados no clássico algoritmo evolutivo , algoritmo coevolutionary cooperativa e evolução parisiense. A diferença entre o algoritmo coevolucionário cooperativo e a evolução parisiense reside na semântica da população. O algoritmo coevolutivo cooperativo divide um grande problema em subproblemas (grupos de indivíduos) e os resolve separadamente em direção ao grande problema. Não há interação / reprodução entre indivíduos das diferentes subpopulações, apenas com indivíduos da mesma subpopulação. No entanto, os algoritmos evolutivos parisienses resolvem todo um problema como um grande componente. Todos os indivíduos da população cooperam juntos para conduzir toda a população em direção a áreas atraentes do espaço de busca.

Fly Algorithm vs otimização de enxame de partículas

Coevolução cooperativa e otimização de enxame de partículas (PSO) compartilham muitas semelhanças. PSO é inspirado no comportamento social de bando de pássaros ou cardume de peixes. Foi inicialmente apresentado como uma ferramenta para animação realista em computação gráfica. Ele usa indivíduos complexos que interagem uns com os outros a fim de construir comportamentos coletivos visualmente realistas por meio do ajuste das regras de comportamento dos indivíduos (que podem usar geradores aleatórios). Na otimização matemática, cada partícula do enxame segue de alguma forma seu próprio caminho aleatório inclinado em direção à melhor partícula do enxame. No Fly Algorithm, as moscas visam construir representações espaciais de uma cena a partir de dados reais do sensor; as moscas não se comunicam ou cooperam explicitamente e não usam nenhum modelo de comportamento.

Ambos os algoritmos são métodos de busca que começam com um conjunto de soluções aleatórias, que são corrigidas iterativamente em direção a um ótimo global. No entanto, a solução do problema de otimização no Algoritmo Fly é a população (ou um subconjunto da população): As moscas colaboram implicitamente para construir a solução. No PSO a solução é uma única partícula, aquela com melhor adequação. Outra diferença principal entre o Fly Algorithm e com o PSO é que o Fly Algorithm não é baseado em nenhum modelo comportamental, mas apenas constrói uma representação geométrica.

Aplicações do algoritmo Fly

Visão estéreo de computador
Evitar obstáculos
Localização e mapeamento simultâneos (SLAM)
Reconstrução de tomografia computadorizada por emissão de fóton único (SPECT)
Reconstrução de tomografia por emissão de pósitrons (PET)
Arte digital

Exemplo: reconstrução tomográfica

Sinograma de , que é conhecido.

{\ displaystyle (Y)}

{\ displaystyle f}

Exemplo de reconstrução de um fantoma hot rod usando o Fly Algorithm.

A reconstrução da tomografia é um problema inverso que muitas vezes é mal colocado devido à falta de dados e / ou ruído. A resposta para o problema inverso não é única e, em caso de nível de ruído extremo, pode nem existir. Os dados de entrada de um algoritmo de reconstrução podem ser dados como a transformação de Radon ou sinograma dos dados a reconstruir . É desconhecido; é conhecido. A aquisição de dados na tomografia pode ser modelada como: ${\ displaystyle \ left (Y \ right)}$ ${\ displaystyle \ left (f \ right)}$ ${\ displaystyle f}$ ${\ displaystyle Y}$

${\ displaystyle Y = P [f] + \ epsilon}$

onde é a matriz do sistema ou operador de projeção e corresponde a algum ruído de Poisson . Neste caso, a reconstrução corresponde à inversão da transformada de Radon : ${\ displaystyle P}$ ${\ displaystyle \ epsilon}$

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

Observe que pode levar em conta o ruído, a geometria de aquisição, etc. O Fly Algorithm é um exemplo de reconstrução iterativa . Os métodos iterativos na reconstrução tomográfica são relativamente fáceis de modelar: ${\ displaystyle P ^ {- 1}}$

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

onde está uma estimativa de , que minimiza uma métrica de erro (aqui $ℓ$ $2$ -norm , mas outras métricas de erro podem ser usadas) entre e . Observe que um termo de regularização pode ser introduzido para evitar sobreajuste e para suavizar o ruído, preservando as bordas. Os métodos iterativos podem ser implementados da seguinte forma: ${\ displaystyle {\ hat {f}}}$ ${\ displaystyle f}$ ${\ displaystyle Y}$ ${\ displaystyle {\ hat {Y}}}$

Correção iterativa na reconstrução tomográfica.

  (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.

O pseudocódigo abaixo é uma descrição passo a passo do Algoritmo Fly para reconstrução tomográfica . O algoritmo segue o paradigma do estado estacionário. Para fins ilustrativos, os operadores genéticos avançados, como mitose, mutação dupla, etc. são ignorados. Uma implementação de JavaScript pode ser encontrada no Fly4PET .

algorithm fly-algorithm is
    input: number of flies (N), 
           input projection data (p_reference)
    
    output: the fly population (F), 
            the projections estimated from F (p_estimated)
            the 3-D volume corresponding to the voxelisation of F (V_F)
    
    postcondition: the difference between p_estimated and p_reference 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 p_estimated
 8.   
 9.   // Compute the population's performance (i.e. the global fitness)
10.   G_fitness(F) ← Error_metrics(p_reference, p_estimated)
11.    
12.   f_kill ← Select a random fly of F
13.    
14.   Remove f_kill's contribution from p_estimated
15.    
16.   // Compute the population's performance without f_kill
17.   G_fitness(F-{f_kill}) ← Error_metrics(p_reference, p_estimated)
18.    
19.   // Compare the performances, i.e. compute the fly's local fitness
20.   L_fitness(f_kill) ← G_fitness(F-{f_kill}) - G_fitness(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.   // f_kill is a good fly (the population's performance is better when f_kill is included): we should not kill it
24.       else go to Step 28.   // f_kill is a bad fly (the population's performance is worse when f_kill 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.   f_reproduce ← Select a random fly of F
35.    
14.   Remove f_reproduce's contribution from p_estimated
37.    
38.   // Compute the population's performance without f_reproduce
39.   G_fitness(F-{f_reproduce}) ← Error_metrics(p_reference, p_estimated)
40.    
41.   // Compare the performances, i.e. compute the fly's local fitness
42.   L_fitness(f_reproduce) ← G_fitness(F-{f_reproduce}) - G_fitness(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.   // f_kill is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // f_kill is a good fly: we can allow it to reproduce
49.    
50.   // New blood / Immigration
51.   Replace f_kill by a new fly with a random position, go to Step 57.
52.    
53.   // Mutation
54.   Copy f_reproduce into f_kill
55.   Slightly and randomly alter f_kill'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.   V_F ← voxelisation of F
65.    
66.   return V_F
   
   END

Exemplo: artes digitais

Pesquisa evolutiva.

Imagem reconstruída após a otimização usando um conjunto de listras como padrão para cada ladrilho.

Neste exemplo, uma imagem de entrada deve ser aproximada por um conjunto de ladrilhos (por exemplo, como em um mosaico antigo ). Um ladrilho tem uma orientação (ângulo θ), três componentes de cor (R, G, B), um tamanho (w, h) e uma posição (x, y, z). Se houver N blocos, haverá 9 N números de ponto flutuante desconhecidos para adivinhar. Em outras palavras, para 5.000 peças, há 45.000 números a serem encontrados. Usando um algoritmo evolutivo clássico em que a resposta do problema de otimização é o melhor indivíduo, o genoma de um indivíduo seria composto de 45.000 genes. Essa abordagem seria extremamente cara em termos de complexidade e tempo de computação. O mesmo se aplica a qualquer algoritmo de otimização clássico. Usando o Algoritmo Fly, cada indivíduo imita um bloco e pode ser avaliado individualmente usando sua aptidão local para avaliar sua contribuição para o desempenho da população (a aptidão global). Aqui, um indivíduo tem 9 genes em vez de 9 N , e há N indivíduos. Pode ser resolvido como um problema de reconstrução da seguinte maneira:

${\ 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) |}$

onde é a imagem de entrada e são as coordenadas de pixel ao longo dos eixos horizontal e vertical, respectivamente, e são a largura e a altura da imagem em número de pixels, respectivamente, é a população de moscas e é um operador de projeção que cria uma imagem de moscas. Este operador de projeção pode assumir várias formas. Em seu trabalho, Z. Ali Aboodd usa OpenGL para gerar diferentes efeitos (por exemplo, mosaicos ou tinta spray). Para agilizar a avaliação das funções de fitness, o OpenCL também é usado. O algoritmo começa com uma população gerada aleatoriamente (consulte a Linha 3 do algoritmo acima). é então avaliada usando a aptidão global para calcular (ver Linha 10). é uma métrica de erro, tem que ser minimizada. ${\ entrada de estilo de exibição}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle W}$ ${\ displaystyle H}$ ${\ displaystyle F}$ ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle F}$ ${\ displaystyle F}$ ${\ 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}}$

Languages

In other projects