Tabu arama(TA), başlangıçta tümleşik optimizasyon problemleri için geliştirilmiş son sezgisel yaklaşımlardan birisidir. TA bu tür problemlere uygulandığında başarılı bir performans göstermiştir. Ancak TA’ nın sürekli optimizasyon problemlerinin çözümüne katkıları, tavlama benzetimi (simulated annealing) algortiması ve genetik algoritmalar gibi diğer sezgisel yaklaşımlarla kıyaslandığında hala oldukça sınırlıdır [1]. Bu çalışmada sürekli küresel optimizasyon problemlerinin çözümüne yönelik bir TA yaklaşımı geliştirilmiş, özellikle doğrusal olmayan minimizasyon problemleri çalışma kapsamı içinde tutulmuştur.

TA çözümde bir değişiklik yapmayı kabul etmeden önce mevcut çözümlerin komşularının, başka bir ifadeyle yakın çözümlerin bulunduğu kümede arama yapar. Çözüm uzayında yapılabilecek mümkün hareketler kümesinin üretilmesi ve bunlardan birisinin kabul edilmesi iterasyonlar boyunca devam eder [2]. TA’ nın temelleri, uygunluk sınırlarını veya doğal olarak bariyer vazifesi yapan lokal optimalliği aşmak ve sistematik olarak kısıtları zorlayarak yasak alanlarda araştırma yapmaya izin vermek için dizayn edilmiş metotlara dayanır. Bu tür prosedürlerin ilk örnekleri, sistematik olarak uygunluk koşullarını zorlayan vekil kısıt metotlarını (surrogate constraint methods) ve düzlem kesme yaklaşımlarını (cutting plane approaches) temel alan sezgisel yaklaşımları kapsamaktaydı. TA' nın modern biçimi Glover ile şekillenmiştir. Metodun bazı türetilmiş fikirleri ise Hansen tarafından geliştirilmiştir [3].

Glover’ in ilk sunumundan bu yana TA alanında çok sayıda çalışma ortaya çıkmıştır. Bu çalışmaların büyük çoğunluğu türetilmiş optimizasyon problemleri ile ilgiliyken, sürekli optimizasyon problemlerine yönelik birkaç çalışma olmuştur [1]. Battiti ve Tecchiolli [4] “sürekli tepkili Tabu Arama” (continuous reactive Tabu search) başlıklı ilgi çekici bir sürekli TA metodu sunmuştur. Metotları, en umut verici, başka bir ifadeyle içerisinde optimuma en yakın çözümleri barındıran kutucukların yerini belirlemeye ve daha sonra lokal arama için bu kutucuklar içerisinden başlangıç noktası seçmeye çalışmaktadır. Bu çalışmada buna benzer bir yöntem kullanılmıştır.

TA HAFIZA ELEMANLARI

Hafıza kavramı, özellikle geniş alanlı hafızaya sahip yüksek düzeyli TA’ da olduğu gibi bir tür öğrenme süreci içinde kullanıldığında TA’ da temel role sahiptir. Kuvvetlendirme ve çeşitlendirme şemalarında etkili hafıza kullanımı, TA’ yı akıllı bir arama tekniği yapar [1].

TA lokal optimalliğin ötesindeki çözüm uzayını araştırmak için lokal sezgisel arama prosedürü sunan bir tekniktir. TA’ nın ana parçalarından birisi uyarlanabilir hafızasıdır. Böylece daha esnek bir arama davranışı ortaya çıkar. Bu sebeple hafıza temelli stratejiler TA yaklaşımlarının ayırt edici özellikleridir [5].

Tabu yapısı (tabu structure) olarak da bilinen hafıza listesinden bu çalışmada iki adet kullanılmıştır. Daha önce de ifade edildiği gibi, bu çalışmada TA algoritması öncelikli olarak en umut verici kutucukların yerini belirlemeye çalışmaktadır. Bu durumda minimize edilmeye çalışılan amaç fonksiyonundaki her bir değişken için 10 kutucuk oluşturulmuştur. Kutucuklar farklı aralıklardaki gerçek sayılarla doludur. Örnek olarak aşağıdaki fonksiyon alınmıştır:

min f(x, y) =x^2-4x+y^2-y-xy

Amaç fonksiyonunda görüldüğü gibi iki değişken vardır. İki adet tabu yapısı olduğundan bahsedilmişti. Söz konusu iki yapı her bir değişken için geçerli olduğundan, toplam dört tabu yapısı olmaktadır. Tabu yapıları da 10 kutucuktan oluşmaktadır. Kutucuk sayısı azaltılıp çoğaltılabilir. Bu, problemin yapısına ve beklenen çözüm süresinin uzunluğuna bağlıdır. Üçüncü kısımda görüleceği gibi kutucuk sayısının arttırılması güvenilir sonuç elde edilebilmesi için gerekli olan iterasyon sayısının artmasına neden olacaktır. Böylece çözüm süresi uzayacaktır.

NELDER-MEAD LOKAL KOMŞU ARAMA STRATEJİSİ

Geniş bir tanım aralığı içerisinde tesadüfi olarak atanan değişken değerleriyle hatalı sonuçlar elde etme ihtimali artacağından, bu çalışmada tesadüfi atanan değişken değerleri Nelder-Mead algoritması ile lokal en iyi komşuya doğru yaklaşacak şekilde değişmektedir.

Birden fazla değişkenli fonksiyonların lokal minimumunu bulmak için oldukça basit bir yöntem Nelder ve Mead tarafından geliştirilmiştir. İki değişken için yapı bir üçgen biçimini alır ve metot üçgenin köşelerindeki fonksiyon değerlerini karşılaştırarak arama yapar. Fonksiyon değerinin en büyük olduğu en kötü köşe reddedilir ve başka bir köşeyle yer değiştirilir. Yeni üçgen biçimlendirilir ve tekrar arama devam eder. Köşelerdeki fonksiyon değerleri ve üçgenin alanı gittikçe küçülür [6].

Referanslar

[1] Hedar, A., R., Fukushima, M.,  Tabu Search directed by direct search methods for nonlinear global optimization, European Journal of Operational Research, 170, s: 329-349, (2006).

[2] Pukkala, T., Heinonen, T., Optimizing heuristic search in forest planning, Nonlinear Analysis: Real World Applications, 7, s: 1284-1297, (2006).

[3] Reeves, C., Modern Heuristic Techniques for Combinatorial Problems, McGraw-Hill Book C., London, 1995

[4] Battiti, R., Tecchiolli, G., The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization, Annals of Operations Research, 63, s: 153-188, (1996)

[5] Duarte, A., Marti, R., Tabu search and GRASP for the maximum diversity problem, European Journal of Operational Research, 178, s:71-84, (2007)

[6] Mathews, J., H., Fink, K., K., , Numerical Methods Using Matlab, Prentice-Hall Inc., New Jersey, 2004.

Kaynak:Cura, T. (2008). Doğrusal olmayan küresel optimizasyon problemleri için tabu arama algoritmasının kullanılması. Journal Of The School Of Business Administration, Istanbul University, 37(1), http://www.ifdergisi.org/index.php/ifdergi/article/view/20/5