İkili Parçacık Sürüsü ve Genetik Algoritmaya Dayalı Veri Tahsisi Araştırması
Li Shiwen 1, Zhang Hongmei 1, Zhang Xiangli 1, Ban Wenjiao 2
(1. Guilin Elektronik Teknolojisi Üniversitesi, Guangxi Üniversitesi Bulut Bilişim ve Karmaşık Sistemler Anahtar Laboratuvarı, Guilin 541000, Guangxi, Çin;
2. Guilin Elektronik Teknolojisi Üniversitesi, Eğitim Bakanlığı, Bilişsel Radyo ve Bilgi İşlem Anahtar Laboratuvarı, Guilin, Guangxi 541000)
İyileştirilmiş genetik algoritma veri dağıtım yöntemine dayalı olarak, optimal dağıtım planı ve işletim verimliliğinin araştırılması gibi mevcut dağıtılmış veri tabanı veri dağıtım yönteminin eksiklikleri göz önüne alındığında, ikili parçacık sürüsü algoritması tanıtılmış ve bir ikili parçacık sürüsü algoritması önerilmiştir. Genetik algoritmalı veri dağıtım yöntemi, ikili parçacık sürüsü algoritmasının sadece hızlı çalışma hızı ve iyi hafıza işlevi özelliklerine sahip olmakla kalmaz, aynı zamanda genetik algoritmanın küresel arama ve mutasyon yeteneğine de sahiptir. Bu tahsis yöntemi, arama verimliliğini artırabilir ve global optimal çözümü hızlı ve etkili bir şekilde elde edebilir. Deneysel sonuçlar, önerilen veri tahsis yönteminin, global optimal çözümü aramada genetik algoritmaya dayalı tahsis yönteminden üstün olduğunu ve arama hızı açısından sayım yöntemi ve genetik algoritmaya dayalı tahsis yönteminden daha hızlı olduğunu göstermektedir.
Genetik algoritma; ikili parçacık sürüsü algoritması; veri dağıtımı; arama verimliliği; optimum çözüm
Çin Kütüphanesi Sınıflandırma Numarası: TP311
Bir
DOI: 10.16157 / j.issn.0258-7998.2016.07.031
Çince alıntı biçimi: Li Shiwen, Zhang Hongmei, Chen He, vb. İkili Parçacık Sürüsü ve Genetik Algoritmaya Dayalı Veri Tahsisi Araştırması Elektronik Teknoloji Uygulaması, 2016, 42 (7): 122-125, 129.
İngilizce alıntı biçimi: Li Shiwen, Zhang Hongmei, Chen He, ve diğerleri Hibrit ikili parçacık sürüsü ve genetik algoritmaya dayalı veri tahsis probleminin araştırılması.Elektronik Tekniğin Uygulanması, 2016, 42 (7): 122-125, 129.
0 Önsöz
Günümüzde dağıtık veritabanı sistemleri yaygın olarak kullanılmaktadır ve veri dağıtımının performansı üzerindeki etkisi son derece önemlidir. Veri dağıtımı sorununun açıklaması: Bir ağın S = (S1, S2, ..., Sn) bir site setinden oluştuğunu, ağ üzerinde bir işlem setinin T = (T1, T2, ..., Tq) yürütüldüğünü ve bir veri parçası setinin depolandığını varsayalım. F = (F1, F2, ..., Fm), her Fj fragmanının farklı kopyalarını farklı Sk sitelerine belirli bir şekilde tahsis eder, tahsis planı D olarak ifade edilir < F, S, T > . Toplam tahsis planından daha optimize edilmiş bir tahsis planı elde edilebilirse, tüm dağıtılmış veritabanı sisteminin performansı ve güvenilirliği büyük ölçüde geliştirilecektir.
1 Araştırma durumu
Şu anda, veri dağıtımı sorununu incelemek için yurtiçi ve yurtdışında birçok belge var. Fayda maliyet optimizasyonuna dayalı sezgisel tahsis yöntemi, tasarım açısından karmaşıktır ve hesaplama açısından pahalıdır; literatür, veri parçalarının erişim özelliklerine dayalı bir tahsis stratejisi önermektedir, ancak bu strateji, aramanın yerel optimal çözüme düşmesinin kolay olduğu sorununu çözemez. Bazı bilim adamları, veri tahsisi sorununu çözmek için genetik algoritma (GA) kullanırlar. Literatür, küresel arama yeteneklerine sahip olan ve yerel optimal aramaya düşmeyi önleyebilen, genetik algoritmaya dayalı bir veri tahsis yöntemi önermektedir, ancak arama süreci rastgeledir ve eksiktir. Hafıza fonksiyonu, yavaş arama hızı ve istenen sonuç ile optimum çözüm arasında belirli bir boşluk vardır.
İkili Parçacık Sürüsü Optimizasyonu (BPSO) bir hafıza işlevine sahiptir ve arama hızını artırabilir. Bu makalede, genetik algoritma, dağıtılmış veri tabanı veri dağıtımının maliyet formülünü ve uygunluk fonksiyonunu hedefleyen ikili parçacık sürüsü algoritması ile birleştirilerek, hibrit ikili parçacık sürüsü ve genetik algoritmaya (Hibrit BPSO ve GA, HBPSOGA) dayalı yeni bir yöntem önerilmiştir. Veri dağıtım yöntemi.
2 HBPSOGA'ya dayalı tahsis yönteminin analizi
2.1 İstatistikler ve maliyet formülü
2.1.1 Bu makalede kullanılan istatistikler
İstatistiksel bilgiler, veri dağıtımını çözmek için temel bilgidir ve erişim maliyetini, güncelleme maliyetini ve bireysel uygunluğu hesaplamak için kullanılır. İstatistiksel bilginin önemi, elde etme zorluğu ve maliyet formülünün karmaşıklığı üzerindeki etkisine göre Tablo 1'den istatistiksel bilgiler elde edilir.
2.1.2 Maliyet formülü seçimi
Maliyet metriği Min (Toplam Maliyet). Her sitenin aynı işleme kapasitesine sahip olduğunu varsayarsak, erişilen toplam veri miktarı maliyet formülünü ifade etmek için kullanılır, dolayısıyla bu makalede kullanılan maliyet formülü şöyledir:
Bunların arasında, Fj parçası, Sk sitesinde Ti yürütme işlemi tarafından erişilen veri parçasıdır ve Sf, Fj'nin herhangi bir kopyasının bulunduğu, yani veri parçasının Fj kopyalarına sahip olan tüm sitelerdir.
2.2 Genetik algoritma ve iyileştirme
Genetik algoritma, biyolojinin genetik ve evrimsel sürecini simüle ederek oluşturulan küresel bir olasılık arama algoritmasıdır. Veri dağıtım problemini çözmek için klasik genetik algoritmaların kullanılması nedeniyle, optimum dağıtım şeması hızlı bir şekilde bulunamamıştır. Bu nedenle, bu makale klasik genetik algoritmada aşağıdaki iyileştirmeleri yapmaktadır:
(1) Popülasyonu başlatırken, önce veri segmentinin güncelleme alma oranını hesaplayın ve ardından veri segmentinin güncelleme alma oranına göre popülasyonu başlatın. (4) ve (5) formüllerine göre parçanın erişim ziyaretlerinin ve güncelleme ziyaretlerinin sayısını hesaplayın:
Tüm sitelerin erişim ziyaretlerinin Fj segmentine eklenmesiyle elde edilen değer Q ve tüm sitelerin güncelleme ziyaretlerinin Fj segmentine eklenmesiyle elde edilen değer U'dur. Veri parçasında U / Q ise < 1. Grubu başlatırken, geri alma iletişiminin maliyetini düşürmek için siteye tahsis etmek üzere daha fazla kopyasını ayarlamanız gerekir; veri segmenti U / Q ise > 1. Birden çok kopya arasında veri tutarlılığının güncelleme maliyetini azaltmak için daha az kopya ayarlamanız gerekir.
(2) Bireyler geçiş ve mutasyon işlemlerini gerçekleştirdiklerinde, algoritmanın arama hızını ve çözüm kalitesini iyileştirebilen sırasıyla denklem (6) ve (7) 'de gösterildiği gibi kendi kendini ayarlayan çaprazlama operatörleri ve kendi kendini ayarlayan mutasyon operatörleri kullanılır.
2.3 İkili parçacık sürüsü algoritması
Parçacık sürüsü algoritması, biyolojik popülasyonların (kuşlar ve balıklar) yiyecek arama davranışını taklit eden bir arama algoritmasıdır. Bununla birlikte, standart PSO algoritması yalnızca sürekli arama alanı hesaplamaları için uygundur ve ayrık arama alanları için doğrudan kullanılamaz. Bu nedenle, araştırmacılar, ayrık ikili uzay problemini çözmek için parçacık sürüsü optimizasyonunun (BPSO) ikili bir versiyonunu önerdiler.
İkili PSO algoritmasının hız güncelleme formülü şöyledir:
Hızın değerini, konumun 1 alma olasılığı olarak ifade etmek için, hızın değeri aralığa eşlenir. Haritalama yöntemi, formül (9) Sigmoid fonksiyonunu kullanır:
2.4 HBPSOGA'ya dayalı veri dağıtım yöntemi
İkili parçacık sürüsü algoritması basit bir yapıya, hızlı çalışma hızına ve hafıza işlevine sahiptir, ancak yerel optimuma düşmesi kolaydır ve sözde erken yakınsama fenomeni ortaya çıkar. Genetik algoritmanın çok çeşitli küresel arama yetenekleri vardır ve yerel olarak optimuma düşmek kolay değildir, ancak arama hızı yavaştır ve hafıza işlevinden yoksundur. Geliştirilmiş genetik algoritmaya dayalı veri dağıtım yöntemine dayanan bu makale, ikili parçacık sürüsü algoritmasını tanıtmakta ve yalnızca arama hızını artırmakla kalmayıp aynı zamanda yerel optimuma düşmeyi önleyen ve başarı oranını artıran bir hibrit algoritma veri dağıtım yöntemi önermektedir.
Her veri bölümü için, veri bölümünün dağıtım planını elde etmek için bu yazıda HBPSOGA'yı kullanın ve son olarak genel dağıtım planını alın. Aşağıda, bir segmenti tahsis etmek için bu yöntemi kullanmanın belirli adımlarına ayrıntılı bir giriş yer almaktadır:
(1) Maksimum yineleme sayısı Nmax, popülasyon boyutu PopSize, maksimum hız vmax, parçacık sürüsü atalet faktörü w ve öğrenme faktörleri c1, c2 dahil olmak üzere parametre başlatma.
(2) Veri segmentinin güncelleme alma oranını hesaplayın ve Pop = (xij) N × m popülasyonunu, veri segmentinin güncelleme alma oranına göre başlatın; burada N PopSize, birey sayısı ve m, problemin boyutudur, yani İstasyon sayısı; her birey ikili kodlama kullanır ve kod uzunluğu istasyonların sayısına eşittir.Veri parçaları istasyon Sj'ye tahsis edildiğinde, xij = 1, aksi takdirde xij = 0.
(3) Bir bireyin uygunluğunu şu şekilde tanımlayın:
Formülde: TQ ve TU, toplam sorgu maliyetini ve toplam güncelleme maliyetini temsil eder. Ayrıntılar için bkz. Formül (2) ve (3).
(4) Pop popülasyonundaki tüm bireylerin uygunluğunu hesaplayın, bireyleri seçmek için elitizmi kullanın ve Pop popülasyonu oluşturun. Elitist operasyonu, yüksek uyarlanabilirliğe sahip bireyleri tutmak ve düşük uyum yeteneği olan bireyleri ortadan kaldırmaktır.
(5) Pop 'popülasyonundaki tüm bireylerin uygunluğunu hesaplayın ve değerlendirin, kromozom çiftlerini seçmek için rulet yöntemini kullanın ve Pop popülasyonunu elde etmek için Pc olasılığı ile formül (6)' ya göre çaprazlama işlemleri gerçekleştirin. Bir çapraz nokta rastgele belirlenir ve iki yeni birey oluşturmak için iki bireyin genleri kesişme noktasında değiştirilir.
(6) Pop popülasyonundaki bireyler için, popülasyonu elde etmek için formül (7) 'nin Pm olasılığına göre mutasyon işlemi gerçekleştirin.Mutasyon işlemi: Bireyin geni 1 ise 0, 0 ise 1 olur. .
(7) Popülasyondaki tüm bireylerin uygunluğunu hesaplayın, bireysel optimal pozisyon Pbest ve global optimal pozisyon Gbest'i elde edin ve bir popülasyon oluşturmak için sırasıyla denklem (8) ve (10) 'a göre popülasyondaki tüm bireylerin hızını ve pozisyonunu güncelleyin Pop.
(8) Yineleme sayısı maksimum yineleme sayısına Nmax ulaştıysa, algoritma sona erer ve adım (9) 'a gidin, aksi takdirde adım (4)' e gidin.
(9) Soruna en uygun çözüm olarak en uygun kişiyi çıkarın.
3 Deney ve analiz
3.1 Deney ortamı
Deneyde, üç adet dağıtılmış ortam kullanılmıştır. İlk ortam 2 parça, 3 işlem ve 4 site içerir. İkinci ortam 3 parça, 3 işlem ve 5 site içerir. Üçüncü ortam, 10 parça, 5 işlem ve 10 site ile daha karmaşıktır. Dağıtılmış bir ortamda n parça ve m istasyon varsa, (2m-1) n çeşit tahsis şeması vardır. Bu nedenle, bu üç ortamda, veri dağıtım şemaları sırasıyla 225, 29791 ve (1023) 10'dur.
Her bir dağıtılmış ortamda rastgele bir dizi istatistiksel bilgi oluşturulur.Her istatistiksel bilgi kümesine göre, veri dağıtımı için sayımın dağıtım yöntemi, bu makalenin dağıtım yöntemi ve genetik algoritmaya dayalı dağıtım yöntemi kullanılır ve geri alma ve güncelleme hesaplanır. İstatistiksel dağıtım yönteminin toplam maliyeti çalışma süresidir. Numaralandırma algoritmasının tahsis yöntemi, tüm tahsis planlarını dolaşıma sokmaktır, amaç, optimum çözüm tahsis planını elde etmek ve daha sonra bu makalede önerilen tahsis yöntemi ve genetik algoritmaya dayalı tahsis yöntemi ile karşılaştırmaktır. Genetik algoritmaya dayalı tahsis yöntemi referanstır. Üç veri ayırma yönteminin tümü aynı makinede çalışıyor Makine yapılandırması: CPU i3-2323M 2.20 GHz, bellek 4 GB.
3.2 Deneysel analiz
İlk istatistiksel bilgi grubu için (bkz.Tablo 2), veri dağıtımı için bu makalenin dağıtım yöntemi kullanılırken, parametreler şu şekilde ayarlanır: PopSize = 5, w = 0.8, c1 = c1 = 2, vmax = 4, Nmax = 50.
İkinci istatistiksel bilgi grubu için (bkz.Tablo 3), veri dağıtımı için bu makalenin dağıtım yöntemi kullanılırken, parametre değerleri şu şekilde ayarlanır: PopSize = 6, w = 0.8, c1 = c1 = 2, vmax = 4, Nmax = 50.
Üçüncü istatistiksel bilgi grubu için (bkz.Tablo 4), veri dağıtımı için bu makalenin dağıtım yöntemi kullanılırken, parametreler şu şekilde ayarlanır: PopSize = 11, w = 0.8, c1 = c1 = 2, vmax = 4, Nmax = 100.
3 set istatistiksel bilgi üzerine deneyler ve deneysel sonuçlar Tablo 5'te gösterilmektedir. Toplam maliyetin elde edilmesi açısından, bu yazıda önerilen tahsis yöntemi, minimum toplam maliyet tahsis şemasını elde edebilen numaralandırma yöntemi ile aynıdır. Ancak genetik algoritmaya dayalı tahsis yöntemi bunu yapamaz. Harcanan zaman açısından, bu makaledeki dağıtım yöntemi en kısa çalışma süresine sahiptir. Bu makaledeki yöntemin performansı ile her popülasyon yinelemesinde genetik algoritmaya dayalı yöntemin karşılaştırılmasıyla sonuçlar Şekil 1, 2 ve 3'te gösterilmektedir. HBPSOGA'ya dayalı yöntemin GA'ya dayalı yönteme göre daha fazla toplam maliyet değeri elde ettiği görülmektedir. Küçüktür ve aynı toplam maliyet değeri altında daha az yineleme çalıştırır, bu da HBPSOGA'ya dayalı yöntemin aramanın daha hızlı olduğunu gösterir. Deney, bu yazıda yöntemle elde edilen çözümün en uygun çözüm olduğunu ve en uygun çözümün daha hızlı aranabileceğini göstermektedir. Bu, bu yazıda kullanılan dağıtım yönteminin, numaralandırma ve genetik algoritmaya dayalı dağıtım yönteminden daha iyi olduğunu göstermektedir.
4. Sonuç
Bu makale, genetik algoritmanın ve ikili parçacık sürüsü algoritmasının ilgili avantajlarını analiz etmekte ve genetik algoritmayı biraz iyileştirmektedir.Dağıtılmış veri tabanı veri dağıtımı problemini çözerken, deneysel testleri geçen hibrit ikili parçacık sürüsü ve genetik algoritmaya dayalı bir veri dağıtım yöntemi önerilmiştir. Bu yöntemin veri dağıtımındaki etkisi gösterilmiştir. Optimal çözümü elde etme ve arama hızı açısından numaralandırma yöntemine dayalı tahsis yöntemi ve genetik algoritmaya dayalı tahsis yöntemi ile karşılaştırılır. Deneysel sonuçlar, diğer iki yöntemle karşılaştırıldığında, bu yöntemin daha yüksek arama verimliliği ve daha hızlı çözüm hızı özelliklerine sahip olduğunu ve küresel optimal çözümü elde edebileceğini tam olarak göstermektedir.
Referanslar
Lai Ling. Dağıtılmış Veritabanı Sistemi Araştırması. Yazılım Kılavuzu, 2009, 8 (9): 169-170.
ISMAIL O H, MUTHU R, NICHOLAS B. Dağıtılmış veritabanı sistemlerinde veri tahsisi için yüksek performanslı bir hesaplama yöntemi Springer Science, 2007, 39 (1): 3-18.
Yang Zhou. Dağıtılmış Veritabanında Veri Tahsis Stratejisi Araştırması Harbin: Harbin Mühendislik Üniversitesi, 2007.
RAHMANI S, TORKZABAN V, T. HAGHIGHAT A. Dağıtılmış sistemlerde veri tahsisi için yeni bir genetik algoritma yöntemi.Eğitim Teknolojisi ve Bilgisayar Bilimi, First International Workshop on Wuhan, Hubei: IEEE Press, 2009.
PORTALURI, PISA G U, İTALYA. Bulut bilişim veri merkezlerinde kaynak tahsisi için gücü verimli kullanan bir genetik algoritma Cloud Networking (CloudNet), 2014 IEEE 3. Uluslararası Konferansı, Lüksemburg: IEEE Press, 2014.
Li Xiang. Dağıtılmış veritabanı veri tahsis stratejisi üzerine araştırma Dalian: Dalian University of Technology, 2009.
Chen Xixiang, Qiu Jing, Liu Guanjun Hibrit ikili parçacık swarm_genetic algoritmasına dayalı test optimizasyonu seçimi üzerine araştırma. Chinese Journal of Scientific Instrument, 2009, 30 (8): 1674-1680.
He Lin, Ma Changlin Geliştirilmiş uyarlanabilir genetik algoritma ve performans araştırması Harbin: Çin Kontrol ve Karar Akademik Yıllık Konferansı, 2005: 895-898.
