Sezgisel Algoritmalar

Sezgisel Algoritmalar

Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vaz geçerek çözüm zamanını azaltan algoritmalardır.
Sezgisel algoritmalar en iyi sonucu bulacaklarını garanti etmezler fakat makul bir süre içerisinde bir çözüm elde edeceklerini garanti ederler. Genellikle en iyiye yakın olan çözüm yolununa hızlı ve kolay bir şekilde ulaşırlar.
Sezgisel arama algoritmalarına örnek olarak

• A* araması (A star)
• Demet araması (Beam search)
• Tırmanış Araması (Hill climbing)
• En iyi öncelikli arama (Best first search)
• Açgözlü en iyi öncelikli arama (Greedy best first search)

Heuristic diğer bir anlamıyla; bir düğümden (node) başka bir düğüme olan en kısa yolun maliyetini hesaplayan fonksiyonlar olarak bilinir.

Bilgisayar bilimlerinde en kısa yol bulmak için kullanılan algoritmalardan birisidir. Örneğin seyyar tüccar problemi (travelling salesman problem, TSP) gibi bir problemin çözümünde kullanılabilir. Benzer şekilde oyun programlamada, oyunda bulunan oyuncuların en kısa yolu bularak hedefe gitmeleri için de sıklıkla kullanılan algoritmadır.

Kısaca bir düğümden (node) hedef bir düğüme (target node) en kısa hangi düğümler üzerinden gidileceğini bulmaya yarayan “en iyi yerleştirme (best fit)” algoritmasıdır. Ve işte bazı sezgisel algoritmalara örnekler;

A* algoritması

yapı olarak muteber sezgisel (admissable heuristic) bir algoritma olarak sınıflandırılabilir. Bunun sebebi algoritmasının mesafe hesaplamada kullandığı fonksiyondur:

f(n) = g(n) + h(n)

denklemindeki

f(n) = hesaplama yapan sezgisel (heuristic) fonksiyon.

g(n) = Başlangıç düğümünden mevcut düğüme kadar gelmenin maliyeti

h(n) = Mevcut düğümden hedef düğüme varmak için tahmin edilen mesafe.

Dikkat edileceği üzere f(n) fonksiyonunun sezgisel olma sebebi, bu fonksiyon içerisinde bulunan ve tahmine dayalı olan h(n) sezgisel fonksiyonudur.

Algoritmanın çalışması:

Algoritma yukarıdaki toplama işlemini kullanan oldukça basit bir yapıya sahiptir. Veri yapısı olarak bir öncelik sırası (priority queue) kullanan algoritmada en öncelikli olan düğüm f(n) değeri en düşük olan düğümdür.

1.      Algoritma her adımda en düşük değeri (Ve dolayısıyla en önemli) düğümü alır (yani bu düğüme gider) ve düğümü sıradan (queue) çıkarır.

2.      Gidilen bu düğüme göre komşu olan bütün düğümlerin değerleri güncellenir (artık bu düğüme gelmenin bir maliyeti vardır ve dikkat edilirse f(n) fonksiyonu içerisinde bu değer yer almaktadır.)

3.      Algoritma yukarıdaki adımları hedefe varana kadar (yani hedef düğümü öncelik sırasında (priority queue) en öne gelene kadar) veya sırada (queue) düğüm kalmayana kadar tekrarlar.

4.     Örnek Çalışma:

5.     Algoritmanın çalışması için aşağıdaki örneği ele alalım:

6.     

7.     Yukarıdaki grafikte sol üst köşedeki düğümden, sağ alt köşedeki düğüme gitmek isteyelim. Bu durumda f(n) fonksiyonunu oluşturan mesafe değeri, grafik üzerindeki yol maliyetleri olarak hesaplanbilir. Sezgisel fonksiyon olarak, bir düğümün hedefe olan kuş uçuşu mesafesini alalım. Yani iki düğüm arasındaki mesafeyi çizilen yoldan değil de iki düğüm arasındaki cetvel ile ölçülen değer olarak kabul edelim.

8.     Bu durumda düğümlerin sezgisel mesafelerini (heuristic) gösteren graf aşağıdaki şekildedir:

9.     

10. Yukarıdaki bu grafikte kırmızı renkle gösterilen değerler, o düğümden hedef düğüm olan sağ alt köşedeki düğüme olan kuş uçuşu mesafeyi göstermektedir. Bu değerleri kısaca h(n) olarak kabul edebiliriz.

11. Başlangıç düğümümüz olan sol üst köşedeki düğümden başlayarak iki düğümün değerini hesaplayalım. Başlangıcın altında bulunan düğüm için h(n) = 9 ve g(n) = 4 olmaktadır.

12. Başlangıcın sağında bulunan düğüm için ise h(n) = 8 ve g(n) = 3 olmaktadır. Buna göre:

13. f(aşağı) = 9+4 = 13

14. f(sağa) = 8 +3 = 11

15. olarak bulunmaktadır. Algoritmamız bu seçimler arasından küçük olan (ve önceliği yüksek olan) sağa gitmeyi tercih eder.

16. Bu seçimi aşağıdaki şekilde gösterelim.

17. 

18. Yukarıdaki bu seçimden sonra değerler tekrar hesaplanır. Yukarıda yapılan seçime göre düğümlerin değerleri tekrar f(n) = g(n) + h(n) olarak hesaplanırsa:

19. 

20. Yukarıdaki bu grafikte görüldüğü üzere sıramızda (queue) iki düğüm bulunmakta ve iki düğümün değerleri sırasıyla 13 ve 11 olmaktadır.

21. Bu durumda 11 olan düğümü seçip aşağı doğru hareket ediyoruz.

22. 

23. Yukarıdaki son durumda 13 ve 21 değerleri olan iki düğüm arasında seçim yapıldığında, kısa değer olarak 13 bulunduğu için A* arama algoritmamız bu aşamada geldiği alternatif yoldan vaz geçerek en kısa yolun bu yeni düğüm olabileceğini düşünür ve bu yola gider.

24. 

25. Yukarıdaki şekilde bu yeni seçim yeşil renk ile gösteirlmiştir. Yeni seçim yapıldıktan sonra ulaşılan komşu düğümler 14 ve 21 değerlerine sahiptir. Bu durumda 14 değerine sahip olan daha öncelikli düğüme hareket edilecektir.

26. Yeni halinde değerler hesaplandığında sonuç düğümüne gidilmesi mümkündür ve ulaşım değeri yukarıdaki dolaşmaya göre daha düşüktür.

27. 

28. Yukarıdaki son durumda hedefe ulaşılmış ve aşağıdaki yol kullanılmıştır. Sonuçta ulaşım için harcanan mesafe toplandığında 4+6+4 =14 mesafesi diğer alternatif olan 3+4+6+8 =21 değerine göre daha kısadır.

29. Tabi A* algoritması sezgisel bir algoritma olduğu için bu durumu bilmemektedir.

Demet araması(ışın) algoritması

En iyi ilk arama yaklaşımını kullanan arama algoritmaları, arama yaptıkları şekil (graph) üzerinde bütün çözüm ihtimallerini belirli bir sezgisel fonksiyona göre sıralarlar. Diğer bir deyişle arama işlemi sırasında sezgisel bir fonksiyona göre, aramada bazı kararlara öncelik verirler. Bu sezgisel fonksiyonun amacı, karar anında verilen kararın, sonuç durumuna (goal state) ne kadar yakın olduğunu yargılayabilmektir.
Işın aramasının bir özelliği de, daha önceden belirlenmiş ve sınırlı sayıdaki, yapmış olduğu seçimleri saklamasıdır.
Işın araması, bir arama ağacı (search tree) oluştururken, sığ öncelikli arama (breadth first search) yaklaşımı kullanır. buna göre ağacın herhangi bir seviyesinde, gidilebilecek düğümlerin sezgisel değerlerini hesaplar ve bunlardan sadece belirli sayıdaki düğümü, daha sonra geri dönülmek üzere hafızasında tutar. Bu değere ışın aramasına özgü olarak ışın genişliği (beam width) ismi verilir.
Işın genişliği arttıkça daha fazla düğüme bakılmaktadır. Işın genişliği azaldıkça da daha fazla düğüm budanmaktadır (prunning). Budama işleminin dez avantajı, şanssız bir şekilde en iyi sonucu verecek düğüme giden yolu budama riskidir. Ancak bu riskten dolayı bütün düğümleri tutmak (yani hiçbir düğümü budamamak) gibi bir karar verirsek, bu karar sonucunda da çok daha fazla hafıza ve işlem ihtiyacımız olacaktır. İşte ışın araması, bu iki karar arasında en iyi (optimum) noktayı bulmayı amaçlar.
Bu amaca yönelik olarak, ışın araması sabit ışın genişliği (fixed beam width) veya değişken ışın genişliği (variable beam width) kullanacak şekilde kodlanabilir. Değişken ışın genişliği alan arama algoritmasında, öncelikle ışın genişliği asgari değerde tutularak arama yapılır. Aranan en iyi sonuca ulaşılamazsa, ışın genişliği arttırılarak arama işlemi sürdürülür. Beklenen sonuca ulaşılana kadar da ışın genişliği arttırılır.

Işın aramasının kullanıldığı yerlerden birisi de bilgisayarlar tarafından otomatik olarak yapılan tercüme işlemleridir. Bilindiği üzere bir kelime, bilgisayar tarafından işlendiğinde, birden fazla anlama gelebilmektedir. İnsanlar kelimenin kullanımından (syntax, pragma) kelimenin anlamını kısa sürede doğru olarak anlayabilmekte ancak bilgisayarlar için bu anlama süreci ve doğru anlamın bulunması (semantics), hatırı sayılır bir süre almaktadır.
Çözüm olarak ışın araması algoritması, çok sayıdaki çeviri ihtimallerinden sadece belirli bir kısmını işleyerek doğru tercümeyi yapmak için kullanılabilir.

Tırmanış (Tepe Tırmanma) Algoritması

Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Arama işleminin yapıldığı grafikteki tepelerden ismini alır. Basitçe bir grafikte bulunan en düşük noktanın aranması sırasında grafikte yapılan hareketin aslında tepe tırmanmaya benzemesinden ismini almaktadır.

Örneğin yukarıdaki şekilde gösterilen ok temsili bir tepe tırmanma işlemidir. Burada arama yapan algoritma aslında bir çukur bulmuş ancak daha iyisi için tepe tırmanmaktadır denilebilir.

Elbette olayı iki boyutlu bir grafik üzerinde yapılan bir arama veya tırmanılan bir tepe olarak görmek, algoritmanın önemini kavramayı engelleyebilir. Aslında burada anlatılmak istenen bilgisayar bilimleri de dahil olmak üzere, çeşitli bilim ve mühendislik alanlarında, birden fazla çözümü olan problemler için en iyi çözümün arandığı iyileştirme (optimization) problemleridir.

Yani şayet bir sistemin ya da bir programın daha iyi hale getirilmesi isteniyorsa, sistemin verdiği sonuçlara göre arama işlemi yapılarak iyileştirme amaçlanabilir. İşte bu noktada tepe tırmanma algoritması (hill climbing algorithm) de dahil olmak üzere çeşitli arama algoritmaları devreye girer. Örneğin literatürde sıkça kullanılan seyyar tüccar problemi (travelling salesman problem) bu problemlerden birisidir. Tepe tırmanma algoritması verilen bir harita için verilen bir sonucu iyileştirmeye çalışır. Elbette amaç bütün ihtimalleri denemeden iyi bir sonuç bulabilmektir.

Tepe tırmanma algoritması, arama algoritmaları arasındaki en iyi sonucu verene algoritma değildir. Ancak kodlanması ve tasarımının basit oluşundan dolayı sıklıkla kullanılır.

Tepe tırmanma algoritması çeşitleri

Algoritmanın üzerinde çeşitli iyileştirmeler yapılarak daha iyi sonuçlar elde edilmeye çalışılmıştır. Literatürde sıkça kullanılan bir iki tepe tırmanma algoritmasını farkları ile birlikte açıklamaya çalışalım.

Klasik tepe tırmanma algoritmasında amaç arama için merkez kabul edilen (veya başlangıç noktamız diyebileceğimiz) noktadan komşu olan noktaları gezerek daha iyi sonuçlar elde etmektir. Temel olarak bir grafikte rastgele seçilen bir nokta için 3 farklı ihtimal bulunmaktadır:

1.     Noktanın bir tarafında problem iyileşirken diğer tarafında kötüleşmektedir. Bu durumda iyi tarafa doğru tırmanma algoritmamız devam eder.

2.     Noktanın iki tarafında da problem sonucu kötüleşmektedir. Bu durumda bulunduğumuz nokta problem için en iyi noktalardan (optimum points) birisidir. Elbette bu en iyi sonuç olmayabilir yani bu sonuçtan daha iyi sonuçlar olabilir ancak klasik tepe tırmanma algoritması bu diğer sonuçları bulamaz ve bu noktada kalır.

3.     Noktanın iki tarafında da problem iyileşiyordur. Yani tesadüfen bulduğumuz nokta aslında problem için ulaşılabilecek en kötü noktalardan birisidir. Bu durumda tepe tırmanma algoritması yönlerden birisini seçerek tırmanmaya devam eder. Farklı bir çeşit olarak iki yöne de tırmanan algoritma bulunmaktadır.

Klasik tepe tırmanma algoritmasından farklı olarak steepest ascent hill climbing algoritmasında, bulunabilen bütün sonuçlar arasından bir seçim yapılır. Bu algoritmada da klasik tepe tırmanma algoritmasında da sorun aynıdır. Şayet arama işlemi sırasında bir yerel çukura (local minimum) rastlanılırsa bu durumdan algoritma kendisini kurtaramayarak en doğru sonucu bulamayabilir.

Buna karşılık olasılıksal tepe tırmanma algoritmasında ( stochastic hill climbing algorithm) bütün komşuların aranması ve komşuların verdiği sonuca göre hareket etmek yerine, rast gele olarak bir komşunun seçilmesi söz konusudur. Şayet gidilen bu komşu beklenen yönde bir iyileştirme sağlıyorsa, bu yönde aramaya (tırmanmaya) devam edilir, şayet beklenen iyileştirme sağlanamıyorsa, bu durumda daha farklı bir komşu denenir.

Yukarıdaki tepe tırmanma algoritmalarının yanında rastgele başlangıç tepe tırmanma algoritması (random restart hill climbing algorithm) şaşırtıcı derecede iyi sonuç veren bir algoritmadır. Bu algoritma basitçe bir x durumunu başlangıç kabul eder ve daha iyi bir durum bulunca başlangıç durumunu bu daha iyi duruma kaydırır. Algoritma iyi durum buldukça başlangıç durumunu kaydıran ancak bulamadığı durumlarda da aramaya devam eden bir yapıya sahiptir. Rastgele başlangıç tepe tırmanma algoritmasına bazı kaynaklarda pompalı tüfek tepe tırmanma algoritması (shotgun hill climbing algorithm) ismi de verilmektedir.

Tepe tırmanma algoritmaları genel olarak yerel bir başarı noktasında (local optimum point) takılmak gibi bir zafiyete sahiptirler. Daha iyi sonuçlar için simulated annealing gibi arama algoritmaları kullanılabilir.

Örneğin yukarıdaki şekilde x ve y noktaları arasında bir düzlük bulunmaktadır. Başlangıç noktası olarak bu aralıktaki herhangi bir noktadan başlanırsa algoritma komşuları aradığında daha iyi veya daha kötü bir sonuç bulamayacağı için hatalı karar verebilir.

Ayrıca tepe tırmanma algoritmaları problem sonuçlarında nadiren de olsa aynı sonucun elde edilmesi durumunda belirsizce hatalı sonuçlar verebilir. Bu şekildeki durumlara algoritmadaki düzlükler ismi verilir ve algoritma hangi yöne gidilirse gidilsin daha iyi bir sonuç çıkaramaz (hep aynı sonucu çıkarır). Elbette doğası gereği tepe tırmanmaya hazırlanmış algoritmamız, tepe bulamayınca hata yapmaktadır.

Algoritmanın kodlanması

Algoritma iki boyutlu bir grafik için rastgele yön seçimi yapılması durumunda aşağıdaki şekilde kodlanabilir:

Yukarıdaki kodda, basitçe başlangıç noktasından başlanarak, daha iyi sonuçlar bulunduğu sürece bir sonraki komşu noktaya hareket öngörülmüştür.

Ancak problemin çok boyutlu olması yani bir noktanın birden fazla komşusu bulunması durumunda bütün komşuların kontrol edilmesi ve en iyisinin bulunması daha sonra bu komşuya doğru hareket edilmesi gerekeceği için algoritmayı aşağıdaki şekilde yazmak mümkündür:

Yukarıdaki yeni kodda, bir noktanın birden çok komşusu olduğu kabul edilmiş ve bütün komşuları dolaşılarak en iyi komşu alınmış, ardından daha iyi komşu bulundukça bu işlem devam ettirilmiştir. Nihayetinde hiçbir komşu, bulunan son komşudan daha iyi olmayınca program sonlandırılmıştır