Fly algoritması - Fly algorithm

Tarih

Fly Algoritması, Paris yaklaşımına dayanan bir tür işbirlikçi birlikte evrimdir . Fly Algoritma ilk uygulama kapsamında 1999 yılında geliştirilmiştir Evrimsel algoritmalar için bilgisayar stereo görme . Görüntü ilkellerini çıkaran ve ardından 3 boyutlu bilgi elde etmek için bunları eşleştiren klasik görüntü tabanlı stereovizyon yaklaşımından farklı olarak, Fly Agorithm, sahnenin 3 boyutlu alanının doğrudan keşfedilmesine dayanır. Sinek, koordinatları ( x , y , z ) ile tanımlanan 3 boyutlu bir nokta olarak tanımlanır . Kameraların görüş alanına karşılık gelen bir arama uzayında rastgele bir sinek popülasyonu oluşturulduktan sonra, evrimi (Evrimsel Strateji paradigmasına dayalı olarak) , sineğin görünür yüzeyinde ne kadar muhtemel olduğunu değerlendiren bir uygunluk fonksiyonu kullandı . görüntü projeksiyonlarının tutarlılığına dayanan bir nesne. Bu amaçla uygunluk işlevi, hesaplanan sinek projeksiyonlarının gri seviyelerini, renklerini ve/veya dokularını kullanır.

Fly Algoritmasının ilk uygulama alanı stereovizyon olmuştur. Klasik 'görüntü önceliği' yaklaşımları 3 boyutlu bir model oluşturmak için stereo görüntülerden eşleşen özellikleri kullanırken, Fly Algoritması doğrudan 3 boyutlu alanı araştırır ve 3 boyutlu hipotezlerin geçerliliğini değerlendirmek için görüntü verilerini kullanır. "Dinamik Sinekler" olarak adlandırılan bir değişken, sineği , sineğin hızını içeren 6-uple ( x , y , z , x' , y' , z' ) olarak tanımlar . Hız bileşenleri uygunluk hesaplamasında açıkça dikkate alınmaz, ancak sineklerin konumlarının güncellenmesinde kullanılır ve benzer genetik operatörlere (mutasyon, çaprazlama) tabidir.

Sineklerin araçlarda engellerden kaçınmaya uygulanması, sinek popülasyonunun, sineklerden doğrudan araç kontrol sinyalleri üretmek için sahnenin zamana uyumlu, yarı sürekli gelişen bir temsili olduğu gerçeğinden yararlanır. Fly Algoritmasının kullanımı, optimize edilen uygunluk fonksiyonuna ek terimler olarak başka sensörler (örn. akustik yakınlık sensörleri, vb.) eklenebileceğinden, stereo görüntülerle kesinlikle sınırlı değildir. Odometri bilgileri, sineklerin konumlarının güncellenmesini hızlandırmak için de kullanılabilir ve bunun tersine, sineklerin konumları, yerelleştirme ve haritalama bilgileri sağlamak için kullanılabilir.

Fly Algoritmasının bir başka uygulama alanı, nükleer tıpta emisyon Tomografisi için yeniden yapılandırmadır . Fly Algoritması, tek foton emisyonlu bilgisayarlı tomografi ve pozitron emisyon tomografisinde başarıyla uygulanmıştır . Burada, her sinek bir foton yayıcı olarak kabul edilir ve uygunluğu, sensörlerin simüle edilmiş aydınlatmasının sensörler üzerinde gözlemlenen gerçek modelle uygunluğuna dayanır. Bu uygulamada, uygunluk fonksiyonu, yeni 'marjinal değerlendirme' kavramını kullanmak için yeniden tanımlanmıştır. Burada, bir bireyin uygunluğu, küresel nüfusun kalitesine (olumlu veya olumsuz) katkısı olarak hesaplanır. Bu dayanmaktadır izni birini dışarıda çapraz doğrulama ilkesine. Bir küresel uygunluk fonksiyonu bir bütün olarak nüfusun kalitesini değerlendirir; ancak o zaman bir bireyin (bir sineğin) uygunluğu, bireysel uygunluk fonksiyonu değerlendirilmesi gereken belirli bir sinek olan ve olmayan popülasyonun global uygunluk değerleri arasındaki fark olarak hesaplanır . Her sineğin uygunluğu bir 'güven seviyesi' olarak kabul edilir. Vokselizasyon işlemi sırasında, örtük modelleme ( metatoplar gibi ) kullanarak sineğin bireysel ayak izini ayarlamak için kullanılır . Daha doğru olan pürüzsüz sonuçlar üretir.

Daha yakın zamanlarda, mozaik benzeri görüntüler veya sprey boya oluşturmak için dijital sanatta kullanılmıştır. Görüntü örnekleri YouTube'da bulunabilir

Paris evrimi

Burada, bireylerin nüfusu, bireylerin ortak bir amaç için işbirliği yaptığı bir toplum olarak kabul edilir . Bu, tüm yaygın genetik operatörleri (örneğin mutasyon, çaprazlama, seçim) içeren evrimsel bir algoritma kullanılarak uygulanır . Temel fark uygunluk fonksiyonundadır. Burada iki uygunluk fonksiyonu seviyesi kullanılır:

• Belirli bir bireyin performansını değerlendirmek için yerel bir uygunluk işlevi (genellikle seçim sürecinde kullanılır).
• Tüm popülasyonun performansını değerlendirmek için küresel bir uygunluk fonksiyonu. Bu küresel uygunluğu maksimize etmek (veya ele alınan probleme bağlı olarak minimize etmek) popülasyonun hedefidir.

Ayrıca, arama uzayının sadece birkaç alanında bireylerin toplanmasını önlemek için bir çeşitlilik mekanizması gereklidir. Diğer bir fark, evrimsel döngü sona erdiğinde problem çözümünün çıkarılmasındadır. Klasik evrimsel yaklaşımlarda, en iyi birey çözüme karşılık gelir ve popülasyonun geri kalanı atılır. Burada, problem çözümünü oluşturmak için tüm bireyler (veya popülasyonun bir alt grubunun bireyleri) bir araya getirilir. Uygunluk fonksiyonlarının oluşturulma şekli ve çözüm çıkarmanın yapılma şekli elbette probleme bağlıdır.

Parisli Evrim uygulamalarının örnekleri şunları içerir:

• Fly algoritması .
• Metin madenciliği .
• El hareketi tanıma .
• Endüstriyel tarımsal gıda sürecinde karmaşık etkileşimlerin modellenmesi .
• Pozitron Emisyon Tomografisi rekonstrüksiyonu .

anlam ayrımı

Paris yaklaşımı vs işbirlikçi birlikte evrim

İşbirliğine dayalı birlikte evrim , karmaşık bir sorunun bağımsız olarak çözülen alt bileşenlere ayrıştırılarak çözüldüğü geniş bir evrimsel algoritma sınıfıdır . Paris yaklaşımı, işbirlikçi birlikte-evrimsel algoritma ile birçok benzerliği paylaşmaktadır . Paris yaklaşımı, tek bir popülasyonu kullanır, oysa çoklu türler işbirlikçi birlikte evrimsel algoritmada kullanılabilir . Benzer dahili evrimsel motorlar, klasik evrimsel algoritma , işbirlikçi birlikte evrimsel algoritma ve Paris evriminde dikkate alınır. Arasındaki fark kooperatif birlikte geçirilen evrimin algoritması ve Paris evrim halkın semantik yatar. İşbirlikçi ortak evrim algoritması , büyük bir problemi alt problemlere (birey grupları) böler ve onları büyük probleme doğru ayrı ayrı çözer. Farklı alt popülasyonların bireyleri arasında hiçbir etkileşim/üreme yoktur, sadece aynı alt popülasyonun bireyleri ile. Bununla birlikte, Parisli evrimsel algoritmalar , büyük bir bileşen olarak bütün bir sorunu çözmektedir. Popülasyonun tüm bireyleri, tüm popülasyonu arama uzayının çekici alanlarına yönlendirmek için birlikte işbirliği yapar.

Fly Algoritması ve parçacık sürüsü optimizasyonu

İşbirliğine dayalı birlikte evrim ve parçacık sürüsü optimizasyonu (PSO) birçok benzerliği paylaşır. PSO , kuş sürülerinin veya balık sürülerinin sosyal davranışlarından esinlenmiştir. Başlangıçta bilgisayar grafiklerinde gerçekçi animasyon için bir araç olarak tanıtıldı. Bireylerin davranış kurallarını ayarlayarak (rastgele jeneratörler kullanabilir) görsel olarak gerçekçi toplu davranışlar oluşturmak için birbirleriyle etkileşime giren karmaşık bireyleri kullanır. Matematiksel optimizasyonda, sürünün her parçacığı bir şekilde sürünün en iyi parçacığına yönelen kendi rastgele yolunu izler. Fly Algoritması'nda, sinekler, gerçek sensör verilerinden bir sahnenin uzamsal temsillerini oluşturmayı amaçlar; sinekler iletişim kurmaz veya açıkça işbirliği yapmaz ve herhangi bir davranış modeli kullanmaz.

Her iki algoritma da, küresel bir optimuma doğru yinelemeli olarak düzeltilen bir dizi rastgele çözümle başlayan arama yöntemleridir. Bununla birlikte, Fly Algoritması'ndaki optimizasyon probleminin çözümü popülasyondur (veya popülasyonun bir alt kümesidir): Sinekler çözümü oluşturmak için dolaylı olarak işbirliği yapar. Gelen PSO çözüm, tek bir parçacık, en iyi uygunluk ile biridir. Fly Algoritması ile PSO arasındaki diğer bir temel fark, Fly Algoritmasının herhangi bir davranış modeline dayanmaması, yalnızca geometrik bir temsil oluşturmasıdır.

Fly algoritmasının uygulamaları

• Bilgisayar stereo görüşü
• Engel kaldırma
• Eşzamanlı yerelleştirme ve haritalama (SLAM)
• Tek foton emisyonlu bilgisayarlı tomografi (SPECT) rekonstrüksiyonu
• Pozitron emisyon tomografisi (PET) rekonstrüksiyonu
• Dijital sanat

Örnek: Tomografi rekonstrüksiyonu

Sinogram arasında bilinmektedir.${\görüntüleme stili (Y)}$${\görüntüleme stili f}$

Fly Algoritması kullanılarak bir sıcak çubuk fantomunun yeniden yapılandırılması örneği.

Tomografi rekonstrüksiyonu, genellikle eksik veriler ve/veya gürültü nedeniyle kötü pozlanmış ters bir problemdir . Ters problemin cevabı benzersiz değildir ve aşırı gürültü seviyesi olması durumunda mevcut bile olmayabilir. Gibi bir rekonstrüksiyon algoritması giriş verileri verilebilir Radon dönüşümü veya sinogram verileri yeniden . bilinmeyen; bilinen. Tomografide veri toplama şu şekilde modellenebilir: ${\görüntüleme stili \sol(E\sağ)}$${\görüntüleme stili \sol(f\sağ)}$${\görüntüleme stili f}$${\görüntüleme stili Y}$

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

burada sistem matris ya da projeksiyon operatörü ve olduğu bir karşılık gelir Poisson gürültü . Bu durumda yeniden yapılandırma, Radon dönüşümünün tersine çevrilmesine karşılık gelir : ${\görüntüleme stili P}$${\görüntüleme stili \epsilon }$

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

Not vb gürültü, edinim geometri The Fly Algoritması açıklama getirebilir örneğidir tekrarlı rekonstrüksiyon . Tomografik rekonstrüksiyonda yinelemeli yöntemlerin modellenmesi nispeten kolaydır: ${\görüntüleme stili P^{-1}}$

${\displaystyle {\hat {f}}=\operatöradı {arg\,min} ||Y-{\hat {Y}}||_{2}^{2}}$

burada bir tahminidir bir hata ölçümlerini (burada en aza indirir, ℓ ² -norm arasında, ancak diğer hata metrikleri kullanılabilir) ve . Kenarları korurken fazla takmayı önlemek ve gürültüyü yumuşatmak için bir düzenleme teriminin eklenebileceğini unutmayın . Yinelemeli yöntemler aşağıdaki gibi uygulanabilir: ${\displaystyle {\hat {f}}}$${\görüntüleme stili f}$${\görüntüleme stili Y}$${\görüntüleme stili {\şapka {Y}}}$

Tomografi rekonstrüksiyonunda yinelemeli düzeltme.

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

Aşağıdaki sözde kod , tomografik rekonstrüksiyon için Fly Algoritmasının adım adım açıklamasıdır . Algoritma, kararlı durum paradigmasını takip eder. Açıklama amacıyla mitoz, ikili mutasyon vb. gibi gelişmiş genetik operatörler göz ardı edilir. Fly4PET'te bir JavaScript uygulaması bulunabilir .

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.   // fkill is a bad fly: we should not allow it to reproduce
48.       then go to Step 53.   // fkill 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

Örnek: Dijital sanatlar

Evrimsel arama.

Her bir döşeme için desen olarak bir dizi şerit kullanılarak optimizasyondan sonra yeniden oluşturulan görüntü.

Bu örnekte, bir girdi görüntüsüne bir dizi döşeme ile yaklaşılacaktır (örneğin eski bir mozaikte olduğu gibi ). Bir döşemenin yönü (açı θ), üç renk bileşeni (R, G, B), boyutu (w, h) ve konumu (x, y, z) vardır. Varsa N fayans, 9 vardır N tahmin bilinmeyen kayan noktalı sayılar. Başka bir deyişle, 5.000 karo için bulunacak 45.000 sayı vardır. Optimizasyon probleminin cevabının en iyi birey olduğu klasik bir evrimsel algoritma kullanılarak, bir bireyin genomu 45.000 genden oluşacaktır. Bu yaklaşım, karmaşıklık ve hesaplama süresi açısından son derece maliyetli olacaktır. Aynısı herhangi bir klasik optimizasyon algoritması için de geçerlidir. Fly Algoritmasını kullanarak, her birey bir kutucuğu taklit eder ve popülasyonun performansına katkısını (küresel uygunluk) değerlendirmek için yerel uygunluğu kullanılarak bireysel olarak değerlendirilebilir. Burada bir bireyin 9 N yerine 9 geni vardır ve N birey vardır. Aşağıdaki gibi bir yeniden yapılandırma problemi olarak çözülebilir:

${\displaystyle yeniden yapılandırma=\operatöradı {arg\,min} {\overset {x<W}{\underset {y=0}{\sum }}}{\overset {j<H}{\underset {j=0 }{\sum }}}|giriş(x,y)-P[F](x,y)|}$

burada giriş görüntüdür, ve yatay ve dikey eksen boyunca piksel koordinatları sırasıyla, ve piksel sayısı görüntü genişliği ve yüksekliği sırasıyla, uçucu grup olduğu ve sinekler bir görüntü oluşturan bir çıkıntı operatördür. Bu projeksiyon operatörü birçok biçimde olabilir. Z. Ali Aboodd, çalışmasında farklı efektler (örn. mozaikler veya sprey boya) oluşturmak için OpenGL kullanıyor . Uygunluk fonksiyonlarının değerlendirilmesini hızlandırmak için OpenCL de kullanılır. Algoritma , rastgele oluşturulan bir popülasyonla başlar (yukarıdaki algoritmada 3. Satıra bakın). daha sonra hesaplamak için global uygunluk kullanılarak değerlendirilir (bkz. Satır 10). bir hata metriğidir, en aza indirilmelidir. ${\görüntüleme stili girişi}$${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili W}$${\görüntüleme stili H}$${\görüntüleme stili F}$${\görüntüleme stili P}$${\görüntüleme stili P}$${\görüntüleme stili F}$${\görüntüleme stili F}$${\displaystyle G_{fitness}(F)={\overset {x<W}{\underset {y=0}{\sum }}}{\overset {j<H}{\underset {j=0}{ \toplam }}}|giriş(x,y)-P[F](x,y)|}$${\displaystyle G_{fitness}}$

Ayrıca bakınız

• matematiksel optimizasyon
• metasezgisel
• Arama algoritması
• Stokastik optimizasyon
• evrimsel hesaplama
• evrimsel algoritma
• Genetik Algoritma
• Mutasyon (genetik algoritma)
• Çaprazlama (genetik algoritma)
• Seçim (genetik algoritma)

Referanslar