Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde, özellikle hesaplama alanında kullanılan algoritmalardan birisidir. İsmini demir tavlamak veya demiri ısıtmak anlamına gelen annealing (tavlama) kelimesinden almıştır. Algoritmanın amacı, herhangi bir problem için genel iyileştirme (global optimization) elde etmektir. Diğer bir deyişle, herhangi bir fonksiyonun ya da ölçümün genel minimum veya maksimum (global minimum) elde etmek olarak düşünülebilir.
1. Simulated annealing (benzetilmiş tavlama) nerede işe yarar?
Genellikle hesaplamalı bilimlerde bir deneyin yada nümerik sonuçların anlık değerleri elde edilir. Örneğin aşağıdaki grafiği ele alalım:
Yukarıdaki şekil herhangi bir indis değerlerine sahip fonksiyon olabilir. Yukarıdaki 2 boyutlu grafiğin indisleri yada formüllendirilmesi ile ilgilenmeden grafiğin en küçük olduğu değeri bulmaya konsantre olalım. Şayet yukarıdaki grafiği veren bir formül elimizde varsa, bu formülün üzerinde çeşitli matematiksel yöntemler uygulayarak (örneğin türev alarak) bir sonuç elde edebiliriz. Ancak yukarıdaki grafiği veren bir formülümüzün olmadığını ve yukarıdaki değerleri ancak belirli aralıklarla yapılan ölçümler sonucu elde ettiğimizi düşünelim.
Örneğin yukarıdaki noktalar ile gösterilen değerlerin ölçüldüğü ayrık bir (discrete) sistemimiz olduğunu düşünelim. Bu duruma yapay zeka problemlerinde sezgisel sonuçların (heuristic) elde edildiği problemlerde veya gerçek hayattaki farklı zamanlarda yapılan ölçümlerde sıkça rastlanır. Benzer bir durum olarak ölçme maliyetinin yüksek olduğunu da kabul edilebilir. Örneğin her ölçümün yüksek maliyet getirdiği ve dolayısıyla kısıtlı sayıda ölçüm yaparak en düşük değeri bulacağımız x ekseni değerini aradığımızı düşünelim.
İşet yukarıdaki 2 boyutlu grafikte kullanılabilecek benzetimli tavlama (simulated annealing) algoritması, matematiksel olarak bir fonksiyonla modellenemeyen, nümerik ve ayrık uygulamalarda kullanılabilir. Ayrıca problemin kaç boyutlu olduğunun da bir önemi yoktur. Örneğin 3, 4 veya daha fazla boyutlu problemlerde de kolaylıkla uygulanabilir.
2. simulated annealing (benzetilmiş tavlama) nasıl çalışır?
Algoritmanın çalışması aslında isminin de geldiği demir tavlama işlemine benzer. Yani nasıl demir tavlama işlemi sırasında bir demir parçayı ısıtıp sonra soğumaya bırakıyorsak, herhangi bir sayısal ölçüme de benzeri yaklaşım uygulanabilir.
Şayet demir tavlama problemini, demiri oluşturan ufak hücrelerin ısınması ve soğuması olarak düşünecek olursak, ki bu hücreler daha sonra problemimizin örneklendiği her bir deney veya nümerik sonuç olarak modellenecektir, hücreler arası geçiş ve hücrelerin zamana bağlı değerlerini elde etmek mümkündür.
Amacımız genel bir minimum noktası bulmak olduğuna göre, problemin farklı zamanlardaki sonuçlarını ele alıp bu sonuçlardan iyi olanına doğru hareket etmemiz gerekir. Örneğin s durumu ve s’ durumları arasından, P(e,e’,T) olasılık değerine göre seçim yapılır. Buradaki e= E(s) ve e’=E(s’) olarak hesaplanan s ve s’ için enerji değerleridir. Yani grafikteki karşılık değerleri veya deneyimizin sonuç değerleri olarak düşünülebilir. T değeri ise ısı olarak geçer ki bunu da deneydeki ölçüm zamanları olarak kabul etmek mümkündür.
Kısacası P(e,e’,T) değeri bir olasılık sonucu çıkarır. Bu sonuç bize s durumundan s’ durumuna geçişin ne kadar kabul edilebilir olduğunu olasılıksal olarak verir.
Burada daha basit bir açıklama olarak şöyle düşünebiliriz. Şayet e’ değeri, e değerinden yüksekse, yani yeni durumumuzdaki enerji daha yüksek bir enerjiyse, sistem soğumuyor ısınıyor demektir. Bu ise sistemin daha kötüye gittiğinin bir işaretidir ve doğal olarak kabul edilir bir durum değildir.
Ancak sistemin hep iyiye gitmesi hiç kötüye gitmemesini istememiz durumunda yerel minimumla (local minimum) karşılaşırız. Örneğin yukarıda temsili resmi verilen şekli hatırlayalım:
Yukarıdaki şekilde düşey ekseni enerji olarak kabul edersek, soldaki okun gösterdiği değer soğuma olarak düşünülebilir. Yani farklı durumlar için enerji değerleri azalmıştır. İkinci okta ise enerji değerleri artmış yani elde edilen durumlarda ısınma olmuştur. Şimdi yukarıdaki örnek için, şayet ısınan durumları, yani okun yukarı yönlü olduğu durumları kabul etmez ve grafikte sağa doğru hareket etmezsek 1 numaralı çukurda takılıp kalma ihtimali olur. Bu durumda sistemimiz hiçbir zaman, daha iyi sonuçlar olan 2 ve 3 numaralı çukurlara ulaşamayabilir.
Bu yazı şadi evren şeker tarafından yazılmış ve bilgisayarkavramlari.com sitesinde yayınlanmıştır. Bu içeriğin kopyalanması veya farklı bir sitede yayınlanması hırsızlıktır ve telif hakları yasası gereği suçtur.
Bu şekilde elde edilen sonuçlara yerel minimum (local minimum) ismi verilir ve algoritmamızın yukarıda açıklanan şekilde davranması durumuna açgözlü yaklaşımı (greedy approach) ismi verilir. Kısaca ilk bulduğu minimum değerine atlayan ve dolayısıyla sistemdeki daha düşük minimum değerleri bulamayan algoritma haline gelir. (açgözlülük insanı kör ettiği gibi algoritmaları da kör eder)
Bu duruma çözüm olarak e’-e değerindeki değişimler gözlenir. Bu değerler arasındaki değişimlerin artması, bu değerleri üreten s ve s’ durumlarının kabulünü zorlaştırır. Ancak iki durumda ölçülen enerji değerlerinin birbirine çok yaklaşması durumunda sistem kabul edilir. Bu sayede sistemin yükseldiği durumlarda da sistem dolaşmaya devam eder ancak enerji değerlerinin birbirine iyice yaklaşması sonucunda minimum değerler bulunmuş olunur.
3. Simulated annealing’in kodlanması
Yukarıdaki tanımı müsvedde kod olarak yazalım:
Yukarıdaki kod, görüldüğü üzere komşu durumlar üzerinde hareket ederek (yada olasılık durumuna göre etmeyerek) en iyi sonucu bulmaya çalışır.
Yukarıdaki kodun diğer bir özelliği ise sezgi üstü yaklaşımlar için kullanışlı olmasıdır. Dikkat edilirse, algoritmanın taradığı bütün durumlar s ve s’ durumları olarak geçmekte ve dilenirse kaydedilebilmektedir. Bu durum normal bir soğuma sürecinden farklı olarak (gerçek hayatta herhangi bir t anında sadece bir durum vardır) çok durumu tutabilme imkanı sunar.
Ayrıca yukarıdaki algoritmada yapılacak deneme sayısı kodun 7. Satırındaki döngü ile limitlenebilmektedir. Dolayısıyla bir kişi en iyi ama en maliyetli çözüm için bu MAX değerini arttırabilir. Elbette en iyi çözüm demek daha çok deneme demek ve bu da yüksek maliyet demektir. Maliyetin düşürülmesi için deneme sayısının kısılması ise, en iyi genel sonucun bulunamaması ihtimalini yükseltir. Elbette şanslıysak ve genel minimum f(0) değeriyse hiç deneme yapmamıza da gerek yoktur J
Benzetilmiş tavlama yönteminin ( simulated annealing), bir özelliği de, aynı problem için birden fazla çözümü olmasıdır. Bunun sebebi yukarıdaki kodda da belirsiz olarak bırakılan, komsu(), P(), T() fonksiyonlarının (functions) problemin çözümündeki seçilme şeklidir. Yani aynı problemi iki farklı bilgisayar bilimcisi iki farklı komşuluk fonksiyonu, ısı değeri ve olasılık değerine göre çözebilir. Burada probleme özgü olarak modelleme yapmak ve problemin karakteristiğinin doğru analiz edilmesi önem taşır.
Hocam selamlar çalışmalarınızdan ötürü sizi tebrik ediyorum. Türkiyedeki akademik içerikli en iyi site diyebilirim. Hocam lafı uzatmadan projem için Firefly Algoritması gerekmekte ancak herhangi Türkçe kaynak bulamadım bulduğum İngilizce kaynaklardan da çok fazla bir şey anlamadım. Bu konuda bir yazı yazabilir veya bir öneride bulunabilir misiniz?
İyi çalışmalar.
Siteye bir yazı ekledim ancak sizin kullanım alanınız ve algoritmaya ihtiyaç duyma sebebinizi bilemediğim için genel amaçlı, giriş seviyesinde algoritmayı açıklayıcı bir yazı yazdım. Aşağıdaki bağlantıdan erişebilirsiniz:
http://www.bilgisayarkavramlari.com/2011/04/18/atesbocegi-algoritmasi-firefly-algorithm/
başarılar
mrb hocam iyileştirm eile ilgili çözmem gerekn bir soru var kendim çözemedim yardımcı olursanız sevinirim
Bir postanede haftanın her günü farklı sayıda elemana gereksinim duymaktadır. Sendika kurallarına göre bir eleman 5 gün peş peşe çalışmakta diğer iki gün izin yapmaktadır. Çalıştırılması gereken toplam en az eleman sayısını aşagıdaki iş yüküne göre hesaplayınız.
pazartesi salı Carsamba Persembe Cuma cumartesi Pazar
gerekli eleman 17 13 15 19 14 16 11
Yalnışsa yalnış kafa yormak iyidir 🙂
“Sendika kurallarına göre bir eleman 5 gün peş peşe çalışmakta diğer iki gün izin yapmaktadır.” kuralına göre; haftanın tatil günlerinden olan “cumartesi ve Pazar” günlerini çıkartıyorum.
“Çalıştırılması gereken toplam en az eleman sayısı?” problemine göre; haftanın 5 gününü çalışmakla geçirecek olan en az eleman sayısı bizden isteniyor.
Eldeki “gerekli eleman sayıları” ‘ ndan, **en çok iş yüküne sahip en yüksek sayılar**ı çıkartıyorum.Çünki haftanın 5 günü çalışacak olan elemanlardan en az eleman sayısı bizden isteniyor.
(a)Yani; en az eleman sayısı ile iş yükü birbirlerine doğru orantılı olduğundan.
“gerekli eleman sayıları : 13 15 14 16 11” (a)’ ya göre 17 ve 19 sayılarını “gerekli eleman sayıları” içerisinden çıkartıyorum.
Ve çalıştırılması gereken en az eleman sayısını “13+15+14+16+11” toplamlarıyla “69” olarak buluyorum.
(Okulunu okumuş değiliz kafa yorarak sonuca gitmeye çalıştım sadece.)
software isimli kullanıcı epey zaman önce yazmış ancak gözümden kaçmış, kendisinden özür diliyorum. Fatih isimli kullanıcı sayesinde soruyu görmüş oldum. Öncelikle Fatih Bey, yaklaşımınız doğru, ancak arkadaşın sorusunda cumartesi ve pazar günleri çalışılabilir gibi anlaşılıyor. Daha doğrusu 2 gün tatil herhangi iki gün olabilir (pazartesi veya çarşamba da tatil yapabilir). Ayrıca tatiller ve çalışma günleri arka arkaya olacak. Demek ki örneğin çarşamba iş başı yapan birisi çar, per, cum, cts, paz çalıştıktan sonra pts, sal tatil yapacaktır.
Verilen iş yüklerine göre en yoğun gün perşembe (19) ve en boş gün pazar (11). dolayısıyla şayet becerebilirsek perşembe herkes işte, pazar ise en fazla tatil yapılan gün olarak dengelenmeli.
Öncelikle problemi normalize ediyorum. En düşük sayımız 11 olduğuna göre zaten mecburen 11 kişiyi çalıştıracağız. Her günden 11 çıkarıyorum:
6, 2, 4, 8 , 3, 5, 0 // tamamen işlem kolaylığı için yapılmıştır şart değildir.
şimdi arama algoritmamızı kullanalım. Ardışık 5 çalışma günü armak ile ardışık 2 tatil günü aramak aslında aynı anlama gelmektedir. Tatil günlerini aramak kolay olduğu için buradan yola çıkıyorum ve en düşük değere sahip iki ardışık gün bulmak istiyorum. Sırasıyla ardışık günlerin toplamları aşağıda verilmiş
pts, sal = 8
sal, çar = 6
çar, per = 12
per, cum = 11
cum, cts = 8
cts, paz = 5
paz, pts = 6
Görüldüğü üzere en düşük değere sahip ardışık gün cts, paz ikilisidir. Şimdi ilk izin vereceğimiz kişi cts, paz günleri izin kullansın. Bu durumda problemi yeniden hesaplamamız gerekir:
6, 2, 4, 8 , 3, 5, 0 olarak bulduğumuz iş yüklerinden cts, paz hariç 1 çıkarıyoruz çünkü bu günlerde artık çalışan bir işçimiz var:
5, 1, 3, 7, 2, 5, 0
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 6
sal, çar = 4
çar, per = 10
per, cum = 9
cum, cts = 7
cts, paz = 5
paz, pts = 5
Görüldüğü üzere işçimiz çalıştıktan sonra ardışık günlerde azalma olmuştur, sadece cts, paz ikilisinde işçimiz izin yaptığı için azalma yoktur. Gelelim bu yeni değerlere göre yeni bir işçi atamaya. Burada en düşük değer sal, çar ikilisi olduğu için ikinci işçimize sal, çar izin veriyoruz ve iş yüklerimizi yeniden dengeliyoruz:
4, 1, 3, 6, 1, 4, 0
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 5
sal, çar = 4
çar, per = 9
per, cum = 7
cum, cts = 5
cts, paz = 4
paz, pts = 4
Yeni değerlere göre en düşük olan 4 değerlerinden herhangi birisini seçebiliriz. Örneğin yine cts, paz seçelim :
3, 0, 2, 5, 0, 4, 0
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 3
sal, çar = 2
çar, per = 7
per, cum = 5
cum, cts = 4
cts, paz = 4
paz, pts = 3
En az değer olan sal, çar seçilir:
2, 0, 2, 4, 0(-1), 3, 0(-1) //bazı değerler -1 olmuştur ancak bunu 0 almalıyız, -1 işçi olamaz.
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 2
sal, çar = 2
çar, per = 6
per, cum = 4
cum, cts = 3
cts, paz = 3
paz, pts = 2
Yine en az değerlerden birisini seçebiliriz, örneğin pts, sal seçiyorum:
2, 0, 1, 3, 0(-1), 2, 0(-1) //bazı değerler -1 olmuştur ancak bunu 0 almalıyız, -1 işçi olamaz.
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 2
sal, çar = 1
çar, per = 4
per, cum = 3
cum, cts = 2
cts, paz = 2
paz, pts = 2
En az olan sal, çar seçilir:
1, 0, 1, 2, 0(-1), 1, 0(-1) //bazı değerler -1 olmuştur ancak bunu 0 almalıyız, -1 işçi olamaz.
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 1
sal, çar = 1
çar, per = 3
per, cum = 2
cum, cts = 1
cts, paz = 1
paz, pts = 1
Artık sona yaklaştık örneğin pts, sal seçiyorum:
1, 0(-1), 0, 1, 0(-1), 0, 0(-1) //bazı değerler -1 olmuştur ancak bunu 0 almalıyız, -1 işçi olamaz.
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 1
sal, çar = 0
çar, per = 1
per, cum = 1
cum, cts = 0
cts, paz = 0
paz, pts = 1
Cts, paz seçiyorum:
0, 0(-1), 0(-1), 0, 0(-1), 0, 0(-1) //bazı değerler -1 olmuştur ancak bunu 0 almalıyız, -1 işçi olamaz.
ardından yeniden ikili değerleri hesaplıyoruz:
pts, sal = 0
sal, çar = 0
çar, per = 0
per, cum = 0
cum, cts = 0
cts, paz = 0
paz, pts = 0
Artık hiç işçiye ihtiyacımız kalmadı. Şayet sabahın 5’inde hata yapmadıysam, sonuca 8 adımda vardık. Demek ki 19 kişi ile (ilk başta 11 kişiyi zaten mecburen çalıştıracağız diye çıkardığımızı hatırlayın) bu iş yapılabilirmiş. Ayrıca işçilerin izin tablosu aşağıdaki şekilde bulundu:
cts, paz
sal, çar
cts, paz
sal, çar
pts, sal
sal, çar
pts, sal
cts, paz
Bu durum yukarıdaki çözüm adımlarında bahsedildiği üzere tek çözüm değildir. Bazı durumlarda eşit değere sahip alternatiflerden birisini tercih ettik. Diğeri tercih edilerek de başka sonuçlar bulunabilirdi.
Yukarıdaki çözümde kullanılan bir arama algoritmasıdır ve kullanım sırasında sezgisel bir fonskiyon (heuristic function) yazılmıştır. Sorunuzu benzetilmiş tavlama (smiulated annealing) başlıklıklı konunun altına yazmışsınız ancak bence yukarıdaki çözüm daha başarılı çalışır.
Yukarıdaki çözümü daha da hızlandırmak istiyorsanız aynı anda birden fazla çalışan atayabilirsiniz. Örneğin en küçük iki değere sahip izin günlerine atama yapılabilir. Bu sayede daha hızlı çalışacaktır. Ben soruyu çözmek gibi bir niyetiniz olduğunu düşündüğüm için bastiçe çözmeye çalıştım, amacınız hız ise ayrıca bunu da çözebilirim.
Başarılar
Endüstriyel Çizelgeleme dersimin ödevi için bir iş atölyesinde tavlama benzetimini kullanmam gerekiyor. Hiç iş atölyesini bulamadım . Ne yapmalıyım?