Sezgisel Fonksiyonlar (Heuristic Functions)

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, sezgisel algoritmalar (heuristic algorithms) tarafından kullanılan sezgisel fonksiyon (heuristic function) kavramını açıklamak ve bazı zaviyelerden tasnif etmektir.

1. Baskınlık Özelliği (Dominance)
2. Tutarlılık Özelliği (Consistent, Monotone)
3. Makbul Özelliği (Admissible)

Sezgisel algoritma, en basit anlamda, bir sezgisel algoritmanın, problem bağımlı olarak bazı tahminlerde bulunmasıdır. Örneğin daha önce yazdığım A* (A yıldız, A Star) algoritmasında, bir yol bulma örneği vermiştim. Bu algoritmadaki amaç, hedef düğüme (node) en kısa ulaşan yolu bulmaktı. Yollar karışık olmasına karşılık, hedefe giden kuş uçuşu mesafeyi sezgisel bir fonksiyon olarak kabul etmiştik:

Yukarıdaki şekilde, siyah renkle yazılı olan sayılar, düğümler arası mesafeyi gösterirken, düğümlerin üzerinde kırmızı renkle yazılan sayılar, o düğümün, hedefe olan kuş uçuşu mesafesini vermektedir. Bu durumda en kısa yolu bulmayı hedeflediğimiz bu problemde, sezgisel olarak bir fonksiyon tanımlamış oluyoruz ve problem hakkında bir bilgiyi, problemin çözümünde avantaj sağlaması için kullanıyoruz.

Farklı bir problem ve farklı bir fonksiyon tanımı yaparak konuyu daha iyi izah etmeye çalışalım. Örneğin 8 bulmacası (8 puzzle) olarak bilinen, aşağıdaki klasik oyunu ele alalım.

Yukarıdaki temsili resimde görüldüğü üzere, 8 bulmacasının bir başlangıç durumundan bir hedef durumuna kadar her adımda bir kutuyu boş olan hücreye kaydırmak suretiyle oynanması amaçlanmaktadır. Amacımıza yönelik olarak bir bilgisayar programı geliştirmek için sezgisel algoritmalardan (heuristic algorithms) faydalanmak istiyoruz. Bu durumda kullanabileceğimiz sezgisel algoritmalarda en önemli etkenlerden birisi de sezgisel fonksiyonumuz olacaktır. Yani probleme has bir fonksiyon geliştireceğiz ve bu fonksiyonla her adımda karar vermeye çalışacağız.

Bu aşamada iki fonksiyondan birisi önerilebilir:

• Taşların kaç tanesinin yerinde olmadığı
• Taşların bitiş durumunda olması gereken yere olan uzaklığı (kare mesafesi, manhattan distance)

Yukarıdaki iki farklı fonksiyon için de, yine yukarıda verilen şekildeki mesafeleri hesaplayalım.

ilk fonksiyonumuz olan, yanlış yerdeki taş sayısını hesaplamak için, yerinde olmayan taşları listeleyelim: 1,2,3,4,5,6,7,8 taşlarının tamamı hedef durumda olması gereken yerde değil. Burada boşluk hücresinin konumunu da sayarsak fonksiyon değeri olarak 9 buluruz.

İkinci fonksiyonumuza göre taşların, hedef konumuna olan mesafelerini sırasıyla listeleyelim:

1. 3
2. 1
3. 2
4. 2
5. 2
6. 3
7. 3
8. 2

Yukarıda, her taşın hedef konumuna olan mesafesi verilmiştir. Daha iyi anlaşılması açısından, örneğin 1 numaralı taş başlangıç durumunda sağ alt köşedeyken, bitiş durumunda üst ortaya gelmesi isteniyor. Bu taşın, tahtada hiç başka taş olmasaydı, başlangıç durumundan hedef durumuna gelebilmesi için yapılan hamle sayısı 3’tür. Yukarıdaki listede de her taş için bu değer sırasıyla yazılmıştır.

Fonksiyonumuzun toplam değeri : 3+1+2+2+2+3+3+2 = 18 olarak bulunur

Yukarıda, aynı problem için iki farklı sezgisel fonksiyon örneği verdik. Şimdi bu iki fonksiyonu karşılaştırarak özelliklerini açıklamaya çalışalım

1. Baskınlık ( Dominance ) Özelliği

Bu özellik, aynı problemin, aynı algoritma ile sezgisel olarak çözümü sırasında birden fazla fonksiyon bulunuyorsa, bu fonksiyonlar arasında seçim yapma kriterini belirler. Buna göre bir fonksiyonun alabileceği değer kumesi (fonksiyonun menzil uzayı (range) ) ne kadar geniş ise o kadar baskın fonksiyondur ve o derecede tercih edilmelidir.

Örneğin yukarıda, 8 bulmacası için iki farklı fonksiyon tanımı yaptık. Bu fonksiyonlardan ilki olan, yanlış yerdeki taş sayısı, en fazla 9 değeri alabilir. Şayet taşlardan bir tanesi doğru yerdeyse, fonksiyon değeri düşerek 8 değerine sahip olacaktr. Dolayısıyla fonksiyonun tanımlı olduğu, ve sonuç olarak döndürebileceği değerler 0 ile 9 arasındadır.

İkinci fonksiyonumuz olan manhattan mesafesi ise, taşların azami mesafede olması durumunda her taş için ayrı ayrı olarka 4 değerine sahip olabilir. (hedef durumunun (goal state) saat yönünde 4 kere çevrildiğini düşünün) ve 8 taşımız olduğu için 4 x 8 = 32 değeri, fonksiyonun döndürebileceği azami değerdir. Dolayısıyla fonksiyon 0 ile 32 arasındaki herhangi bir değeri döndürebilir.

İki fonksiyon kıyaslandığında, ilk fonksiyonun 9 ihtimalden birisini döndürebildiği, ikinci fonksiyonun ise 32 ihtimalden birini döndürebildiği görülmektedir. Bu durumda, ikinci fonksiyon, ilkine nazaran baskın fonksiyon olmakta ve ikisinden birisinin tercih edilmesi gerektiğinde, ikincisinin tercih edilmesi daha doğru olmaktadır.

Yukarıdaki baskınlık durumunun daha iyi anlaşılması için iki fonksiyon arasındaki farkı anlatmaya çalışalım. Çok kaba anlamda, ikinci fonksiyon 32 farklı değer döndürürken, ilk fonksiyon 9 farklı değer döndürebilmektedir. Bunun anlamı, ikinci fonksiyonun ayırt ettiği bazı durumları, ilk fonksiyonun ayıramamasıdır. Örneğin ilk fonksiyondaki her değer için ikinci fonksiyonda 3-4 farklı değer bulunabilmektedir. Diğer bir deyişle, 9 ihtimalden bir tanesi, 32 ihtimalden bir kaç tanesine karşılık gelmekte, bu bir kaç farklı durum da fonksiyonun sonuca ne kadar yaklaşıldığını ölçmede ayırım oluşturmasını sağlamaktadır.

Daha net bir şekilde farkını anlatacak olursak, bulmacanın verildiği şekildeki, 8 ve 5 numaralı karolar, başlangıç durumunda yer değiştirmiş olsaydı, ilk fonksiyonumuza göre, yerinde olmayan taş sayısı yine 9 olarak bulunacaktı. Ancak ikinci fonksiyonumuzda 18 yerine 20 değeri bulunmuş olunacaktı. Bu değişim, ilk fonksiyona göre karar vermemize imkan tanımazken, ikinci fonksiyon, aralarında seçim yapma imkanı sunacaktı.

2. Tutarlılık (Consistent, Monotone)

Tutarlılık kavramını anlamak için üçgen eşitsizliği halini anlamamız gerekir. Çok basit anlamda, bir üçgenin üç kenarı a b ve c olmak üzere, herhangi iki kenarının toplamı, üçüncü kenardan büyük olmalıdır. Bu hale üçgen eşitsizliği hali denir ve tersten okunursa, herhangi bir kenarın, diğer iki kenarın toplamından küçük olması olarak yorumlanabilir.

Şimdi bu çok basit kavram olan üçgen eşitsizliğinin sezgisel fonksiyonla nasıl bir ilişkisi var diye sorabilirsiniz. Tutarlılık durumu, gayet basittir aslında, basitçe bir arama şeklinde (graph) herhangi bir düğümün aldığı sezgisel fonksiyon değeri, çocuğunun aldığı sezgisel foknsiyon değeri ile toplandığında çıkan sonuç çocuğunun çocğuna doğrudan giden değerden daha büyük olmalıdır. Durumu aşağıdaki şekilde görsel olarak ifade edelim:

Yukarıdaki şekilde görüldüğü üzere en sağdaki düğüme giden ve n_i düğümünden başlayan iki yol bulunmaktadır. Bu yollardan birisi doğrudan gitmekte olup, ağırlık değeri (weight) h(n_{i) olarak ifade edilmiştir. İkinci yol ise nj üzerinden geçen yol olup, önce c(ni, nj) (ni ile nj arasındaki gerçek mesafe (sezgisel değil) ) mesafesi gidilmekte ardından nj için sezgisel bir değer bulunmaktadır. İşte üçgen eşitsizliği, bu iki değer arasında, ikincisinin daha büyük olmasını gerektirir. Ki bu durum, yukarıdaki şekilde de aşağıdaki şekilde ifade edilmiştir:}

h(n_i) <e; c(n_i, n_j) + h(n_j)

Şayet bir sezgisel fonksiyon yukarıdaki bu şartı her durum için sağlıyorsa tutarlı (consistent) sağlamıyorsa tutarsız (inconsistent) olarak tasnif edilebilir.

Fonksiyonların, tutarlı olması tercih edilir bir durumdur, bunun sebebi bir düğümden diğerine gidildiğinde ödenen maliyetin sezgisel fonksiyona yansımasının, sonucu bulmada etkisi olmasıdır. Şayet bir fonksiyon tutarsız ise, mesafe giderken harcanan maliyetin, sezgisel fonksiyona yansımadığı, en az bir durum var demektir ki bu da problemin çözümünde sorunlarla karşılaşılmasını (en azından tutarlı bir fonksiyona göre daha geç sonucun bulunmasını) beraberinde getirir.

Tutarlı bir fonksiyonun, aynı zamanda tektonlu (monotone) olarak isimlendirilmesinin sebebi ise, yukarıda izah edildiği üzere bir fonksiyonun tutarlı olması halinde, her düğümün tek bir kere ziyaret edilmesidir. Şayet bir fonksiyon tutarsız ise (inconsistent) bu durumda, aynı düğüm, arama işlemi sırasında, birden fazla kere ziyaret edilebilir. İşte bu anlamda tutarlı fonksiyonlar aynı zamanda tektonlu (monotone) olarak isimlendirilir.

3. Makbul (Macaiz, Kabul Edilebilir, Admissable)

Literatürde admissable olarak geçen durumdur. Bir sezgisel algoritmanın kabul edilebilir olup olmadığını (makbul) belirler. Makbul, hali, kısaca bir sezgisel fonksiyonun, herhangi bir mesafe için, gerçek mesafeden her zaman daha küçük değer vermesidir. Örneğin herhangi bir düğüm n için gerçek mesafe f(n) iken sezgisel fonksiyon olan h(n) değeri, her zaman için h(n) <e; f(n) şartını sağlamalıdır

Şayet bütün düğümler, yukarıdaki bu h(n) <e; f(n) şartını sağlıyorsa, bu sezgisel fonksiyona makbul (admissible) ismi verilebilir. Şayet sağlamayan tek bir durum varsa, bu sezgisel fonksiyonun makbul olmadığını (gayri makbul, non-admissible) söyleyebiliriz.

Yukarıdaki bu yaklaşımın sebebi, gerçek değerden daha yüksek bir sezgisel değer elde edildiği anda, bu sezgisel değerin, en iyi çözüm olan gerçek değeri perdelemesidir. Yani bir sezgisel algoritmada, makbul olmayan bir sezgisel fonksiyon kullanılırsa, bu fonksiyon için, sezgisel algoritmamız en iyi çözümü bulamayabilir.