Optimal Duraklama(Optimal Stopping)

Donald Shoup, Los Angeles Times tarafından ‘parking rock star’ olarak tanımlanan ve UCLA’de şehir planlama profesörü olan Amerikalı bir mühendisdir. Elektronik Mühendisliği ve Ekonomi alanlarında lisans derecesine sahip olan Shoup doktorasını da yine Ekonomi alanında yapmış ve kariyerinin ilk yıllarını UCLA’in Hükümet ve Halkla ilişkiler Enstitüsü’nde araştırma ekonomisti olarak geçirmiştir. Bir süre sonra yine UCLA’de Şehir Planlama Doçenti olarak kariyerine devam etmiştir…

Günlük yaşamla ilgili ‘Algoritma’ kelimesinden bahsetmek garip görünebilir, ayrıca Algoritma kelimesi, insanlar için büyük verinin, büyük devletler ve kalburüstü teknoloji şirketlerinin sinsi planlarının en önemli silahı olduğu çağrışımını uyandırabilir. Fakat algoritmalar kabaca, bir problemi çözmek için takip edilen adımlar bütünüdür ve tarihi, teknoloji ya da bilgisayarlardan çok daha eskiye dayanır(bkz. İranlı matematikçi Harezmi). Optimal Duraklama ise bir çok seçenek arasından mümkün olan en iyisine karar vermek için kullanılan belirli algoritmaların uygulanabileceği matematiksel bir karar teorisidir. Bu teori ‘Araştırmaya ne zaman son verilmeli?’ soruna bir cevap arar.

Optimal Duraklama teorisi, mevcuttaki seçeneklerin %37'sini uygun seçimi yapabilmek için örneklem olarak kullanır. Bu %37'lik dilim içindeki en iyi seçenek belirlenir ve örneklem dışında kalan seçenekler arasında bundan daha iyi olan ilk seçenek seçilir ve seçim süreci sonlandırılır.

Optimal Duraklama teorisinin bir çözüm ürettiği ve adından en çok bahsedilen sorunlardan birisi Sekreter Problemi’dir. Açık olan sekreterlik pozisyonu için yapılan yüzlerce iş başvurusunun, tek tek değerlendirilmesi uzun zaman alacaktır ve bu süre boyunca yapılması gereken işler vardır. 100 iş başvurusunun olduğu kabul edilen bir senaryoda adayların hepsiyle tek tek mülakat yapmak yerine, başvurular arasından seçilen rastgele 37 kişinin niteliklerini, en iyi adayı seçmek adına bir denge noktası belirlemek için kullanmak, mutlak bir verinin olmadığı bu örnek için gayet ideal bir yaklaşımdır. Ancak binlerce başvurunun olduğu bir senaryoda adayların %37'sini incelemek bile maliyetli bir yöntem olacağından bu noktada bir mutlak veri -Sekreter adaylarının teknik yeterliliklerini(daktilo, klavye kullanma becerilerini) test etmek gibi- elde etmek gerekebilir. Neticede ise teknik olarak yeterli olan adaylar arasında yine bir örneklem oluşturup seçim yapılabilir.

Bu teori ile ilgili bir diğer bilindik örnek ise Profesör Shoup’un alanında ünlü olmasını sağlayan ‘The High Cost of Free Parking’ kitabında karşımıza çıkan araba park etme problemidir. Bu problem, ‘Arabayı park etmeye karar vermek için ne kadar boş park yeri geçilmelidir?’ sorusuna cevap arar. Shoup’un modellemesine göre ideal park yeri; park yerinin fiyatı, yürünecek mesafenin getirdiği zaman kaybı ve zahmet, yer ararken harcanan zaman ve harcanan yakıt arasındaki dengeyi optimize etmelidir. Bununla birlikte park etmeyle ilgili bir çok sorun tek bir kavramda birleşmektedir: Doluluk oranı.

Doluluk oranının park etme stratejisi üzerindeki etkisi, bunu bir optimal duraklama problemi olduğunu bize gösterir.

Varmak istediğiniz konuma yaklaşmaya başladığınızda gördüğünüz ilk boş park yerine park etmek mantıklı mıdır? Yoksa varış noktasına yaklaştığınızda yürünecek mesafe daha kısa olduğundan daha uygun bir park yeri bulmuş olur musunuz? yada bulamamış.

Cevaplar doluluk oranına bağlı olarak değişmektedir. Doluluk oranı, park yerinin hedefe uzak olsa da bulunan ilk park yerine park etmek ya da en yakın park yerini bulmak için zaman ve yakıt harcamak arasındaki en optimize noktayı belirlemek için önemli bir değişken haline gelir. Bu durumda amaç, aracı park ettikten sonra hedef konuma yürünecek mesafeyi en aza indirmek aynı zamanda yakıt ve zaman masraflarını da olabildiğince düşük tutmaktır. Dolayısıyla önce ara sonra seçim yap -ki bu Optimal Duraklama teorisinin temel prensibidir- yaklaşımıyla ideal park yerine ulaşmaya çalışmak gerekir. Bu yaklaşımın, teorik olarak fazladan yakıt harcama, zaman kaybetme ve yürümenin zahmetine girme gibi durumları ortadan kaldırması beklenir. Brian Christian ve Tom Griffiths, ‘Algorithms to Live by’ kitabında -yazı, bu kitabın ilk bölümünden esinlenir- Profesör Shoup’a bu yaklaşımın UCLA’e doğru giderken Los Angeles trafiğinde işe yarayıp yaramadığını sorduklarını belirtir ve profesörden şu yanıtı aldıklarını ekler:

• Bisiklet kullanıyorum.