Sezgisel Arama Algoritmaları

Sezgisel Arama

• G.W. Leibniz, özel buluşlardan ziyade, tek bir yöntemin birçok çözümü kapsadığı için icat etme sanatını mükemmelleştirmenin önemli olduğunu belirtmiştir.
• Fagenbaum ve Fieldman, sezgiselliği (sezgisel kurallar, sezgisel yöntem) problemin durum uzayı büyük olduğunda çözüm aramasını sınırlayan bir araç olarak tanımlamışlardır.
• Arama algoritmalarında sezgi, hedefe ne kadar yakın olunduğuna dair bir tahmindir.
• Sezgisel arama algoritmaları aynı çözümü daha hızlı bulmayı amaçlar.

Sezgisel Arama Algoritmaları

• İlk En İyi Arama (Best-first Search)
• A* Arama
• Lokal Arama (Local Search Algorithms)
  • Tepe Tırmanma (Hill-climbing Search)
  • Rasgele Başlangıçlı Tepe Tırmanma (Random-restart Hill Climbing)
  • Paralel Tepe Tırmanma(Local Beam Search)
  • Benzetimli Tavlama (Simulated Annealing Search)
  • Genetik Algoritmalar

İlk En İyi Arama Algoritması (Best First Search)

• İlk adım olarak, kuyruk kök durumu içerir.
• Algoritma çalışmaya bulunduyu FALSE olarak işaretleyerek başlar.
• Kuyruk boş olmadığı ve hedef bulunmadığı sürece algoritma çalışmaya devam eder.
• Kuyruktan ilk durum çekilir ve hedef durum ise, bulundu TRUE olarak işaretlenir.
• Çekilen durumdan gidilebilecek tüm durumlar kuyruğun sonuna eklenir.
• Kuyruktaki durumlara bir değerlendirme fonksiyonuna göre puan verilir.
• Durumlar, bu puanlara göre küçükten büyüğe doğru sıralanır.
• Bu algoritma, hedefe en yakın gibi görünen duruma doğru ilerler.
• Örnek değerlendirme fonksiyonu, mevcut durumdan hedefe kuş uçuşu mesafesidir (SLD - Shortest Line Distance).
• Kuş uçuşu mesafesi, gerçek mesafeden daha kısa olamayacağından, bu yöntem iyimser bir yaklaşımdır.
• Amaç Arad'dan Bükreş'e gitmek olan Romanya haritası(aima.cs.berkeley.edu/figures.pdf)
• Algoritma her adımda tahmini olarak hedefe en yakın görünen duruma ilerler.
• Bükreş'e ulaşmak için farklı şehirler üzerinden geçilir.
• Algoritma, kuyrukta 6 eleman varken çalışmaya devam eder.

İlk En İyi Arama'nın Analizi

• Tam değildir, döngülere takılabilir.
• Zaman karmaşıklığı O(bm) dir, ancak iyi sezgisel kurallar büyük iyileşmeler sağlayabilir.
• Alan karmaşıklığı O(bm) dir, çünkü tüm durumlar hafızada tutulur.
• Optimal değildir.

A* Arama

• Kökten itibaren toplam maliyeti yüksek olan durumlara gidişi engellemeyi hedefler.
• Değerlendirme fonksiyonu: f(n) = g(n) + h(n)
• g(n): Kökten mevcut duruma (n) gelişin maliyeti
• h(n): Mevcut durumdan (n) hedefe gidişin tahmini maliyeti
• f(n): Kökten hedefe n'den geçilerek gidişin tahmini maliyeti
• DFS, Best First Search döngülere takılabilirken, BFS ve UCS takılmaz.
• A* algoritması, g(n) kullandığı için döngüleri hesaba katmaz, çünkü g(n) artar.
• h(n) iyimser ise (gerçek durumdan daha iyi tahmin ediyorsa) optimaldir.

8 Taş İçin Sezgisel Kurallar

• h1(n) = Yerinde olmayan taşların sayısı
• h2(n) = Taşların hedefteki yerlerine uzaklıkları toplamı (Manhattan mesafesi)
• h2, h1'den küçük olduğu için iyimserdir.
• Her taşın tek adımda yerine konulduğu varsayılır.

Baskınlık / Dominance

• Geçerli iki sezgisel kural için tüm durumlarda h2(n) ≥ h1(n) ise, h2 baskındır ve arama için daha uygundur.
• h2'nin kullanılması daha hızlı çözüm bulunmasını sağlar.
• h1 ve h2 farklı çözümler bulsa da, çözümlerin maliyetleri aynıdır.
• Çözümlere ulaşma maliyetleri farklı olabilir.

Esnetilmiş Problemler

• Orijinal problemden daha az kısıtlama içeren problemlere denir.
• 8 taş probleminde bir taşın istediği yere gidebilmesi h1(n)'i, komşusuna gidebilmesi h2(n)'i verir.

Yeni Problem

• Amaç: Tüm W'lerin B'lerin solunda olması.
• Operatörler:
• Bir taş yanındaki taşın diğer yanı boşsa üzerinden atlayabilir (maliyet 2).
• Bir taş yanındaki boş yere gidebilir (maliyet 1).
• Oluşturulacak H önerileri problemi çözmede yardımcı olacaktır.
• Enlemesine aramada ilk olarak başlangıç düğümü (S) ele alınır, ardından sırasıyla diğer düğümler ziyaret edilir.
• Derinlemesine aramada ise, başlangıç düğümünden başlayarak bir dal boyunca mümkün olduğunca derine inilir.
• Düşük maliyetli arama(uniform cost search)
• A* Arama f(n)=g(n)+h(n)

A*'ın İyiliği

• A* algoritmasında, eğer h fonksiyonu gerçek maliyetten daha düşük tahminler veriyorsa ve tüm maliyetler pozitifse, algoritma optimal çözümü bulur.
• G optimal ve G2 suboptimal çözümler olsun.
• Stack'te hem n (optimal yola götüren seçim) hem de G2 var.
• A*, G2'yi n'den önce açmaz; eğer f(n) < f(G2) ise, n daha önce seçilir.
• Stack'te n (optimal yola götüren seçim) ve G2 var.
• A*, G2'yi n'den önce açar mı (stack'ten çeker mi)?
• Eğer f(n)

Uygulama ve Özet

• A* algoritması kullanılırken, hafıza tüketimi önemli bir faktördür.
• Olayların daha az adım sürmesi, genellikle hafızanın daha az büyümesine neden olur.
• Sezgisel arama yöntemleri, problem hakkındaki bilgiden yararlanır.
• Sezgi (Heuristic), hedefe ulaşmak için kalan maliyetin tahminidir.
• İyi bir sezgi, arama süresini üstelden doğrusala indirir.
• A*, yapay zekada anahtar bir teknolojidir.
• Tek robotla keşif algoritması, hedefleri belirleme, iyiliklerini hesaplama, hedef seçme, robotu hedefe yönlendirme ve hedefte başa dönme adımlarını içerir.
• Çok robotla keşif algoritması, hedefleri belirleme, her robot için iyiliklerini hesaplama, robot-hedef eşlemesi yapma, eşlenmiş ikililer için yol bulma ve robotları hedeflere yönlendirme adımlarını içerir.