Dağıtım algoritmasının tahmini - Estimation of distribution algorithm

Dağıtım algoritmasının tahmini. Her i yinelemesi için , bir Pdu dağılımındaki bir P popülasyonu için rastgele bir çizim yapılır . Dağıtım parametreleri PDe daha sonra seçilen noktalar PS kullanılarak tahmin edilir . Gösterilen örnek , benzersiz bir optimum O ile sürekli bir amaç fonksiyonunu f(X) optimize eder . Örnekleme ( N 'nin normal dağılımını izleyerek ), çözme algoritması boyunca optimum etrafında yoğunlaşır.

Bazen olasılıksal model oluşturma genetik algoritmaları (PMBGA'lar)olarak adlandırılan dağıtım algoritmalarının ( EDA'lar ) tahmini, gelecek vaat eden aday çözümlerin açık olasılıklı modellerini oluşturarak ve örnekleyerek optimum aramaya rehberlik eden stokastik optimizasyon yöntemleridir. Optimizasyon, kabul edilebilir çözümlere göre bilgi vermeyen bir önceliği kodlayan modelle başlayan ve yalnızca global optimumu üreten modelle biten, olasılıklı bir modelin bir dizi artımlı güncellemesi olarak görülür.

EDA'lar evrimsel algoritmalar sınıfına aittir . EDA'lar ve çoğu geleneksel evrimsel algoritma arasındaki temel fark, evrimsel algoritmaların bir veya daha fazla varyasyon operatörü tarafından tanımlanan örtük bir dağılım kullanarak yeni aday çözümler üretmesi , EDA'ların ise bir Bayes ağı , çok değişkenli bir normal dağılım veya başka bir şey tarafından kodlanmış açık bir olasılık dağılımı kullanmasıdır. modeli sınıfı. Diğer evrimsel algoritmalara benzer şekilde, EDA'lar vektörlerden LISP tarzı S ifadelerine kadar bir dizi temsil üzerinden tanımlanan optimizasyon problemlerini çözmek için kullanılabilir ve aday çözümlerin kalitesi genellikle bir veya daha fazla amaç fonksiyonu kullanılarak değerlendirilir.

Bir EDA'nın genel prosedürü aşağıda özetlenmiştir:

t := 0
initialize model M(0) to represent uniform distribution over admissible solutions
while (termination criteria not met) do
    P := generate N>0 candidate solutions by sampling M(t)
    F := evaluate all candidate solutions in P
    M(t + 1) := adjust_model(P, F, M(t))
    t := t + 1

Optimizasyonda açık olasılıklı modellerin kullanılması, EDA'ların, çoğu geleneksel evrimsel algoritma ve yüksek epistasisli problemler gibi geleneksel optimizasyon teknikleri için çok zor olduğu bilinen optimizasyon problemlerini uygulanabilir bir şekilde çözmesine izin verdi . Bununla birlikte, EDA'ların avantajı aynı zamanda bu algoritmaların bir optimizasyon uygulayıcısına çözülmekte olan problem hakkında birçok bilgiyi ortaya çıkaran bir dizi olasılıksal model sağlamasıdır. Bu bilgi, yerel arama için probleme özel komşuluk operatörleri tasarlamak, benzer bir problem üzerinde EDA'ların gelecekteki çalışmalarını saptırmak veya problemin verimli bir hesaplamalı modelini oluşturmak için kullanılabilir.

Örneğin, popülasyon 4 uzunluğundaki bit dizileri ile temsil ediliyorsa, EDA, dört olasılıktan (p1, p2, p3, p4) tek bir vektör kullanarak umut vaat eden çözüm popülasyonunu temsil edebilir, burada p'nin her bir bileşeni o olasılığı tanımlar. konum 1'dir. Bu olasılık vektörünü kullanarak rastgele sayıda aday çözüm yaratmak mümkündür.

Dağıtım algoritmalarının (EDA) tahmini

Bu bölüm, farklı karmaşıklık düzeylerinde iyi bilinen bazı EDA'lar tarafından oluşturulan modelleri açıklamaktadır. Bu bir nüfusa kabul daima edilir nesil , bir seçim operatörü , bir model-bina operatörü ve bir örnekleme operatörü . ${\görüntüleme stili P(t)}$${\görüntüleme stili t}$${\görüntüleme stili S}$${\görüntüleme stili \alfa }$${\görüntüleme stili \beta }$

Tek değişkenli çarpanlara ayırma

En basit EDA'lar, karar değişkenlerinin bağımsız olduğunu varsayar, yani . Bu nedenle, tek değişkenli EDA'lar yalnızca tek değişkenli istatistiklere dayanır ve çok değişkenli dağılımlar, tek değişkenli olasılık dağılımlarının ürünü olarak çarpanlara ayrılmalıdır , ${\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}$${\görüntüleme stili N}$

${\displaystyle D_{\text{Tek değişkenli}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).}$

Bu tür çarpanlara ayırma birçok farklı EDA'da kullanılır, daha sonra bunlardan bazılarını açıklayacağız.

Tek değişkenli marjinal dağıtım algoritması (UMDA)

UMDA, seçilen bir popülasyondan marjinal olasılıkları tahmin etmek için bir operatör kullanan basit bir EDA'dır . Öğeleri içerdiğini varsayarak , olasılıklar üretir: ${\displaystyle \alpha _{UMDA}}$${\görüntüleme stili S(P(t))}$${\görüntüleme stili S(P(t))}$${\ Displaystyle \ lambda }$${\displaystyle \alpha _{UMDA}}$

${\displaystyle p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.}$

Her UMDA adımı aşağıdaki gibi tanımlanabilir.

${\displaystyle D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).}$

Nüfusa dayalı artımlı öğrenme (PBIL)

PBIL, yeni çözümleri örneklediği ve modeli güncellediği modeliyle örtük olarak popülasyonu temsil eder. Her nesilde, bireyler örneklenir ve seçilir. Bu tür bireyler daha sonra modeli aşağıdaki gibi güncellemek için kullanılır. ${\görüntüleme stili \mu }$${\displaystyle \lambda \leq \mu }$

${\displaystyle p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P) (t))}x_{i},~\forall i\in 1,2,\dots ,N,}$

öğrenme oranını tanımlayan bir parametre burada , küçük bir değer, önceki modelin örneklenen yeni çözümler tarafından yalnızca biraz değiştirilmesi gerektiğini belirler . PBIL şu şekilde tanımlanabilir: ${\displaystyle \gamma \in (0,1]}$${\displaystyle p_{t}(X_{i})}$

${\displaystyle D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))}$

Kompakt genetik algoritma (cGA)

CGA, aynı zamanda, tek değişkenli dağılımlar tarafından tanımlanan örtük popülasyonlara da dayanır. Her nesilde , iki birey örneklenir, . Popülasyon daha sonra azalan uygunluk sırasına göre en iyi ve en kötü çözüm olacak şekilde sıralanır . CGA, tek değişkenli olasılıkları aşağıdaki gibi tahmin eder: ${\görüntüleme stili t}$${\görüntüleme stili x,y}$${\displaystyle P(t)=\beta _{2}(D(t))}$${\görüntüleme stili P(t)}$${\displaystyle S_{{\metin{Sırala}}(f)}(P(t))}$${\görüntüleme stili u}$${\görüntüleme stili v}$

${\displaystyle p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1, 2,\nokta ,N,}$

burada, genellikle olarak ayarlanan öğrenme oranını tanımlayan bir sabittir . CGA şu şekilde tanımlanabilir: ${\displaystyle \gamma \in (0,1]}$${\görüntüleme stili \gama =1/N}$

${\displaystyle D(t+1)=\alpha _{\text{CGA}}\circ S_{{\text{Sırala}}(f)}\circ \beta _{2}(D(t))}$

İki değişkenli çarpanlara ayırma

Tek değişkenli modeller verimli bir şekilde hesaplanabilmesine rağmen, çoğu durumda GA'lardan daha iyi performans sağlamak için yeterince temsil edici değildirler. Böyle bir dezavantajın üstesinden gelmek için, değişken çiftleri arasındaki bağımlılıkların modellenebildiği EDA topluluğunda iki değişkenli çarpanlara ayırmanın kullanılması önerildi. Bir çift değişkenli çarpanlara olduğu, aşağıdaki gibi tanımlanabilir bağımlı olası bir değişkeni içeren , yani . ${\displaystyle \pi _{i}}$${\displaystyle X_{i}}$${\displaystyle |\pi _{i}|=1}$

${\displaystyle D_{\text{İki değişkenli}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{ben}).}$

İki değişkenli ve çok değişkenli dağılımlar genellikle , kenarların istatistiksel bağımlılıkları (veya koşullu olasılıkları) ve tepe noktalarının değişkenleri ifade ettiği olasılıksal grafik modeller (grafikler) olarak temsil edilir . Bir PGM'nin yapısını veri bağlantısı-öğrenmeden öğrenmek için kullanılır.

Giriş kümelemeyi en üst düzeye çıkaran karşılıklı bilgi (MIMIC)

MIMIC, değişkenler arasındaki ardışık bağımlılıkları temsil eden zincir benzeri bir modelde ortak olasılık dağılımını çarpanlara ayırır . Bu karar değişkenlerinin bir permütasyon bulur , öyle ki en aza indirir Kullback-Leibler sapma gerçek olasılık dağılımı ile ilgili olarak, yani . MIMIC modelleri bir dağılım ${\displaystyle r:i\mapsto j}$${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1 }p_{t}(X_{r(i)}|X_{r(i+1)}).}$

Yeni çözümler en soldan en sağdaki değişkene doğru örneklenir, ilki bağımsız olarak, diğerleri koşullu olasılıklara göre üretilir. Tahmini dağılımın her nesilde yeniden hesaplanması gerektiğinden, MIMIC aşağıdaki şekilde somut popülasyonları kullanır.

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).}$

İki değişkenli marjinal dağıtım algoritması (BMDA)

BMDA, iki değişkenli dağılımlarda ortak olasılık dağılımını çarpanlara ayırır. İlk olarak rastgele seçilen bir değişken bir grafikte düğüm olarak eklenir, grafikte yer alan değişkenlerden birine en çok bağımlı olan değişken henüz grafikte olmayanlar arasından seçilir, bu işlem grafikteki herhangi bir değişkene bağımlı olmayana kadar bu işlem tekrarlanır. grafik (bir eşik değerine göre doğrulanmıştır).

Ortaya çıkan model, düğümlerde kök salmış birden çok ağaç içeren bir ormandır . Kök olmayan değişkenleri göz önünde bulundurarak , BMDA, kök değişkenlerin bağımsız olarak örneklenebileceği, diğerlerinin tümünün ana değişkene koşullandırılması gereken faktörlü bir dağılım tahmin eder . ${\ Displaystyle \ Upsilon _{t}}$${\ Displaystyle I_{t}}$${\displaystyle \pi _{i}}$

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i} )\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).}$

BMDA'nın her adımı aşağıdaki gibi tanımlanır

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).}$

Çok değişkenli çarpanlara ayırma

EDA'ların geliştirilmesinin bir sonraki aşaması, çok değişkenli çarpanlara ayırmanın kullanılmasıydı. Bu durumda, birleşik olasılık dağılımı genellikle sınırlı büyüklükteki bir dizi bileşende çarpanlara ayrılır . ${\displaystyle |\pi _{i}|\leq K,~\forall i\in 1,2,\dots ,N}$

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i})}$

Çok değişkenli dağılımları kodlayan PGM'lerin öğrenilmesi, hesaplama açısından pahalı bir iştir, bu nedenle, EDA'ların çok değişkenli istatistikleri iki değişkenli istatistiklerden tahmin etmesi olağandır. Böyle bir gevşeme, PGM'nin polinom zamanında ; bununla birlikte, bu tür EDA'ların genelliğini de sınırlar. ${\görüntüleme stili N}$

Genişletilmiş kompakt genetik algoritma (eCGA)

ECGA, karar değişkenleri arasındaki yüksek dereceli bağımlılıkların modellenebildiği çok değişkenli çarpanlara ayırma kullanan ilk EDA'lardan biriydi. Yaklaşımı, çok değişkenli marjinal dağılımların ürünündeki ortak olasılık dağılımını çarpanlara ayırır. Her birinin değişkenler içeren bir bağlantı kümesi olduğu bir alt küme kümesi olduğunu varsayalım . Faktörleştirilmiş ortak olasılık dağılımı aşağıdaki gibi temsil edilir ${\displaystyle T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}}$${\displaystyle \tau \T_{\text{eCGA}}}$${\displaystyle |\tau |\leq K}$

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau).}$

ECGA, "bağlantı-öğrenme" terimini, bağlantı kümelerini tanımlayan prosedürleri belirtmek için popüler hale getirdi. Bağlantı öğrenme prosedürü iki ölçüye dayanır: (1) Model Karmaşıklığı (MC) ve (2) Sıkıştırılmış Nüfus Karmaşıklığı (CPC). MC, tüm marjinal olasılıkları depolamak için gereken bit sayısı cinsinden model temsil boyutunu nicelendirir.

${\displaystyle MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),}$

CPC, diğer taraftan, tüm bölümlerde kenar dağılımı, entropi açısından veri sıkıştırma miktarını belirler seçilen nüfus boyutu, bağlantı grubu olarak karar değişkeni sayısıdır ve değişkenlerin bileşik entropi içinde${\ Displaystyle \ lambda }$${\görüntüleme stili |\tau |}$${\görüntüleme stili\tau }$${\görüntüleme stili H(\tau )}$${\görüntüleme stili\tau }$

${\displaystyle TBM=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ).}$

ECGA'daki bağlantı-öğrenme şu şekilde çalışır: (1) Her değişkeni bir kümeye yerleştirin, (2) mevcut bağlantı kümelerinin CCC = MC + CPC'sini hesaplayın, (3) küme çiftlerini birleştirerek sağlanan CCC'deki artışı doğrulayın, (4) en yüksek CCC iyileştirmesi ile bu kümelere etkin bir şekilde katılır. Bu prosedür, hiçbir CCC iyileştirmesi mümkün olmayana ve bir bağlantı modeli üretene kadar tekrarlanır . ECGA somut popülasyonlarla çalışır, bu nedenle ECGA tarafından modellenen faktörlü dağılım kullanılarak şu şekilde tanımlanabilir: ${\displaystyle T_{\metin{eCGA}}}$

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{eCGA}}\circ S(P(t))}$

Bayes optimizasyon algoritması (BOA)

BOA, gelecek vaat eden çözümleri modellemek ve örneklemek için Bayes ağlarını kullanır. Bayes ağları, değişkenleri temsil eden düğümler ve değişken çifti arasındaki koşullu olasılıkları temsil eden kenarlar ile yönlendirilmiş döngüsel olmayan grafiklerdir. Bir değişkenin değeri , içinde tanımlanan maksimum diğer değişkenler üzerinde koşullandırılabilir . BOA, ağın parametrelerinin, yani koşullu olasılıkların, maksimum olabilirlik tahmincisi kullanılarak seçilen popülasyondan tahmin edildiği, faktörleştirilmiş bir ortak dağılımı kodlayan bir PGM oluşturur. ${\displaystyle x_{i}}$${\görüntüleme stili K}$${\displaystyle \pi _{i}}$

${\displaystyle p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}) .}$

Bayes ağ yapısı ise yinelemeli olarak oluşturulmalıdır (bağlantı-öğrenme). Kenarları olmayan bir ağ ile başlar ve her adımda, bazı puanlama ölçütlerini (örneğin Bayes bilgi kriteri (BIC) veya olabilirlik eşdeğerli Bayes-Dirichlet ölçütü (BDe)) daha iyi geliştiren kenarı ekler. Puanlama metriği, seçilen popülasyonu modellemedeki doğruluğuna göre ağ yapısını değerlendirir. BOA, inşa edilmiş ağdan yeni gelecek vaat eden çözümleri aşağıdaki gibi örnekler: (1) her bir düğümden önce ebeveynleri gelecek şekilde her değişken için atasal sıralamayı hesaplar; (2) her değişken, ebeveynlerine koşullu olarak örneklenir. Böyle bir senaryo göz önüne alındığında, her BOA adımı şu şekilde tanımlanabilir:

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BOA}}\circ S(P(t))}$

Bağlantı Ağacı Genetik Algoritması (LTGA)

LTGA, bir olasılık dağılımını açık bir şekilde modellemediği, ancak yalnızca bağlantı ağacı adı verilen bir bağlantı modeli olduğu için çoğu EDA'dan farklıdır. Bir bağlantı , ilişkili bir olasılık dağılımı olmayan bir dizi bağlantı kümesidir, bu nedenle, yeni çözümleri doğrudan 'den örneklemenin bir yolu yoktur . Bağlantı modeli, kümeler Ailesi (FOS) olarak depolanan üretilen bir bağlantı ağacıdır . ${\görüntüleme stili T}$${\görüntüleme stili T}$

${\displaystyle T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\}, \{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

Bağlantı ağacı öğrenme prosedürü, aşağıdaki gibi çalışan hiyerarşik bir kümeleme algoritmasıdır. İki Her adımda yakın kümeleri ve birleştirilir, yalnızca tek bir küme kalmayıncaya kadar bu prosedür tekrarlanır, her bir alt ağaç bir alt kümesi olarak depolanır . ${\görüntüleme stili ben}$${\görüntüleme stili j}$${\displaystyle \tau \T_{\text{LT}}}$

LTGA, bir rekombinasyon operatörüne benzeyen ancak yalnızca iyileştirme hareketlerini kabul eden bir "optimal karıştırma" prosedürünü yönlendirmek için kullanır . Biz bu ifade notasyonu burada, tarafından indekslenen genetik materyal transferi göstermektedir gelen için . ${\displaystyle T_{\metin{LT}}}$${\displaystyle R_{\metin{LTGA}}}$${\displaystyle x[\tau ]\y alır[\tau ]}$${\görüntüleme stili\tau }$${\görüntüleme stili y}$${\görüntüleme stili x}$

Algorithm Gene-pool optimal mixing
   Input: A family of subsets ${\displaystyle T_{\text{LT}}}$ and a population ${\displaystyle P(t)}$
   Output: A population ${\displaystyle P(t+1)}$.
   for each ${\displaystyle x_{i}}$ in ${\displaystyle P(t)}$ do
       for each ${\displaystyle \tau }$ in ${\displaystyle T_{\text{LT}}}$ do
           choose a random ${\displaystyle x_{j}\in P(t):x_{i}\neq x_{j}}$
           ${\displaystyle f_{x_{i}}}$ := ${\displaystyle f(x_{i})}$
           ${\displaystyle x_{i}[\tau ]}$:= ${\displaystyle x_{j}[\tau ]}$
           if ${\displaystyle f(x_{i})\leq f_{x_{i}}}$ then
               ${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$ 
   return ${\displaystyle P(t)}$

LTGA, tipik seçim operatörlerini uygulamaz, bunun yerine seçim, yeniden birleştirme sırasında gerçekleştirilir. Benzer fikirler genellikle yerel arama buluşsal yöntemlerine uygulanmıştır ve bu anlamda LTGA hibrit bir yöntem olarak görülebilir. Özetle, LTGA'nın bir adımı şu şekilde tanımlanır:

${\displaystyle P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))}$

Başka

• Olasılık kolektifleri (PC)
• Öğrenerek tepe tırmanışı (HCwL)
• Çok değişkenli normal algoritmanın (EMNA) tahmini
• Bayes ağ algoritmasının (EBNA) tahmini
• Normal dağılımların vektörleri ile öğrenme ile stokastik tepe tırmanışı (SHCLVND)
• Gerçek kodlu PBIL
• Bencil Gen Algoritması (SG)
• Kompakt Diferansiyel Evrim (cDE) ve çeşitleri
• Kompakt Parçacık Sürü Optimizasyonu (cPSO)
• Kompakt Bakteriyel Toplayıcılık Optimizasyonu (cBFO)
• Olasılıksal artımlı program evrimi (PIPE)
• Gauss ağları algoritmasının (EGNA) tahmini
• Eşik yakınsama ile tahmin çok değişkenli normal algoritma
• Bağımlılık Yapısı Matrisi Genetik Algoritması (DSMGA)

İlgili

• CMA-ES
• çapraz entropi yöntemi

Referanslar