Kelebek Optimizasyonuna Dayalı "Akademik Rapor" Parçacık Filtresi Algoritması
Özet:
Standart partikül filtresinin optimal altı önem fonksiyonunun neden olduğu partikül bozunması problemine yönelik olarak, kelebek optimizasyonuna dayalı geliştirilmiş bir partikül filtre algoritması önerilmiştir. Parçacık filtresinin önem örnekleme süreci, kelebek algoritması tarafından optimize edilir, böylece gerçek durumdan uzaktaki parçacıklar, gerçek durumun daha olası olduğu alana hareket eder. Optimize edilmiş partikül filtresi algoritması, partiküllerin etkisini artırır ve yerel optimizasyon sorunlarını önler. Simülasyon sonuçları, geleneksel partikül filtresi ve partikül sürüsü optimizasyonu partikül filtresi algoritmasıyla karşılaştırıldığında, optimize edilmiş partikül filtresi algoritmasının, önemli ölçüde azaltılmış bir ortalama kare hatası olduğunu ve gerekli partikül sayısının, partikül bozulmasını etkili bir şekilde iyileştiren geleneksel partikül filtresi algoritmasından daha az olduğunu göstermektedir. Sorun, filtreleme doğruluğunu iyileştirin.
Çince alıntı biçimi: Liu Yuntao. Kelebek optimizasyonuna dayalı parçacık filtre algoritması J. Bilgi Teknolojisi ve Ağ Güvenliği, 2018,37 (7): 37-41.
0 Önsöz
Parçacık filtreleme, Monte Carlo düşüncesine [1] dayanan doğrusal olmayan Gaussian olmayan durum tahmin filtreleme yöntemidir ve hata teşhisi ve hedef izleme gibi ilgili alanlarda belirli uygulama etkilerine ulaşmıştır. Duan Zhuohua ve arkadaşları [2], parçacık filtrelerine dayalı bir mobil robot sensör arıza teşhis yöntemi önerdiler ve yöntemin mobil robotların bir veya daha fazla hatasını etkili bir şekilde tanımlayabildiğini doğruladılar. Cheng Jian ve arkadaşları [3], kızılötesi hedef takibine parçacık filtresi teorisini uyguladılar Partikül filtresi teorisi çerçevesinde, kızılötesi hedef durumunun posterior olasılık dağılımı ağırlıklı rastgele bir numune seti ile temsil edilir ve kızılötesi hedef, rastgele örneklerin Bayesci yinelemeli evrimiyle elde edilir. Izlemek. Bununla birlikte, yinelemelerin sayısı arttıkça, partikül önem ağırlıklarının varyansı gittikçe büyür, böylece partikül ağırlıkları birkaç partikül üzerinde yoğunlaşır ve diğer partiküllerin önemi ağırlıkları küçük olur.Bu, partikül bozunması olgusudur. DOUCET A ve arkadaşları [4] teorik olarak parçacık bozunmasının kaçınılmaz olduğunu kanıtladılar. Parçacık bozunması sorunu, parçacık filtrelemenin doğruluğunu ciddi şekilde etkileyecektir.
Partikül filtrelemedeki partikül bozunması problemi ile ilgili olarak, yurtiçi ve yurtdışındaki akademisyenler çok sayıda araştırma yaptılar. Zhang Qi ve arkadaşları [5], ağırlık seçimine dayalı bir partikül filtre algoritması önermiş, partikül ağırlığının boyutuna göre, örneklerin çeşitliliğini artırmak için filtreleme için daha iyi partiküller seçilmekte ve böylece partikül filtrelemenin bozunma problemi hafifletilmektedir. Xia Fei ve arkadaşları [6], yeniden örnekleme aşamasında en uygun olanın ağırlık sınıflandırması ve hayatta kalması için bir yeniden örnekleme algoritması benimsemiştir.Her partikülün normalleştirilmiş ağırlığı artan sırada düzenlenir ve partiküller ağırlığın varyansına göre elimine edilir. Böylelikle standart partikül filtresinin bozulma problemini bir dereceye kadar çözen iyileştirilmiş bir partikül filtresi algoritması elde edilir. Bununla birlikte, yukarıdaki iki yöntem hala geleneksel örnekleme çerçevesine dayanmaktadır ve parçacık bozunması sorununu tamamen çözemez.
Kelebek Algoritması (Kelebek Algoritması, BA), ARORA S ve SINGH S [7] tarafından önerilen kelebek yemleme davranışına dayanan küresel bir optimizasyon algoritmasıdır. Simülasyon, bu algoritmanın diğer doğal sezgisel algoritmalardan daha üstün olduğunu ve diğer algoritmalardan daha yüksek yakınsama doğruluğuna ve daha hızlı yakınsama hızına sahip olduğunu göstermektedir. Bu algoritmanın özelliklerinden esinlenen bu makale, partikül filtresi örnekleme sürecini optimize etmek için kelebek algoritmasını tanıtmaktadır ve simülasyon deneyleri aracılığıyla, kelebek optimize edilmiş partikül filtresi algoritmasının temel partikül algoritmasının filtre partikül bozulma problemini iyileştirebileceğini doğrulamaktadır.
1 Parçacık filtresi algoritması
Parçacık filtreleme, Monte Carlo düşüncesine dayanan bir Bayes tahmin yöntemidir [8]. Doğrusal olmayan bir sistemin durum uzayı modeli olduğunu varsayalım:
Bunlar arasında f (·) ve h (·) sırasıyla durum geçiş denklemi ve gözlem denklemidir. xt sistemin t anında durum değişkenidir, zt sistemin t anında gözlenen değeridir, wt ve vt sırasıyla sistemin işlem gürültüsü ve gözlem gürültüsü olan bağımsız seslerdir ve ut sistemin t anında girdisidir.
Filtreleme, arka filtreleme olasılık yoğunluğunu hesaplamaktır p (xt | z1: t). P (xt | z1: t) 'nin p (x0: t | z1: t)' nin kenar olasılık yoğunluğu olduğu bilinmektedir. Filtreleme olasılık yoğunluğunun p (xt-1 | z1: t-1) t-1'de bilindiğini varsayarsak, sistem durumu xt birinci dereceden Markov sürecine uyar ve sistem gözlemi zt bağımsızdır. Tarafından
T-1 zamanındaki gözlem değerini içeren t zamanında sistem durumunun önceki olasılık yoğunluğu p (xt | z1: t-1) elde edin:
Denklem (3), tahmin sürecidir, burada p (xt | xt-1) sistemin durum geçiş olasılık yoğunluğudur. T zamanında zt gözlenen değeri kullanılarak, p (xt | z1: t-1) güncellenerek ve revize edilerek, t zamanındaki sistem durumunun son olasılık yoğunluğu p (xt | z1: t) elde edilir ve durum güncellemesi Bayes teoremi ile elde edilebilir. denklem:
onların arasında
Bununla birlikte, doğrusal olmayan Gaussian olmayan sistemler için, (3) ve (4) denklemlerindeki ara parametrelerin ve diğer konumsal parametrelerin ortadan kaldırılmasını hesaplamak zordur ve böyle bir olasılık yoğunluk fonksiyonunu ifade etmek için tam bir analitik ifade elde etmek zordur. Bu nedenle, parçacık filtresi, tahmin edilecek dağılımı yaklaşık olarak belirlemek için arka olasılık yoğunluğundan p (xt | z1: t) çok sayıda rasgele örnek noktasından örneklemek için sıralı Monte Carlo örnekleme yöntemini kullanır. Bu rastgele örnek noktaları parçacık olarak adlandırılır. Posterior dağılımın tamamına yaklaşmak için çok sayıda partikül kullanılır Partikül sayısı yeterince büyük olduğunda, posterior dağılım doğru bir şekilde yaklaşık olarak tahmin edilebilir, bu da global yaklaşık optimal bir filtredir. Arka olasılık yoğunluğu p (xt | z1: t) 'den N parçacığın örneklendiğini varsayarsak, arka olasılık yoğunluğu aşağıdaki formülle tahmin edilebilir:
Bunlar arasında, xit, arka olasılık yoğunluğundan örneklenen parçacıkları temsil eder ve (·) Dirac delta fonksiyonunu temsil eder.
Ancak pratikte p (xt | z1: t) fonksiyonundan örnek almak zordur. Ağırlıklandırma için q (xt | z1: t) cinsinden x parçacıkları örnekleyerek, önceden bilinen ve örneklemesi kolay bir referans dağılımından q (xt | z1: t) ve yaklaşık p (xt | z1: t) örnekleyebilirsiniz. ). Önemli olasılık yoğunluğu olarak seçildiğinde
Önem ağırlık varyansı en küçük olduğunda, optimal önem olasılık yoğunluğudur. Ağırlık hesaplama denklemi:
Formül (8) 'de p (zt | xit-1) çözülemez, bu nedenle önem olasılık yoğunluğu olarak önceki olasılık yoğunluğunu seçmek daha yaygındır, yani
Formül,
Önem ağırlığını normalleştirin, yani
Son olasılık yoğunluğu şu şekilde ifade edilebilir:
Formülde önem ağırlığı formül (11) 'de gösterilmiştir. N olduğunda, büyük sayılar teoreminden denklemin (12) gerçek arka olasılığa p (xt | z1: t) yaklaştığı bilinmektedir.
2 Kelebek optimize edilmiş partikül filtresi
2.1 Kelebek algoritması
Kelebek algoritması, doğal bir sezgisel küresel optimizasyon algoritmasıdır. Ana fikri, bir kelebek grubunun yiyecek arama davranışına benzer. Her kelebek belirli bir yoğunlukta koku yayacak ve her kelebek, etrafındaki diğer kelebeklerin kokusunu hissedecek ve ona doğru hareket edecektir. Daha fazla koku yayan kelebeklerle hareket edin. Bir kelebeğin kokusu üç faktöre bağlıdır: algılama formu, uyaran yoğunluğu ve güç indeksi. Şeklinde açıklanan
F = cIa (13)
Bunlar arasında, F koku konsantrasyonunu, c algı formunu, I uyaran yoğunluğunu ve a güç indeksini temsil eder.
F (x) hedef fonksiyonu göz önüne alındığında, kelebek algoritmasının temel adımları aşağıdaki gibidir:
(1) n kelebek ile bir kelebek popülasyonunu başlatın ve f (xi) amaç fonksiyonu ile her bir xi kelebeğinin uyarma yoğunluğunu Ii belirleyin.
(2) Kelebek popülasyonundaki her kelebeğin uygunluk değerini hesaplayın ve en iyi konuma sahip kelebeği bulun.
(3) Kelebeğin kokusunu hesaplayın. Dış ortamın müdahalesi nedeniyle, kelebeğin yerel bir arama mı yoksa küresel bir arama mı yaptığını belirlemek için rastgele bir p sayısı üretilir.
(4) Küresel bir arama yapılırsa, kelebek en yüksek küresel uygunluğa sahip kelebeğe uçar, küresel arama şu şekilde ifade edilebilir:
Bunlar arasında, xt + 1i, i-inci kelebeğin t-inci iterasyonundaki çözüm vektörüdür. g * tüm kelebekler arasında en iyi çözümü temsil eder.
(5) Yerel bir arama yapılırsa, kelebek Lévy'nin rastgele uçuşunu gerçekleştirir. Yerel arama şu şekilde ifade edilebilir:
Kelebek hareketinin yerel optimum seviyeye düşmesini önlemek için, Lévy uçuşu algoritmaya dahil edilir.Levy uçuşu esasen rastgele bir yürüyüştür ve adım boyutu dağılımı, ağır kuyruk olasılık dağılımına uygundur:
Lévy uçuşu yerel aramayı hızlandırabilir ve arama verimliliğini artırabilir. Bu yazıda, 'nın değer aralığı (1,2] 'dir.
2.2 Kelebek algoritması ve parçacık filtresinin birleşmesi
Kelebek algoritmasında kelebek, partikül filtresindeki partikül olarak kabul edilir, kelebek algoritması ile partikül filtresi arasında belli bir benzerlik olduğu görülebilmektedir. Öncelikle kelebek algoritmasındaki kelebek, gerçek sistem durumuna sürekli yaklaşan partikül filtresi algoritmasındaki partiküllerin posterior olasılık dağılımına benzer şekilde, sürekli olarak konumunu güncelleyerek kelebeğe en yüksek uyarlanabilirlikle uçar. İkincisi, kelebek algoritmasında en yüksek uygunluğa sahip kelebek popülasyondaki optimal değerdir Partikül filtresi algoritmasına benzer şekilde, en büyük önem ağırlığına sahip partikül büyük olasılıkla gerçek posterior dağılımdadır.
Bu makale, partikül filtresinin performansını artırmak için partikül filtresi örnekleme sürecine kelebek algoritması optimizasyonu fikrini tanıtmaktadır. Bununla birlikte, kelebek optimizasyon algoritması doğrudan partikül filtresi ile birleştirilirse birçok soruna neden olacaktır.Bu nedenle, partikül filtresini optimize etmek için kelebek algoritmasının tanıtılması sürecinde aşağıdaki modifikasyonların yapılması gerekmektedir:
(1) Geleneksel partikül filtrelemenin önem olasılık yoğunluğu, önceki olasılık yoğunluğudur ve mevcut andaki gözlem değeri kaybolur, bu nedenle kelebeğin uygunluk değeri hesaplanırken en son gözlem değeri kullanılır. Bu nedenle, bir kelebeğin uygunluk değerini hesaplamak için denklem şu şekilde tanımlanır:
Bunlar arasında, Rk gözlenen gürültünün varyansı, znew en son gözlem ve zpred tahmin edilen gözlemdir.
(2) Kelebeğin hareketi sırasında, her kelebek bilinen mevcut optimal değere yaklaşacaktır. Kelebek algoritmasının global arama denkleminde, g * -xti kelebeğin hareket yönünü belirlemiştir, ancak Lévy uçuşu negatif bir değere sahip olduğunda, kelebek optimum değerin tersi yönde hareket ederek geçersiz tekrarlanan hesaplamalara neden olacaktır. Bu nedenle, Lévy uçuşunun mutlak değeri alınmalıdır. Geliştirilmiş global arama denklemi şu hale gelir:
(3) Kelebek algoritmasının global arama denkleminde (18) ve yerel arama denkleminde (15), Lévy uçuş değeri ve Fi değeri çok küçük olduğunda, kelebeğin konumu temelde hareket etmeyecek ve bu da geçersiz konum güncellemesine neden olacaktır. Bu nedenle, kelebeğin güncellenmiş yer değiştirmesi çok küçük olduğunda, fiili duruma göre uygun şekilde genişletilmesi gerekir.
Özetle, kelebek algoritması ile optimize edilmiş partikül filtresinin (BA-PF) uygulaması aşağıdaki gibidir:
(1) Başlatma. Önem olasılık yoğunluk işlevi olarak önceki olasılığı seçin ve önem işlevinden N parçacık oluşturun
(2) Tahmin. Durumu formül (1) ile hesaplayın
(3) En uygun değeri bulun. Parçacık filtresindeki her parçacığı, kelebek algoritmasında bir kelebek olarak düşünün. Uygunluk fonksiyonu formülü (17) ile her parçacığın uygunluk değerini hesaplayın ve formül (19) aracılığıyla global optimal parçacık g *, yani en büyük uygunluk değerine sahip kelebeği bulun.
(4) Her bir parçacığın koku Fi değerini hesaplamak için denklem (13) 'ü kullanın ve parçacığın global arama için denklem (18)' i mi yoksa yerel arama için denklem (16) 'yı kullanıp kullanmadığını belirlemek için rastgele bir r sayısı oluşturun. Yineleme sayısı maksimum M sayısına ulaştığında yineleme durdurulur.
(5) Optimize edilmiş parçacıkların önem ağırlığını güncelleyin ve normalleştirin.
(6) Yeniden Örnekleme. Etkili parçacık Neff, etkili numune eşiği Nth'den düşükse, yani
Yeniden örnekleyin. Yeni bir parçacık seti edinin
.
(7) Durum tahmini. kullanım
Durum tahmini yapın.
(8) Algoritmanın devam edip etmediğini belirleyin, devam ederse adım (2) 'ye dönün, aksi takdirde algoritma sona erer.
3 Deneysel sonuçlar ve analiz
Deneysel donanım ortamı bir dizüstü bilgisayardır (Intel Core i7 işlemci, 16 GB bellek) ve deneysel yazılım ortamı MATLAB 2016a'dır. İyileştirilmiş partikül filtresinin etkinliğini doğrulamak için, kelebek optimize edilmiş partikül filtresi algoritması (BA-PF), geleneksel partikül filtresi (PF) ve kokusuz Kalman filtre optimizasyonuna (UPF) dayalı partikül filtresi ile karşılaştırılır. Bu makale literatürü benimser [9] Sistemdeki doğrusal olmayan sistem, sistemin durum denklemi ve ölçüm denklemi:
Bunlar arasında, 1 = 0.5, 2 = 0.2, 3 = 0.5, = 0.04, işlem gürültüsü w Gama (3,2) gama gürültüsü ve gözlem gürültüsü v, ortalama değeri sıfır ve varyansı 0.0001 olan Gauss gürültüsüdür. Yukarıda bahsedilen doğrusal olmayan model sisteminin durumunu tahmin etmek ve izlemek için üç algoritma kullanılır. Kök ortalama kare hatası ERMSE, her filtreleme algoritmasının performansını ölçmek için kullanılır. Kök ortalama kare hata formülü şöyledir:
Deneysel algoritma parametre ayar değeri referansı Tablo 1'de gösterilmiştir.
Simülasyon, Tablo 2'de gösterildiği gibi, N = 20, N = 40 ve N = 100 farklı partikül numaraları altında üç partikül filtre algoritmasının filtreleme doğruluğunu ve çalışma süresini karşılaştırır. Şekil 1, bağımsız bir simülasyon koşulu altında parçacık sayısı N = 20 olduğunda üç parçacık filtresi algoritmasının durum tahminini gösterir ve Şekil 2, karşılık gelen simülasyon işleminde üç parçacık filtresi algoritmasının tahmini hatasının mutlak değerini gösterir.
Şekil 1, Şekil 2 ve Tablo 2'den BA-PF algoritmasının karekök ortalama karesel hatasının PF algoritması ve UPF algoritmasından önemli ölçüde daha küçük olduğu görülmektedir.Aynı zamanda BA-PF algoritması, parçacık sayısı az olduğunda yüksek filtreleme doğruluğuna sahip olabilmektedir. Bunun temel nedeni, BA-PF algoritmasının geçersiz partikülleri yüksek olasılıklı alanlara hareket ettirerek partiküllerin etkisini artırabilmesidir. PF algoritması, t = 16'dan t = 22'ye kadar olduğu gibi, parçacık sayısı küçük olduğunda durum tahminini kaybetmesi kolaydır. UPF, kokusuz Kalman filtrelemesini sunduğu için, filtreleme doğruluğu PF algoritmasından daha yüksek, ancak BA-PF algoritmasından daha düşüktür.
Farklı partikül filtre algoritmalarının sağlamlığını test etmek için, t = 40 ve t = 45 zaman noktalarında ani durum değişiminin bağımsız simülasyonu, genlik 15'tir. Şekil 3, üç partikül filtresi algoritmasının partikül sayısı N = 20 ve ani bir değişiklikten sonraki durum tahmin sonuçlarını gösterir ve Şekil 4, karşılık gelen üç partikül filtre algoritmasının tahmin hatalarının mutlak değerlerini gösterir. Tablo 2'den BA-PF algoritmasının yürütme süresinin PF algoritmasının yürütme süresinden biraz daha yüksek, ancak UPF algoritmasının yürütme süresinden çok daha düşük olduğu da görülebilir.
Şekil 3 ve Şekil 4'ten, durum değerinin t = 40 ve t = 45'te atladığı ve hem PF algoritmasının hem de UPF algoritmasının bariz tahmin sapmalarına sahip olduğu ve PF algoritmasının en bariz olanı olduğu görülebilir. Bununla birlikte, BA-PF algoritması Lévy rastgele uçuşu sunarak yerel optimal problemden kaçınıyor ve belirgin bir sapma meydana gelmiyor.Bu, BA-PF algoritmasının sistem durumundaki ani değişikliklere güçlü bir şekilde uyarlanabilir ve algoritmanın yüksek sağlamlığına sahip olduğunu gösteriyor. Özetle, BA-PF algoritması, önemli örnekleme sürecinde kelebek optimizasyon algoritmasını tanıttığı için, partikül bozunma fenomenini etkili bir şekilde iyileştirir ve filtreleme doğruluğunu iyileştirir.
4. Sonuç
Bu makale, kelebek optimizasyonuna dayalı bir partikül filtre algoritması önermektedir.Kelebek algoritması, geleneksel partikül filtrelemenin önemli örnekleme sürecini optimize etmek için tanıtılmıştır ve partikülleri gerçek durumun daha muhtemel olduğu alanlara taşımak için gerçek durumdan uzağa yönlendirerek partikül filtrelemenin varlığını etkili bir şekilde iyileştirir. Partikül bozulması sorunu, partikül filtresinin filtreleme doğruluğunu iyileştirir. Aynı zamanda BA-PF algoritması, kelebek arama modunu ve Lévy'nin rastgele uçuşunu değiştirerek yerel optimuma düşmeyi önler. Deneysel sonuçlar, BA-PF algoritmasının, parçacık sayısı az olduğunda etkili filtreleme sağlayabildiğini ve PF algoritmasından daha iyi filtreleme performansına sahip olduğunu ve algoritmanın yüksek sağlamlığa sahip olduğunu göstermektedir.
Referanslar
1 PARK S, HWANG J P, KANG H J, ve diğerleri.Örnek yoksullaşmasının önlenmesi için yeni bir evrimsel parçacık filtresi J. IEEE İşlemleri Evrimsel Hesaplama, 2009, 13 (4): 801-809.
[2] Duan Zhuohua, Cai Zixing, Yu Jinxia ve diğerleri Parçacık filtresine dayalı mobil robot atalet navigasyon sensörünün hata teşhisi J. Central South University Dergisi (Natural Science Edition), 2005, 36 (4): 642-647.
[3] Cheng Jian, Zhou Yue, Cai Nian ve diğerleri, partikül filtresine dayalı kızılötesi hedef takibi J. Journal of Infrared and Millimeter Waves, 2006, 25 (2): 113-117.
4 DOUCET A, GODSILL S, ANDRIEU C. Bayes filtreleme için sıralı Monte Carlo örnekleme yöntemleri hakkında M. Kluwer Academic Publishers, 2000.
[5] Zhang Qi, Hu Changhua, Qiao Yukun Ağırlık seçimine dayalı partikül filtre algoritması üzerine araştırma J Kontrol ve Karar, 2008, 23 (1): 117-120.
[6] Xia Fei, Hao Shuotao, Zhang Hao, ve diğerleri Buhar türbini arıza teşhisinde geliştirilmiş partikül filtresinin uygulanması J Bilgisayar Ölçümü ve Kontrolü, 2016, 24 (1): 35-38.
7 ARORA S, SINGH S. Küresel optimizasyon için Lèvy Uçuşları ile Kelebek algoritması C. Uluslararası Sinyal İşleme, Hesaplama ve Kontrol Konferansı. IEEE, 2016: 220-224.
8 GORDON N J, SALMOND D J, SMITH A F M. Doğrusal olmayan / Gaussian olmayan Bayesçi durum tahminine yeni yaklaşım J. IEE Proceedings F-Radar and Signal Processing, 2002, 140 (2): 107-113.
9 DOUCET A, FREITAS N D, WAN E. Kokusuz partikül filtresi C. Nöral Bilgi İşlem Sistemleri, NIPS, 2001: 584-590.
Yazar hakkında:
Liu Yuntao (1991-), erkek, yüksek lisans derecesi, ana araştırma yönü: gömülü sistem, yapay zeka.
İş teklifleri
Eğitim Bilgileri
Ayrıca ziyaret etmek için URL'ye de tıklayabilirsiniz
