Arama algoritmalarının daha az ihtimali arayarak nasıl çalışacağından bahseden ve Sezgisel olarak neler yapabileceğimizden bahseden bu bölüm Kitabımızın 4. Bölümüdür. Bu Bölümde Doç.Dr.Sadi Evren Şeker Genel arama algoritmalarını kısaca tekrar edip, gerçek hayat problemlerini nasıl arama problemlerine dönüştürdüğümüzü anlatıyor ve ayrıca sezgisel algoritma nedir? Problemlere nasıl yaklaşılır, bilmeden arama ve bilerek arama arasındaki farkları anlatıyor. Yapay Zeka 5 Bölümünün içerisinde aşağıda belirtilen konular anlatılacaktır:
*Aç gözlü yaklaşımı (Greedy Approach)
*En iyi en önce algoritması (Best First Search)
*A Yıldız Algoritması (A* search)
*Sezgisel Fonksiyonlar (Heuristic Functions)
*Tepe Tırmanması (hill climbing)
*Benzetimli Tavlama (Simulated Annealing)
*Yerel Işın Araması (Local Beam Search)
*Genetik Algoritmalar (Genetic Algorithms)
Sezgisel algoritma. Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniğidir. … 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
*Sezgisel ya da buluşsal (heuristic) bir problem çözme tekniğidir.
*Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsenmez (en iyi sonucu bulacaklarını garanti etmezler).
*Çeşitli alternatif hareketlerden etkili olanlara karar vererek iyiye yakın çözüm yolları elde etmeyi amaçlar.
*Makul bir süre içerisinde bir çözüm elde edeceklerini garanti ederler.
*Genellikle en iyiye yakın olan çözüm yoluna hızlı ve kolay bir şekilde ulaşırlar.
Neden Tercih Edilirler?
*Optimizasyon problemi, kesin çözümü bulma işleminin tanımlanmadığı bir yapıya sahip olabilir.
*Anlaşılabilirlik açısından sezgisel algoritmalar karar verici için çok daha basit olabilir (kural çıkartılabilir).
*Öğrenme amaçlı ve kesin çözümü bulma işleminin bir parçası olabilir.
*Matematiksel ifadeler ile yapılan tanımlamalarda genellikle birçok parametre/kısıt ihmal edilir.
*Bu durumda, model parametrelerini belirleme aşamasında kullanılan verinin hatalı olması, sezgisel yaklaşımın üretebileceği alt optimal çözümden daha büyük hatalara neden olabilir.
Bir algoritma tasarım yöntemi olan ve arama algoritmaları üzerinde kullanılabilen aç gözlü yaklaşımının nasıl çalıştığını iki klasik problem üzerinden :
Knapsack Problem (Torba Problemi) ve
Coin Exchange Problem (para üzeri verme problemi)
üzerinden anlatılıyor ve aç gözlü yaklaşımın hataya sebep olabilecek durumları inceleniyor.
Sezgisel arama algoritmalarından best first search (En iyi ilk arama) algoritmasının nasıl çalıştığı örnekler üzerinden gösterilerek anlatılıyor.
Best First Search (En İyi Arama) Greedy Search
*En İyi Arama, bilgilendiren arama metodlarındandır.
*Bu yöntem Breath-First ile Depth-First aramalarının en iyi yönlerini birleştirmiştir.
*Düğümler değerlendirme fonksiyonu f(n) ’e göre genişletilir. Geleneksel olarak f bir maliyet ölçüsüdür.
*Üretilen düğümler içinden en uygunu seçilir ve bu düğüm genişletilir. Seçme işlemi h(n) (sezgisel fonksiyon)’ e göre yapılır. h(n) : n düğümünden amaç düğüme olan tahmini en ucuz maliyet.
*Varsayım : h(n) = 0 ise n amaç düğümdür.
Bir sezgisel fonksiyonun (heuristic function) taşıdığı özellikleri ve uygun olması (admissable) veya tutarlı olması (consistent) kavramları anlatılıyor. Ardından iki sezgisel fonksiyonun nasıl karşılaştırılabileceğini ve bir sezgisel fonksiyonun diğer bir sezgisel fonksiyona baskın olması (dominance) durumu inceleniyor.
A* (A star) olarak bilinen arama ve yol bulma (path finding) algoritmasının nasıl çalıştığını, sezgisel fonksiyonun rolünü ve sonuca etkisini, örnek üzerinden gösterilerek anlatılıyor.
A* Search (Toplam Yolu Azaltma)
Belirli ve iyi tanımlanmış koşullar altında, bu sezgisel başlangıç ve amaç noktası arasında, eğer varsa minimum maliyetli yolu en az sayıda düğüm oluşturarak bulacağı garanti eder.
A* akla uygun bir sezgisel kullanır. •n düğümü göstermek üzere; f(n) = g(n)+h(n): değerlendirme fonksiyonu tanımlanır (başlangıç noktasından bulunan düğüme kadar tahmini toplam maliyet) g(n): Başlangıç noktasından, bulunan düğüme kadar olan maliyetin doğru ölçümü (gerçek mesafe olabilir) h(n): Mevcut düğümden amaç düğümüne kadar en az maliyet tahmini. Bu fonksiyon negatif olmamalı ve asla amaç düğümüne ulaşım maliyetinden daha fazla olmamalı. h : Tasarım problemine bağlı olarak değişen fonksiyon. •g fonksiyonu S ’den (başlangıçtan) n ’ye her yol için kesin olarak hesaplanırken, h fonksiyonu daha az belirgin ve sezgisel bir bilgidir.
Eğer tüm düğümler için h=0 ise araştırma en iyi öncelikli araştırmaya (best-first search) döner.
Tepe tırmanma algoritması üzerinden optimizasyon ve arama algoritmalarını, yerel ve küresel (global) optimizasyon kavramını ve sezgisel fonksiyonların birere hedef fonksiyonu olarak (objective function) nasıl kullanılacağı anlatılıyor. Optimizasyon algoritmalarının, ayrıca arama problemlerine nasıl dönüştürüldüğü de gözden geçiriliyor.
Optimizasyon algoritmalarından, yerel ışın optimizasyonunun (local beam search), sezgisel arama problemleri üzerinde nasıl kullanılacağı bir örnek üzerinden anlatılıyor.
Optimizasyon algoritmalarından simulated annealing algoritmasını kullanarak arama problemlerini ve sezgisel fonkisyonları (heuristic functions) nasıl optimize edileceği anlatılıyor. Algoritmanın ayrıca bir graf arama problemine nasıl dönüştürüldüğü ve yerel minimum (veya maksimum) problemini çözmek için geliştirdiği yöntem anlatılıyor.
