![Orman Optimizasyon Algoritması
Mustafa Köstek
Bilecik Şeyh Edebali Üniversitesi,Gülümbe,Bilecik,11000,Turkey
mustafakostek@gmail.com
Özet
Yeni bir optimizasyon algoritması olarak,orman
algoritması ilk kez tanıtıldı.[1]Bu algoritma
optimizasyonu gerçeklemek için ormandaki ağaçların
büyüme,üreme ve ölümünü taklit
eder.Algoritma,ağaçlar ve dalları deneme çözümleri
ve sırasıyla optimize için gerekli parametreler
topluluğu temsili ve üç mekanizma
,büyüme,yayılmasını önleme ve ölüm,yani deneme
çözümü fitness değerlendirmek için tanımlanan bir
faktördür ağaçlar canlılık geliştirmek için istihdam
edilmektedir.Çalışırken genel olarak global
optimizasyon bu algoritma denem çözümlerinde
paralel,ancak bir parametre yöntem süpürme
benimser,yani,küresel optima bulma özelliği
birleştiren yerel bir optimizasyon,onun büyüme
mekanizması,bir grup üzerinde çalışma global
optimizasyon ve yerel optimizasyon hızlı
yakınsama.Hangi global optimizasyon
yeteneğine,doğruluk ve verimlilik açısından FA
performansı değerlendirildi.
1. GiriÅŸ
Optimizasyon algoritması güçlü ve verimli bir
matematiksel tekniÄŸi maksimizasyon yada
minimizasyon verilen işlevi ile ilgili sorunların çözümü
için son 50 yılda trend bir alandır.Genellikle bazı
küresel algoritmalarda benzer işlemleri
gerçekleştirirler,GA,karınca kolonisi,sürü parçacık
optimizasyonu gibi.Rastgele oluÅŸturulmuÅŸ deneme
çözümü bir dizi ile başlayan her deneme çözümünü
fitness fonksiyonu tanımlama ve ileriye doğru
hesaplamalar deÄŸerlendirilmesi,yinelenen deneme
çözümü en iyilerine doğru yavaş yavaş ilerlemesi için
bazı mekazimalar uygulanır.Bu algoritma deneme
çözümü paralel bir grup üzerinde çalıştığından,yerel
optimumdan kaçan ve sonunda birkaç kuşak üzerinden
bir sorunun küresel aşırı yakınsak yeteneği vardır.Ama
prensip ve onlar kabul optimizasyonu gerçekleştirmek
için bir mekanizma farklıdır. Örneğin, yanı sıra
işleçleri kullanmak seçimi, crossover ve mutasyon,
MHK alır yiyecek bulma davranışını ilham ile gerçek
karınca kolonileri GA Darwinci teori evrim ve doğal
seçilim modellenmiş ve PSO kuş sürüsü ile ilgili
sosyolojik davranış geliyor. Farklı ilke ve
mekanizmaları için farklı en iyileştirme performans
neden olabilir. Bu nedenle çok sayıda araştırma
mekanizmaları değiştirerek algoritmalar
performansını artırmak için yapılır. Global
optimizasyon algoritmaları farklı olarak yerel
optimizasyon algoritmaları yokuş aşağı, Nelder ve
Mead'in Simplex yöntemi gibi mümkün olduğunca
yakın yerel asgari bulmaya çalışır. Bu nedenle, Yerel
optimizasyon algoritmaları için başlangıç noktası
hassastır. Farklı başlangıç noktaları için farklı yerel
optimaya neden olabilir. Ama genellikle yerel
optimizasyon algoritmaları yakınsama hızını global
optimizasyon algoritmalarından daha yüksektir. Bu
nedenle, yerel optimizasyon algoritmaları özellikleri
ekleyerek bu global optimizasyon algoritmaları
algoritmalar yakınlaşma hız için yararlanılabilir. Bu
çalışmada, yeni bir optimizasyon algoritması, yani
orman algoritması FA, ilk kez tanıtıldı. Diğer
optimizasyon algoritmaları kullanılan prensibi
oldukça farklı, bu algoritma bir ormandaki ağaçlar
büyüme'den türetilen. Ağaçlar, öz adaptasyon yeteneği
var. Büyüyen veya kendi dallarında solan büyüme
prosedürüne, çevreye adapte optimizasyon bir
işlemdir. Canlılık faktörü tanımlanması ve büyüme,
yayılmasını önleme ve ölüm mekanizmaları
gerçekleştirme gibi, FA Optimizasyon işlemleri için
ormandaki ağaçlar büyüme taklit eder. Bu
algoritmanın paralel, deneme çözümleri grubu genel
olarak global optimizasyon çalıştırmak, ama onun
büyüme mekanizması büyümesine veya yerel bir
optimizasyon olan dallar, solgunluk yöntemi süpürme
parametresi kullanılır.Bu nedenle FA global
optimizasyon global optima ve yerel optimizasyon hızlı
yakınsama bulmak için her iki yeteneğe de sahip olur.](https://image.slidesharecdn.com/balksz1-150813093934-lva1-app6892/85/forest-optmization-algorithm-1-320.jpg)
![2.2 Çoğalma
Doğal orman, ağaçlar her yıl kendi yavrularını
besler.Benzer şekilde, FA, yeni ağaçlar, ağaç olasılık
bir yavru ağaçlar canlılık oranı ise çoğalma içinde
proliferasyon mekanizması, uygulama her nesilde
gerçekleşir.Aşağıdaki şartı sağladığında bu ağaç için,
bir yavrudur.
(v/vort )∗rand>a
V ağacının canlılık olduğunda, Vort orman ortalama
canlılığını gösterir ve önceden belirlenmiş bir eşik
olduğunu niteler.Normalde, bir yavru kendi anasına
benzer olmalıdır, ancak vakaların küçük bir kısmı akut
mutasyon, bir yavruyu kendi anasından oldukça farklı
hale getirebilir.Bir optimizasyon algoritması için, akut
mutasyon giriş ağaçları bazı yeni tür üreterek orman
çeşitliliği artırmak ve erken yakınsama önlemek için
yararlıdır denebilir.
FA, bir yavru kendi ebeveyn olarak şube ve aynı
sayıda şubeleri uzunluğu ile verilir:
L=(1+σ∗ (2∗ rand −1))∗ Lp
L ve Lp sırasıyla yavruları ve ebeveyn için bir dal
uzunlukları nerede olduğunu niteler; Normal
mutasyon durumlarda küçük mutasyon faktörü,
(örneğin 0.1) ve akut mutasyon durumlarda (örneğin
0.8)büyük.)
2.3 Ölme
En iyi ağacı (büyük canlılık ile ağacı) bir
optimizasyon
prosedürü sırasında kaybolursa, FA tekrar bulmak için
başarısız ya da yeniden bulmak uzun bir zaman alabilir
ve böylece optimizasyon yakınsaması gecikebilir, ya
elitizm doğrudan bir sonraki kuşağa en iyi ağaç
seçilerek gerçekleşir ya da bu sorunu önlemek
mümkün değildir.
3.Çizim orman nufusu kontrol eder.
Dolayısı ile fitness orantılı seçim şemasına,
süperağaçları (ormandaki geri kalanından daha çok
daha
büyük canlılık değerleri olan ağaçlar) hayatta ve
çoğalırlar, yakında özdeş "kardeşleri" ile tüm orman
doldurmak için daha fazla şansa sahiptir.Böylece
çeşitliliği kaybetmek ve bir olasılıkla yerel optimum
olarak statik erken yakınsamaya neden olur.Bu sorunu
değiştirilmesi için, FA uzun ömürlü ve
süper-ağaçların hayatta kalma ve çoğalmasını
sınırlayan doğal ölüm kullanır.Rekabetçi ölüm
önceden ayarlanmış maksimum boyutu içinde
orman nüfusunu kontrol eder.
3. Test
Bu bölümde anlatılan söz konusu FA ile genetik
algortima karşılaştırılacaktır.3 adet lokal minimumu
olan booth's(1,3=0),goldstein(0,-1=3) ve mscormik(-
0,5,-1.5= -1.9) fonksiyonlarında sırasıyla yakınsamaları
yorumlanacaktır.FA'nın parametreleri şu şekilde
optimize edilecektir;
• Populasyon başlangıcı:10
• δ=0.1
• Populasyon limiti:100
• a=0.05
• yaş=33
• lmax=2
• lmin=-2
olarak belirlendi.Genetik algoritmada ise kod
[2] kaynaktan alınmıştır.100 iterasyonda
goldstein fonksiyonunda aşağıdaki sonuç elde
edilmiÅŸtir.
Goldsteinin sonucları 4.Çizim'de olduğu gibidir.
3. Çizim: Orman nüfus kontrolünün akış diyagramı
4. Çizim: Goldstein fonksiyonunda genetik algoritma ile
orman algoritmasının karşılatırılması](https://image.slidesharecdn.com/balksz1-150813093934-lva1-app6892/85/forest-optmization-algorithm-3-320.jpg)
![Bu şekilde mavi genetik algoritmayı kırmızı kare
olarak gösterilen ise orman algoritmasının
temsilidir.Yatay eksen döngü sayısını dikey eksen ise
4 Sonuçlar
Sonuç olarak genç ve güncel olan bir
algoritmanın süregelen klasik bir optimizasyon
algoritması olan genetik algoritma ile kıyaslaması 3
farklı fitness fonksiyonu(goldstein,mscormik,booths)
ile yapıldı.Global minimum ve maksimumlarda yüksek
oranlarda doğru ve erken yakınsama ile başarılı
neticeler elde etmiştir. Sonuçlar göstermiştir ki bu genç
ve etkili algoritma efektiflik olarak bilinmez ama iÅŸlev
olarak çok etkileyici bir dinamizme sahiptir.
Referanslar
[1]: , http://ieeexplore.ieee.org/xpl/articleDetails.jsp?
reload=true&arnumber=6977546, ,
[2]: akifÅŸahman, http://www.akifsahman.com/?p=196, ,
her bir döngüden sonra en iyi fitness değerini
nitelemektedir.5.Çizim bunu kanıtlar niteliktedir.
Şekil de ise mccormik fonksiyonunda döngü sayısına
bağlı olarak genetik(çizgi) ve orman algoritması(kare)
en iyi değerleri gösterilmiştir.
6.Çizim de anlaşıldığı üzere aynı parametreler ile çizgi
genetik algoritmayı kareler ise orman agoritmasını
temsil etmektedir.Fitness olarak booths foksiyonu
seçilmiş sınırlar [-5 5] aralığında tanımlanmıştır.
6. Çizim: Booths fonksiyonunda ilgili algoritmaların döngü
sayısına bağlı olarak karşılaştırılması
5. Çizim: Mscormik fonksiyonda genetik algoritma ile orman
optimizasyonunun karşılaştırılması](https://image.slidesharecdn.com/balksz1-150813093934-lva1-app6892/85/forest-optmization-algorithm-4-320.jpg)
forest optmization algorithm
- 1. Orman Optimizasyon Algoritması Mustafa Köstek Bilecik Şeyh Edebali Üniversitesi,Gülümbe,Bilecik,11000,Turkey mustafakostek@gmail.com Özet Yeni bir optimizasyon algoritması olarak,orman algoritması ilk kez tanıtıldı.[1]Bu algoritma optimizasyonu gerçeklemek için ormandaki ağaçların büyüme,üreme ve ölümünü taklit eder.Algoritma,ağaçlar ve dalları deneme çözümleri ve sırasıyla optimize için gerekli parametreler topluluğu temsili ve üç mekanizma ,büyüme,yayılmasını önleme ve ölüm,yani deneme çözümü fitness değerlendirmek için tanımlanan bir faktördür ağaçlar canlılık geliştirmek için istihdam edilmektedir.Çalışırken genel olarak global optimizasyon bu algoritma denem çözümlerinde paralel,ancak bir parametre yöntem süpürme benimser,yani,küresel optima bulma özelliği birleştiren yerel bir optimizasyon,onun büyüme mekanizması,bir grup üzerinde çalışma global optimizasyon ve yerel optimizasyon hızlı yakınsama.Hangi global optimizasyon yeteneğine,doğruluk ve verimlilik açısından FA performansı değerlendirildi. 1. Giriş Optimizasyon algoritması güçlü ve verimli bir matematiksel tekniği maksimizasyon yada minimizasyon verilen işlevi ile ilgili sorunların çözümü için son 50 yılda trend bir alandır.Genellikle bazı küresel algoritmalarda benzer işlemleri gerçekleştirirler,GA,karınca kolonisi,sürü parçacık optimizasyonu gibi.Rastgele oluşturulmuş deneme çözümü bir dizi ile başlayan her deneme çözümünü fitness fonksiyonu tanımlama ve ileriye doğru hesaplamalar değerlendirilmesi,yinelenen deneme çözümü en iyilerine doğru yavaş yavaş ilerlemesi için bazı mekazimalar uygulanır.Bu algoritma deneme çözümü paralel bir grup üzerinde çalıştığından,yerel optimumdan kaçan ve sonunda birkaç kuşak üzerinden bir sorunun küresel aşırı yakınsak yeteneği vardır.Ama prensip ve onlar kabul optimizasyonu gerçekleştirmek için bir mekanizma farklıdır. Örneğin, yanı sıra işleçleri kullanmak seçimi, crossover ve mutasyon, MHK alır yiyecek bulma davranışını ilham ile gerçek karınca kolonileri GA Darwinci teori evrim ve doğal seçilim modellenmiş ve PSO kuş sürüsü ile ilgili sosyolojik davranış geliyor. Farklı ilke ve mekanizmaları için farklı en iyileştirme performans neden olabilir. Bu nedenle çok sayıda araştırma mekanizmaları değiştirerek algoritmalar performansını artırmak için yapılır. Global optimizasyon algoritmaları farklı olarak yerel optimizasyon algoritmaları yokuş aşağı, Nelder ve Mead'in Simplex yöntemi gibi mümkün olduğunca yakın yerel asgari bulmaya çalışır. Bu nedenle, Yerel optimizasyon algoritmaları için başlangıç noktası hassastır. Farklı başlangıç noktaları için farklı yerel optimaya neden olabilir. Ama genellikle yerel optimizasyon algoritmaları yakınsama hızını global optimizasyon algoritmalarından daha yüksektir. Bu nedenle, yerel optimizasyon algoritmaları özellikleri ekleyerek bu global optimizasyon algoritmaları algoritmalar yakınlaşma hız için yararlanılabilir. Bu çalışmada, yeni bir optimizasyon algoritması, yani orman algoritması FA, ilk kez tanıtıldı. Diğer optimizasyon algoritmaları kullanılan prensibi oldukça farklı, bu algoritma bir ormandaki ağaçlar büyüme'den türetilen. Ağaçlar, öz adaptasyon yeteneği var. Büyüyen veya kendi dallarında solan büyüme prosedürüne, çevreye adapte optimizasyon bir işlemdir. Canlılık faktörü tanımlanması ve büyüme, yayılmasını önleme ve ölüm mekanizmaları gerçekleştirme gibi, FA Optimizasyon işlemleri için ormandaki ağaçlar büyüme taklit eder. Bu algoritmanın paralel, deneme çözümleri grubu genel olarak global optimizasyon çalıştırmak, ama onun büyüme mekanizması büyümesine veya yerel bir optimizasyon olan dallar, solgunluk yöntemi süpürme parametresi kullanılır.Bu nedenle FA global optimizasyon global optima ve yerel optimizasyon hızlı yakınsama bulmak için her iki yeteneğe de sahip olur.
- 2. Aşağıda, Bölüm 3 de genetik algoritma ile kıyaslaması yapılmıştır. 2.Orman optimizasyon algoritması Bir orman, canlı, dinamik ve karmaşık biyolojik bir sistemdir.Bir ormanda ağaçların büyümesi birçok fiziksel, kimyasal ve biyolojik faktörden etkilenir.FA optimizasyonu gerçekleştirmek için bir ormanı simülasyon amacıyla basit bir model kullanır. Gerekli parametreler optimize edilmesi gibi ağaçların deneme çözümleri topluluğu olarak bir ormanda ağaçları ve dalları düşünmektedir.Algoritma temel olarak üç tane mekanizmayı inceler; Büyüme, proliferasyon(çoğalma) ve ölüm. Bir optimizasyon prosedürü sırasında, her ağaç kendi iyiliğini değerlendirmek için hesaplamaları birçok kez ileri yakınsıyor olacak çünkü, ağaçların giderek artan sayıda hesaplanması zaman kazanmak açısından yararlıdır.1.çizimde ağacın yaşam döngüsü gösterilmiştir.FA, şubelerin değeri 'uzunluk parametreleri ifadesi' olarak adlandırılır. Doğada, ağaçlar büyüyen ya da onların hayatta kalması ve yeterli güneş ışığı ve beslenme elde etmesini sağlamak için kendi dallarında solma yapar.Benzer şekilde, her nesil, FA ağaçların canlılık geliştirmek ayrıca şube uzunluğunu ayarlamak için büyüme mekanizması kullanır.Aşağıdaki adımlardan oluşur her ağacın, her dalına, büyüme mekanizması için, tek tek hayata geçirilir. 2.1 Gelişme Uzunluğu L0 ve canlılık V0 olan bir ağacın bir dalı varsayalım.Organının uzunluğu şu denklem ile artar. v>v0∧L≤Lmax → L=L0∗(1+δ∗rand ) v<v0∨L>Lmax → L=Lmax L ve V sırasıyla ağaç dalı ve yeni bir canlılık için yeni uzunluğu:Önceden ayarlanmış bir büyüme hız faktörü; rand 0-1 arasında değişen rastgele bir değerdir ve Lmax şube için önceden ayarlanmış maksimum uzunluk,drag ise 0-1 arasında bir değerdir. Bir dalın uzunluğunun artışı bir ağacın canlılığının ve sınırlamayı geçmemesi şubenin uzunlukta bir artışa yol açmasına sebep olur ve bu adım tekrarlatır. Solma Benzer şekilde, bu adım aşağıdaki gibi bir formül kullanarak kendi şubelerinde uzunluğu azaltarak ağaçların canlılığını geliştirmeyi amaçlamaktadır. v>v0∧L≥Lmin → L=L0∗(1−δ∗rand ) v<v0∨L<Lmin → L=Lmin Uzunluğunda azalma artık ağacın canlılığındaki bir iyileşmeye neden veya uzunluğu, sınırı aşmasına kadar bu adımı da tekrarlatacaktır.Bir büyüme mekanizmasının işlemesi çok basit olarak gözlemlenebilir.Bir parametre süpürme yöntemi kullanarak, büyüme mekanizması, bir ağaç tarafından temsil edilen bir deneme çözümü etrafında yerel optimum bulmak için büyük bir şansı var, ve büyük ölçüde ağaçların canlılığını artırır. 2.Çizimde ağaçların analitik düzlemde gösterimi yapılmıştır. 1. Çizim: Orman optimizasyon akış diyagramı 2. Çizim: Analitik düzlemde temsili ağaçların gösterimi
- 3. 2.2 Çoğalma Doğal orman, ağaçlar her yıl kendi yavrularını besler.Benzer şekilde, FA, yeni ağaçlar, ağaç olasılık bir yavru ağaçlar canlılık oranı ise çoğalma içinde proliferasyon mekanizması, uygulama her nesilde gerçekleşir.Aşağıdaki şartı sağladığında bu ağaç için, bir yavrudur. (v/vort )∗rand>a V ağacının canlılık olduğunda, Vort orman ortalama canlılığını gösterir ve önceden belirlenmiş bir eşik olduğunu niteler.Normalde, bir yavru kendi anasına benzer olmalıdır, ancak vakaların küçük bir kısmı akut mutasyon, bir yavruyu kendi anasından oldukça farklı hale getirebilir.Bir optimizasyon algoritması için, akut mutasyon giriş ağaçları bazı yeni tür üreterek orman çeşitliliği artırmak ve erken yakınsama önlemek için yararlıdır denebilir. FA, bir yavru kendi ebeveyn olarak şube ve aynı sayıda şubeleri uzunluğu ile verilir: L=(1+σ∗ (2∗ rand −1))∗ Lp L ve Lp sırasıyla yavruları ve ebeveyn için bir dal uzunlukları nerede olduğunu niteler; Normal mutasyon durumlarda küçük mutasyon faktörü, (örneğin 0.1) ve akut mutasyon durumlarda (örneğin 0.8)büyük.) 2.3 Ölme En iyi ağacı (büyük canlılık ile ağacı) bir optimizasyon prosedürü sırasında kaybolursa, FA tekrar bulmak için başarısız ya da yeniden bulmak uzun bir zaman alabilir ve böylece optimizasyon yakınsaması gecikebilir, ya elitizm doğrudan bir sonraki kuşağa en iyi ağaç seçilerek gerçekleşir ya da bu sorunu önlemek mümkün değildir. 3.Çizim orman nufusu kontrol eder. Dolayısı ile fitness orantılı seçim şemasına, süperağaçları (ormandaki geri kalanından daha çok daha büyük canlılık değerleri olan ağaçlar) hayatta ve çoğalırlar, yakında özdeş "kardeşleri" ile tüm orman doldurmak için daha fazla şansa sahiptir.Böylece çeşitliliği kaybetmek ve bir olasılıkla yerel optimum olarak statik erken yakınsamaya neden olur.Bu sorunu değiştirilmesi için, FA uzun ömürlü ve süper-ağaçların hayatta kalma ve çoğalmasını sınırlayan doğal ölüm kullanır.Rekabetçi ölüm önceden ayarlanmış maksimum boyutu içinde orman nüfusunu kontrol eder. 3. Test Bu bölümde anlatılan söz konusu FA ile genetik algortima karşılaştırılacaktır.3 adet lokal minimumu olan booth's(1,3=0),goldstein(0,-1=3) ve mscormik(- 0,5,-1.5= -1.9) fonksiyonlarında sırasıyla yakınsamaları yorumlanacaktır.FA'nın parametreleri şu şekilde optimize edilecektir; • Populasyon başlangıcı:10 • δ=0.1 • Populasyon limiti:100 • a=0.05 • yaş=33 • lmax=2 • lmin=-2 olarak belirlendi.Genetik algoritmada ise kod [2] kaynaktan alınmıştır.100 iterasyonda goldstein fonksiyonunda aşağıdaki sonuç elde edilmiştir. Goldsteinin sonucları 4.Çizim'de olduğu gibidir. 3. Çizim: Orman nüfus kontrolünün akış diyagramı 4. Çizim: Goldstein fonksiyonunda genetik algoritma ile orman algoritmasının karşılatırılması
- 4. Bu şekilde mavi genetik algoritmayı kırmızı kare olarak gösterilen ise orman algoritmasının temsilidir.Yatay eksen döngü sayısını dikey eksen ise 4 Sonuçlar Sonuç olarak genç ve güncel olan bir algoritmanın süregelen klasik bir optimizasyon algoritması olan genetik algoritma ile kıyaslaması 3 farklı fitness fonksiyonu(goldstein,mscormik,booths) ile yapıldı.Global minimum ve maksimumlarda yüksek oranlarda doğru ve erken yakınsama ile başarılı neticeler elde etmiştir. Sonuçlar göstermiştir ki bu genç ve etkili algoritma efektiflik olarak bilinmez ama işlev olarak çok etkileyici bir dinamizme sahiptir. Referanslar [1]: , http://ieeexplore.ieee.org/xpl/articleDetails.jsp? reload=true&arnumber=6977546, , [2]: akifşahman, http://www.akifsahman.com/?p=196, , her bir döngüden sonra en iyi fitness değerini nitelemektedir.5.Çizim bunu kanıtlar niteliktedir. Şekil de ise mccormik fonksiyonunda döngü sayısına bağlı olarak genetik(çizgi) ve orman algoritması(kare) en iyi değerleri gösterilmiştir. 6.Çizim de anlaşıldığı üzere aynı parametreler ile çizgi genetik algoritmayı kareler ise orman agoritmasını temsil etmektedir.Fitness olarak booths foksiyonu seçilmiş sınırlar [-5 5] aralığında tanımlanmıştır. 6. Çizim: Booths fonksiyonunda ilgili algoritmaların döngü sayısına bağlı olarak karşılaştırılması 5. Çizim: Mscormik fonksiyonda genetik algoritma ile orman optimizasyonunun karşılaştırılması