0 Optimizasyon ve Arama Yöntemleri

Tweet

Optimizasyon teorisi, nicel olarak en iyiyi bulmayı ve bunun yöntemlerini inceler. En iyinin nasıl tanımlanacağını ve ona nasıl ulaşılacağını araştırır. Literatürde yaygın olarak kullanılan üç tip optimizasyon ve arama yöntemi vardır: hesaba dayalı, sayıma dayalı ve rastgele yöntemler (Goldberg 1989).

Hesaba dayalı optimizasyon ve arama yöntemleri üzerinde oldukça çalışılmıştır. Dolaylı ve dolaysız olmak üzere iki ana kategoride incelenmektedir. Dolaylı yöntemler, amaç fonksiyonun eğimini sıfıra eşitleyen ve genellikle doğrusal olmayan denklemler kümesinin çözümü ile bütün yönlerde yerel en iyiyi arar. Dolaysız yöntemler ise, yerel eğim fonksiyonuna bağlı olarak ve eğim yönünde hareketle, yerel optimumu bulmaya çalışır. Tepeye tırmanma işlemi olarak da adlandırılan bu yöntemde, yerel optimumu bulmak için, fonksiyonda mümkün olan en dik yönde tırmanılır.

Hesaba dayalı yöntemler için kolay, tek tepeli bir fonksiyon

Her iki yöntemin ortak özelliklerinden birisi, aranılan optimumun yerel olmasıdır. O an bulunulan noktadan yola çıkarak, komşu noktalar arasından en iyisi bulunmaya çalışılır. Yerel komşuluk ilişkisi ile yapılan aramada, genel en yüksek tepe yerine, şekildeki gibi yerel alçak bir tepe bulunabilir.  Böyle durumlarda, aramayı yeniden başlatmak veya genişletmek gerekebilir. Hesaba dayalı arama yöntemlerinin bir başka ortak özelliği, aramada kullanılan fonksiyonların türevlerinin var olmasına veya eğimlerinin iyi tanımlanabilmesine bağlıdır (Masri et al 1999). Türevler için sayısal yaklaşım yapılsa bile sorunlar oluşabilmektedir (Rio et al 2000). Fonksiyonların süreksizliği, çok modluluğu ve gürültülü arama uzayları hesaba dayalı yöntemlerin uygulanmasını zorlaştırmaktadır. Bu nedenle, hesaba dayalı arama yöntemleri bir çok problem için uygun sonuç veremez (Chakroborty et al 1995).

Hangi tepe ikilemini gösteren, çok tepeli fonksiyon

Bir başka tip arama yöntemi olan sayıma dayalı yöntemlerde,  sonlu arama uzayında veya ayrıklaştırılmış sonsuz arama uzayında, her defasında bir nokta olmak üzere arama uzayının her noktasında amaç fonksiyon değerine bakılır. Bu tip yöntemler, basitliği ve küçük boyutlu problemlerde insana daha yatkın olmasına rağmen, büyük boyutlu problemlerde etkili olamaması nedeniyle gürbüz değildirler. Her defasında bir noktaya bakıldığı için, büyük uzaylarda arama yapılırken bazı pratik bilgilere ihtiyaç duyabilirler. Sayıma dayalı tekniklerde,  problemler makul boyutlara bölünmelerine rağmen, boyut problemi açısından eleştirilmektedir (Koumousis and Arsenis 1998).

Rastgele arama yöntemleri, hesaba dayalı ve sayıma dayalı yöntemlerin sorunları nedeniyle, araştırmacılar tarafından giderek artan bir şekilde kullanılmaktadır. Uzun çalıştırmalarda, rastgele yöntemlerin sayıma dayalı yöntemlerden daha farklı olmadığı kabul edilmektedir. Bu nedenle, rastgele arama yöntemleri tamamen kabullenilmemiştir. Rastgele arama yöntemleri, arama uzayındaki her noktayı belli bir yönü ve ölçütü olmaksızın ararlar. Burada, rastgele arama ile randomize yöntemlerin aynı yöntemler olmadığına dikkat edilmelidir.  Rastgele aramayı, yönsüz arama olarak algılamamak gerekmektedir. Rastgele seçim işlemini, oldukça kapsamlı arama yapmakta bir araç olarak kullanan genetik algoritmalar bu yöntemlere bir örnektir (Koumousis and Arsenis 1998). Rastgele seçim işleminin  yönlendirilmiş arama işleminde  bir araç olarak kullanılması, ilk bakışta çok garipmiş gibi görünse de, doğadaki örneklerinden esinlenerek geliştirilmiştir (Cao and Wu 1999, Pattnaik et al 1998). Bir başka yaygın arama tekniği olan benzetilmiş tavlama da, minimum enerji seviyesini bulmak için yine rastgele işlemleri kullanmaktadır (Palshikar 2001).