Karınca Kolonisi Optimizasyon Algoritmaları
12 Temmuz 2007
KARINCA KOLONİSİ OPTİMİZASYON ALGORİTMALARI
Bu algoritmalar ,karıncaların doğal davranışlarını taklit ederek sürekli ve süreksiz problemleri çözmek için kullanılır. Bu algoritmaların en çok kullanıldığı problem TSP yani seyahat eden tüccar (travelling salesman problem) problemidir. Biz daha sonra bir Japon bilim adamı ve arkadaşları tarafından ortaya atılan TACO (touring ant colony optimisation algorithm) yöntemini sürekli fonksiyonların optimizasyonu için kullanacağız.
Karınca kolonisi yöntemi pozitif geri beslemeli bir yöntemdir. Bu yöntemde temel alınan karıncaların davranışını biraz açıklarsak , bir karınca evi(nest) ile besin(food) kaynağı arasında gidip gelmek için çevre şartlarına göre gidebileceği yolları belirler. Bu yollardan birinden geçen ilk karınca yolun kısalığına göre (yol kısa ise daha çok olmak üzere) yola koku bırakır bu kokuya phremone denir. Daha sonra gelen karıncalar da aynı şeyi yaparak yolda devam ederler. Bir karınca iki yolun birleştiği noktada bir yol tercihi yapacaktır. Bu yolun seçimini öncelikle yoldaki koku miktarına, ikinci derecede ise rasgelelikle yapar yani bir yol hem koku miktarına hem de randomize bir ölçütle tercih edilir. Eğer yol sadece koku ile seçilecek olsaydı bütün karıncalar sadece ilk geçen karıncanın geçtiği yolları tercih edecek ve bu nedenle ilk seçilen yola kıyasla daha kısa yolları keşfetme imkanını bulamayacaktı.
Görüldüğü gibi bu şekilde kısa yollarda daha fazla koku bulunacak ve bir karıncanın bu yolu seçme ihtimali artacaktır. Daha geniş manada ise bu algoritmalarda yola bırakılan kokunun artması durumunda bu kokuyu azaltmak için yoldan karınca geçtikten sonra veya belirli bir zaman periyodu sonrasında belirli miktarda koku buharlaşması(phremone decay) olmalıdır. Bu buharlaşma ile daha değişik yol kombinasyonu ve dolayısıyla daha kısa bir yol bulma ihtimali doğacaktır. Bunun dışında her karıncanın bir hafızası olmalı bu şekilde her karınca attığı en iyi turu hafızasında tutar.
Daha genel baktığımız karınca kolonisi algoritmalarını daha özelleştirirsek önce bir TACO yöntemine bakalım.
TACO yönteminde bir karınca şekilde görüldüğü üzere n adet seçim yaparak 2n adet yoldan tercih eder ,her seçimden sonra daha önce seçtiği yolların 2lik sistemdeki değerliklerini 10luk sisteme çevirerek koku miktarını hesaplar ve seçtiği yola koku bırakır. Böylece bir karınca en yüksek değerlikli bitten en düşük değerlikliye yani 10luk sistemde ondalıktan küsurata doğru seçim yapar. Bu yöntem için koku miktarının hesaplanması şöyledir:
burada Q , koku yayma katsayısı olup optimizasyon işlemi sırasında değiştirilerek en iyi değer bulunur. f(x) fonksiyonu ise optimize edilecek fonksiyondur.
Bir değişken için yapılacak işlemin diyagramı ise aşağıdaki gibidir:
optimize edeceğimiz fonksiyon birden çok değişkenlidir. İşlem bütün karıncalar yolu takip ederek sonuca ulaştığında biter. TACO da buharlaşma yani koku azalması yoktur. Ancak Gaziantep üniversitesinde yapılan çalışmalarda koku buharlaşması kullanılmıştır. Bu çalışmalar daha iyi sonuç vermiştir.
Uğur SAYNAK-Temmuz 2002
Kategori: Bilim